内容提要
论文指出联邦或分布式场景下的差分隐私选择任务存在效用差距,证明依赖标准噪声聚合原语需Ω(√d/ε)样本。作者提出实现稀疏向量技术(SVT)的新原语,并据此设计ε-差分隐私选择算法,在维度d下加性误差为O(log(dn)/ε),与中心模型相当,且仅需近最优的O(d log* d)次SVT查询,从而与shuffle/聚合模型形成指数级分离,并适用于Fp损失最小化、频繁项识别和稀疏均值估计等任务。
延伸解读
聚合模型下的固有局限
文章指出,在联邦或分布式场景中,依赖标准噪声聚合原语的差分隐私选择算法需要至少Ω(√d/ε)个样本,才能达到一定的效用。这意味着在聚合模型下,选择任务的误差下界较高,与中心模型存在显著差距。这一结果揭示了现有框架(如本地、混洗或安全聚合)在处理选择任务时的内在限制,并非实现细节问题。
新原语SVT带来的效用提升
作者提出实现稀疏向量技术(SVT)的新原语,并基于此设计ε-差分隐私选择算法。该算法在维度d下加性误差为O(log(dn)/ε),当n是d的多项式时,与中心模型的误差相当。此外,算法仅需近最优的O(d log* d)次SVT查询,显著降低了查询复杂度。这表明通过引入SVT原语,可以在聚合模型中实现接近中心模型的效用。
与混洗模型的指数级分离
结合混洗模型已有的下界,文章证明了SVT模型与混洗或聚合模型之间存在指数级分离。这意味着在相同的隐私保证下,SVT模型能够以更少的样本或更低的误差完成选择任务,而混洗模型则无法做到。这一理论结果强调了SVT原语在分布式差分隐私中的潜力,为设计更高效的隐私算法提供了新方向。
广泛的任务适用性
文章展示了SVT模型可应用于多种任务,包括Fp损失最小化、频繁项识别和稀疏均值估计。这些任务在联邦学习或分布式数据分析中常见,且通常对效用要求较高。新算法在这些任务上均能保持与中心模型相当的误差,表明其不仅限于选择问题,还具有更广泛的实用价值。
Q&A
联邦或分布式场景下做差分隐私选择,为什么效果不如中心化模型?
因为依赖标准噪声聚合原语的选择算法需要至少 Ω(√d/ε) 个样本,这造成了固有的效用差距,使得误差较高。
论文提出了什么新原语来改进差分隐私选择?
论文提出了一种实现稀疏向量技术(SVT)的新原语,并论证了它在多种信任模型下都有简单实现。
新算法在维度d下的加性误差是多少?与中心模型相比如何?
新算法的加性误差为 O(log(dn)/ε),当 n 是 d 的多项式界时,与中心模型的误差相匹配。
新算法需要多少次SVT查询?是否接近最优?
需要期望 O(d log* d) 次SVT查询,这是接近最优的查询复杂度。
SVT模型与shuffle或聚合模型之间有什么理论分离结果?
结合shuffle模型已有的下界,该结果证明了SVT模型与shuffle或基于聚合的模型之间存在指数级分离。
这种基于SVT的差分隐私选择方法能用在哪些任务上?
该方法适用于Fp损失最小化、频繁项识别(heavy-hitter identification)和稀疏均值估计等任务。