论文标题
pptimal差异私人学习阈值和准concave优化
Õptimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization
论文作者
论文摘要
学习阈值功能的问题是机器学习的基本问题。经典学习理论意味着$ o（ξ^{ - 1} \ log（1/β））$的样本复杂性（对于具有信心$ 1-β$的概括错误$ξ$）。但是，该问题的私有版本更具挑战性，尤其是样本复杂性必须取决于域的$ | x | $。在过去十年中，通过下限和上限进行量化这种依赖性的进展。在本文中，我们终于缩小了大约DP的间隙，并提供了几乎紧密的上限，$ \ tilde {o}（\ log^* | x |）$，它与Alon等人的下限相匹配（即使学习不当学习），并且在$ \ tilde {o}（O log}（\ log log^| x | x | x |）$^| x | x | x | x | x的上一个上的上限不当，并改善了上限。我们还为$ \tildeθ（2^{\ log^*| x |}）$提供匹配的上限和下限，以用于私有准级concave优化的加法误差（相关和更一般的问题）。我们的改进是通过新颖的重新定板计算范式来实现的，以进行私人数据分析，我们认为这将有进一步的应用。
The problem of learning threshold functions is a fundamental one in machine learning. Classical learning theory implies sample complexity of $O(ξ^{-1} \log(1/β))$ (for generalization error $ξ$ with confidence $1-β$). The private version of the problem, however, is more challenging and in particular, the sample complexity must depend on the size $|X|$ of the domain. Progress on quantifying this dependence, via lower and upper bounds, was made in a line of works over the past decade. In this paper, we finally close the gap for approximate-DP and provide a nearly tight upper bound of $\tilde{O}(\log^* |X|)$, which matches a lower bound by Alon et al (that applies even with improper learning) and improves over a prior upper bound of $\tilde{O}((\log^* |X|)^{1.5})$ by Kaplan et al. We also provide matching upper and lower bounds of $\tildeΘ(2^{\log^*|X|})$ for the additive error of private quasi-concave optimization (a related and more general problem). Our improvement is achieved via the novel Reorder-Slice-Compute paradigm for private data analysis which we believe will have further applications.
