# The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimization

arXiv: https://arxiv.org/abs/2401.12058 · HTML: https://mlsanity.com/paper/2401.12058/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 24 references that are in the map.
- First posted on arXiv 22 Jan 2024.

## Builds on (most cited first, 8 of 8)

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back](https://mlsanity.com/paper/1608.04414/) (2016)
- [SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochs](https://mlsanity.com/paper/2107.05074/) (2021)
- [Benign Underfitting of Stochastic Gradient Descent](https://mlsanity.com/paper/2202.13361/) (2022)
- [Never Go Full Batch (in Stochastic Convex Optimization)](https://mlsanity.com/paper/2107.00469/) (2021)
- [The Sample Complexity Of ERMs In Stochastic Convex Optimization](https://mlsanity.com/paper/2311.05398/) (2023)
- [Initialization-Dependent Sample Complexity of Linear Predictors and Neural Networks](https://mlsanity.com/paper/2305.16475/) (2023)

## Built on by (most cited first, 6 of 6)

- [The Sample Complexity of Gradient Descent in Stochastic Convex Optimization](https://mlsanity.com/paper/2404.04931/) (2024)
- [Flat Minima and Generalization: Insights from Stochastic Convex Optimization](https://mlsanity.com/paper/2511.03548/) (2025)
- [Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimization](https://mlsanity.com/paper/2505.08306/) (2025)
- [Complexity of Vector-valued Prediction: From Linear Models to Stochastic Convex Optimization](https://mlsanity.com/paper/2412.04274/) (2024)
- [All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimension](https://mlsanity.com/paper/2602.08350/) (2026)
- [The Fourth Quadrant: A Stylized View of Benign Misfitting](https://mlsanity.com/paper/2608.01032/) (2026)

## Abstract (arXiv)

We study the generalization performance of gradient methods in the fundamental stochastic convex optimization setting, focusing on its dimension dependence. First, for full-batch gradient descent (GD) we give a construction of a learning problem in dimension d=O(n2), where the canonical version of GD (tuned for optimal performance of the empirical risk) trained with n training examples converges, with constant probability, to an approximate empirical risk minimizer with Omega(1) population excess risk. Our bound translates to a lower bound of Omega (√d) on the number of training examples required for standard GD to reach a non-trivial test error, answering an open question raised by Feldman (2016) and Amir, Koren, and Livni (2021b) and showing that a non-trivial dimension dependence is unavoidable. Furthermore, for standard one-pass stochastic gradient descent (SGD), we show that an application of the same construction technique provides a similar Omega(√d) lower bound for the sample complexity of SGD to reach a non-trivial empirical error, despite achieving optimal test performance. This again provides an exponential improvement in the dimension dependence compared to previous work (Koren, Livni, Mansour, and Sherman, 2022), resolving an open question left therein.