mlsanityData to 7 Oct 2026

Generalization Bounds using Lower Tail Exponents in Stochastic Optimizers

arXiv 2108.00781 ↗First posted 2 Aug 2021stat.ML cs.LGcited by 27

Not on the map. Why?

Abstract (arXiv)

Despite the ubiquitous use of stochastic optimization algorithms in machine learning, the precise impact of these algorithms and their dynamics on generalization performance in realistic non-convex settings is still poorly understood. While recent work has revealed connections between generalization and heavy-tailed behavior in stochastic optimization, this work mainly relied on continuous-time approximations; and a rigorous treatment for the original discrete-time iterations is yet to be performed. To bridge this gap, we present novel bounds linking generalization to the lower tail exponent of the transition kernel associated with the optimizer around a local minimum, in both discrete- and continuous-time settings. To achieve this, we first prove a data- and algorithm-dependent generalization bound in terms of the celebrated Fernique-Talagrand functional applied to the trajectory of the optimizer. Then, we specialize this result by exploiting the Markovian structure of stochastic optimizers, and derive bounds in terms of their (data-dependent) transition kernels. We support our theory with empirical results from a variety of neural networks, showing correlations between generalization error and lower tail exponents.

Key facts. Cited by 27 papers in the map (data through 7 Oct 2026). Builds on 42 of its 76 references that are in the map. First posted on arXiv 2 Aug 2021.

Builds on

42 of 76 references.

References · 42

  1. 2020Scaling Laws for Neural Language Modelscited by 6,411
  2. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  3. 2017Exploring Generalization in Deep Learningcited by 595
  4. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  5. 2019Fantastic Generalization Measures and Where to Find Themcited by 507
  6. 2019Implicit Regularization in Deep Matrix Factorizationcited by 402
  7. 2018Stronger generalization bounds for deep nets via a compression approachcited by 306
  8. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  9. 2017Three Factors Influencing Minima in SGDcited by 270
  10. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 267
  11. 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 213
  12. 2018Implicit Self-Regularization in Deep Neural Networks: Evidence from Random Matrix Theory and Implications for Learningcited by 211
30 more
  1. 2020The Break-Even Point on Optimization Trajectories of Deep Neural Networkscited by 149
  2. 2020The Heavy-Tail Phenomenon in SGDcited by 122
  3. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 118
  4. 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
  5. 2020Predicting trends in the quality of state-of-the-art neural networks without access to training or testing datacited by 113
  6. 2019Traditional and Heavy-Tailed Self Regularization in Neural Network Modelscited by 104
  7. 2015How much does your data exploration overfit? Controlling bias via information usagecited by 95
  8. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
  9. 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 84
  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. 2018A Walk with SGDcited by 74
  14. 2018Chaining Mutual Information and Tightening Generalization Boundscited by 65
  15. 2020Catastrophic Fisher Explosion: Early Phase Fisher Matrix Impacts Generalizationcited by 61
  16. 2019Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networkscited by 60
  17. 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
  18. 2016A Variational Analysis of Stochastic Gradient Algorithmscited by 56
  19. 2021Heavy Tails in SGD and Compressibility of Overparametrized Neural Networkscited by 44
  20. 2019Heavy-Tailed Universality Predicts Trends in Test Accuracies for Very Large Pre-Trained Deep Neural Networkscited by 43
  21. 2019On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networkscited by 42
  22. 2020Stochasticity of Deterministic Gradient Descent: Large Learning Rate for Multiscale Objective Functioncited by 26
  23. 2020Failures of model-dependent generalization bounds for least-norm interpolationcited by 26
  24. 2017Rethinking generalization requires revisiting old ideas: statistical mechanics approaches and complex learning behaviorcited by 24
  25. 2021Fractal Structure and Generalization Properties of Stochastic Optimization Algorithmscited by 23
  26. 2019Non-Gaussianity of Stochastic Gradient Noisecited by 22
  27. 2021Post-mortem on a deep learning contest: a Simpson's paradox and the complementary roles of scale metrics versus shape metricscited by 19
  28. 2018Continuous-time Models for Stochastic Optimization Algorithmscited by 16
  29. 2020Majorizing Measures for the Optimizercited by 4
  30. 2020Convergence rates and approximation results for SGD and its continuous-time counterpartcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 8; 2024: 4; 2025: 7; 2026: 5.

27 papers.

Sort:

By area:

  1. 2022Learning continuous models for continuous physicscited by 28
  2. 2023Temperature Balancing, Layer-wise Weight Analysis, and Neural Network Trainingcited by 19
  3. 2023From Stability to Chaos: Analyzing Gradient Descent Dynamics in Quadratic Regressioncited by 16
  4. 2023Generalization Bounds with Data-dependent Fractal Dimensionscited by 15
  5. 2022Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squarescited by 12
  6. 2024Model Balancing Helps Low-data Training and Fine-tuningcited by 11
  7. 2026HTMuon: Improving Muon via Heavy-Tailed Spectral Correctioncited by 11
  8. 2023Data-dependent Generalization Bounds via Variable-Size Compressibilitycited by 9
  9. 2024Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Setscited by 9
  10. 2024From Spikes to Heavy Tails: Unveiling the Spectral Evolution of Neural Networkscited by 9
  11. 2025Models of Heavy-Tailed Mechanistic Universalitycited by 9
  12. 2025Eigenspectrum Analysis of Neural Networks without Aspect Ratio Biascited by 9
15 more
  1. 2023A unified framework for information-theoretic generalization boundscited by 6
  2. 2022Generalization Bounds for Gradient Methods via Discrete and Continuous Priorcited by 5
  3. 2023Generalization Guarantees via Algorithm-dependent Rademacher Complexitycited by 4
  4. 2023From Mutual Information to Expected Dynamics: New Generalization Bounds for Heavy-Tailed SGDcited by 4
  5. 2025Algorithm- and Data-Dependent Generalization Bounds for Diffusion Modelscited by 4
  6. 2023Approximate Heavy Tails in Offline (Multi-Pass) Stochastic Gradient Descentcited by 3
  7. 2024Tighter Generalisation Bounds via Interpolationcited by 2
  8. 2025Generalization Bounds for Markov Algorithms through Entropy Flow Computationscited by 2
  9. 2025Generalization Guarantees for Representation Learning via Data-Dependent Gaussian Mixture Priorscited by 2
  10. 2025Multiview Representation Learning via Distributed Joint Latent Space Structuringcited by 1
  11. 2025Stability, Complexity and Data-Dependent Worst-Case Generalization Boundscited by 1
  12. 2026Unveiling Multi-regime Patterns in SciML: Distinct Failure Modes and Regime-specific Optimizationcited by 1
  13. 2026Generalization at the Edge of Stabilitycited by 0
  14. 2026Spectral Signatures of Large Language Modelscited by 0
  15. 2026Dimension-Corrected Hitting Times for Heavy-Tailed Spectral Emergence in Neural Optimizer Dynamicscited by 0