PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Duy Hoang, Bastien Berret, Olivier Bruneau, Laurent Fribourg

arXiv:2608.24210v1cs.LG

TL;DR

The paper addresses how to estimate neural-network early stopping without training or relying on distributional assumptions used by many random-matrix methods. It develops an L1-based Rademacher-complexity framework for linear regression, applies it to nonlinear networks through linear probing, and reports close agreement with numerical stopping estimates. The scope remains limited by its focus on linear models, scalar outputs, and clean input data.

  • Problem

    Existing early-stopping estimates typically require gradient-descent training, while analytic random-matrix approaches often assume a data or covariance-eigenvalue distribution.

  • Method

    The paper uses a data-dependent Rademacher-complexity criterion with the L1-norm to estimate a low stopping time for linear regression and applies it to nonlinear networks through linear probing.

  • Results

    The L1-norm yields stopping estimates much closer to numerical stopping times than the L2-norm, with excellent analytic–numerical agreement reported in the examples.

  • Takeaways & Limitations

    The framework provides an analytic early-stopping assessment without a separate test set or gradient-flow training, within the demonstrated linear and linear-probed settings.

  • Takeaways & Limitations

    The paper focuses on linear models, scalar outputs, and inputs without random noise; direct nonlinear treatment and these extensions remain future work.

Abstract

from arXiv · show

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.

1 Introduction

The paper develops a data-independent analytic early-stopping estimate using Rademacher complexity rather than random matrix theory. Its L1-norm formulation is evaluated for linear models and extended to nonlinear networks through linear probing.

  • Contribution: The method estimates the optimal stopping time analytically from a data-dependent criterion C(s), without gradient-descent training or distributional assumptions.The largest s satisfying C(s) provides a low estimate t+ of the optimal time t∗.
  • Contribution: Unlike many random-matrix approaches, the framework does not assume Gaussian data or a Marchenko–Pastur covariance spectrum.The comparison concerns analytic estimates based on random matrix theory and Rademacher complexity.
  • Contribution: Using the L1-norm for Rademacher complexity removes a distribution-dependent factor M and produces stopping estimates closer to numerical stopping times than the L2-norm.The paper reports this comparison on its examples, without giving the numerical gaps in the introduction.
  • Contribution: The framework also analytically evaluates the loss at t = ∞ to determine whether early stopping should be used.The theoretical focus is linear models, while nonlinear neural-network applications use linear probing.
  • Related work: The paper situates its approach among Rademacher-complexity analyses that often require neural-network parameter counts to exceed sample counts.The cited overparameterized setting is associated with benign overfitting or epochwise double descent.

2 Preliminary Results

The preliminary framework bounds population loss with Rademacher complexity and uses gradient flow to analytically identify an early-stopping time without validation training. Using the L1-norm removes dependence on the distribution-related factor M, while the theoretical loss bound remains U-shaped as training progresses.

  • Population loss and Rademacher complexity: The population loss is bounded with Rademacher complexity, using the empirical error and a complexity term that depends on model parameters and sample size.The bound holds with probability at least 1 − δ over the training sample.
  • L1-norm choice: Using the L1-norm removes the factor M from the bound and makes both the estimated stopping time t+ and the bound independent of M.The gradient flow itself still uses the classical quadratic loss, while L1 is used to evaluate Rademacher complexity.
  • Assumptions: The framework assumes bounded input and output domains when estimating the constants C and M.For binary classification, the text specifies M = 2.
  • Analytic early stopping: The method estimates the optimal stopping time analytically from the gradient-flow dynamics, without a separate test set or applying gradient flow.The model parameters are initialized at zero and updated using gradient flow on the training set.
  • Analytic early stopping: The upper-bound curve is U-shaped because the empirical-loss contribution decreases while the L2-norm complexity contribution increases.The framework therefore targets the first local minimum of the bound.

3 A Data-dependent Estimate t+ of t∗

The paper defines t+ as an analytically computable estimate of the first minimum of the Rademacher-complexity loss bound. It proves that t+ is a lower estimate of t∗, can equal t∗ under sufficient conditions, and should be interpreted cautiously when later minima arise.

  • Identification of t+: The method estimates the first local minimum of the complexity-based loss bound by solving for a zero of its derivative.The derivative is expressed through time-varying exponential terms involving the covariance-matrix eigenvalues.
  • Spectral decomposition: The eigenvalues are separated into a small set of higher values and a bulk of lower values, corresponding respectively to informative and nuisance spaces.Their quotient is interpreted as a signal-to-noise-ratio-like quantity.
  • Identification of t+: The analysis partitions time into intervals where the signs of the relevant derivative components remain invariant.On the first interval, the method assumes Φ(0) > 0; otherwise, t∗ = 0 and the method fails.
  • Guarantees: The estimate satisfies t+ ≤ t∗, and sufficient conditions give t+ = t∗.The bound-based loss is decreasing on [0, t+).
  • Computation: The value t+ can be computed numerically from Φ(t) using fixed-point iteration or Newton’s method, without applying gradient flow.An approximation can also be used, and the examples report that approximate values are often nearly identical.
  • Later training behavior: Later local minima can occur after the first minimum, especially in overparameterized settings associated with epoch-wise double descent.The paper compares the bound at t∗ or t+ with its value at infinite time to assess whether early stopping is beneficial or benign overfitting may occur.

4 Examples

The examples test the analytic early-stopping estimate across binary classification, MNIST linear probing, norms, and input distributions. The estimate generally tracks the numerically optimal stopping time, with stronger agreement at larger n/m ratios and better performance for the L1-norm.

  • Norms and scope: The RC-based method is reported to work better with the L1-norm than with the L2-norm, while the examples focus on the underparameterized regime m ≤ n.For m > n, the method is reported to fail because the relevant quantity becomes positive almost immediately near t = 0.
  • Gaussian distribution: For Gaussian binary classification with n = 512 and m = 256, the analytic estimate t+ = 27 matches the theoretical optimum t∗ = 27.The optimum lies in T1 = [0, 100), corresponding to case 1 of Proposition 7.
  • Gaussian distribution: For n = 16384 and m = 256, the estimate t+ = 64 again equals the theoretical optimum t∗ = 64.This is also case 1 of Proposition 7, with both times below τ1 = 100.
  • Gaussian distribution: For a Gaussian example with m = 256 and n = 512, t+ = 342 approximates τ1 = 343 and remains below the theoretical optimum t∗ = 357.This is case 2 of Proposition 7, where t∗ lies beyond the first sign-invariant interval.
  • MNIST classification: MNIST linear probing produces close analytic and numerical optima: t+ = t∗ = 415 for classes 0 and 1, while ttest = 418.The corresponding test-loss values at t+, t∗, and ttest are identical at 0.0582.
  • Various input data distributions: Across Gaussian, uniform, and Pareto inputs, the method works better when n/m is larger; for Pareto data it fails at n = 512 but succeeds at n = 16384.For Pareto data, the reported pairs are t+ = t∗ = 0 at n = 512 and t+ = t∗ = 45 ≈ ttest = 46 at n = 16384.

5 Final Remarks

The paper defines a data-dependent stopping time that estimates when an upper bound on population loss is minimized, without applying gradient flow. It is best suited to underparameterized linear models, extends to nonlinear examples through linear probing, and has several stated future extensions.

  • 5 Final Remarks: The proposed stopping time t+ estimates the time t* when an upper bound on population loss reaches its minimum.The approximation t+approx is also designed to be computed without applying gradient flow.
  • 5 Final Remarks: t+ and especially t+approx can be calculated without applying gradient flow.
  • 5 Final Remarks: The method is well suited to the underparameterized setting m ≤ n, with results improving as the ratio n/m increases.
  • 5 Final Remarks: The method applies to different data distributions without requiring specific knowledge of those distributions.
  • 5 Final Remarks: The work focuses on linear models, while direct nonlinear application, vectorial outputs, and noisy inputs remain future directions.Nonlinear examples were addressed through linear probing, but direct nonlinear treatment was not developed.

Appendix A. Proof of Proposition 1

The appendix proves Proposition 1 by applying a Rademacher-complexity generalization theorem to the linear function class and then bounding its complexity using the coefficient norm.

  • Appendix A. Proof of Proposition 1: The proof invokes a high-probability generalization theorem with Rademacher complexity R_n for the linear class.The stated probability is 1 − δ.
  • Appendix A. Proof of Proposition 1: For linear models, R_n is bounded by ∥a∥_2 C/√n.

Appendix B. Proof of Proposition 5

The appendix derives Proposition 5 by differentiating the empirical and upper-bound losses and using the gradient-flow solution for the coefficient vector initialized at zero.

  • Appendix B. Proof of Proposition 5: The proof begins by differentiating the empirical loss L_S with respect to time.
  • Appendix B. Proof of Proposition 5: It also differentiates the upper-bound loss L*_D using the stated earlier relation.
  • Appendix B. Proof of Proposition 5: For coefficients initialized at zero, the gradient-flow-updated vector a(t) is characterized using the relation K a(t) = v(t) + y.
  • Appendix B. Proof of Proposition 5: The resulting identities follow by combining the preceding relations with equations (7), (32), and (35).

Appendix C. Proof of Proposition 7

The proof of Proposition 7 analyzes when the upper-bound loss decreases, partitions the argument at τ1, and derives whether t+ equals t* or τ1 under the corresponding conditions.

  • Appendix C. Proof of Proposition 7: The proof establishes a derivative criterion: dL*_D(t)/dt < 0 if and only if Φ(t) > 0.
  • Appendix C. Proof of Proposition 7: The analysis defines t* as the least s ≥ 0 at which the derivative of L*_D reaches the relevant stopping condition.
  • Appendix C. Proof of Proposition 7: The proof separates the cases t* < τ1 and t* ≥ τ1.
  • Appendix C. Proof of Proposition 7: When t* < τ1, the inequalities imply t+ = t*.
  • Appendix C. Proof of Proposition 7: In the alternative case, the inequalities imply t+ = τ1.
  • Appendix C. Proof of Proposition 7: Under the additional condition in (24), Γ(t) can be reduced to the sum over indices in I+ with positive Γ_i(t).
Loading 2608.24210v1…