  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.
