mlsanityData to 7 Oct 2026

Information-Theoretic Generalization Bounds for Stochastic Gradient Descent

arXiv 2102.00931 ↗First posted 1 Feb 2021cs.LG stat.MLcited by 84

Not on the map. Why?

Abstract (arXiv)

We study the generalization properties of the popular stochastic optimization method known as stochastic gradient descent (SGD) for optimizing general non-convex loss functions. Our main contribution is providing upper bounds on the generalization error that depend on local statistics of the stochastic gradients evaluated along the path of iterates calculated by SGD. The key factors our bounds depend on are the variance of the gradients (with respect to the data distribution) and the local smoothness of the objective function along the SGD path, and the sensitivity of the loss function to perturbations to the final output. Our key technical tool is combining the information-theoretic generalization bounds previously used for analyzing randomized variants of SGD with a perturbation analysis of the iterates.

Key facts. Cited by 84 papers in the map (data through 7 Oct 2026). Builds on 41 of its 64 references that are in the map. First posted on arXiv 1 Feb 2021.

Builds on

41 of 64 references.

References · 41

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,337
  3. 2018Averaging Weights Leads to Wider Optima and Better Generalizationcited by 1,194
  4. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  5. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  6. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  7. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  8. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
  9. 2017Sharp Minima Can Generalize For Deep Netscited by 462
  10. 2016Entropy-SGD: Biasing Gradient Descent Into Wide Valleyscited by 357
  11. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
  12. 2015Norm-Based Capacity Control in Neural Networkscited by 299
29 more
  1. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  2. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 242
  3. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  4. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  5. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  6. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 145
  7. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 118
  8. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  9. 2014Preserving Statistical Validity in Adaptive Data Analysiscited by 102
  10. 2018Privacy Amplification by Iterationcited by 97
  11. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  12. 2015How much does your data exploration overfit? Controlling bias via information usagecited by 95
  13. 2019Sharper bounds for uniformly stable algorithmscited by 91
  14. 2019Asymmetric Valleys: Beyond Sharp and Flat Local Minimacited by 90
  15. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
  16. 2018Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?cited by 87
  17. 2018Generalization Error Bounds for Noisy, Iterative Algorithmscited by 79
  18. 2015Generalization in Adaptive Data Analysis and Holdout Reusecited by 76
  19. 2018Chaining Mutual Information and Tightening Generalization Boundscited by 65
  20. 2019Generalization bounds for deep convolutional neural networkscited by 58
  21. 2013A PAC-Bayesian Tutorial with A Dropout Boundcited by 43
  22. 2017Calibrating Noise to Variance in Adaptive Data Analysiscited by 28
  23. 2020On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithmcited by 28
  24. 2018Iterate averaging as regularization for stochastic gradient descentcited by 27
  25. 2017Generalization for Adaptively-chosen Estimators via Stable Mediancited by 26
  26. 2020Extrapolation for Large-batch Training in Deep Learningcited by 25
  27. 2018Spread Divergencecited by 23
  28. 2019Beating SGD Saturation with Tail-Averaging and Minibatchingcited by 21
  29. 2019Chaining Meets Chain Rule: Multilevel Entropic Regularization and Training of Neural Netscited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 20; 2023: 17; 2024: 15; 2025: 17; 2026: 6.

84 papers.

Sort:

By area:

  1. 2021User-friendly introduction to PAC-Bayes boundscited by 234
  2. 2022Towards Understanding Sharpness-Aware Minimizationcited by 145
  3. 2022Neural Networks Efficiently Learn Low-Dimensional Representations with SGDcited by 61
  4. 2021Information-theoretic generalization bounds for black-box learning algorithmscited by 49
  5. 2021Heavy Tails in SGD and Compressibility of Overparametrized Neural Networkscited by 44
  6. 2022Topology-aware Generalization of Decentralized SGDcited by 37
  7. 2021On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implicationscited by 31
  8. 2021Towards a Unified Information-Theoretic Framework for Generalizationcited by 29
  9. 2022A New Family of Generalization Bounds Using Samplewise Evaluated CMIcited by 28
  10. 2021Generalization Bounds using Lower Tail Exponents in Stochastic Optimizerscited by 27
  11. 2021Time-independent Generalization Bounds for SGLD in Non-convex Settingscited by 27
  12. 2022Generalization Bounds via Convex Analysiscited by 27
38 more
  1. 2022Single Trajectory Nonparametric Learning of Nonlinear Dynamicscited by 26
  2. 2022Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problemscited by 25
  3. 2023Tighter Information-Theoretic Generalization Bounds from Supersamplescited by 21
  4. 2022Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GDcited by 19
  5. 2022Benign Underfitting of Stochastic Gradient Descentcited by 18
  6. 2022Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimizationcited by 18
  7. 2023Information Theoretic Lower Bounds for Information Theoretic Upper Boundscited by 16
  8. 2021Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channelscited by 15
  9. 2022Information-Theoretic Analysis of Unsupervised Domain Adaptationcited by 15
  10. 2023Algorithmic Stability of Heavy-Tailed SGD with General Loss Functionscited by 15
  11. 2023Online-to-PAC Conversions: Generalization Bounds via Regret Analysiscited by 14
  12. 2024A PAC-Bayesian Link Between Generalisation and Flat Minimacited by 13
  13. 2022Two Facets of SDE Under an Information-Theoretic Lens: Generalization of SGD via Training Trajectories and via Terminal Statescited by 11
  14. 2022Chained Generalisation Boundscited by 10
  15. 2023More Communication Does Not Result in Smaller Generalization Error in Federated Learningcited by 10
  16. 2023Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithmcited by 10
  17. 2024Information-Theoretic Generalization Bounds for Deep Neural Networkscited by 10
  18. 2022Information bottleneck theory of high-dimensional regression: relevancy, efficiency and optimalitycited by 9
  19. 2022Generalisation under gradient descent via deterministic PAC-Bayescited by 9
  20. 2023Data-dependent Generalization Bounds via Variable-Size Compressibilitycited by 9
  21. 2024Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Setscited by 9
  22. 2022Stability Based Generalization Bounds for Exponential Family Langevin Dynamicscited by 8
  23. 2022On Leave-One-Out Conditional Mutual Information For Generalizationcited by 8
  24. 2024Enhancing Domain Adaptation through Prompt Gradient Alignmentcited by 8
  25. 2023Inconsistency, Instability, and Generalization Gap of Deep Neural Network Trainingcited by 6
  26. 2025Implicit Regularisation in Diffusion Models: An Algorithm-Dependent Generalisation Analysiscited by 6
  27. 2022On generalization bounds for deep networks based on loss surface implicit regularizationcited by 5
  28. 2023Learning Trajectories are Generalization Indicatorscited by 5
  29. 2023Understanding the Generalization Ability of Deep Learning Algorithms: A Kernelized Renyi's Entropy Perspectivecited by 5
  30. 2023Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Boundscited by 5
  31. 2025Entropy-Guided Token Dropout: Training Autoregressive Language Models with Limited Domain Datacited by 5
  32. 2022Benefits of Additive Noise in Composing Classes with Bounded Capacitycited by 4
  33. 2025Algorithm- and Data-Dependent Generalization Bounds for Diffusion Modelscited by 4
  34. 2024How Does Distribution Matching Help Domain Generalization: An Information-theoretic Analysiscited by 3
  35. 2024Generalization Bounds via Conditional f-Informationcited by 3
  36. 2025Fairness Overfitting in Machine Learning: An Information-Theoretic Perspectivecited by 3
  37. 2025Fisher information flow in artificial neural networkscited by 3
  38. 2023Generalization Error Bounds for Noisy, Iterative Algorithms via Maximal Leakagecited by 2

50 most cited of 84 All 84 (JSON)