# Renyi Differential Privacy of the Subsampled Shuffle Model in Distributed Learning

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 45 references that are in the map.
- First posted on arXiv 19 Jul 2021.

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

- [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)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Federated Machine Learning: Concept and Applications](https://mlsanity.com/paper/1902.04885/) (2019)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [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)
- [R'enyi Differential Privacy of the Sampled Gaussian Mechanism](https://mlsanity.com/paper/1908.10530/) (2019)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (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)
- [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)
- [Tempered Sigmoid Activations for Deep Learning with Differential Privacy](https://mlsanity.com/paper/2007.14191/) (2020)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [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)
- [The Privacy Blanket of the Shuffle Model](https://mlsanity.com/paper/1903.02837/) (2019)
- [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)
- [Privacy Amplification via Random Check-Ins](https://mlsanity.com/paper/2007.06605/) (2020)
- [Private Summation in the Multi-Message Shuffle Model](https://mlsanity.com/paper/2002.00817/) (2020)
- [Three Variants of Differential Privacy: Lossless Conversion and Applications](https://mlsanity.com/paper/2008.06529/) (2020)
- [Scalable and Differentially Private Distributed Aggregation in the Shuffled Model](https://mlsanity.com/paper/1906.08320/) (2019)
- [On the Renyi Differential Privacy of the Shuffle Model](https://mlsanity.com/paper/2105.05180/) (2021)
- [Differentially Private Summation with Multi-Message Shuffling](https://mlsanity.com/paper/1906.09116/) (2019)
- [Improved Summation from Shuffling](https://mlsanity.com/paper/1909.11225/) (2019)

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

- [Differentially Private Federated Learning on Heterogeneous Data](https://mlsanity.com/paper/2111.09278/) (2021)
- [Shuffle Gaussian Mechanism for Differential Privacy](https://mlsanity.com/paper/2206.09569/) (2022)
- [Learning from End User Data with Shuffled Differential Privacy over Kernel Densities](https://mlsanity.com/paper/2502.14087/) (2025)
- [Multi-Message Shuffled Privacy in Federated Learning](https://mlsanity.com/paper/2302.11152/) (2023)
- [DPBalance: Efficient and Fair Privacy Budget Scheduling for Federated Learning as a Service](https://mlsanity.com/paper/2402.09715/) (2024)
- [Shuffling-Aware Optimization for Private Vector Mean Estimation](https://mlsanity.com/paper/2604.28032/) (2026)

## Abstract (arXiv)

We study privacy in a distributed learning framework, where clients collaboratively build a learning model iteratively through interactions with a server from whom we need privacy. Motivated by stochastic optimization and the federated learning (FL) paradigm, we focus on the case where a small fraction of data samples are randomly sub-sampled in each round to participate in the learning process, which also enables privacy amplification. To obtain even stronger local privacy guarantees, we study this in the shuffle privacy model, where each client randomizes its response using a local differentially private (LDP) mechanism and the server only receives a random permutation (shuffle) of the clients' responses without their association to each client. The principal result of this paper is a privacy-optimization performance trade-off for discrete randomization mechanisms in this sub-sampled shuffle privacy model. This is enabled through a new theoretical technique to analyze the Renyi Differential Privacy (RDP) of the sub-sampled shuffle model. We numerically demonstrate that, for important regimes, with composition our bound yields significant improvement in privacy guarantee over the state-of-the-art approximate Differential Privacy (DP) guarantee (with strong composition) for sub-sampled shuffled models. We also demonstrate numerically significant improvement in privacy-learning performance operating point using real data sets.