论文标题
私人学习与在线学习之间的计算分离
A Computational Separation between Private Learning and Online Learning
论文作者
论文摘要
最近的一项工作表明，差异性的PAC学习与在线学习之间的定性等效性：概念类是私人学习的，并且只有在线学习有限的错误时才可以学习。但是，这种等效性的两个方向都在样本和计算效率上都造成了明显的损失。在研究这种联系的特殊情况下，Gonen，Hazan和Moran（Neurips 2019）表明，可以将统一或高效的纯私人学习者逐渐汇总到在线学习者中。我们表明，假设存在单向函数，即使对于具有多项式样本复杂性的一般纯私人学习者来说，这种有效的转换也是不可能的。这解决了Neel，Roth和Wu的问题（FOCS 2019）。
A recent line of work has shown a qualitative equivalence between differentially private PAC learning and online learning: A concept class is privately learnable if and only if it is online learnable with a finite mistake bound. However, both directions of this equivalence incur significant losses in both sample and computational efficiency. Studying a special case of this connection, Gonen, Hazan, and Moran (NeurIPS 2019) showed that uniform or highly sample-efficient pure-private learners can be time-efficiently compiled into online learners. We show that, assuming the existence of one-way functions, such an efficient conversion is impossible even for general pure-private learners with polynomial sample complexity. This resolves a question of Neel, Roth, and Wu (FOCS 2019).
