Revisiting Model-Agnostic Private Learning: Faster Rates and Active Learning
arXiv:2011.03186
Abstract
The Private Aggregation of Teacher Ensembles (PATE) framework is one of the most promising recent approaches in differentially private learning. Existing theoretical analysis shows that PATE consistently learns any VC-classes in the realizable setting, but falls short in explaining its success in more general cases where the error rate of the optimal classifier is bounded away from zero. We fill in this gap by introducing the Tsybakov Noise Condition (TNC) and establish stronger and more interpretable learning bounds. These bounds provide new insights into when PATE works and improve over existing results even in the narrower realizable setting. We also investigate the compelling idea of using active learning for saving privacy budget, and empirical studies show the effectiveness of this new idea. The novel components in the proofs include a more refined analysis of the majority voting classifier - which could be of independent interest - and an observation that the synthetic "student" learning problem is nearly realizable by construction under the Tsybakov noise condition.
References in corpus (13)
- Deep Learning with Differential Privacy
- Learning Differentially Private Recurrent Language Models
- Scalable Private Learning with PATE
- Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data
- Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo
- Subsampled Rényi Differential Privacy and Analytical Moments Accountant
- Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle
- Beyond Disagreement-based Agnostic Active Learning
- Active Learning with Logged Data
- Limits of Private Learning with Access to Public Data
- Privately Answering Classification Queries in the Agnostic PAC Model
- Model-Agnostic Private Learning via Stability
- Improving Differentially Private Models with Active Learning