# Privacy Amplification via Random Check-Ins

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2020.

## Built on by (most cited first, 30 of 39)

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Federated Learning of Gboard Language Models with Differential Privacy](https://mlsanity.com/paper/2305.18465/) (2023)
- [What Do We Mean by Generalization in Federated Learning?](https://mlsanity.com/paper/2110.14216/) (2021)
- [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://mlsanity.com/paper/2306.08153/) (2023)
- [Sparse Random Networks for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2209.15328/) (2022)
- [On the Convergence of Federated Averaging with Cyclic Client Participation](https://mlsanity.com/paper/2302.03109/) (2023)
- [Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses](https://mlsanity.com/paper/2106.09779/) (2021)
- [Fast and Memory Efficient Differentially Private-SGD via JL Projections](https://mlsanity.com/paper/2102.03013/) (2021)
- [Stronger Privacy Amplification by Shuffling for R'enyi and Approximate Differential Privacy](https://mlsanity.com/paper/2208.04591/) (2022)
- [Differentially private inference via noisy optimization](https://mlsanity.com/paper/2103.11003/) (2021)
- [Privacy Amplification for Federated Learning via User Sampling and Wireless Aggregation](https://mlsanity.com/paper/2103.01953/) (2021)
- [Differentially Private Natural Language Models: Recent Advances and Future Directions](https://mlsanity.com/paper/2301.09112/) (2023)
- [Privacy Amplification for Matrix Mechanisms](https://mlsanity.com/paper/2310.15526/) (2023)
- [Reconstructing Individual Data Points in Federated Learning Hardened with Differential Privacy and Secure Aggregation](https://mlsanity.com/paper/2301.04017/) (2023)
- [Privacy amplification by random allocation](https://mlsanity.com/paper/2502.08202/) (2025)
- [Balls-and-Bins Sampling for DP-SGD](https://mlsanity.com/paper/2412.16802/) (2024)
- [Leveraging Randomness in Model and Data Partitioning for Privacy Amplification](https://mlsanity.com/paper/2503.03043/) (2025)
- [Renyi Differential Privacy of the Subsampled Shuffle Model in Distributed Learning](https://mlsanity.com/paper/2107.08763/) (2021)
- [Network Shuffling: Privacy Amplification via Random Walks](https://mlsanity.com/paper/2204.03919/) (2022)
- [Hierarchical Federated Learning with Privacy](https://mlsanity.com/paper/2206.05209/) (2022)
- [Shuffle Gaussian Mechanism for Differential Privacy](https://mlsanity.com/paper/2206.09569/) (2022)
- [Differentially Private Deep Learning with ModelMix](https://mlsanity.com/paper/2210.03843/) (2022)
- [Learning from End User Data with Shuffled Differential Privacy over Kernel Densities](https://mlsanity.com/paper/2502.14087/) (2025)
- [Efficient privacy loss accounting for subsampling and random allocation](https://mlsanity.com/paper/2602.17284/) (2026)
- [Privacy Amplification via Random Participation in Federated Learning](https://mlsanity.com/paper/2205.01556/) (2022)
- [Collaborative Mean Estimation over Intermittently Connected Networks with Peer-To-Peer Privacy](https://mlsanity.com/paper/2303.00035/) (2023)
- [Privacy Preserving Semi-Decentralized Mean Estimation over Intermittently-Connected Networks](https://mlsanity.com/paper/2406.03766/) (2024)
- [Enhancing Privacy in the Early Detection of Sexual Predators Through Federated Learning and Differential Privacy](https://mlsanity.com/paper/2501.12537/) (2025)

## Abstract (arXiv)

Differentially Private Stochastic Gradient Descent (DP-SGD) forms a fundamental building block in many applications for learning over sensitive data. Two standard approaches, privacy amplification by subsampling, and privacy amplification by shuffling, permit adding lower noise in DP-SGD than via na"ive schemes. A key assumption in both these approaches is that the elements in the data set can be uniformly sampled, or be uniformly permuted -- constraints that may become prohibitive when the data is processed in a decentralized or distributed fashion. In this paper, we focus on conducting iterative methods like DP-SGD in the setting of federated learning (FL) wherein the data is distributed among many devices (clients). Our main contribution is the random check-in distributed protocol, which crucially relies only on randomized participation decisions made locally and independently by each client. It has privacy/accuracy trade-offs similar to privacy amplification by subsampling/shuffling. However, our method does not require server-initiated communication, or even knowledge of the population size. To our knowledge, this is the first privacy amplification tailored for a distributed learning framework, and it may have broader applicability beyond FL. Along the way, we extend privacy amplification by shuffling to incorporate (ε,δ)-DP local randomizers, and exponentially improve its guarantees. In practical regimes, this improvement allows for similar privacy and utility using data from an order of magnitude fewer users.