Revisiting Model-Agnostic Private Learning: Faster Rates and Active Learning
This work provides enhanced theoretical insights for differentially private learning, particularly in noisy scenarios, which is incremental but important for privacy-preserving machine learning applications.
The paper addresses the gap in theoretical understanding of the Private Aggregation of Teacher Ensembles (PATE) framework in non-realizable settings by introducing the Tsybakov Noise Condition, establishing stronger learning bounds that improve over existing results, and empirically showing that active learning can save privacy budget.
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.