提出近线性时间的私有假设选择算法，达到最优误差界。
Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor
- 基于差分隐私设计中央模型算法，近线性时间完成选择
- 实现最优近似因子α=3，样本复杂度仅多出对数级开销
- 解决该领域多年未决问题，适合隐私敏感场景应用
从样本中估计分布密度是统计学基本问题。假设选择考虑在给定样本集和n个候选分布（即假设）的情况下，找出最能描述真实数据分布的那个。该问题已知可在约O(log n)样本下高效求解，运行时间约为Õ(n)。输出质量以与未知分布的总变差距离衡量，算法的近似因子决定该距离相对于最优候选假设的距离大小。已知α=3为该问题的最优近似因子。本文研究差分隐私约束下的假设选择问题。提出一种中央模型下的差分隐私算法，运行时间接近与假设数量呈线性关系，实现最优近似因子，且样本复杂度仅比原来多出一个关于n的多项式对数项。这解决了[Bun, Kamath, Steinke, Wu, NeurIPS 2019]提出的开放问题。此前已有上界需二次时间。
原文摘要 · Abstract (English)
Estimating the density of a distribution from its samples is a fundamental problem in statistics. Hypothesis selection addresses the setting where, in addition to a sample set, we are given $n$ candidate distributions -- referred to as hypotheses -- and the goal is to determine which one best describes the underlying data distribution. This problem is known to be solvable very efficiently, requiring roughly $O(\log n)$ samples and running in $\tilde{O}(n)$ time. The quality of the output is measured via the total variation distance to the unknown distribution, and the approximation factor of the algorithm determines how large this distance is compared to the optimal distance achieved by the best candidate hypothesis. It is known that $α= 3$ is the optimal approximation factor for this problem. We study hypothesis selection under the constraint of differential privacy. We propose a differentially private algorithm in the central model that runs in nearly-linear time with respect to the number of hypotheses, achieves the optimal approximation factor, and incurs only a modest increase in sample complexity, which remains polylogarithmic in $n$. This resolves an open question posed by [Bun, Kamath, Steinke, Wu, NeurIPS 2019]. Prior to our work, existing upper bounds required quadratic time.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。