mlsanityData to 7 Oct 2026

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

arXiv 2404.10201 ↗First posted 16 Apr 2024cs.DS cs.CR cs.ITcited by 5

Not on the map. Why?

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.

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

Builds on

31 of 48 references.

References · 31

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2016Deep Learning with Differential Privacycited by 2,682
  3. 2018Amplification by Shuffling: From Local to Central Differential Privacy via Anonymitycited by 163
  4. 2018Protection Against Reconstruction and Its Applications in Private Federated Learningcited by 127
  5. 2018Distributed Differential Privacy via Shufflingcited by 115
  6. 2016Minimax Optimal Procedures for Locally Private Estimationcited by 103
  7. 2019The Privacy Blanket of the Shuffle Modelcited by 73
  8. 2020Breaking the Communication-Privacy-Accuracy Trilemmacited by 68
  9. 2015Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimizationcited by 41
  10. 2022Optimal Algorithms for Mean Estimation under Local Differential Privacycited by 36
  11. 2015Local, Private, Efficient Protocols for Succinct Histogramscited by 35
  12. 2017Prio: Private, Robust, and Scalable Computation of Aggregate Statisticscited by 35
19 more
  1. 2020Private Summation in the Multi-Message Shuffle Modelcited by 34
  2. 2017Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacycited by 28
  3. 2021Lossless Compression of Efficient Private Local Randomizerscited by 27
  4. 2016Collecting and Analyzing Data from Smart Device Users with Local Differential Privacycited by 25
  5. 2019Manipulation Attacks in Local Differential Privacycited by 23
  6. 2023Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimationcited by 22
  7. 2021Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Messagecited by 18
  8. 2021Shuffle Private Stochastic Convex Optimizationcited by 17
  9. 2015Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data Dictionariescited by 16
  10. 2019Private Aggregation from Fewer Anonymous Messagescited by 15
  11. 2023Fast Optimal Locally Private Mean Estimation via Random Projectionscited by 14
  12. 2019Communication Complexity in Locally Private Distribution Estimation and Heavy Hitterscited by 11
  13. 2020On Distributed Differential Privacy and Counting Distinct Elementscited by 8
  14. 2020The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimationcited by 7
  15. 2020On the Round Complexity of the Shuffle Modelcited by 5
  16. 2022Differential Secrecy for Distributed Data and Applications to Robust Differentially Secure Vector Summationcited by 5
  17. 2021Applying the Shuffle Model of Differential Privacy to Vector Aggregationcited by 2
  18. 2022Aggregation and Transformation of Vector-Valued Messages in the Shuffle Model of Differential Privacycited by 2
  19. 2023PINE: Efficient Norm-Bound Verification for Secret-Shared Vectorscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 1; 2026: 2.

5 papers.

  1. 2024Learning with User-Level Local Differential Privacycited by 3
  2. 2026Revisiting Active Sequential Prediction-Powered Mean Estimationcited by 3
  3. 2024Beyond Statistical Estimation: Differentially Private Individual Computation via Shufflingcited by 1
  4. 2025PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectorscited by 1
  5. 2026Shuffling-Aware Optimization for Private Vector Mean Estimationcited by 0