# Stability Based Generalization Bounds for Exponential Family Langevin Dynamics

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 79 references that are in the map.
- First posted on arXiv 9 Jan 2022.

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

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017)
- [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)
- [QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding](https://mlsanity.com/paper/1610.02132/) (2016)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [The Discrete Gaussian for Differential Privacy](https://mlsanity.com/paper/2004.00010/) (2020)
- [Label Noise SGD Provably Prefers Flat Global Minimizers](https://mlsanity.com/paper/2106.06530/) (2021)
- [Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates](https://mlsanity.com/paper/1911.02151/) (2019)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Tightening Mutual Information Based Bounds on Generalization Error](https://mlsanity.com/paper/1901.04609/) (2019)
- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification](https://mlsanity.com/paper/2007.03813/) (2020)
- [Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms](https://mlsanity.com/paper/2004.12983/) (2020)
- [Information-Theoretic Generalization Bounds for Stochastic Gradient Descent](https://mlsanity.com/paper/2102.00931/) (2021)
- [Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints](https://mlsanity.com/paper/1707.05947/) (2017)
- [Generalization Error Bounds for Noisy, Iterative Algorithms](https://mlsanity.com/paper/1801.04295/) (2018)
- [Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo](https://mlsanity.com/paper/1502.07645/) (2015)
- [On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning](https://mlsanity.com/paper/1902.00621/) (2019)
- [Generalization Bounds for Uniformly Stable Algorithms](https://mlsanity.com/paper/1812.09859/) (2018)
- [Private Adaptive Gradient Methods for Convex Optimization](https://mlsanity.com/paper/2106.13756/) (2021)
- [Generalization Bounds via Information Density and Conditional Information Density](https://mlsanity.com/paper/2005.08044/) (2020)
- [SWALP : Stochastic Weight Averaging in Low-Precision Training](https://mlsanity.com/paper/1904.11943/) (2019)

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

- [Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2212.13556/) (2022)
- [Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds](https://mlsanity.com/paper/2310.20102/) (2023)
- [Learning Trajectories are Generalization Indicators](https://mlsanity.com/paper/2304.12579/) (2023)
- [Lipschitzness Effect of a Loss Function on Generalization Performance of Deep Neural Networks Trained by Adam and AdamW Optimizers](https://mlsanity.com/paper/2303.16464/) (2023)
- [Towards Understanding the Generalizability of Delayed Stochastic Gradient Descent](https://mlsanity.com/paper/2308.09430/) (2023)
- [Beyond Single-Model Views for Deep Learning: Optimization versus Generalizability of Stochastic Optimization Algorithms](https://mlsanity.com/paper/2403.00574/) (2024)
- [Stability-based Generalization Bounds for Variational Inference](https://mlsanity.com/paper/2502.12353/) (2025)
- [Two tales for a geometric Jensen--Shannon divergence](https://mlsanity.com/paper/2508.05066/) (2025)

## Abstract (arXiv)

Recent years have seen advances in generalization bounds for noisy stochastic algorithms, especially stochastic gradient Langevin dynamics (SGLD) based on stability (Mou et al., 2018; Li et al., 2020) and information theoretic approaches (Xu and Raginsky, 2017; Negrea et al., 2019; Steinke and Zakynthinou, 2020). In this paper, we unify and substantially generalize stability based generalization bounds and make three technical contributions. First, we bound the generalization error in terms of expected (not uniform) stability which arguably leads to quantitatively sharper bounds. Second, as our main contribution, we introduce Exponential Family Langevin Dynamics (EFLD), a substantial generalization of SGLD, which includes noisy versions of Sign-SGD and quantized SGD as special cases. We establish data-dependent expected stability based generalization bounds for any EFLD algorithm with a O(1/n) sample dependence and dependence on gradient discrepancy rather than the norm of gradients, yielding significantly sharper bounds. Third, we establish optimization guarantees for special cases of EFLD. Further, empirical results on benchmarks illustrate that our bounds are non-vacuous, quantitatively sharper than existing bounds, and behave correctly under noisy labels.