mlsanityData to 7 Oct 2026

Towards Understanding Generalization via Decomposing Excess Risk Dynamics

arXiv 2106.06153 ↗First posted 11 Jun 2021cs.LG cs.AI stat.MLcited by 5

Not on the map. Why?

Abstract (arXiv)

Generalization is one of the fundamental issues in machine learning. However, traditional techniques like uniform convergence may be unable to explain generalization under overparameterization. As alternative approaches, techniques based on stability analyze the training dynamics and derive algorithm-dependent generalization bounds. Unfortunately, the stability-based bounds are still far from explaining the surprising generalization in deep learning since neural networks usually suffer from unsatisfactory stability. This paper proposes a novel decomposition framework to improve the stability-based bounds via a more fine-grained analysis of the signal and noise, inspired by the observation that neural networks converge relatively slowly when fitting noise (which indicates better stability). Concretely, we decompose the excess risk dynamics and apply the stability-based bound only on the noise component. The decomposition framework performs well in both linear regimes (overparameterized linear regression) and non-linear regimes (diagonal matrix recovery). Experiments on neural networks verify the utility of the decomposition framework.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 44 of its 63 references that are in the map. First posted on arXiv 11 Jun 2021.

Builds on

44 of 63 references.

References · 44

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  3. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  4. 2017Exploring Generalization in Deep Learningcited by 595
  5. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  6. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  7. 2019Benign Overfitting in Linear Regressioncited by 544
  8. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
  9. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  10. 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 339
  11. 2017Implicit Regularization in Matrix Factorizationcited by 318
  12. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
32 more
  1. 2018Stronger generalization bounds for deep nets via a compression approachcited by 306
  2. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  3. 2019Uniform convergence may be unable to explain generalization in deep learningcited by 223
  4. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  5. 2017Generalization in Deep Learningcited by 146
  6. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 145
  7. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 127
  8. 2018Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approachcited by 125
  9. 2016Matrix Completion has No Spurious Local Minimumcited by 124
  10. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  11. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  12. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  13. 2019Sharper bounds for uniformly stable algorithmscited by 91
  14. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
  15. 2020Shape Matters: Understanding the Implicit Bias of the Noise Covariancecited by 88
  16. 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
  17. 2020Understanding Double Descent Requires a Fine-Grained Bias-Variance Decompositioncited by 75
  18. 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
  19. 2019Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobiancited by 67
  20. 2019The Implicit Bias of Depth: How Incremental Learning Drives Generalizationcited by 64
  21. 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
  22. 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
  23. 2019Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margincited by 56
  24. 2019In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictorscited by 44
  25. 2021Stability of SGD: Tightness Analysis and Improved Boundscited by 33
  26. 2021On the computational and statistical complexity of over-parameterized matrix sensingcited by 31
  27. 2019Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recoverycited by 26
  28. 2019Fast-rate PAC-Bayes Generalization Bounds via Shifted Rademacher Processescited by 20
  29. 2018Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimizationcited by 14
  30. 2021Information Complexity and Generalization Boundscited by 14
  31. 2020The Deep Bootstrap Framework: Good Online Learners are Good Offline Generalizerscited by 10
  32. 2021Understanding Generalization in Adversarial Training via the Bias-Variance Decompositioncited by 10

Built on by

Cited by year (2026 to 7 Oct)

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

5 papers.

  1. 2023Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimizationcited by 6
  2. 2022Towards Data-Algorithm Dependent Generalization: a Case Study on Overparameterized Linear Regressioncited by 3
  3. 2026ERGO: Excess-Risk-Guided Optimization for High-Fidelity Monocular 3D Gaussian Splattingcited by 1
  4. 2024Understanding Generalization of Federated Learning: the Trade-off between Model Stability and Optimizationcited by 0
  5. 2026Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networkscited by 0