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.

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

References in corpus (3)

• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Generalization Bounds for Uniformly Stable Algorithms
• Subgaussian Tail Bounds via Stability Arguments

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