Algorithm- and data-dependent generalization bounds are required to explain the generalization behavior of modern machine learning algorithms. In this context, there exists information theoretic generalization bounds that involve (various forms of) mutual information, as well as bounds based on hypothesis set stability. We propose a conceptually related, but technically distinct complexity measure to control generalization error, which is the empirical Rademacher complexity of an algorithm- and data-dependent hypothesis class. Combining standard properties of Rademacher complexity with the convenient structure of this class, we are able to (i) obtain novel bounds based on the finite fractal dimension, which (a) extend previous fractal dimension-type bounds from continuous to finite hypothesis classes, and (b) avoid a mutual information term that was required in prior work; (ii) we greatly simplify the proof of a recent dimension-independent generalization bound for stochastic gradient descent; and (iii) we easily recover results for VC classes and compression schemes, similar to approaches based on conditional mutual information.

算法和数据相关的广义化界限是解释现代机器学习算法的广义化行为所必需的。在这个背景下，存在包括(各种形式的)互信息和基于假设集稳定性的信息论广义化界限。我们提出了一个概念上相关但技术上独特的复杂度度量方法来控制广义化误差，这就是算法和数据相关的假设类的经验Rademacher复杂度。通过结合Rademacher复杂度的标准特性和这个类的方便结构，我们能够(i)获得基于有限分形维度的新界限，这些界限将之前从连续假设类推广到有限假设类，并避免了先前工作中所需的互信息项；(ii)大大简化了最近一个和维度无关的随机梯度下降的广义化界限的证明；(iii)我们轻松恢复了VC类和压缩方案的结果，类似于基于条件互信息的方法。

通过算法相关的 Rademacher 复杂度实现泛化保证