# Shuffling-Aware Optimization for Private Vector Mean Estimation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 25 references that are in the map.
- First posted on arXiv 30 Apr 2026.

## Builds on (most cited first, 19 of 19)

- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [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)
- [Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling](https://mlsanity.com/paper/2012.12803/) (2020)
- [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)
- [Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation](https://mlsanity.com/paper/2001.03618/) (2020)
- [Optimal Algorithms for Mean Estimation under Local Differential Privacy](https://mlsanity.com/paper/2205.02466/) (2022)
- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [How Private are DP-SGD Implementations?](https://mlsanity.com/paper/2403.17673/) (2024)
- [Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message](https://mlsanity.com/paper/2109.13158/) (2021)
- [Renyi Differential Privacy of the Subsampled Shuffle Model in Distributed Learning](https://mlsanity.com/paper/2107.08763/) (2021)
- [Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages](https://mlsanity.com/paper/2404.10201/) (2024)
- [Aggregation and Transformation of Vector-Valued Messages in the Shuffle Model of Differential Privacy](https://mlsanity.com/paper/2201.13266/) (2022)
- [Analysis of Shuffling Beyond Pure Local Differential Privacy](https://mlsanity.com/paper/2601.19154/) (2026)

## Abstract (arXiv)

We study d-dimensional unbiased mean estimation in the single-message shuffle model, where each user sends a single privatized message and the analyzer only observes the shuffled multiset of reports. While minimax-optimal mechanisms are well understood in the local differential privacy setting, the corresponding notion of optimality after shuffling has remained largely unexplored. To address this gap, we introduce the recently proposed shuffle index and use it to formulate the post-shuffling mechanism design problem as an explicit optimization problem. We then establish a minimax lower bound on the achievable mean squared error in terms of the shuffle index, which implies that mechanisms that are optimal under LDP can become suboptimal once shuffling is applied. Finally, we construct an asymptotically minimax optimal mechanism in the high privacy regime, which as a consequence achieves a privacy-utility trade-off nearly identical to that of the central Gaussian mechanism.