🤖 machine learning

On Regularization via Early Stopping for Least Squares Regression

This paper characterizes the dynamics of discrete full-batch gradient descent for linear regression to demonstrate that early stopping yields a solution equivalent to minimum-norm generalized ridge regression, thereby proving its generalization benefits across arbitrary data spectra and learning rate schedules while providing an estimate for the optimal stopping time.

Original authors: Rishi Sonthalia, Jackie Lok, Elizaveta Rebrova

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rishi Sonthalia, Jackie Lok, Elizaveta Rebrova

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a student (the machine learning model) to solve a math problem (predicting outcomes from data). You have a textbook with examples (the training data), and you want the student to learn the underlying rules so they can solve new problems they've never seen before (generalization).

The paper you provided is about a specific teaching strategy called Early Stopping. Usually, teachers let students study until they get every single practice problem perfect. But sometimes, if a student studies too long, they start memorizing the specific quirks of the practice book (like the font or the paper texture) rather than the actual math rules. This is called "overfitting," and it makes them fail on new tests.

Early Stopping is the strategy of saying, "Okay, stop studying now, before you start memorizing the noise."

Here is what the authors discovered, explained simply:

1. The "Invisible Hand" of Stopping Early

The authors wanted to know: What exactly happens to the student's brain when we stop them early?

They found that stopping early is mathematically identical to a specific type of "discipline" called Ridge Regression.

The Analogy: Imagine Ridge Regression is like giving the student a heavy backpack. The backpack forces them to keep their answers simple and close to zero (the starting point).
The Discovery: The paper proves that if you stop the student at the right moment, their brain state is exactly the same as if they had been wearing that heavy backpack the whole time. You don't need to physically add the backpack (the math penalty); you just need to stop the lesson at the perfect time, and the result is the same.

2. The "Volume Knob" for Different Frequencies

The authors looked at how the student learns different parts of the problem. They realized that the data isn't just one big block; it's made of many different "frequencies" or directions (some easy, some hard).

The Analogy: Think of the data as a symphony. Some instruments play loud, obvious notes (easy patterns), while others play quiet, complex notes (hard patterns).
The Discovery: When you use Gradient Descent (the standard way of teaching), the student learns the loud notes very fast. If you keep going, they start trying to learn the quiet notes, but in doing so, they start hearing "static" (noise) in the quiet notes and memorizing that static as if it were music.
The Result: Early stopping acts like a volume knob. It turns down the volume on the complex, quiet notes just enough so the student hears the music but ignores the static. The paper gives a formula to figure out exactly how long to keep the volume knob turned down.

3. The "Learning Rate" Matters

A crucial part of the paper is about Learning Rates. This is how fast the student takes a step when learning.

Constant Pace: If the student walks at a steady, slow pace, they learn the loud notes, then the quiet notes, and eventually start hearing static. Stopping them early works great here.
Fading Pace: If the student starts fast and then slows down too quickly (like exponential decay), they might stop learning the quiet notes before they even get to the static. In this case, stopping early doesn't help much because they were already slowing down on their own.
The Paper's Claim: The authors provide a rulebook. They say, "If your learning rate schedule looks like X, then stopping early is a superpower. If it looks like Y, stopping early is useless."

4. The "Magic Formula" for When to Stop

The most practical part of the paper is a formula they derived to tell you exactly when to stop.

The Inputs: You need to know three things:
1. How much "noise" is in your textbook (how messy the data is).
2. How strong the "signal" is (how clear the actual rules are).
3. How fast the student is walking (the learning rate).
The Output: The formula spits out a specific number of steps (iterations).
The Test: The authors tested this on real-world data (like handwritten digits and images). They found that their formula predicted the "sweet spot" almost perfectly. If they stopped at the time their formula suggested, the student performed better than if they had studied longer or shorter.

5. When NOT to Stop Early

The paper also warns that early stopping isn't always the answer.

The Analogy: If you are already wearing a very heavy backpack (a strong mathematical penalty called "Ridge Regularization"), you don't need to stop early. The backpack is already doing the work of keeping the student simple.
The Claim: If the "backpack" is too heavy, stopping early actually hurts performance. The student needs to keep going to finish the job. The authors prove mathematically that if the penalty is strong enough, you should just let the student study until they are done.

Summary

This paper is a "user manual" for the strategy of Early Stopping.

It explains why it works (it's the same as adding a mathematical penalty).
It explains when it works (depends on how fast you learn and how messy the data is).
It gives you a calculator to find the exact moment to stop, which they proved works on real data.

They didn't invent a new way to teach; they just figured out the precise physics of when to pull the plug to get the best results.

Technical Summary: Regularization via Early Stopping for Least Squares Regression

Problem Statement

The paper addresses the fundamental challenge of understanding the effects of early stopping on the parameters and generalization capabilities of machine learning models, specifically within the context of linear regression. While early stopping is a widely used regularization technique, its theoretical properties remain incompletely understood, particularly for discrete full-batch gradient descent with arbitrary learning rate schedules and data distributions.

Existing literature often relies on strong assumptions, such as continuous-time gradient flow dynamics or Gaussian assumptions on the feature matrix, to derive stopping rules. These approaches fail to quantify the optimal stopping time under practical, non-constant learning rate schedules or to explain phenomena like "grokking" (where models initially overfit before generalizing) in discrete settings. Furthermore, the precise relationship between early stopping and explicit $L_2$ (ridge) regularization, and the conditions under which early stopping is beneficial versus detrimental, require more rigorous characterization without restrictive distributional assumptions.

Methodology

The authors analyze the discrete dynamics of full-batch gradient descent for linear regression, avoiding the continuous-time gradient flow approximation. The core methodological contribution is the derivation of exact, closed-form expressions for the parameter trajectory $\beta_k$ after $k$ steps.

Key methodological components include:

Spectral Decomposition: The analysis is conducted in the eigenbasis of the sample covariance matrix $X^T X$ . The authors define a function $\phi(k; \zeta, \{\eta_i\})$ that captures the cumulative effect of a learning rate schedule $\{\eta_i\}$ on a specific eigenvalue $\zeta$ .
Exact Trajectory Formulation: Using this function, the authors derive an explicit formula for $\beta_k$ that holds for any data matrix $X$ , any learning rate schedule, and any initialization. This formula decomposes the error into a signal component (dependent on initialization and true parameters) and a noise component (dependent on residuals).
Risk Analysis: The expected excess risk is analyzed by taking expectations over the noise and, under a spherical prior assumption, over the signal. The authors differentiate the risk with respect to the iteration count (treating it as a continuous variable via Assumption 2) to identify critical points.
Equivalence Proofs: The paper establishes mathematical equivalences between early-stopped solutions and solutions to generalized ridge regression problems, allowing for a direct comparison of regularization effects.

Key Contributions

1. Exact Trajectories for Discrete Dynamics

The paper provides Proposition 1, which gives exact formulas for the discrete dynamics of $\beta_k$ for the kernel ridge regression problem. Unlike prior works, these formulas make no assumptions on the data distribution, the learning rate schedule, or the noise distribution. The authors provide closed-form expressions for $\phi$ under various common schedules, including constant, polynomial decay, constant additive decay, and exponential decay (using Gamma functions and $q$ -Pochhammer symbols).

2. Equivalence to Generalized Ridge Regression

The authors prove Theorem 5, demonstrating that for generic data and arbitrary learning rate schedules, the solution obtained after $T$ iterations of early stopping (with $\mu=0$ ) is equivalent to the minimum norm solution of a generalized ridge regression problem. The regularization matrix $D$ in this generalized problem is explicitly determined by the learning rate schedule and the stopping time.
Conversely, Theorem 6 shows that any minimum norm solution to a standard ridge regression problem can be obtained via early stopping if one can assign a distinct learning rate to each eigenspace of the sample covariance matrix.

3. Conditions for Benefit and Detriment

The paper establishes sufficient conditions for when early stopping improves generalization performance:

Theorem 8 (Beneficial): Early stopping is beneficial if the learning rate schedule allows the "shrinkage factor" $\phi(k)$ to decay sufficiently fast such that the limit of the ratio $\phi(k)/\phi(0)$ is less than a threshold determined by the signal-to-noise ratio. This holds for constant, linearly decaying, and other schedules where the cumulative step size diverges.
Theorem 9 (Not Beneficial): Early stopping is not beneficial if the learning rate decays too quickly (e.g., fast polynomial or exponential decay) such that the shrinkage factor does not reach the necessary threshold. In these cases, the risk continues to decrease with further training.
Theorem 10 (Ridge Regularization): These conditions are extended to the case where explicit ridge regularization ( $\mu > 0$ ) is present. A key finding is that if the explicit regularization parameter $\mu$ exceeds a critical value ( $\mu \ge \tau^2 / (n\sigma^2)$ ), early stopping provides no additional benefit.

4. Optimal Stopping Time Estimate

The authors propose an estimate for the optimal stopping time (Equation 31) based on the cumulative learning rate budget $\sum \eta_i$ . The estimate is derived by equating the shrinkage factor to the optimal balance between signal and noise for a representative eigenvalue. This estimate generalizes prior results from the gradient flow regime to discrete dynamics with arbitrary spectra and non-constant learning rates.

Results and Empirical Validation

The theoretical findings are validated through experiments on synthetic data and real-world datasets (MNIST and CIFAR10).

Accuracy of Estimate: The proposed stopping time estimate (Equation 31) closely matches the empirically observed optimal stopping times across various learning rate schedules (constant, polynomial, linear, exponential, cosine annealing, and random).
Regime Dependence: The experiments confirm the theoretical prediction that early stopping is beneficial when the explicit ridge parameter $\mu$ is below the optimal ridge parameter $\mu^*$ , but becomes detrimental (or unnecessary) when $\mu \ge \mu^*$ .
Schedule Sensitivity: The results demonstrate that the iteration at which the optimum occurs varies significantly depending on the learning rate schedule, but the cumulative budget of the learning rates serves as a robust predictor for the optimal stopping point.
Grokking: The analysis suggests that for many common learning rate schedules (where the cumulative step size diverges), linear models do not exhibit "grokking" (late generalization after overfitting); instead, they exhibit the classic bias-variance tradeoff where early stopping is optimal.

Significance and Claims

The paper claims to provide a non-asymptotic, distribution-free characterization of early stopping in linear regression. Its significance lies in:

Bridging Theory and Practice: By moving away from continuous-time gradient flow and Gaussian assumptions, the results apply to practical, discrete training scenarios with arbitrary learning rate schedules.
Unifying Perspective: It formally unifies early stopping with generalized ridge regularization, showing that the "implicit" regularization of early stopping is mathematically equivalent to an explicit, data-dependent $L_2$ penalty.
Practical Guidance: It offers a concrete, theoretically grounded estimate for the optimal stopping time that depends only on observable quantities (signal-to-noise ratio, eigenvalue spectrum, and learning rate schedule), rather than requiring knowledge of the true underlying signal.
Clarifying Limitations: The work explicitly delineates when early stopping is beneficial versus when it is not, particularly highlighting the interaction between explicit ridge regularization and early stopping, and identifying specific learning rate schedules that render early stopping ineffective.

The authors conclude that while the current analysis is limited to linear models, the framework provides a foundation for understanding more complex models, such as two-layer neural networks, and suggests future directions for extending these results to stochastic gradient descent and adaptive optimization methods.