mlsanityData to 7 Oct 2026

Stability Based Generalization Bounds for Exponential Family Langevin Dynamics

arXiv 2201.03064 ↗First posted 9 Jan 2022cs.LG stat.MLcited by 8

Not on the map. Why?

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.

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

Builds on

38 of 79 references.

References · 38

  1. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,283
  2. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  3. 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 561
  4. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  5. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  6. 2017How to Escape Saddle Points Efficientlycited by 284
  7. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 242
  8. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  9. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  10. 2016QSGD: Communication-Efficient SGD via Gradient Quantization and Encodingcited by 147
  11. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 145
  12. 2020The Discrete Gaussian for Differential Privacycited by 134
26 more
  1. 2021Label Noise SGD Provably Prefers Flat Global Minimizerscited by 121
  2. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 118
  3. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  4. 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
  5. 2014Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Boundscited by 104
  6. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  7. 2019Sharper bounds for uniformly stable algorithmscited by 91
  8. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
  9. 2020Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identificationcited by 88
  10. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  11. 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
  12. 2018Generalization Error Bounds for Noisy, Iterative Algorithmscited by 79
  13. 2015Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlocited by 61
  14. 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
  15. 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
  16. 2021Private Adaptive Gradient Methods for Convex Optimizationcited by 46
  17. 2020Generalization Bounds via Information Density and Conditional Information Densitycited by 43
  18. 2019SWALP : Stochastic Weight Averaging in Low-Precision Trainingcited by 40
  19. 2021PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classescited by 31
  20. 2020Individually Conditional Individual Mutual Information Bound on Generalization Errorcited by 30
  21. 2019Distributed Training with Heterogeneous Data: Bridging Median- and Mean-Based Algorithmscited by 29
  22. 2020On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithmcited by 28
  23. 2021Time-independent Generalization Bounds for SGLD in Non-convex Settingscited by 27
  24. 2021Wide Network Learning with Differential Privacycited by 17
  25. 2017On Connecting Stochastic Gradient MCMC and Differential Privacycited by 15
  26. 2020Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspacescited by 10

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 4; 2024: 1; 2025: 2.

8 papers.

  1. 2022Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimizationcited by 18
  2. 2023Learning Trajectories are Generalization Indicatorscited by 5
  3. 2023Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Boundscited by 5
  4. 2023Lipschitzness Effect of a Loss Function on Generalization Performance of Deep Neural Networks Trained by Adam and AdamW Optimizerscited by 2
  5. 2023Towards Understanding the Generalizability of Delayed Stochastic Gradient Descentcited by 0
  6. 2024Beyond Single-Model Views for Deep Learning: Optimization versus Generalizability of Stochastic Optimization Algorithmscited by 0
  7. 2025Stability-based Generalization Bounds for Variational Inferencecited by 0
  8. 2025Two tales for a geometric Jensen--Shannon divergencecited by 0