Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages
我们研究了隐私混洗模型中的隐私向量均值估计问题，其中 nnn 个用户各自在 ddd 维度中都有一个单位向量。我们提出了一种新的多消息协议，该协议使用每个用户 O~(min(nε2,d))\tilde{\mathcal{O}}\left(\min(n\varepsilon^2,d)\right)O~(min(nε2,d)) 条消息来实现最优误差。此外，我们表明，任何实现最优误差的（无偏）协议都要求每个用户发送 Ω(min(nε2,d)/log(n))\Omega(\min(n\varepsilon^2,d)/\log(n))Ω(min(nε2,d)/log(n)) 条消息，证明了我们的消息
