Hypothesis Set Stability and Generalization

2019/04/09 by Foster, Dylan J., Greenberg, Spencer, Kale, Satyen +3 · 4 citations
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1904.04755

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.

Cited by

• Disentangled and Distilled Encoder for Out-of-Distribution Reasoning with Rademacher Guarantees
• A Bootstrap Perspective on Stochastic Gradient Descent
• Revisiting Knowledge Distillation: The Hidden Role of Dataset Size
• Stability, Complexity and Data-Dependent Worst-Case Generalization Bounds

Related

• Generalization Guarantees via Algorithm-dependent Rademacher Complexity
• On the Rademacher Complexity of Linear Hypothesis Sets
• Learning from weakly dependent data under Dobrushin's condition
• Algorithmic stability and hypothesis complexity
• Lean Formalization of Generalization Error Bound by Rademacher Complexity