Smooth Sensitivity for Learning Differentially-Private yet Accurate Rule Lists
This work addresses the problem of improving accuracy in differentially-private interpretable models for practitioners needing privacy-preserving machine learning, though it is incremental as it builds on existing DP frameworks.
The paper tackled the trade-off between accuracy and privacy in differentially-private machine learning by establishing the smooth sensitivity of the Gini impurity, resulting in DP rule lists with higher accuracy for identical privacy budgets compared to global sensitivity methods.
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.