Hypothesis Set Stability and Generalization
Dylan J Foster, Spencer Greenberg, Satyen Kale, Haipeng Luo, Mehryar Mohri, Karthik Sridharan
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.
BibTeX
@inproceedings{NEURIPS2019_300d1539,
author = {Foster, Dylan J and Greenberg, Spencer and Kale, Satyen and Luo, Haipeng and Mohri, Mehryar and Sridharan, Karthik},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Wallach and H. Larochelle and A. Beygelzimer and F. d\textquotesingle Alch\'{e}-Buc and E. Fox and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Hypothesis Set Stability and Generalization},
url = {https://proceedings.neurips.cc/paper_files/paper/2019/file/300d1539c3b6aa1793b5678b857732cf-Paper.pdf},
volume = {32},
year = {2019}
}