Title: A Sample Complexity Measure with Applications to Learning Optimal Auctions,
Abstract: 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.