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

Abstract

In stochastic convex optimization the goal is to minimize a convex function $F(x)\doteq {\mathbf{E}}_{\mathbf{f}\sim D}[\mathbf{f}(x)]$ over a convex set $\mathcal{K}\subset {\mathbb{R}}^d$ where $D$ is some unknown distribution and each $f(\cdot )$ in the support of $D$ is convex over $\mathcal{K}$. The optimization is commonly based on i.i.d.~samples $f^1,f^2,\dots ,f^n$ from $D$. A standard approach to such problems is empirical risk minimization (ERM) that optimizes $F_S(x)\doteq \frac{1}{n}{\sum }_{i\le n}{f}^i(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 $F_S$ to $F$ over $\mathcal{K}$. We demonstrate that in the standard ${\ell }_p/{\ell }_q$ setting of Lipschitz-bounded functions over a $\mathcal{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 ${\ell }_2/{\ell }_2$ setting by Shalev-Shwartz et al. (2009). In stark contrast, these problems can be solved using dimension-independent number of samples for ${\ell }_2/{\ell }_2$ setting and $\log d$ dependence for ${\ell }_1/{\ell }_{\infty }$ 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 ${\ell }_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.

arXiv commentAdded illustrations of functions used in some of the constructions

References in corpus (5)

• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions
• Preserving Statistical Validity in Adaptive Data Analysis
• Sequential Probability Assignment with Binary Alphabets and Large Classes of Experts

Cited by in corpus (13)

• Private Stochastic Convex Optimization with Optimal Rates
• High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
• Reasoning About Generalization via Conditional Mutual Information
• SGD Generalizes Better Than GD (And Regularization Doesn't Help)
• Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps
• Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions
• A Simple Analysis for Exp-concave Empirical Minimization with Arbitrary Convex Regularizer
• Better scalability under potentially heavy-tailed gradients
• Improved scalability under heavy tails, without strong convexity
• Characterization of Excess Risk for Locally Strongly Convex Population Risk
• Algorithmic Instabilities of Accelerated Gradient Descent
• A Tight Lower Bound for Uniformly Stable Algorithms