Private Hypothesis Selection
Private Hypothesis Selection
复制标题
DOI：
10.1109/tit.2021.3049802
复制
发表时间：
2019-05
影响因子：
2.5
通讯作者：
Mark Bun;Gautam Kamath;T. Steinke;Zhiwei Steven Wu
中科院分区：
文献类型：
--
作者：
Mark Bun;Gautam Kamath;T. Steinke;Zhiwei Steven Wu
我们为假设选择提供了差异化私有算法。给定来自未知概率分布p和一组M概率分布的样品$ \ MATHCAL {H} $，目标是以$ \ varepsilon $ -Diffitally私有方式输出，从$ \ Mathcal {h h} $输出其与P的总变化距离与最佳分布的变化距离（我们用$ \ alpha $表示）。我们基本算法的示例复杂性是$ \ text {o} \ left（{\ frac {\ log \ text {m}}} {\ alpha ^{2}}} + \ frac {\ frac {\ log \ log \ text {m}} {m}} {m}} { \ alpha \ varepsilon}} \ right）$，与非私人算法相比，隐私成本最低。我们还可以通过放松到$（\ varepsilon，\ delta）$ -Differential私密性来处理无限假设类$ \ MATHCAL {H} $。我们应用假设选择算法为许多自然分布类别提供学习算法，包括高斯，产品分布，独立随机变量的总和，分段多项式和混合类别。我们的假设选择程序使我们能够一致地将课堂的封面转换为学习算法，从而补充已知的学习下限，这些范围是按类的包装数量的大小。由于对于常数$ \ alpha $，覆盖和包装数字通常密切相关，因此我们的算法达到了许多兴趣类别的最佳样本复杂性。最后，我们描述了无私人发行PAC学习的应用。
We provide a differentially private algorithm for hypothesis selection. Given samples from an unknown probability distribution P and a set of m probability distributions $\mathcal {H}$ , the goal is to output, in a $\varepsilon $ -differentially private manner, a distribution from $\mathcal {H}$ whose total variation distance to P is comparable to that of the best such distribution (which we denote by $\alpha $ ). The sample complexity of our basic algorithm is $\text {O}\left ({\frac {\log \text {m}}{\alpha ^{2}} + \frac {\log \text {m}}{\alpha \varepsilon }}\right)$ , representing a minimal cost for privacy when compared to the non-private algorithm. We also can handle infinite hypothesis classes $\mathcal {H}$ by relaxing to $(\varepsilon,\delta)$ -differential privacy. We apply our hypothesis selection algorithm to give learning algorithms for a number of natural distribution classes, including Gaussians, product distributions, sums of independent random variables, piecewise polynomials, and mixture classes. Our hypothesis selection procedure allows us to generically convert a cover for a class to a learning algorithm, complementing known learning lower bounds which are in terms of the size of the packing number of the class. As the covering and packing numbers are often closely related, for constant $\alpha $ , our algorithms achieve the optimal sample complexity for many classes of interest. Finally, we describe an application to private distribution-free PAC learning.