cs.LGOct 24, 2026

When is early stopping beneficial under label noise? A phase diagram for kernel gradient flow

Authors: Fabrizio Boncoraglio, Lenka Zdeborová

Organizations: Statistical Physics of Computation Laboratory, École Polytechnique Fédérale de Lausanne (EPFL) CH-1015 Lausanne

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Early stopping is commonly used to prevent fitting label noise from degrading generalization. Does this mean that, when a positive fraction of the training labels is intrinsically unpredictable, the best test error must occur before interpolation? Experiments on a CIFAR10 classification task with randomly labeled examples motivate the opposite possibility: although fixed-feature and shallow models exhibit late-time deterioration of the test error, the need for early stopping essentially disappears in larger, deeper convolutional networks even after the random labels have all been classified correctly. We determine when late-time deterioration disappears entirely in a solvable setting. For kernel gradient flow on a synthetic noisy classification task, we derive sharp high-dimensional learning curves and obtain a phase diagram controlled by the balance between the linear kernel component that learns the shared relation between inputs and labels and the higher-order components that enable fitting the label noise. In one regime, generalization is optimized at finite time and early stopping is necessary. In another, generalization improves until interpolation, but the endpoint is suboptimal across kernels. At the boundary, the interpolating endpoint attains the lowest generalization error across the considered kernel family and all training times. Thus, even with extensive irreducible label noise, interpolation can outperform early stopping. The neural-network experiments leave open how learned representations acquire an analogous favorable geometry.

Figures & tables

Figure 1: Generalization along the path to memorization. Test error on 2000 cats and dogs ( xx -axes) versus classification error on the randomly labelled automobiles ( yy -axes) taken from the CIFAR10 dataset. The fixed training set has n=7000n=7000 images: 28002800 cats, 28002800 dogs with their respective labels, and 14001400 automobiles with independent random labels. Panels vary the overparametrization ratio κ=P/n≈1,10,100\kappa=P/n\approx 1,10,100 , where PP counts optimized parameters. Curves average about 30 completed seeds; a centered arithmetic average of up to seven neighboring recorded times is applied to both coordinates for display, preserving the initial and final values. These parametric curves trace the two errors as training time tt increases. Triangles mark initialization, squares the last iterate and crosses the minimum displayed test error. All trainable networks use square loss and constant-rate Nesterov SGD, without augmentation or weight decay, through 1500 epochs; RF-CNN uses full-batch readout GD through 101210^{12} steps. In Appendix F we provide all numerical details and the unsmoothed trajectories, including training loss.
Figure 2: The generalization cost of training to interpolation. For γ=π/5\gamma=\pi/5 , δ0=0\delta_{0}=0 , and λ=0\lambda=0 , colors show 100Δstop100\Delta_{\rm stop} from Eq. ( 16 ) in percentage points, comparing interpolation with optimal stopping for the same kernel. The gray region has exactly zero stopping benefit. The dashed line, εc≃0.2633\varepsilon_{\rm c}\simeq 0.2633 (for γ=π/5\gamma=\pi/5 ), separates it from a region with a finite optimal stopping time, independently of α\alpha . Contours mark benefits of 0.10.1 , 0.20.2 , 0.30.3 , and 0.40.4 percentage points.
Figure 3: Test error at interpolation and optimal stopping. We fix α=1.5\alpha=1.5 , ε=0.1\varepsilon=0.1 , and λ=0\lambda=0 and evaluate Eqs. ( 9 ) and ( 10 ). The solid curve is Egen(∞;γ)\mathcal{E}_{\rm gen}(\infty;\gamma) ; the dashed and dash-dotted curves are Egen(τes;γ)\mathcal{E}_{\rm gen}(\tau_{\rm es};\gamma) for δ0=0\delta_{0}=0 and 11 . For γ≤γc(ε)\gamma\leq\gamma_{\rm c}(\varepsilon) , Eq. ( 15 ) gives tes=∞t_{\rm es}=\infty , so all three curves coincide. The star marks the unique global optimum at γc(ε)/π≃0.2550\gamma_{\rm c}(\varepsilon)/\pi\simeq 0.2550 from Eq. ( 14 ). For larger angles, finite optimal stopping remains strictly above this value; the gap is more visible for δ0=1\delta_{0}=1 . The inset zooms on the increasing excess Egen(τes;γ)−Egen(∞;γc(ε))\mathcal{E}_{\rm gen}(\tau_{\rm es};\gamma)-\mathcal{E}_{\rm gen}(\infty;\gamma_{\rm c}(\varepsilon)) for the dashed blue curve at δ0=0\delta_{0}=0 , to highlight that the minimum is truly attained only at γ=γc(ε)\gamma=\gamma_{c}(\varepsilon) .
Figure 4: Kernel geometry controls the gradient-flow trajectory. We fix α=1.5\alpha=1.5 , ε=0.1\varepsilon=0.1 , δ0=1\delta_{0}=1 , and λ=0\lambda=0 . Arrows indicate increasing time; the cross marks test-error minima and the blue dot marks convergence. The blue trajectory benefits from early stopping. Red and green improve until interpolation, but only the critical red kernel attains the test-error bound in Eq. ( 18 ) (vertical line).
Figure 5: Gradient flow and ridge follow different parametric paths. We fix α=5\alpha=5 , ε=0.1\varepsilon=0.1 , and δ0=0\delta_{0}=0 , with γ/π=0.40\gamma/\pi=0.40 , γ=γc(ε)\gamma=\gamma_{\rm c}(\varepsilon) ( γc(ε)/π≃0.2550\gamma_{\rm c}(\varepsilon)/\pi\simeq 0.2550 ), and γ/π=0.22\gamma/\pi=0.22 . For each kernel, we plot the test-error difference between unregularized kernel gradient flow and converged kernel ridge regression at the same memorization error. Negative values favor gradient flow. Squares mark the shared t→0+t\to 0^{+} and λ→∞\lambda\to\infty classification limits; the circle marks the shared interpolating endpoint. Curves are numerical evaluations of Eqs. ( 9 )–( 11 ); we use the ERM ridge result of Farné et al. (2026) . More details in Appendix E .
Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6: Numerical validation across four learning regimes. Lines show the theoretical generalization and memorization errors; circles and squares show the corresponding means from RBF simulations, with one standard error bars. All panels use λ=0\lambda=0 and retain the kernel’s nonzero constant term. Parameters are shown above the panels. (a) Delayed generalization after factual memorization. (b) Delayed generalization followed by late overfitting. (c) Optimal stopping before factual memorization. (d) Continued improvement toward the critical interpolating endpoint. Dotted lines mark tmem(0.01)t_{\rm mem}(0.01) and dashed lines finite test_{\rm es} . The corresponding reduced times are τes=μ12tes\tau_{\rm es}=\mu_{1}^{2}t_{\rm es} and τmem(δ)=μ12tmem(δ)\tau_{\rm mem}(\delta)=\mu_{1}^{2}t_{\rm mem}(\delta) .
Figure 7: Kernel-dependent generalization and memorization on CIFAR10. Full RBF-kernel gradient flow with zero initialization and zero ridge. Curves show the unsmoothed mean errors over five repetitions; arrows indicate increasing time. Stars mark the minimum mean test error on the evaluated grid, including the exact convergence endpoint and choosing it when tied. Filled squares mark interpolation. The different bandwidths reproduce the qualitative contrast between trajectories that benefit from early stopping and trajectories with little or no observed deterioration near interpolation.
Figure 8: Unsmoothed dynamics behind Figure 1 . Test error, memorization error and full training MSE (top to bottom), averaged over 2828 – 3030 completed seeds per curve through 15001500 epochs at κ≈1,10,100\kappa\approx 1,10,100 . Shading gives pointwise 95%95\% confidence intervals for the mean across seeds. Crosses mark each raw mean test curve’s minimum and the corresponding values of the other metrics; squares mark the last observation. No temporal averaging is applied. The models are two-, four- and six-layer CNNs, a residual network with nominal depth 1616 (ResNet-16), and a wide residual network with nominal depth 2828 (WRN-28).
Figure 9: Generalization while fitting random labels with augmented cross-entropy. Clean cat-dog test error versus classification error on randomly labelled automobiles, for the 61446144 -image dataset and approximately 2.72.7 million optimized parameters per network. Coordinates are averaged over at most five neighboring saved observations within each seed, then over five seeds. Triangles mark initialization, arrows indicate increasing time, crosses mark the minimum displayed mean test error and squares mark the reporting endpoints. Trajectories extend to 20002000 epochs, except WRN-28, which is shown through 10001000 epochs.
Figure 10: Unsmoothed trajectories under augmented cross-entropy training. Clean test error, automobile memorization error and mean binary cross-entropy on all original training images. Lines show five-seed means; shading gives pointwise 95%95\% confidence intervals for these means. Crosses mark the minimum raw mean test error and the corresponding values of the other metrics; squares mark the reporting endpoints. The comparison includes CNN4, ResNet-16, CNN6, WRN-28 and MobileNetV2. Trajectories extend to 20002000 epochs, except WRN-28, which is shown through 10001000 epochs. Time is displayed as log⁡10(1+t)\log_{10}(1+t) with epoch labels; the cross-entropy axis is logarithmic.
Figure 11: Sensitivity to the optimization protocol. Difference between the final test error and the lowest test error recorded during each run, averaged over five seeds and expressed in percentage points. Results compare two-layer CNNs, four-layer CNNs and ResNet-16 at intermediate capacity (top) and high capacity (bottom). Error bars give 95%95\% confidence intervals for the mean. The larger deep models retain a smaller gap across the displayed optimizer, learning-rate and batch-size choices.
Figure 12: Extended ResNet controls with augmented cross-entropy. Columns vary training-set size, batch size and random-label fraction under the 400400 -epoch recipe of Section F.3 . Means are unsmoothed; bars show one sample standard deviation over ten seeds at ε=0.1,0.2\varepsilon=0.1,0.2 and five otherwise. “Fixed LR” and “linear LR” refer to peak rates. Memorization error is omitted at ε=0\varepsilon=0 .
Figure 13: ResNet controls with constant-rate square loss. Conditions follow Figure 12 , with five seeds. Per-seed arithmetic averaging uses a symmetric window of half-width at most 0.080.08 in log⁡10(1+t)\log_{10}(1+t) , shrinking at the endpoints. Lines and shading give means and one sample standard deviation. Horizons are 200200 epochs for n=9216n=9216 , 300300 for ε=0.6\varepsilon=0.6 , and 400400 otherwise; time is labelled in epochs.
Figure 14: Memorization paths with random labels on cats and dogs. Square-loss training at κ=P/n≈1,10,100\kappa=P/n\approx 1,10,100 , averaged over ten seeds. Both coordinates use the endpoint-preserving average over at most seven saved times described in Section F.1 . Triangles mark initialization, crosses the minimum displayed mean test error and squares the endpoints. Trainable networks run for 15001500 epochs; RF readout GD runs through 101210^{12} full-batch steps.
Figure 15: Unsmoothed square-loss trajectories with random labels on cats and dogs. Test error, memorization error and training square loss for the five trainable architectures, through 15001500 epochs. Lines show ten-seed means; shading gives pointwise 95%95\% confidence intervals. Crosses mark the minimum raw mean test error and corresponding other metrics; squares mark endpoints. Time uses log⁡10(1+t)\log_{10}(1+t) with epoch labels, and loss is shown logarithmically.
Figure 16: Memorization paths with augmented cross-entropy and randomized cats and dogs. Five-seed means after endpoint-preserving averaging over at most five saved times; markers follow Figure 14 . Reporting horizons are 20002000 epochs for CNN4, 11001100 for ResNet-16, 900900 for WRN-28 and 17001700 for MobileNetV2. Each network has approximately 2.72.7 million optimized parameters.
Figure 17: Unsmoothed cross-entropy trajectories with randomized cats and dogs. Five-seed means of test error, memorization error and training cross-entropy on original images, with pointwise 95%95\% confidence intervals. Horizons follow Figure 16 ; CNN6 is additionally shown through 20002000 epochs. Markers and axes follow Figure 15 . No temporal averaging is applied.
More in this topic

Early Stopping

Early stopping uses signals during training or inference to halt computation before a fixed budget, balancing generalization, quality, and cost.

See all 46 papers

Explore similar work

CardsList
Aug 6, 2026

Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification

In overparameterised classification, training data can be linearly separable even when the underlying distribution is not. In this setting, gradient descent (GD) on the logistic loss diverges in norm while converging in direction to a max-margin interpolating classifier, whose implicit bias can be statistically suboptimal. In this work, we show that early stopping can overcome this suboptimality: in a Gaussian mixture model with label-flipping noise, GD stopped at an appropriate oracle time achieves minimax-optimal excess zero-one risk for covariance spectra with fast and continuous decay, including polynomial and exponential spectral decays. Our analysis combines a sharp upper bound for the early-stopped iterate with a matching statistical lower bound over arbitrary classifiers, yielding optimal rates that are validated by experiments. A central technical contribution is a new calibration result that converts excess logistic risk into excess zero-one risk; it handles the model misspecification induced by the label-flipping noise, and removes the square-root rate in standard bounds. We also establish a lower bound for linear interpolators, showing that interpolation can require exponentially more samples than early stopping to achieve the same excess risk.

Alex Buna, Shirley Xiaoqi Liu, Patrick Rebeschini

Department of Statistics, University of Oxford

Early StoppingGradient DescentGaussian Mixture ModelsMinimax EstimationClassification
AskPDF
May 27, 2026

Gradient-Flow Optimization as Dynamic Random-Effects Inference: Testing and Early Stopping with Applications to Deep Learning

Gradient-flow optimization is usually viewed as an algorithmic procedure for minimizing empirical loss, with training duration selected by validation or heuristic early stopping rules. We develop a statistical inference framework for gradient-flow training. We show that whenever fitted values evolve through a time-invariant positive semidefinite training operator, the output at each time is equivalent to the best linear unbiased predictor under a corresponding random-effects model. Training time then becomes a variance-component parameter governing variance reallocation from residual noise to structured signal. This turns two training decisions into inferential problems: whether training is needed becomes a variance-component test for signal beyond initialization, and how long to train becomes restricted maximum likelihood (REML) estimation of the training-time variance component. We show that the REML-guided early stopping rule selects the time at which optimized spectral losses become decorrelated from the training-operator eigenvalues. The asymptotic prediction optimality of the REML-guided early stopping time is established for fixed-design in-sample risk and random-design out-of-sample risk. Deep learning models in fixed-kernel gradient regimes provide canonical instantiations for our results. Numerical experiments and a UK Biobank proteomics application show competitive accuracy of the REML-guided early stopping time with reduced reliance on validation splits and repeated checkpoint evaluation.

Minhao Yao, Ruoyu Wang, Xihong Lin +2

Centre for Biomedical Data Science, Duke-NUS Medical School, National University of Singapore · Department of Biostatistics, Harvard T.H. Chan School of Public Health, Boston, MA, USA · Institute of Natural Sciences, MOE-LSC, School of Mathematical Sciences, CMA-Shanghai, SJTU-Yale2026 Joint Center of Biostatistics and Data Science, Shanghai Jiao Tong University +1

Early StoppingNeural Network Training DynamicsMaximum Marginal Likelihood EstimationGradient Descent Dynamics
AskPDF
Aug 25, 2026

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

Training neural networks requires balancing the trade-off between fitting the training data and achieving robust performance on unseen inputs. This ability, commonly referred to as generalizability, is determined by the gap between the empirical risk on the training set (empirical loss'') and the expected risk over the data distribution (generalization error''). Existing approaches typically estimate the generalization error numerically, requiring gradient descent training and an early stopping'' strategy. In this work, we introduce an analytic framework that estimates the optimal time of early stopping without the need for training. Several works in the literature also give such analytical estimations, but they are generally based on random matrix theory and often make assumptions on the distribution of the data or the eigenvalue distribution of the covariance matrix. In contrast, our work is based on Rademacher complexity (RC) without needing such probabilistic assumptions. For both theoretical and numerical reasons, it is more relevant to express RC with the L1- norm rather than with the L2-norm. We focus on the case of linear models and the problem of linear regression. Thanks to the linear probing'' method, our results can, however, be successfully applied to nonlinear neural networks, as illustrated in the classification MNIST example.

Duy Hoang, Bastien Berret, Olivier Bruneau +1

Universit´e Paris-Saclay, CNRS, ENS Paris-Saclay, LMF Gif-sur-Yvette, 91190, France · Universit´e Paris-Saclay, Inria, CIAMS Gif-sur-Yvette, 91190, France · Universit´e Paris-Saclay, ENS Paris-Saclay, LURPA Gif-sur-Yvette, 91190, France

Early StoppingNeural Network GeneralizationStatistical Learning TheoryLinear Regression
AskPDF