Introduction
A persistent gap in machine learning theory is the disconnect between idealized models and real-world data. Most theoretical analyses of learning algorithms make a difficult trade-off: they are either "data-agnostic," providing broad bounds that are often too loose to be practically useful, or they assume the data is "unstructured" (e.g., isotropic white noise). However, real-world datasets like MNIST or CIFAR-10 are highly structured, often residing on low-dimensional manifolds.
This paper bridges that gap by providing an exactly solvable theoretical framework to predict the "learning curves"—how test error drops over time—for Stochastic Gradient Descent (SGD). By accounting for the actual covariance structure of the data, the authors demonstrate how real-world datasets lead to power-law error decays rather than the exponential rates predicted by simpler models. Furthermore, this framework provides a rigorous mathematical explanation for why small batch sizes are often the most computationally efficient choice.
Theoretical Framework and Methods
The authors analyze a linear model $f(x) = w \cdot \psi(x)$ trained with Mean Squared Error (MSE) loss. While seemingly simple, this formulation covers a wide range of powerful models, including Random Feature Models and Wide Neural Networks operating in the Neural Tangent Kernel (NTK) regime.
Key technical contributions of this framework include:
- Exact Recursion Relations: The authors derive a formula for the "error matrix," tracking how the discrepancy between the model weights and the ideal weights evolves at every step of SGD.
- Moment Analysis: They prove that test loss dynamics are primarily governed by the second and fourth moments of the feature distribution.
- Gaussian Approximation: Remarkably, even for non-Gaussian real data, a "Gaussian equivalent" model (relying only on the second-order covariance) provides highly accurate predictions for test loss.
- NTK Integration: By utilizing the NTK, the theory extends to deep learning, treating wide neural networks as linear models in a high-dimensional feature space.
Key Insights
Structure Dictates the Curve
On "unstructured" isotropic data, test error drops exponentially ($e^{-t/N}$), implying that a massive number of steps is required to learn effectively. However, on "structured" data like images, the error follows a power law ($t^{-\beta}$).
This power-law behavior explains the diminishing returns commonly observed in deep learning training, where models continue to make slow but steady progress over long periods. The authors derive a closed-form expression for the power-law exponent $eta$ based on the decay of the data's eigenvalues, showing that deeper networks exhibit slower eigenvalue decay and, consequently, faster learning rates.
The "Mode Coupling" Effect
In standard full-batch Gradient Descent, different "modes" (features) are learned independently. In SGD, however, the noise introduced by sampling minibatches "couples" these modes. The mathematical framework captures how the learning of one feature can interfere with or assist the learning of another due to this noise.
The Case for Small Batches
A central debate in machine learning practice is the selection of batch size. The authors analyze this under a fixed compute budget (Total Samples = Batch Size $m$ $\times$ Steps $t$).
They find that for structured data, the optimal batch size is typically very small—often $m=1$. Taking many noisy steps proves more computationally efficient than taking fewer, highly accurate steps. The "noise" of small batches helps the model navigate the complex feature covariance more quickly per unit of compute.
Validation and Results
The theoretical predictions were rigorously validated against synthetic data (isotropic and power-law features) as well as real-world datasets (MNIST and CIFAR-10) using Random ReLU features to simulate nonlinear embeddings. The theoretical curves overlap almost perfectly with actual SGD simulations, confirming the universality of the Gaussian theory: knowing just the covariance (the second moment) is often sufficient to predict the entire training trajectory of a deep network.
Additionally, the paper provides a precise "stability condition." It proves that if the batch size is too small or the learning rate is too high relative to the sum of squares of the data's eigenvalues, the training will diverge.
Limitations and Future Work
While powerful, the framework has limitations. It relies on the "lazy training" (NTK) regime and does not fully account for active "feature learning," where a network's internal representations change significantly. Furthermore, the current derivation is specific to MSE loss and standard SGD, omitting cross-entropy loss and modern optimizers like Adam or techniques like momentum.
Future work could extend this framework to classification-specific losses or use it to study "curriculum learning," exploring how dynamically changing the data distribution during training might optimize the learning curve.
Summary updated