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.
翻译:私人教师集合(PATE)框架(PATE)是私人不同学习中最有希望的最新方法之一。 现有的理论分析表明,PATE在可实现的环境中一贯学习任何VC类,但在更一般的情况下,最佳分类器的错误率与零相距不远,却未能解释其成功之处。 我们通过引入Tsybakov Noise Condition(TNC)填补了这一差距,并建立了更强大、更可解释的学习界限。 这些界限为PATE(PATE)工作时提供了新的洞察力,并改进了现有成果,即使在狭小的可实现环境中也是如此。 我们还调查了使用积极学习来保存隐私预算的令人信服的想法,而实证研究表明了这一新想法的有效性。 证据中的新组成部分包括对多数选民分类器进行更精确的分析 -- -- 这可能具有独立的兴趣 -- 以及认为合成的“学生”学习问题在Tsybakov噪音条件下的建筑工程中几乎可以实现。