论文标题
带有近似差异隐私的样品高效的PAC学习
Sample-efficient proper PAC learning with approximate differential privacy
论文作者
论文摘要
在本文中，我们证明，正确学习具有近似差异隐私的一类Littlestone尺寸的样本复杂性是$ \ tilde o（d^6）$，忽略隐私和准确参数。这个结果回答了Bun等人的问题。 （focs 2020）通过改进样品复杂性上的$ 2^{o（d）} $的上限。在我们的工作之前，样本复杂性的有限性用于私人学习一类有限的小littlestone维度仅因不当私人学习者而闻名，而我们的学习者是适当的答案，这一事实是Bun等人的另一个问题，Bunquet等人也要求。 （神经2020）。使用Bousquet等人开发的机械，然后我们证明了对二进制假设类别的样品复杂性最多是多项式的，其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 $\tilde O(d^6)$, ignoring privacy and accuracy parameters. This result answers a question of Bun et al. (FOCS 2020) by improving upon their upper bound of $2^{O(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.
