Abstract

 In stochastic convex optimization the goal is to minimize a convex function . over a convex set where D is some unknown distribution and each f (·) in the support of D is convex over K. The optimization is commonly based on i.i.d. samples  from D. A standard approach to P such problems is empirical risk minimization (ERM) that optimizes . . Here we consider the question of how many samples are necessary for ERM to succeed and the closely related question of uniform convergence of FS to F over K. We demonstrate that in the standard setting of Lipschitz-bounded functions over a K of bounded radius, ERM requires sample size that scales linearly with the dimension d. This nearly matches standard upper bounds and improves on (log d) dependence proved for setting in [18]. In stark contrast, these problems can be solved using dimension-independent number of samples for setting and log d dependence for setting using other approaches. We further show that our lower bound applies even if the functions in the support of D are smooth and efficiently computable and even if an regularization term is added. Finally, we demonstrate that for a more general class of bounded-range (but not Lipschitz-bounded) stochastic convex programs an infinite gap appears already in dimension 2.