mlsanityData to 14 Oct 2026

Generalization of Gibbs and Langevin Monte Carlo Algorithms in the Interpolation Regime

arXiv 2510.06028 ↗First posted 7 Oct 2025cs.LG stat.MLcited by 1

Not on the map. Why?

Abstract (arXiv)

This paper provides data-dependent bounds on the expected error of the Gibbs algorithm in the overparameterized interpolation regime, where low training errors are also obtained for impossible data, such as random labels in classification. The results show that generalization in the low-temperature regime is already signaled by small training errors in the noisier high-temperature regime. The bounds are stable under approximation with Langevin Monte Carlo algorithms. The analysis motivates the design of an algorithm to compute bounds, which on the MNIST, CIFAR-10, and SVHN datasets yield nontrivial, close predictions on the test error for true labeled data, while maintaining a correct upper bound on the test error for random labels.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 33 of its 59 references that are in the map. First posted on arXiv 7 Oct 2025.

Builds on

33 of 59 references.

References · 33

  1. 2014Very Deep Convolutional Networks for Large-Scale Image Recognitioncited by 15,364
  2. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  3. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  4. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 533
  5. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 303
  6. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 243
  7. 2021User-friendly introduction to PAC-Bayes boundscited by 239
  8. 2019Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Sufficescited by 227
  9. 2017A Conceptual Introduction to Hamiltonian Monte Carlocited by 209
  10. 2015Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithmcited by 197
  11. 2019A Primer on PAC-Bayesian Learningcited by 132
  12. 2018Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approachcited by 126
21 more
  1. 2018Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problemcited by 123
  2. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 119
  3. 2018Log-concave sampling: Metropolis-Hastings algorithms are fastcited by 118
  4. 2017User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradientcited by 116
  5. 2020Tighter risk certificates for neural networkscited by 112
  6. 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
  7. 2018Generalization Error Bounds for Noisy, Iterative Algorithmscited by 82
  8. 2017Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priorscited by 81
  9. 2022Improved analysis for a proximal algorithm for samplingcited by 73
  10. 2018Sharp convergence rates for Langevin dynamics in the nonconvex settingcited by 68
  11. 2020PAC-Bayes Analysis Beyond the Usual Boundscited by 63
  12. 2022Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlocited by 63
  13. 2018The promises and pitfalls of Stochastic Gradient Langevin Dynamicscited by 56
  14. 2019Stochastic gradient Markov chain Monte Carlocited by 56
  15. 2021Time-independent Generalization Bounds for SGLD in Non-convex Settingscited by 27
  16. 2019Distribution-Dependent Analysis of Gibbs-ERM Principlecited by 17
  17. 2023Time-Independent Information-Theoretic Generalization Bounds for SGLDcited by 12
  18. 2022Generalisation under gradient descent via deterministic PAC-Bayescited by 9
  19. 2024Generalization of Hamiltonian algorithmscited by 2
  20. 2025Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processescited by 2
  21. 2023Estimating optimal PAC-Bayes bounds with Hamiltonian Monte Carlocited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithmscited by 0