Sample-efficient proper PAC learning with approximate differential privacy
Sample-efficient proper PAC learning with approximate differential privacy
复制标题
具有近似差分隐私的样本有效的适当 PAC 学习
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Pasin Manurangsi
中科院分区：
文献类型：
--
作者：
Badih Ghazi;Noah Golowich;Ravi Kumar;Pasin Manurangsi
本文证明了在忽略隐私和精度参数的情况下，正确学习具有近似微分隐私的Littlestone维d类的样本复杂度为Õ（d6）。这一结果回答了Bun等人（FOCS 2020）的一个问题，提高了他们对样本复杂性的上限2O(d)。在我们的工作之前，私人学习有限Littlestone维的类的样本复杂性的有限性仅适用于不合适的私人学习器，而我们的学习器是正确的这一事实回答了Bun等人的另一个问题，这也是Bousquet等人提出的（NeurIPS 2020）。使用Bousquet等人开发的机器，我们然后证明了消毒二元假设类的样本复杂度在其Littlestone维数和对偶Littlestone维数上最多是多项式。这意味着当且仅当类具有有限的Littlestone维度时，类是可消毒的。我们证明的一个重要成分是二元假设类的一个新性质，我们称之为不可约性，它可能是一个独立的兴趣。
In this paper we prove that the sample complexity of properly learning a class of Littlestone dimension d with approximate differential privacy is Õ(d6), ignoring privacy and accuracy parameters. This result answers a question of Bun et al. (FOCS 2020) by improving upon their upper bound of 2O(d) on the sample complexity. Prior to our work, finiteness of the sample complexity for privately learning a class of finite Littlestone dimension was only known for improper private learners, and the fact that our learner is proper answers another question of Bun et al., which was also asked by Bousquet et al. (NeurIPS 2020). Using machinery developed by Bousquet et al., we then show that the sample complexity of sanitizing a binary hypothesis class is at most polynomial in its Littlestone dimension and dual Littlestone dimension. This implies that a class is sanitizable if and only if it has finite Littlestone dimension. An important ingredient of our proofs is a new property of binary hypothesis classes that we call irreducibility, which may be of independent interest.
登录
查看更多内容
DOI：
10.1145/3188745.3188946
发表时间：
2018-06
期刊：
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Mark Bun;C. Dwork;G. Rothblum;T. Steinke
通讯作者：
Mark Bun;C. Dwork;G. Rothblum;T. Steinke
用于私人分类和在线预测的闭包属性
DOI：
--
发表时间：
2020
期刊：
Proceedings of Thirty Third Conference on Learning Theory
影响因子：
--
作者：
Alon, Noga;Beimel, Amos;Moran, Shay;and Stemmer, Uri
通讯作者：
and Stemmer, Uri
DOI：
--
发表时间：
2020
期刊：
34th Conference on Neural Information Processing Systems
影响因子：
--
作者：
Bun, Mark
通讯作者：
Bun, Mark
私有中心点和半空间学习
DOI：
--
发表时间：
2020
期刊：
COLT 2019
影响因子：
--
作者：
Amos Beimel, Shay Moran
通讯作者：
Amos Beimel, Shay Moran