# Practical and Private (Deep) Learning without Sampling or Shuffling

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

## Key facts

- Cited by 170 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 77 references that are in the map.
- First posted on arXiv 26 Feb 2021.

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

- [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)
- [Adaptive Federated Optimization](https://mlsanity.com/paper/2003.00295/) (2020)
- [Towards Federated Learning at Scale: System Design](https://mlsanity.com/paper/1902.01046/) (2019)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Subsampled R'enyi Differential Privacy and Analytical Moments Accountant](https://mlsanity.com/paper/1808.00087/) (2018)
- [Differentially Private Learning Needs Better Features (or Much More Data)](https://mlsanity.com/paper/2011.11660/) (2020)
- [Differentially Private Learning with Adaptive Clipping](https://mlsanity.com/paper/1905.03871/) (2019)
- [Auditing Differentially Private Machine Learning: How Private is Private SGD?](https://mlsanity.com/paper/2006.07709/) (2020)
- [Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning](https://mlsanity.com/paper/2101.04535/) (2021)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [The Discrete Gaussian for Differential Privacy](https://mlsanity.com/paper/2004.00010/) (2020)
- [Tempered Sigmoid Activations for Deep Learning with Differential Privacy](https://mlsanity.com/paper/2007.14191/) (2020)
- [Privacy Amplification by Iteration](https://mlsanity.com/paper/1808.06651/) (2018)
- [Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling](https://mlsanity.com/paper/2012.12803/) (2020)
- [A General Approach to Adding Differential Privacy to Iterative Training Procedures](https://mlsanity.com/paper/1812.06210/) (2018)
- [AdaCliP: Adaptive Clipping for Private SGD](https://mlsanity.com/paper/1908.07643/) (2019)
- [Training Production Language Models without Memorizing User Data](https://mlsanity.com/paper/2009.10031/) (2020)
- [The Price of Differential Privacy For Online Learning](https://mlsanity.com/paper/1701.07953/) (2017)
- [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)
- [Understanding Unintended Memorization in Federated Learning](https://mlsanity.com/paper/2006.07490/) (2020)
- [A Better Bound Gives a Hundred Rounds: Enhanced Privacy Guarantees via f-Divergences](https://mlsanity.com/paper/2001.05990/) (2020)
- [Online Learning via the Differential Privacy Lens](https://mlsanity.com/paper/1711.10019/) (2017)

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

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Federated Learning with Buffered Asynchronous Aggregation](https://mlsanity.com/paper/2106.06639/) (2021)
- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [FedScale: Benchmarking Model and System Performance of Federated Learning at Scale](https://mlsanity.com/paper/2105.11367/) (2021)
- [Toward Training at ImageNet Scale with Differential Privacy](https://mlsanity.com/paper/2201.12328/) (2022)
- [The Skellam Mechanism for Differentially Private Federated Learning](https://mlsanity.com/paper/2110.04995/) (2021)
- [Federated Learning of Gboard Language Models with Differential Privacy](https://mlsanity.com/paper/2305.18465/) (2023)
- [Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams](https://mlsanity.com/paper/2202.08312/) (2022)
- [Public Data-Assisted Mirror Descent for Private Model Training](https://mlsanity.com/paper/2112.00193/) (2021)
- [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://mlsanity.com/paper/2306.08153/) (2023)
- [Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning](https://mlsanity.com/paper/2401.10371/) (2024)
- [Differentially Private Learning Needs Hidden State (Or Much Faster Convergence)](https://mlsanity.com/paper/2203.05363/) (2022)
- [Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning](https://mlsanity.com/paper/2211.06530/) (2022)
- [Node-Level Differentially Private Graph Neural Networks](https://mlsanity.com/paper/2111.15521/) (2021)
- [Private Adaptive Optimization with Side Information](https://mlsanity.com/paper/2202.05963/) (2022)
- [On the Convergence and Calibration of Deep Learning with Differential Privacy](https://mlsanity.com/paper/2106.07830/) (2021)
- [On Privacy and Personalization in Cross-Silo Federated Learning](https://mlsanity.com/paper/2206.07902/) (2022)
- [One-shot Empirical Privacy Estimation for Federated Learning](https://mlsanity.com/paper/2302.03098/) (2023)
- [User Inference Attacks on Large Language Models](https://mlsanity.com/paper/2310.09266/) (2023)
- [Privacy-Preserving Instructions for Aligning Large Language Models](https://mlsanity.com/paper/2402.13659/) (2024)
- [DP-SGD vs PATE: Which Has Less Disparate Impact on Model Accuracy?](https://mlsanity.com/paper/2106.12576/) (2021)
- [Teach LLMs to Phish: Stealing Private Information from Language Models](https://mlsanity.com/paper/2403.00871/) (2024)
- [Quantum machine learning with differential privacy](https://mlsanity.com/paper/2103.06232/) (2021)
- [On the Convergence of Federated Averaging with Cyclic Client Participation](https://mlsanity.com/paper/2302.03109/) (2023)
- [Can Public Large Language Models Help Private Cross-device Federated Learning?](https://mlsanity.com/paper/2305.12132/) (2023)
- [PrE-Text: Training Language Models on Private Federated Data in the Age of LLMs](https://mlsanity.com/paper/2406.02958/) (2024)
- [Fine-Tuning Large Language Models with User-Level Differential Privacy](https://mlsanity.com/paper/2407.07737/) (2024)
- [Almost Tight Error Bounds on Differentially Private Continual Counting](https://mlsanity.com/paper/2211.05006/) (2022)
- [CANIFE: Crafting Canaries for Empirical Privacy Measurement in Federated Learning](https://mlsanity.com/paper/2210.02912/) (2022)
- [Grounding Foundation Models through Federated Transfer Learning: A General Framework](https://mlsanity.com/paper/2311.17431/) (2023)

## Abstract (arXiv)

We consider training models with differential privacy (DP) using mini-batch gradients. The existing state-of-the-art, Differentially Private Stochastic Gradient Descent (DP-SGD), requires privacy amplification by sampling or shuffling to obtain the best privacy/accuracy/computation trade-offs. Unfortunately, the precise requirements on exact sampling and shuffling can be hard to obtain in important practical scenarios, particularly federated learning (FL). We design and analyze a DP variant of Follow-The-Regularized-Leader (DP-FTRL) that compares favorably (both theoretically and empirically) to amplified DP-SGD, while allowing for much more flexible data access patterns. DP-FTRL does not use any form of privacy amplification. The code is available at https://github.com/google-research/federated/tree/master/dp_ftrl and https://github.com/google-research/DP-FTRL .