mlsanityData to 14 Oct 2026

Generalization error bounds for iterative learning algorithms with bounded updates

arXiv 2309.05077 ↗First posted 10 Sep 2023cs.LG stat.MLcited by 1

Not on the map. Why?

Abstract (arXiv)

This paper explores the generalization characteristics of iterative learning algorithms with bounded updates for non-convex loss functions, employing information-theoretic techniques. Our key contribution is a novel bound for the generalization error of these algorithms with bounded updates. Our approach introduces two main novelties: 1) we reformulate the mutual information as the uncertainty of updates, providing a new perspective, and 2) instead of using the chaining rule of mutual information, we employ a variance decomposition technique to decompose information across iterations, allowing for a simpler surrogate process. We analyze our generalization bound under various settings and demonstrate improved bounds. To bridge the gap between theory and practice, we also examine the previously observed scaling behavior in large language models. Ultimately, our work takes a further step for developing practical generalization theories.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 35 of its 50 references that are in the map. First posted on arXiv 10 Sep 2023.

Builds on

35 of 50 references.

References · 35

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2020Scaling Laws for Neural Language Modelscited by 6,586
  3. 2022Training Compute-Optimal Large Language Modelscited by 3,019
  4. 2020Sharpness-Aware Minimization for Efficiently Improving Generalizationcited by 1,417
  5. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  6. 2018On Lazy Training in Differentiable Programmingcited by 675
  7. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
  8. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  9. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 533
  10. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 427
  11. 2023Scaling Data-Constrained Language Modelscited by 403
  12. 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 341
23 more
  1. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 303
  2. 2019An Investigation into Neural Net Optimization via Hessian Eigenvalue Densitycited by 292
  3. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  4. 2016Eigenvalues of the Hessian in Deep Learning: Singularity and Beyondcited by 159
  5. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 141
  6. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 119
  7. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 119
  8. 2022Adaptive Gradient Methods at the Edge of Stabilitycited by 101
  9. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 98
  10. 2015How much does your data exploration overfit? Controlling bias via information usagecited by 95
  11. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
  12. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  13. 2018Generalization Error Bounds for Noisy, Iterative Algorithmscited by 82
  14. 2022How Does Sharpness-Aware Minimization Minimize Sharpness?cited by 65
  15. 2022The alignment property of SGD noise and how it helps select flat minima: A stability analysiscited by 64
  16. 2019In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictorscited by 44
  17. 2017Algorithmic stability and hypothesis complexitycited by 39
  18. 2022Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithmscited by 22
  19. 2018On the Generalization of Stochastic Gradient Descent with Momentumcited by 20
  20. 2022Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GDcited by 19
  21. 2022Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimizationcited by 19
  22. 2022On the Algorithmic Stability and Generalization of Adaptive Optimization Methodscited by 5
  23. 2023Learning Trajectories are Generalization Indicatorscited by 5

Built on by

Cited by year

Citing papers per year: 2024: 1.

1 paper.

  1. 2024A General Theory for Compositional Generalizationcited by 4