Hypothesis Set Stability and Generalization
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Algorithmic Stability and Uniform Generalization
One of the central questions in statistical learning theory is to determine the conditions under which agents can learn from experience. This includes the necessary and sufficient conditions for generalization from a giv…
Dimensionality ReductionLearning TheorySample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds
We present new information-theoretic generalization guarantees through the a novel construction of the "neighboring-hypothesis" matrix and a new family of stability notions termed sample-conditioned hypothesis (SCH) stab…
Generalization BoundsBoosting the Confidence of Generalization for $L_2$-Stable Randomized Learning Algorithms
Exponential generalization bounds with near-tight rates have recently been established for uniformly stable learning algorithms. The notion of uniform stability, however, is stringent in the sense that it is invariant to…
Generalization BoundsAlgorithmic stability and hypothesis complexity
We introduce a notion of algorithmic stability of learning algorithms---that we term \emph{argument stability}---that captures stability of the hypothesis output by the learning algorithm in the normed space of functions…
An Exponential Efron-Stein Inequality for Lq Stable Learning Rules
There is accumulating evidence in the literature that stability of learning algorithms is a key characteristic that permits a learning algorithm to generalize. Despite various insightful results in this direction, there …
Generalization Bounds