Hypothesis Set Stability and Generalization
This work addresses generalization theory for machine learning practitioners, but it is incremental as it extends existing bounds to data-dependent scenarios.
The authors tackled the problem of generalization for data-dependent hypothesis sets by introducing a new notion of hypothesis set stability and Rademacher complexity, resulting in a general learning guarantee that unifies standard Rademacher complexity and algorithm-dependent uniform stability bounds.
We present a study of generalization for data-dependent hypothesis sets. We give a general learning guarantee for data-dependent hypothesis sets based on a notion of transductive Rademacher complexity. Our main result is a generalization bound for data-dependent hypothesis sets expressed in terms of a notion of hypothesis set stability and a notion of Rademacher complexity for data-dependent hypothesis sets that we introduce. This bound admits as special cases both standard Rademacher complexity bounds and algorithm-dependent uniform stability bounds. We also illustrate the use of these learning bounds in the analysis of several scenarios.