Poster
Hypothesis Set Stability and Generalization
Dylan Foster · Spencer Greenberg · Satyen Kale · Haipeng Luo · Mehryar Mohri · Karthik Sridharan

Tue Dec 10th 05:30 -- 07:30 PM @ East Exhibition Hall B + C #220
in Theory -- Learning Theory »

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.

Keywords: Theory -> Learning Theory · Algorithms -> Model Selection and Structure Learning

Author Information

Dylan Foster (MIT)
Spencer Greenberg (Spark Wave)
Satyen Kale (Google)
Haipeng Luo (University of Southern California)
Mehryar Mohri (Courant Inst. of Math. Sciences & Google Research)
Karthik Sridharan (Cornell University)

More from the Same Authors