[2502.07584] Generalization Bounds for Markov Algorithms through Entropy Flow Computations

Statistics > Machine Learning arXiv:2502.07584 (stat) [Submitted on 11 Feb 2025 (v1), last revised 5 Mar 2026 (this version, v2)] Title:Generalization Bounds for Markov Algorithms through Entropy Flow Computations Authors:Benjamin Dupuis, Maxime Haddouche, George Deligiannidis, Umut Simsekli View a PDF of the paper titled Generalization Bounds for Markov Algorithms through Entropy Flow Computations, by Benjamin Dupuis and 3 other authors View PDF HTML (experimental) Abstract: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. Wi...