Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back *
In stochastic convex optimization the goal is to minimize a convex function
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 f 1 , f 2 , . . . , f n from D. A standard approach to 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 F S to F over K. We demonstrate that in the standard p / q 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 2 / 2 setting in [18]. 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.
The paper considers the the question of when empirical risk minimization suffices to to actually find a true risk minimizer, a question which is fundamental to many statistical tasks. Rigorously, the setup is as follows: we wish to minimize E[f] where f is drawn from some distribution D, assuming the f's are "nice" in some sense (here they consider various settings, including convex, Lipschitz, etc). We get samples from f_1, ..., f_n from this distribution, and can form the empirical risk, which is the average of the sample f's. The question is whether or not minimizing this empirical risk will always get us a minimizer for the ground truth, or something close.  In this work the authors provide strong lower bounds for this problem, in a variety of settings. Their most basic result is that for convex, Lipschitz functions over the unit l2 ball, to ensure that the ERM is O(1) close to the true minimizer requires Omega(d) samples, where di is the dimension. This is a tight lower bound in terms of the dimension. To the best of my knowledge, the previous best lower bounds were surprisingly weak--only Omega (log d). They can also modify their construction to show that a similar lower bound also holds other lp norms, for smooth, convex, Lipschitz functions, and for l1 regularization. Finally, a further modification shows that ERM never works for range constrained stochastic convex optimization (without a Lipschitz constraint), although other techniques work for this setting.
I like this result quite a bit. In my opinion, the question they consider is quite important. The lower bounds seem to give the right tradeoffs for different lp norms (at least, in terms of dependence on d). The reductions are well presented and clear, and I don't see any issue with them.   The main drawback of their approach I see is that it does not easily generalize to also obtain tight bounds in terms of eps, the desired error. Moreover, often times (as they point out) algorithms can bypass the ERM entirely and get better sample complexities, so perhaps ERM is simply not the right quantity to study. However, since it is so pervasive in practice, I feel like ultimately understanding generalization of ERM is an important question and the authors make an important contribution to it, and for that reason I think it is worthy of inclusion in NIPS.