Private PAC learning implies finite Littlestone dimension

2018/06/04 by Alon, Noga, Livni, Roi, Malliaris, Maryanthe +1 · 10 citations
#Artificial Intelligence (cs.AI) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1806.00949

Abstract

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 question due to [Bun et al., 2015, 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.

Cited by

• Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back
• Model Agreement via Anchoring
• Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings
• Private Realizable-to-Agnostic Transformation with Near-Optimal Sample Complexity
• Privately Estimating Black-Box Statistics
• Private Learning of Littlestone Classes, Revisited
• Learning in an Echo Chamber: Online Learning with Replay Adversary
• On the Computational Complexity of (Extended) Threshold Dimension and (Semi-)Ladder Index
• Epsilon-saturation for stable graphs and Littlestone classes
• Regularity for hypergraphs with bounded VC₂ dimension

Related

• Sample-efficient proper PAC learning with approximate differential privacy
• Private Learning of Littlestone Classes, Revisited
• Multiclass versus Binary Differentially Private PAC Learning
• Private PAC Learning May be Harder than Online Learning
• An Equivalence Between Private Classification and Online Prediction