# Smooth Sensitivity for Learning Differentially-Private yet Accurate Rule Lists

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 37 references that are in the map.
- First posted on arXiv 18 Mar 2024.

## Builds on (most cited first, 17 of 17)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Membership Inference Attacks From First Principles](https://mlsanity.com/paper/2112.03570/) (2021)
- [Label-Only Membership Inference Attacks](https://mlsanity.com/paper/2007.14321/) (2020)
- [Adversarial Robustness Toolbox v1.0.0](https://mlsanity.com/paper/1807.01069/) (2018)
- [Differential Privacy and Machine Learning: a Survey and Review](https://mlsanity.com/paper/1412.7584/) (2014)
- [Learning Certifiably Optimal Rule Lists for Categorical Data](https://mlsanity.com/paper/1704.01701/) (2017)
- [Fairness via Explanation Quality: Evaluating Disparities in the Quality of Post hoc Explanations](https://mlsanity.com/paper/2205.07277/) (2022)
- [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)
- [Trained Random Forests Completely Reveal your Dataset](https://mlsanity.com/paper/2402.19232/) (2024)
- [Optimal Kidney Exchange with Immunosuppressants](https://mlsanity.com/paper/2103.02253/) (2021)
- [Locally Private Learning without Interaction Requires Separation](https://mlsanity.com/paper/1809.09165/) (2018)
- [Probabilistic Dataset Reconstruction from Interpretable Models](https://mlsanity.com/paper/2308.15099/) (2023)
- [Differentially Private Deep Learning with Smooth Sensitivity](https://mlsanity.com/paper/2003.00505/) (2020)
- [The Bouncer Problem: Challenges to Remote Explainability](https://mlsanity.com/paper/1910.01432/) (2019)
- [Differentially Private Naive Bayes Classifier using Smooth Sensitivity](https://mlsanity.com/paper/2003.13955/) (2020)

## Abstract (arXiv)

Differentially-private (DP) mechanisms can be embedded into the design of a machine learning algorithm to protect the resulting model against privacy leakage. However, this often comes with a significant loss of accuracy due to the noise added to enforce DP. In this paper, we aim at improving this trade-off for a popular class of machine learning algorithms leveraging the Gini impurity as an information gain criterion to greedily build interpretable models such as decision trees or rule lists. To this end, we establish the smooth sensitivity of the Gini impurity, which can be used to obtain thorough DP guarantees while adding noise scaled with tighter magnitude. We illustrate the applicability of this mechanism by integrating it within a greedy algorithm producing rule list models, motivated by the fact that such models remain understudied in the DP literature. Our theoretical analysis and experimental results confirm that the DP rule lists models integrating smooth sensitivity have higher accuracy that those using other DP frameworks based on global sensitivity, for identical privacy budgets.