2022/12/08 by Olivier Bousquet, Haim Kaplan, Bousquet, Olivier +11
Computer Science · #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2212.04216
openalex publication_date 2022/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We construct a universally Bayes consistent learning rule that satisfies differential privacy (DP). We first handle the setting of binary classification and then extend our rule to the more general setting of density estimation (with respect to the total variation metric). The existence of a universally consistent DP learner reveals a stark difference with the distribution-free PAC model. Indeed, in the latter DP learning is extremely limited: even one-dimensional linear classifiers are not privately learnable in this stringent model. Our result thus demonstrates that by allowing the learning rate to depend on the target distribution, one can circumvent the above-mentioned impossibility result and in fact, learn arbitrary distributions by a single DP algorithm. As an application, we prove that any VC class can be privately learned in a semi-supervised setting with a near-optimal labeled sample complexity of O(d/ε) labeled examples (and with an unlabeled sample complexity that can depend on the target distribution).