2016/08/15 by Feldman, Vitaly · 2 citations
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · doi:10.48550/arxiv.1608.04414
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 ⊂ \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,…,fn from D. A standard approach to such problems is empirical risk minimization (ERM) that optimizes FS(x) \doteq (1)/(n)∑i≤ 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 Ω(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.