Generalization Bounds for Markov Algorithms through Entropy Flow Computations
Not on the map. Why?
Abstract (arXiv)
Many learning algorithms can be represented as Markov processes, and understanding their generalization error is a central topic in learning theory. For specific continuous-time noisy algorithms, a prominent analysis technique relies on information-theoretic tools and the so-called ``entropy flow'' method. This technique is compatible with a broad range of assumptions and leverages the convergence properties of learning dynamics to produce meaningful generalization bounds, which can also be informative or extend to discrete-time settings. Despite their success, existing entropy flow formulations are limited to specific noise and algorithm structures (eg, Langevin dynamics). In this work, we exploit new technical tools to extend its applicability to all learning algorithms whose iterative dynamics is governed by a time-homogeneous Markov process. Our approach builds on a principled continuous-time approximation of Markov algorithms and introduces a new, exact entropy flow formula for such processes. Within this unified framework, we establish novel connections to a well-studied family of modified logarithmic Sobolev inequalities, which we use to connect the generalization error to the ergodic properties of Markov processes. Finally, we provide a detailed analysis of all the terms appearing in our theory and demonstrate its effectiveness by deriving new generalization bounds for several concrete algorithms.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 39 of its 88 references that are in the map. First posted on arXiv 11 Feb 2025.
Builds on
39 of 88 references.
References · 39
- 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,337
- 2017Exploring Generalization in Deep Learningcited by 595
- 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
- 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 413
- 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
- 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 242
- 2021User-friendly introduction to PAC-Bayes boundscited by 234
- 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 213
- 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
- 2020The Heavy-Tail Phenomenon in SGDcited by 122
- 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 118
- 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
27 more
- 2018Stochastic Modified Equations and Dynamics of Stochastic Gradient Algorithms I: Mathematical Foundationscited by 109
- 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
- 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
- 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 84
- 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
- 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
- 2021On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs)cited by 73
- 2021Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descentcited by 71
- 2022High-dimensional limit theorems for SGD: Effective dynamics and critical scalingcited by 69
- 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
- 2016A Variational Analysis of Stochastic Gradient Algorithmscited by 56
- 2022Anticorrelated Noise Injection for Improved Generalizationcited by 41
- 2021Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysiscited by 38
- 2019Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLTcited by 30
- 2021Generalization Bounds using Lower Tail Exponents in Stochastic Optimizerscited by 27
- 2021Time-independent Generalization Bounds for SGLD in Non-convex Settingscited by 27
- 2022Explicit Regularization in Overparametrized Models via Noise Injectioncited by 25
- 2021Fractal Structure and Generalization Properties of Stochastic Optimization Algorithmscited by 23
- 2015Perturbation theory for Markov chains via Wasserstein distancecited by 16
- 2021Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorizationcited by 15
- 2021A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossipcited by 15
- 2022Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squarescited by 12
- 2023Time-Independent Information-Theoretic Generalization Bounds for SGLDcited by 12
- 2022Generalisation under gradient descent via deterministic PAC-Bayescited by 9
- 2024Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Setscited by 9
- 2023Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic Gradient Descentcited by 6
- 2024Generalization Bounds for Heavy-Tailed SDEs through the Fractional Fokker-Planck Equationcited by 5
Built on by
Citing papers per year: 2025: 1; 2026: 1.
2 papers.