# Privacy of SGD under Gaussian or Heavy-Tailed Noise: Guarantees without Gradient Clipping

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 59 references that are in the map.
- First posted on arXiv 4 Mar 2024.

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

- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [Understanding Gradient Clipping in Private SGD: A Geometric Perspective](https://mlsanity.com/paper/2006.15429/) (2020)
- [Differentially Private Empirical Risk Minimization Revisited: Faster and More General](https://mlsanity.com/paper/1802.05251/) (2018)
- [Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping](https://mlsanity.com/paper/2005.10785/) (2020)
- [Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent](https://mlsanity.com/paper/2102.05855/) (2021)
- [Differentially Private Model Publishing for Deep Learning](https://mlsanity.com/paper/1904.02200/) (2019)
- [Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks](https://mlsanity.com/paper/2006.09313/) (2020)
- [Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss](https://mlsanity.com/paper/2205.13710/) (2022)
- [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)
- [Differential Privacy as a Mutual Information Constraint](https://mlsanity.com/paper/1608.03677/) (2016)
- [Global Non-convex Optimization with Discretized Diffusions](https://mlsanity.com/paper/1810.12361/) (2018)
- [First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noise](https://mlsanity.com/paper/1906.09069/) (2019)
- [Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks](https://mlsanity.com/paper/2106.03795/) (2021)
- [On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networks](https://mlsanity.com/paper/1912.00018/) (2019)
- [Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence](https://mlsanity.com/paper/2007.11612/) (2020)
- [Fractional Underdamped Langevin Dynamics: Retargeting SGD with Momentum under Heavy-Tailed Gradient Noise](https://mlsanity.com/paper/2002.05685/) (2020)
- [Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression](https://mlsanity.com/paper/1303.6149/) (2013)
- [Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration](https://mlsanity.com/paper/1809.04618/) (2018)
- [Faster Differentially Private Samplers via R'enyi Divergence Analysis of Discretized Langevin MCMC](https://mlsanity.com/paper/2010.14658/) (2020)
- [Three Variants of Differential Privacy: Lossless Conversion and Applications](https://mlsanity.com/paper/2008.06529/) (2020)
- [Differential Privacy Guarantees for Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2201.11980/) (2022)
- [Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models](https://mlsanity.com/paper/2303.04288/) (2023)
- [Perturbation theory for Markov chains via Wasserstein distance](https://mlsanity.com/paper/1503.04123/) (2015)
- [Statistical Indistinguishability of Learning Algorithms](https://mlsanity.com/paper/2305.14311/) (2023)
- [Algorithmic Stability of Heavy-Tailed SGD with General Loss Functions](https://mlsanity.com/paper/2301.11885/) (2023)
- [Differentially Private Accelerated Optimization Algorithms](https://mlsanity.com/paper/2008.01989/) (2020)
- [Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squares](https://mlsanity.com/paper/2206.01274/) (2022)

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

- [Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysis](https://mlsanity.com/paper/2603.19648/) (2026)
- [R'enyi Differential Privacy for Heavy-Tailed SDEs via Fractional Poincar'e Inequalities](https://mlsanity.com/paper/2511.15634/) (2025)
- [Bias-Variance Trade-off for Clipped Stochastic First-Order Methods: From Bounded Variance to Infinite Mean](https://mlsanity.com/paper/2512.14686/) (2025)

## Abstract (arXiv)

The injection of heavy-tailed noise into the iterates of stochastic gradient descent (SGD) has garnered growing interest in recent years due to its theoretical and empirical benefits for optimization and generalization. However, its implications for privacy preservation remain largely unexplored. Aiming to bridge this gap, we provide differential privacy (DP) guarantees for noisy SGD, when the injected noise follows an α-stable distribution, which includes a spectrum of heavy-tailed distributions (with infinite variance) as well as the light-tailed Gaussian distribution. Considering the (ε, δ)-DP framework, we show that SGD with heavy-tailed perturbations achieves (0, O(1/n))-DP for a broad class of loss functions which can be non-convex, where n is the number of data points. As a remarkable byproduct, contrary to prior work that necessitates bounded sensitivity for the gradients or clipping the iterates, our theory can handle unbounded gradients without clipping, and reveals that under mild assumptions, such a projection step is not actually necessary. Our results suggest that, given other benefits of heavy-tails in optimization, heavy-tailed noising schemes can be a viable alternative to their light-tailed counterparts.