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

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 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