# Scalable and Provably Accurate Algorithms for Differentially Private Distributed Decision Tree Learning

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Dec 2020.

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

- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Accuracy, Interpretability, and Differential Privacy via Explainable Boosting](https://mlsanity.com/paper/2106.09680/) (2021)
- [SoK: Privacy-Preserving Collaborative Tree-based Model Learning](https://mlsanity.com/paper/2103.08987/) (2021)
- [Private Boosted Decision Trees via Smooth Re-Weighting](https://mlsanity.com/paper/2201.12648/) (2022)
- [FedGA-Tree: Federated Decision Tree using Genetic Algorithm](https://mlsanity.com/paper/2506.08176/) (2025)

## Abstract (arXiv)

This paper introduces the first provably accurate algorithms for differentially private, top-down decision tree learning in the distributed setting (Balcan et al., 2012). We propose DP-TopDown, a general privacy preserving decision tree learning algorithm, and present two distributed implementations. Our first method NoisyCounts naturally extends the single machine algorithm by using the Laplace mechanism. Our second method LocalRNM significantly reduces communication and added noise by performing local optimization at each data holder. We provide the first utility guarantees for differentially private top-down decision tree learning in both the single machine and distributed settings. These guarantees show that the error of the privately-learned decision tree quickly goes to zero provided that the dataset is sufficiently large. Our extensive experiments on real datasets illustrate the trade-offs of privacy, accuracy and generalization when learning private decision trees in the distributed setting.