# Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss

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

## Key facts

- Cited by 61 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 61 references that are in the map.
- First posted on arXiv 27 May 2022.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Opacus: User-Friendly Differential Privacy Library in PyTorch](https://mlsanity.com/paper/2109.12298/) (2021)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [R'enyi Differential Privacy of the Sampled Gaussian Mechanism](https://mlsanity.com/paper/1908.10530/) (2019)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1605.01559/) (2016)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Privacy Amplification by Iteration](https://mlsanity.com/paper/1808.06651/) (2018)
- [Private Selection from Private Candidates](https://mlsanity.com/paper/1811.07971/) (2018)
- [Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent](https://mlsanity.com/paper/2102.05855/) (2021)
- [Sampling from a log-concave distribution with Projected Langevin Monte Carlo](https://mlsanity.com/paper/1507.02564/) (2015)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Differentially Private Learning Needs Hidden State (Or Much Faster Convergence)](https://mlsanity.com/paper/2203.05363/) (2022)
- [Faster Differentially Private Samplers via R'enyi Divergence Analysis of Discretized Langevin MCMC](https://mlsanity.com/paper/2010.14658/) (2020)
- [LinkedIn's Audience Engagements API: A Privacy Preserving Data Analytics System at Scale](https://mlsanity.com/paper/2002.05839/) (2020)
- [Differential Privacy Guarantees for Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2201.11980/) (2022)

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

- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning](https://mlsanity.com/paper/2401.10371/) (2024)
- [Bounding Training Data Reconstruction in DP-SGD](https://mlsanity.com/paper/2302.07225/) (2023)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Provable Guarantees for Generative Behavior Cloning: Bridging Low-Level Stability and High-Level Behavior](https://mlsanity.com/paper/2307.14619/) (2023)
- [Improved dimension dependence of a proximal algorithm for sampling](https://mlsanity.com/paper/2302.10081/) (2023)
- [Reconstructing Training Data from Model Gradient, Provably](https://mlsanity.com/paper/2212.03714/) (2022)
- [Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling](https://mlsanity.com/paper/2210.08448/) (2022)
- [How Private are DP-SGD Implementations?](https://mlsanity.com/paper/2403.17673/) (2024)
- [Tighter Privacy Auditing of DP-SGD in the Hidden State Threat Model](https://mlsanity.com/paper/2405.14457/) (2024)
- [Scalable DP-SGD: Shuffling vs. Poisson Subsampling](https://mlsanity.com/paper/2411.04205/) (2024)
- [Certified Machine Unlearning via Noisy Stochastic Gradient Descent](https://mlsanity.com/paper/2403.17105/) (2024)
- [Unified Enhancement of Privacy Bounds for Mixture Mechanisms via f-Differential Privacy](https://mlsanity.com/paper/2310.19973/) (2023)
- [Shifted Interpolation for Differential Privacy](https://mlsanity.com/paper/2403.00278/) (2024)
- [Gradients Look Alike: Sensitivity is Often Overestimated in DP-SGD](https://mlsanity.com/paper/2307.00310/) (2023)
- [The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD](https://mlsanity.com/paper/2410.06186/) (2024)
- [Privacy Loss of Noisy Stochastic Gradient Descent Might Converge Even for Non-Convex Losses](https://mlsanity.com/paper/2305.09903/) (2023)
- [Neural Collapse Meets Differential Privacy: Curious Behaviors of NoisyGD with Near-perfect Representation Learning](https://mlsanity.com/paper/2405.08920/) (2024)
- [A Statistical Viewpoint on Differential Privacy: Hypothesis Testing, Representation and Blackwell's Theorem](https://mlsanity.com/paper/2409.09558/) (2024)
- [Convergent Privacy Loss of Noisy-SGD without Convexity and Smoothness](https://mlsanity.com/paper/2410.01068/) (2024)
- [Privacy of the last iterate in cyclically-sampled DP-SGD on nonconvex composite losses](https://mlsanity.com/paper/2407.05237/) (2024)
- [Convergence of the Inexact Langevin Algorithm in KL Divergence with Application to Score-based Generative Models](https://mlsanity.com/paper/2211.01512/) (2022)
- [From Noisy Fixed-Point Iterations to Private ADMM for Centralized and Federated Learning](https://mlsanity.com/paper/2302.12559/) (2023)
- [Differentially Private Graph Diffusion with Applications in Personalized PageRanks](https://mlsanity.com/paper/2407.00077/) (2024)
- [A survey on secure decentralized optimization and learning](https://mlsanity.com/paper/2408.08628/) (2024)
- [An Improved Privacy and Utility Analysis of Differentially Private SGD with Bounded Domain and Smooth Losses](https://mlsanity.com/paper/2502.17772/) (2025)
- [Privacy of SGD under Gaussian or Heavy-Tailed Noise: Guarantees without Gradient Clipping](https://mlsanity.com/paper/2403.02051/) (2024)
- [Enhancing Privacy in Federated Learning through Local Training](https://mlsanity.com/paper/2403.17572/) (2024)
- [Empirical Privacy Variance](https://mlsanity.com/paper/2503.12314/) (2025)
- [Mitigating Privacy-Utility Trade-off in Decentralized Federated Learning via f-Differential Privacy](https://mlsanity.com/paper/2510.19934/) (2025)

## Abstract (arXiv)

A central issue in machine learning is how to train models on sensitive user data. Industry has widely adopted a simple algorithm: Stochastic Gradient Descent with noise (a.k.a. Stochastic Gradient Langevin Dynamics). However, foundational theoretical questions about this algorithm's privacy loss remain open -- even in the seemingly simple setting of smooth convex losses over a bounded domain. Our main result resolves these questions: for a large range of parameters, we characterize the differential privacy up to a constant factor. This result reveals that all previous analyses for this setting have the wrong qualitative behavior. Specifically, while previous privacy analyses increase ad infinitum in the number of iterations, we show that after a small burn-in period, running SGD longer leaks no further privacy. Our analysis departs from previous approaches based on fast mixing, instead using techniques based on optimal transport (namely, Privacy Amplification by Iteration) and the Sampled Gaussian Mechanism (namely, Privacy Amplification by Sampling). Our techniques readily extend to other settings, e.g., strongly convex losses, non-uniform stepsizes, arbitrary batch sizes, and random or cyclic choice of batches.