Research map / Federated learning and privacy / Privacy attacks and secure learning
DynFrs: An Efficient Framework for Machine Unlearning in Random Forest
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 DynFrs, an exact machine-unlearning framework for Extremely Randomized Trees that combines per-sample tree subsampling (OCC(q)) with a lazy-tag mechanism that defers subtree reconstruction until a query arrives.
Problem
Efficient exact machine unlearning (and continual addition) for Random Forests, which existing methods handle poorly for sequential, batch, and online mixed request streams.
Approach
Each sample is assigned to only ceil(qT) trees so a deletion touches a small fraction of the forest, and a lazy tag on nodes defers subtree retraining until a query traverses them, so only the query path is rebuilt; ERT's few candidate splits make best-split changes rarer.
Key results
- Sequential unlearning achieves a 22x to 523x speedup over DaRE across datasets (q=0.1 and q=0.2).
- Batch unlearning runtime for 100 samples on Higgs is 642 ms versus 145386 ms for OnlineBoosting and 165122 ms for DaRE.
- On 6 of 9 datasets DynFrs (q=0.2) has the best predictive performance; e.g., Synthetic AUC 0.9454 vs DaRE 0.9451.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DynFrs with q=0.2 instead of the strongest predictive baseline | ERT random forest · Purchase, Vaccine, Adult, Bank, Heart, Diabetes, NoShow, Synthetic, and Higgs | AUC-ROC or accuracy | Mixed |
| Use DynFrs for sequential unlearning instead of DaRE | Random Forest unlearning · All evaluated datasets | unlearning speedup: 22× to 523× | Helped |
| Use DynFrs for single-sample unlearning instead of DaRE | Higgs · Higgs, 1-sample unlearning | runtime (ms): 174{ $\pm135$} -> \textbf{1.60}{ $\pm1.8$} | Helped |
| Use DynFrs for 10-sample unlearning instead of DaRE | Higgs · Higgs, 10-sample unlearning | runtime (ms): 20119{ $\pm31897$} -> \textbf{32.1}{ $\pm8.6$} | Helped |
| Use DynFrs for 100-sample unlearning instead of OnlineBoosting | Higgs · Higgs, 100-sample unlearning | runtime (ms): 145386{ $\pm5677$} -> \textbf{642}{ $\pm317$} | Helped |
| Set q=0.2 rather than q=0.1 (ablation) | DynFrs · Adult and Diabetes | predictive performance | Helped |
| Set q below 0.1 (ablation) | DynFrs · Adult and Diabetes | predictive performance | Hurt |
| Add the lazy tag strategy (ablation) | DynFrs · Higgs batch unlearning | runtime | Helped |
| Remove the lazy tag strategy (ablation) | DynFrs · Batch unlearning | runtime trend | Hurt |
Surprising findings
- Subsampling trees per sample (OCC(q)) sometimes improves predictive accuracy over the non-subsampled forest, e.g., on Adult and Diabetes peak accuracy at q=0.4 and q=0.2.
- Unlearned and retrained models show nearly identical accuracy across removal proportions, supporting empirical exactness.
Limitations
- Exactness argument for the lazy tag and OCC(q) is shown theoretically but the claim of exact unlearning is evaluated empirically only through accuracy curves.
- HedgeCut could not be run on Synthetic and Higgs, and baselines were limited to binary classification datasets.
- Results are for ERT base learner; the framework's advantage relies on ERT's robustness to split changes.
Experimental setup
Datasets: Purchase Vaccine Adult Bank Heart Diabetes NoShow Synthetic Higgs
Benchmarks: Purchase Vaccine Adult Bank Heart Diabetes NoShow Synthetic Higgs
Metrics: accuracy AUC-ROC unlearning boost runtime in ms training time in s
Baselines: DaRE HedgeCut OnlineBoosting scikit-learn Random Forest
Builds on: Extremely Randomized Trees DaRE HedgeCut OnlineBoosting SISA
Closest papers by meaning
- Generalized Random Forests Using Fixed-Point Trees (ICML 2025 · similarity 0.85)
- Trained Random Forests Completely Reveal your Dataset (ICML 2024 · similarity 0.85)
- Autoencoding Random Forests (NeurIPS 2025 · similarity 0.84)
- Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees (NeurIPS 2026 · similarity 0.84)
- Principled Federated Random Forests for Heterogeneous Data (NeurIPS 2026 · similarity 0.83)
- Partition Tree: Conditional Density Estimation over General Outcome Spaces (NeurIPS 2026 · similarity 0.83)
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.