mlsanityData to 7 Oct 2026

Which Algorithms Have Tight Generalization Bounds?

arXiv 2410.01969 ↗First posted 2 Oct 2024cs.LG stat.MLcited by 1

Not on the map. Why?

Abstract (arXiv)

We study which machine learning algorithms have tight generalization bounds. First, we present conditions that preclude the existence of tight generalization bounds. Specifically, we show that algorithms that have certain inductive biases that cause them to be unstable do not admit tight generalization bounds. Next, we show that algorithms that are sufficiently stable do have tight generalization bounds. We conclude with a simple characterization that relates the existence of tight generalization bounds to the conditional variance of the algorithm's loss.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 24 of its 43 references that are in the map. First posted on arXiv 2 Oct 2024.

Builds on

24 of 43 references.

References · 24

  1. 2021Convex optimizationcited by 2,479
  2. 2019Benign Overfitting in Linear Regressioncited by 544
  3. 2019Fantastic Generalization Measures and Where to Find Themcited by 507
  4. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  5. 2019Uniform convergence may be unable to explain generalization in deep learningcited by 223
  6. 2020In Search of Robust Measures of Generalizationcited by 79
  7. 2020On the role of data in PAC-Bayes boundscited by 64
  8. 2021Information-theoretic generalization bounds for black-box learning algorithmscited by 49
  9. 2019Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakagecited by 48
  10. 2019In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictorscited by 44
  11. 2022Testing distributional assumptions of learning algorithmscited by 30
  12. 2022A New Family of Generalization Bounds Using Samplewise Evaluated CMIcited by 28
12 more
  1. 2020Failures of model-dependent generalization bounds for least-norm interpolationcited by 26
  2. 2020Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysiscited by 21
  3. 2022Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networkscited by 21
  4. 2023Tighter Information-Theoretic Generalization Bounds from Supersamplescited by 21
  5. 2022Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GDcited by 19
  6. 2023Fantastic Generalization Measures are Nowhere to be Foundcited by 19
  7. 2022Understanding Generalization via Leave-One-Out Conditional Mutual Informationcited by 16
  8. 2022On Leave-One-Out Conditional Mutual Information For Generalizationcited by 8
  9. 2024Leveraging PAC-Bayes Theory and Gibbs Distributions for Generalization Bounds with Complexity Measurescited by 7
  10. 2023Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimizationcited by 6
  11. 2023Mean-field Analysis of Generalization Errorscited by 5
  12. 2023Generalization Error Bounds for Noisy, Iterative Algorithms via Maximal Leakagecited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Minimax Limits of k-Fold Cross-Validation via Majoritycited by 0