Smooth Sensitivity for Learning Differentially-Private yet Accurate Rule Lists

Timothée Ly (1) , Julien Ferry (2) , Marie-José Huguet (1) , Sébastien Gambs (3) , Ulrich Aivodji (4)

1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
2 EPM - École Polytechnique de Montréal
3 UQAM - Université du Québec à Montréal = University of Québec in Montréal
4 ETS - Ecole de Technologie Supérieure [Montréal]

Differentially-private (DP) mechanisms can be embedded into the design of a machine learning algorithm to protect the resulting model against privacy leakage, although this often comes with a significant loss of accuracy. In this paper, we aim at improving this trade-off for rule lists models by establishing the smooth sensitivity of the Gini impurity and leveraging it to propose a DP greedy rule list algorithm. In particular, our theoretical analysis and experimental results demonstrate that the DP rule lists models integrating smooth sensitivity have higher accuracy that those using other DP frameworks based on global sensitivity.

Domaines: Intelligence artificielle [cs.AI]; Cryptographie et sécurité [cs.CR]

Timothée Ly, Julien Ferry, Marie-José Huguet, Sébastien Gambs, Ulrich Aivodji. Smooth Sensitivity for Learning Differentially-Private yet Accurate Rule Lists. 2024. ⟨hal-04505410⟩