Smooth Sensitivity for Learning Differentially-Private yet Accurate Rule
  Lists
Timothée Ly Julien Ferry Marie-José Huguet Sébastien Gambs Ulrich Aivodji
Differentially-private (DP) mechanisms can be embedded into the design of a
machine learningalgorithm to protect the resulting model against privacy
leakage, although this often comes with asignificant loss of accuracy. In this
paper, we aim at improving this trade-off for rule lists modelsby establishing
the smooth sensitivity of the Gini impurity and leveraging it to propose a DP
greedyrule list algorithm. In particular, our theoretical analysis and
experimental results demonstrate thatthe DP rule lists models integrating
smooth sensitivity have higher accuracy that those using otherDP frameworks
based on global sensitivity.