The Sample Complexity Of ERMs In Stochastic Convex Optimization
Daniel Carmon Roi Livni Amir Yehudayoff
Stochastic convex optimization is one of the most well-studied models for
learning in modern machine learning. Nevertheless, a central fundamental
question in this setup remained unresolved: "How many data points must be
observed so that any empirical risk minimizer (ERM) shows good performance on
the true population?" This question was proposed by Feldman (2016), who proved
that $\Omega(\frac{d}{\epsilon}+\frac{1}{\epsilon^2})$ data points are
necessary (where $d$ is the dimension and $\epsilon>0$ is the accuracy
parameter). Proving an $\omega(\frac{d}{\epsilon}+\frac{1}{\epsilon^2})$ lower
bound was left as an open problem. In this work we show that in fact
$\tilde{O}(\frac{d}{\epsilon}+\frac{1}{\epsilon^2})$ data points are also
sufficient. This settles the question and yields a new separation between ERMs
and uniform convergence. This sample complexity holds for the classical setup
of learning bounded convex Lipschitz functions over the Euclidean unit ball. We
further generalize the result and show that a similar upper bound holds for all
symmetric convex bodies. The general bound is composed of two terms: (i) a term
of the form $\tilde{O}(\frac{d}{\epsilon})$ with an inverse-linear dependence
on the accuracy parameter, and (ii) a term that depends on the statistical
complexity of the class of $\textit{linear}$ functions (captured by the
Rademacher complexity). The proof builds a mechanism for controlling the
behavior of stochastic convex optimization problems.