# Differentially Private Random Decision Forests using Smooth Sensitivity

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2016.

## Built on by (most cited first, 16 of 16)

- [A General Framework for Auditing Differentially Private Machine Learning](https://mlsanity.com/paper/2210.08643/) (2022)
- [How unfair is private learning ?](https://mlsanity.com/paper/2206.03985/) (2022)
- [Data-adaptive Differentially Private Prompt Synthesis for In-Context Learning](https://mlsanity.com/paper/2410.12085/) (2024)
- [Federated Boosted Decision Trees with Differential Privacy](https://mlsanity.com/paper/2210.02910/) (2022)
- [SoK: Privacy-Preserving Collaborative Tree-based Model Learning](https://mlsanity.com/paper/2103.08987/) (2021)
- [Classification with Partially Private Features](https://mlsanity.com/paper/2312.07583/) (2023)
- [Oblique and rotation double random forest](https://mlsanity.com/paper/2111.02010/) (2021)
- [Differentially-Private Decision Trees and Provable Robustness to Data Poisoning](https://mlsanity.com/paper/2305.15394/) (2023)
- [Privacy-Preserving Federated Learning over Vertically and Horizontally Partitioned Data for Financial Anomaly Detection](https://mlsanity.com/paper/2310.19304/) (2023)
- [Private Multi-Winner Voting for Machine Learning](https://mlsanity.com/paper/2211.15410/) (2022)
- [S-BDT: Distributed Differentially Private Boosted Decision Trees](https://mlsanity.com/paper/2309.12041/) (2023)
- [Smooth Sensitivity for Learning Differentially-Private yet Accurate Rule Lists](https://mlsanity.com/paper/2403.13848/) (2024)
- [Training Set Reconstruction from Differentially Private Forests: How Effective is DP?](https://mlsanity.com/paper/2502.05307/) (2025)
- [Differentially Private Selection using Smooth Sensitivity](https://mlsanity.com/paper/2504.08086/) (2025)
- [Differential Privacy in Machine Learning: A Survey from Symbolic AI to LLMs](https://mlsanity.com/paper/2506.11687/) (2025)
- [Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees](https://mlsanity.com/paper/2605.22756/) (2026)

## Abstract (arXiv)

We propose a new differentially-private decision forest algorithm that minimizes both the number of queries required, and the sensitivity of those queries. To do so, we build an ensemble of random decision trees that avoids querying the private data except to find the majority class label in the leaf nodes. Rather than using a count query to return the class counts like the current state-of-the-art, we use the Exponential Mechanism to only output the class label itself. This drastically reduces the sensitivity of the query -- often by several orders of magnitude -- which in turn reduces the amount of noise that must be added to preserve privacy. Our improved sensitivity is achieved by using "smooth sensitivity", which takes into account the specific data used in the query rather than assuming the worst-case scenario. We also extend work done on the optimal depth of random decision trees to handle continuous features, not just discrete features. This, along with several other improvements, allows us to create a differentially private decision forest with substantially higher predictive power than the current state-of-the-art.