提出新算法，在本地差分隐私下高效选择最接近的分布。
Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph
- 基于谢费图建模分布差异，减少查询次数。
- 仅需约 $\tilde{O}(k^{3/2})$ 次非自适应查询。
- 适合高精度隐私保护下的假设选择任务。
我们提出一种新算法，解决了在本地差分隐私约束下进行假设选择的问题。给定一组 $k$ 个概率分布 $Q$，该算法满足本地差分隐私，对每个来自分布 $p$ 的个体执行 $ ilde{O}(k^{3/2})$ 次非自适应查询，并输出 $Q$ 中一个与 $p$ 几乎最接近的分布。此前方法要么需要 $Ω(k^2)$ 次查询，要么依赖多轮交互式查询。技术上，我们引入了一种称为谢费图（Scheffé graph）的新结构，刻画了 $Q$ 中分布间的差异关系，可能对更广泛的假设选择任务具有价值。
原文摘要 · Abstract (English)
We propose an algorithm with improved query-complexity for the problem of hypothesis selection under local differential privacy constraints. Given a set of $k$ probability distributions $Q$, we describe an algorithm that satisfies local differential privacy, performs $\tilde{O}(k^{3/2})$ non-adaptive queries to individuals who each have samples from a probability distribution $p$, and outputs a probability distribution from the set $Q$ which is nearly the closest to $p$. Previous algorithms required either $Ω(k^2)$ queries or many rounds of interactive queries. Technically, we introduce a new object we dub the Scheffé graph, which captures structure of the differences between distributions in $Q$, and may be of more broad interest for hypothesis selection tasks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。