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.
Cite
Text
Foster et al. "Hypothesis Set Stability and Generalization." Neural Information Processing Systems, 2019.Markdown
[Foster et al. "Hypothesis Set Stability and Generalization." Neural Information Processing Systems, 2019.](https://mlanthology.org/neurips/2019/foster2019neurips-hypothesis/)BibTeX
@inproceedings{foster2019neurips-hypothesis,
title = {{Hypothesis Set Stability and Generalization}},
author = {Foster, Dylan J and Greenberg, Spencer and Kale, Satyen and Luo, Haipeng and Mohri, Mehryar and Sridharan, Karthik},
booktitle = {Neural Information Processing Systems},
year = {2019},
pages = {6729-6739},
url = {https://mlanthology.org/neurips/2019/foster2019neurips-hypothesis/}
}