论文标题
私人分类和在线预测之间的等效性
An Equivalence Between Private Classification and Online Prediction
论文作者
论文摘要
我们证明，每个具有有限littlestone尺寸的概念类都可以通过（近似）差异偏见的算法来学习。这回答了Alon等人的一个公开问题。 （Stoc 2019）谁证明了相反的陈述（Neel等人也提出了这个问题（FOCS 2019））。这两个结果共同在线学习性和私人PAC可学习性之间产生了等效。 我们介绍了一种新的算法稳定性概念，称为“全球稳定性”，这对我们的证明至关重要，可能具有独立的利益。我们还讨论了结果的应用，以提高差异私人学习者的隐私和准确性参数。
We prove that every concept class with finite Littlestone dimension can be learned by an (approximate) differentially-private algorithm. This answers an open question of Alon et al. (STOC 2019) who proved the converse statement (this question was also asked by Neel et al.~(FOCS 2019)). Together these two results yield an equivalence between online learnability and private PAC learnability. We introduce a new notion of algorithmic stability called "global stability" which is essential to our proof and may be of independent interest. We also discuss an application of our results to boosting the privacy and accuracy parameters of differentially-private learners.
