标题： 通过稳定性获得的互信息自由拓扑泛化界 显示英文标题

标题： Mutual Information Free Topological Generalization Bounds via Stability

摘要： 为随机优化算法提供泛化保证是现代学习理论中的一个重大挑战。 最近，一些研究强调了训练轨迹的几何结构对泛化误差的影响，无论是理论上还是实证上。 在这些工作中，提出了一系列拓扑泛化界，将泛化误差与源于拓扑数据分析（TDA）的拓扑复杂性概念联系起来。 尽管这些界限在实证上取得了成功，但它们依赖于复杂的信息论（IT）项，这些项在特定情况下可以被限制，但对于实际算法（如ADAM）来说仍然难以处理，这可能会降低所推导界限的相关性。 在本文中，我们旨在制定全面且可解释的拓扑泛化界限，避免难以处理的互信息项。 为此，我们引入了一个新的学习理论框架，通过基于算法稳定性的证明技术，摆脱了现有的策略。 通过将现有的\textit{假设集稳定性}概念扩展到\textit{轨迹稳定性}，我们证明了轨迹稳定算法的泛化误差可以被上界表示为（i）描述优化器在参数空间中轨迹复杂性的TDA量，以及（ii）算法的轨迹稳定性参数。 通过一系列实验评估，我们证明了边界中的TDA项非常重要，尤其是在训练样本数量增加时。 这最终解释了拓扑泛化界限的实证成功。 显示英文摘要

摘要： Providing generalization guarantees for stochastic optimization algorithms is a major challenge in modern learning theory. Recently, several studies highlighted the impact of the geometry of training trajectories on the generalization error, both theoretically and empirically. Among these works, a series of topological generalization bounds have been proposed, relating the generalization error to notions of topological complexity that stem from topological data analysis (TDA). Despite their empirical success, these bounds rely on intricate information-theoretic (IT) terms that can be bounded in specific cases but remain intractable for practical algorithms (such as ADAM), potentially reducing the relevance of the derived bounds. In this paper, we seek to formulate comprehensive and interpretable topological generalization bounds free of intractable mutual information terms. To this end, we introduce a novel learning theoretic framework that departs from the existing strategies via proof techniques rooted in algorithmic stability. By extending an existing notion of \textit{hypothesis set stability}, to \textit{trajectory stability}, we prove that the generalization error of trajectory-stable algorithms can be upper bounded in terms of (i) TDA quantities describing the complexity of the trajectory of the optimizer in the parameter space, and (ii) the trajectory stability parameter of the algorithm. Through a series of experimental evaluations, we demonstrate that the TDA terms in the bound are of great importance, especially as the number of training samples grows. This ultimately forms an explanation of the empirical success of the topological generalization bounds.