Abstract
This paper introduces a theoretical framework to predict the test loss of Stochastic Gradient Descent (SGD) by incorporating the covariance structure of data. By modeling features as Gaussian, the authors accurately forecast learning curves for neural networks on datasets like MNIST and CIFAR-10. The results highlight that for structured data, small batch sizes are often computationally optimal, bridging the gap between abstract theory and practical performance.
Introduction
While SGD is the workhorse of modern machine learning, theoretical understanding of its average-case performance on specific datasets has been limited. Existing theories often rely on data-agnostic bounds or assume isotropic data. However, real-world data like images possess rich, low-dimensional structures. This paper addresses how the geometry of a dataset interacts with SGD hyperparameters to determine test error.
Methods
The authors analyze a linear model $f(x) = w \cdot \psi(x)$ under Mean Squared Error (MSE) loss, a setup that describes wide neural networks in the "kernel regime." Key methodological contributions include:
- Recursive Solutions: A recursion relation for the weight error matrix to track expected test loss.
- Gaussian Approximation: A proof that test loss dynamics are primarily driven by the eigenvalues of the feature covariance matrix.
- Compute Budget Analysis: A framework using $C = tm$ to compare efficiency across batch sizes.
Key Insights
Gaussian Universality
A central finding is "Gaussian Universality": despite the non-Gaussian nature of image features, Gaussian-based theory predicts learning curves with high accuracy. This indicates that the spectral properties of the data are the primary drivers of SGD dynamics.
The Small Batch Advantage
For a fixed compute budget, smaller batch sizes are often superior. While larger batches offer cleaner gradients, the increased number of steps possible with smaller batches leads to faster error reduction on structured data.
Key Results
- Predictive Accuracy: Theoretical curves overlap almost perfectly with simulations on MNIST and CIFAR-10.
- Optimal Batch Size: For structured data, $m=1$ is often optimal per unit of computation, provided the learning rate is tuned.
- Stability Limits: The paper identifies limits where small batch sizes or high learning rates cause loss divergence.
Conclusion
The theory provides a powerful tool for understanding SGD on structured data within the "lazy training" regime. Future work will aim to extend these insights to feature learning regimes, Cross-Entropy loss, and advanced optimizers like Adam.
Summary updated