Learning Privately with Labeled and Unlabeled Examples
Learning Privately with Labeled and Unlabeled Examples
复制标题
通过标记和未标记的示例进行私下学习
作者：
A. Beimel;Kobbi Nissim;Uri Stemmer
私人学习器是一种算法，它能在给定贴有标签的个体示例样本的情况下，输出一个概括性假设，同时保护每个个体的隐私。2008 年，Kasiviswanathan 等人（FOCS 2008）给出了私有学习器的通用结构，其中的样本复杂度（通常）高于非私有学习器所需的复杂度。随后，几篇后续论文进一步研究了样本复杂度的这一差距，表明（至少在某些情况下）这一差距是不可避免的。此外，这些论文还考虑了通过放宽学习者的隐私或学习保证来克服这一差距的方法。我们受半监督学习和主动学习（非隐私）模型的启发，提出了另一种方法，其重点在于标记示例的样本复杂度，而未标记示例的成本要低得多。我们考虑的私人半监督学习者是在随机样本上运行的，而样本中只有一小部分（希望是一小部分）是有标签的。学习者无法控制哪些样本元素被标记。我们的主要结果是，私人学习者的标注样本复杂度以 VC 维度为特征。我们提出了私有半监督学习器的两种通用结构。第一种结构的学习器的标注样本复杂度与概念类的 VC 维度成正比，但是算法的非标注样本复杂度与域元素的表示长度一样大。我们的第二种构造提出了一种新技术，可以降低给定私有学习器的标注样本复杂度，同时大致保持其非标注样本复杂度。此外，我们还证明了在某些情况下，标记样本复杂度并不取决于学习器的隐私参数。
A private learner is an algorithm that given a sample of labeled individual examples outputs a generalizing hypothesis while preserving the privacy of each individual. In 2008, Kasiviswanathan et al. (FOCS 2008) gave a generic construction of private learners, in which the sample complexity is (generally) higher than what is needed for non-private learners. This gap in the sample complexity was then further studied in several followup papers, showing that (at least in some cases) this gap is unavoidable. Moreover, those papers considered ways to overcome the gap, by relaxing either the privacy or the learning guarantees of the learner. We suggest an alternative approach, inspired by the (non-private) models of semi-supervised learning and active-learning, where the focus is on the sample complexity of labeled examples whereas unlabeled examples are of a significantly lower cost. We consider private semi-supervised learners that operate on a random sample, where only a (hopefully small) portion of this sample is labeled. The learners have no control over which of the sample elements are labeled. Our main result is that the labeled sample complexity of private learners is characterized by the VC dimension. We present two generic constructions of private semi-supervised learners. The first construction is of learners where the labeled sample complexity is proportional to the VC dimension of the concept class, however, the unlabeled sample complexity of the algorithm is as big as the representation length of domain elements. Our second construction presents a new technique for decreasing the labeled sample complexity of a given private learner, while roughly maintaining its unlabeled sample complexity. In addition, we show that in some settings the labeled sample complexity does not depend on the privacy parameters of the learner.
用于私人分类和在线预测的闭包属性
DOI：
--
发表时间：
2020
期刊：
Proceedings of Thirty Third Conference on Learning Theory
影响因子：
--
作者：
Alon, Noga;Beimel, Amos;Moran, Shay;and Stemmer, Uri
通讯作者：
and Stemmer, Uri
影响因子：
3.3
作者：
Huang, Guo Shuai;Li, Si Jia;Cao, Xiang Yu
通讯作者：
Cao, Xiang Yu