Sample Complexity Bounds on Differentially Private Learning via Communication Complexity
Sample Complexity Bounds on Differentially Private Learning via Communication Complexity
复制标题
通过通信复杂性对差异化私人学习进行样本复杂性限制
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
David Xiao
中科院分区：
文献类型：
--
作者：
V. Feldman;David Xiao
在这项工作中，我们通过差异私有算法分析了分类的样本复杂性。差异隐私是Dwork等人介绍的强烈而充分研究的隐私概念。 （2006年）确保算法的输出泄漏几乎没有任何参与个人提供的数据点的信息。在以前的许多先前工作中，研究了私人PAC和不可知论学习的样本复杂性（Kasiviswanathan等，2008），但是许多基本问题仍然保持开放，最值得注意的是，使用隐私学习是否需要更多的样本，而不是没有隐私。
我们表明，使用（纯）差异隐私学习的样本复杂性可以比学习的样本复杂性高于隐私约束或具有近似差异隐私的学习样本复杂性。我们的第二个贡献和主要工具是（纯）对概念类别$ c $（或$ scdp（c）$）的样本复杂性与评估问题的随机单向通信复杂性之间的等效性$ c $的概念。使用这种等价性，我们证明了以下范围：
1。$ scdp（c）= \ omega（ldim（c））$，其中$ ldim（c）$是Littlestone（1987）的维度，表征了在线摄影 - 绑定学习模型中错误的数量。 $ ldim（c）$上的已知界限，这意味着$ scdp（c）$可能高于$ c $的VC-dimension。
2。对于任何$ t $，都存在$ c $的类别，因此$ ldim（c）= 2 $，但$ scdp（c）\ geq t $。
3。对于任何$ t $，都存在$ c $的类别，使得（pure）$ \ alpha $ -divential的私人PAC学习的样本复杂性是$ \ omega（t/\ alpha）$放松$（\ alpha，\ beta）$ - 差异化私人PAC学习为$ O（\ log（1/\ beta）/\ alpha）$。这解决了Beimel等人的开放问题。 （2013b）。
In this work we analyze the sample complexity of classification by differentially private algorithms. Differential privacy is a strong and well-studied notion of privacy introduced by Dwork et al. (2006) that ensures that the output of an algorithm leaks little information about the data point provided by any of the participating individuals. Sample complexity of private PAC and agnostic learning was studied in a number of prior works starting with (Kasiviswanathan et al., 2008) but a number of basic questions still remain open, most notably whether learning with privacy requires more samples than learning without privacy.
We show that the sample complexity of learning with (pure) differential privacy can be arbitrarily higher than the sample complexity of learning without the privacy constraint or the sample complexity of learning with approximate differential privacy. Our second contribution and the main tool is an equivalence between the sample complexity of (pure) differentially private learning of a concept class $C$ (or $SCDP(C)$) and the randomized one-way communication complexity of the evaluation problem for concepts from $C$. Using this equivalence we prove the following bounds:
1. $SCDP(C) = \Omega(LDim(C))$, where $LDim(C)$ is the Littlestone's (1987) dimension characterizing the number of mistakes in the online-mistake-bound learning model. Known bounds on $LDim(C)$ then imply that $SCDP(C)$ can be much higher than the VC-dimension of $C$.
2. For any $t$, there exists a class $C$ such that $LDim(C)=2$ but $SCDP(C) \geq t$.
3. For any $t$, there exists a class $C$ such that the sample complexity of (pure) $\alpha$-differentially private PAC learning is $\Omega(t/\alpha)$ but the sample complexity of the relaxed $(\alpha,\beta)$-differentially private PAC learning is $O(\log(1/\beta)/\alpha)$. This resolves an open problem of Beimel et al. (2013b).