Scalable and Provably Accurate Algorithms for Differentially Private Distributed Decision Tree Learning

Understand

This paper introduces the first provably accurate algorithms for differentially private, top-down decision tree learning in the distributed setting (Balcan et al., 2012).

• We propose DP-TopDown, a general privacy preserving decision tree learning algorithm, and present two distributed implementations.
• Our first method NoisyCounts naturally extends the single machine algorithm by using the Laplace mechanism.
• Our second method LocalRNM significantly reduces communication and added noise by performing local optimization at each data holder.