Abstract:
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 . A folklore example shows that the sample complexity is at least . Shalev-Shwartz, Shamir, Srebro and Sridharan proved that the complexity is at least for .Later on, Feldman proved that it is at least . Proving asymptotically stronger lower bounds was left as an open problem. We prove that, in fact, the sample complexity is at most . The proof builds a mechanism for controlling stochastic convexoptimization problems.
Chat is not available.