# Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees

arXiv: https://arxiv.org/abs/2605.22756 · HTML: https://mlsanity.com/paper/2605.22756/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 33 of its 65 references that are in the map.
- First posted on arXiv 21 May 2026.

## Builds on (most cited first, 30 of 33)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Retiring Adult: New Datasets for Fair Machine Learning](https://mlsanity.com/paper/2108.04884/) (2021)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Generalized Random Forests](https://mlsanity.com/paper/1610.01271/) (2016)
- [Differentially Private Learning Needs Better Features (or Much More Data)](https://mlsanity.com/paper/2011.11660/) (2020)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Hyperparameter Tuning with Renyi Differential Privacy](https://mlsanity.com/paper/2110.03620/) (2021)
- [Differentially Private Release and Learning of Threshold Functions](https://mlsanity.com/paper/1504.07553/) (2015)
- [Diffprivlib: The IBM Differential Privacy Library](https://mlsanity.com/paper/1907.02444/) (2019)
- [Geographic Spines in the 2020 Census Disclosure Avoidance System](https://mlsanity.com/paper/2203.16654/) (2022)
- [Instance-optimal Mean Estimation Under Differential Privacy](https://mlsanity.com/paper/2106.00463/) (2021)
- [The Power of Factorization Mechanisms in Local and Central Differential Privacy](https://mlsanity.com/paper/1911.08339/) (2019)
- [Understanding the Sparse Vector Technique for Differential Privacy](https://mlsanity.com/paper/1603.01699/) (2016)
- [Differentially Private SQL with Bounded User Contribution](https://mlsanity.com/paper/1909.01917/) (2019)
- [Permute-and-Flip: A new mechanism for differentially private selection](https://mlsanity.com/paper/2010.12603/) (2020)
- [~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization](https://mlsanity.com/paper/2211.06387/) (2022)
- [Differentially Private Random Decision Forests using Smooth Sensitivity](https://mlsanity.com/paper/1606.03572/) (2016)
- [Differentially Private Approximate Quantiles](https://mlsanity.com/paper/2110.05429/) (2021)
- [Trained Random Forests Completely Reveal your Dataset](https://mlsanity.com/paper/2402.19232/) (2024)
- [Differential Privacy on Finite Computers](https://mlsanity.com/paper/1709.05396/) (2017)
- [Widespread Underestimation of Sensitivity in Differentially Private Libraries and How to Fix It](https://mlsanity.com/paper/2207.10635/) (2022)
- [On Differentially Private Counting on Trees](https://mlsanity.com/paper/2212.11967/) (2022)
- [Exact Privacy Analysis of the Gaussian Sparse Histogram Mechanism](https://mlsanity.com/paper/2202.01100/) (2022)
- [Optimizing Hierarchical Queries for the Attribution Reporting API](https://mlsanity.com/paper/2308.13510/) (2023)
- [Weighted Fourier Factorizations: Optimal Gaussian Noise for Differentially Private Marginal and Product Queries](https://mlsanity.com/paper/2512.21499/) (2025)
- [The Correlated Gaussian Sparse Histogram Mechanism](https://mlsanity.com/paper/2412.10357/) (2024)
- [Differentially-Private Decision Trees and Provable Robustness to Data Poisoning](https://mlsanity.com/paper/2305.15394/) (2023)
- [Differentially Private Substring and Document Counting with Near-Optimal Error](https://mlsanity.com/paper/2412.13813/) (2024)
- [Privacy in Theory, Bugs in Practice: Grey-Box Auditing of Differential Privacy Libraries](https://mlsanity.com/paper/2602.17454/) (2026)

## Abstract (arXiv)

Random forests are widely used in fields involving sensitive tabular data, but existing approaches to enforcing differential privacy (DP) typically degrade performance to the point of impracticality. In this paper, we introduce Lumberjack, a differentially private random forest algorithm that achieves substantially higher utility by constructing large random decision trees and then applying aggressive, privacy-preserving pruning to retain only sufficiently populated nodes. A key component of our approach is a novel (varepsilon,δ)-DP heavy hitter detection algorithm for hierarchical data, whose error is Ovarepsilon,δ(√log h) for trees of height h and may be of independent interest. This favorable scaling enables the use of significantly deeper trees than in prior work, leading to improved expressiveness under privacy constraints. Our empirical evaluation on benchmark datasets shows that Lumberjack consistently outperforms prior DP random forest methods, establishing a new state of the art. In particular, our approach yields substantial improvements in the privacy-utility trade-off for practical privacy budgets. Our findings suggest that carefully designed DP random forests can close much of the utility gap, highlighting a promising and underexplored direction for future research.