THE SAMPLE COMPLEXITY OF ERM IN EUCLIDEAN STOCHASTIC CONVEX OPTIMIZATION

Stochastic convex optimization is a model for optimization in a stochastic environment that is also motivated by the theory of machine learning. Empirical risk minimization (ERM) is a fundamental algorithmic principle. We study the sample complexity of ERM in stochastic convex optimization in the standard Euclidean setup in d-dimensional space with accuracy parameter $\epsilon > 0$. A folklore example shows that the sample complexity is at least $\Omega(\frac{1}{\epsilon^2})$. Shalev-Shwartz, Shamir, Srebro and Sridharan proved that the complexity is at least $\Omega(\log(d))$ for $\epsilon = \frac{1}{2}$.Later on, Feldman proved that it is at least $\Omega(\frac{d}{\epsilon})$. Proving asymptotically stronger lower bounds was left as an open problem. We prove that, in fact, the sample complexity is at most $\tilde{O}(\frac{d}{\epsilon}+\frac{1}{\epsilon^2})$. The proof builds a mechanism for controlling stochastic convexoptimization problems.