BriefGPT.xyz
Apr, 2015
阈值函数的差分隐私发布和学习
Differentially Private Release and Learning of Threshold Functions
HTML
PDF
Mark Bun, Kobbi Nissim, Uri Stemmer, Salil Vadhan
TL;DR
该研究提出了不同ially private算法(DP算法)在发布阈值函数的近似答案时的样本复杂度的新上限和下限结果,还展示了实现此任务在无限域X上是不可能的,并需要样本复杂度n≥Ω(log * |X| ),同时对于使用DP合理地学习概念类与无隐私信息学习之间的差异也给出了首个下限结果。
Abstract
We prove new upper and lower bounds on the
sample complexity
of $(\epsilon, \delta)$ differentially private algorithms for releasing approximate answers to threshold functions. A
threshold function
$c_x$ over a t
→