Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages
CoRR(2024)
摘要
We study the problem of private vector mean estimation in the shuffle model
of privacy where n users each have a unit vector v^(i)∈ℝ^d.
We propose a new multi-message protocol that achieves the optimal error using
𝒪̃(min(nε^2,d)) messages per user.
Moreover, we show that any (unbiased) protocol that achieves optimal error
requires each user to send Ω(min(nε^2,d)/log(n)) messages,
demonstrating the optimality of our message complexity up to logarithmic
factors. Additionally, we study the single-message setting and design a
protocol that achieves mean squared error
𝒪(dn^d/(d+2)ε^-4/(d+2)). Moreover, we show that any
single-message protocol must incur mean squared error Ω(dn^d/(d+2)),
showing that our protocol is optimal in the standard setting where ε
= Θ(1). Finally, we study robustness to malicious users and show that
malicious users can incur large additive error with a single shuffler.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要