🤖 machine learning

A Data-dependent Early Stopping Rule using Rademacher Complexity with L1-norm

This paper proposes an analytic framework based on Rademacher complexity with an L1-norm to estimate the optimal early stopping time for linear regression models without requiring training or probabilistic assumptions, demonstrating its applicability to nonlinear neural networks through linear probing.

Original authors: Duy Hoang, Bastien Berret, Olivier Bruneau, Laurent Fribourg

Published 2026-08-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Duy Hoang, Bastien Berret, Olivier Bruneau, Laurent Fribourg

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

Training a computer to recognize patterns, whether it is identifying a cat in a photograph or predicting a stock price, involves a delicate balancing act. The machine learns by looking at examples, adjusting its internal settings to fit the data it has seen. However, if it learns too perfectly, it begins to memorize the specific quirks of those examples rather than understanding the underlying rules. This is a bit like a student who memorizes the answers to a practice test but fails the real exam because they cannot apply the logic to new questions. In the world of artificial intelligence, this failure to generalize is a major hurdle. To prevent it, researchers often use a strategy called "early stopping," where they halt the learning process at just the right moment—after the model has learned the rules but before it starts memorizing the noise. The challenge has always been knowing exactly when that moment arrives. Traditionally, finding this sweet spot requires running the training process multiple times on separate sets of data, a method that is slow, computationally expensive, and often relies on guessing.

A team of researchers at Université Paris-Saclay has proposed a new way to solve this timing problem without the need for repeated trials. Instead of guessing or running extra simulations, they developed a mathematical method that can predict the ideal stopping point directly from the data itself. Their approach relies on a concept known as Rademacher complexity, which essentially measures how well a model can distinguish between real patterns and random noise. By using this measure, the researchers created a rule that tells a computer exactly when to stop learning. What makes their work distinct is that it does not require assumptions about the shape or distribution of the data, a common requirement in previous methods. Furthermore, they found that using a specific way of measuring error, known as the L1-norm, provided significantly more accurate predictions than the standard methods used in the field.

The researchers focused their initial work on linear models, which are the simplest type of machine learning algorithms, but they demonstrated that their findings could be extended to complex, non-linear neural networks. To test their theory, they applied their method to a classic problem: distinguishing between handwritten digits. In one experiment, they trained a neural network to tell the difference between the numbers three and five from a dataset of over ten thousand images. Using their new rule, the system calculated a stopping time of 342 steps. When they compared this to the actual best stopping time found by running the full training process and checking a separate test set, the real optimum was 357 steps. The difference was negligible, and the performance of the model stopped at the predicted time was nearly identical to the performance of the model stopped at the true optimum. In another test involving the numbers zero and one, the predicted stopping time was 415 steps, while the actual optimum was 418 steps. In both cases, the model trained using their rule avoided the trap of overfitting and achieved the best possible accuracy for unseen data.

The study also revealed that the method works best when there is a large amount of data relative to the complexity of the model. When the researchers tested scenarios with fewer data points, the method became less precise, sometimes suggesting a stopping time of zero, which indicates the model should not be trained at all. This aligns with the understanding that complex models need sufficient data to learn general rules. The researchers also compared their new method against older techniques that rely on different mathematical assumptions about the data. They found that their approach, which uses the L1-norm for calculation, consistently produced stopping times much closer to the true optimum than the older methods. This suggests that the way error is measured is just as important as the stopping rule itself.

Perhaps most importantly, the researchers showed that stopping early is not just a theoretical concept but a practical necessity in many cases. They calculated what would happen if the training were allowed to continue indefinitely. In the examples they studied, the model's performance on new data actually got worse if training continued past the optimal point, confirming that early stopping prevents the model from degrading. However, they also noted that in some specific, highly complex scenarios where the model has far more parameters than data points, continuing to train might eventually lead to better results, a phenomenon known as "benign overfitting." Their method helps identify which situation a user is in, allowing them to decide whether to stop early or keep going.

By providing a way to calculate the optimal stopping time without running the full training process, this work offers a more efficient path for developing reliable artificial intelligence. It removes the need for trial and error, saving time and computational resources. The method is particularly useful for situations where data is abundant but computing power is limited, or where the cost of training is high. While the current study focuses on linear models and specific types of data, the researchers believe their framework can be adapted for more complex systems and different types of outputs. Their work provides a clear, data-driven answer to a question that has long required guesswork, offering a more precise tool for navigating the trade-off between learning and memorizing.

Technical Summary: A Data-dependent Early Stopping Rule using Rademacher Complexity with L1-norm

Problem Statement
Training neural networks requires balancing the trade-off between fitting training data and achieving robust performance on unseen inputs, a property known as generalizability. This is determined by the gap between the empirical risk ( $L_S$ ) and the expected population risk ( $L_D$ ). The generalization loss ( $L_G$ ) is defined as the difference between these two. During gradient descent (GD), $L_S$ typically decreases while $L_G$ increases, creating a "bias-variance" trade-off. The goal of early stopping is to halt training at an optimal time $t^*$ that minimizes the sum $L_S + L_G$ .

Classically, $t^*$ is estimated numerically by monitoring a separate test set ( $S_{test}$ ). Alternatively, analytical approaches using Random Matrix Theory (RMT) exist, but they often rely on strong probabilistic assumptions, such as Gaussian data distributions or specific eigenvalue distributions (e.g., Marchenko–Pastur) of the data covariance matrix. This paper addresses the need for an analytical early stopping rule that does not require separate test sets or restrictive distributional assumptions.

Methodology
The authors propose an analytic framework based on Rademacher Complexity (RC) to estimate the optimal stopping time without performing gradient descent. The methodology focuses on linear models and linear regression, with extensions to nonlinear networks via "linear probing."

L1-Norm Formulation: Unlike many existing RC bounds that utilize the L2-norm, this work expresses Rademacher complexity using the L1-norm. This choice is motivated by the desire to eliminate a data-dependent constant $M$ (a bound on the loss) from the generalization error bound. By setting $p=1$ in the general $L_p$ -norm bound, the authors derive an upper bound on the population loss ( $L_D$ ) that depends only on the empirical error vector and the model norm, avoiding the explicit dependence on $M$ .
Gradient Flow Dynamics: The problem is modeled in continuous time using Gradient Flow (GF). The authors analyze the dynamics of the training error vector $v(t)$ and the model parameters $a(t)$ . The population loss upper bound, denoted $L^*_D(t)$ , is shown to be "U-shaped," initially decreasing as the empirical loss drops and later increasing as the model norm grows.
Analytic Stopping Criterion ( $t^+$ ): The core contribution is the derivation of a data-dependent criterion $C(s)$ $C (s)$ that ensures $L^*_D(t)$ $L_{D}^{*} (t)$ is decreasing for all $t \leq s$ $t \leq s$ .
- The authors decompose the data covariance matrix eigenvalues into "informative" (large) and "nuisance" (small) sets.
- They define a function $\Phi(t)$ involving these eigenvalues and the error dynamics.
- The stopping time $t^+$ is defined as the supremum of time $s$ such that $\Phi(t) > 0$ for all $t \in [0, s)$ .
- Mathematically, $t^+$ is the first time $\Phi(t)$ crosses zero. It is proven that $t^+$ is a lower bound estimate of the true optimal time $t^*$ (i.e., $t^+ \leq t^*$ ). Under specific conditions (e.g., when the true minimum lies within the first sign-invariant interval), $t^+ = t^*$ .
Approximation: The paper provides a simple approximation $t^+_{approx} \approx \frac{1}{\lambda_1} \ln \frac{\Gamma(0)}{\Omega(0)}$ , which resembles a signal-to-noise ratio (SNR) formulation found in RMT literature but derived here without probabilistic assumptions.

Key Contributions

Distribution-Free Analytical Estimation: The paper introduces a method to estimate the optimal early stopping time analytically without assuming Gaussian data or specific eigenvalue distributions.
L1-Norm Advantage: The authors demonstrate theoretically and numerically that using the L1-norm for Rademacher complexity yields a stopping time estimate ( $t^+$ ) significantly closer to the numerical optimum ( $t_{test}$ ) than the L2-norm approach.
Underparameterized Focus: The method is specifically designed for the underparameterized regime ( $m \leq n$ ), where "benign overfitting" and "epoch-wise double descent" are less prevalent, making early stopping a beneficial strategy.
Linear Probing Application: While the theory is derived for linear models, the authors successfully apply the results to nonlinear neural networks (specifically on MNIST classification) by freezing hidden layers and training only the output layer (linear probing).

Results
The authors validate their method through several examples:

Synthetic Gaussian Data: In binary classification tasks with varying sample sizes ( $n=512$ and $n=16384$ ), the analytic estimate $t^+$ exactly matched the true optimal time $t^*$ in the first case and provided a tight lower bound in the second. The L1-based estimate was consistently closer to the test-set optimum than the L2-based estimate.
MNIST Classification (3-5 and 0-1): Using a 4-layer ReLU network with linear probing, the method accurately predicted the stopping time. For the 3-5 classification, $t^+ = 342$ compared to the numerical optimum $t^* = 357$ and test-set optimum $t_{test} = 356$ . For 0-1 classification, $t^+ = 415$ matched $t^* = 415$ and was close to $t_{test} = 418$ .
Beneficial Stopping: In all tested cases, the loss at the estimated stopping time was lower than the loss at infinite training time ( $L^*_D(t^+) < L^*_D(\infty)$ ), confirming that early stopping is beneficial and avoiding the "benign overfitting" regime.
Robustness: The method performed well across different data distributions (Gaussian, Uniform, Pareto), with performance improving as the ratio of samples to parameters ( $n/m$ ) increased.

Significance and Claims
The paper claims that its primary significance lies in providing a data-dependent, analytic early stopping rule that operates without the need for a separate validation set or restrictive probabilistic assumptions about the data distribution. By leveraging Rademacher complexity with the L1-norm, the authors offer a practical tool for determining when to stop training linear models (and, via linear probing, certain nonlinear networks) to minimize generalization error. The authors modestly note that while the method works well for underparameterized models, it is not intended for the overparameterized regime where "benign overfitting" occurs. They also identify future work directions, including direct application to fully nonlinear models, vectorial outputs, and handling random noise in input data.

Technical Summary: A Data-dependent Early Stopping Rule using Rademacher Complexity with L1-norm

More like this