# Learning Curves for SGD on Structured Features

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 55 references that are in the map.
- First posted on arXiv 4 Jun 2021.

## Builds on (most cited first, 30 of 33)

- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [Explaining Neural Scaling Laws](https://mlsanity.com/paper/2102.06701/) (2021)
- [The Intrinsic Dimension of Images and Its Impact on Learning](https://mlsanity.com/paper/2104.08894/) (2021)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks](https://mlsanity.com/paper/2002.02561/) (2020)
- [Measuring the Effects of Data Parallelism on Neural Network Training](https://mlsanity.com/paper/1811.03600/) (2018)
- [Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networks](https://mlsanity.com/paper/2006.13198/) (2020)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020)
- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [Neural Tangents: Fast and Easy Infinite Neural Networks in Python](https://mlsanity.com/paper/1912.02803/) (2019)
- [The Heavy-Tail Phenomenon in SGD](https://mlsanity.com/paper/2006.04740/) (2020)
- [Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model](https://mlsanity.com/paper/1907.04164/) (2019)
- [Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm](https://mlsanity.com/paper/1702.07254/) (2017)
- [The Gaussian equivalence of generative models for learning with shallow neural networks](https://mlsanity.com/paper/2006.14709/) (2020)
- [Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setup](https://mlsanity.com/paper/1906.08632/) (2019)
- [Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime](https://mlsanity.com/paper/2004.12019/) (2020)
- [Benign Overfitting of Constant-Stepsize SGD for Linear Regression](https://mlsanity.com/paper/2103.12692/) (2021)
- [Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes](https://mlsanity.com/paper/1805.10074/) (2018)
- [Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression](https://mlsanity.com/paper/1602.05419/) (2016)
- [Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classification](https://mlsanity.com/paper/2006.06098/) (2020)
- [Kernel Alignment Risk Estimator: Risk Prediction from Training Data](https://mlsanity.com/paper/2006.09796/) (2020)
- [Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures](https://mlsanity.com/paper/2104.13628/) (2021)
- [An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias](https://mlsanity.com/paper/2006.07904/) (2020)
- [Last iterate convergence of SGD for Least-Squares in the Interpolation regime](https://mlsanity.com/paper/2102.03183/) (2021)
- [Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model](https://mlsanity.com/paper/2006.08212/) (2020)
- [Asymptotic Optimality in Stochastic Optimization](https://mlsanity.com/paper/1612.05612/) (2016)
- [Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT](https://mlsanity.com/paper/1904.02130/) (2019)
- [From Averaging to Acceleration, There is Only a Step-size](https://mlsanity.com/paper/1504.01577/) (2015)

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

- [Homogenization of ℓ2-Adversarial Training in High-Dimensions: Exact Dynamics under Stochastic Gradient Descent](https://mlsanity.com/paper/2607.00207/) (2026)

## Abstract (arXiv)

The generalization performance of a machine learning algorithm such as a neural network depends in a non-trivial way on the structure of the data distribution. To analyze the influence of data structure on test loss dynamics, we study an exactly solveable model of stochastic gradient descent (SGD) on mean square loss which predicts test loss when training on features with arbitrary covariance structure. We solve the theory exactly for both Gaussian features and arbitrary features and we show that the simpler Gaussian model accurately predicts test loss of nonlinear random-feature models and deep neural networks trained with SGD on real datasets such as MNIST and CIFAR-10. We show that the optimal batch size at a fixed compute budget is typically small and depends on the feature correlation structure, demonstrating the computational benefits of SGD with small batch sizes. Lastly, we extend our theory to the more usual setting of stochastic gradient descent on a fixed subsampled training set, showing that both training and test error can be accurately predicted in our framework on real data.