# Multi-Message Shuffled Privacy in Federated Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 65 references that are in the map.
- First posted on arXiv 22 Feb 2023.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Extracting Training Data from Large Language Models](https://mlsanity.com/paper/2012.07805/) (2020)
- [Deep Leakage from Gradients](https://mlsanity.com/paper/1906.08935/) (2019)
- [Inverting Gradients -- How easy is it to break privacy in federated learning?](https://mlsanity.com/paper/2003.14053/) (2020)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Subsampled R'enyi Differential Privacy and Analytical Moments Accountant](https://mlsanity.com/paper/1808.00087/) (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)
- [Expanding the Reach of Federated Learning by Reducing Client Resource Requirements](https://mlsanity.com/paper/1812.07210/) (2018)
- [cpSGD: Communication-efficient and differentially-private distributed SGD](https://mlsanity.com/paper/1805.10559/) (2018)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Distributed Mean Estimation with Limited Communication](https://mlsanity.com/paper/1611.00429/) (2016)
- [The Discrete Gaussian for Differential Privacy](https://mlsanity.com/paper/2004.00010/) (2020)
- [Protection Against Reconstruction and Its Applications in Private Federated Learning](https://mlsanity.com/paper/1812.00984/) (2018)
- [The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation](https://mlsanity.com/paper/2102.06387/) (2021)
- [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)
- [Hypothesis Testing Interpretations and Renyi Differential Privacy](https://mlsanity.com/paper/1905.09982/) (2019)
- [Fingerprinting Codes and the Price of Approximate Differential Privacy](https://mlsanity.com/paper/1311.3158/) (2013)
- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [Breaking the Communication-Privacy-Accuracy Trilemma](https://mlsanity.com/paper/2007.11707/) (2020)
- [Discrete Distribution Estimation under Local Privacy](https://mlsanity.com/paper/1602.07387/) (2016)
- [Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation](https://mlsanity.com/paper/2001.03618/) (2020)
- [The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning](https://mlsanity.com/paper/2203.03761/) (2022)
- [Optimal Algorithms for Mean Estimation under Local Differential Privacy](https://mlsanity.com/paper/2205.02466/) (2022)

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

- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacy](https://mlsanity.com/paper/2405.02341/) (2024)

## Abstract (arXiv)

We study differentially private distributed optimization under communication constraints. A server using SGD for optimization aggregates the client-side local gradients for model updates using distributed mean estimation (DME). We develop a communication-efficient private DME, using the recently developed multi-message shuffled (MMS) privacy framework. We analyze our proposed DME scheme to show that it achieves the order-optimal privacy-communication-performance tradeoff resolving an open question in [1], whether the shuffled models can improve the tradeoff obtained in Secure Aggregation. This also resolves an open question on the optimal trade-off for private vector sum in the MMS model. We achieve it through a novel privacy mechanism that non-uniformly allocates privacy at different resolutions of the local gradient vectors. These results are directly applied to give guarantees on private distributed learning algorithms using this for private gradient aggregation iteratively. We also numerically evaluate the private DME algorithms.