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.
Figures & tables
Figure 1: Top: the sign-invariant subinterval T1=[0,100) with curves Γ1,Ω . Middle: curve dLD∗/dt . Bottom: curve Φ(t) . We have t+=t∗=27<τ1=100 (case 1 of Proposition 7 ).
Figure 2: Curves LD∗Lp and LtestLp for Gaussian distribution ( m=256 , n=512 ). We check that LtestLp is below LD∗Lp ( p=1,2 ), and tL1∗ closer than tL2∗ to ttestLp for p=1 and 2 .
Figure 3: Top: the sign-invariant subinterval T1=[0,100) with curves Γ1,Ω . Middle: curve dLD∗/dt . Bottom: curve Φ(t) . We have t+=t∗=64<τ1 (case 1).
Figure 4: Curves LD∗Lp and LtestLp for Gaussian distribution ( m=256 , n=16384 ). We check that LtestLp is below LD∗Lp ( p=1,2 ), and tL1∗ closer than tL2∗ to ttestLp for p=1 and 2 .
Figure 5: Top: sign-invariant subintervals T1=[0,343) , T2=[343,407) , T3=[407,600) with curves Γ1,Γ2,Ω . Middle: curve dLD∗/dt . Bottom: curve Φ(t) . We have t+=342≈τ1=343≤t∗=357 (case 2 of Proposition 7 ).
Figure 6: Curves LD∗Lp+ϵp and LtestLp for classification 3-5. We check that LtestLp is below LD∗Lp+ϵp ( p=1,2 ), and tL1∗ closer than tL2∗ to ttestLp for p=1 and p=2 .
t1+
tα+
t+
tapprox+
t∗
ttest
∞
t
342
342
342
400
357
356
∞
Ltest
0.1166
0.1166
0.1166
0.1167
0.1166
0.1166
0.1172
LD∗+ϵ
0.2138
0.2138
0.2138
0.2139
0.2138
0.2138
0.2274
Table 1: The values of t1+ , tα+ ( α=2 ), t+ , … , ttest with corresponding Ltest(t) and LD∗(t)+ϵ (Example 11 ).
Figure 7: Top: sign-invariant subintervals T1=[0,421) , T2=[421,493) , T3=[493,600) with curves Γ1,Γ2,Ω . Middle: curve dLD∗/dt . Bottom: curve Φ(t) . We have t+=t∗=415<τ1=421 (case 1).
Figure 8: Curves LD∗Lp+ϵp and LtestLp for classification 0-1. We check that LtestLp is below LD∗Lp+ϵp ( p=1,2 ), and tL1∗ closer than tL2∗ to ttestLp for p=1 and p=2 .
t1+
tα+
t+
tapprox+
t∗
ttest
∞
t
414
417
415
508
415
418
∞
Ltest
0.0582
0.0582
0.0582
0.0586
0.0582
0.0582
0.0590
LD∗+ϵ
0.1703
0.1703
0.1703
0.1707
0.1703
0.1703
0.1713
Table 2: The values of t1+ , tα+ ( α=2 ), t+ , … , ttest with corresponding Ltest(t) and LD∗(t)+ϵ (Example 12 ).
A fundamental problem in machine learning is understanding the effect of early stopping on the parameters obtained and the generalization capabilities of the model. Even for linear models, the effect is not fully understood for arbitrary learning rates and data. In this paper, we analyze the dynamics of discrete full batch gradient descent for linear regression. With minimal distributional assumptions, we characterize the trajectory of the parameters and the expected excess risk. Using this characterization, we show that when training with any learning rate schedule and finite time horizon, the early stopped solution is equivalent to the minimum norm solution for a generalized ridge regression problem. We also prove that early stopping is beneficial for generic data with arbitrary spectrum and for a wide variety of learning rate schedules. We provide an estimate for the optimal stopping time and empirically demonstrate the accuracy of our estimate.
Rishi Sonthalia, Jackie Lok, Elizaveta Rebrova
Department of Mathematics, Boston College · ORFE Department, Princeton University
We study data-driven early stopping for spectral regularisation methods in the classical non-parametric regression setting. Building on the discrepancy principle, we propose a multi-scale stopping rule that applies to general kernel estimators and show that, unlike previous approaches, it achieves full adaptivity over all smoothness levels in the well-specified case. A key contribution of our work is an extension based on random feature approximations, which reduces computational cost on large datasets while preserving minimax-optimal statistical guarantees. Our procedure not only selects an optimal stopping time but also provides a fully data-driven choice of the number of random features needed to achieve optimal rates. Through the established connection between random features and neural networks in the neural tangent kernel regime, our method further yields a principled, data-driven recommendation for the network width. We prove that the resulting simultaneously chosen width and stopping time allow neural networks to attain minimax-optimal learning rates without prior knowledge of smoothness or capacity parameters.
One of the fundamental challenges in the deep learning community is to theoretically understand how well a deep neural network generalizes to unseen data. However, current approaches often yield generalization bounds that are either too loose to be informative of the true generalization error or only valid to the compressed nets. In this study, we present a simple yet non-vacuous generalization bound from the optimization perspective. We achieve this goal by leveraging that the hypothesis set accessed by stochastic gradient algorithms is essentially fractal-like and thus can derive a tighter bound over the algorithm-dependent Rademacher complexity. The main argument rests on modeling the discrete-time recursion process via a continuous-time stochastic differential equation driven by fractional Brownian motion. Numerical studies demonstrate that our approach is able to yield plausible generalization guarantees for modern neural networks such as ResNet and Vision Transformer, even when they are trained on a large-scale dataset (e.g. ImageNet-1K).
Chengli Tan, Jiangshe Zhang, Junmin Liu +1
Northwestern Polytechnical University, Xi’an, China · Xi’an Jiaotong University, Xi’an, China · SGIT AI Lab, State Grid Corporation of China, Xi’an, China