# Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages

arXiv: https://arxiv.org/abs/2404.10201 · HTML: https://mlsanity.com/paper/2404.10201/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 48 references that are in the map.
- First posted on arXiv 16 Apr 2024.

## Builds on (most cited first, 30 of 31)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [Protection Against Reconstruction and Its Applications in Private Federated Learning](https://mlsanity.com/paper/1812.00984/) (2018)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [The Privacy Blanket of the Shuffle Model](https://mlsanity.com/paper/1903.02837/) (2019)
- [Breaking the Communication-Privacy-Accuracy Trilemma](https://mlsanity.com/paper/2007.11707/) (2020)
- [Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization](https://mlsanity.com/paper/1512.09170/) (2015)
- [Local, Private, Efficient Protocols for Succinct Histograms](https://mlsanity.com/paper/1504.04686/) (2015)
- [Prio: Private, Robust, and Scalable Computation of Aggregate Statistics](https://mlsanity.com/paper/1703.06255/) (2017)
- [Optimal Algorithms for Mean Estimation under Local Differential Privacy](https://mlsanity.com/paper/2205.02466/) (2022)
- [Private Summation in the Multi-Message Shuffle Model](https://mlsanity.com/paper/2002.00817/) (2020)
- [Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacy](https://mlsanity.com/paper/1702.00610/) (2017)
- [Manipulation Attacks in Local Differential Privacy](https://mlsanity.com/paper/1909.09630/) (2019)
- [Lossless Compression of Efficient Private Local Randomizers](https://mlsanity.com/paper/2102.12099/) (2021)
- [Collecting and Analyzing Data from Smart Device Users with Local Differential Privacy](https://mlsanity.com/paper/1606.05053/) (2016)
- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message](https://mlsanity.com/paper/2109.13158/) (2021)
- [Shuffle Private Stochastic Convex Optimization](https://mlsanity.com/paper/2106.09805/) (2021)
- [Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data Dictionaries](https://mlsanity.com/paper/1503.01214/) (2015)
- [Private Aggregation from Fewer Anonymous Messages](https://mlsanity.com/paper/1909.11073/) (2019)
- [Fast Optimal Locally Private Mean Estimation via Random Projections](https://mlsanity.com/paper/2306.04444/) (2023)
- [Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters](https://mlsanity.com/paper/1905.11888/) (2019)
- [On Distributed Differential Privacy and Counting Distinct Elements](https://mlsanity.com/paper/2009.09604/) (2020)
- [The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation](https://mlsanity.com/paper/2009.08000/) (2020)
- [On the Round Complexity of the Shuffle Model](https://mlsanity.com/paper/2009.13510/) (2020)
- [Differential Secrecy for Distributed Data and Applications to Robust Differentially Secure Vector Summation](https://mlsanity.com/paper/2202.10618/) (2022)
- [Applying the Shuffle Model of Differential Privacy to Vector Aggregation](https://mlsanity.com/paper/2112.05464/) (2021)
- [Aggregation and Transformation of Vector-Valued Messages in the Shuffle Model of Differential Privacy](https://mlsanity.com/paper/2201.13266/) (2022)

## Built on by (most cited first, 5 of 5)

- [Revisiting Active Sequential Prediction-Powered Mean Estimation](https://mlsanity.com/paper/2604.18569/) (2026)
- [Learning with User-Level Local Differential Privacy](https://mlsanity.com/paper/2405.17079/) (2024)
- [Beyond Statistical Estimation: Differentially Private Individual Computation via Shuffling](https://mlsanity.com/paper/2406.18145/) (2024)
- [PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors](https://mlsanity.com/paper/2503.11897/) (2025)
- [Shuffling-Aware Optimization for Private Vector Mean Estimation](https://mlsanity.com/paper/2604.28032/) (2026)

## Abstract (arXiv)

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 tildeOleft(min(nvarepsilon2,d)right) messages per user. Moreover, we show that any (unbiased) protocol that achieves optimal error requires each user to send Omega(min(nvarepsilon2,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 O(dnd/(d+2)varepsilon-4/(d+2)). Moreover, we show that any single-message protocol must incur mean squared error Omega(dnd/(d+2)), showing that our protocol is optimal in the standard setting where varepsilon = Theta(1). Finally, we study robustness to malicious users and show that malicious users can incur large additive error with a single shuffler.