提出统一框架,用熵流分析各类马尔可夫学习算法的泛化误差。
Generalization Bounds for Markov Algorithms through Entropy Flow Computations
- 基于连续时间近似与精确熵流公式,扩展熵流方法至所有时齐马尔可夫算法。
- 建立泛化误差与马尔可夫过程遍历性的新联系,导出多类算法的新界。
- 适用于含噪声迭代学习算法,尤其适合理论研究者深入理解泛化机制。
许多学习算法可表征为马尔可夫过程,其泛化误差分析是学习理论的核心问题。针对特定连续时间噪声算法,已有信息论工具和“熵流”方法能结合学习动态的收敛性,得出有意义的泛化界,且可推广至离散时间情形。然而,现有熵流形式仅限于特定噪声与算法结构(如Langevin动力学)。本文通过引入新的技术工具,将该方法扩展至所有由时齐马尔可夫过程驱动的迭代学习算法。我们的方法基于对马尔可夫算法的严格连续时间逼近,并提出一类新的精确熵流公式。在此统一框架下,我们建立了与经典修正对数Sobolev不等式家族的新联系,将泛化误差与马尔可夫过程的遍历性质关联起来。最后,我们详细分析了理论中各项含义,并通过推导若干具体算法的泛化界,验证了该方法的有效性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。