Hypothesis Set Stability and Generalization

Abstract

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.

Published in NeurIPS 2019. This version is equivalent to the camera-ready version but also includes the supplementary material

References in corpus (1)

• Generalization Bounds for Uniformly Stable Algorithms

Cited by in corpus (7)

• Sharper bounds for uniformly stable algorithms
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent
• Stability and Generalization of Stochastic Gradient Methods for Minimax Problems
• PAC-Bayes Analysis Beyond the Usual Bounds
• Improved Learning Rates for Stochastic Optimization
• Churn Reduction via Distillation
• Relative Deviation Margin Bounds