Characterizing the Sample Complexity of Pure Private Learners
Characterizing the Sample Complexity of Pure Private Learners
复制标题
描述纯私人学习者的样本复杂性
DOI：
--
复制
发表时间：
2019
影响因子：
6
通讯作者：
Uri Stemmer
中科院分区：
文献类型：
--
作者：
A. Beimel;Kobbi Nissim;Uri Stemmer
Kasiviswanathan等人（FOCS 2008）将私人学习定义为PAC学习和差异隐私的结合。非正式地，私人学习者被应用于标记的个人信息的集合，并输出一个假设，同时保护每个人的隐私。Kasiviswanathan等人没有解决如何描述个体学习者样本复杂性的问题。我们给出了一个组合特征的样本大小充分和必要的学习一类概念下纯差分隐私。这个特征类似于众所周知的非私有学习的样本复杂性的概念类的VC维度的特征。我们引入了概念类的概率表示的概念，我们的新的复杂性度量RepDim对应于概念类的最小概率表示的大小。我们证明了对于样本复杂度为m的概念类C，任何私有学习算法都蕴含RepDim（C）= O（m），并且存在样本复杂度为m = O（RepDim（C））的私有学习算法。我们进一步证明，一个类似的表征持有的数据库大小计算下的纯差分隐私的优化问题的一大类，也为私人数据发布的问题研究。
Kasiviswanathan et al. (FOCS 2008) defined private learning as a combination of PAC learning and differential privacy. Informally, a private learner is applied to a collection of labeled individual information and outputs a hypothesis while preserving the privacy of each individual. Kasiviswanathan et al. left open the question of characterizing the sample complexity of private learners. We give a combinatorial characterization of the sample size sufficient and necessary to learn a class of concepts under pure differential privacy. This characterization is analogous to the well known characterization of the sample complexity of non-private learning in terms of the VC dimension of the concept class. We introduce the notion of probabilistic representation of a concept class, and our new complexity measure RepDim corresponds to the size of the smallest probabilistic representation of the concept class. We show that any private learning algorithm for a concept class C with sample complexity m implies RepDim(C) = O(m), and that there exists a private learning algorithm with sample complexity m = O(RepDim(C)). We further demonstrate that a similar characterization holds for the database size needed for computing a large class of optimization problems under pure differential privacy, and also for the well studied problem of private data release.
私有中心点和半空间学习
DOI：
--
发表时间：
2020
期刊：
COLT 2019
影响因子：
--
作者：
Amos Beimel, Shay Moran
通讯作者：
Amos Beimel, Shay Moran