Towards Data-Algorithm Dependent Generalization: a Case Study on Overparameterized Linear Regression
Authors: Jing Xu
Jiaye Teng
Yang Yuan
Andrew C Yao
Venue: NeurIPS 2023 poster (2023)
Keywords: data-algorithm dependent generalization analysis
overparameterized linear regression
TL;DR: We present a novel generalization analysis on overparameterized linear regression, which takes both data-factor and algorithm-factor into consideration.

Abstract: One of the major open problems in machine learning is to characterize generalization in the overparameterized regime, where most traditional generalization bounds become inconsistent even for overparameterized linear regression. In many scenarios, this failure can be attributed to obscuring the crucial interplay between the training algorithm and the underlying data distribution. This paper demonstrate that the generalization behavior of overparameterized model should be analyzed in a both data-relevant and algorithm-relevant manner. To make a formal characterization, We introduce a notion called data-algorithm compatibility, which considers the generalization behavior of the entire data-dependent training trajectory, instead of traditional last-iterate analysis.  We validate our claim by studying the setting of solving overparameterized linear regression with gradient descent. Specifically, we perform a data-dependent trajectory analysis and derive a sufficient condition for compatibility in such a setting. Our theoretical results demonstrate that if we take early stopping iterates into consideration, generalization can hold with significantly weaker restrictions on the problem instance than the previous last-iterate analysis.

Towards Data-Algorithm Dependent Generalization: a Case Study on Overparameterized Linear Regression
Jing Xu" IIS Tsinghua University
Jiaye Teng"
III, Tsinghua University
mujing21@mails tsinghua. edu. en
tjy20Gmails, tsinghua. edu.
Yang Yuan
Andrew Chi-Chih Yao
III., Tsinghua University
III. Tsinghua University
Shanghai Artificial Intelligence Laboratory
Shanghai Artificial Intelligence Laboratory
Shanghai Qi Zhi Institute
Shanghai Qi Zhi Institute
yuanyangötsinghua edu. cn
andrescyao@tsinnghaa edu. cn
Abstract
One of the major open problems in machine learning is to characterize general- ization in the overparameterized regime, where most traditional generalization bounds become inconsistent even for overparameterized linear regression [46]. many scenarios, this failure be attributed to obscuring the crucial interplay between the training algorithm and the underlying data distribution. This paper demonstrate that the generalization behavior of overparameterized model should be analyzed in a both data-relevant and algorithm-relevant manner. To make a formal characterization, We introduce notion called data-algorithm compatibility, which considers the generalization behavior of the entire data-dependent training trajectory, instead of traditional last-iterate analysis. We validate our claim by studying the setting of solving overparameterized linear regression with gradient descent. Specifically, we perform data-dependent trajectory analysis and derive a sufficient condition for compatibility in such a setting. Our theoretical results demonstrate that we take early stopping iterates into consideration, generalization can hold with significantly weaker restrictions on the problem instance than the previous last-iterate analysis.
Introduction
their remarkable generalization ability is still among the essential mysteries in the deep learning community. One of the most intriguing features of deep neural networks is overparameterization, which confers level of tractability the training problem, but leaves traditional generalization theories failing to work. In generalization analysis. both the training algorithm and the data distribution play essential For instance, a line of work [46 74] highlights the role of the algorithm by showing that the -orrithmmirrelevantt uniform convergence bounds can become inconsistent in deep learning regimes. Another line of work g 688 on benign overfitting emphasizes the role of data distribution via profound analysis of specific overparameterized models.
Although deep neural networks achieve great success in practice 13 14 63
roles 223 28).
Despite the significant role of data and algorithm in generalization analysis, existing theories usually focus on either the data factor (e.g., uniform convergence [46] and last iterate analysis [8] (8) or the algorithm factor (e.g., -base bounds 24 Combining both data and algorithm factor into
Equall Contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Excess Risk
Test Error Training Error
Training Loss
10
Excess Risk
107
Training LOss
Training Error
Test Error
137
30-
30-
20
W
50
304
289
X0
Epochs
Epochs
(a) Linear Regression
(b) Corrupted MNIST
Figure 1: (a) The training plot for linear regression with spectrum X; 1/t2 using GD. Note that the axes are in the log scale. (b) The training plot of CNN on corrupted MNIST with 20 % label noise using SGD. Both models successfully learn the useful features in the initial phase of training. but it takes a long time for them to fit the noise in the dataset. The observations demonstrate the power of data-dependent trajectory analysis, since the early stopping solutions on the trajectory generalize well but the final iterate fails to generalize. See Appendix C for details.
generalization analysis can help derive tighter generalization bounds and explain the generalization ability of overparameterized models observed in practice. In this sense, natural question arises:
How to incorporate both data factor and algorithm into generalization analysis?
To gain insight into the interplay between data and algorithms, we provide motivating examples of a synthetic overparameterized linear regression task and classification task on the corrupted MNIST dataset in figure In both scenarios, the final iterate with less algorithmic information, which may include the algorithm type (e.g., GD or SGD), hyperparameters (e.g., learning rate, number of epochs), generalizes much worse than the early stopping solutions (see the Blue Line). In the linear regression case, the generalization error of the final iterate can be more than x 100 larger than that of the early stopping solution. In the MNIST case, the final iterate the SGD trajectory has 19.9% test error, much higher than the 2.88% test error the best iterate on the GD trajectory. Therefore, the almost ubiquitous strategy of early stopping is key ingredient in generalization analysis for overparameterized models, whose benefits have been demonstrated both theoretically and empirically 2 27 34 41l 72). By focusing on the entire optimization trajectory and performing data-dependent trajectory analysis, both data information and the dynamics of the training algorithm be exploited yield consistent generalization bounds.
When we take the algorithm into considcration and analyze the data-dependent training trajectory, generalization occurs if the minimum excess risk of the iterates the training trajectory converges to zero, as the sample size tends to infinity. This accords with the real practice of training deep neural networks, where can pick up the best parameter the training trajectory, by calculating its loss on a validation dataset. We dub this notion of generalization as as data- setai-aggoottt--ooeee comparibility. which is formally defined in Section 3.2
The significance of compatibility comes in three folds. Firstly, incorporates both data and algorithm factors into generalization analysis, and is suitable for the overparameterization regime (see Defini- tion B.I.. Secondly, it serves as a minimal condition for generalization, without which one cannot expect to find consistent solution via standard learning procedures. Consequently, compatibility holds with only mild assumptions and applies to wide range of problem instances (see Theorem 4.1). Thirdly, it captures the algorithmic significance of early stopping in generalization. By exploiting the algorithm information along the entire trajectory, we arrive at better generalization bounds than the last-iterate analysis (see Table and
[ for examples).
To theoretically validate compatibility, we study under overparameterized linear regression setting. Analysis of the overparameterized linear regression is reasonable starting point to study more complex models like deep neural networks [17 (57) since many phenomena the high dimensional non-linear model are also observed in the linear regime (e.g., Figure I]. Furthermore, the neural

---

langent kernel (NTK) framework 4 26 demonstrates that very wide neural networks trained using gradient descent with appropriate random initialization can be approximated by kernel regression in reproducing kernel Hilbert space, which rigorously establishes close relationship between overparameterized linear regression and deep neural network training.
Specifically, we investigate solving overparameterized linear regression using gradient descent with constant step size, and prove that under some mild regularity conditions, gradient descent is compatible with overparameterized linear regression if the effective dimensions of the feature covariance matrix are asymptotically bounded by the sample size. Compared with the last-iterate analysis [8), the main theorems in this paper require significantly weaker assumptions, which demonstrates the benefits of data-relevant and algorithm-relevan generalization analysis.
We summarize our contributions as follows:
We formalize the notion of cttt--lggrrtim--ommaibiiiii which highlights the interaction between data and algorithm and serves as a minimal condition for generalization.
We derive sufficient condition for compatibility in solving overparameterized linear regression with gradient descent. Our theory shows that generalization of carly-stopping iterates requires much weaker restrictions in the considered setting.
Technically, we derive time-variant generalization bounds for overparameterized linear regression via data-dependent trajectory analysis. Empirically, we conduct the various experiments verify the the theoretical results and demonstrate the benefits of early stopping.
2
Related Works
Data- Data-Dependent Techniques mainly focus on the data distribution condition for generalization.
One of the most popular data-dependent methods is uniform convergence 77] 29, 74 75). However, recent works [46 47] point out that uniform convergence may not be powerful enough explain generalization, because it may only yield inconsistent bound in even linear regression cases. Another line of works investigates benign overfitting, which mainly studies generalization of overfitting
solutions
g 21 35
770
76 [77]
Al
Techniques measure the role of the algorithmic information in generalization.
line of works derives generalization bounds via algorithm stability 12 18 19
24
31
32
45
A parallel line of works analyzes the implicit bias of algorithmic information 25 39 40 59
64
which are mainly based on analyzing a specific data distribution (e.g., linear separable).
Other Generalization Techniques. Besides the techniques above, there are many other approaches. For example, PAC-Bayes theory performs well empirically and theoretically [6 61] and can yield non-vacuous bounds in deep learning regimes 54]. Furthernore, there are other promising techniques including information theory 66 [6 7T] and compression- based bounds [3
48
38
Early Stopping has the potential to improve generalization for various machine learning problems [ [R]
30
38
533
62
69, 74]. A line of works studies the rate of early stopping in linear regression
and kernel regression with different algorithms, e.g. gradient descent (72). stochastic gradient
descent [75 51 55 66), gradient flow (2), conjugate gradient [10) and spectral algorithms [22 36
Beyond linear models, carly-stopping is also effective for training deep neural networks [27 34
Another line of research focuses the signal for early stopping 20 52
Preliminaries
In this section, we formally define compatibility between the data distribution and the training algorithm, starting from the basic notations.
3.1 Notations
Data Distribution. Let denote the population distribution and D denote a data point sampled from distribution D. Usually, z contains feature and its corresponding response. Besides, we denote the dataset with samples Z A {zi]een) where D are i.idd sampled from distribution D.
3

---

Loss and Excess Risk. Let 2(0:z) denote the loss sample with parameter θ E R'. The corresponding population loss is defined as L(O; D) B z). When the context is clear, we omit the dependency on D and denote the population loss by L(O). Our goal is to find the optimal parameter O* which minimizes the population loss, i.e., L(O") ming L(O). Measuring how parameter 0 approaches 0 relies term excess risk R(0), defined as R(0) _ L(0) L(
Algorithm. Let A(-) denote a iterative algorithm that takes training data as input and outputs sequence of parameters (0% |120, where t is the iteration number. The algorithm can be either deterministic or stochastic, egg., variants of (S)GD.
3.2 Definitions of Compatibility
Based on the above notations, we introduce the notion of compatibility between data distribution and algorithm Definition 3.1] Informally, compatibility measures whether consistent excess risk can be reached along the training trajectory. Note that we omit the role of the loss function in the definition, although the algorithm depends on the loss function.
Definition 3.1 (Compatibility). Given loss function f(-) with corresponding excess risk R(-), a data distribution DD is compatible with an algorithm A if there exists nonempty subsets Ta of N, such that supteT, R(O!!)) converges to zero in probability
sample size tends to infinity, where (0x) 1120 denotes the output of algorithm A, and the randomness comes from the sampling of training data Z from distribution D and the execution of algorithm A. That is say, (D,A) is compatible if there exists nonempty sets Tw, such that
sup R(O(.)) S 0 as n2 000
(1)
EET,
We call (Tulaso the compatibility region of (D, A). The distribution D is allowed to change with n. this case, DD should be understood as a sequence of distributions (Da)n21. 1. We also allow the dimension of model parameter 0 to be infinity or to grow with n. We omit this dependency n when the context is clear.
Compatibility serves minimal condition for generalization, since if a data distribution is incompat- ible with the algorithm, one cannot expect to reach a small excess risk even if we allow for arbitrary early stopping. However, we remark that considering only the minimal excess risk is insufficient for
a practical purpose, as one cannot exactly find the / that minimizes R(O!))) due to the noise in the validation set. Therefore, it is meaningful to consider a region of time on which the excess risk is consistent as in Definition 3.1 The larger the region is, the more robust the algorithm will be to the noise in its exccution.
Comparisons with Other Notions. Compared classic definitions of learnability, e.g. PAC learning, the definition of compatibility is data-specific and algorithm-specific and is thus a more fine-grained notion. Compared to the concept of benign proposed in 8 which studies whether the excess risk at t= oo converges to zero in probability as the sample size goes to infinity, compatibility only requires that there exists time to derive a consistent excess risk. We will show later in Section 4.2 that in the overpamameterized linear regression setting, there exist cases such that the problem instance is compatible but not benign.
4 Analysis of Overparameterized Linear Regression with Gradient Descent
To validate the mcaningfulness of compatibility, study it in the overparameterized linear regression regime. We first introduce the data distribution, loss, and training algorithm, and then present the main theorem, which provides a sufficient condition for compatibility in this setting.
4.1 Preliminaries for Overparameterized Linear Regression
Notations. Let O,o, Ω w denote asymptotic notations, with their usual meaning. For example, the argument a, = O(b,,) means that there exists large enough constant C, such that S Cbn. We use S with the same meaning as the asymptotic notation O. Besides, let ||æ||| denote the l, norm for vector æ. and ||||| denote the operator norm for matrix A. We allow the vector to belong to

---

countably infinite-dimenn dimensional Hilbert space H. and with slight abuse of notation, we use Rx interchangeably with H. In this case, x denotes inner product and T denotes tensor product for I, 2 E H. A random variable X called o-subgaussian EE E[ - x²² /2 for any X.
Data Distribution. Let (æ, y) E Rº x R denote the feature vector and the response, following - R " denote the feature covariance matrix, whose eigenvalue Σi>g iaa with decreasing cigenvalues Å1 2 A 2 .... We
joint distribution D. Let Σ decomposition is Σ VAV make the following assumptions on the distribution of the feature vector.
Assumption (Assumptions on feature distribution). We assume that
1. E [x] O.
2. \1 0, Ei d < C for some absolute constant C.
3. Let Ø A V The random vector it has independent oz-Subgaussian entries.
Loss and Excess Risk. We choose square loss the loss function f, i.c. E(O, (x, = 1/2(y x' 2 The corresponding population loss is denoted by L(Ø) = EE(O, (x, y)) and the optimal parameter is denoted by 0 argminggs T((O). We assume that ||0*|| < C for some absolute constant C. If there are multiple such minimizers, we choose an arbitrary one and fix it thereafter. We focus the excess risk of parameter 0, defined as
1 ( -0--0) E(0 -0))
R(O) = L( - L(0)
(2)
2
Let E = y x T denote the noise data point (a, y). The following assumptions involve the conditional distribution of the noise.
Assumption 2 (Assumptions on noise distribution). We assume that
1. The conditional noise s x has zero mean.
2. The conditional noise s x is oy-subgaussian.
Note that both Assumption and Assumption are commonly considered in the related literatures S
68 [6].
Training Set. Given training set {(,,, y)]ssssnn with pairs independently sampled from the population distribution D, we define X - (æI,..., (x,) E Raxp as the feature matrix, Y & (y1. T E R" as the corresponding noise vector, and g & Y -xe as the residual vector. Let the singular value decomposition (SVD) of X be X = U WT, with À = diag( ... Mnn e gax" ll
We consider the overparameterized regime where the feature dimension larger than the sample size, namely, p n. In this regime, assume that rank X) ) almost surely as in Bartlett et al. [8].
This assumption is equivalent to the invertibility of X
Assumption 3 (Linear independent training set). For any p. assume that the features in the training set (æ), ",, ,n, is linearly independent almost surely.
Algorithm. Given the dataset (X, Y), define the empirical loss function as L(
2n X0 Y
1
We choose full-batch gradient descent on the empirical risk with a constant learning rate À as the algorithm A in the previous template. In this case, the update rule for the optimization trajectory (0,) J:20 is formulated as
0,+1 = 0,
(X0,- -
n
Without loss of generality, we consider zero initialization 0n 0 in this paper. In this case, for sufficiently small learning rate X, 0g converges to the min-norm interpolator 0 = X (XXT)-1X as goes to infinity, which was well studied previously [8]. This paper takes one step further and discuss the excess risk along the entire training trajectory (R(00)
5

---

Effective Rank and Effective Dimensions. We define the effective ranks of the feature matrix E as Our results depend notions of effective dimension
r(E) Ei and Rie ( of the feature covariance E, defined as
2 Ad)
Eisa A?
Co Eisi A
ko min
2 0: A1+1
(4)
n2
Eiso A
4 min l 120: A441
(5)
m
where co. are constants independent of the dimension p. sample size n. and time We omit the dependency of ko, hn on co, C1, n, Σ when the context is clear.
4.2 Main Theorem for Overparameterized Linear Regression with Gradient Descent
Next, we present the main result this section, which provides a clean condition for compatibility between gradient descent and overparameterized linear regression.
Theorem 4.1. Consider the overparameterized linear regression setting defined in section 4.1
Let
Assumption 22 and hold. Assume the learning rate satisfies À = O Ty(2))
If the covariance satisfies kn = o(1), Rho (E) w(r), ()) o(n), it is compatible in the region Tw = (w ( oc).
If the covariance satisfies Ko O(n), o(n), r(E) o(n). it is compatible in the region Tn (w (4) (z)).
If the covariance does not change with n, and satisfies ko O(n) and = co, it is compatible in the region Tn = (w (2) (7))
The proof of Theorem is given in Appendix A and sketched Section 5 The theorem shows that gradient descent is compatible with overparameTerized linear regression under some mild regularity conditions on the learning rate, effective rank and effective dimensions. The condition on the learning rate is natural for optimizing smooth objective. We conjecture that the condition ko- O(n) can not be removed in general cases, since the effective dimension ko characterizes the concentration of the singular values of the data matrix X and plays crucial role in the excess risk of the gradient descent dynamics.
Comparison with Benign Overfitting. The paper [ studies overparameterized linear regression and gives the condition for min-norm interpolator to generalize. They prove that the feature covariance Σ benign if and only if
Ko o(n), RE, (E) w(n), r(E) o(n)
(6)
As discussed in Section 3.2 benign problem instance also satisfies compatibility, since benign overfitting requires stronger condition on ko and an additional assumption on Reg (E). The following example shows that this inclusion relationship is strict.
Example 4.1. Under the same assumption as in Theorem 4.1 if the spectrum of E satisfies
k
for some 1, we derive that ko (m). Therefore, this problem instance satisfies compatibility, but does not satisfy benign overfitting.
Example shows the existence of a case where the early stopping solution can generalize but interpolating solution fails. Therefore, Theorem can characterize generalization for much wider range of problem instances.
"Constants may depend dx. and omit this dependency thereafter for clarity.

---

Proof Sketch and Techniques
5.1 A Time Variant Bound
We further introduce an additional type of effective dimension besides ko, k1, which is time variant and is utilized track the optimization dynamics. Definition 5.1 (Effective Dimensions). Given feature covariance matrix E, define the effective dimension 22 as
l2 min 120:
E S s2dlt,, Σn: 120
(8)
1211
where 02 is a constant independent of the dimension sample size n. and time t. The term c(t, n) is function to discussed later. When the context clear, we omil its dependencies on 02 olt,n), n, n, E and only denote it by k2.
Based on the effective rank and effective dimensions defined above, we provide a time variant bound in Theorem 5. for overparameterized linear regression, which further leads to the argument in Theorem 4. Compared to the existing bound [8, Theorem 5.] focuses
focuses on investigating the role of training epoch in the excess risk, to give refined bias-variance decomposition.
Theorem 5.1 (Time Variant Bound). Suppose Assumption Given ó (0, 1), assume that kn n log 3 n.
and 3 hold. Fix function c(t, n).
Ei for large enough constant
c'
Then with probability at least 1 - 8, we have any EEN, N.
R(O.) S B(O,) + V(O.),
where
B(O.) = ||0"1|
+
|لم
max
r(E)
r(E)
log ) n
At
n
n2
1 5
hi
lo
At
VOO) = o log
+
+ cll,n)
A
c(t,n)n
72
We provide high-level intuition behind Theorem 5.1 We decompose R(O,) into the bias term and the variance term. The variance term is then split into the leading part and tailing part based on the spretrum of the feature covariance Σ. The eigenvalues in the tailing part will cause the variance term in the excess risk the min-norm interpolating solution to be (2(1) ) for fast decaying spectrum, as is the case in [8]. However, since the convergence in the tailing eigenspace is slower compared with the leading eigenspace, a proper early stopping strategy will prevent the overfitting in the tailing eigenspace and meanwhile avoid underfitting in the leading eigenspace.
The c(t, n) Principle. is worth emphasizing that our bound holds for arbitrary positive function c(t, n). Therefore, one can fine-tune the generalization bound by choosing proper c(t, n). In the subsequent sections, we show how to derive consistent risk bounds for different time i, based on different choices of nz). We present the case of choosing constant e(1, n) in the next section. We leave the case of choosing varying c(t, n) to Appendix 5.3
5.2 Varying t, Constant c(t,
Theorem 5.1 provides an excess risk upper bound uniformly for i E N. However, it is still non-trivial to derive Theorem 4.1 where the remaining question to decide the term e(t, n). The following corollary shows the generalization bound when setting c(t, n) to constant.
Corollary 5.1. Let Assumption
7 and
hold. Fix constant e(t, Suppose ko O()),
l = o(n), r(E) o(n). X
Σ Eiso Xx) Then there exists sequence of positive constants
(5n) (6n)22 which converge such that with probability least 1 5.. the excess risk is consistent fort E (w (+) .0 (())), i.e.
R(O.) = =(1).
(10)
7

---

Table 1: Comparisons of excess risk bound with Bartlett et al. [8] and Zou et al. [76]. We provide four types of feature covariance with eigenvalues 2k, including Inverse Polynomial (Ax kar
> 1), Inverse Log Polynomial (Aş- = (k=1" 3 > 1), Constant (A. = भ/. 1 S k S n lte
8 > 0), and Piecewise Constant (Aş: = if k I 8 and A = - + 1 2 k S d, where
8 = n²,, ,, = n²,0 < <rsi, 11 > 1). In light of these bounds, ours outperforms Bartlett et al. [8] in
all the cases, and outperforms Zou et al. [76] in Constant Piecewise Constant cases if and
q < min r: } We refer to Appendix B for more details.
DISTRIBUTIONS
OURS
BARTLETT ET AL.
8
ZoU ET AL. 76
INVERSE POLYNOMIAL
min a-1 -2
(())
0 n
INVERSE POLYNOMIAL.
d(1)
0 log n
Tog T2
(n-2))
o (n mint
(n=min(=:))) min
0 (n= min(e.1)
CONSTANT
O (n-min min( 1 O (n min( -iimiiitaa-ii3-- 1.2 0 min(1-ni--])
PIECEWISE CONSTANT
Furthermore, for any positive constant ö, with probability at least 8, the minimal excess risk on the training trajectory can be bounded as
max / (r(E),1)
max(k1, 1}
min R(0)) S
(1I)
Lemma 5.1 below shows that K1 o(n) always holds for fixed distribution. Therefore, combining
Corollary and the following Lemma 5.1 completes the proof of Theorem 4.1
Lemma 5.1.
For any fixed (i.e. independent of sample size n) feature covariance Σ satisfying
assumption 7 we have k2 (n(n) = o(n).
Next we apply the bound in Corollary 5.1 to several data distributions. These distributions are widely discussed in [8] 76). We also derive the existing excess risk bounds, which focus on the min-norm interpolator g and one-pass SGD iterate [76), of these distributions and compare them with our theorem. The results are summarized in Table [ which shows that the bound in Corollary [.1 outperforms previous results for general class of distributions.
Example 5.1. Under the same conditions as Theorem 5.1 let Σ denote the feature covariance matrix. We show the following examples:
1. (Inverse Polynominal). If the spectrum of E satisfies d ko for some a > 1, we derive that Ko (n), Kn = = (n²) (n²). Therefore, min, VO.) = O and min, R(O,))
0 n min .1
2. (Inverse Log-Polynominal), the spectrum of Σ satisfies d k llog (k+1) for some 1.
derive that ko θ log
h1
= log" n.). Therefore, min, V(0,) O log" n
and min, R(O.) O log"
3. (Constant). If the spectrum of Σ satisfies A = +/z: S S ++,
-, for some >> 0, we
derive that kn = 0, k 0. Therefore, min, V(O,) 0 (t) and min, R(O,) =0 (tt) Vi.
1
4. (Piecewise Constant), If the spectrum of E satisfies A 1 s k < d.
where = n., ki = n". Therefore,
d-a
8 n²,d n9.0 < r < 1,q 2 1. We derive that ko min, V(O,) = O(n"~1) and min; R(O,) = O (n min (1-r
8

---

Table 2:
The effective dimension Yn, the optimal early stopping excess risk, and the min-norm
excess risk for different feature distributions, with sample size n. = 100, p = 1000. The table shows that early stopping solutions generalize significantly better than min-norm interpolators, and reveals a positive correlation between the effective dimension ln and excess risk of early stopping solution. We calculate the 95% confidence interval for each excess risk.
DISTRIBUTIONS
k
OPTIMAL EXCESS RISK
MIN-NORM EXCESS RISK
A
n1
2.399 0.0061
24.071 + 0.2447
X
0.214 + 0l0050
43.472 + 0.6463
A
71
0.077 + 0.0005
10.401 + 0.2973
A 1lggs++1
0.697 + 0.0053
89.922 + 0.9591
log
A Tio (T+T)
0.298 0.0054
82.413 + 0.9270
log
A (1+1)
0.187 1 0.0047
38.145 1 0.5862
log
5.3 Varying i, Varying n(t,n)
Although setting e(t, r2) to a constant as in Corollary 5.1 suffices to prove Theorem 4.1 in this section we show that the choice of c(t, can be much more flexible. Specifically, we provide a concrete example and demonstrate that by setting c(t, n) to a non-constant, Theorem 5.1 can indeed produce larger compatibility regions.
Example 5.2. Under the same conditions as Theorem 5.1 let E denote the feature covariance matrix. a 2ut
If the spectrum of Σ satisfies Al= k- for some a > 1, we set c(t, n2) = 7
1
2a11
for a given
0+1 2a
S
3a+1 2a
Thenforr t = O(n"), ), we derive that V(O)) = 0 (n 2a 30+2r-1
20+1
Example 5.2 shows that by choosing c(t. n)) as a non-constant, we exploit the full power of Theo- rem 5.1 and extend the region t θ n 3
(().. In this example, Theorem 5.1 outperforms all O -type bounds, which become vacuous when = w()).
Experiments
In this section, we provide numerical studies of overparameterized linear regression problems. We consider overparameterized linear regression instances with input dimension p 1000, sample size n = -000. The features are sampled from Gaussian distribution with different covariances. The empirical results (a.) demonstrate the benefits of trajectory analysis underlying the definition of compatibility, since the optimal excess risk along the algorithm trajectory is significantly lower than that of the min-norm interpolator (b.) validate the statements in Corollary 5.1 since the optimal excess risk is lower when the eigenvalues of feature covariance decay faster. We refer to Appendix C for detailed setups, additional results and discussions.
Observation One: Early stopping solution along the training trajectory generalizes significantly better than the min-norm interpolator. We calculate the excess risk of optimal early stopping solutions and min-norm interpolators from 1000 independent trials and list the results in Table 2 The results illustrate that the early stopping solution on the algorithm trajectory enjoys much better generalization propertics. This observation corroborates the importance of data-dependent training trajectory in generalization analysis.
Observation Two: The f'steer covariance spectrum decays, the lower optimal excess risk is. also illustrates a positive correlation between the decaying rate of x; and the generalization performance of the early stopping solution. This accords with Theorem [.I] showing that the excess risk is better for smaller effective dimension k1, where small k₁ indicates a faster-decaying eigenvalue >ç We additionally note that such phenomenon also illustrates the difference between min-norm and early stopping solutions in linear regression, since Bartlett et al. [8] demonstrate that the min-norm solution not consistent when the eigenvalues decay too fast, By comparison, early stopping solutions do not suffer from this restriction.
Table also

---

7 Conclusion
In this paper, we investigate how to characterize and analyze generalization in a data-dependent and algorithm-dependenn manner. We formalize the notion of data-algorithm compatibility and study it under the regime of overparameterizee linear regression with gradient descent. Our theoretical and empirical results demonstrate that can ease the assumptions and broaden the scope of generalization by fully exploiting the data information and the algorithm information. Despite linear cases in this paper, compatibility be much more general concept. Therefore, we believe this paper will motivate more work on data-dependent trajectory analysis.
Acknowledgement
The authors would like acknowledge the support from the 2030 Innovation Megaprojects of China (Programme on New Generation Artificial Intelligence) under Grant No.
References
[1] Madhu S. Advani, Andrew M. Saxe, and Haim Sompolinsky. High-dimensional dynamics of generalization error in neural networks. Newral Networks, 132:428 446. 2020. doi: 10.1016/ neunet.2020.08.00 0.22. URL httpp::////oo.oooo 100 1016/j www.et..t...m.m 2020. 08.00...00 022
[2] Alnur Ali, J. Zico Kolter, and Ryan J. Tibshirani. A continuous-time view early stopping for least squares regression. In Kamalika Chaudhuri and Masashi Sugiyama, editors, The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, volume 89 of Proceedings of Machine Learning Research, pages 1370-1378. PMLR, 2019. URL /tt.att::/prooeeiiiie
mlr. ppwss/v89/ ali19a. html
[3] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stock- holmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 263. PMLR, 2018. v80/ 2000/rora18b... html
mlr, mlr.press/ press/
[4] Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 322-332. PMLR, 2019. URL http: arora19a.
//proceedings.nt mlr prwpp/eessspee
htress/v97//e v97 htt../pprre//////rrraaaaa. html
[5] Yingbin Bai, Erkun Yang, Bo Han, Yanhua Yang, Jiatong Li, Yinian Mao, Gang Niu, and Tongliang Liu. Understanding and improving early stopping for learning with noisy labels. CoRR, abs/2106. 15853, 2021. URL htttp: org/ hbs//ab//// abs/abbs....../ 15853
[6] Pradeep Kr. Banerjee and Guido Montúfar. Information complexity and generalization bounds. CoRR. abs/2105.01747. 2021. URL httpps::/aarii..rrg//////// httpa/bb//21111117 01747
[7] Peter L. Bartlett, Dylan J. Foster, and Matus Telgarsky.
pecetrallynnormalie mar- gin bounds for neural networks. In Isabelle Guyon, Ulrike von Luxburg, Samy Ben- gio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, edi- tors, Advances in Neural Information Processing Systems 30: Annual Conference on Neu- ral Information Processing Systems 2017, December 4.9, 2017. Long Beach, CA, USA, neur sunrips.co cc/ wwcp/pppe///a// hooper//017/hsh.
pages 6240-6249, 2017. URL 12225//a00114400033333333c
[8] Peter I.. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. CoRR, wabs/190..... 13300, 2019. htttttttp//xxx// arg/abs/1906 11300
10

---

[9] Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL /tLLhttps://proceeeee itt.eeeedinnnnnuuurppp... nww. ips ccc/paper/202//eeee
Abstract mttstraccthtml
[10) Gilles Blanchard and Nicole Krämer. Convergence rates of kernel conjugate gradient for random design regression. Analysis and Applications, 14(06):633-79,, 2016.
[11) Olivier Bousquet and André Elisseeff. Stability and generalization. J. Mach. Learn. Res., 2: 499-526, 2002.
[12] Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theooy, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria), volume 125 of Proceedings of Machine Learning Research, pages 610-626. PMLR, 2020. URL mlr.
btw../////oouuuuut..bbbb html
[13] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot Iearn- ers. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6- 12, 2020, virtual, 2020. URL httpps:/pprceeedinggg htw.eeedddinnnnn..nnss...e www.rnnrri.... cc/ 1457c0d6bf 2tbb44977788bf88c1142442225 Abstract. html
wttpsscccppppppppeeeee paper/ /tapper//22////// h
[14] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Jill Burstein, Christy Doran, and Thamar Solorio, editors, Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume I (Long and Short Popers), pages 4171- 4186. Association for Computational Linguistics, 2019. doi: 10.18653/v 1ttp//////11////11 1423. URL https://aoi.orgg www..///......//.../ www.11666/11111 14233
[15] Aymeric Dieuleveut and Francis Bach. Nonparametric stochastic approximation with large step-sizes. The Annals of Statistics, 44(4):1363-1399, 2016.
[16] Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Gal Elidan, Kristian Kersting, and Alexander T. Ihler, editors, Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence, UAI 2017, Sydney, Australia, August 11-15. 2017. AUAI Press, 2017. URL http: /ttt::///aai... httgg//aa22////rrrceenn///////// pdf
[17] Melikasadat Emami, Mojtaba Sahrace-Ardakan Parthe Pandit, Sundeep Rangan, and Alyson K. Fletcher. Generalization error of generalized linear models in high dimensions. In Proceedings of the 37th International Conference on Machine Learning. ICML 2020, 13-18 July 2020, Virtual Event, volume 1 19 of Proceedings of Machine Learning Research, pages 2892 2901. PMLR, 2020. URL http://///ceceeeiiin
mlr. presss/vils emami 20a html
[18] Vitaly Feldman and Jan Vondrák. Generalization bounds for uniformly stable algorithms. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Bisach,, and Roman Garnett, editors, Advances in Neural Information Processing Systems
31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 9770-9780, 2018. URI /tt/ peroceedinggsneeripp neurips ccc/paprr/ htlo/////////2226666600000000060 http////eoeeeoeooooooaodoooeaaa. Abstract.htm

---

[19] Vitaly Feldman and Jan Vondrák. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Alina Beygelzimer and Daniel Hsu, editors. Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, A7, USA, vol- ume 99 of Proceedings of Machine Learning Research, pages 1270-1279. PMLR, 2019. URL.
mlr. press/ v99/ dmlnm1199. 1mmmm9....11111111..... html
[20] Mahsa Forouzesh and Patrick Thiran. Disparity between batches as signal for early stopping. In Nuria Oliver, Fernando Pérez-Crus Stefan Kramer, Jesse Read, and José Antonio Lozano, editors, Machine Learning and Knowledge Discovery in Databases. Research Track European Conference, ECML. PKDD 2021, Bilbao, Spain, September 13-17, 2021, Proceedings, Part II, volume 12976 of Lecture Notes in Computer Science, pages 217-232. Springer, 2021. doi: 10. 830-000-77
0007/978-3-030-862222 14
14. URL https: htmps://doi... org/
[21] Spencer Frei, Niladri Chatterji, and Peter L. Bartlett. Benign overfitting without linearity: Neu- ral network classifiers trained by gradient descent for noisy linear data. CoRR, abs/2202.05928, 2022. StRLhhttss://// http:///axwww.oo//bb/eeeee tergg/abs/22005 059288
[22] L.. Lo Gerfo, Lorenzo Rosasco, Francesca Odone, Ernesto De Vito, and Alessandro Verri. Spectral algorithms for supervised learning. Neural Comput., 20(7):1833-8977 2008. doi: (0.11622nec..200.00555 2008.05-77777.. URL URL httpps//ddii..... otg/10...0011..0 (0162//eco.oo 2008. 000008.05-77-00 05-07-517
[23] Sebastian Goldt, Madhu Advani, Andrew M. Saxe, Florent Krzakala, and Lenka Zde- borová. Dynamies of stochastic gradient descent for two-layer neural networks in the teacher-student setup. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buuc, Emily B. Fox, and Roman Garnett, editors, Advances Neu- ral Information Processing Systems 32: Annual Conference Neural Information Pro- cessing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada. pages 6979-6989 2019, URL https: httpt:://tposeeeeee http:///pcceeeen..////// neur www.uris..ccppppppeeeee wttpsccc/papee/1///aaaaaaaa ceb07055bb0022074418882228688832 htw.:9220004--batttttttttt.. bbbstract.hmml
[24] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochas- tic gradient descent. In Maria-Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 1225- 1234. JMLR.or. org. 2016. URLhttp:: httt:::/pproceedinnneeeeooee/eee mlr www.eeewesseeeeeeeeeeeee http://///aaaa.t.... html
[25] Wei Hu, Lechao Xiao, Ben Adlam, and Jeffrey Pennington. The surprising simplicity of the early- time learning dynamics of neural networks. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tice Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information P Processing Systems 2020, NeurlPs 2020, December 6-12, 2020, virtual, 2020. URL WtLLhtttss//prrceediii www.wiinnnn.n.nnnnnooeeee.e.eeee neurips cc sc/paper/2020. http:///////hhh///eeeeaa c&df c6b7
hww. html
[26] Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Conver- gence and generalization in neural networks. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa- Desa-Bianchi, and Roman Garnett, editors, Advances in Neural Information P Processing Systems 31: Annual Conference tion Processing Systems 2018 NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 8580-8589, 2018. URL htttps://proceedinggs nww.inerri.... cet.iiissccpaaaaaeea http:pps.ccppapp///ae httpp/appp/////a////// Becbelf224e62bBBeeeccbb111222222 Saaageaaaee.ra222222eeeeeaaaarrr Abstract.
Neural Informa-
[27] Ziwei Ji, Justin D. Li, and Matus Telgarsky. Early-stopped neural networks are consistent. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wort- man Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Confer- ence on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 1805-1817, 2021. URL httptp:://ppccceiinggg. www.nneuuuucccm cttpippsscc/pppper/22//// Saaal//eleeaassssaf000e000000//0 wtwp:s/bbbccc---tatattt...cc...t Abstract.hta. html
[28) Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
URL httpss://pppeereviiee wttp://wwww..etttorrriiddddeeeee
12

---

[29] Vladimir Koltchinskii and Dmitriy Panchenko. Rademacher processes and bounding the risk of function learning. In High dimensional probability I1, pages 443-457. Springer, 2000.
[30] Ilja Kuzborskij and Csaba Szepesvári. Nonparametric regression with shallow overparame- terized neural networks trained by GD with early stopping. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 Augusi 202 I, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 2853-2890. PMLR, 2021. wtt.lhttpp//prrceediin ianggssmml..... mlr. Btteess/v33///uuuuuu j21a 21m.ltmlll
[31] Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 5809-5819. PMLR, 2020. URL http::/ppocceeeiiiiieee mlr. press/v119/ lei20c. html
[32] Jian Li, Xuanyuan Luo, and Mingda Qiao. On generalization error bounds of noisy gradient methods for non-convex learning. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URRLhttpp
7 //openreview
[33] Jianguua Li, Thanh V. Nguyen, Chinmay Hegde, and Ka Wai Wong. Implicit sparse regularization: The impact of depth and early stopping. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Anmual Conference on Neu- ral Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 28298-28309, 2021. URL
neur wttpccpppppp.////////p//
ee 11111444000001eeeee0060000662220
[34] Mingehen Li, Mahdi Soltanolkotabi, and Samet Oymak. Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks. In Silvia Chiappa and Roberto Calandra, editors, The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pages 1313-43324 PMLR, 2020. URL httpp://proceedings. mlr wwwps//vve/e//e.eee
html
[35] Zhu Li, Weijie Su, and Dino Sejdinovic. Benign overfitting and noisy features. CoRR, abs/2008.02901, 2020.
[36] Junhong Lin and Volkan Cevher. Optimal rates for reguaral algorithms with least- squares regression over hilbert spaces. CoRR, abs/1801.06720, 2018. URL /ttt:////arx
brg/abs:/8001.067
[37] Junhong Lin and Lorenzo Rosasco, Optimal rates for multi-pass stochastic gradient methods http://aww..rrppppppee/////////1
J. Mach. Learn. Res., 18:97:1-97:47, 2017.
html
[38] Chaoyue Liu, Amirhesam Abedsoltan, and Mikhail Belkin. On emergence of clean-priority learning in early stopped neural networks. CoRR, 0aw/2336.025333 2023, doi: 10.48550/arXiv. 2306.02533. URL https://dot.ii.. org/ooo.///o 101.11..00500011111 2306. .25333
[39] Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL httpss///pperrevier
het/forum?id-33 SJLLIIBKKSSSSSSPS
[40] Kaifeng Lyu, Zhiyuan Li, Runzhe Wang, and Sanjeev Arora. Gradient descent on two- layer nets: Margin maximization and simplicity bias. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neu- ral Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 12978 129911 2021. URL URL httpl:: httopp:://rrooeediggss wwweeediinnn.n.uuiiinn heurips.. httpp..ccppppee ctcc/apper/2221///ae/ 0c255aa11bb6633774442eee98888833 Abstratt.tttaaatttttam
13

---

[41] Neil Mallinar, James B. Simon, Amirhesam Abedsoltan, Parthe Pandit, Misha Belkin, and Preetum Nakkiran. Benign. tempered. or catastrophic: Toward refined taxonomy of over- fitting. In NewrlPS, 2022. URL http://papers. www.: wwpppppr.pppppppptppptppppee.... Filee/paperr2000
02000002222222223777222222222222 -atp://ddddeedeettttttooooooeeee Conferenc .html
[42] David A. McAllester. Simplified pac-bayesian margin bounds. In Bernhard Schölkopf and Manfred K. Warmuth, editors, Computational Learning Theory and Kernel Machines, 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop. COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings, volume 2777 of Lecture Notes in Computer Science, pages 203 215. Springer. 2003, doi: 10. 00.1007/978-3-540-451111
[43] David A. McAllester. A pac-bayesian tutorial with A dropout bound. CoRR, abs//307..0 307.2017181 2013. URL
22188
[44] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. Adaptive computation and machine learning. MIT Press, 2012. ISBN 978-0-262-01827 812--88. URL http://mitpress mit. ett.bbooss/fouunaatioon---aeeeee hag.radttttooommccccceeeaaaaaaan
[45] Wenlong Mou, Liwei Wang. Xiyu Zhai, and Kai Zheng. Generalization bounds of SGLD for non-convex learning: Two theoretical viewpoints. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, volume 75 of Proceedings of Machine Learning Research, pages 605-638. PMLR, 2018. hRtp |ttpptt: http::///ccceeenss./mmmm ......m.l... mlr wwwppprasssvv wttps/////mmmmmuumemmmmmm html
[46] Vaishnavh Nagarajan and J. Zico Kolter. Uniform convergence may be unable to explain generalization in deep learning. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelz- imer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neu- ral Information Processing Systems 32: Annual Conference on Neural Information Pro- cessing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 11611-11622, 2019. URL https http:::://proceddnngg weweeedddinnnnnnriiiseeeee meuripp.cc../ wwtpccpppppppcetecccccccceeeee Shaper/2019/hass 01699772772333333bbbb44446666663
[47] Jeffrey Negrea, Gintare Karolina Dziugaite, and Daniel Roy. In defense of uniform convergence: Generalization via derandomization with an application to interpolating predictors. In Proceed- ings of the 37th International Conference on Machine Learning. ICML 2020. 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 7263-7272 PMLR, 2020. URL htt.:ttt///occcednnggg mlr prress/v119/eegreaalle html
[48] Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally margin bounds for neural networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL forum?id Skz__K__i WFbCZ
net/
[49] Emilio
Amiran Ambroladze, John Shawe-Taylor, and Shiliang Sun. Pac- bayes bounds with data dependent priors. Mach. Learn. Res., 13:3507-3531, 2012. URL h/dl: acm. org/ citation. cfm?id=2200335
[50] María Pérez-Ortiz, Omar Rivasplata, John Shawe-Taylor, and Csaba Szepesvári. Tighter risk certificates for neural networks. J. Mach. Learn. Res., 22:227:1-227:44 2021. URL
http://jmlr... hwwps/rrrppppppppppeeeeee wwwpps//v2/2200000pppppppp htmll
[51] Loucas Pillaud- Hillaud-Vivien, Alessandro Rudi, and Francis R. Bach. Statistical optimality of stochas- tic gradient descent on hard learning problems through multiple passes. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi. and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 81 8125- 81 135, 2018. htt.a//....ttttttppp/eeeeeeeeeee htas://fffo0ess0BBocc00ss333331- wwtpsatttttttttttttttaatt
14

---

[52] Lutz Prechelt. Early stopping but when? In Grégoire Montavon, Genevieve B. Orr, and Claus-Robert Müller, editors, Neural Networks: Tricks of the Trade Second Edition, volume 7700 of Lecture Notes in Computer Science, pages 53-67. Springer, 2012. doi: 10. 10.1007/ 978-3-642-35288-881
TTR.hhttps://doi..om org/ 10. 1007 1007 000000099777-300 642- -004222-528---- 30289-228888 8__
[53] Garvesh Raskutti, Martin Wainwright, and Bin Yu. Early stopping and non-parametric regression: an optimal data-dependent stopping rule. J. Mach. Learn Res., 15(1):335-366.
2014, doi: 01555/2262743526674442 URLhttps://dd acm. org wttg//oi/10..a00 005.0///110.555555277555533
2627446
[54] Omar Rivasplata, Ilja Kuzborskij, Csaba Szepesvári, and John Shawe-Taylor, Pac-bayes analysis beyond the usual bounds. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria- Florina Balcan, and Hswan- -sea Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL https: http://e////cccc.s.eeeoo neur iaarrips.ooo cc/ 2020/ /t/////hhh/////////////a//aaaaa/ http0////aa/c/2222222222333 1199922998Bc55ae221111aaaa
paper/ pappr/2020/eai
htw.://99bbbo--bbbtttttt.t... Abstract.
[55] Lorenzo Rosasco and Silvia Villa. Learning with incremental iterative regularization. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec. Canada. pages 1630-1638 2015. URL htttpp:://proceednngg www.oedddinnnnnneuipipeee cerrrisscccpppeee wttpcc/cppppcc.... http:/apppppp/aaaapeee (B
Aobstract.htma
[56] Daniel Russo and James Zou. Controlling bias in adaptive data analysis using information theory. In Arthur Gretton and Christian C. Robert, editors, Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, AISTATS 2016, Cadiz, Spain, May 9- 1-11, 2016, volume 51 JMLR Workshop and Conference Proceedings, pages 2232-1240. JMLR.org, 2016. WRRLhtt::/prrceediiee
mlr press/v51/rusoo// httmllll6m...mm.11
[57] Mojtaba Sahraee-Ardakan, Melikasadat Emami, Parthe Pandit, Sundeep Rangan, and Alyson K. Fletcher. Kernel methods and multi-layer perceptrons learn linear models in high dimensions. CoRR, Abs/2201.08082 2022. URL httts://aaxiv..rrg/ ht////b//2200// 08082
[58] Matthias W. Seeger. bayesaa generalisation error bounds for gaussian process classification. 2002. URL htt.::ttp//// //tr/////rr.////// org/ wwwgg/aaprs//eeee v3/ seegee20
J. Mach. Learn. Res., html
[59] Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateck Jain, and Praneeth Netrapalli. The pitfalls of simplicity bias in neural networks. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Aisuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL httpst / neur ips www.:s1ss---ttttttttt.aaa...
cc/paper/ 20200///2220//
[60] Vaishaal Shankar, Rebecca Roelofs, Horia Mania, Alex Fang, Benjamin Recht, and Ludwig Schmidt. Evaluating machine accuracy on imagenet. In Proceedings of the 37th International Conference Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 8634-8644. PMLR, 2020. URL html
//proceedings.nit mlr. prwspppessse........
[61] John Shawe-Taylor and Robert C. Williamson. A PAC analysis of a bayesian estimator. In Yoav Freund and Robert E. Schapire, editors, Proceedings of the Tenth Annual Conference on Computational Learning Theory, COLT 1997, Nashville, Tennessee, USA, July 6-9, 1997, pages 1145/26745655
2 2-9. ACM, 1997. doi: 10. 00.1145/264460.274666 URL httptt:///ii..ooo
267466
[62] Ruoqi Shen, Liyao Gao, and Yi-An Ma. On optimal early stopping: Over-informative versus under-informative parametrization. CoRR, abs/2202.09888, 2022. Jttp:pttts///rriv..rr abs/ 0bs/2200.rm 09885
15

---

[63] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy P. Lillicrap. Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game of go without human knowledge. Nat. 350 359, 2017. doi: 10. 10.1038/nature242700 URLhttps:: htttps://doi http:://dooooo///////ee 10. 1038/ n22
[64] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, and Nathan Srebro. The implicit bias of gradient descent on separable data. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3. 2018, Conference Track Proceedings. OpenReview.net, 2018. URL httts::/
net/ http:/ooormmidddd net//forummiddr117nsgsg.
[65] Pierre Stock and Moustapha Cissé. Convnets and imagenet beyond accuracy: Understanding mistakes and uncovering biases. In Vittorio Ferrari, Martial Hebert, Cristian Sminchisescu, and Yair Weiss, editors, Computer Vision ECCV 2018 15th European Conference, Munich, Germany, September 8- 14. 2018, Proceedings, Part VI, volume 11210 of Lecture Notes in Springer, 2018. doi: 10. 01177978---030-012555
Computer Science, pages https://doi. org wttgg//..100//90001 1007
URL
[66] Pierre Tarres and Yuan Yao. Online learning as stochastic approximation of regularization paths: Optimality and almost-sure convergence. IEEE Trans. Inf. Theory, 60(9):5716-5735 2014. doi: 10. 1 10.11000/11222112333555
https://///dol org/ 10. 1119////IIT 2014. 2332531
[67] Jiaye Teng, Jianhao Ma, and Yang Yuan. Towards understanding genariiizaannnnnnniiiiiiiiooo via decomposing excess risk dynamics. CoRR, abs/2106.06153. 2021. URL htt.tsss//aaxii.orr/aaassss/// 06153
[68] Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. arXiv preprint arXiv:2009. 14286 2020.
[69] Tomas Vaskevicius, Varun Kanade, and Patrick Rebeschini. The statistical complexity of early- stopped mirror descent. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL https: htttt::://ppoceeeingg neurips. wttpp/ccccpppppep/ecceeeeee /00/ppr//000//ah//
02442669966-112229888866668688 htt.ca/bbboooooooo222a22aaaaaa.. Abstract.htmm html
[70] Ke Wang and Christos Thrampoulidis. Benign overfitting binary classification of gaussian mixtures. In IEEE International Conference Acousties, Speech and Signal Processing, ICASSP 2021, Toronto, ON. Canada, June 6-11, 2021, pages 4030-4034 IEEE, 2021. doi:
10.10091CASS$3337222222 24999999999. URL https: org/ 10. 1109/ ICASSP39728 0021.9413945
[71] Aolin Xu and Maxim Raginsky. Information-theerrtic analysis of generalization capa- bility of learning algorithms. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Sysiems 30: Annual Conference on Neu- ral Information Processing Systems 2017, December 4-9, 2017. Long Beach, CA. USA, pages
2017. URL https: httpt: httpps:/pproceeeingg.... neurips cc/ ctt.cc//ppppp..... httpp/pppp/////aaae/eee 2007/hash/ a171:202244465598776666666633 wtt.siis--ssstttt...o html
[72] Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On early stopping in gradient descent learning, Constructive Approximation, 26(2):289-315, 2007.
[73] Sangdoo Yun, Seong Joon Oh, Byeongho Heo, Dongyoon Han, Junsuk Choe, and Sanghyuk
Chun. Re-labeling imagenet: From single to multi-labels, from global to localized labels.
In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19-25, 2021, pages 2340-2350. Computer Vision Foundation IEEE, 2021. URL https:/ htttps:/oppeacceess theeeessstteeeeeeeeeee thecvf. http:////////ttee/////////////// Betei/YYnnneeeeeeee Labelll-eLbblllllee ing-
SaageNNe__Fromt Single_ to Multi Labells- From Franhlsaaro____ooab_a to Lo__liiieeed CVPR.
html
16

---

[74] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Commun. ACM, 64(3).17-115,, 2021. doi: 10.1 10.1145/3446776.
httpps//o// org/ org/...gg/1... 10. 6446/344776
[75] Lijia Zhou, Danica J. Sutherland, and Nati Srebro. On uniform convergence and low-norm interpolation learning. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florima Balcan, and Hsuan-Tier Lin, editors, Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL httls: httppp:: neurips. weerips.cc/pappe.... wwtpccpppppppp/o/e/// (aapgerr/20//haahh
[76] Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham M. Kakade. Benign overfitting of constant-stepsize SGD for linear regression. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021. Boulder, Colorado, USA. volume 134 of Proceedings of Machine Learning Research, pages 4633-4635. PMLR, 2021. URL http: mlr htt.://ssw...pperreeeeeeeee aTees/v134/zou22/1 html
[77] Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham M. Kakade. Risk bounds of multi-pass SGD for least squares in the interpolation regime. In NeurlPS, 2022. URL http::/papprrre nips. cc/ wwwppppr.ppp../ fil.s/le///// 2ttp:/flleeepppe2/22/////////// pttpppp//22///aaa 549222..22201000112f184440000 Abstract Conference.hrr 
17

---

Supplementary Materials
A Proofs for the Main Results
We first sketch the proof in section A.1 and give some preliminary lemmas A.2 The following
sections A.3 A.4 and A.3 given in
devoted to the proof of Theorem 5.1 The proof of Theorem 4.1
A.6
A.1
Proof Sketch
We start with standard bias-variance decomposition following Bartlett et al. (8) which derives that the time-variant excess risk R(O;) can be bounded by a bias term and variance term. We refer to Appendix A.3 for more details.
For the bias part, we first decompose into an optimization error and an approximation error. For the optimization error,
the spectrum analysis to bound it with O (1/t) where denotes the time. For the approximation error, we bound with O (1/ /n)) where n denotes the sample size, inspired by Bartlett et al. [8] We refer to Appendix A.4 more details.
For the variance part, key step is to bound the term (I - A where X is the feature matrix. The difficulty arises from the different scales of the eigenvalues of X where the largest eigenvalue has order (n) while the smallest eigenvalue has order O(1), according to Lemma 10 in Bartlett al. (8. To overcome this issue. we divide the matrix X X based on whether its eigenvalues is larger than c(t, n), which is flexible term dependent on time t and sample size Therefore, we split the variance term based on eigenvalues covariance matrix E (leading to the ky-related term) and based on the eigenvalues of X X (leading to the ly-rellted term). We refer to Appendix A.5 for more details.
A.2 Preliminaries
The following result comes from Bartlett et al. [8 which bounds the eigenvalues of XXT.
Lemma A.1. (Lemma 10 in Bartlett al. 181) For any Ta, there exists constant such that for any < ls < n, with probability at least -
Σ X + Au+in ii
Pk+1 Sc
(12)
This implies that as long as the step size À is small than a threshold independent of sample size n, gradient descent is stable.
Corollary A.1. There exists constant c, such that with probability at least e 2, for any 0 < X < T. we have
A
0
(13)
Proof. The right hand side of the inequality is obvious since À >> For the left hand side, we have to show that the eigenvalues of I À X is non-negative. since X X and X have the same non-zero eigenvalues, we know that with probability at least - e ž, the smallest eigenvalue of 2 X can be lower bounded by
A ad
(Eiz di + Ak+1 21 2cd Σ A
1 #1 2 1
(14)
1>0
where the second inequality uses lemma A.1 and the last inequality holds A
2c 21c
18

---

A.3 Proof for the Bias- Variance Decomposition
Let X denote the Moore Penrose pseudoinverse of matrix X. The following lemma gives a closed form expression for O,.
Lemma A.2. The dynamics of {0r)c20 satisfies
0: (1
x x) (00- (00- + x
(15)
Proof. We prove the lemma using induction. The equality holds at = 0 as both sides are Og. Recall that O2 is updated as
Oz+1 = 02 + - (Y X
(16)
n
Suppose that the dynamic holds up to the t-th step. Plug the expression for 6, into the above recursion and note that X X
X
get
Oc+1 =
1
X T X
Or + - -
1+1
(Oo x + (1 (1- xty x
>
X X
(17)
n
n
1+1
I
x
(0o xix)+
which finishes the proof.
Next we prove two identities which will be used further proof.
Lemma A.3. The following two identities hold for any matrix X and non con-negative integer t:
I- + (I- xtx = (1-2XTx)
(18)
I 2 n
xixx
x I (
(1-
(19)
n
Proof. Note that X xxt= = XT, we can expand the left hand side of the first identity above using binomial theorem and eliminate the pseudo-inverse X
X-X
+ (1 x-=xTx) xlx
I
= =I x +
x x xtx
k=0
A
= =I X +
X
X
(20)
k
n
A=1
I
(xT x)
k
(1 -1- x x x
19

---

The second identity can be proved in similar way:
I - I - A x XiXX
A xxxx) x)
Xixxi
k)
Σ
A
(x x
n
(21)
Σ
(1)
A
(x xx x Xx"
n
Σ
XT(XT1)
n
k=1
>
xxxx]
x
n
We are now ready to prove the main result of this section.
Lemma A.4. The excess risk at the t-th epoch can be upper bounded as
R(O,) < 0" BO + CCE,
(22)
where
I- - -x_xxxx xxT)²²
X
B
x X
E
(23)
ni
n
(
C=
( n
(1-1--xxx)
X
I I- n
(1--xxxx)] (XXT)=
(24)
which churacterizes bias term and variance term in the excess risk. Furthermore, there exists constant such that with probubility at least - 8 over the randomness of we have
1 E cC S Co log g Tr[C].
(25)
Proof. First note that XX is invertible by Assumption Express the excess risk as follows
R(O,) El(y x TT 0.)² (y -x =T
E((y x T 0 0r x TT))2
(y x )
(26)
E((x T(O, 0²))² + 2(y x (x) T 0 x 0,]
2
E(x T (0, 2²
2
Recall that 0. and Y X0 + E and we can further simplify the formula for 0, in lemma A.2
0, - > xxxx) (0o xtt)
(27)
I (I- m x=2xxxx] x x'(X0' +e).
20

---

Plug it into the above expression for R(O,), we have
2
R(O,))
( x
- 1
x
x' + +6)- -0)=x000
x1x (1-2xTx)
R
xr T
X
0r
(28)
2
n
?
A xxxx) x
+
I
-
Applying lemma
A.3 we obtain
2
I (1-2xx:)]xxxx)
R(O,)
E
x
xTxx
x
x
0"
+ + X
2
n
2
x xx )
2
S E
T
x
x
0¹
+ E
C T X
I -
I-
0" B0" T Ce.
(29)
which proves the first claim the lemma. The second part of the theorem directly follows from lemma 18 in Bartlett et al. 8
A.4 Proof for the Bias Upper Bound
The next lemma guarantees that the sample covariace matrix J X X concentrates well around Σ.
Lemma A.S. (Lemma 35 in Bartlett et al. (8]) There exists constant such that for any 0 < ó < 1 with probability as least 1 8,
(E)
r(E)
log(
log(
Σ
X n
X
Sc
max
(30)
The following inequality will be useful in our proof to characterize the decaying rate of the bias term with t. Lemma A.6. For any positive semidefinite matrix P which satisfies Pl| S 1, we have
P(1 - PY t
(31)
Proof. Assume without loss of generality that P is diagonal. Then it suffices to consider seperately each eigenvalue of P. and show that a o) s
In fact, by AM-GM inequality we have
to (1 o)t a (1-o)'s S
(32)
1+1
which completes the proof.
Next we prove the main result of this section.
Lemma A.7. There exists constant such that if0 S X
EEioo xo then for any 8 with
probability at least - 8 the following bound the bias term holds for any t
1)
[(E)
r Σ
log(
log
T. B0 < <c|10'12
+
Σ
max
(33)
At
71
71
77
72
21

---

Proof. The bias can be decomposed into the following two terms
-- B0 = TT ( (I-XXXx)
x
xx- x
- xx-xXX
2 x x
0r
n2
n
n
(34)
00 n1 (=xTx) x)
(I-2xTx)
21
0"
For sufficiently small learning rate X as given by corollary A.1
we know that with high probability
x
x
1,
(35)
which together with lemma
A.5 gives high probability bound the first term:
T-T
x
Σ
1
x
x
x
0
n
(36)
r r(E)
r(E)
log(A)
log(A) !))
< c | 10
max
n
For the second term, invoke lemma
A.6 with P = 2 X
X and we get
0- 1 (=xTx) x)
(I (1-20 A 2
x
0"
< x
10013
x
x)
(1 (1-XXTx)
)1
21
72
n
n
(37)
1
|0
2
Putting these two bounds together gives the proof for the main theorem.
A.5 Proof for the Variance Upper Bound
Recall that X UUAWT is the singular value decomposition of data matrix X, where U (u..... un), W (wi,... ... wn). A diag(Hi, , with μr 2 μ2 2 un.
Recall that
Co Ei>i A
ko min(1 2 0: A141
n C1 Ei>o )
k min(1 2 0: A141 S
(38)
n
22 min 2 0: Σ \ + nd441 S c2c(t,n) Exil
for some constant co, c1, 02 and function c(t,n).
We further define
kg = min(l 2 0: p41 S cse(t,n) Enih.
(39)
2
for some constant C3.
The next lemma shows that we can appropriately choose constants to ensure that ka < ko holds with high probability, and in some specific cases we have k2 S ki.
Lemma A.8. For any function c(t, n) and constant C22 there exists constants c, Ca. such that lis S 12 with probability at least = -. Furthermore, if elt, n) is a positive constant function, for any ey. there exists e2 such that ko < k1.
22

---

Proof. According to lemma A.1 there exists a constant c, with probability at least c- 2
we have
Mlat1 S el
X + ndbg+1) S cc2oll,n)
Σ A
(40)
t>k2
$50
Therefore, we know that ka S 22 for 0g 002.
By the definition of ,i, we have
Σ 12
+ S (cr + 1)
Σ X
(41)
1200
which implies that 2/ S k1 for 02
gr1 a(tm)]
if c(t, nt) is positive constant.
Next we bound Tr[C], which implies upper bound on the variance term.
Theorem A.1. There exist constants c, co, C12 C2 such that if ko =" then with probability at least
1 e 2, the trace of the variance matrix C has the following upper bound for any l:
k1 + n
l2
Tr|C] Se
cll,n)
A/
(42)
ct,n))
72
8>0
Proof. We divide the eigenvalues of XXT into two groups based on whether they are greater than czc(1, n) Eivo As. The first group consists of μi ... pkgs and the second group consists of Mka-1" 4/.. For 1 S j S l:g, we have
1 --(1-111)
(4) 1
(43)
Therefore have the following upper bound
I- ---1-xXXX0
> A xxx )
n
1- 11(11 2 mi )
A
pnn T
Udiag
UT
n- ky times
ky times
2
2
1 (1
X
< Udiag
Mka+1
1
pn
UT
n
n
(44)
kg times
n n- times
-ddia
UT
n bg times
ky times
)
[1-(1-)
[
+ Udiag
O..... 0,
Mkg++
11-1-
Mn
UT.
n2
For positive semidefinite matrices P,Q, R which satisfies Q A R, holds that Tr(PQ] S TT(PPR] It implies the following upperbound of Tr[C]:
23

---

Tr(C]
11- xxx )p (XXT) ( XEX
1 n
Tr
I
n
kg n
U (XX])= -2 XEX
Tr
Udiag
1,... 1, 0, 0.. 0
12- times
Ry times
Th Udiag
0....0. 0,
- (1
A
Mkg+1
A 1 km 71
U (XXT) -2
XEX
n
(45)
Bounding !
Noticing X WA and = Eisr Ao we express the first term as sums of eigenvector
products,
kg times
ki times
1 = =Tr Udiag
0,
U (XXX XEXT
ky times
n ka times
Tr
Udiag
I 0, 0..
U
T
kg limes
bi times
Tr
diag
1,... 1 0, ...
n-' EW
(46)
Ra times
times
Σ X; Tr
diag
1,.., 0, .....0 0
A A-
W 0,0 W
i21
Xi (o. w,)
Σ
My
21
ISJcks
Next we divide the above summation into
< í < hn and i >> h1 For the first part, notice that
Σ
<
A
(v. w))
M
Mj
15y5ka
ISjS
Σ
1
w.
15j5n H4
(47)
v; = io,,
A UÁ
U
Xxx (XX -22,,
where é; is defined á, X Vx.
UAEWT m. Vx.
From the proof of lemma 11 in Bartlett al. 8 we know that for any das there exists constant co and such that if ko
n with probability at least 1 e the first part can be bounded as
24

---

(v)
Σ ISish
Xxx
)
B0; S cc-
k1
(48)
ISIS ISisky Pj
which gives bound for the first part.
For the second part we interchange the order of summation and have
Σ Σ 12 15 14
w)) (0)
Σ
(0, w.y) ?
MJ
18/5kg
12
Σ
Ao w);
cjclt, n)
iis d
15 sijsk 12
Akit1
Σ
Σ
(0g w))²
caclt, m))
Σiso A,
IsiSks 12
(49)
Akit1
Σ
czelt, n)) Eiso>e A
15.5ka
Akytiks
cyclt, n) Σiso A,
K3
c(l,n))
for large enough.
Putting 48 and together, and noting that k3 I l2 with high probability as given in lemma A.8 we know there exists constant e that with probability at least 1 e- #,
h i
1a
+
(50)
n
n)t
Bounding 2
Similar to the first step in bounding !, we note that
12 kg times
times
2
A
2 = 'T
U Udiag
0, 0....0.. 0,
1 -
1
1
UÁ -
UA U EEWAUU
Ky times
1 - (1
A
(1
A
Tr diag 0.... 0.
Mkg+1
1 -
Mn
Mkat1
pnn
W T SW].
(51)
From Bernoulli's inequality and the definition of kis for any K3 +
S S n, have
1
1
1
X
1
(>
2
At
2
14
S
c3
At
dt, n)
Σ Aa
(52)
Pk
n
f4k
n2
12
m
Hence,
25

---

At
2 S cz)(l,n)
A
WW]
1>0
(53)
c3c(t,n)
A
Σ 1>0
A
Putting things together
From the bounds for ! and 2 given above, we know that there exists a constant such that with probability least 1 the trace of the variance matrix C' has the following upper bound
hi + n
22 dtt
A
Tr c
+ +ct,, n)
Σ A
(54)
130
Lemma A.4 A.7 and Theorem A.1 gives the complete proof. Note that the high probability events in the proof are independent of the epoch number t, and this implies that the theorem holds uniformly for all E
Proof of theorem 5.7
A.6 Proof of Compatibility Results
Corollary A.2 (Corollary 5.1 restated). Let Assumption 7 and hold. Fix a constant c(t, n). Suppose ko (n), & = o(n), r(2) = o(n). X ==
Then there exists a sequence of positive constants { which converge such that with probability at least 6r, the excess risk is consistent for t (w (t) o ()) i.e.
R(O:) o(1).
Furthermore, for any positive constant 6, with probability at least 5, the minimal excess risk on the training trajectory can be bounded as
max Vr(E),1) max (ki,
min R(O,,) S c
Vn
Proof. According Lemma all t:
A.7
with probability least 1
fu the following inequality holds for
1
r(E)
r(2)
log( o.
log( 5..
B(O.) x
+
max
(55)
X
If 8n is chosen such that log on
(n)), we have that with probability least 1
3.
have for all
1 -= w (t):
B(O,) = o(1),
(56)
in the sample size
When ctt, n) is constant, we have 12 ki with high probability as given lemma A.8 Therefore,
according to Lemma A.4 A.4land and Theorem A.1 we know that if log O(n), with probability at least
1 - 2.
6n. the following bound holds for all
hi
X222
V(O,) & log
(57)
5,
n²
Since hn = o(n), o (#), we have
+ 221²
o1). Therefore, there exists mildly decaying
sequence 6n with log (.))
+
o(1), i.c.
V(O)) o(L).
(58)
26

---

To conclude, o, can be chosen such that
log (.)) 5m
( =
1
lo)
(m)), [In),log
0
(59)
8n
x222
n
and then with probability at least
6n the excess risk consistent for all i E (+) (
R (.)) + V o(1)
(60)
This completes the proof for the first claim. The second claim follows from Equation 53 and 57 by setting = + Vn
Lemma A.9 (Lemma 5.1 restated). For any fixed (i.e. independent of sample size n) feature covariance E satisfying assumption we have ki (n) o(n).
Proof. Suppose there exists constant c, such that h (n) 2 en. By definition of k1, we know that A 61 Eiso A holds for s S kn (n). Hence have
Len2i+1
Ci Eiso X
A 2 n2
cn2 2 Σ A.
(61)
I= len2
|+1
1>0
summing up all / leads to contradiction since Σi>o 0o, which finishes the proof.
Theorem A.2 (Theorem 4.1 restated). Consider the overparameterized linear regression setting
defined in section 4.1 Let Assumption 72 and hold. Assume the learning rate satisfies
O Ti(E))
If the covariance satisfies kn = o(n), REg = w(n), r(E) o(n), is compatible with the region T, = (w (+) o0).
If the covariance satisfies kn = 0n))k = o(n), r(2) = o(n), it is compatible with the region T,, = (w oo (:)).
If the covariance does change with n, and satisfies ko O(n) and co, it is compatible with the region Tn (w (+) (5)).
Proof. For the first argument, notice that (a) the bias term still be bounded when t w(1) and r(E) = o(n), according to Lemma A.4, (b) the variance term can be bounded with - oo (that is, the variance loss would increase with time t). Therefore, the first argument directly follows Theorem 4 in Bartlett et al. [
The second argument follows Corollary 5.1 and the third argument follows Corollary 5.1 and Lemma 5.1 Specifically, for any e > 0, there exists {6n Inso and N such that for any sample size N. we have
Pr sup R(O,) > S >
(62)
IET.
Let + shows that supter, R(O,)) converges to 0 in probability, which completes the proof for the second and the third claim.
B Comparisons and Discussions
In this section, provide additional discussions and calculations for the main results, and compare it with previous works, including benign overfitting (Section B.T). stability-based bounds (Section B.2 uniform convergence (Section B.3) and carly-stopping bounds (Section B.4).
27

---

B.1 Comparisons with Benign Overfitting
We summarize the results in Bartlett et al. [8 Zou et al. 76 and our results in Table | and provide a detailed comparison with them below.
Comparison to Bartlett al. []. In this seminal work, the authors study the excess risk of the min-norm interpolator. As discussed before, gradient descent converges to the min-norm interpolator in the overparameterized linear regression setting. One of the main results in Bartlett al. 8 is to provide a tight bound for the variance part in excess risk as
V(O): = 0
Kp
n2 RAo
(63)
(
where 0 = X ( -Y denotes the min-norm interpolator, and R&(E) Eish x:)2 (Eis 2 denote another type of effective rank.
By introducing the time factor, Theorem 5.1 improves over Equation 63 in at least two aspects. Firstly. Theorem [5. guarantees the consistency of the gradient descent dynamics for broad range of step number f, while Bartlett et al. 8 study the limiting behavior of the dynamics of - co. Secondly, Theorem 5.1 implies that the excess risk of early stopping gradient descent solution can be much better than the min-norm interpolator. Compared to the bound in Equation (63). the bound in Corollary 5.1 (a.) replaces ko with much smaller quantity k1; and (b.) drops the second term involving RRo ( Therefore, we can derive a consistent bound for an early stopping solution, even though the excess risk of limiting point (min-norm interpolator) can be (2()).
Comparison to Zou et al. (76). Zou et al. (76 study a different setting, which focuses on the one-pass stochastic gradient descent solution of linear regression. The authors prove bound for the excess risk as
n Eisk X3 R(O,) 0 ki + (Eis 2,0,,,2
(64)
where 6, denotes the parameter obtained using stochastic gradient descent (SGD) with constant step size at epoch I. Similar to our bound, Equation also uses the effective dimension kn to characterize the variance term. However, scenario from ours, which is one-pass SGD scenario. During the one-pass SGD training, one uses a fresh data point to perform stochastic gradient descent in each epoch, and therefore they set f ((n) by default. As a comparison, we apply the standard full-batch gradient descent, and thus the time can be more flexible. Besides, our results in Corollary [5.1 improve the bound in Equation (64) by dropping the second term, We refer to the third and fourth example in Example 5.1 for a numerical comparison of the bound
emphasize that Zou al. (76) derive the bound in pretty different
B.2 Comparisons with Stability-Basee Bounds
In this section, we show that Theorem 5.1 gives provably better upper bounds than the stability- based method. We cite result. from Teng al. (67]. which uses stability arguments to tackle overparameteried linear regression under similar assumptions.
Theorem B.1 (modified from Theorem 1 in Teng et al. [67]). Under the overparameterized linear
@r.T a regression settings, assume that ||>||| < 1, |s| S V, Ve.. Sg- is of.-subgaussian. Let B, = sup ||O,]. the following inequality holds with probability at least 1 8-8:
( (max 0" Σ0 22 (V + B,)2)
log(4/0)
10
M(V + B,)²
R(O,) =
+
(65)
At
Theorem B.
in the overparameterized linear regression setting, by replacing the bounded Lipschitz condition with the bounded domain condition. fine-grained analysis [3] may remove the bounded Lipschitz condition, but it additionally requires
applies the general stability- results 19 24
"Due to the bias term in Theorem 5.1 the overall excess risk bound cannot surpass the order O(1vvn). which leads to the cases that Zou et al. (76) outperforms our bound. However, we note that such differences come from the intrinsic property of GD and SGD, which may be unable avoid in the GD regimes.
28

---

zero noise or decaying learning rate, which is different from our setting. We omit the excess risk decomposition technique adopted in Teng et al. [67 for presentation clarity.
Theorem B.I can not directly yield the stability argument Theorem 4.1 since obtaining a high probability bound of Be requires delicate trajectory analysis and is non-trivial task. Therefore, data-irrelevant methods such as stability-basee bounds can not be directly applied to our setting, Even if one can replace B3, in Equation with its expectation that easier handle (this modification will require adding concentration-relatee terms, and make the bound in Equation 65 looser), we can still demonstrate that Theorem 5.1 tighter than the corresponding stability-baas based analysis by providing a lower bound on E B, which will imply lower bound on the righthand side of Equation 65
Theorem B.2. Let Assumption / 2 holds. Suppose X == O E
x.)
Suppose the conditional
variance of the noise a|æ is lower bounded by og. There exists constant c, such that with probability at least ne E, have for i o(n).
A2t²
Σ X1 )
E 0 Ω
(66)
ko
First we prove the following lemma, bounding the number of large pi-
Lemma B.1. Suppose o(n). Let I denote the number of pii such that μ4i = 52 (7). Then with probability at least ne " we have Ot)).
Proof. According to Lemma A.1 we know that with probability at least ne Equation 12
holds for all 0 < k <
1. Conditioned on this, we have
n t
P4
As + Aun) ((++)) Σ Sl+n
(67)
Jom
<>0
Since & = o(n), we have = (t) claimed.
We also need the result from Bartlett et al. 8. which gives lowerbound of pa.
Lemma B.2. (Lemma 10 in Bartlett et al. (8) For any og, there exists constant such that with probability at least e we have,
Σ )m)
Pn
(68)
We are now ready prove Theorem
B.2
29

---

Proof. We begin with the calculation of ||0,|l". By Lemma A.2 the conditional unbiasedness of noise in A and the noise variance lower bound, we have
0,11
(0o (x-xx() + x x x
7
A [xTx)] x (XO- xX(000 +E)
I
--
--- xxxxx x x'x0'
I -11-2xxx)
+E
x'E
n
3
2 E
- x x
X
Xle
ETr
I --
x x x->x(x))
)))
X T X1iT
I -x x
n
I (1-2x(x) xtxti
I- 1-(1-2xTx))
2 E.
n
n 112
o²²
(69)
When 14
= =4= 0 (7), we have
X
((s Hzt (1
) -
=0 -)==))))
2)
(0( (ntttt)
1 1 (1
p4) 1
put +
(70)
Plugging it into Equation
69 and then use Lemma B.I B.2
we know that under the high probability
event in Lemma B.I and
B.2
E 0,112 = Ω (mn (m- 1) 12
12 (2atttt) = =Ω (12
12
X212
Σ X1 )
Matt = 12
(71)
Therefore, the stability-basee based bound, i.e., the right hand side of Equation 65 can be lower bounded in expectation as 12
Σisho >1). This implies that the stability- based bound is vacuous when
n2
n (Eiszo A:)
t t= Ω
Thus, stability- based methods will provably yield smaller compatibility
region than (w (+)) o (2)) in Theorem 4.1 when Σisto X; is not very small, as demonstrated in the examples below.
Example B.1. Let Assumption 7
3 holds. Assume without loss of generality that X = @(1). We
have the following examples:
1. (Inverse Polynominal), If the spectrum of E satisfies
A ka
for some o >> we derive that kn = (n)) Eisko >== 0 (,))))) Therefore, the stability bound in Theorem B. is vacuous when
t= 12 a+l
which is outperformed by the region in Theorem
5. when 2.
30

---

2. (Inverse Log-Polynominal) If the spectrum of Σ satisfies
Ak=
h: klog (k: + 1)
for some 3 > 1, we derive that ko = bound in Theorem is vacuous when
Toon Ei>ko ) =
((1). Therefore, the stability
52 n33 ))3)
5.1 which oulperformed by the region Theorem
3. (Constant). If the spectrum of E satisfies
A ni+s' S nte
for some we derive that ko Eisho d 1. Therefore, the stability bound in Theorem B.7 is vacuous when
1= Ω n3
which outperformed by the region Theorem 5.1
4. (Piecewise Constant), If the spectrum of E satisfies
1 k S
A
d-8
where = n n9,0 < Therefore, the stability bound in Theorem B. is vacuous when
1,9 2 1, we derive that ko = n., Eisto d 1.
Ω nz (n))
which is oulperformed by the region in Theorem 5.1
B.3 Comparisons with Uniform Convergence Bounds
We first state standard bound on the Rademacher complexity of linear models.
Theorem B.3 (Theorem in Mohri et al. (44). Let S C {x: ||=||2 S r be sample of size and let
H (x + (w, x) |//l222 22 S A}. Then, the empirical Rademacher complexity of H. can be bounded
as follows:
A2
Rs(H)
(72)
Furthermore, Talagrand's Lemma (See Lemma 5.7 in Mohri al. 44 indicates that
( H) S LRs(H)) @(A2)
(73)
vn
where L - (A) is the Lipschitz coefficient of the square loss function / in setting. Therefore, the Rademacher generalization bound vacuous when A 2(n+).. By Theorem B.2 know
that 0, 2 = 2( when / = Ω
# A similar comparison as in Example B.1 can
A(E x
demonstrate that uniform stability arguments will provably yield smaller compatibility region than that in Theorem 5.1 for example distributions.
31

---

B.4 Comparison with Previous Works on Early Stopping
line of works focuses on deriving the excess risk guarantee of linear regression or kernel regression with early stopping (stochastic) gradient descent. We refer to Section 2 for details. Here we compare
our results with some most relevant works, including [37 51 72
Comparison with Yao et al. [72]. Yao et al. 72 study kernel regression with early stopping gradient descent. Their approaches are different from ours in the following aspects.
Firstly, the assumptions used in the two approaches are different, due to different goals and techniques. Yao et al. [72] assume that the input feature and data noise have bounded norm (see Section 2. in Yao et al. (22). while we require that the input feature is subgaussian with independent entries.
Furthermore, although Yao et al. 72 obtain a minimax bound in terms of the convergence rate, it suboptimal in terms of compatibility region. Specifically. The results in our paper show region like (0, 12) while the techniques Yao et al. [72] can only lead to region like (0, vn). See Proof of the Main Theorem in section 2 in Yao et al. 722 for details. Such differences come from different
goals of the two approaches, where Yao et al. 72 focus providing the optimal early-stopping time
while we focus on providing larger time region in which the loss consistent.
Comparison with Lin and Rosasco 377. Lin and Rosasco (37 study stochastic gradient descent with arbitrary batchsize, which reduced full batch gradient descent when setting the batchsize to sample size n. Their results are different from ours, since they require the boundness assumption, and focus more on the optimal early stopping time rather than the largest compatibility region, in c+1
the same spirit of Yao et al. [72]. Specifically, Lin and Rosasco [37] derive region like (0, n 1 )
where ( and y are problem dependent constants (See Theorem in Lin and Rosasco [37] for details).
The following examples demonstrate that this paper's results yield larger regions for wide range of distribution classes.
Example B.2. (Inverse Polynominal). If the spectrum of E satisfies
A
k-
for some > 1. For this distribution, we have C = 2. à. and their region is (0, (0,TT which
3041
smaller than (0, n 20+1) given in Example 5.2
Example B.3. (Inverse Log-Polynominal,, If the spectrum of Σ satisfies
A k log (k + 1)²
for some 3 > 1. For this distribution, we have ( = 2. 7 = L, and their region is (0, n2)) which is smaller than n0 given Corollary 5.1
B.5 Calculations in Example 5.1
We calculate the quantities r(E), ko, ki, k2 for the example distributions 5.1 that k is typically much smaller quantity than ky-
The results validate
1. Calculations for A
a
Define Fh
(
Σcse A An+1
as in Bartlett et al. 88. Since Σisk ja = O pa
r), we have
Tk
Σ
θ
Aa-1
= (k)). Hence, hn- = (m)) and the conditions of theorem 5.1 is
satisfied.
As Eiso d 0o, By its definition we know that kj is the smallest such that A (12) Therefore, k (
2. Caleulations for d
k llog (k+1) 3 1.
Σisk (141" O llog dx) = 0 1og which implies Tx (x) = k log k.
sc
Solving ko log ko (n), we have kn (
Thee calculations for ko, An and t2 in this section only apply when is sufficiently large.
32

---

By the definition of k1. we know that 11 is the smallest / such that / (1+ 2 (n).
Therefore, ( log"
3.
Calculations for X ni-e; sis n , 0.
Since ro (2) = n2 we have hy = 0. By the definition of k1, we also have k1 = 0.
1 k S
4. Calculations for À d-o 8 s+1 k - d : n², n², < 1, 2 1.
For 0 8, (E) O 1) (nn") o(n), while r. r>)
- 0 w()).
d-s
Therefore, ko = n². Similarly, noting that 2 w(n) for 0 S k < and X, = =0 [/2) = o(n), we know that h1 = n'.
B.6 Calculations for As= 1/k2 or in Section 5.3
1 Set c(t, n)) = n² where 3 > 0 will be chosen later. First we calculate k2 under this choice of c(t, n).
Note that Σi>k 3a O (x--)) Therefore, 22 is the smallest & such that ke-r + k = -( For the bound on V(t)) to be consistent, need l/ o(n). Hence, ka-1 O a ), which implies 211
1
1
k2 =
Plugging the value of c(t, n) and ly into bound, we have
V(O,) O na 11- -18 n
222-8-2)
which attains its minimum (n
2or-3n+2r--
20.1
2 2ar-a-1 2a+1
For ((0) O(1), we need < the range of in which the above calculation applies.
30++1
For 3 2 0, we need a-1
Putting them together gives
2art2
B.7 Discussions on Dn,
In this paper, the distribution 2 is regarded as sequence of distribution {D,} which may dependent on sample size n. The phenomenon comes from overparameterrizaton and asymptotic requirements. In the definition of compatibility, we require the dimension (if finite) cannot be independent of n since n - co would break overparameterization.. Therefore, the covariance Σ also has n-dependency, since Σ is closely related to p.
In this case, overparameterriztion requires that
Several points are worth mentioning: (1) Similar arguments generally appear in related works, for example, in Bartlett et al. g when discussing the definition of benign covariance. (2) One can avoid such issues by considering an infinite dimensional feature space. This is why we discuss the special case in Theorem 4.1 (3) If is fixed finite constant that does not alter with the problem becomes underparameterizzed and thus trivial to get a consistent generalization bound via standard concentration inequalities.
C
Additional Experiment Results
C.1 Details for Linear Regression Experiments
In this section, we provide the experiment details for linear regression experiments and present additional empirical results.
The linear regression experiment in Figure Soaure/followwe follows the setting described section 6 Although the final iterate does not interpolate the training data, the results suffice to demonstrate the gap between the sarly-stopping and final-iterate excess risk. The training plot for different covariances are given in Figure [
Next, we provide the experiment results of sample sizes n = 50, n = 200 and feature dimensions p 500, p- 2000. The settings are the same described above, except for the sample size. The optimal excess risk and min-norm excess risk are provided in Table 3 6 and 5 The tables indicate that the two observations stated above hold for different sample size n.
33

---

Tainng
Loes
loes
Traiina Loos
Risc
Risic
Training
Training
Opochs
Epochs
Epochs
(a) X;
(b) X 12
(c) A
13
Excess
Training Lass
Risk
Training Lais
Excess Malk
Treiming Loss
Epachs
Epachs
(d) A 1log(++1]
X
(f)
1log (+++1
Flog ((+1]
Figure 2: The training plot for overparameterized linear regression with different covariances using GD.
Table 3: The effective dimension , the optimal early stopping excess risk and min-norm excess risk for different feature distributions, with sample size n 50, 1000. We calculate the 95% confidence interval for the excess risk.
DISTRIBUTIONS
k1
OPTIMAL EXCESS RISK
MIN-NORM EXCESS RISK
A
(n))
2.515 + 0.0104
12.632 1 0.1602
A
(n++)
0.269 = 0.0053
50.494 + 0.9378
A F
(1z
0.083 + 0.0011
13.208 1: 0.4556
A 11g
0.808 0.0090
46.706 0.6983
log
A Hog (++1)
0.381 0.0076
74.423 = 1.1472
log
A Hog (H+1)
0.233 0.0052
43.045 + 0.8347
Jog T
C.2 Details for MNIST Experiments
In this section, we provide the experiment details and additional results in MNIST dataset.
The MNIST experiment details are described below. We create a noisy version of MNIST with label noise rate 20%, i.e. randomly perturbing the label with probability 20% for each training data, to simulate the label noise which common in real datasets, e.g ImageNet 60 65 73 inject noise into the test data.
We do not
We choose standard four layer comvolutional neural network as the classifier. We use vanilla SGD optimizer without momentum or weight decay. The initial learning rate is set to 0.5. Learning rate is decayed by 0.98 every epoch. Each model is trained for 300 epochs. The training batch size set to 1024, and the test batch size set to 1000. We choose the standard cross entropy loss as the loss function.
We provide the plot for different levels label noise in Figure 3 We present the corresponding test error of the best early stopping iterate and the final iterate in Table 7 Since the theoretical part of this paper focuses on GD, we also provide a corresponding plot of GD training in Figure for completeness.
34

---

Table 4: The effective dimension 11, the optimal early stopping excess risk and min-norm excess risk for different feature distributions, with sample size 200, p = 1000. We calculate the 95% confidence interval for the excess risk.
DISTRIBUTIONS
k
OPTIMAL EXCESS RISK
MIN-NORM EXCESS RISK
A
(m)
2.173 0.0065
52.364 + 0.4009
A
((n2)
0.161 + 0.0039
36.855 + 0.4833
A
(nna)
0.068 + 0.0012
8.1990 + 0.2313
A flg(s++1)
0.628 0.0034
152.70 + 1.1073
log
A log (141)
0.241 0.0036
83.550 + 0.7596
log
A (141)
0.146 0.0108
33.469 1 0.4540
Tog 12
Table 5: The effective dimension k, the optimal early stopping excess risk and min-norm excess risk for different feature distributions, with sample size n 100, = 500. We calculate the 95% confidence interval for the excess risk.
DISTRIBUTIONS
k1
OPTIMAL EXCESS RISK
MIN-NORM EXCESS RISK
A
(m))
1.997 0.0876
27.360 + 0.3019
X
(nn2)
0.211 0.0050
43.531 + 0.7025
A
(n27)
0.076 0.0011
10.062 + 0.3022
A (lg((+1)
O log
0.645 0.0056
96.465 + 1.0594
A log (1+1)
log 0.289 0.0055
83.694 + 0.9827
A Flog
0.181 0.0045
38.090 + 0.6378
log
Table 6: The effective dimension k,, the optimal early stopping excess risk and min-norm excess risk for different feature distributions, with sample size 100, p 2000. We calculate the 95% confidence interval for the excess risk.
DISTRIBUTIONS
k1
OPTIMAL EXCESS RISK
MIN-NORM EXCESS RISK
A
((n)
2.662 0.0066
23.111 0.2278
A
((z7)
0.219 0.0050
43.130 0.6421
A =
(na
0.077 0.0010
10.031 + 0.2942
A Flogl++T
0.749 + 0.0055
88.74 + 0.9414
A (log
0.312 1 0.0057
82.859 1. 0.9394
Tog
A (1+1)
0.190 + 0.0047
37.782 + 0.5945
log
Table 7: The test error of optimal stopping iterate and final iterate on MNIST dataset with different levels of label noise. The results demonstrate that stopping iterate have significantly better generalization performance than interpolating solutions for real datasets.
NOISE LEVEL
OPTIMAL TEST ERROR
FINAL TEST ERROR
0%
1.07%
1.13%
10%
1.75%
10.16%
20%
2.88%
19.90%
30%
2.18%
27.94%
40%
2.57%
35.15%
50%
2.71%
42.95%
35

---

Trininng Emar
Traniing Enror
Training Error
Test Eno
Test
Epochs (a) 0% label noise
Epochs (b) 10% label noise
Epochs
(c) 20% label noise
Training Emoo
Teste Enror
Test Errux
Toxt Error
Training
Training
Epocho
(d) 30% label noise
(e) 40% label noise
(I) 50% label noise
Figure 3: The training plot for corrupted MNIST with different levels label noise using SGD.
Figure (c) is copied from Figure
Yaring
Paining Emror
Tost Enor
Epochs
Figure 4: The training plot for corrupted MNIST with 20% label noise using GD.
36


Reviews:
[{"review_id": "NPedP9DxSd", "reviewer": "Reviewer_5qZn", "summary": "The authors present a new mathematical framework for characterizing generalization of over-parameterized machine learning models. The new framework provides improved bounds from prior work, and improves on prior work by combining both data and algorithm information. To summarize their contributions: The paper formalizes a notion of compatibility, as a minimal condition for generalization based on the interaction between data and algorithm. They derive sufficient conditions for compatibility for over-parameterized linear regression with gradient descent, and then derive time-variant generalization bounds for the over-parameterized linear regression and show empirical results that verify the motivation of compatibility and demonstrate benefits of early stopping.\n\nCaveat: This paper falls outside my area of expertise to the level that in my available time I cannot vouch for the accuracy of the theorems provided in the paper.", "questions": "Are there any roadblocks that would make application of this difficult for other models, such as non-linear regression problems including deep neural networks? Are there larger or broader implications of data-algorithm compatibility and your results that you can discuss?", "limitations": "Societal impact does not seem relevant or needed to address for this paper. The paper acknowledges a limited scope to linear cases, but does not go into any additional weaknesses.", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Theoretical proofs are given, along with bounds comparisons, and empirical results. The paper seems well-written and rigorous in its assessment. The problem is well motivated and extremely well-referenced in its citations and descriptions of the current work in this area. The ability and degree to which over-parameterized models can generalize is one of the main mysteries of deep learning, and where traditional theory in generalization breaks down, so the paper is extremely relevant. ", "weaknesses": "This paper requires substantial knowledge of generalization theory to understand and is not accessible to a broader audience. For example, the introduction makes the assumption that terms like excess risk are understood by the reader, before they are later defined. While the theory is claimed to be general, thorough treatment is only given for linear regression, and derivations of sufficiency conditions and bounds for other problems are left as future work. While deep learning was given as a primary motivation to understand generalization for over-parameterized models, application to these models was not addressed in the paper. The experimental and conclusions sections were very minimal. I understand that the theory was the primary focus of the paper, but would have liked to see more practical demonstration and discussion of implications for the theoretical results that can be drawn from your investigations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere gratitude to the reviewer for the valuable feedback and supportive comments. \nThe reviewer's major concern comes from the linear example. \nIndeed, we only derive a linear example to express the effectiveness of compatibility. However, the idea behind is general which would bring some interesting insights into the generalization community. \nBelow we do our best to address the reviewer's concerns.\n\n>Q1: Are there any roadblocks that would make application of this difficult for other models, such as non-linear regression problems including deep neural networks? Are there larger or broader implications of data-algorithm compatibility and your results that you can discuss?\n\nA1: We thank the reviewer for the insightful and constructive comments. As the reviewer points out, the proposed data-algorithm compatibility is a general concept which can be deployed in deep learning, while the given example mainly focuses on the overparameterized linear regression. \n\nStudying a linear example is widely adopted in generalization analysis to understand deep learning, since (a) existing theories on neural tangent kernel [1,2] and random feature model [3,4] (both are theoretical approximations of neural networks) draw a rigorous connection between them, and (b) their generalization performances has some inherent relationships and common patterns, as indicated by our experiments. \n\nDue to technical limitations, we cannot directly generalize to neural networks now, but we believe that the concepts in this paper still provide some interesting insights for the generalization community.\n\n \n\n>Q2: This paper requires substantial knowledge of generalization theory to understand and is not accessible to a broader audience. [...]  I understand that the theory was the primary focus of the paper, but would have liked to see more practical demonstration and discussion of implications for the theoretical results that can be drawn from your investigations.\n\nA2: We thank the reviewer for the suggestions! We will reorganize the arguments and revise the paper accordingly to make it easier to understand. As an example, we will provide a definition of excess risk in the introduction, and add the discussion on the broader impact. Thank you!\n\nOnce again, we express our gratitude to the reviewer for the valuable feedback, which will undoubtedly contribute to enhancing the quality of our work. We remain committed to improving the clarity and rigor of our paper and welcome any further feedback.\n\n[1] Jacot A, Gabriel F, Hongler C. Neural tangent kernel: Convergence and generalization in neural networks[J]. Advances in neural information processing systems, 2018, 31.\n\n[2] Arora S, Du S S, Hu W, et al. On exact computation with an infinitely wide neural net[J]. Advances in neural information processing systems, 2019, 32.\n\n[3] Rudi A, Rosasco L. Generalization properties of learning with random features[J]. Advances in neural information processing systems, 2017, 30.\n\n[4] Mei S, Montanari A. The generalization error of random features regression: Precise asymptotics and the double descent curve[J]. Communications on Pure and Applied Mathematics, 2022, 75(4): 667-766.\n"}, {"review_id": "RvsfBfhXwi", "reviewer": "Reviewer_ytRs", "summary": "This paper considers the benign overfitting phenomenon in overparameterized linear regression problems under early stopping type gradient descent. \n\nSpecifically, this paper gives a time variant bound for the excess risk during the gradient descent training.\nBy comparing the optimal time variant bound with the previous bounds for the minimum-norm interpolant, this paper finds some data distribution examples that the optimal early stopping satisfies benign overfitting (compatibility) but the minimum-norm interplant does not. \nAmong all the examples, some of which outperform the previous early stopping type bounds in overparameterized linear regression problems.\n", "questions": "* In table 2, for the distributions that $\\lambda_i = \\frac{i}{i \\log^2(i+1)}$ and $\\lambda_i = \\frac{i}{i \\log^3(i+1)}$, both cases are benign overfitting based on *Bartlett et al*, but the min-norm excess risk seems to be very large though, is this caused by the bias term or the variance term?\n\n* I am curious what the generalization bound for early stopping will be like if following the notations in *Theorem 4. [Bartlett et al.]* in terms of $r_0(\\Sigma), k^*, R_{k^*}(\\Sigma)$?\nI am trying to understand the difference between methods using the proposed effective dimension in this paper and using the effective ranks in *Bartlett et al.*, because understanding the differences may help to motivates other more refined controls for the generalization analysis.\n", "limitations": "NA", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The organization and presentation of this paper is smooth and clear, and it provides a better understanding on the benign overfitting phenomenon for early stopping type gradient descent.\n* The theory in this paper is solid. Although it mainly follows from the previous two works *Bartlett et al.* and *Zou et al.*, the proposed notion 'effective dimensions' for the feature covariance matrix in this paper provides an alternative way to analyze the variance term in the Bias–variance decomposition.\n", "weaknesses": "There is no major weakness for me.\n\n---\n\nA minior issue:\n\nFor the examples and the numerical experiments in this paper, it would be better if the authors could provide the patterns to show the interplay between the bias term $B(\\theta_t)$ and the variance term $V(\\theta_t)$ during training.\nEspecially when comparing with the bounds in previous works, it would be more intuitive to see why the compatibility happens but the benign overfitting does not, if the comparisons  of the evolutions of $B(\\theta_t)$ and $V(\\theta_t)$ are shown separately.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's supportive and insightful comments. \nWe ensure to add the related discussion in the revision. Below, we do our best to address the reviewer's questions adequately. \n\n>Q1: For the examples and the numerical experiments in this paper, it would be better if the authors could provide the patterns to show the interplay between the bias term $B(\\theta_t)$ and the variance term $V(\\theta_t)$ during training.\n\nA1: Thanks for the constructive suggestion. In the experiment part, the bias term $B(\\theta_t)$ decays rapidly, and the model achieves small excess risk in the initial phase of training (as in our Figure 1). Meanwhile, the variance term $V(\\theta_t)$ increases steadily in the training process, and it takes a long time for the variance term as well as the excess risk to converge to a plateau. \n\nWe also provide the following table to validate the above pattern theoretically. \nThe table shows different bounds on bias and variance in different methods.\nWe will add the discussion in the next revision. \n\n| Reference | Setting | Bias | Variance |\n|----------|----------|----------| ----------|\n|This paper|gradient descent  | $\\frac{1}{t}+\\frac{1}{\\sqrt{n}}$ |$\\frac{k_1}{n}+\\frac{t^2}{n^2}$|\n| [1]  |  overfitting solution  | $\\frac{k_0}{n}$    | $\\frac{n}{R_{k_0}(\\boldsymbol{\\Sigma})}$   |\n| [2] | one-pass stochastic gradient descent | $\\frac{k_1}{n}$   | $ \\frac{n \\sum_{i>k_1} \\lambda_i^2}{\\left(\\sum_{i>0} \\lambda_i\\right)^2}$    |\n\n>Q2:  In table 2, for the distributions that $\\lambda_i=\\frac{1}{log^2⁡(i+1)}$ and $\\lambda_i=\\frac{1}{log^3(i+1)}$, both cases are benign overfitting based on Bartlett et al, but the min-norm excess risk seems to be very large though, is this caused by the bias term or the variance term?\n\nA2: We thank the reviewer for the insightful question! Benign overfitting means that the excess risk goes to zero as the sample size $n$ goes to zero. For the practical cases, it may be numerically large for a fixed sample size $n$ (may be due to a slow convergence rate with respect to $n$). As for the cause of the large excess risk, we believe that it comes from the variance term since the bias term is usually easy to learn in linear regression. We will add the discussion in the next version. \n\nAlthough the exact number cannot imply benign overfitting, we can still compare the early-stopping regimes and the interpolation regimes. This is what the experiments want to show in this paper. \n\n\n>Q3: I am trying to understand the difference between methods using the proposed effective dimension in this paper and using the effective ranks in [1].\n\nA3: We thank the reviewer for the insightful question. The differences come from two folds: (a) our proposed effective dimensions is time-dependent ($k_2$) while those in [1] do not need to focus on the time; and (b) due to the time effect, we can split the data covariance with more fine-grained analysis. Therefore, the term $k_0/n$ proposed in [1] can be improved to $k_1/n$ in our paper (where $k_1$ is provably smaller than $k_0$). We ensure to add the comparison in the revision. \n\nOnce again, we appreciate the reviewer's feedback and hope that our response address the concerns. We remain committed to improving the clarity and rigor of our paper and welcome any further feedback.\n\n[1] Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. CoRR, abs/1906.11300, 2019.\n\n[2] Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham M. Kakade. Benign overfitting of constant-stepsize SGD for linear regression.\n"}, {"review_id": "rGAuorqmxH", "reviewer": "Reviewer_dysH", "summary": "This paper suggests a new framework for evaluating the generalization error called compatibility. Compatibility takes into account both the data and algorithm and says the two are compatible if there is an early stopping region, as $n \\to \\infty$ that has zero excess risk. The paper then considers the linear regression framework and provides spectral conditions under which full batch constant step size gradient descent is compatible. ", "questions": "In Assumption 1 subpoint 2, should it $\\lambda_p > 0$? Instead of $\\lambda_1 > 0$.\n\nAre the Cs on lines 169 and 173 supposed to be the same?\n\nWhy is $\\boldsymbol{Y}$ called the noise vector?\n\nIn Equations (4), (5), how do we know such an $\\ell$ exists?\n\nWhat is $c$ in the statement of Theorem 5.1 in $k_0 \\le n/c$?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main strength of the paper is the generality of the data distributions considered. Specifically, most prior theory work assumes we have isotropic data or some fixed transform of isotropic data. However, this paper considers general anisotropic data. In this setup, they provide mild conditions under which we see that early stopping is beneficial for generalization. \n\nThe paper also provides clear evidence of the benefits of early stopping. Showing that the min norm solution is not necessarily the optimal solution for generalization. Further, the paper shows that this is true even in the large data limit when the min norm solution is benign. \n\n", "weaknesses": "The are two main weaknesses (one major one minor)\n\n1) The paper is missing the comparison to Madhu S. Advani, Andrew M. Saxe, and Haim Sompolinsky. High-dimensional Dynamics of\nGeneralization Error in Neural Networks. Neural Networks, 2020 \n\nWhile the data assumptions in the above paper are more restrictive, that is isotropic data. The paper exactly characterizes the risk curve as a function of time and determines the optimal stopping time. Hence a proper discussion of this is crucial. \n\n\n3) While the paper is well written, the paper sweeps technical details under the rug that would be important to know. For example, the constants $c_0$ and $c_1$ are opaque and play an important role. See my questions for more instances.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere gratitude to the reviewer for their valuable feedback and insightful comments. \nWe apologize for not making everything clear and ensure to revise our manuscript according to the reviewer's suggestions. \nBelow we do our best to address the reviewer's concerns.\n\n>Q1: The paper is missing the comparison to [1].\nA1: We thank the reviewer for the recommendation. We ensure to add the discussion with [1] as well as its related papers [2], [3] in the revision. \n\nAs the reviewer points out, the major difference between our paper and [1] lies in the different assumptions on the data. [1] assumes that the input data, data noise, and teacher model weights all follow i.i.d. isotropic Gaussian distribution. In particular, the data covariance in this setting is an identity matrix. In comparison, our results only require bounded ground truth weights and subGaussian data and noise, which is milder.\n\n>Q2: In Assumption 1 subpoint 2, should it $\\lambda_p>0$ Instead of $\\lambda_1>0$?\n\nA2: We apologize for the confusion. Here we indeed assume that $\\lambda_1 > 0$ to rule out the all-zero input cases. This holds trivially in practice but we still express it explicitly to make the paper complete. Our results hold even when $\\lambda_p=0$, which is a degenerate case and can be transferred to another linear regression problem with lower dimensions. \n\n>Q3: Are the Cs on lines 169 and 173 supposed to be the same?\n\nA3: It can be treated as the same absolute constant that is large enough. The use of a unified $C$ is for notation simplicity.  For example, if we have $\\sum_{i>0}\\lambda_i< C_1, ||\\theta^*||<C_2$, we can take $C$ as the maximum of $C_1$ and $C_2$. Such tricks are because we want to put more focus on the rate of dimension and sample size, as most relevant papers do. \n\n>Q4: Why is $Y$ called the noise vector?\n\nA4: We apologize for the typo. We will change it to the response vector in the revision. \n\n>Q5: In Equations (4), (5), how do we know such an $l$ exists?\n\nA5: Thanks for the good catch. We take $l=\\infty$ if a finite $l$ does not exist. This would lead to a vacuous generalization bound. We will make it clearer in the next version. \n\n>Q6: What is $c$ in the statement of Theorem 5.1 in $k0≤n/c$?\n\nA6: $c$ is a large enough constant independent of time $t$, dimension $p$, sample size $n$.\n\nOnce again, we thank the reviewer for the time and feedback, which will undoubtedly help us improve the quality of our work. We remain committed to improving the clarity and rigor of our paper and welcome any further feedback.\n\n\n[1] Advani M S, Saxe A M, Sompolinsky H. High-dimensional dynamics of generalization error in neural networks[J]. Neural Networks, 2020, 132: 428-446.\n\n[2] Saxe A M, Bansal Y, Dapello J, et al. On the information bottleneck theory of deep learning[J]. Journal of Statistical Mechanics: Theory and Experiment, 2019, 2019(12): 124020.\n\n[3] Goldt S, Advani M, Saxe A M, et al. Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setup[J]. Advances in neural information processing systems, 2019, 32.\n"}, {"review_id": "syJYXmau4D", "reviewer": "Reviewer_YpbP", "summary": "This paper suggests a notion of compatibility, which is an algorithm-dependent and data-dependent term to bound the excess risk of overparameterized linear regression models. Using this notion, the authors come up with three regimes on the covariance matrix, and characterize the compatible region (that is the region of steps where we can train the model with GD and still converge in terms of excess risk). The authors show the connection between compatibility and benign overfitting and also compare to stability bound. Several examples are provided to demonstrate how the compatibility region depends on the covariance structure.", "questions": "See weakness.", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I find the paper to be well-written and easy to follow. The overall topic of generalization of overparameterized models (even in the linear case) is important. The authors make a considerable effort to introduce existing bounds.", "weaknesses": "1. I find the study of overparameterized linear model *together with* early stopping less motivating. In particular, early stopping for linear regression is equivalent to $\\ell_2$ regularization. In this case, we can already apply uniform convergence bound for generalization error. In this case, is the motivation mainly to get a better bound? If so, I would suggest the authors move the comparison to stability bound into the main text. This is in contrast to the overfitting case since if we are overfitting, there is no uniform convergence bound at all.\n\n2. One relevant work is missing, [1] (and its related citations) discussed cases when we have different kinds of overfitting. In particular, their theorem 3.1 (b) corresponds to your example 4.1. I would love to see how your results are related to theirs. \n\n[1] Benign, Tempered, or Catastrophic: A Taxonomy of Overfitting\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful and meaningful comments which would greatly help us revise our manuscript. \nThe reviewer's major concern comes from whether we can cover the results from the relationship between early-stopping and ridge regression.\nBelow, we show why our results cannot be covered intuitively and defer the technical details later. \nFirstly, in their relationship, the regularization parameter of ridge regression is set to $1/t$, where $t$ denotes the early-stopping time [1]. \nIn linear regression, such $t$ usually relates to sample size $n$ (e.g., $t = \\sqrt{n}$), and therefore, with small regularization, its parameter norm may still be large and generalization bound may fail. \nSecondly, the information bottleneck principle tells us that minimal steps may provide better results. By relating the early-stopping and ridge regression, the information is partially lost. Therefore our bound would be tighter. \nWe calculate the generalization performance of ridge regression under the regularization $1/t$ and show that it cannot cover our results.\nWe ensure to add the detailed discussion in the revision. \nBelow we do our best to address the reviewer's concerns in detail.\n\n\n>Q1: Early stopping for linear regression is equivalent to $\\ell_2$ regularization. In this case, we can already apply uniform convergence bound for generalization error.\n\nA1: We thank the reviewer for the constructive comment. Indeed, there is a close relationship between early stopping and ridge regression. For example, [1] proves that early stopping excess risk at time $t$ can be upper bounded by ridge regression excess risk with **regularization coefficient $1/t$**. However, ***our results cannot be covered since the results in [1] do not apply for large time $t$ (leading to small regularization $\\lambda = 1/t$)***. \n\nFor example, consider the case that eigenvalue decays as $\\frac{1}{i^{1.5}}$. if we take $t=\\Theta\\left(\\sqrt{n}\\right)$ and $\\lambda=\\Theta\\left(\\frac{1}{\\sqrt{n}}\\right)$, it can be shown that for the ridge regression solution,  a norm-based generalization bound will give an excess risk of  $\\Omega(1)$, which only provides a vacuous generalization bound of the early stopping solution. As a comparison, our results give consistent generalization bound for this case. \n\n\nFurthermore, this generalization bound in this approach cannot cover ours, even if we use a more fine-grained analysis rather than uniform convergence. Following Theorem 1 in [2], we can calculate that the variance term is $\\Omega(1)$ when $t=\\Omega\\left(\\sqrt{n}\\right)$, and the bound is vacuous for the above example. \n\nDue to space limit, we are unable to post the proof here. We will add the calculation details as soon as possible in the discussion period. \n\n>Q2: One relevant work is missing... their theorem 3.1 (b) corresponds to your example 4.1. I would love to see how your results are related to theirs.\n\nA2: We thank the reviewer for the recommendation. We ensure to add a discussion and cite the related papers [3], [4], [5], [6],[7],[8],[9],[10], [11] in the next revision. \n\nAs pointed out by the reviewer, Theorem 3.1(b) in [3] shows that for feature covariance $\\lambda_i=1/i^\\alpha$ with $\\alpha>1$, the excess risk will converge to $(\\alpha-1)\\sigma^2>0$, and falls into the **tempered**  taxonomy as in [3]. As a comparison, we prove that with early stopping, the model can achieve $o(1)$ excess risk for these data distributions, and falls into the **benign** taxonomy as in [3]. In this sense, our results are consistent with and extend the result in [3]. \n\nAgain, we would like to express our great gratitude to the reviewer for their thoughtful comments. We are eager to provide any additional clarification that may be needed to help the evaluation.\n\n\n\n[1] Ali A, Kolter J Z, Tibshirani R J. A continuous-time view of early stopping for least squares regression[C]//The 22nd international conference on artificial intelligence and statistics. PMLR, 2019: 1370-1378.\n\n[2] Tsigler A, Bartlett P L. Benign overfitting in ridge regression[J]. J. Mach. Learn. Res., 2023, 24: 123:1-123:76.\n\n[3] Mallinar N, Simon J B, Abedsoltan A, et al. Benign, tempered, or catastrophic: A taxonomy of overfitting[J]. arXiv preprint arXiv:2207.06569, 2022.\n\n[4] Carrell A, Mallinar N, Lucas J, et al. The calibration generalization gap[J]. arXiv preprint arXiv:2210.01964, 2022.\n\n[5] Simon J B, Dickens M, Karkada D, et al. The Eigenlearning Framework: A Conservation Law Perspective on Kernel Regression and Wide Neural Networks[J]. arXiv preprint arXiv:2110.03922, 2021.\n\n[6] Liu C, Abedsoltan A, Belkin M. On Emergence of Clean-Priority Learning in Early Stopped Neural Networks[J]. arXiv preprint arXiv:2306.02533, 2023.\n\n[7] Emami M, Sahraee-Ardakan M, Pandit P, et al. Generalization error of generalized linear models in high dimensions[C]//International Conference on Machine Learning. PMLR, 2020: 2892-2901.\n\n[8] Beaglehole D, Belkin M, Pandit P. Kernel Ridgeless Regression is Inconsistent for Low Dimensions[J]. arXiv preprint arXiv:2205.13525, 2022.\n\n[9] Sahraee-Ardakan M, Emami M, Pandit P, et al. Kernel methods and multi-layer perceptrons learn linear models in high dimensions[J]. arXiv preprint arXiv:2201.08082, 2022.\n\n[10] Nakkiran P, Kaplun G, Bansal Y, et al. Deep double descent: Where bigger models and more data hurt[J]. Journal of Statistical Mechanics: Theory and Experiment, 2021, 2021(12): 124003.\n\n[11] Belkin M. Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation[J]. Acta Numerica, 2021, 30: 203-248.\n\n[12] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. Adaptive computation and machine learning. MIT Press, 2012.\n"}]

Author rebuttal:

Meta-review: The submitted paper proposes a new mathematical framework called "compatibility" for analyzing the generalization error of over-parameterized machine learning models, specifically focusing on over-parameterized linear regression using gradient descent with early stopping. The reviewers generally acknowledge the significance of the paper's contributions. Namely, its theoretical contribution, clarity of presentation, and relevance towards the audience.
Nevertheless, while the theoretical insights are appreciated, some reviewers did express the desire for a more practical demonstration. That, together with a discussions of implications for real-world deep learning models, which were mentioned as one particular motivation, can significantly improve the paper.

Please consider reviewer's suggestions, including missing refs, and address those in the final revision.
Decision: Accept (poster)