论文标题
在非交互性本地隐私模型中使用公共未标记的数据中的PAC学习半空间
On PAC Learning Halfspaces in Non-interactive Local Privacy Model with Public Unlabeled Data
论文作者
论文摘要
在本文中，我们研究了非交互性局部差异隐私模型（NLDP）中PAC学习半空间的问题。为了违反指数样本复杂性的障碍，先前的结果研究了一个轻松的设置，在该设置中，服务器可以访问一些其他公共但未标记的数据。我们继续朝这个方向前进。具体来说，我们考虑了标准设置下的问题，而不是以前研究的较大的保证金设置。在对基础数据分布的不同温和假设下，我们提出了两种基于Massart噪声模型和自我监督学习的方法，并表明可以实现仅在私人和公共数据中以其他术语在维度和多项式中线性的样本复杂性，从而显着改善了先前的结果。我们的方法也可以用于其他私人PAC学习问题。
In this paper, we study the problem of PAC learning halfspaces in the non-interactive local differential privacy model (NLDP). To breach the barrier of exponential sample complexity, previous results studied a relaxed setting where the server has access to some additional public but unlabeled data. We continue in this direction. Specifically, we consider the problem under the standard setting instead of the large margin setting studied before. Under different mild assumptions on the underlying data distribution, we propose two approaches that are based on the Massart noise model and self-supervised learning and show that it is possible to achieve sample complexities that are only linear in the dimension and polynomial in other terms for both private and public data, which significantly improve the previous results. Our methods could also be used for other private PAC learning problems.
