Hypothesis set stability and generalization

Dylan J. Foster; Spencer Greenberg; Satyen Kale; Haipeng Luo; Mehryar Mohri; Karthik Sridharan

Hypothesis set stability and generalization

Dylan J. Foster, Spencer Greenberg, Satyen Kale, Haipeng Luo, Mehryar Mohri, Karthik Sridharan

Computer Science

Research output: Contribution to journal › Conference article › peer-review

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.

Original language	English (US)
Journal	Advances in Neural Information Processing Systems
Volume	32
State	Published - 2019
Event	33rd Annual Conference on Neural Information Processing Systems, NeurIPS 2019 - Vancouver, Canada Duration: Dec 8 2019 → Dec 14 2019

ASJC Scopus subject areas

Computer Networks and Communications
Information Systems
Signal Processing

Cite this

@article{b01f1e4c222d4e24b5aa69636ffe30f6,

title = "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.",

author = "Foster, {Dylan J.} and Spencer Greenberg and Satyen Kale and Haipeng Luo and Mehryar Mohri and Karthik Sridharan",

note = "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. Publisher Copyright: {\textcopyright} 2019 Neural information processing systems foundation. All rights reserved.; 33rd Annual Conference on Neural Information Processing Systems, NeurIPS 2019 ; Conference date: 08-12-2019 Through 14-12-2019",

year = "2019",

language = "English (US)",

volume = "32",

journal = "Advances in Neural Information Processing Systems",

issn = "1049-5258",

publisher = "Neural information processing systems foundation",

}

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. Publisher Copyright: © 2019 Neural information processing systems foundation. All rights reserved.

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

SN - 1049-5258

VL - 32

JO - Advances in Neural Information Processing Systems

JF - Advances in Neural Information Processing Systems

T2 - 33rd Annual Conference on Neural Information Processing Systems, NeurIPS 2019

Y2 - 8 December 2019 through 14 December 2019

ER -

Hypothesis set stability and generalization

Abstract

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this