Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back

In stochastic convex optimization the goal is to minimize a convex function F(x) doteq mathbf E_mathbf f~ D[mathbf f(x)] over a convex set cal K subset mathbb Rd where D is some unknown distribution and each f(·) in the support of D is convex over cal K. The optimization is commonly based on i.i.d.~samples f1,f2,ldots,fn from D. A standard approach to such problems is empirical risk minimization (ERM) that optimizes FS(x) doteq frac1nsumi≤ n fi(x). 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 cal K. We demonstrate that in the standard ℓp/ℓq setting of Lipschitz-bounded functions over a cal K of bounded radius, ERM requires sample size that scales linearly with the dimension d. This nearly matches standard upper bounds and improves on Omega(log d) dependence proved for ℓ2/ℓ2 setting by Shalev-Shwartz et al. (2009). In stark contrast, these problems can be solved using dimension-independent number of samples for ℓ2/ℓ2 setting and log d dependence for ℓ1/ℓ_∞ 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 ℓ1 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.