When Do Models Generalize? A Perspective From Data-Algorithm Compatibility
Authors: Jing Xu
Jiaye Teng
Yang Yuan
Andrew C Yao
Venue: Submitted to ICLR 2023 (2023)
Keywords: generalization
data-algorithm compatibility
early stopping
overparameterized linear regression

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 (Nagarajan and Kolter, 2019). In many scenarios, their failure can be attributed to obscuring the crucial interplay between the training algorithm and the underlying data distribution. To address this issue, we propose a concept named compatibility, which quantitatively characterizes generalization in a both data-relevant and algorithm relevant manner. By considering the entire training trajectory and focusing on early-stopping iterates, compatibility exploits the data and the algorithm information and is therefore a more suitable notion for generalization. We validate this by theoretically studying compatibility under 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 in the sense of compatibility, generalization holds with significantly weaker restrictions on the problem instance than the previous last iterate analysis.

Under review as a conference paper at ICLR 2023
WHEN DO MODELS GENERALIZE? A PERSPECTIVE FROM DATA-ALGORITHN COMPATIBILITY
Anonymous authors Paper under double-blind review
ABSTRACT
One of the major open problems in machine learning is to characterize gener- alization the overparameterized regime, where most traditional generalization bounds become inconsistent even for overparameterized linear regression (Na-) garajan & Kolter (019). In many scenarios, their failure can be attributed to obscuring the crucial interplay between the training algorithm and the underlying data distribution. To address this issue, we propose a concept named compatibil- ity, which quantitatively characterizes generalization in a both data-relevant and algorithm--ell relevann manner. By considering the entire training trajectory and fo- cusing on early-stopping iterates, compatibility exploits the data and the algorithm information and is therefore a suitable notion for generalization of overparam- eterized models. We validate this by theoretically studying compatibility under the setting of solving overparameterized linear regression with gradient descent. Specifically, we perform a data-dependent trajectory analysis and derive suffi- cient condition for compatibility in such setting. Our theoretical results demon- strate that the sense of compatibility, generalization holds with significantly weaker restrictions the problem instance than the previous at-convergence anal- ysis.
INTRODUCTION
Although deep neural networks achieve great success in practice (Silver et al. 2017 Devlin et al. 2019 Brown al. 2020), their remarkable generalization ability still among the essential mys- teries in the deep learning community. One of the most intriguing features of deep neural networks is overparameterizzaton, which confers level of tractability the training problem, but leaves traditional generalization theories failing to work. In generalization analysis, both the training al- gorithm and the data distribution play essential roles (Jiang al.) 2020). For instance, line of work (Zhang et al. 2021: Nagarajan & Kolter 2019) highlights the role of the algorithm by showing that the algorithm areelevant uniform convergence bounds can become inconsistent in deep learning regimes. Another line of work (Bartlett et al. 2019 Tsigler & Bartlett 2020) on benign overfitting emphasizes the role of data distribution via profound analysis of specific overparameterized models.
Despite the significant role of data and algorithm in generalization analysis, existing theories usu- ally focus on either the data factor (e.g., uniform convergence (Nagarajan & Kolter 2019) and last iterate analysis (Bartlett et al. 2019 Tsigler & Bartleti (0200) or the algorithm factor (e.g., stability- based bounds (Hardt et al. 2016). Combining both data and algorithm factor into generalization analysis can help derive tighter generalization bounds and explain the generalization ability of over- parameterized models observed in practice. In this sense, a natural question arises:
How to incorporate both data factor and algorithm factor into generalization analysis?
To gain insight into the interplay between data and algorithms, 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,
'The taxonomy of data deta-dependent techniques does not mean that they totally ignore all the information of algorithm, but mean that it loses some important algorithm information which makes it vacuous in generaliza- tion analysis. Similar arguments hold for algorithm-dependen techniques.

---

Under review as a conference paper at ICLR 2023
Excess Risk
Test Error
Training Loss
Training Error
Excess Risk
Training Loss
Training Emror
Test Error
187
11"1
1o
30
Epochs (a) Linear Regression
Epochs
(b) Comrupted MNIST
Figure 1: (a) The training plot for linear regression with spectrum X 1/1² 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 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 solution on the trajectory generalizes well but the final iterate fails to generalize. See Appendix Cor details.
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 eπror of the final iterate can be more than x x100 larger than that of the early stopping solution. In the MNIST case, the final iterate trajectory has 19.9% test error, much higher than the 2.88% test error of the hest 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 Yao al. 2007, Ali al. 2019 Li al. 20206 Ji al. 202T). By focusing on the entire optimization trajectory and performing data-dependent trajectory analysis, both data information and the dynamics of the training algorithm can be exploited yield consistent generalization bounds.
the SGD
To analyze the data-dependent trajectory, we introduce new concept named data-algorithm- compatibility, which jointly characterizes the role of the data and the algorithm in generalization analysis. Informally speaking, an algorithm compatible with a data distribution if as the sample size goes to infinity, the minimum excess risk of the iterates the training trajectory converges to zero.
The significance of compatibility comes in three folds. Firstly, compatibility incorporates both data and algorithm factors into generalization analysis, and brings new messages into generalization in mini-
the overparameterizattin regime (see Definition [.1].. Secondly, compatibility mal condition for generalization, without which one cannot expect to find a 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, compatibility captures the algorithmic significance of early stopping in generalization. By exploiting the algorithm informa- tion along the entire trajectory, we arrive at better generalization bounds than the at-convergence analysis (see Table and for examples).
To thcoretically validate compatibility, we study it under overparameterized linear regression setting. Analysis of the overparameterized linear regression a reasonable starting point to study compat- ibility for more complex models like deep neural networks, since many phenomena of the high dimensional non-linear model are also observed in the linear regime (e.g., Figure [I) Furthermore, the recent neural tangent kernel (NTK) framework demonstrates that very wide neural networks trained using gradient descent with appropriate random initialization can be approximated by kernll regression in reproducing kernel Hilbert space, which rigorously establishes close relationship between overparameterized linear regression and deep neural network training (Jacot et al. 2018 Arora et al. 2019).
2

---

Under review as a conference paper at ICLR 2023
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 compat- ible with overparameterized linear regression if the effective dimensions of the feature covariance matrix are asymptotically bounded by the sample size. this setting, the assumptions needed for generalization in the sense of compatibility are significantly weaker than that in the at-convergence analysis (Bartlett et al., 2019), which demonstrates the benefits of data-relevant and algorithm- relevant generalization analysis.
We summarize our contributions as follows:
We formalize the notion of compatibility, which highlights the interaction between data and algorithm and serves as minimal condition for generalization.
We derive a sufficient condition for compatibility in solving overparameterized linear re- gression with gradient descent. Our theory substantiates the meaningfulness of compati- bility by showing that generalization in the sense of compatibility typically requires much weaker restrictions in the problem instance.
Technically, derive time-variant generalization bounds for overparameterized linear gression via data-dependent trajectory analysis. Empirically, various experiment results verify the motivation of compatibility and demonstrate the benefits of early stopping.
2 RELATED WORKS
Data-Dependent Techniques mainly focus on the data distribution condition for generalization. One of the most popular bounds among data-dependent bounds is uniform convergence (Koltchinskil & Panchenko 2000, Bartlett et al. 2017] Zhou et al. 2020 Zhang et al.) 2021). However, recent works(Nagarajj) & Kolter 2019 Negrea et al. 2020 point out that uniform convergence may not be powerful enough to explain generalization, because it may only yield inconsistent bound in even linear regression cases. Another line of works investigates benign overfitting, which mainly involves generalization at convergence (Bartlett et al. 2019) Zou et al. 2021 Tsigler & Bartlett 2020
al. 2020c Wang Thrampoulidis) 2021 Frei et al. 2022).
Agorithm-Dependeee Techniques measure the role of the algorithmic information in generaliza- tion. A line of works derives generalization bounds via algorithm stability (Hardt al.) [0166]
Feldman & Vondrák 2018 Mou et al. 2018: Feldman & Vondrák 2019; [Bousquet et al.) 2020, Li
al. 2020at Lei & Ying 2020, Bassily al. 2020 TTng et al.) 2021). A parallel line of works
analyzes the implicit bias of algorithmic information (Bousquet & Elisseeff 2002: Soudry et al.)
2018 Shah et al. 2020 Hu et al. 2020 Lyu & Li 2020 Lyu et al. 2021), which are mainly based on analyzing specific data distribution (e.g., linear separable).
Other Generalization Techniques. Besides the techniques discussed above, there are many other approaches. For example. PAC-Bayes theory performs well empirically and theoretically (Shawe- Taylor & Williamson, 1997; Seeger [2022] McAllester [2003]
et al.) 2012
McAllester [013) (ziiuaiZe & 2017 Neyshabbur al. (018)) and can even yield non vacuous
bounds in deep learning regimes (Rivasplata et al. [2020] Pérez-Ortiz et al.) 2021
Furthermore,
there are other promising techniques including information theory (Russo & Zou 2016 Xu & Ra-
ginsky 2017: Banerjee & Montúfar 202I), and compression-basee bounds (Arora et al. 2018).
Early Stopping has the potential improve generalization for various machine learning prob-
lems (Raskutti et al.| 20144) Vaskevicius et al., [220)] IZhang et al.) [202]] L et al.) [202T] Kuzborskij &
Szepesvári 2021] Bai al.) 2021] Shen et al.) 2022). A line of works studies the rate of early stop- ping in linear regression and kernel regression with different algorithms, e.g., gradient descent (Yao)
al. 2007 , stochastic gradient descent (Tarres Yao 20144) Rosasco & Villa 2015 Dieuleveut
& Bach] 2016 [in & Rosasco| 2017, Pillaud- Vivien et al.] (0188), gradient flow (Ali et al. 2019),
conjugate gradient (Blanchard & Krämer (016) and spectral algorithms (Gerfo et al.) 2008 Lin &
Cevher 2018). Of the most relevance here is Yao et al. (2007), which proves optimal excess bound for a certain class of kernel regression problems solved using early stopping gradient descent, Beyond linear models, carly-stopping is also effective for training deep neural networks (Li et al.
20206 Ji et al. 202T). Another line of research focuses on the signal for carly stopping (Prechelt
2012 Forouzesh & Thiran 202T)
3

---

Under review as a conference paper at ICLR 2023
3 COMPATIBILITY
In this section, we formally define compatibility between the data distribution and the training algo- rithm, starting from the basic notations.
3.1 NOTATIONS
Data Distribution, Let denote the population distribution and z DD denote data point sam- pled from distribution D. Usually, & contains feature and its corresponding response. Besides, we denote the dataset with samples as Z 2 {zi]eg(n) where z; D are i.i.d. sampled from distribution D.
Loss and Excess Risk. Let ((0;z) denote the loss on sample with parameter O E R2. The corresponding population loss is defined L(0; D) Ex~DE((; z). When the context is clear, omit the dependency on 'D and denote the population loss by L(0). Our goal is to find the optimal parameter 0 which minimizes the population loss, i... L( ming L(0). Measuring how
parameter 0 approaches 0" relies term excess risk R(0), defined as R(0) _ I((0) I.(0)).
Algorithm. Let A(-) denote a iterative algorithm that takes training data as input and outputs Jezo, where is the iteration number. The algorithm be either deterministic or stochastic, egg., variants of (S)GD.
sequence of parameters )0%)),
3.2 DEFINITIONS OF COMPATIBILITY
Based on the above notations, we introduce the notion of compatibility between data distribution and algorithm in Definition 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 the loss function.
Definition 3.1 (Compatibility). Given a loss function {(-) with corresponding excess risk R(-), data distribution D is compatible with an algorithm A if there exists nonempty subsets To of N, such that suPtet, R(O!.) converges zero in probability as sample size n. tends infinity, where (0 h22 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 to say, (D, is compatible if there exists nonempty sets Tn. such that
sup R((O9)) S0 as
72 - 00.
(1)
ET,
We call (Tn Jaza the compatibility region of (D, A). The distribution D is allowed to change with In this case, D should be understood as sequence of distributions (Dn)nii- We also allow the dimension of model parameter to be infinity or to grow with n. We omit this dependency on n when the context is clear.
Compatibility serves as minimal condition for generalization, since data distribution in- compatible with the algorithm, one cannot expect to reach small excess risk even if we allow for arbitrary early stopping. However, we remark that considering only the minimal excess risk is in- sufficient for practical purpose, as one cannot exactly find the that minimizes R(O due to the noise in the validation set. Therefore, excess risk is consistent as in Definition 3.1 The larger the compatibility region is, the more robust the algorithm will be the noise in its execution.
meaningful consider a region of time t on which the
Comparisons with Other Notions. Compared to classic definitions of learnability, e.g., PAC learn- ing, the definition of compatibility is data-specific and algorithm-specife and is thus a more fine- grained notion. Compared to the concept of benign proposed in the recent paper (Bartlett et al.) 2019), which studies whether the excess risk at f = co converges to zero in probability as the sample size goes to infinity, compatibility only requires that there exists time to derive consis- that tent 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

---

Under review as a conference paper at ICLR 2023
4 COMPATIBILITY ANALYSIS OF OVERPARAMETERIZER LINEAR REGRESSION WITH GRADIENT DESCENT
This paper mainly analyzes comparibility in the overparameterized linear regression regime. We first introduce the data distribution, loss, and training algorithm, and then present the main theorem, which provides sufficient condition for compatibility this setting.
4.1 PRELIMINARIES FOR OVERPARAMETERRIZE LINEAR REGRESSION
Notations. Let O, o, S2 denote asymptotic notations, with their usual meaning. For example, the argument On = O(b,) means that there cxists a large enough constant C, such that On S Cb,. We use $ with the same meaning as the asymptotic notation O. Besides, let || denote the & norm for vector I, and ||||| denote the operator norm for matrix A. We allow the vector to belong to countably infiniteddimensional Hilbert space H. and with slight abuse of notation, interchangeably with H. In this case, x denotes inner product and x= denotes tensor product for x; 2 E H.
R
Data Distribution. Let (2r, E RP x denote the feature vector and the response, following
a joint distribution D. Let E Elæx denote the feature covariance matrix, whose eigenvalue decomposition Σ VAVT Σiso 2 with decreasing eigenvalues \ X2 ... We
make the following assumptions on the distribution of the feature vector.
Assumption (Assumptions on feature distribution). We assume that
1. [+] =
2. A > 0, 0,E As < C. for some absolute constant C.
3. Let ã = A V x. The random vector ã has independent o., o=-Subgaussian entries?
Loss and Exeess Risk. We choose square loss as the loss function f, i.e. E(0, (x, v)) = 1/2(y- T)2. The corresponding population loss is denoted by L(0) EE(0 (x. y)) and the optimal parameter denoted by 0" - argmingeR= T.(0). We assume that ||0*|| C for some absolute constant C. If there are multiple such minimizers, we choose an arbitrary one and fix thereafter. We focus on the excess risk of parameter 0, defined as
1 R(0) = ((0) - -(00) = Ely - x To) -
2 E x T - -
0-) 000 - 0*).
1
(2)
Let = y T 0- denote the noise in data point (xx y). The following assumptions involve the conditional distribution of the noise.
Assumption (Assumptions on noise distribution). We assume that
1. The conditional noise e|x has zero mean.
2. The conditional noise e|x is oy suy-uuuaaasiian
Note that both Assumption I and Assumption are commonly considered in the related literatures Barrlettt et al.
2019 sigler & Bartlett 2020 Zou et al. 2021).
Training Set. Given training set {(x,, 3/1) vi)ssis with n pairs independently sampled from the population distribution D, we define X å (æ1,.... (x))) e Raxp as the feature matrix, Y & (91.... "T E R" as the corresponding noise vector, and g A --x0* as the residual vector. Let the singular value decomposition (SVD) of X be X = U W with À = diag(u ... Mn e p l1 2
Mn.
We consider the overparameterized regime where the feature dimension is larger than the sample size. namely, p > n. In this regime, we assume that rank X) n almost surely as Bartlett al. 2019 This assumption is equivalent to the invertibility of X
22.2 for any A.
A random variable X is a-suhhaussian xx )
5

---

Under review as a conference paper at ICLR 2023
Assumption (Linear independent training set). For any p. assume that the features in the training set {01, "2,"1" :nn is linearly independent almost surety.
Algorithm. Given the dataset (x, Y), define the empirical loss function as L( _ 1 X Y 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: 1:20 is formulated as
2n
X X X0, - Y).
8,+1 = 0:
(3)
Without loss of generality, we consider zero initialization 0, sufficiently small learning rate X, 0g converges to the min-norm interpolator 0 = X (XXT)-1X
this paper. In this case, for
as goes to infinity, which was well studied previously (Bartlett et al. 2019). This paper takes one step further and discuss the excess risk along the entire training trajectory {R(O.))
Effective Rank and Effective Dimensions. We define the effective rank of the feature matrix E as
r(E) A Eiz0 A Our results on compatibility depend on two notions of effective dimension of the feature covariance Σ, defined as
Co Eisi A
kn - min
12 0: A411 S
(4)
n2
C1 Eiso 2o
h A min
120: A411
(5)
where co. C1 are constants independent of the dimension p. sample size n, and time dependency of ko, k1 on co. C1, n2, E when the context is clear.
We omit the
4.2 COMPATIBILITY FOR OVERPARAMETERIIZEI LINEAR REGRESSION WITH GR GRADIENT DESCENT
Next, we present the main result of this section, which provides clean condition for compatibility between gradient descent and overparameterized linear regression.
Theorem 4.1 (Compatibility for Overparameterized Linear Regression with Gradient De- scent). Consider the overparumeterized linear regression setting defined in sectionf..1 Let Assump- Then under the condition tion 2 and 3 hold. Assume the learning rate satisfies X 0 1
(T(E))
that Ko- O(n), ki oln), = o(n)), gradient descent is compatible with overparameterized linear regression in the region Tn = (w
namely,
sup R(O.) P. 0 as CC. tT
Furthermore, if the feature dimension p = xo and the data distribution does not change with n, then the condition ko On)) alone suffices for compatibility.
The proof of Theorem 4.1 is given in Appendix and sketched Section 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 learn- ing 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. We discuss extensions to the kernel regression setting in Appendix [B.6]
Comparison with Benign Overfitting, The recent paper Bartlett et al. (2019) studies overparame- terized linear regression and gives the condition for min-norm interpolator to generalize. They prove that the feature covariance Σ is benign if and only if
(Eizko )₂2 Ei X?
kg = o(n), R Σ
w(n), r(E) = on))
(7)
CConstants may depend on oz. and omit this dependency thereafter for clarity.

---

Under review as a conference paper at ICLR 2023
As discussed in Section 3.2 benign problem instance also satisfies compatibility, since benign over- fitting requires a stronger condition on ko and an additional assumption on Rkg (Z). The following example shows that this inclusion relationship is strict.
Example 4.1. Under the same assumption as in Theorem
1 if the spectrum of E satisfies
A ko
(8)
for some 1, we derive that ko (n). Therefore, this problem instance satisfies compatibilitty but does not satisfy benign overfitting.
Example shows the existence of a case where the early stopping solution can generalize but interpolating solution fails to generalize. Therefore, compatibility can characterize generalization for much wider range of problem instances.
Comparisons with Existing Methods. Theorem cannot be directly implied by off-the-sheli
stability- -basee generalization bounds (Hardt et al. 2016 Feldman & Vondrák 2019)) uniform convergence bounds (Koltchinskii & Panchenko| 2000; Bartlett et al.) 2017). The main reason is that both methods rely a high probability bound of the parameter norm, which requires non- trivial -atandependent and algorithn-dependent analysis. Even if this can be done, both methods will provably give looser bounds with smaller compatibility regions than that in Theorem 4. See Appendix [3. for a detailed comparison with stability-bar -basey bounds and Appendix [B.4] for discus- sions uniform convergence bounds. We also provide comparison with previous analysis of early stopping (ao et al. 2007 Lin & Rosasco 2017 Pillaud-Vivien et al. 20188) in Appendix B.5
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 to track the optimization dynamics. Definition 5.1 (Effective Dimensions). Given feature covariance matrix E, define the effective dimension l22 as
22 min 120: E S Sc2c(t,n) 1>0
En
1>1
where 02 a constant independent of the dimension p. sample size nI and time L. The term c(t, is function to be discussed later. When the context is clear, we omit its dependencies on C22 c(t, n), n, E and only denote by lzz.
Based on the effective rank and effective dimensions defined above, we provide a time-variam bound in Theorem 5. for overparameterized linear regression, which further leads to the compatibility argument in Theorem 4.1 Compared to the existing bound (Bartlett et al., 2019), Theorem [.1 focuses on investigating the role of training epoch in the excess risk, and of independent interest. Theorem 5.1 (Time Variant Bound). Suppose Assumption Given 8 (0, 1), assume that kn 2. log < E. 0
and 3 hold. Fix a function ett, n). E..0 A. for a large enough constant Then with probability at least 1 - 8, we have for any 1 E N,
R(O.) S B(O,) + ((,),,
(10)
where
1
log(t) (+)
B(O.) = 11
+
|Σ
max
(11)
N
2
kz
A n
((0,) og log
nt
(12)
c(t, n)n
'It is worth mentioning that Bartlett et al. 2019 and this paper study the generalization behavior of different models. The comparison here and in the following sections aims to validate the meaningfulness of compatibility analysis, instead of heating their results.

---

Under review as a conference paper at ICLR 2023
Table I: Comparisons of excess risk bound with Bartlett et al. (2019) and Zou al. (021). We provide four types of feature covariance with eigenvalues XR. including Inverse Polynomial
(Ax kar a > 1), Inverse Log Polynomial (Ax- (k+1) B > 1), Constant (Ax m 1 Isks n + k d, where
0), and Piecewise Constant (Ak 1 if S k I and X = -- if n², d n2,0 < I 1,9 > 1). In light of these bounds, ours outperforms Bartlett et al. (019)) in all the cases, and outperforms Zou et al. (2021) in Constant / Piecewise Constant cases < z and q < min --r, r, 9). We refer to Appendix for more details.
DISTRIBUTIONS
OURS
BARTLETT ET AL.
2019
Zou ET AL. 2021
INVERSE POLYNOMIAL
n min o-1
(())
0 a-1
INVERSE LOG POLYNOMIAL
(()
0 les n
log n
CONSTANT
O n
O nn- min (eim(e)t))
o
(n min(e.1)
O (n min( (1-1 (n-mii(--r--111))
O n2 min (1
min -
PIECEWISE CONSTANT
We provide a 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 lcading part and tailing part based on the sprctrum of the feature covariance Σ. The cigenvalues in the tailing part will cause the variance term in the excess risk of the min-norm interpolating solution to be 22(1) ) for fast decaying spectrum, as is the case in (Bartlett al. 2019). However, since the convergence in the tailing eigenspace is slower compared with the leading eigenspace, proper early stopping strategy will prevent the overfitting in the tailing eigenspace and meanwhile avoid underfitting in the leading eigenspace.
The c(l, Principle. It is worth emphasizing that our bound holds for arbitrary positive function ctt, n). Therefore, one can fine-tune the generalization bound by choosing a proper e(t, n). In the subsequent sections, we show how to derive consistent risk bounds for different time t, based on different choices of nt), We present the case of choosing a constant c(t, n) in the next section. We leave the case of choosing a varying c(t, n) to Appendix B.7
5.2 VARYING t, CONSTANT c(t, n)
Theorem 5.1 provides an excess risk upper bound uniformly for E N. However, is still non-trivial to derive Theorem 4.1 where the remaining question is to decide the term c(t, n). The following corollary shows the generalization bound when setting c(t, n) to a constant.
Corollary 5.1 (Constant c(I, n)). Let Assumption 7 and 3 hold. Fix constant c(t, n). Suppose
Eiso.. Then there exists sequence of positive constants {6, hnz0 which converge to O, such that with probability at least 1- 8m, the excess risk is for E (w (2) ( i.e
ku- = On), h o(n), r(E) = o(n), X O
R(O,) = o(1).
(13)
Furthermore, for any positive constant 6, with probability at least ō, the minimal excess risk on the training trajectory can be bounded as
max / Vr(E),1)
max (ki, 1}
min R(O,) S
(14)
Lemma 5.1
below shows that k = o(n) always holds for fixed distribution. Therefore, combining Corollary 5. I and 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] we have (n) (n)= o(n).
Example Distributions We apply the bound in Corollary 5.1 to several data distributions. These distributions are widely discussed in (Bartlett et al. 2019 You et al. 2021). We also derive the
8

---

Under review as a conference paper at ICLR 2023
Table The efffective dimension k1, 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 1 and excess risk of early stopping solution. We calculate the 95% confidence interval for each excess risk.
DISTRIBUTIONS
k1
OPTIMAL EXCESS RISK
MIN-NORM EXCESS RISK
A
2.399 0.0061
24.071 + 0.2447
A
0.214 1: 0.0050
43.472 + 0.6463
A
0.077 + 0.0005
10.401 + 0.2973
A (lg((++1)
0.697 0.0053
89.922 + 0.9591
Tog m
À Tlog-(14)
0.298 + 0.0054
82.413 + 0.9270
log
A flog (++1)
0.187 + 0.0047
38.145 + 0.5862
log
existing excess risk bounds, which focus on the min-norm interpolator (Bartlett et al. 2019) and one-pass SGD iterate Zou et al., 202T), of these distributions and compare them with our theorem. The results are summarized in Table [ which shows that the bound in Corollary 5. outperforms previous results for general class of distributions. We defer the details Appendix
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 = 100. 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 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 signif- icantly 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 properties. This observation corroborates the meaningfulness of compat- ibility and the importance of data-dependent training trajectory in generalization analysis.
Observation Two: The faster covariance spectrum decays, the lower optimal excess risk is. Table 2 also illustrates a positive correlation between the decaying rate of X and the generalization performance of the early stopping solution. This accords with Theorem 5.1 showing that the ex- cess risk is better for smaller effective dimension k1, where small k indicates a faster-decaying eigenvalue A, We additionally note that such phenomenon also illustrates the difference between min-norm and early stopping solutions in linear regression, since Bartlett et al. (2019) 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.
7 CONCLUSION
In this paper, we propose the concept of data-algorithm compatibility, and study compatibility for overparameterized linear regression with gradient descent. Our theoretical and empirical results demonstrate that compatibility eases the assumptions and broadens the scope of generalization by fully exploiting the data information and the algorithm information. Despite lincar cases in this paper, compatibility can be much more general concept. Therefore, we believe this paper will motivate more work on data-dependen trajectory analysis.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Alnur Ali, J. Zico Kolter, and Ryan J. Tibshirani. A continuous- view of early stopping for least squares regression. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Oki- nawa, Japan, volume 89 Proceedings of Machine Learning Research, pp. 1370-1378. PMLR, 2019. URL
mlr. wwwpsp/eeeee...p. (1t/9//al19aaaaaee.
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 (eds.), Proceed- ings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learming Research, pp. 254 PMLR, 2018. URL httttt:::p/poooeeeggggee ml wtt.ssmww.p.....eeeeeeeemeeeeee arraaaa00/ara1000
html
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine- Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, California, USA, volume 97
of Proceedings of Machine Learning Research, pp. 322-332. PMLR, 2019. URL http:// proceedings www.:..r...rr.e...mmm.m..em.m..e wtt////raaaa... 9a html
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.158553 2021. [tthtt::::/
15853
15853
Pradeep Kr. Banerjee and Guido Montúfar. Information complexity and generalization bounds. CoRR, abs/2105.017747 2021. URL httttttts///aatiii wttp:///////......./1111
Peter L. Bartlett, Dylan J. Foster, and Matus Telgarsky. Spectraaly--normalieed margin bounds for neural networks. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Gareet (eds.), Ad- vances in Neural Information Processing Systems 30: Annual Conference formation Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 6240-6249, 2017, URL https::/ neurips........pp.pp...........e https////oeoa.arrrsrsooooo/////a htc/papprr/011//ee b22b257 9d4 50w530033300cccceccoo Awwttt-ttttttttttaee.acaaaacee.e html
Neural In-
Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. CORR, abs/1906 1300, 2019. URL bttp:: wttp://wwww...or//////./.... 11300
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Had- sell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Process- ing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 12, 2020, virtual, 2020. URL https: http::t:/ppppceeeea http::////ccceeeeeeeeeee www.ips.eerrrpr.ooe.oo. 2dd5e 36d Abst ract html
Saper/2020/hashi 2eere22222222 wwwe:ccccccccaaa4440c 2ec.eeeaaaeaaa22aaeeeeeeeeeeeeee
Gilles Blanchard and Nicole Krämer. Convergence rates of kernel conjugate gradient for random design regression. Analysis and Applications, 14(06):763-794, 2016.
Olivier Bousquet and André Elisseeff. Stability and generalization. J. Mach. Learn. Res., 2:499-526, 2002. URL /ttt:t//p///1 httpa////aaaeeee//////////ee//// html
Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Jacob D. Abernethy and Shivani Agarwal (eds.), Conference Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event /Gruz, Austria), volume 125 of Proceedinggs of Ma- chine Learning Research, pp. 610-626. PMLR, 2020. URL httt::/pproceette igg..nggg... mmlr. wtsss//125/bbosquue
html
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh,
10

---

Under review as a conference paper at ICLR 2023
Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCan- dlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models few-shot learners. In Hugo Larochelle,, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL 1457c0d6bf cb 967477777 www.baaacc22fe0 Abst .ttl
Jacob Devlin, Ming- Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers), pp. 4171- 4186. Association for Computational Linguistics, 2019. doi: 10.18653/11/199-44223 URL
http::::/ddo..rrg////
Aymeric Dieuleveut and Francis Bach. Nonparametric stochastic approximation with large step- sizes. The Annals of Statistics, 44(4):1363- 11399999999999--111 2016.
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 (eds.), Proceedings of the Thirty-Third Conference on Uncertainty Artificial Intelligence, UAI 2017, Sydney, Australia, August 11-15, 2017, AUAT Press, 2017.
Noureddine El Karoui. The spectrum of kernel random matrices. The Annals of Statistics, 38(1): 1-50, 2010.
Vitaly Feldman and Jan Vondrák. Generalization bounds for uniformly stable algorithms. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Con- ference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 9770-9780, 2018 URL http:::s//ppoceeednng. neuriss...rrpp... paper/2018/har haathhh/Soa21116666667333888888 ott.eeeeeeccccccaaaaaaett.tt.e.e www.:abaaad--.ttttttt......
Vitaly
Feldman and Jan Vondrák. High probability generalization bounds for uniformly sta- ble algorithms with nearly optimal rate. In Alina Beygelzimer and Daniel Hsu (eds.), Con- ference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pp. 2270-1279 PMLR, 2019. URL http: //proceedings . mlr. wwwpppeessssvv... /3/ www.eeedealllemmmmmmmmmmmmaaamma www.daannnana..aammmmmmmm html
Mahsa Forouzesh and Patrick Thiran. Disparity between batches as a signal for early stopping- In Nuria Oliver, Fernando Pérez-Cruz, Stefan Kramer, Jesse Read, and José Antonio Lozano (eds.), Machine Learning and Knowledge Discovery 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, pp. 217-232. Springer, 2021, doi: 100/ 00--3-000-6552-777 14. /ttp://pp//.oo..ooo////...////33
URL https:: /ttp///oiiiaoo wrt. 200.10...10..0000 3-
14
Spencer Frei, Niladri Chatterji, and Peter I.. Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. CoRR, wbwp:aa2..//99////// 2022. [tttsss::://arx/ o abs 2202. 05928
L. Lo Gerfo, Lorenzo Rosasco, Francesca Odone, Ernesto De Vito, and Alessandro Verri. Spectral algorithms for supervised learning. Newral Comput., 20(7):1873-1897 2008 doi: 10.1162/neco. www.orgg/11... www.1112nneee 2008. 05-07-517
2008.05-07-517. URL httttt:t:://ec
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 (eds.). 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, pp. 1225-1234. RMLR.org. 2016. JRI.tttp htttt::/proccedd:: ngs.eediddnnnmmmmm... wtt.seeww..prr..eeeeeeeeee 8/aa rdt 16. html

---

Under review as a conference paper at ICLR 2023
Wei Hu, Lechao Xiao, Ben Adlam, and Jeffrey Pennington. The surprising simplic- ity of the early-time learning dynamics of neural networks. In Hugo Larochelle, Mare' Aurelio Ranzato. Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neu- ral Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, vir- wwtpppppppw//////eeeeeeepe
tual, 2020. URL ottps::/prroeeddngs..o
c6dEc6b7c601ac29 1118833777881eeee Abstrelaaeaaaeeetatttttt
Abstract. html
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kemel: Convergence and generalization in neural networks. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Anmual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 5580-8589, 2018. URL abt.eeeeet.t.eteotttaattttttteaa 5a aet.aeeeeeebaaeeeeeeeeeeee
neurips.............p........... CC caassscccpppppa pttppppppp//paaaeeeeee Abstract.
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 Wortman
Vaughan (eds.), Advances in Neural Information Processing Systems 34: Anmual Conference on
Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp.
1805-1817, 2021. URL httppsss/pprrccceednggg// neer.. http://pwwcccccnrre.eeeeeeesespp 0e
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. httphhttt///ppee/e www.e...rvii....mm.. net fentt/forumiicom www.uumiiddsggPPPPP JBBVH
Vladimir Koltchinskii and Dmitriy Panchenko. Rademacher processes and bounding the risk of function learning. In High dimensional probability 11, pp. 443 457. Springer, 2000.
Iia Kuzborskij and Csaba Szepesvári. Nonparametric regression with shallow overparameterized neural networks trained by GD with early stopping. In Mikhail Belkin and Samory Kpotufe (eds.), Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pp. 2853-2890. PMLR, 2021. m.r.. http://..........////////ooo.oa. j2la. html
URL
Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. 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, pp. 5809-580588 PMLR, 2020. httl:http//proceeee lei20c. htmll
mlr. press/v119/
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, 2020a. URL https:// openreview net/ wt/./oorrmm//// Seerrummmiiikxee Skxxsx
Jangyuan Li, Thanh V. Nguyen, Chinmay Hegde, and Ka Wai Wong. Implicit sparse reg- ularization: The impact of depth and early stopping. In Mare Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Ad- vances in Neural Information Processing Systems 34: Annual Conference on Neural Infor- mation Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 28298 28309, 2021. URL
neurips. cc wtt.cc/pppaaa http//ppprr22..... / 1e1166629.0000111eeeeefeeferr..3 Abst html
Mingchen 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 (eds.), 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, pp. 4324. PMLR, 2020b. URL http: //proceedings.. ml I wwwpppaswl0///// wtt.://igg..m.....aaaaeaamaae.
html
12

---

Under review as a conference paper at ICLR 2023
Zhu Li, Weijie Su, and Dino Sejdinovic. Benign overfitting and noisy features. 102000, 2020c. BtRt::tp:://aat wwwpxiioog//abs//0000 02901
CoRR,
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "rddee"iigeeees"" regresssoo
regression can gener-
alize. CoRR, abs/ 000800037,, 2018. /ttp:tpp:/a.....////ataaaee
Junhong Lin and Volkan Cevher. Optimal rates for spectral algorithms with leat-sss-suee regression over hilbert spaces. CoRR, Abs/1801.067220 2018.
URL http://arxiv.orgg
abs/1801. 06720
Junhong Lin and Lorenzo Rosasco. Optimal rates for multi-pass stochastic gradient methods J. Mach. Learn. Res., 18:97:1-97:47, 2017. URL
17-176. html
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 wwt.itttps///.. http::::////peeevievwee net/ forum?ic GJKPS
Kaifeng Lyu, Zhiyuan Li, Runzhe Wang, and Sanjeev Arora. Gradient descent on tWO- layer nets: Margin maximization and simplicity bias. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Ad- vances in Neural Information Processing Systems 34: Annual Conference
Neural Infor- mation Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 12978- 12991, 2021. URL /tetps::/proceedee www.iggsn.uuiip...m wttpuuiissccppppppeeeeepe wwwpppppee///////aa...... 6c351da 0at.eee8e74422222222666666222200 htt.ra/eeesd--ttttcttt..... html
Abstract
David A. McAllester. Simplified pac-bayesian margin bounds. In Bernhard Schölkopf and Man- fred K. Warmuth (eds.), 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 URL
Computer Science, pp. 215.215. Springer, 2003. doi: 1007 / 3 5-0-544051111
https: or
David A. McAllester. A pac-bayesian tutorial with A dropout bound. CoRR, abs/ 1307,2188 2013.
htt http: www.wawwwww...a..aaaaaaaaaaaaaaa
org wttpor/g/abbb///// 1111..1188
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667-766, 2022.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. Adaptive computation and machine learning. MIT Press, 2012. ISBN 978-0-262-018225- URL
http::/mitpreet
mit wew//bookkke foundat http://aaaaiiiinanaannnneeeeeeaa
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 (eds.), Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, volume 75 of Proceedings of Machine Learning Research, pp. 605-638. PMLR, 2018. URL. Ba .ttml
httt:://proceets ngs. m wwwpss//s//mmmmm
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 (eds.), 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, pp. 11611-11622, 2019. URL
http://roooeiinnn...e.....p neurips wttppppscccppppppp..... Abt.:sbbbbbbbtttt....... html
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 Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 7263-72277 7272. PMLR, 2020. URL U httphhtt:p/ppcceeiiiipp ngs ml wttps///v1///erreeeeeeee html http://wee...ao.o...ppprr///////
Machine Learning, ICML 2020, 13-18 July 2020,
13

---

Under review as a conference paper at ICLR 2023
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally noraalied margin bounds for neural networks. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL htttps:///penrevieew /
Forum?id=Ske WfbCZ
Emilio
Amiran Ambroladze, John Shawe-Taylor and Shiliang Sun. Pac-bayes bounds with data dependent priors. J. Mach. Learn. Res., 13:3507-3531, 2012. URL http:
María Pérez-Ortiz, Omar Rivasplata, John Shawe-Taylor, and Csaba Szepesvári. Tighter risk cer-
tificates for neural networks. J. Mach. Learn. Res., 22:227:1-227:40, 2021. URL http:
//jmlr /tmp.r..rrr//apprr/////0//000--/
html
Loucas Pillaud- Vivien, Alessandro Rudi, and Francis R. Bach. Statistical optimality of stochastic 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 (eds.), Advances in Neural Information Processing Systems 31: Anmual Conference on Neural Infor- mation Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 8125 8135, 2018. URL
mew.eeiddiiinnnn.nnnee.eee...eee pwtppaapee/211//eae.es. html html
Lutz Prechelt. Early stopping but when? In Grégoire Montavon, Genevieve B. Orr, and Klaus- Robert Müller (eds.), Neural Networks: Tricks of the Trade- Second Edition, volume 7700 of Lec- fure Notes in Computer Science, pp. 53-67. Springer. 2012. doi: 10. 10.1007/978-3-64--355555 642 35289-8522888855
5.
URL /tt.:/ttpp////...o/////0/0..
Garvesh Raskutti, Martin J. Wainwright, and Bin Yu. Early stopping and non-parametric regres- sion: an optimal data-depnndent stopping rule. J. Mach. Learn. Res., 15(1):335-366, 2014. doi: 10.5555/2627455.2666 266774444...6 URLhttps: //dl acm. /tt.//o001.....5//22223
2627445 6
Omar Rivasplata, Ilja Kuzborskij, Csaba Szepesvári, and John Taylor. Pac-bayes analysis be- yond the usual bounds. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- - Lin (eds.), Advances in Neural Information Processing Systems 33: An- nual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-122 2020, virtual, 2020. URL
neur....eeepppp.. ips.. htcpsscccceeeo
CC/ cc/ppaperr/222//aa...
c3992e9a68c5en 2bd 848 7ttaBBBcccc77b0000abbbbbeeee html
Lorenzo Rosasco and Silvia Villa. Learning with incremental iterative regularization. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 28: Annual Conference on Neural In- formation Processing Systems 2015, December 7-12, 2015, Montreal, Quebec. Canada, pp- 1630 1638, 2015. URL URL/hattps///pprccdddagg htwpeeedddiisss..eiiieeeee newninnripp. http://sssaoooorrrr/aa/////////a html
Daniel Russo and James Zou. Controlling bias in adaptive data analysis using information theory. In Arthur Gretton and Christian C. Robert (eds.), Proceedings of the 19th International Conference Artificial Intelligence and Statistics, AISTATS 2016, Cadiz, Spain, May 9-11, 2016, volume 51 of JMLR Workshop and Conference Proceedings, pp. 1232-1240. JogR. 2016. htttttp: 7/proceedin ngs. wtt..mmww....s/////m.. wttpee///ll//ouaaaaseee
html
Matthias W. Seeger. Pac-bayesian generalisation error bounds for gaussian process classification. J. Mach. Learn. Res., 3:233 209, 2002. URLpttp: http://aww..ogoppppp//////////e/
html
Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateek Jain, and Praneeth Netrapalli, The pit- falls of simplicity bias in neural networks. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Had- sell, Maria-Florina Balcan, and Hsuan-Tiees Lin (eds.), Advances in Neural Information Process- ing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12 621 2020, virtual, 2020. URL ht http::/:///ppppppppeeeeeeee / .hmt.
neurips.co/
14

---

Under review as a conference paper at ICLR 2023
Vaishaal Shankar, Rebecca Roelofs, Horia Mania, Alex Fang, Benjamin Recht, and Ludwig Schmidt. Evaluating machine accuracy on imagenet. In Proceedings of the 37th Interna- tional Conference Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, vol- ume 119 of Proceedings of Machine Learning Research, pp. 8644-8644. PMLR, 2020. URL httt::/ppocceett
ml www..r..sssse.. vvll 9/ wwwanaaa0c.ccncecceeeee html
John Shawe- and Robert C. Williamson. A PAC analysis of bayesian estimator, In Yoav Fre- und and Robert E. Schapire (eds.), Proceedings of the Tenth Annual Conference on Computational Learning Theory, COLT 1997, Nashville, Tennessee, USA, July 6-9, 1997, pp. 2-9. ACM, 1997. doi: 10.1145/267460.267468
BRLpttts://aoi.....
267466
Ruoqi Shen, Liyao Gao, and Yi-An Ma. On optimal early stopping: Over-informmative versus under- informative parametrization. CoRR, abs/2202.09885, 2022.
URL. https://arxiv.oo
abs abs/2202. 09885
David Silver, Julian Schrittwieser, Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy P. Lilli- crap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game of go without human knowledge. Nat., 550(7676):354-399 2017. doi: 10. n0.10388/ature24270.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, and Nathan Srebro. The implicit bias of gra- dient descent on separable data. 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. /tt.pps://penneeeerte net/ fow.mmddddrgggnn
OpenReview.net, 2018. httpss/:::// /ttps://oppeeeveeeeeeee
Pierre Stock and Moustapha Cissé. Convnets and imagenet beyond accuracy: Understanding mis- takes and uncovering biases. In Vittorio Ferrari, Martial Hebert, Cristian Sminchisescu, and Yair Weiss (eds.), Computer Vision ECCV 2018 15th European Conference, Munich, Ger- many, September 8-14, 2018, Proceedings, Part VI, volume 11210 of Lecture Notes in Com-
puter Science, pp. 504-519, Springer, 2018. doi: 10. (00799788-30030000231111111
URL
001---0000---011---3333333333 https://doi. org. 00t.:/00000000000000000000002000
Pierre Tarres and Yuan Yao. Online learning as stochastic approximation of regularization paths: Optimality and almost-sure convergence. IEEE Trans. Inf. Theory, 6019):5716-5735 2014. doi: 10. N0.11099/T..2211.233222
Jiaye Teng, Jianhao Ma, and Yang Yuan. Towards UKL/attpes//axxiv.orr///////// cess risk dynamics. CoRR, abs/2106.06153, 2021.
via decopp ex-
06153
Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. arXiv preprint arXiv:2009. /4286, 2020.
Tomas Vaskevicius, Varun Kanade, and Patrick Rebeschini. The statistical complexity of early- stopped mirror descent. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: An- nual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020. http:tts////rrrcediingggo neur ips. cc pttp//apper2222/ath... 02422
Abst html
Ke Wang and Christos Thrampoulidis. Benign overfitting binary classification of gaussian mixtures. In IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2021, Toronto, ON, Canada, June 6-11, 2021, pp. 4030-4034. IEEE, 2021. doi: 10. RBBpICCASSP3972.2221..999 2021.941399
hRL/httss://doi... 1tt.://00..100//AA33337700
Aolin Xu and Maxim Raginsky, Information-theereiicc analysis of generalization capabil- ity of learning algorithms. In Isabelle Guyon, Ulrike von Luxburg. Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan. and Roman Gamett (eds.), Ad- vances in Neural Information Processing Systems 30: Annual Conference on Neural In- formation Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp-
15

---

Under review as a conference paper at ICLR 2023
2524-25333 2017. URL http:://wpoccoceooo...eees/sssss
447756652224555533333366166----- .tml
Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On early stopping in gradient descent learn-
ing. Constructive Approximation, 26(2):29-315, 2007.
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 la- bels. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19-25, 2021. pp. 2340-2350. Computer Vision Foundation / IEEE, 2021. URL https: /pppss:s//penaccssssss theccf. com/ http://onnnnn///22211/6///
/Yun.
Re-Labe La-Laabelinn ImageNet From Single to Multi- From Global to
Localized CVPR 2021_222110 www.ppappp.p..
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Commun. ACM, 64(3):107-115, 2021.
doi: 10.1145/344677. htttp::/s///.... 1tt..o/.....1//446777777
Lijia Zhou, Danica J. Sutherland, and Nati Srebro. On uniform convergence and low-norm in- terpolation learning. Hugo Larochelle, Marc Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: An- mual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. /tpLLtttps//pppoceiiigg.ot newriisss 62 4 Fodo Abs httppe/www.ss.apoopp////////a/aa
Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham M. Kakade. Benign over- fitting of constant-stepsize SGD for linear regression. In Mikhail Belkin and Samory Kpotufe (eds.), Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pp. 4633-4635 PMLR, 2021. URL htt.http:/// httt:://proceeding.. m. wttps///13///002222222 html
16

---

Under review as a conference paper at ICLR 2023
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.5 are devoted to the proof of Theorem 5.1 The proof of Theorem 4.1 is given in A.6
A.1 PROOF SKETCH
We start with a standard bias-variance decomposition following Bartlett et al. (2019), which derives that the variant excess risk R R(+)) can be bounded by 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, use the spectrum analysis to bound it with O (1/l) where / denotes the time. For the approximation error, we bound it with O (1/vn)) where n denotes the sample size, inspired by Bartlett et al. (2019). We refer to Appendix AA.4 for more details.
For the variance part, a key step is to bound the term (I a x where X is the feature matrix. The difficulty arises from the different scales of the eigenvalues of XXT, where the largest eigenvalue has order (n) while the smallest eigenvalue has order O11), according to Lemma 10 in Bartlett et al. (2019). To overcome this issue, we divide the matrix X.X based whether its cigenvalues larger than c(t, n). which flexible term dependent on time and sample size n. Therefore, we split the variance term based on eigenvalues of covariance matrix E (leading to the -rerelee term) and based on the eigenvalues X (leading to the kzz-ellated term). We refer to Appendix A.5 for more details.
A.2 PRELIMINARIES
The following result comes from Bartlett et al. 2019). which bounds the eigenvalues of XXT..
Lemma A.1. (Lemma 10 in Bartlett et al. (2019) For any oz there exists constant such that for any S ks n, with probability least
Σ As + ARtIn Ki
pa+1 Sc
(15)
This implies that as long as the step size À is small than a threshold independent sample size n, gradient descent is stable.
Corollary A.1. There exists constant such that with probability at least e ;; for any 0 < X S Ei we have
0 - n
(16)
Proof. The right hand side of the inequality is obvious since À > For the left hand side, we have to show that the eigenvalues of X X is non-negative. since T X and X have the same non-zero eigenvalues, know that with probability at least - = the smallest eigenvalue of 2 X can be lower bounded by
(Eizods + Aat1) 21 2cA Σ 2
#n 2 - cA
(17)
150
where the second inequality uses lemma A.1 and the last inequality holds if X 5
2c
2c
17

---

Under review as a conference paper at ICLR 2023
A.3 PROOF FOR THE BIAS- VARIANCE DECOMPOSITION
Let X denote the Moore-Penrose pseudoinverse of matrix X. The following lemma gives closed form expression for t,.
Lemma A.2. The dynamics of (0r)120 satisfies
0: I -I-AX''
X x x
(00- (00-x')) + +
(18)
Proof. We prove the lemma using induction. The equality holds at / 0 as both sides are Og. Recall that 0g is updated as
8,+1 = 0: + A x (Y X0,).
(19)
Suppose that the dynamic holds up to the f-th step. Plug the expression for 0, into the above recursion and note that X Xxt XT, we get
A x
O++1
I
x
X
0,
1+1
(0o -xtY)+ + (1-2xTx) x + x
x X
(20)
1+1
xTx)
x
x
(0o -X
n
which finishes the proof.
Next we prove two identities which will be used in further proof.
Lemma A.3. The following two identities hold for any matrix X and non non-negative integer t:
I- I-XiX + (I [ x1=xxx)= x = x
(1_2xTx)
(21)
I 1 2 n
(1-xxxx)xxxxX-
XT [- 11-1--xxa 1-(1-2xx-)
(22)
Proof. Note that X XT, expand the left hand side of the first identity above using binomial theorem and eliminate the pseudo-inverse Xt:
I- X-x + [ xxxxxx
x
xtx
A A x
=I X
+
xix
k=
() (XTX)*-IX* xxlx
= II- X
x
(23)
A * (xT x)*
(1 1- > x (1~XXXx) x
18

---

Under review as a conference paper at ICLR 2023
The second identity can be proved in similar way:
i - 1 xxTx)
Xxixx'
[-_x xxxx)
A
xIxxT
k3
Σ
A
XXXXXXX
k
n
(24)
(x
Σ
XXXI
k
X T
I
1
1-=xx²)]
A
We 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,) s 0-
T BO +E² Ce, TCE
(25)
where
- x x E
X -x xxTx)²
(26)
T
n
(-
C C= -=(XXT)-
I (1-
XEXT XXXXT
(11112xxx)
1- (1 nh
(XXT) (27)
which characterizes bias term and variance term in the excess risk. Furthermore, there exists con- stant such that with probability at least - 5 over the randomness
have
1 T Ce S co log z Tr[C].
E
(28)
Proof. First note that X X
is invertible by Assumption
Express the excess risk as follows
R(O.)) B[(y - x T 0.)² - (y x TT
E((y x 0 0- x 0,)2 (y x )²)
(29)
B[(x T(,, 0²))² + 2( Tz) 0" x TOO]]
E[x T (0, 0²)
2
Recall that 0 = 0 and Y X0 + e and we can further simplify the formula for 0, in lemma A.2
X A xxxx) (0o x
0:
(30)
I I xxxx) x! x( +e).
19

---

Under review as a conference paper at ICLR 2023
Plug it into the above expression for R(O,). we have
2
1
2 x
xxxxXXx
- x
R(O,))
E
+6) xx
2
n
(1-2xtx)
E
x
xix -1) 0r
(31)
2
n
xte 1
A xxxx)
+
I
I
Applying lemma A.3
obtain
1
I 1-11- x=2xxx)|(xxa (XXT)
2
R(O,)
E2
x
x
x
x
+ + X
π
n
2
(XXT )
2
S E
T
x
x
0"
+ E
8 T X
(
I I -11-
= 0- B0 + e Ce.
(32)
which proves the first claim in the lemma. The second part of the theorem directly follows from
lemma 18 in Bartlett et al. (2019).
A.4 PROOF FOR THE BIAS UPPER BOUND
The next lemma guarantees that the sample covariace matrix J x Lemma A.5. (Lemma 35 in Bartlett et al. (2079)) There exists constant such that for any 5 1 with probability as least 0,
concentrates well around
1 X T
r(E) n
( log( ) π
log( !
<dEi
max
(33)
n
n
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
|P|| S 1, we have
P(1 PY1 1
(34)
Proof. Assume without loss of generality that P diagonal. Then it suffices to consider seperately each eigenvalue of P, and show that a01 o) o)
< 1.
In fact, by AM-GM inequality we have
(1-o)² to + (1 o)t t+
S 7.
(35)
1+1
which completes the proof.
Next prove the main result of this section.
Lemma A.7. There exists constant e such that if 0 < X < E X, then for any 0 < < 1, with
probability least 8 the following bound on the bias term holds for any t
(1) Nt
1) (36)
Σ
log( 7
log(
T B0 <c|10-11
+ +||||aaa max
20

---

Under review as a conference paper at ICLR 2023
Proof. The bias can be decomposed into the following two terms
0 B0
0
(I
- x
x
E
x
x
-1-xXXx
A x x ))'
0-
(37)
21
+ rT
-x x
I
x
X
0".
7
n
For sufficiently small learning rate given by corollary
A.I
know that with high probability
x
x
S 1,
(38)
which together with lemma
A.5
gives high probability bound on the first term:
T-
-
x
x
Σ
1
x
x
x
X
n
(39)
r Σ
r(E)
log(
1
log( 1)
S 1011
max
For the second term, invoke lemma
A.6 with P
1 X
X and we get
TT x T x
x x -1-xx2
(1 I- n
21
0
$ 10 1|
\ x x
(I-xXXx)
d x-=xXxx
x)
)
26
n
(40)
<
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 U T the singular value decomposition of data matrix X, where U (u1,-.., un.) W (Wi,"*. ... w.), A (Ma. Ma. with μn 2 u2 2 ... ... Pn-
Recall that
Eisid, di
kn min(1 2 0: At41 S
n
C Eiso di }
h min(1 2 0: A141 S
(41)
22 min(! 0: Σ
A + nd4+1 S c2c(t,n) Eitl
i>1
120
for some constant Co, C1, 02 and function e(t,n).
We further define
hg min(! 0: 1441 5 c3c(l,n) EdeL.
(42)
i>
for some constant C3.
The next lemma shows that we can appropriately choose constants to ensure that ka S h2 holds with high probability, and in some specific cases we have li < ki.
Lemma A.8. For any function e(t, n) and constant cz2 there exists constants Ca. such that lts S ba with probability at least e E. Furthermore, if c(t, n) is positive constant function, for any Cy there exists C2 such that k < ki-
21

---

Under review as a conference paper at ICLR 2023
Proof. According to lemma A.1 there exists constant c, with probability at least 1 c we have
Mb2+1 S cl Σ X ndb2+1) I cogolt, n)
Σ A
(43)
12
$>0
Therefore, we know that kg S K2 for cg = 002.
By the definition of ,i, we have
Σ 1
> n S ((1 + +1)++1 11 A
(44)
$20
which implies that l2 S ky for 02
if c(t, n) is positive constant. c(tm))"
g++1
Next bound Tr(C], which implies upper bound the variance term.
Theorem A.1. There exist constants c, Co, 01 02 such that if ko S ". then with probability at least e 2, the trace of the variance matrix C has the following upper bound for any
k1 + Tr|C] Sc
k2 + cll,n))
At Y1
A
(45)
n n),
8>0
Proof. We divide the eigenvalues of XX T into two groups based on whether they are greater than Csc(t, n) Σixo As. The first group consists of μ1 ... Mky and the second group consists of Mkg+1 pn. For 1 S lig we have
1- (1 11) 1.
(46)
Therefore we have the following upper bound on I- 1- -11-2xxT)
2 xx
xxx))
)
n
1 1- 11 |
Udiag
Mnn
U
n
n- Ry times
kg times
2
>
3 Udiag
1
n 1kk+1
1
1
UT
12
(47)
ks times
n ky times
Udiag
UT
n kg times
ka times
?
+ Udiag
O....O. O,
- Mks++
-
Un
UT.
For positive semidefinite matrices P, Q, R which satisfies Q Q= R. holds that Tr S Tr|PR It implies the following upperbound of Tr(C]:
22

---

Under review as a conference paper at ICLR 2023
Tr(C]
xx )7²
11-xxx n
(XXx)~ XEX XXX
Tr
Ng times n ki times
Tr
Udiag
0....
U (xx1)² - XEX
T2 Ry times
ky times
2
+ Tr Udiag
0,...0.
m MKs++
72 Um
U (XXT) -2
XEXX
(48)
Bounding !
Noticing X = U and Σ = EiSI Noana we express the first term sums of eigenvector products,
kg n kg times
1 Tr Udiag
1.... 1, .....
U (XXX) XEXT
kg n ki times
Tr
U diig
0.
U UU T
hg
n ky
Tr
diag
1,... 1
0,
'w''i EW
(49)
ky n times
Σ A Tr
diag
0 0.... 0
A W T-
W
21
Σ
(u. w,)
Ky
21
15ick3
Next divide the above summation into
< hn and i >> k1- For the first part, notice that
Σ
A
(o.
2 A
<
(,,Tw))
M3
15
15j5n
Σ
1 w
v
M4
(50)
15jsn
AoTTWA WT v.
AoYY A UA- U0 TUA
= -R&T
-22,,
where à; is defined as क;
X Ax
U A T
VA
(019). we know that for any o., there exists a constant Op and such that if ko < 2 with probability at least the first part can be bounded
From the proof of lemma 11 in Bartlett et al.
23

---

Under review as a conference paper at ICLR 2023
N ΣΣ (o
Σ
1 30.
c
(51)
ISiSk 15iSky" Pj
71
1sigk
which gives bound for the first part.
For the second part we interchange the order of summation and have
Σ 2
E
A U. w/) 2
(v, w);)
ISiSks
S Ki
12
Σ
E
A (0, w; 2
c30l1, n) Eiso Ao
Isiska 12
Aki+1
(0 w.
czc(t, n)
Ei>0 A1
15i5ks 12
(52)
AkIt1
cac(t, n) Σiso Aa
15isks
Ak
cgclt, n)
Eiso
h3
n(t,n)n
for large enough.
Putting 51 and 52 together, and noting that K3 < k2 with high probability as given in lemma A.8 we know there exists a constant e that with probability least 1
1 S h1
12
+
(53)
n
n)t
Bounding 2
Similar to the first step in bounding !, we note that
ky
Ky times
2
1 (1
A
)
2 Tr Udiag
0,...0.
Mks++
1
1
pnn
n
n
U U UU TT
12- Ry times
kg times
1 - (1
X
)p:
1
(1
A
}
Tr diag
0,
Mka+1
1 -
Mks+1
n
pn
n
W T Σw]
(54)
From Bernoulli's 's inequality and the definition of K3, for any Kg + +11 S J S n, we have
1 -
1
A
1kk
2
<
1
()
( (utt) =
2
A 2
12 #k
W C3
(M)) (Al)
2
c(t, n)
Σ dis
(55)
n
1>0
Hence,
24

---

Under review as a conference paper at ICLR 2023
(1
c3)(l,
Σ a
TH WW]
(56)
At
c3c(t,m)
A4
120
Putting things together
From the bounds for ! and ( given above, know that there exists constant such that with probability least 1 e the trace variance matrix has following upper bound
Tr[C] se
ki +
22 c(t,n)n
+ c(t,n)
Σ Aa 120
(57)
Lemma A.4 A.7 and Theorem A.1 gives the complete proof. Note that the high probability events in the proof independent of the epoch number I, and this implies that the theorem holds uniformly for all E N.
Proof of theorem 5.7
A.6 PROOF oF COMPATIBILITY RESULTS
Corollary A.2 (Corollary 5.1 restated). Let Assumption
2 and hold. Fix a constant c(t, n). Then there exists a sequence of positive constants In20 which converge to O, such that with probability at least 8n, the excess risk is consistent for I E (w (+) (²)),, i.e.
Suppose ko On), k o(n), r(E) o(n).
E.so
R(O:) = o(1).
Furthermore, for any positive constant 6, with probability at least 6, the minimal excess risk on the training trajectory can be bounded as
max Vr(E),1)
max (aax(11,
min R(O,) S
vn
n
Proof. According to Lemma all
A.7
with probability at least 1 fu 2.
the following inequality holds for
1
r(E)
r(2) Σ
log( o.. log( 6.
B(O.) x
+
max
(58)
X
n
n
n
n
5n chosen such that log bn
on). we have that with probability at least 1
8
we have for
2.
all / (+):
B(O.) o(1),
(59)
in the sample size n.
When c(t, nt) is constant. we have k2 < k
with high probability as given in lemma A.8 Therefore, we know that log &. = O(n), with probability at least
according to Lemma A.4 and Theorem A.l
2, the following bound holds for all t:
ki
X n²
V(O.) S log
(60)
Since k, = o(n), (%).
we have
x²2
o(1). Therefore, there exists a mildly decaying
n
sequence 6, with log
+
= o(1), i.c.,
V(O,) o(1)
(61)
25

---

Under review as a conference paper at ICLR 2023
To conclude, on can be chosen such that
log Jom
w(1), log (2)==
=0(),, O(n),
1
(62)
5m
X2
7
and then with probability at least on. the excess risk consistent for all (w (+) R(O.) = (0,,) + (0.) = o(1)
(%)):
(63)
This completes the proof for the first claim. setting = + v
The second claim follows from Equation 58 and 60 by
Lemma A.9 (Lemma 5. restated). For any fixed (i.e. independent of sample size n) feature covari- ance Σ satisfying assumption 7 have (n) o(n).
Proof. Suppose there exists constant such that (n) 2 en.
By definition of ki, we know that
A 2 <1 Eiso di holds for < kn (n). Hence we have
Len2ft1
01 Eiso A n2
Σ
cn2' 2
Σx. X
(64)
1=1
i>0
summing up all leads to contradiction since Σi>o d 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 2 and hold. Assume the learning rate satisfies
O (T))) Then under the condition that ku On), k1 o(n), = o(n), gradient descent is
compatible with overparameterized linear regression in the region Tn = (w ()) namely,
sup R(O.) - 0 *E,,
Furthermore, the feature dimension p = do and the data distribution does change with n, then the condition ko (n)) alone suffices for compatibility.
Proof. According to Corollary 5.1 and Lemma 5.1 that for any sample size
for any 0, there exists {5a)n2 and N such
N, we have
Pr sup R(OO.) IET,
< 6n.
(65)
Let - oo shows that sUPreT, R(0.) converges to probability, which completes the proof. 11
B EXAMPLES AND DISCUSSIONS
B. EXAMPLE DISTRIBUTIONS
We apply our bound in Corollary 5.1 to several examples. In each example, we show the data distribution, the time interval, and the corresponding generalization bound. These distributions widely discussed in (Bartlett et al.) 2019; Zou et al. 202I).
Example B.I. Under the same conditions Theorem
5.7 let Σ denote the feature covariance
matrix. We show the following examples:
1. (Inverse Polynominal). If the spectrum of E satisfies
N ka
for some 1, we derive that kn (n)) ki 2 (nt).. Therefore, min, V(O,)
11
1-a
and
min R(O,) = = min a-1 -
26

---

Under review as a conference paper at ICLR 2023
2. (Inverse Log-Polynominal) If the spectrum of E satisfies
Ale
klog (k + 1)
for some > 1, we derive that Ko θ
logn ki
@
0
Therefore,
log"
min, ((0.) log and
min ((OO)=
1ogg
3. (Constant). If the spectrum of Σ satisfies
1 A ni+s" S h: S nt
for some & O, we derive that Ko hi = 0. Therefore, min, V(O,) = = and
1
min P((O)) =
Vn
4. (Piecewise Constant), If the spectrum of E satisfies
1
1 S
A
s+isk<d.
where = =nn nn,d== n² < r S 1, 2 1. We derive that ko = n., h = n". Therefore,
min, V(O.) 1nn and
min R(O,) o (n min min (l-
B.2 COMPARISONS WITH BENIGN OVERFITTING RESULTS
We summarize the results in Bartlett et al. (2019): Zou al. (2021) and our results in Table and provide a detailed comparison with them below.
Comparison to Bartlett et al. (2019). In this seminal work, the authors study the excess risk of the min-norm interpolator. As discussed before, the min-norm interpolator is the convergence point of gradient descent in the overparameterized linear regression setting. One of the main results in Bartlett et al. (2019) is providing tight bound for the variance part in excess risk as
V = O Ko
(66)
REo Σ
where 0 = XTXXX-)- denotes the min-norm interpolator, and R₂ = Eiis /
(Eish ) denote another type of effective rank.
By introducing the time factor, Theorem 5. improves over Equation (66) in at least two aspects. the consistency of the gradient descent dynamics for broad range
Firstly, [.c of step number t,, while Bartlett et al. 2019) only study the limiting behavior of the dynamics of co. Secondly. Theorem [51 implies that the excess risk of early stopping gradient descent solution be much better than the min-norm interpolator. Compared to the bound in Equation (66), the bound Corollary ( (a.) replaces Ko with a much smaller quantity k and (b.) drops the second derive consistent bound for overparameterized linear regression for an early stopping solution, even though the excess risk of limiting point (min-nomn interpolator) can be (2(1) (See the first example in B.I. We can further derive data-dependent time interval in which the bound is consistent, which cannot be directly obtained in Bartlett et al. (2019)
term involving Rxo [2). Therefore,
We do not compare the hias component in the excess risk bound here since our bound for the bias compo- nent follows Bartlett et al. 2019).
27

---

Under review as a conference paper at ICLR 2023
Comparison to Zou al. (2021). Zou al. (2021) study different setting, which focuses on the one-pass stochastic gradient descent solution of linear regression. The authors prove a bound for the excess risk
h1 n nEis A7 +
R(O,) =0
(67)
(Eiso A,)2
n
where 0, denotes the parameter obtained using stochastic gradient descent (SGD) with constant step size at epoch I. Similar to our bound, Equation 67 also uses the effective dimension kn to characterize the variance term. However, in a pretty different scenario from ours, which is one-pass SGD scenario. During the one-pass fresh data point to perform stochastic gradient descent in each epoch, and
emphasize that Zou et al. (202T) derive the bound
SGD training, therefore they set = (n) by default. As a comparison, we apply the standard full-batch gradient descent, and thus the time can be more flexible. Besides, results in Corollary 5.1 improve the bound in Equation (67) by dropping the second term. We refer to the third and fourth example in Example B.1 for more details, w our bound outperforms Zou al. (2021) when e 1/2 or < min 2 3/22..
B.3 COMPARISONS WITH STABILITY-BASEL BOUNDS
In this section, we show that Theorem 5.1 gives provably better upper bounds than the stability- based method. We cite result from 'Tngg al. (02T), which uses stability arguments tackle overparameteried linear regression under similar assumptions.
Theorem B.1 (modified from Theorem 1 in Teng et al. (202)). Under the overparameterized linear 8- regression settings, assume that || S 1, | S V, v DS0- supteje Oell. the following inequality holds with probability at least 1-
is o² -uu-ubgaussian, Let Be
log(4/8)
At(V + B,) 1011 At
R(O,) Ō mmx 0. -00022 100 +B,)
(68)
71
n
Theorem B.I applies the general stability-based results (Hardt et al. 2016 Feldman & Vondrák 2019) in the overparameterized linear regression setting, by replacing the bounded Lipschitz condi- tion with the bounded domain condition. A fine-grained analysis (Lei & Ying. 2020) may remove the bounded Lipschitz condition, but it additionally requires zero noise or decaying learning rate, which different from our setting. We omit the excess risk decomposition technique adopted in Teng et al. (202T) for presentation clarity.
Theorem B. can not directly yield the stability argument Theorem since obtaining a high probability bound of B; requires delicate trajectory analysis and is non-trivial task. Therefore, data-irrelevant methods such stability- baseed bounds can not be directly applied to our setting. Even if one can replace B, in Equation 68 with its expectation that is easier to handle (this modifi- cation will require adding concentration-relate terms, and make the bound in Equation 68 looser), can still demonstrate that Theorem 5.1 is tighter than the corresponding stability -bastd analysis by providing a lower bound on EE B3]. which will imply a lower bound on the righthand side of Equation 68
( Suppose the conditional variance of the noise e|mc is lower bounded by og. There exists constant e, such that with probability at least - ne ", we have for t o(n),
Theorem B.2. Let Assumption i holds. Suppose
X262
E 2101112 =
Σ A
(69)
First we prove the following lemma, bounding the number of large pi-
'Due to the bias term in Theorem 5.1 the overall excess risk bound cannot surpass the order 0(1/ which leads to the cases that Zou al. (202T) outperforms our bound. However, we note that such differences from the intrinsic property of GD and SGD, which may he unable avoid in the GD regimes.
28

---

Under review as a conference paper at ICLR 2023
Lemma B.1. Suppose t o(n). Let l denote the number of pa, such that μ4, 22 (?)) Then with probability least ne have (t).
Proof. According to Lemma A.1 we know that with probability at least 1 - ne Equation 15
holds for S n 1. Conditioned on this, we have
n
A 2 (1++m)
Σ S
(70)
t
1=
k=
F2
1>0
Since / = o(n), we have = (t) as claimed.
We also need the result from Bartlett al. (2019). which gives lowerbound of ya-
Lemma B.2. (Lemma 10 in Bartlett et al. (2019) For any dx there exists constant such that with probability at least we have,
ΣN
Un 2 c
(71)
12.10
We now ready prove Theorem
B.2
Proof. We begin with the calculation of |0011. By Lemma A.2 the conditional unbiasedness of noise in Assumption and the noise variance lower bound, we have
0.l1
x xxxx (0o ('-X'
72
- AxTx) xxxx ) x
E
-
(xo" + +e)
x x) x)) xix0'
+E 1 -
1-(1-2xTx)) X
n
n
2
--=-X 2 x x x Xle
N E
-- I A
11-1-2x0 xxxx)) X Xtee T TxtT
I- 1 - (
ET
( [1 1 (1-(1- (1--xxxx)) xtxii
1- 1-(1-2xTx)
> TT
(1 )12
o²
(72)
When /4 00=0(0 (2), we have
1
u4) =
put +
(73)
Plugging it into Equation 72 and then use Lemma B.I B.2 we know that under the high probability event in Lemma B.I and B.2
0 = ? (n- 1) 2²
(22 22 mntt = S2
12t2
Σ x1 x)
n? Hntt =
(74)
29

---

Under review as a conference paper at ICLR 2023
Therefore, the stability- based bound, i.e., the right hand side of Equation 68 can be lower bounded in expectation as S2
6 Eisho Ax). This implies that the stability-basel bound is vacuous when
n2 (Eesan Ae)
t= Ω
Thus, stability-based methods will provably yield smaller compatibility
region than (w (2), (?)) in Theorem 4.1 when Σi>ko X is not very small, as demonstrated in examples below.
Example B.2. Let Assumption I
holds. Assume without loss of generality that ((1). We
have the following examples:
1. (Inverse Polynominal), If the spectrum of E satisfies
Ak
ka
for some >> derive that kn- (m), Σisko d (0 (noT))) Therefore, the stability bound in Theorem B. vacuous when
12
which outperformed by the compatibility region Theorem 5.1 when a
2. (Inverse Log-Polynominal), If the spectrum of E satisfies
A
klog (k: + 1)
for some 3 > we derive that ko = = bound in Theorem B. is vacuous when
Eisio d -(1). Therefore, the stability
log
52
n3
which outperformed by the compatibility region in Theorem 5.1 3. (Constant). If the spectrum of E satisfies
A nite! S tte
for some 5 > O, we derive that Ko = 0, Ei>ko d = 1. Therefore, the stability bound in Theorem vacuous when
1= n
which is oulperformed by the compatibility region in Theorem 5.1
4. (Piecewise Constant), the spectrum of E satisfies
1 < s
A6 1 s+1 +
where n", = Therefore, the stability bound in Theorem B. vacuous when
n0,0 <
1,9
> 1,
we derive that Ko n², Eisho d 1.
t= Ω (23)
which outperformed by the compatibility region in Theorem 5.1
B.4 COMPARISONS WITH UNIFORM CONVERGENCE BOUNDS
We give standard bound on the Rademacher complexity of linear models.
30

---

Under review as a conference paper at ICLR 2023
Theorem B.3 (Theorem in Mohri et al. (2012), Let S S {x: |||||2 rr be sample of size and let H. = {a + (w, z)
2 2 S A.. Then, the empirical Rademacher complexity of H. can be
bounded as follows:
A²
Rs) $
(75)
Furthermore, Talagrand's Lemma (See Lemma 5.7 in Mohri et al. 2012 indicates that
(A²) vn
Rs(1 H) - LRs(H))
(76)
where L (A) is the Lipschitz coefficient of the square loss function in our setting. Therefore,
the Rademacher generalization bound is vacuous when A 2((4). By Theorem B.2
know
that 1 ((nb) when t = 2
n
A similar comparison as in Example B.2 can
s(Eista x=)²
demonstrate that uniform stability arguments will provably yield smaller compatibility region than that in Theorem 5.1 for example distributions.
B.5 COMPARISON WITH PREVIOUS WORKS ON EARLY STOPPING
A 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 detailed discussion.
Here we compare our results with some most relevant works, including Yao et al. 2007 Lin &
Rosasco 2017 Pillaud- Vivien al. 2018).
Comparison with Yao et al. (2007). Yao et al. (007) study kernel regression with early stopping gradient descent and share some similaritie with our paper. However, their approaches cannot cover ours, and are fundamentally different from ours in the following aspects.
Firstly, the assumptions used in the approaches niques. Yao et al. (2007) assume that the input feature and data noise have bounded norm (see Section 2.1 Definitions and Notations in Yao et al.) (2007)). while require that the input feature is subgaussian with independent entries. The assumption used in our paper is widely- in benign overfitting analysis, following Bartlett al. (2019).
different, due to different goals and tech-
Furthermore, although Yao et al. (2007) obtain a minimax bound in terms of the convergence rate, is suboptimal in terms of compatibility region. Specifically, The results in our paper show a com- patibility region like (0, n.) while the techniques Yao et al. (2007) can only lead to compatibility region like (0, /n). See Proof of the Main Theorem section in Yao al. (2007) for details. Such differences come from different goals of the two approaches, where Yao et al. (2007) focus on
providing the optimal carly-stopping time while we focus on providing a larger compatibility region.
Comparison with Pillaud- Vivien et al. (2018). Pillaud- Vivien et al. (2018) study kernel regression with multi-pass stochastic gradient descent and derive optimal excess risk guarantee. Different from approaches with full-batch gradient descent, they study averaged stochastic gradient descent with batchsize equal to 1.
Comparison with Lin & Rosasco 2017) Lin & Rosasco 2017) study stochastic gradient descent with arbitrary batchsize, which is reduced to full batch gradient descent when setting the batchsize to sample size n. However, their results still fundamentally 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 the same spirit of Yao et al. (007)) Specifically, Lin Rosasco (011))
C+1 ), where Ç and are problem dependent constants (See Theorem 1 in [in Rosasco (2017) for details). The following examples demonstrate that this paper's results yield larger compatibility regions for wide range of distribution classes.
derive a compatibility region like (0, n 121217)
Example B.3. (Inverse Polynominal). If the spectrum of Σ satisfies
d
ka
for some a > 1. For this distribution, we have Ç= 1 (0, n IatI) ), which is smaller than the compatibility region (0, 2044
y==
and the compatibility region is
given in Example B.5
31

---

Under review as a conference paper at ICLR 2023
Example B.4. (Inverse Log-Polynominal), If the spectrum of Σ satisfies
Ak
k logg" (k 1)
for some 3 > 1. For this distribution, we have Ç = 2.2 7 = and the compatibility region is (0, n which is smaller than the compatibility region (0, given Corollary 5.1
B.6 DISCUSSIONS ON EXTENSIONS TO KERNEL REGRESSION
In this section, we discuss extending the analysis in overparameterizze linear regression to kernel regression setting.
Let H denote a infinite dimensional Hilbert space equipped with inner product (:s and Φ Rd H. denote a feature map. Consider the following class of functions:
F= {f Fd + R f(x) (0, ((x)) x.
(77)
Let (æ, y) _ IR denote the data vector and the response, following a joint distribution D. The goal of kernel regression is to find function f parameterized by 0, that minimizes the following population loss
(( = 1 -0 (0) x(x))
(78)
Therefore, kernel regression is equivalent to solving linear regression problem transformed data (o(x), y). By replacing a with )). the notations and results in Section 4 can naturally extended to the kernel regression case, which is detailed follows.
Given a dataset (x,, y:) hissn sampled i.i.d from D, consider the following dynamics of gradient descent analogous to Equation
Oct1 = O, 0 (XX) (0(X)0, - YY,
(79)
where ((X)= (o(z)). (....)........ ((..,,,,,,))) )(x,)) and = (y), (y...... vn) ,n)) Note that this dynamic takes place in the feature space H. The following corollary characterizes the compatibility between kernel regression and gradient descent.
Corollary B.1. Assume the distribution of (ő(x). y) satisfies Assumptions 7
221 and does not
change with sumple size n. Let E. = E ( denote the feature covariance. Then under the condition that the effective dimension ku (E²) (n)) and the learning rate X = 0 mx gradient descent using 79 compatible with kernel regression.
Proof. The corollary follows from Theorem 4.1 by noting that its proof holds for feature vectors in an infinite dimensional Hilbert space.
We give several remarks regarding the difference between the generalization analysis of kernel re- gression and overparameterized linear regression.
Firstly, Corollary B.1 assumes ((x) has subgaussian i.i.d entries after normalization (see Assump- tion 3), which can be hard to satisfy due to the non-linearity of feature mapping ((.).
Secondly, Corollary B.J focuses on gradient descent the feature space H. Another perspective is to apply the Representer theorem (Mohri et al. 2012) to express the weight 0 into a linear combination of transformed inputs 0 Σisign aj Q) (2 and analyze the gradient descent dynamics of the n-dimennional vector a = (a), an). Although they both converge to the min-norm solution, these two gradient descent dynamics are different, and Theorem is not directly applicable to gradient descent on a.
Thirdly, previous works [El Karoui 2010 Liang & Rakhlin 2018 Mei & Montanari 2022 prove that the spectrum of feature covariance No has an approximately linear relationship with the spec- trum of data covariance Σ = E xxx" when feature mapping o(-) corresponds to an inner product type kernel. This can be used to derive more intrinsic compatibility condition using only data distribution rather than feature distribution. We leave a more refined analysis for alga-itgo compatibility in the kernel regression regime for future works.
32

---

Under review as a conference paper at ICLR 2023
B.7 VARYING E, VARYING c(t,
Although setting c(t, n)) to a constant as in Corollary 5.1 suffices to prove Theorem 4. in this section show that the choice of c(t, n) can be much more flexible. Specifically, provide concrete example and demonstrate that by setting c(t,n) n) to a non-constant, Theorem 5.1 can indeed produce larger compatibility regions.
Example B.S. Under the same conditions Theorem 5.1
let E denote the feature covariance
matrix. If the spectrum of E satisfies A k- for some a > 1, we set c(t, n.) = 111 2us
for 3c++1 Thenfor t = ((n"), ) we derive that V(0,) = (n 2ar -2--2--11111
a given a+1 2a
STS
2a
20+1
Example B.5
shows that by choosing c(t, n) as a non-constant, we exploit the full power of The-
orem
5.1
w(n). In this example, Theo- outperforms all O - -type bounds, which become vacuous when = w()).
and extend the compatibility region
rem 5.1
B.8 CALCULATIONS IN SECTION B.1
We calculate the quantities r(E), ko, Ki, l2 for the example distributions in B.1 The results validate that k is typically a much smaller quantity than ko. and hy serves as a proxy for 12 in the constant cft, n) setting.
1. Calculations for λ
K. > 1.
Define rx(2))- = Eise A: d1
as in Bartlett et al. (2019). Since Eisk
O
we have
Jau
Th (x) =
(kk). Hence, ko (()) and the conditions of theorem 5.1
satisfied.
As Σiso A co, By its definition we know that k is the smallest / such that A111 ( Therefore, 1 = O( Similarly, k2 = (
2. Calculations for \ (kog* 3 1.
Eisk (1+1) O logg dx) 0 (1
log 11 which implies (x k log k.
Solving ko log ko 2 (n), we have kn = O log
By the definition of 11 we know that kj the smallest such that / (1 (n)..
Therefore, kn ( log" ). 222 O(10" "og"
by similar calculations.
3. Calculations for X; _ S S n n 0.
Since ro E) = n It,,, we have ko = 0. By the definition of h and k2, we also have
kn la =
1 1 k <
4. Calculations for \
T-6 s k d' n - 1, 1.
<r
For 0 S k: < 8, r, = = 0(n") ) = o(n), while rs (E) = + = 0(n9) = w(n).
Therefore, 0o = = n². Similarly, noting that d + = w(n) for 0 < k < and A = ( = o(n)), we know ाe that k = n'. Similarly, 122 n..
B.9 CALCULATIONS FOR A gu , 1 IN SECTION B.7
Set c((,n)) 1. where 3 > 0 will be chosen later. First we calculate ky under this choice of c(1, n). no
Note that Eish fo = ( (+-T). Therefore, kg the smallest such that gor
n = O For
the bound on V (0.) to be consistent, we need ko = o(n). Hence, To-T O T
m which implies
211 k2 = T
Thee caleulations for ko, hn and ky in this section only apply when is sufficiently large.
33

---

Under review as a conference paper at ICLR 2023
Plugging the value of c(t, n.) and l into our bound, we have
v (().) 0 nn -1)--))(++1))) n22T-B-2)
which attains its minimum (n
2nr 2ar-3a-2r-1 2041
at 3 = θ 2ar-a-1
2a+1
For V V0)) = O(1), we need < the range of t in which the above calculation applies.
30-1 For 3 2 0, we need T 2
a+1
Putting them together gives
20-2-
20
B.10 DISCUSSION ON Dn
In this paper, the distribution D is regarded as sequence of distribution {P,, which may dependent on sample size n. The phenomenon comes from overparameterization and asymptotic requirements. In the definition of compatibility, we require n - co. In this case, overparameterization requires that the dimension p (if finite) cannot be independent of since n + co would break overparame- terization. Therefore, the covariance Σ also has n-dependency, since is closely related to p.
Several points are worth mentioning: (1) Similar arguments generally appear in related works. For example, [arrtlttt et al. (2019) use similar arguments when discussing the definition of benign co- variance (Page 7 in the arxiv version). (2) One avoid such issues by letting p - oo. This is why we discuss the special case p = oo in Theorem 4.1 (3) is fixed finite constant that does not alter with n, the problem becomes underparameterized and thus trivial to get consistent generalization bound.
B.11 COMPARISONS WITH PAC-BAYES BOUNDS
As of the most exciting techniques in generalization analysis, PAC-Bayes theory works both theoretically and empirically. Usually, the form of PAC-Bayes bounds relies on the distance between the prior distribution which unrelated to the training procedure, and the posterior distribution which is the distribution after training (e.g., isotropic Gaussian distribution centered at a trained parameter).
In this sense, PAC-Bayes considers different regimes from this paper, since the returned classifier in this paper is not a distribution. Moreover, PAC-Bayes usually do not explicitly focus on early- stopping iterates, while the notion of compatibility heavily relies on the early-stopping arguments. By considering early-stopping that encodes algorithm information, we can derive tighter generaliza- tion bound relying weaker assumptions.
More interestingly, PAC-Bayes framework is not mutually exclusive with the trajectory analysis, One can indeed introduce trajectory analysis into PAC-Bayes techniques and derive compatibility region based on trajectory-baset PAC-Bayes theory. By doing so, one can explicitly incorporate more algorithm information into PAC-Bayes framework. We leave more detailed discussions for future work.
We next show the differences in more detail:
1. Different settings. In PAC-Bayes analysis, the returned classifier is a distribution instead of fixed parameter. Forcing PAC-Bayes analysis in the fixed parameter regime would cost much because it is hard to define distribution distance (e.g., KL divergence) on two single-point distributions.
2. Different classifiers. Although both methods consider "a bag of" classifiers, they are fun- damentally different. In PAC-Bayes framework, the trained random classifiers are regarded to be independently drawn from the posterior distribution. However, in trajectory analysis, all classifiers are dependent during the training process. Therefore, trajectory analysis is more challenging in this sense.
3. Different characterizations. PAC-Bayee Ba-ees framework characterizes the expectation of gen- eralization loss, over the randomness of the posterior distribution over parameters, which do not explicitly sketch the time factor. In comparison, the trajectory analysis in this pa- per focus on providing a compatibility region, where the generalization error uniformly consistent and considers the time factor.
34

---

Under review as a conference paper at ICLR 2023
Risk
Treinine Lozs
Training
Trainin
Epochs
Epachs
Epachs
(a) A
(b) X
7
(c) A 13
Excass Bast
Excem Rai
Waining Loss
Traiing
Training LoGs
Rick
Trainina LoGs
Excess zick
Training Loos
Epochs
(d) X (1+1
A
(f)
(++1)
Flog (1++1
Figure 2: The training plot for overparameterized linear regression with different covariances
using GD,
C ADDITIONAL EXPERIMENT RESULTS
C.1 DETAILS AND DISCUSSIONS FOR LINEAR REGRESSION EXPERIMENTS
In this section, provide the experiment details for linear regression experiments and present additional empirical results.
In Section 6 We consider six overparameterized linear regression instances with input dimen- sion = 1000 and sample size n = 100. The feature vectors are independently sam- pled from zero-mean Gaussian distributions, whose covariances are diagonal with entries X T1 2 # Flog(e+1)' (iog" (1+1) respectively. For each feature x, we construct the re- sponse as y = x 0 + E, where 0 is sampled from a p-dimensional standard Gaussian distribution for each instance, and is sampled from standard Gaussian distribution. We conduct gradient de- scent with learning rate = 0.001 on the above instances. We also compute min-norm excess risk via its closed form, with 1 10-4 weight decay on parameter O avoid numerical instability. Note that the regularization will only reduce the final excess and will not jeopardize our final conclusion's correctness.
The linear regression experiment in Figure follows the setting described in section Although the final iterate does interpolate the training data, the results suffice to demonstrate the gap between the early-stopping and final-iterate excess risk. The training plot for different covariances are given in Figure
We provide the experiment results of sample sizes n 50, n 200 and feature dimensions 500, p 2000 analogous to those Section [6] The settings are the same as described in the main text, except for the sample size. The optimal excess risk and min-norm excess risk are provided Table 3 6 and 5 The tables indicate that the three observations given section [ hold for
different sample size
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,
35

---

Under review as a conference paper at ICLR 2023
Table 3: The effective dimension Y1, 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
k
OPTIMAL EXCESS RISK
MIN-NORM EXCESS RISK
A
(n))
2.515 0.0104
12.632 1 0.1602
A
((7))
0.269 + 0.0053
50.494 + 0.9878
A
(na))
0.083 = 0.0011
13.208 + 0.4556
A 1ogge+1)
0.808 0.0090
46.706 + 0.6983
log
A 1log
0.381 0.0076
74.423 + 1.1472
log
X llgg
0.233 0.0052
43.045 + 0.8347
log
Table 4: The effective dimension 11, the optimal early stopping excess risk and min-norm excess risk for different feature distributions, with sample size n2 200 1000. We calculate the 95% confidence interval for the excess risk.
DISTRIBUTIONS
k
OPTIMAL EXCESS RISK
MIN-NORM EXCESS RISK
A
(n)
2.173 0.0065
52.361 0.4009
X
(()))
0.161 0.0039
36.855 + 0.4833
A
(na)
0.068 0.0012
8.1990 + 0,2313
A #lggt+1)
0,628 0.0034
152.70 + 1.1073
A Flog
0.241 + 0.0036
83.550 1: 0.7596
Ing
A (1+1)
0.146 + 0.0108
33. $3.469 + 0.4540
Tog
to simulate the label noise which is common in real datasets, e.g ImageNet (Stock & Cissé 2018 Shankar et al. 2020 Yun et al. (002). We do not inject noise into the test data.
We choose standard four layer convolutional 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 is set to 1024, and the test batch size is set to 1000. We choose the standard cross entropy loss as the loss function.
We provide the plot for different levels of label noise in Figure We present the corresponding test error of the best early stopping iterate and the final iterate Table Since the theoretical part of this paper focuses on GD,, we also provide corresponding plot of GD training in Figure for completeness.
36

---

Under review as a conference paper at ICLR 2023
Table 5: The effective dimension k1, 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
kn
OPTIMAL, EXCESS RISK
MIN-NORM EXCESS RISK
A
(m)
1.997 0.0876
27.360 + 0.3019
A
((n2)
0.211 0.0050
43.531 +: 0.7025
A =
(na)
0.076 0.0011
10.062 + 0.3022
A Flogg+11
0.643 0.0056
96.465 + 1.0594
log
A (++1)
0.289 + 0.0055
83.694 + 0.9827
Ing
A (1+1)
0.181 + 0.0045
38.090 1 0.6378
Tog
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 2000. We calculate the 95% confidence interval for the excess risk.
DISTRIBUTIONS
OPTIMAL EXCESS RISK
MIN-NORM EXCESS RISK
A
(n))
2.662 0.0066
23.111 1: 0.2278
A
(
0.219 0.0050
43.130 0.6421
X =
(n
0.077 0.0010
10.031 + 0.2942
A Flog(+1)
0.749 + 0.0055
88.744 1 0.9414
A flog
0.312 + 0.0057
82.859 + 0.9394
loga
A (1+1)
0.190 = 0.0047
37.782 + 0.5945
log
Tell Toiningg Emor
Teal Ener Triring Emor
To ring Emor
Prining Error
Taining Error
Training Error
Test
Epochs (a) 0% label noise
Epochs (b) 10% label noise
Epocho (c) 20% label noise
Enor
Thaining
Training
Ener
Training Emnn
Training Emrrr
Training Enoor
Res Breer
Test Error
Epochs
Epochs
Epochs
(d) 30% label noise
(e) 40% label noise
(f) 50% label noise
Figure 3: The training plot for corrupted MNIST with different levels of label noise using SGD.
Figure (c) is copied from Figure
37

---

Under review as a conference paper at ICLR 2023
Training Emorr
Tost
Epochs
Figure 4: The training plot for corrupted MNIST with 20% label noise using GD.
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%
38


Reviews:
[{"review_id": "uf6A-cHy5S", "reviewer": "Reviewer_9FRm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "- This paper provides a follow-up of the \"benign overfitting\" result from  Bartlett et al., 2019. \n- While the benign overfitting setting studies the min-norm interpolator of the data (which corresponds to the _final_ solution learned by linear regression), this paper considers excess risk guarantees for intermediate early-stopped solutions of linear regression. In this sense, the paper analyzes the trajectory of GD solutions.\n- This allows them to prove convergence of excess risk for a much more general class of data distributions than was covered in Bartlett et al., 2019.\n", "summary_of_the_review": "The paper presents an interesting, significant and non-trivial extension of the statistical analsyses in overparameterized linear regression to early-stopped settings.  The proof and results are explained well. There are issues with how the motivation is framed, which I hope can be addressed during the rebuttal.  \n\n### Update after response\n\nThanks to the authors for their response. I appreciate the new added comparisons to related work. \n\nI had concerns that the claim suggesting that this is the first technique that is data- and algorithm- dependent is too strong. \nThe authors admit that there are indeed existing techniques that depend on data and algorithm, but that this dependence is too superficial.\nWhile I agree, I still believe that centering the paper around the notion of \"compatibility\" as a way of encoding algorithm and data-dependence is not as valuable and significant in itself as the paper claims. The paper does make a solid contribution in terms of statistically analyzing early-stopping for the benign overfitting type of setting; however, it also claims that there's novel insight and value in the definition of compatibility, which I do not see. Therefore, I wish to keep my score as it is. I strongly encourage the authors to rethink the story of the paper and focus on highlighting the key technical contributions rather than the abstraction of compatibility --- unless, there are multiple applications of compatibility beyond linear regression that can somehow drive home the point that this abstraction is insightful.", "strength_and_weaknesses": "Strengths\n===\n1. The paper makes a valuable extension over the existing studies of overparameterized linear regression. While earlier studies look at the min-norm interpolator, this paper goes a step further to analyze intermediate solutions, which is highly non-trivial and interesting. \n2. Early-stopping is also a practically relevant concept, thus justifying the significance of the setting considered in the paper.\n3. It is also interesting that they are able to formally identify scenarios where the final iterate has overfitting that is _not_ benign, while the early-stopped solution does have excess risk converging to zero (which they term as \"compatibility\"). The formal notion of compatibility itself is novel.\n4. The proof seems to be a non-trivial extension of Bartlett et al., 2019.\n4.  The paper is well-written. The proof and its implications were clearly outlined in the main paper. There are also many example distributions which are helpful in drawing comparisons with benign overfitting.\n\nWeaknesses\n===\n1. My main complaint is with the way the result is framed. I am afraid I do not agree with the motivation/narrative that this paper analyzes the interplay between data and algorithm while prior work. While classical bounds (such as VC dimensions), do ignore the algorithm altogether, more recent bounds (such as those based on norms, flatness etc.,), _do_ care about how the algorithm induces various biases in the model. Even in the context of studies in high-dimensional linear regression, the very fact that they study the min-norm interpolator says that they are looking at an algorithm-dependent solution and not any ERM solution. What might be correct to say here is that while previous studies of overparameterized linear regression perform a trajectory-independent analysis, this paper takes a trajectory-dependent analysis. \n\nOverall, I would frame this paper as \"a statistical study of early-stopping\"  (which _is_ valuable in itself) rather than the current claim of  a \"capturing data-algorithm interplay which has never been done before\" which seems misguided and disproportionate.  \n\n2. I'd like to map the result intuitively to the motivation behind early-stopping, such as the one outlined in the introduction. Early-stopping helps the classifier ignore noise in the data, which in this case should correspond to the variance term. Is this essentially the reason why the early-stopping iterate's bound is better than the final iterate? e.g., in Thm 4.1, does $V(\\theta) \\neq o(1)$ when  $\\theta$ is the final iterate?\nAdding a discussion of how the result maps to the standard intuition of early-stopping would be helpful.\n\n### Minor points:\n3. Since the order of quantifiers is very important (the $\\forall t$ must follow _after_ the \"w.h.p\"), I'd be explicit about this order in all the lemmas and intermediate theorems.\n\n4. Sec B.4 argues that uniform convergence upper bounds do not enjoy as strong a guarantee. I wonder if it's possible to show a lower bound on uniform convergence such as in the sense of Negrea et al., 2020 i.e., consider the set of early-stopped iterates for various draws of the data, and show that the uniform convergence bound considered on that set has poor sample-complexity dependence.\n\n5. I'm not sure I followed the first step in Eq 7. Minor: might be worth labeling every equation. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "nMANhYPovPh", "reviewer": "Reviewer_rKAH", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors present a compatibility condition between the data distribution and the algorithm used for regression. This corresponds to a weaker requirement than the benign overfitting studies that simply study the generalization property *at convergence*. ", "summary_of_the_review": "Without a proper comparison with the papers from early stopping, I cannot consider the restatement of it under *compatibility condition* as a proper contribution. I am happy to change my evaluation if I am wrong.", "strength_and_weaknesses": "### **Strength** \n\nThe authors introduce a framework that can be rich theoretically. Instead of studying the *implicit bias* of an algorithm at convergence, it studies whether the path of training dynamics has reached a good generalization point in a certain time zone. They also prove a separation with benign overfitting under certain condition on the spectrum of the covariance matrix.\n\n### **Weaknesses** \n\nDespite the fact that the set-up is clear, the (only) reel results presented are the one of gradient descent for a linear model. The link between early stopping and good generalization properties has already be well studied and I am surprised the authors cite Yao et al, Ali et al as they are doing exactly the same thing! As far as I understood, the only difference is the way to present the results: here, as now commonly stated in the benign overfitting, the generalization bounds are presented under the form of certain cut-off eigenvalue summations. Whereas in Yao et al, eigenvalue decay as polynomials are stated to make the bounds more readable. Morevover, on the contrary to what the authors say, the Assumption 1 *is not mild* (mainly the independence of the entries of $\\tilde{x}$). As the rates of Yao et al are known to be minimax in the setup of the paper, I do not think that the present analysis could be tighter than theirs.\n\n\n**Minor issues**\n\n- Prefer *at convergence* than *the last iterate*\n- Need a deeper comparison with early stopping.\n- Under this form, Assumption 1 is hard to understand: the notation $O, o, w$ are not defined: are they with respect to $n$? If this is so, how to understand $o(n/\\lambda)$, does $\\lambda$ depends on $n$, if yes, $\\lambda = O(1/Tr(\\Sigma))$ is misleading ?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "ZCB5b5GQ5VH", "reviewer": "Reviewer_a4RZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work has a key focus on generalization in overparameterized learning problems. The authors propose a new trajectory analysis for generalization that depends both on the data-generating distribution and the algorithm of the underlying setting, unlike most of the existing work which typically concentrates on one of either. A condition, named *compatibility* is being introduced, which asserts that a data-generating distribution and an algorithm are compatible roughly when the excess risk converges (both data and algorithm are treated random, as a key component of this work)  to zero as the training sample size grows. A *compatibility region* is the collection of \"allowed\" values that the data generating distribution and the algorithm can be parametrized with where the resulting pair is compatible. The authors' main focus after this definition is to derive the compatibility region of a linear regression model that is trained with gradient descent (number of iterations as a parameter that belongs in the compatibility region) with the underlying feature-label pairs. Some of the claims are exhibited via synthetic numerical experiments, and then comparisons with some of the existing bounds are analyzed. ", "summary_of_the_review": "The literature review, writing of the paper, numerical experiments, and motivation are poor. However, the paper has a thorough analysis, strong results, and looks mathematically correct. ", "strength_and_weaknesses": "I would like to note that, I am **not** an expert in generalization. I am aware of the general idea, but I would not consider myself as a researcher who is up to date with all the advancements. However, I would have been definitely interested in reading this work if I were to see this paper in the proceedings, hence I will ask questions that I am genuinely wondering, and I will specify strengths and weaknesses from my perspective.\n\n**Strength:** The assumptions are mostly standard and I cannot foresee an \"assumption-related problem\". I really like Theorem 1 and its proof looks correct as much as I am concerned. Corollary 5.1 might have a good impact. Appendix B is extremely well, but \"too well\" that some of the results can even move back to the main paper (e.g., without seeing Example B.1 it is hard to imagine the main idea of the relevant Thm; similarly, Theorem B.2. looks very interesting).  \n\n**Weaknesses:** \n*I list the major and minor concerns that made me give a \"marginal accept\" instead of \"accept\". However, I still think the paper has some novelty hence I am also going to stay active during the discussion period in case the authors have updates or questions regarding my review.*\n\n***Major Weaknesses/Questions***\n- The paper after Definition 3.1 is more or less all about linear regression with gradient descent. The \"strong\" proofs exploit a lot about the structure of linear regression, which already has lots of cool generalization bounds in the literature. I am therefore wondering, to what extent can we use it for other models. Because if we already know we want to use linear regression, then the compatibility definition itself does not have much advantage; I would consider this more useful if we had results over several algorithms and we understand which is good in what setting. Also, due to the simplicity of linear regression with gradient descent, it looks like the compatibility region tells us more about when to stop for how kind of data generating distribution, which is an overstudied topic.\n- The literature summary is not very thorough in my view, especially compared to the rest of the paper. PAC-Bayes generalization theory is almost nowhere discussed, however, there are so many new studies that may be doing what this paper is doing implicitly. Except for an analysis in the Appendix, I did not see much on Rademacher complexity-based generalizations, and I would like to know more about how these approaches differ. \n- The numerical experiments are weak. There is not much these experiments tell the reader, rather than displaying mostly what was shown. The selection of parameters is also done in an ad-hoc manner. \n- I am not sure if considering the data-algorithm pair was *completely* not studied. This is a very strong and risky statement. I agree that in generalization theory this is studied much less, though.\n\n***Minor Weaknesses/Questions***\n- Can we get have any finite sample guarantees? This is very popular these days. I guess it should be easier to analyze in the overparameterized setting.\n- Abstract: The Nagarajan citation is on Deep Learning, but the sentence sounds general. \n- Abstract: \"more suitable notion\" -> more than what?\n- Abstract, and anywhere else: \"last iterate analysis\" is either not cited or not explained. This looks vague.\n- Introduction has a sentence that says \"both the training algorithm and the data distribution play essential roles in generalization analysis\". This is well-known for any setting, not just overparameterized regime.\n- Introduction and overall: The question \"How to incorporate both data factor and algorithm into generalization analysis?\" is not motivated. Why should we be interested in this? For example, later on, you show that this would require fewer assumptions. This might be one reason. But overall, please answer \"why\" in addition to \"how\".\n- The introduction has \"the final interpolator ...\" this term and sentence stay unclear.\n- Figure 1 (a): the right axis is different than the left axis. Why is that?\n- Page 2: The sentence that starts with \"Informally speaking,\" is not clear to me.\n- Section 3.1, **Algorithm**: The parameter $t$ has almost no explanation. This is not clear at all. In general, we keep referring to $t$ in Definition 3.1, too, but this only makes sense in the gradient descent setting. The notation or motivation is not clear.\n- Definition 3.1: As stated above, $\\boldsymbol{\\theta}_{n}^{(t)}$ is not clear. Could you also somewhere state why such an asymptotic convergence in probability would imply generalization? $T_n$ notation is not clear until someone comes to the next sections. \n- Could you please relate **Assumption 3** to the fact that $(\\boldsymbol{X}\\boldsymbol{X}^\\top)$ is invertable? \n- \"iff\" -> if and only if\n- Page 6 refers to Theorem 5.1, this should be a typo.\n- Overall too many times Vartless et al. (2019) are cited. Could you please mention it less? Maybe we can mention benign overfitting first, and then keep referring to \"benign overfitting\" instead?\n- In the Conclusion and throughout the paper the authors say \"this method eases the assumptions\". However, I am not sure about one thing. Here, since we consider algorithm and data together, we are somehow splitting the assumptions equally over them. If we had not parametrized one of either, then we would have needed more assumptions on the latter. In other words, having control over both already gives us the power to decrease the severity of assumptions.\n- The **Setup** part in Section 6 is very simplistic. In general, it is not \"fun\" to read these experiments. They are very standard. I would appreciate seeing more original experiments. The selection of parameters is very ad-hoc and not clear.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "OxfTYsqeJAH", "reviewer": "Reviewer_kDAx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper analyzes the generalization performance of a simple model — linear regression. Given that a prior work (Bartlett et. al. 2019) has shown a benign over-fitting of the final iterate of SGD for over-parameterized linear models, this work with milder conditions theoretically shows that good generalization can also be achieved during the training, not necessarily by the last iterate. ", "summary_of_the_review": "The analysis in the paper requires weaker conditions and includes more scenairos, e.g., polynomically decaying eigenvalues of covariance, than prior works. For these scenarios, it proves existence of good generalization solutions during full-batch GD training.\n\nHowever, the analysis is only performed on the simple linear regression model, and it is not clear whether it applies to non-linear models. \n\nSome of the numerical verifications are not consistent with the theory.\n", "strength_and_weaknesses": "Strength:\n\nCompared to the benign over-fitting study (Bartlett et. al. 2019), this work requires weaker conditions on the covariance matrix. Particularly, it allows the scenarios where the eigenvalues decay polynomially, $\\lambda_k \\sim 1/k^\\alpha$. Instead,  (Bartlett et. al. 2019) requires a heavy tail of the spectrum of the covariance. \n\nFor the scenarios that are included by the conditions of this paper but are excluded by (Bartlett et. al. 2019), this paper obtains a theoretical guarantee of the existence of good generalization solutions during the GD training. However, the tradeoff for these weaker conditions is that the good generalization is not necessarily at the final iteration. \n\nWeaknesses:\n\nThe analysis is still restricted to the simple linear regression model, while most of the interests of the machine learning community are on the non-linear models, especially neural networks. It is widely believed that many properties of, or finding/observations on, linear models do not extend to non-linear models. \n\n\nFigure 1 is not consistent with the theoretical results and could be misleading. \n\n>First, Figure 1b is trained using SGD, while the theory (Theorem 4.1) is on full-batch GD. These two algorithms do not have the same trajectory, hence, the U-shape curve for SGD in Figure 1b does not necessarily tell the same story as Theorem 4.1. A curve with full-batch GD training is needed in Figure 1. \n\n>Second, Figure 1a seems still at the early stage of training, as the training loss is still large. It is hard to see whether the test loss will have a second descent. For overparameterized models, the training loss can touch zero, and we should train the model after the zero training loss is obtained. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject