Private PAC learning implies finite Littlestone dimension

We show that every approximately differentially private learning algorithm (possibly improper) for a class H with Littlestone dimension d requires Ω(log * ( d )) examples. As a corollary it follows that the class of thresholds over ℕ can not be learned in a private manner; this resolves open questions due to [Bun et al. 2015] and [Feldman and Xiao, 2015]. We leave as an open question whether every class with a finite Littlestone dimension can be learned by an approximately differentially private algorithm.

Authors

• Noga Alon
• Roi Livni
• Maryanthe Malliaris
• Shay Moran

Keywords

• Differential Privacy
• Littlestone dimension
• PAC learning