TY - JOUR
T1 - Hypothesis set stability and generalization
AU - Foster, Dylan J.
AU - Greenberg, Spencer
AU - Kale, Satyen
AU - Luo, Haipeng
AU - Mohri, Mehryar
AU - Sridharan, Karthik
N1 - Funding Information:
Acknowledgements. HL is supported by NSF IIS-1755781. The work of SG and MM was partly supported by NSF CCF-1535987, NSF IIS-1618662, and a Google Research Award. KS would like to acknowledge NSF CAREER Award 1750575 and Sloan Research Fellowship.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85090171258&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85090171258&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:85090171258
VL - 32
JO - Advances in Neural Information Processing Systems
JF - Advances in Neural Information Processing Systems
SN - 1049-5258
T2 - 33rd Annual Conference on Neural Information Processing Systems, NeurIPS 2019
Y2 - 8 December 2019 through 14 December 2019
ER -