Timezone: »

 
Poster
A Sample Complexity Measure with Applications to Learning Optimal Auctions
Vasilis Syrgkanis

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #223
in Posters Tue »
We introduce a new sample complexity measure, which we refer to as split-sample growth rate. For any hypothesis $H$ and for any sample $S$ of size $m$, the split-sample growth rate $\hat{\tau}_H(m)$ counts how many different hypotheses can empirical risk minimization output on any sub-sample of $S$ of size $m/2$. We show that the expected generalization error is upper bounded by $O\left(\sqrt{\frac{\log(\hat{\tau}_H(2m))}{m}}\right)$. Our result is enabled by a strengthening of the Rademacher complexity analysis of the expected generalization error. We show that this sample complexity measure, greatly simplifies the analysis of the sample complexity of optimal auction design, for many auction classes studied in the literature. Their sample complexity can be derived solely by noticing that in these auction classes, ERM on any sample or sub-sample will pick parameters that are equal to one of the points in the sample.
Keywords: Learning Theory · Game Theory and Computational Economics
[ Paper] 

Author Information

Vasilis Syrgkanis (Microsoft Research)

More from the Same Authors