Research map / Optimization / Nonconvex and smooth optimization
The Sample Complexity of Gradient Descent in Stochastic Convex Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that full-batch gradient descent in non-smooth stochastic convex optimization can overfit with sample complexity linear in dimension, matching worst-case ERM rates up to logs, via a sample-dependent oracle reduction and a Feldman-style construction.
Problem
Sample complexity of full-batch vanilla gradient descent (with common hyperparameters) in non-smooth stochastic convex optimization, where prior bounds left a gap between square-root and linear dimension dependence.
Approach
Builds a lower-bound construction where GD's trajectory encodes the sample, using a Feldman-style set of hypercube vectors and a Nemirovski-type subgradient oracle that drives GD to overfit; a reduction then converts the sample-dependent oracle into a fixed convex function via convex interpolation, so the bound holds for any first-order oracle.
Key results
- Shows GD with common hyperparameters can have generalization error Omega~(d/m + 1/sqrt(m)), matching worst-case ERM sample complexity up to log factors.
- For d >= Omega(max{m, T^{1/3}}), GD's generalization gap is Omega(min{eta*sqrt(T) + 1/(eta T), 1}) for O(1)-Lipschitz convex functions.
- Resolves an open problem: linear dimension dependence is necessary for GD, improving the prior square-root-of-dimension lower bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Gradient Descent with common hyperparameter choices | Gradient Descent in SCO · SCO generalization error | generalization error: \tilde \Theta(d/m+1/\sqrt{m}) | Hurt |
| Use Gradient Descent with \eta=\Theta(1/\sqrt{T}) and T\le m^{1.5} | Gradient Descent in SCO · SCO, T\le m^{1.5} | population excess loss: \lbound{\frac{d}{m}+\frac{1}{\sqrt{m}}} | Hurt |
| Run GD for T iterations under d=\Omega(\max\{m,\frac{1}{4} T^{1/3}\}) | Gradient Descent in SCO · SCO, d=\Omega(\max\{m,\frac{1}{4} T^{1/3}\}) | population excess loss: \Omega\left( \min\left\{\eta \sqrt{T}+ \frac{1}{\eta T},1\right\}\right) | Hurt |
| Tune hyperparameters to achieve minimal empirical risk at the optimal rate | Gradient Descent in SCO · SCO generalization | sample complexity | No clear effect |
Surprising findings
- GD, with standard step size eta=O(1/sqrt(T)), does not outperform worst-case ERMs in generalization when T=O(m).
Limitations
- Lower bound holds for specific constructed distributions and functions, not for all convex problems.
- Gap remains between lower bound and upper bounds in regimes such as T=Omega(m^2) and low-dimensional stability.
- Requires T at most cubic in dimension for the strongest form of the bound.
Experimental setup
Metrics: generalization error (population excess risk)
Baselines: worst-case empirical risk minimizers SGD stable-GD
Builds on: Feldman's construction for ERM lower bounds Nemirovski function Attias et al. stability-based GD bounds
Closest papers by meaning
- Never Go Full Batch (in Stochastic Convex Optimization) (NeurIPS 2021 · similarity 0.94)
- Sample complexity of stochastic optimization with integer variables (NeurIPS 2026 · similarity 0.91)
- High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.90)
- New Sample Complexity Bounds for Sample Average Approximation in Heavy-Tailed Stochastic Programming (ICML 2024 · similarity 0.90)
- Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization (ICML 2025 · similarity 0.89)
- Information Complexity of Stochastic Convex Optimization: Applications to Generalization, Memorization, and Tracing (ICML 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.