通过联邦 API 进行差分隐私选择的复杂度

媒体报道 Apple 机器学习 原文语言:英文

论文研究差分隐私选择问题在联邦场景中的复杂度:证明依赖标准噪声聚合的算法需要 Ω(√d/ε) 样本,并提出稀疏向量技术(SVT)新原语,使附加误差降至 O(log(dn)/ε),与中心模型一致,仅需近最优 O(d log* d) 次查询,与 shuffle 模型形成指数级差距,适用于 Fp 损失最小化、热门项识别等任务。一名作者来自 Anthropic。

全文

Complexity of Differentially Private Selection via Federated APIs

AuthorsHilal Asi, Vitaly Feldman, Jelani Nelson†, Huy L. Nguyen‡, Kunal Talwar, Samson Zhou§

Differential privacy (DP) has become the standard for privacy-preserving data analysis, yet its practical implementation in federated or distributed settings often faces a significant utility gap compared to the central model. While existing frameworks, including local, shuffle, and secure aggregation models, offer vetted primitives, they can incur high error for important tasks such as selection. Our first contribution is to show that this is inherent in the aggregation model: any private selection algorithm relying on the standard noisy aggregation primitive requires Ω(d/ϵ)Ω(\sqrt{d} / \epsilon)Ω(d​/ϵ) samples. To address this limitation, we propose adding a new primitive that implements a version of the Sparse Vector Technique (SVT) and argue that it has simple implementations under various trust models. We demonstrate its power by developing an εεε-differentially private algorithm for the selection problem. For selection in dimension ddd, our algorithm achieves an additive error of O(log⁡(dn)ε)O\left(\frac{\log(dn)}{\varepsilon}\right)O(εlog(dn)​), matching that of the central model when nnn is polynomially bounded in ddd. Furthermore, we show that this can be done using a near-optimal expected number O(dlog⁡∗d)O(d \log^* d)O(dlog∗d) of SVT queries. Together with existing lower bounds for the shuffle model, this result establishes an exponential separation between the SVT model and shuffle or aggregation-based models. We demonstrate the model’s broad applicability to diverse tasks such as FpF_pFp​ loss minimization, heavy-hitter identification, and sparse mean estimation.

† Anthropic; work done while at UC Berkeley

‡ Northeastern

§ Texas A&M University

正文以来源语言显示。

参考来源

← 返回每日AI报告