  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.
