Research map / Federated learning and privacy / Differential privacy
Improving Private Random Forest Prediction Using Matrix Representation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a matrix representation of random forest training and prediction (Matrix Random Forest) that enables optimized Laplace-mechanism noise allocation across all trees and inference queries for differentially private random forests.
Problem
Differentially private random forests suffer a utility gap: equal per-tree budget allocation degrades accuracy as trees grow, and subsample-and-aggregate prediction degrades with many inference queries.
Approach
Encode root-to-leaf decision paths of all trees as rows of a matrix and inference queries as a matrix, so that privacy can be analyzed jointly via the matrix mechanism; this yields optimized strategy matrices that allocate DP noise finely for both DP batch training (leaf values) and DP batch prediction (vote counts).
Key results
- DP batch training and batch prediction reach about 85% accuracy at epsilon=2 on the Car dataset when predicting 345 test samples with 128 random decision trees, exceeding existing solutions by about 30%.
- Accuracy improvements of 20-40% on small to medium datasets and 10-20% on larger datasets (Heart, Mushroom, Adult) relative to Laplace-based baselines.
- Applying the matrix representation to subsample-and-aggregate improves accuracy by up to 50%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use matrix-optimized noise allocation instead of the compared baseline techniques | DP batch training and DP batch prediction · Small to medium-sized datasets | accuracy: 20-40% | Helped |
| Use matrix-optimized noise allocation instead of the compared baseline techniques | DP batch training and DP batch prediction · Heart, Mushroom, and Adult | accuracy: 10-20% | Helped |
| Use DP batch training or DP batch prediction | Random decision trees · Car test set (345 samples), ϵ = 2, 128 trees | accuracy: 85%; exceeding the accuracy of existing solutions by 30% | Helped |
| Use matrix-optimized batch prediction instead of equal per-query privacy budget allocation | Random decision trees · Car, increasing numbers of inference queries | accuracy: 30% accuracy for 100 samples; 90% for 1000 samples | Helped |
| Increase the number of trees | DP batch training · Car, ϵ = 2, h = 4 | accuracy | No clear effect |
| Increase the number of trees | DP training with the Laplace mechanism · Car, ϵ = 2, h = 4 | accuracy | Hurt |
| Increase the number of trees | Disjoint DP training with the Laplace mechanism · Car, ϵ = 2, h = 4 | accuracy | Hurt |
| Apply matrix-optimized batch prediction within subsample-and-aggregate instead of the existing approach | Subsample-and-aggregate · Car | accuracy: up to 50% | Helped |
Surprising findings
- Accuracy of DP batch training does not degrade as the number of trees increases, unlike equal-budget Laplace baselines whose accuracy falls with more trees.
- Existing subsample-and-aggregate accuracy drops to about 30% at 100 inference queries, whereas DP batch prediction stays around 90% even at 1000 queries.
Limitations
- Noise optimization overhead can be substantial for large feature domains, requiring feature subsampling and multiple ensembles.
- Results rely on the Laplace mechanism and random decision trees rather than greedy tree-building methods.
Experimental setup
Datasets: Car Iris Balance Heart Mushroom Adult
Benchmarks: Car Iris Balance Heart Mushroom Adult
Metrics: test accuracy runtime (sec) mean squared error of strategy query answering
Baselines: Laplace mechanism batch training disjoint-tree Laplace training subsample-and-aggregate Extra-Trees (non-private)
Builds on: Matrix Mechanism random decision trees subsample-and-aggregate Laplace mechanism
Closest papers by meaning
- Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees (NeurIPS 2026 · similarity 0.89)
- Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation (NeurIPS 2026 · similarity 0.85)
- Privacy Amplification for Matrix Mechanisms (ICLR 2024 · similarity 0.85)
- Trained Random Forests Completely Reveal your Dataset (ICML 2024 · similarity 0.85)
- Certification for Differentially Private Prediction in Gradient-Based Training (ICML 2025 · similarity 0.85)
- Near-Exact Privacy Amplification for Matrix Mechanisms (ICLR 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.