# Differentially-Private Decision Trees and Provable Robustness to Data Poisoning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Membership inference attacks, one of 12 directions in LLM safety and security.
- Builds on 31 of its 60 references that are in the map.
- First posted on arXiv 24 May 2023.

## Placed in

- LLM safety and security / [Membership inference attacks](https://mlsanity.com/safety/membership-inference-attacks/)

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [BadNets: Identifying Vulnerabilities in the Machine Learning Model Supply Chain](https://mlsanity.com/paper/1708.06733/) (2017)
- [The Mythos of Model Interpretability](https://mlsanity.com/paper/1606.03490/) (2016)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Detecting Backdoor Attacks on Deep Neural Networks by Activation Clustering](https://mlsanity.com/paper/1811.03728/) (2018)
- [Certified Defenses against Adversarial Examples](https://mlsanity.com/paper/1801.09344/) (2018)
- [Certified Defenses for Data Poisoning Attacks](https://mlsanity.com/paper/1706.03691/) (2017)
- [Anti-Backdoor Learning: Training Clean Models on Poisoned Data](https://mlsanity.com/paper/2110.11571/) (2021)
- [Adversarial Neuron Pruning Purifies Backdoored Deep Models](https://mlsanity.com/paper/2110.14430/) (2021)
- [Manipulating Machine Learning: Poisoning Attacks and Countermeasures for Regression Learning](https://mlsanity.com/paper/1804.00308/) (2018)
- [Why do tree-based models still outperform deep learning on tabular data?](https://mlsanity.com/paper/2207.08815/) (2022)
- [Witches' Brew: Industrial Scale Data Poisoning via Gradient Matching](https://mlsanity.com/paper/2009.02276/) (2020)
- [Deep Learning with Label Differential Privacy](https://mlsanity.com/paper/2102.06062/) (2021)
- [Deep Partition Aggregation: Provable Defense against General Poisoning Attacks](https://mlsanity.com/paper/2006.14768/) (2020)
- [Certified Robustness to Label-Flipping Attacks via Randomized Smoothing](https://mlsanity.com/paper/2002.03018/) (2020)
- [On the Effectiveness of Mitigating Data Poisoning Attacks with Gradient Shaping](https://mlsanity.com/paper/2002.11497/) (2020)
- [Data Poisoning against Differentially-Private Learners: Attacks and Defenses](https://mlsanity.com/paper/1903.09860/) (2019)
- [Diffprivlib: The IBM Differential Privacy Library](https://mlsanity.com/paper/1907.02444/) (2019)
- [Robustness Implies Privacy in Statistical Estimation](https://mlsanity.com/paper/2212.05015/) (2022)
- [DP-InstaHide: Provably Defusing Poisoning and Backdoor Attacks with Differentially Private Data Augmentations](https://mlsanity.com/paper/2103.02079/) (2021)
- [Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation](https://mlsanity.com/paper/2211.00724/) (2022)
- [Differentially Private Quantiles](https://mlsanity.com/paper/2102.08244/) (2021)
- [Permute-and-Flip: A new mechanism for differentially private selection](https://mlsanity.com/paper/2010.12603/) (2020)
- [Privacy-Preserving Gradient Boosting Decision Trees](https://mlsanity.com/paper/1911.04209/) (2019)
- [Decision Tree Classification with Differential Privacy: A Survey](https://mlsanity.com/paper/1611.01919/) (2016)
- [Differentially Private Random Decision Forests using Smooth Sensitivity](https://mlsanity.com/paper/1606.03572/) (2016)
- [Differentially- and non-differentially-private random decision trees](https://mlsanity.com/paper/1410.6973/) (2014)

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

- [Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees](https://mlsanity.com/paper/2605.22756/) (2026)

## Abstract (arXiv)

Decision trees are interpretable models that are well-suited to non-linear learning problems. Much work has been done on extending decision tree learning algorithms with differential privacy, a system that guarantees the privacy of samples within the training data. However, current state-of-the-art algorithms for this purpose sacrifice much utility for a small privacy benefit. These solutions create random decision nodes that reduce decision tree accuracy or spend an excessive share of the privacy budget on labeling leaves. Moreover, many works do not support continuous features or leak information about them. We propose a new method called PrivaTree based on private histograms that chooses good splits while consuming a small privacy budget. The resulting trees provide a significantly better privacy-utility trade-off and accept mixed numerical and categorical data without leaking information about numerical features. Finally, while it is notoriously hard to give robustness guarantees against data poisoning attacks, we demonstrate bounds for the expected accuracy and success rates of backdoor attacks against differentially-private learners. By leveraging the better privacy-utility trade-off of PrivaTree we are able to train decision trees with significantly better robustness against backdoor attacks compared to regular decision trees and with meaningful theoretical guarantees.