From Optimization Dynamics to Generalization Bounds via Łojasiewicz Gradient Inequality
Authors: Fusheng Liu
Haizhao Yang
Soufiane Hayou
Qianxiao Li
Venue: Accepted by TMLR ()

Abstract: 
Optimization and generalization are two essential aspects of statistical machine learning. In this paper, we propose a framework to connect optimization with generalization by analyz- ing the generalization error based on the optimization trajectory under the gradient flow algorithm. The key ingredient of this framework is the Uniform-LGI, a property that is generally satisfied when training machine learning models. Leveraging the Uniform-LGI, we first derive convergence rates for gradient flow algorithm, then we give generalization bounds for a large class of machine learning models. We further apply our framework to three distinct machine learning models: linear regression, kernel regression, and two-layer neural networks. Through our approach, we obtain generalization estimates that match or extend previous results.

Published in Transactions on Machine Learning Research (10/2022)
From Optimization Dynamics to Generalization Bounds via Lojasiewicz Gradient Inequality
Fusheng Liu
fu. nus.u..ed.u
Institute of Data Science National University of Singapore
Haizhao Yang
hayang edu
Department of Mathemalics University of Moryland College Park
Soufiane Hayou
hayou@nus. wwtporwwwuus......... edu.sg
Department of Mathematics National University of Singapore
Qianxiao Li
gianziao Truss edu.sg
Department of Mathematics National Universily of Singapore
Reviewed on OpenReview: https: // openrevie.. net/ bet/fforee forum? id= mW6nD3567a
Abstract
Optimization and generalization are two essential aspects of statistical machine learning. In this paper, we propose a framework to connect optimization with generalization by analyz- ing the generalization error based on the optimization trajectory under the gradient flow algorithm. The key ingredient of this framework is the Uniform-LGI, property that is generally satisfied when training machine learning models. Leveraging the Uniform-T.GT, we first derive convergence rates for gradient flow algorithm, then we give generalization bounds for a large class of machine learning models. We further apply our framework to three distinct machine learning models: linear regression, kernel regression, and two-layer neural networks. Through our approach, we obtain generalization estimates that match or extend previous results.
1 Introduction
From the perspective of statistical learning theory, the goal of machine learning is to find a predictive function that can give accurate predictions on new data. For supervised learning problems, empirical risk minimization (ERM) is a common practice to achieve this goal. The idea of ERM is to minimize a cost function on observed data using an optimization algorithm. Therefore, fundamental question is: given a training algorithm, does it produce solution with good generalization? This question has been the subject of substantial body of literature, which answers this question in terms of the implicit bias of optimization methods such as stochastic gradient descent (SGD). For example, one line of works considered the case where gradient methods converge to minimal norm solutions
kernel regression (Bartlett et al. 2020 Tsigler & Bartlett 2020 Liang & Rakhlin 2020 Liang et al. 2020), and then analyzed the gencralization propertics of those minimal norm solutions by bias variance Iradeoff. Another line of works focused on the Neural Tangent
Kernel (NTK) regime (Allen-Zine Zhu et al. 2019 Arora et al., 2019 Cao & Gu 2020 Ji & Telgarsky 2020 Chen
et al. p021) where SGD iterates converges to a global minimum with short distance from initialization.
They suggested to use norm-based measures to theoretically derive generalization bounds. Specifically,
these papers studied the generalization of (deep) neural networks norm-constrained parameter space

---

Published in Transactions on Machine Learning Research (10/2022)
W = ( W B(0, R)}; where W is the collection of weight matrices for all layers, and B(0, R) is ball with radius R. On the NTK regime, SGD with random initialization is proved to be able to find global minimum in the parameter space ((0, R) with R R=V=" (O(L)) y, where y is the label and O(L) is the NTK matrix defined on the training imput data (Arora et al. 2019 Cao & Gu 2020). All of these works have made significant progress on the interplay of optimization and generalization. However, the settings that they focused on are specific in the sense that (1) the phenomenon of norm minimization has only been proven to occur with the quadratic loss with appropriate initialization scheme; (2) R has been thcoretically obtained only in the NTK regime; (3) these works has considered the models after convergence and the generalization analysis of models during training are not completely understood. Therefore, the connection between optimization and generalization still remains incomplete understandings in general scenarios.
In this paper, we aim to tackle these issues by studying the connection between optimization and generaliva- tion of a wide class of machine learning modcls. Thus, a more precise analysis of how the parameter evolves when the training time varies is needed. For this purpose, inspired by the Lojasiewicz gradient inequality (LGI) condition in Bolte et al. (2007), which states that the gradient norm is lower bounded by some power of the value function, we consider uniform version of LGI that extends this condition to a non-vanishingly small set. Specifically, we propose the Uniform-LGI (Definition 2.1 which is a modified version of the LGI. This assumption plays a critical role in connecting optimization and generalization through norm-based gen- eralization bounds. The first section is dedicated to the numerical validation of the Uniform-LCe on different machine learning models. By introducing the local Uni condition along the optimization path, we derive convergence rales and generalization bounds that yield bias-variance tradeoffs during training. Our framework can be applied to a broad class of machine learning models to obtain optimization results and generalization estimates.
Contributions. Our contributions are three-fold:
First, we design a finite sample test algorithm to verify the Uniform-LGT condition along the training path. Our numerical results suggest the Uniform-LGI condition is generally satisfied when training machine learning models and more general compared to the (Polyak 1963). Then, we propose framework for connecting optimization dynamics and general- ization performance based on the Uniform-LGI condition.
(PL) condition
Specifically, we first analyze the convergence rate for the loss functions that satisfy the Uniform- LG1 condition (Theorem 2.2 under the gradient flow algorithm. Through Rademacher complexity theory, we derive generalization bound (Theorem 2.3) for a wide class of hypothesis spaces that holds during the training process. The generalization bound exhibits bias varinnai tradeoff pattern.
We illustrate different use cases of our framework, showing how we obtain generalization estimates for a linear regression problem (Theorem 3.3 kernel regression (Theorem 3.5), and two-layer neural networks (Theorem 3.8 for shallow networks & Theorem E.8 for overparameterized case). These bounds are derived in unified way, and either match existing results derived for individual cases expand upon the scenarios where we can rigorously establish the phenomenon of benign overfitting.
2 Main Results
In this section, we present our main results. We first introduce the notations and the problem setting in Scction 2.1
We then in investigate the key ingredicnt, the Uniform-LGI condition of our framework in Section 2.2 Lastly, we derive optimization results and generalization bounds for the gradient flow trajectory under the Uniform-I.GT condition.
in Section 233
2.1 Setup and Notations
Consider a hypothesis space JF [f(w,)) -) IR + w W), where W a parameter set in Euclidean space. Given loss function
R x R
R, and training set S v1); C IRd x R with n
2

---

Published in Transactions on Machine Learning Research (10/2022)
independent and identically distributed (1..d.)) samples from a joint distribution D, the goal of ERM is to optimize the empirical loss function (w) on S:
min (w)) = n W
(f(w..)).)).
(1)
Notations. We use ||-I| to denote the E norm of a vector or the spectral norm of a matrix, and use ||-I1r to denote the Frobenius norm of a matrix. For two vectors, we use ()) to denote their inner product. For a symmetric matrix A, we use (Ain(A), resp. Amax(A) to denote the smallest, resp. the largest, cigenvalue of A. For any non-negative integer n, let [0: n] (0,1, n]. We use O()) to denole the Big-O bound.
2.2 Investigation on Uniform-LGI
Now we introduce the key component of our Tramework: the Uniforn-LGI, a condition that holds for a wide class of loss functions. We give several examples of loss functions that satisfy the Uniform-LGI. Our numerical results suggost that the Uniform-LGI is generally satisfied when training neural network models.
The classical LGT gives lower bound on the gradient of disferentiablee function based on ils value above its minimum. Many functions, e.g., real analytic functions and subanalytic functions, satisfy this property, at least locally (Boltc et al. 2007). Here, we require a uniform version of this incquality as a condition to control the optimization Irajectory. Let us define this notion below.
Definition 2.1 (Uniform-I.GI) A loss function [(w) satisfies Uniform-LGI on a set S with constants e 11/2,1) and <> 0, if
e [[ e (C(w))-min min ((v) Ve E S. #ES
(2)
The Uniform-LGI is a more general condition than the well-known Pl-condition (Krimi et al. 2016 in
the sense that 1) The p-PL condition is a special case for the Uniform-LGI when c == /2μi 0 = 1/2. The Uniform-LGI contains a wider class of functions than the PL-condition. For instance, consider L(w) = 2
this function satisfies the PL-condition only when k 1. When k 2 2, it satisfies the general Uniform-LGI with 0 1 1/2k. Figures [a), [b), Figure 2 aa, 2(b), 2
()c) show that many nontrivial setups do not have 0 1/2 in practice. Besides, the well-known P PL-condition in (Karimi et al. 2016) is a defined in a neighborhood of a global minimum, indicating that every stationary point is a global minimum, while the Uniform-LGI is more general that is defined in an arbitrary set, where there may exist no global minimum. This yiclds that the Uniform-LGI covers more scenarios than the PL-condition when analyzing optimization properties as it is difficult for an optimization algorithm to find a global minimum in practice.
Note that this is an inequality, so the pair of (c,0) such that the Uniform- LGI holds is not unique. Usually the smallest 0 is defined as the Uniform-LGI exponent. The classical LGI states that for any subanalytic function (Bolte et al.) 2007) including a.e. differentiable models with squared loss, cross-entropy loss and hinge loss, the exponent 0 is strictly less than 1. In the following, give some examples of loss functions satisfying the Uniform-LGI globally over their entire domains or locally along the optimization path.
Global Uniform-LGI. Let the loss function L(WL...., w1) = (Wy ".p.....p. ,,,,, which can be viewed as a one-dimensional L-layer linear neural network model with squared loss on the data (1, Then || = 4(wz ... w1) Σ 1/w, 2 4L(wL- ... w 2-2/4 4L(C)=-1/4, Therefore, L satisfies Uniform-LGi condition globally on R² with c I and
1/2L for L> 1.
Apart from the global Uniform-LGI, there exists large number of loss functions satisfying the Uniform- LGI locally within given range. Since we want to study the optimization and generalization of a training algorithm, next we investigate the Uniform-LGI condition along the optimization path during training.
(Local) Uniform-LGI along the optimization path. Given an initialization w(()), a gradient-based optimization algorithm (e.g. GD, SGD, etc.) produces a series of parameters w((), t0()) 20(2) ((())..., ..... (k) for
the first k steps. If A converges, l can be infinite and the limiting parameter (x(x)) is a stationary point of L(w). To numerically verify the Uniform-I.GT condition (find 0,c) along the entire optimization path
3

---

Published in Transactions on Machine Learning Research (10/2022)
(w()) i.e., find c, such that log [V[(w)] 2 logc 0 log (C(w) minves [(t)) holds on S= (w()) 1==1: we design an algorithm for finite sample test. First, for the first k collected data points, we consider to use linear regression to fit these & data points and get the slope 02, then we adjust с to catch the worst case, i.e., set C = min [[ / (C(w())- ((w))) 0x Then the obtained cg2 0g are the constants such that the Uniform-LGI holds for the first & data points. While numerical experiments can never prove an incquality, it is useful in estimating the constants by looking at the limiting values as the number of points increases. This is called finite-size scaling analysis (Privman 1990) and is frequently used in fields such as statistical physics to investigate numerically the behaviour of infinite-size systems (e.g. phase transitions).
Algorithm Finite sample test for Uniform-LGI
Input: loss function [(w); a collection of parameters ("), w(), w(2), ...., w(k); the optimal loss value [(w"); start point Ku; step
1: for k= 0 to K do
2: calculate the gradient norm || V ((
3: end for
4: for == Ko to K step s do
collect the k data {log (C(w(())-(vv) .lgg [V( ) t-
6: fit. the data by linear regression, and return the slope 0
7:
8 0
||
8:
+ min (C(w()))((ww))))
9: end for
10: fit the data {log (E(w(t)) - L(ww)) log | [[(()))))) by linear regression, and return the slope 0 ||
11: 0k41 + 0
12: CK+1 f minkg]o:k] (C(w()))L(w)) ((w))) x
Output: the estimated Uniform-LGt constants (0k.: CKa)s (o (.
Note that the pair of (c, 0) such that the Uniform-LGI holds is not unique, and the output (0K+1, CK+1) 1) is one possible pair of constants such that the Uniform- LGI holds on the first K collected data points. Intuitively, if Algorithm
| outputs a series of estimated Uniform-LGI constants that converge to some (0",c"), then we have good evidence to support the assumption that [(w) satisfies equation (2) along the optimization === with c'. Moreover, if 0 E [1/2,1] and c O, then L(w) satisfies the Uniform-LCH on { (w) 1' In the following, we present numerical experiments that confirms the validity of the Uniform-LGI along GD/SGD paths on synthetic models and neural network models under Algorithm
path (w(() 1
Synthotic models. We consider training three synthetic models by GD with optimal loss values L(w²) = 0, for which we can provably estimate the Uniform-LGI constants: (a) differentiable but non-analytic loss function L(w)= = - ािं for # 0, 0 for 0. For the non-analytic model, by the classical LGI property we know that there exists no 0 and such that the Uniform-LGI holds around the minimum = 0, which is consistent with Figure I(a); (b) differentiable loss function L(w) = fw + 1 ww For this loss function,
we have [V ~ Oww w ). Therefore, the Uniform- LGI constant @ should be at least 1/4, which is consistent with the result in Figure [b) that the estimated 0 0.308; (c) undetermined linear regression model L(w)= 2n Σx,(w (w x; )2 on synthetic dataset. We know that the squared loss is always strongly convex, thus it satisfies the PL-condition (0 = 0.5), which is consistent with Figure [(c] that the estimated f = 0.5. More details about the experiments are provided in Appendix
C(w)
We report the estimated Uniform-I.GT constants (0ko: ). (0Kots; (Kotss CRots). (0x+ 10x+1.00 +K++, by finite sample test (Algorithm D and denote by (0*, .ct) the final estimation (0K+1,c41)) Figure [ shows three different cases: (a) (0, c) do not converge; (b) (8, c) converge with 0* 1/2 and c* > 0; (c) (8, c) converge with 0* x 0.5. This demonstrate rates les that our method is robust in determining whether model satisfies the Uniform-I.GI.
1 A real function is said to analytic it possesses derivatives all orders and agrees with its Taylor series in neighborhood of every point.
4

---

Published in Transactions on Machine Learning Research (10/2022)
erAh: -0.906.c" 39.192
3ul w: 30.08.. 0.805
Lincar -0.501, =000072
40
0.80
1.50
0.88
1.25
30
eziimated
0.4
0.75
0.84
20
3.50
0.2
0.82
15
10a
10
10" 10a
10
20c
400
600
800
1000
20000
40000
60000 80000 100000
K
(a)
(b)
(c)
Figure 1: Investigation of the Uniform-LGI on synthetic models by finite sample test (estt(Alge (Algorithm I For the non-analytic model (a), both 0 and do not converge. For the synthotic model (b), e converges to positive number but converges a number that is 1/2. For the linear regression model (c), the Uniform-LGI holds along the training path with 0* 0.5 expected since linear regression satisfies the PL condition.
2-aaer 0.781.c" 0.062
ResNet18: 0.737,c'
ResNet: 0.53.c'=0.171
0.8
1.5
1.25
1.00
estimated
asimated
1.0
0.75
0.5
0.50
0.2
0.25
0.00
200
400
600
800
1000
100
200
300
75
100
125
150
175
200
K
(a)
(b)
(c)
Figure Investigation of the Uniform-I.GI condition on neural network models by finite sample test (Algorithm 1 For all of these models, and e converges 0r [1/2, and respectively. Hence, these two models satisfy the Uniform-I.GT condition along the optimization path with constants 0* and c*.
Neural network models. We train three neural network models: two-layer multilayer perceptron (MLP) with width 100 (no bias) the MNIST dataset (LeCun et al. 1998); ResNet18 (He et al.] 2016), Wide- ReseNet- 16-8 (Zagoruyko & Komodakis 2016) on the CIFARI0 dataset (Krizhevsky et al.) 2009). For each experiment, we train the network using SGD (no momentum) with random shuffling, batch size 64 and fixed learning rate 0.01. For the MLP model, we stop the training with 1000 epochs and set the optimal loss value be 0. For the ResNet models, we stop the training once the cross coos-entropy loss is less than 0.001 and estimate the local optimal loss value as minkejo:k] ((w(k)), which is smaller than 10-3, To avoid division by zero, we delete the parameter w" in w(()), w, w(?), ,..., w()) Then we apply the finite sample test (Algorithm 1 with starting point Kg = 50, step
to obtain the estimated Uniform-I.GT constants.
We report (0K,CCK)), (0 K0 CKo+s) ... 1.....,,000 (0k+1, CK41), and denote (0",c") by the average of the last 5 iterates, i..., 8r = (0x-3 +.... 0 (0,c) converge for both models, and the Uniform-I.GT holds along the optimization path.
(CK-3 +... ck+1)/5. As shown in Figure 2 the estimated
Table [ in Appendix A reports the confidence intervals of 0", of 10 independent runs over random ini- tialization and data reshufiling. One interesting observation is that by increasing the width and depth of R8sNet18, the SGD path of Wide-ResNett-6-5 has a smaller Uniform-LGG exponent 6" that close to 1/2. This is parallel the phenomenon in Liu et al. (2020) that overparameterized neural networks satisfy the PT condition. More discussion for the Uniform-T.GI the overparaneteerized networks in Appendix E.5
5

---

Published in Transactions on Machine Learning Research (10/2022)
2.3 Optimization and Generalization Results Under the Uniform-LGI Condition
In Section 2.2 empirical results suggest that the Uniform-LGGI is generally satisfied on the training path for various machine learning models. In this section, we derive optimization and generalization results assumiig that the Uniform-LGI holds. We consider to problem of optimizing the empirical loss (1) with gradient flow:
dw
dt VVL((()))) E [0, +00),
(3)
where wi(t) is the parameter vector at time t, ((() is the initialization. Assume V(r,y) ~ D, ||>||| S 1, /// S 1.
First, we give an optimization result under the Uniform-LGI condition. We show that when 0 = 1/2, the convergence rate is linear; when 0 E (1/2, 1), the convergence rate is sublinear. Furthermore, we give an explicit estimate for the distance between the initialization and the parameter during the training process.
Theorem 2.2 (Optimization). For fired initialization w(),, suppose that there exist On E [1/2,1) and On > 0 such that the loss function (w) salisfies the Uniform-LGI on (w(t) :12 0} with Ous On. Then w(t) converges to a stationary point w(x) with convergence rate given by
1/2: La(w(()) (n(w(oo)) S Se- (Cn(vo())) L. (ww(oo)))
On E (1/2,1) fn(w(()) fn(w((x)) S Ml) ML) 1/(22n -1) (Co( - fn fn((u(())))
where M = (20,, 1) (Ln(1o(0)) - L. (10100))))) 20,-1 The distance between the initialization w( and the parameter w(t) at time bounded by
Bn - -(Cn(eu(t) - Cn (n((w(0))) 1-00 [|w|0) w0Il S cn c1(1-Om) ( - Ln(wolo)))
The proof of Theorem 2.2 is given in Appendix B This theorem shows that if the loss function satisfies the Uniform-I.GT along the gradient flow path, then it converges to stationary point with an explicit convergence rate and distance estimate. The estimation of G. 0, for different n should be analyzed case by case based on the loss function, as shown in Section 3 Our optimization result. can also be extended to the standard gradient descent algorithm. See Appendix for details.
Once we have distance estimate for the parameter during the training process, we can derive gencralization bounds for the norn-constrained parameter space during the training process based on the Rademacher complexity theory. For the generalization error analysis, we assumee that there exists an almost everywhere differcntiable function V Ro+4 + IR such that the model fw.,) can be represented in the following form,
V E Rd, fw, 1 (aj xr ......,,................. a,,
2r vr BI,
......................... B,),..,B,),,
(4)
where ai...., ap E Rd, SI...., B, E R, and w = vec (fai...., ap, S1. .i...., b₂ E igddty vec is the vectoriza- tion that concatenates all clements into a column vector. wide class of functions can be represented in the form including linear functions, fully connected neural networks and convolutional neural networks.
Additional notations. For the loss function l, we use Le(S) to denote its Lipschitz constant (the maximal gradient norm) on S with respect to its first argument. For v in 4. we define L == (T.) (T), T.(p)(S), T. (S), ... I T.(tt((s) (s) where ( the Lipschitz constant of on with ( ........ ......!)) })))) and use CD(w) to de-
respect to the i-th variable. Let () = vec ((at) .....
ap (0) note the expected loss E(ay)=D [([[(w,)) v)). For a = (aI,.... ox) and
(b,,...,,y)) we de- fine Sa,b = {w: Vi e [p].] E [q], |ayll < a, 1 S b,}, and Ma.s = supwes,, w...ss....lll a.Il=ll I. (f(m,z))8) Note that for any loss function E R x + [0. that 1-Lipschitz the first argument, we have that Le(,))) Ma.s
for any a, An example for such a loss function is the ramp loss (Huang et al. 2014) that is commonly used for classification.
6

---

Published in Transactions on Machine Learning Research (10/2022)
In the next theorem, to simplify the notation, we consider studying the generalization of we when the loss Ln (we) first reaches e Ln (w((1) for some given & E [0, Then by Theorem 2.2 the distance [| -well 1-6.
is bounded above by (L
Finally by estimating the initial loss value and the final loss value, we can use the distance estimate to get a generalization bound. To showcase a bias-variance tradeoff, we bound the test error (D(W)) rather than the generalization gap LD (w²) L (wr).
c.(11-p))
Theorem 2.3 (Generalization). For a fixed initialization w(),, suppose that there exist On E [1/2, 1) and Go > O such that the loss function (w) satisfies the Uniform-LGI on (w(t) : 0} with 8n Cn. and assume that there erist Mg, Mg such that with probability at least 1 8-8 over the training samplees S, fn(ww!l)) S Ma. over S, the generalization
Ln En(wlo)) I M&. Then for any given e, 6 E [0, 1], with probability at least bound of any porameter we with La(we) =Ln(w(l) is given by
2 n. 2 (L (L Vni
3(p + + log (4/))
CD(ws) S SELn(w(0)) +
sup
3Ma,bb
(5)
[|a] +||6+ " S2rr
2n
(Ms (Ms-Ms)
-0n (+Ms MM3)
1-Pm
where Tn,5,
en ..,)
The proof of Theorem 2.3 is in Appendix D We use the distance estimate in Theorem 2.2 to get norm- based parameter space w : w - ( I rj. Then this allows us to use Rademacher complexity theory to obtain the generalization ion result. There are several key terms in 5 : (1) Ms: This is a high probability upper bound for loss value at initialization. In practice, for commonly used initialization schemes, such as Xavier initialization Gloort & Bengio, 2010g and Kaiming initialization (He et al., 2015). L. (w(()) is uniformly bounded with high probability: (2) Cx: These two quantities are the Uniform-LCC constants along the optimization path. The asymptotic analysis of Cn is model-dependent,, and we provide several examples in Section 3 (3) Le(Sa,)), Ma,s: These quantities are directly related to the loss function l. For instance, given loss function é IR x R + [0, 1] that is 1-Lipschitz in the first argument, we have that Le(Sa.n)
Ma.s = 1; (4) (S. This term is related to the properties of f. For example, when f iss linear, (z y) = x + y, then [[,y((.,))] = v2. When f is a two-layer neural network, i.c., f(w, 2)) Em v;O(u, z). we will show in (Sa,))l is bounded above by /2r (equation (29h). ) For two-layer neural networks, p and q are both equal to the number of the hidden units, which usually much smaller than the sample size n. In this case, the bound is dominated by the first two terms, which represent a bias-variance tradeoff pattern during training. To see this, if E 1 (no training, high bias, low variance), then fn,,, 0, and the bound is dominated by the initial loss; if Ms/M, (convergence model, low bias, high variance), then the generalization bound is dominated by the model complexity Tn.6e.
Section 3.3 that +|P|||++++++00'=>>>>>
Remark 2.4. The generalization bound also holds for the converged model by simply setting E to be Ms/Ma. In particular, when the final empirical loss value is O, e can be O. For the gradient descent algorithm, one can also directly use the optimization result (the distance bound) in Appendix C to derive the generalization
result. The only quantity that needs to be changed is that Tn,6,- (M,-M.) 0,, (1. (1-1))72)
(cMs -M.)"
where vj is
the learning rate, Bc is the smoothness constant. See Appendix for details.
3 Applications
In this section, we apply our framework (Theorem 2.2 and Theorem 2.3 to three machine learning models. To obtain clean expressions of the generalization bound in terms of the sample size n, we consider range of n related to the dimension d. In particular, we consider underdetermined systems where the ratio n/d remains finite unless stated otherwise:
3 20. 71 E (0, o0), s.t. Vd, rod S n = n(d) S Yid
This setting is non-asymptotic since we do not require d to be sufficiently large. For each application, we consider regression problems with squared loss E(y, (y 0)2 which not globally Lipschitz nor globally bounded. Thus, we cannot apply directly Theorem 2.3 to the squared loss, since requires to bound The (Sa.b) and Mas which depend on a, b and the model architecture. To mitigate this issue, we consider to
7

---

R R - [0,1o] lo] that is VTo-Tipschitz (on the first argument) for some to > 0 and {(y.y) 0. For the squared loss, this can be achieved by truncating l at ly - ğl = vla and then using a constant extension past the truncated point to make it contimuous. In this case, Le(Sa,)) = Vlu. Ma. = lo for any a, b. Finally, to use Theorem 2.3, it remains to estimate the new empirical loss value J -i=1 ((J(wr, v.); y4) in terms of (w=)). By the Lipschitzeess property and Cauchy-Schwarz inequality, one can show that 1 - ((f(w,, v:) S v (2lnCn (see the inequality 22 in Appendix E.1 Combining the above Published in Transactions on Machine Learning Research (10/2022)
evaluate the generalization with new loss l that is globally Lipschitz and globally bounded. Specifically, let :
derivations, applications of the framework are straightforward.
Remark 3.1. One can also get generalization bounds under the squared loss Ely. 0) = (v 2) Note that Ma.6 SUPuES..,,lllIS11 [(w,x) + and (S.,)) suPweS.... [a] $1 ([ x]]] Then can get an upper
bound for LD(Ws) by Theorem 2.3
3.1 Underdetermined & Linear Regression
We begin with an underdetermined linear regression model f(w, 2) w with squared loss:
arg min (w) = 2n i=1 wER4
(w T xs - vi)²
(6)
where the input data matrix X' = (#I....., _TAT E Raxd has full row rank (d > n). Then the above regression model has at least one global minimum with zero loss.
Target function. Suppose the training data generated from an underlying function g Rd + R with y4 = g(z)), Vi E [n]. Let y (31.... .Ba) and assume that there exits c* such that
DIll S c² e Amaxx (X.T)).
(7)
7 actually indicates that g is Lipschitz with dimension independent Lipschitz constant. For example, (z) = "(xT""", where w" Rd with ||w*||2 c² for some constant c", and Φ(-) is Lipschitz with x(0) 0. Assumption 3.2. There exists symmetric positive-definie matrices Σg E Rd with 0 < λo S Amin (23) < Amax (E2) S A for any d, such that the entries of X'E are i.i.d. subgaussian random variables with zero mean and subgaussian moments bounded by
This assumption is reasonable in practice in the sense that it only requires the data (rows of the data matrix X)) to be i.i.d. and entries of each row of X (Feature vector components) are not necessarily independent.
By applying our framework, we get the following optimization and generalization results for the models during training when the empirical loss function (w(w)) = =Cn (L)))
Theorem 3.3. Consider the undertermined Eg linear regression model Suppose that there erists conslant co lhhl is independent of d such that || S co- Then the Jollowings hold:
L. (w) salisfies Uniform-LGI along the gradient flow curve (u(0:120) 0} with Cn.
(xx
On 1/22.
2. Ln (w) converges to zero linearly, i.e., (w(()) S cxp (~2Xmin (XXTtt/m) L. (w)()))
3. If E 10, then under Assumption 3.2 for any 2 0 and any target function that satisfies with probability at least 1 -8 8- 8-78 7d -dd-nI- r over the training samples S, the generalization bound of the parameter we with (u(w)) = ELn for some E E [0, 1] is given by
7
A(co + c²))
/ /211-c)d1 Ag
(+
+
log(4/6)
VTo
en
3
log (46)
B(Z.g)D Le ([(,,,) S (w(())(((0)))
-3
C
vn
2n
where c, C, C > 0 and r E (0,1) depend only on the subgaussian moment of the entries.
2hh subganssian moment of X defined as inf {M 2M200 Retx S MMPR1, WERR.
8

---

Published in Transactions on Machine Learning Research (10/2022)
The proof of Theorem 3.3 is given in Appendix E.1 The generalization bound reveals bias-variance tradeoff for the linear regression model in the high dimension setting. For 1, the generalization bound is domi- nated by the initial loss. For = 0 (convergence model), we get a generalization bound O (Vlog(1/8)/m)
Comparison. This result is related to Bartlett et al.] (2020) that studied the phenomenon of benign over- fitting in high-dimensional & linear regression. First, we summarize the different settings and assumptions in our paper and Bartlett et al. (2020) through example: the training data {(2, ) C C x R are i..dd drawn from D. In our case, for any (z,z) E D, y x x==" """ for some w* E R with uniformly bounded norm in d, and entries of z are ii.d. (thus Ao = A1 = 1) with mean O, variance Σ = E [[xx"] (diagonal). Thus E has a flat spectrum with condition number 1. We further assume that || I 1 for all d. Let E Raxd y = (yi,...,yh, E IR" then the minimum norm solution v = xty (f is the pseudo inverse). Let the excess risk E [g[(x --xx " )²,, then our result states that E (z/ given that d and n diverge but their ratio remains finite. Now we consider new data set {(ē,, 9: [= C H. x E that are iid. drawn from D. In Bartlett et al. (2020), the setting is that for any (#. ÿ) E D, 9 TT for some T= E IRd with uniformly bounded norm in d, and entries of E are independent with mean O, variance Σ = [[ If the entries of i are independent, then Σ is diagonal. Let the minimum norm solution w.r.t. the new data set Φ- = Xty, then is shown in Bartlett et al. (2020) that when E has a suitable decaying eigenspectrum, the excess risk É = Ez((d T w - a "-)²"=+]+- we can see that there exist two cases for benign overfitting: the data covariance matrix has a decaying eigenspectrun (Bartlett et al.] 2020); the data covariance matrix has flat eigenspectrum but each data vector has bounded norm (Theorem 3.3). Due to the rescaling of the data vector, even though Σ has a flat eigenspectrum, the benign overfitting provably happens when te has a bounded norm. To have better understanding of the benign overfitting phenomenon when the data covariance matrix has a flat cigenspec- trum, we consider an example in Bartlett et al. (2020) that we can deduce from our result. Under the same notation as above, we consider the following data transformation for any (x, y) E D: ă = $1/2zvd, /-1/3=" lva
x= -=..........)
+ when n - co. Therefore,
w' |5-1/2m /Vd 1 15-1/2m /va
y
Then the induced new data distribution D satisfies the assumptions Note that X = 25/12//,55
1/- /val thus the minimum 1/2w0-11 Therefore, the excess risk E = Ex w - - -- |5-1/2 /Vlla We can see that there exists an explicit relation between E and E. In the high dimension setting (d and n diverge but have a finite ratio), our result shows that E = =((/VV)). We consider a benign overfitting example in (Brtllttt et al. 2020 Part 1 of Theorem 6): the eigenvalues of Σ decay with a rate given by 1. Now we show that É + 0 when entries of w" are order 1/Vd. Notice dva
and settings in Bartlett et al. (2020). norm solution w- = x T
172
oj j log P(++1 with 3 dva
that |8-1/9 assumptions and settings to analyze the case of sharp eigenspectrum for benign overfitting, and get result that is consistent with Bartlett et al. (2020).
E
ava O. In summary, we can transform our E j
3.2 Kernel Regression
Consider a positive definite kernel : X X + RR with a corresponding feature map P Rd + F satisfying (p(x), ((y)) v). We assume that [k(2,x)) S Vr E X. Tet H be the reproducing kernel Hilbert space (RKHS) with respect to k. If J R², then the kernel regression model with Ez loss is to solve the following problem
1 n
arg min (w)
Σ (w i=1
(((x)()))))))))))))))) vi)²
(8)
wER
2n
Similar to the & linear regression case, we consider the following target function:
Target. function. Suppose the training data is generated by an underlying function g : Rdd + R with y = g(x),, Vi E [n]. We further assume that there exists c² > 0 such that
| S c- Vimaxe (k(2 X)).
(9)
where k(X, X) is the x n kernel matrix with k(X, 2)ij = k( 25)
9

---

Published in Transactions on Machine Learning Research (10/2022)
"w") where w" E E with (Vs) ||"*) 1l2 S c* for some constant c², and o(-) is Lipschitz with ((0) = 0. To get the generalization results of kernel regression. we will discuss two types of kernels separately: radial basis function (RBF) (Broomhead & Lowe 1988)
For instance, the following functions satisfy ( g(x) <(v((x))
kernel and inner product kernel.
RBF kernel. We study the RBF kernel of the form k( y) = e (lly - ==I) for a certain RBF @. For the input data, we define the seporation distance of X as SD = min; || - zyyl Vi,j E [n].
x E3e where Σ is defined in Assumption 3.2 Inner product kernel. We consider k(æ, y) e
Following El Karoui et al. (2010), we make the following assumption on the function
Assumption 3.4. @ C in neighborhood of 0 with e(0) = 0, e(1) / (0) 2 0, e0 2 0.
We now apply our framework to get optimization and generalization results for the final convergence model when 0. For the RBF kernel, the generalization bound depends on the separation distance of the samples. For the inner product kernel, we study the spectrum property of the high-dimensional random kernel matrix.
Theorem 3.5. Consider the kernel regression model (6). Suppose that there erists constant co that is independent of d such that [| ||, S co. Then the followings hold:
1. (w) satisfies Uniform-LGI along the gradient flow curve {wl)) :t 0} with Cn On = 1/2, where en is controlled by the kernel and inpul samples.
2. Cn (wo!)) converges to zero linearly, i.e., (wl()) S exp (-2Xanin (k(X,x)))t Cn(((").
For any target function that satisfies we have:
For the RBF kerne suppose that e: 1220 -220 is decreasing function and e (1|==1) E L (BR.). If there erists two positive constants qmin and qmax such that SD E 19mins Imax] for all n, then with probability at least 1 1-8 over the training samples, the generalization bound of the parameter we with fu (w:)) = =cLn(w(0) for some E E 1] is given by
BlawYD [e (((((e,) v) S 2loefn(wv()) Clco, 6", e, dl Qmins 1max ) VT +310 V
log (4/)
/n
2n
where C(ey, c², e, d, Qming Imax) is a constant that depends only on Co, c², 0, d, Amin: 9max- For the inner product kernel, under Assumption 3.2 small enough such that d (V35-1/2 + log 0.51
if d is large enough and ô > 0 is (.5( g' g(()), then with probability at least 1 8 - d= over the samples, the generalization bound of the parameter we with (w(w)) = eLn (w) for some E E [0, is given by
&
3.4
C c(1 (log(1/8)///)) VI-E
3 + log (4/8)
B(aWYD (((e; s /
+3l0
2n
where C depends en c", m, d (0), e' (0), e(1) and the subgaussian moment of the entries.
The proof of Theorem 3.5 given in Appendix E.2
Example 1. Kernels satisfying the conditions and assumptions in Theorem 3.5 include (1) RBF Gaussian:
e(r) pr? pr? .P 0; (2) RBF Multiquadrics: e(r) = (p (2)02) 0,8 E 2 8 < -d; (3) Inner product
Polynomial kernel: p(r) = T r e E Zz,
B 2 2: (4) NTK corresponding to Two-layer ReLU neural networks
on sd-1(Vd); e(r) r(5 arccus(r))
2x
The result of the inner product kernel is related to Liang & Rakhlin 2020 who derived generalization bounds for the minimum RKHS norm estimator. They showed that when the data covariance
Comparison.
Here d fixed and varied.
10

---

Published in Transactions on Machine Learning Research (10/2022)
matrix and the kernel matrix enjoy certain decay of the cigenvalues, the generalization bound vanishes n goes to infinity. For example, for exponential kernel and the covariance matrix E: [[(xx] ' with the j-th eigenvalue Ay(2:) = j_ the l generalization bound becomess ( when a E (0, 1) and n > d. In comparison, we do not assume the eigenvalue docay property for the covariance matrix and still are able to obtain an optimal generalization bound O (n-1/3) in the high dimension setting. Further, we exlend the works in Liang Rakhlin (2020) by proving a new result of the RBF kernel. Note that the result of the RBF kernel is not under the high-dimensional setting; thus it is not a direct adaptation of Liang & Rakhlin 2020), and the proof itself is of independent interest.
3.3 Two-layer Neural Networks
In this section, show that our framework can be applied to neural network models. We obtain gener- alization bounds for shallow neural networks under the Uniform- LGI assumption. First, define a two-layer ReLU neural network with width m:
f(w,z) = TTUx)) = Σ uro( xt)
(10)
where (xx) = max (0, x), x E Rdd is the input, = "m)) T E Rm. U= (u1,..., Umm) E Rmxd are the parameters, w = vec (1v,U)). Trivially, there exists an almost everywhere differentiable function V : Ram + R with V (81,..., Sm, (1,..., ..)..))) Ein st0(1:) such that 44) holds. We consider minimizing i the quadratic loss (w(w)= == 2n Ei (f(w, - 3² by gradient flow (3) under a fixed initialization w(").
The numerical observations in Figure 2 show that the Uni condition is generally satisfied on each optimization path when training the neural network models (including the two-layer neural networks). In the next proposition, we theoretically prove that there exist On > 0, 0, E [1/2, 1) such that the Uniform-LGI holds for the gradient flow path over each choice of the training samples.
Proposition 3.6. For a fized initialization w!!) and a fixed choice of the training sample Sn with size n, there exist two constants e, (Sa) 0, (S,) E [1/2,1) 1) such that. the loss function (n(w) salisfies the Uniform-L.G along the gradient flow curve {wit) :t 2 0} with c. (S,), O,((s). Specifically, for the population loss (D(w) and its induced gradient flow curve {w : t 2 0}, if Lo(w) is subanalytic (Bolte et al., 2007)), then there (2) exist op > 0, 0D E 1) such that (w) satisfies the Uniform- LGI along (wi :t 2 0} with cD, Op.
The proof can be found in Appendix F.3 Note that the Uniform-I.GT constants c, (S.): (s(,) are random variables that depend on the choice of the training sample Sn- Based on the limiting values (cD, fp), we make the following assumption that c, (S.). > 0, (S.)) (1/2,1) hold uniformly with high probability over the choice of Sn.
Assumption 3.7. For the Uniform-LGT constants in Proposition and any 5 E (0. 1), there exists Cr,5 > O, 0n,8 E [1/2, 1) such that with probability at least 8/3 over the sample Sn: (Sw) S 6n,5. Cn (S.) 2 Cn.6.
This assumption ion is also supported by the statistical results in Table Indeed, the numerical results suggest that the Uniform-LGI constants satisfy this assumption with high confidence over the training sample. We are now ready to state the main result for the two-layer neural network model.
Theorem 3.8. Consider the bwo-layer newral nelwork model
10 with inilialization (0) Under Assumption
7.7 for any ó E (0 we have the following:
With probability at least 1 - 5/33 over the training sample, the convergence rate is given by
0n.6= = 1122 (n(w(() - (m(()(o)) S se- (La - Ln (n( 6n.5 E (1/2,1) (n(w0)) Cn(w(oo)) < (1 Mt) 1/(20, -1) (C,((w Ca (w(os))))
where M = 22,6(20 1) (Ln (w)(0)) 20n0-11

---

Published in Transactions on Machine Learning Research (10/2022)
Under Assumption 3.2 assume that there erist Ms such that with probobility ot least 1 8-22 over the training samples S, f.n (wloo)) S Ma- for any target function that salisfies (7), then with probability at least 1 - 8 over the training samples, the generulization bound of the parameter we with Ln( (we) E =Ln (w) for some E E [0.1] is given by
(Ō (og(+/g(())) 1-0 - (EMo - M
4
B(r.))/ [ (), s
+
+
Vn
Cn.o Bm,s))
6m + (0g(12/6)
3l0
2n
where Ö depends only on c², 7o. No |1 and the subgaussian moment of the entries.
The proof of Theorem 3.8 is provided in Appendix E.4 We can see that for shallow neural networks (m much smaller than n), the generalization bound is dominated by the first two terms. When the gradient flow converges to global minimum with zero training loss (Ma 0), then the generalization bound for the convergence model (e 00 reduces to Ö ( 0,,,)= -2 1/2), where Ö hide the logarithmic factor.
Empirical evaluation. To remonstrate that our generalization bound is non-vacuous and can effectively capture the test error, we perform experiments on the CIFAR10 dataset (first two classes). First, we get the Uniform-LGT constants Cn,5. ,n,5 by finite sample test (Algorithm [ with varied sample size n. Then, we calculate the generalization bound (up to some constant). cT.6 6n,s) 1/2 + vm/nn. Finally, we randomly flip the label and record the Uniform-LGi constants Cn,5, in,s with different ratio of label flip. See Appendix for implementation details. From Figure 3 (a), we observe that Cn,6; fn,5 have good dependency the sample size n. Figure 3 (b) shows that the generalization bound decreases as increases, indicating (c), when the ratio of label flip increases, Co,5 decreases and On,s increases. Our results (Theorem (38) show that if Cn.5 decreases and On.5 increases, then we should expect worse optimization and generalization error, which also correlates with the known findings that random labels negatively affect both optimization and generalization Zhang et al. 2016
that our bound is non-vacuous, As shown in Figure (c),
CIFAR10 fairplane automobilet
CIFAR10
CIFAR10 (airplane auromobilee)
1.0
condaaris
9..0
Generalization hound
2.5
Uniform constamts
0.8
6.66
2.0
0.6
8,,0
0.4
0.4
Cr
1.5
0.2
0.2
2000
4000
6000
8030
19000
2000
4000
6000
9003
10200
0.0
0.1
0.2
0.3
0.4
0.5
Sample size
Semple size
Ratio of label flip
(a)
(b)
(c)
Figure 3: (a) The Uniform-LGG constants Cn,d, On,8 obtained by finite sample test (Algorithm) 1 with respect + /m/n on the sample
to sample size n. (b) Dependence of our generalization bound 5, 0n,s) 22,,))22n-11 11/2 size (c) The Uniform-LGH constants Cn,6, On,s with respect to the ratio of label flip. All Results are reported with the mean and standard deviation over 5 independent runs.
Overparameterized neural netowrks. Our generalization bound bocomes vacuous when m is large enough. But for overparameterizel neural networks, the PT. condition (0n,s = 1/2) is proved to hold in the NTK regime (Liu et al.) 2020). To make our framework complete, we derive optimization and generaliza- tion results for the overparameterized two-layer neural network. The generalization result is based on the Rademacher complexity theory in Arora et al. (2019) in the NTK regime. In particular, we theoretically show that 6n.5 = 1/2 and Gn,5 = (1) over the training sample and standard random initialization when m is large enough, and we give a generalization bound of order O (Vog((n0)/m) which confirms the phenomenon of benign over-fitting in the high dimension setting. More details are provided in Appendix E.5
12

---

Published in Transactions on Machine Learning Research (10/2022)
4 Related Works
Optimization. Thcoretically analyzing the training process of most machine learning models is chal- lenging problem the loss landscapes are generally non-convex. One approach to studying non-convex optimization problems is to use the Dolyak-Lojasievves (PL) condition (Polyak] 1963), which characterizes the local geometry of loss landscapes and ensures the existence of global minima. Tt is shown in Karimi ct al. (2016) that GD admits linear convergence for a class of optimization objective functions under the PL condition. In this paper, we modify the original LGT to obtain convergence rales (not necessarily converges to global minimum) and generalization estimates during the training process.
Generalization. Traditional VC dimension-based generalization bounds depend on the number of pa- rameters and are vacuous for large models such as overparameterrize neural networks. To overcome this limitation, several non-vacuous generalization bounds are proposed, e.g. the norm /aam//mmaannnaedeedeee generaliza-
tion bounds (Neyshabur et al. 2015; Bartlett et al.) 2017
Golowich et al.] 2018 Neyshabur et al.] 2019).
and the PAC- PAC-Bayes-basee based bounds (Dziugaite & Roy 2017 Neyshabur et al. 2018 Zhou et al.] 2019 Ri-
vasplata et al. 2020). However, these bounds tend to ignore or focus less on optimization, e.g., norm-basod generalization bounds may not discuss how small-norm solutions are obtained through practical training. In this paper, we connect the optimization and generalization by deriving generalization bounds based on the optimization path length during training model training.
Interplay of optimization and generalization. Implicit bias builds the bridge between optimization and generalization, which has been widely studied to explain the generalization ability of machine learning models. Recent works (Soudry et al. 2018a b Nacson et al. 2019a b Lyu & Li. 2020 showed that linear
classifiers or deep neural networks trained by GD/SGD maximizes the margin of the scparating hyperplancs and therefore generalizes well. Other works (Arora el. al.,
2019 Zou & Gu 2019 Cao & Gu 2020: Ji
& Telgarsky 2020 Chen et al. 2021 considered overparameterizett neural networks in the lazy training regime where the minimizer has good generalization due to the low "complexity" of the parameter space. In this work, we focus on specific conditions on loss functions under which we can connect optimization and generalization on the situations which do not satisfy those above.
Comparison with existing works on the LGI condition. Recent work by Frei & Gu 2021 studies optimization and generalization via general PL-conditions. Their key assumptions, problem settings, and type of results differ from ours on many aspects. In Frei & Gul (2021), the authors analyze loss function f that satisfics the (g:E, a; p)-proxy PL incquality, which is a more general condition than the LGI in this paper. For example, by setting g = J. = min [ww,, the proxy PL inequality corresponds to the LGI. However, a key assumption in Frei & Gu (2021) is that f(w) satisfies a (g. E, a, p)-proxy PL inequality globally for all w E RR, while our assumption only requires that f(w) satisfics the LGI locally, e.g., along the optimization path. For the problem settings, we cover different situations. Frei & Gu (021)) considers the online learning setting where samples are observed one-by-one. In contrast, we focus on the classic gradient flow /descent setting, where the training samples are given before training. Thus, these two works provide different types of results. Through the global proxy-PL incquality, Frei & Gu (2021) gives an upper bound for the best case of the test error, i.e., minker (D(w))). In this work, we obtain bounds for the test error (o(w(() for any time t, which can be used to showcase bias- variance trade-off patterns. For instance, a simple application of our theory yields a new case of benign overfitting on linear/kernel regression in the high dimensional set ting (Theorem 3.3 & 3.5 Moreover, in this work, we propose a finite sample test algorithm that can be applied to verify the Uniform-LGG and estimate the Uniform-I.GT constants for standard deep learning settings. Another work by Poster et al. (2018) studies similar LGI conditions. Under the key assumption that the population risk [w) satisfies the LGI some given parameter space W, the authors show that the excess min risk -nitee-inwew LD (w) is bounded above by supwew VV vLD(w) (w)ll- In practice, it is not easy to validate whether Ep satisfies the LGI because it depends on the data distribution and requires a very large number of samples. In comparison, we only assume that the empirical risk (w) satisfies the LGI along the training path, and the Uniform-LGI condition can be numerically verified by the finite sample test algorithm. Under these two different assumptions, both our results and those of Foster et al. (2018) yield consistent generalization bounds (l/ for the linear regression models in the high- digh-dimmnsional setting. A local version of the PT. condition has been studied in Chatterjee (2022). This local PT, condition is
13

---

Published in Transactions on Machine Learning Research (10/2022)
particular case of our Uniform-LGI with 9 1/2. In the case of feed-forward neural networks, Chatterjee (2022) show that gradient descent with proper initialization converges to global minimum given that (1) the activation functions are smooth and strictly increasing; (2) the minimum value of the parameters is large enough; (3) the learning rate is small enough. In this work, we give both convergence guarantce (to a local minimum) and generalization analysis based on the Uniform-I.GI condition.
5 Conclusion
In this work, we address the questions of when and why an optimization algorithm finds a minimum with good gencralization propertics. For this purpose, we propose framework bridge the gap between optimization and generalization based on the optimization path. The pivotal component the Uniform-LGI condition: condition the loss function that is generally satisfied during the training of standard machine learning models. Using this assumption, we show that gradient flow converges to stationary point with an explicit convergence rate and we derive generalization bound that hold during training. Finally, we apply the framework to three widely used machine learming models. By estimating the optimization path length, we get non-vacuous generalization bounds, even in the high dimensional case.
6 Acknowledgement
We thank the anonymous TMLR reviewers for several helpful comments. H. Yang is partially supported by the US National Science Foundation under award DMS- 2244988, DMS-2206333, and the Office of Naval Research Young Investigator Award. Q. supported by the National Research Foundation, Singapore, under the NRF fellowship (project No. NRE-NREF13-2011-000
14

---

Published in Transactions on Machine Learning Research (10/2022)
References
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. In Advonces in neural information processing systems, pp. 6158-6169, 2019.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. Tn International Conference Machine Learning, pp. 322 332. PMLR, 2019.
Peter Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally normalized margin bounds for neural networks. In Advances in Neural Information Processing Systems, pp. 6240 6249, 2017.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):30063330000 2020.
Jérôme Bolte, Aris Danillidis, and Adrian Lewis. The lojasiewicz inequality for nonsmooth subanalytic functions with applications subgradient dynamical systems. SIAM Journal on Optimization, 17(4): 1205-1223, 2007.
David S. Broomhead and David Lowe. Multivariable functional interpolation and adaptive networks. Complex Syst., 2, 1988.
Yuan Cao and Quanquan Gu. Generalization error bounds of gradient descent for learning wer-paaammterrize deep relu networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3349 3356, 2020.
Sourav Chatterjee, Convergence of gradient descent for deep neural networks. arXiv:2203.16/ 16462, 2022.
arXiv preprint
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much over over- prremetrimmeiiioonnnnn is sufficient to learn deep relu networks? In International Conference on Learning Representations, 2021.
Benedikt Diederichs and Armin Iske. Improved estimates for condition mumbers of radial basis function interpolation matrices. Journal of Approzimation Theory, 238:38-51 51, 2019.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over- parameterized neural networks. In International Conference on Learning Representations, 2019.
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Proceedings of the 33rd Annual Conference on Uncertainty in Artificial Intelligence (UAI), 2017.
Noureddine El Karoui et al. The spectrum of kernel random matrices. Annals of statistics, 38(1):1 50, 2010.
Dylan J Foster, Ayush Sekhari, and Karthik Sridharan. Uniform convergence of gradients for non-convex learning and optimization. Advances in Neural Information Processing Systems, 31, 2018.
Spencer Frei and Quanquan Gu. Proxy convexity: unified framework for the analysis of neural networks trained by gradient descent. Advances in Neural Information Processing Systems, 34:7937-799 2021.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, 2010.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural net- works. In Conference On Learning Theory, pp. 297-299. PMLR, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human- level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026- 1026-1034, 2015.
15

---

Published in Transactions on Machine Learning Research (10/2022)
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognilion, pp. 770-778, 2016.
Xiaolin Huang, Lei Shi, and Johan AK Suykens. Ramp loss linear programming support vector machine. The Journal of Machine Learning Research, 15(1):2185 2211, 2014.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks. In International Conference on Learning Representations, 2020.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradient methods under the polyak-lojasiewicz condition. In Joint European Conference on Machine Learning and Knowledgee Discovery in Databases, pp. 795-8 811. Springer, 2016.
Alex Krizhevsky, GeofTrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Beatrice Laurent and Pascal Massart. Adaplive estimation of quadratic functional by model selection. Annals of Statistics, pp. 1302-13801 1228,, 2000.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied docu- ment recognition. Proceedings of the IEFE, 86(11):2278 2324, 1998.
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes. Springer Science Business Media, 2013.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. The Anmals of Stalisties, 48(3):1329 1347, 2020.
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the multiple descent minimum-norm interpolants and restricted lower isometry of kernels. In Conference on Learning Theory, pp. 2683-2711. PMLR, 2020.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over- peer-arramtteiied non- linear systems and neural networks. arXiv preprint arXiv:2003. 00307, 2020.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. Tn International Conference on Learning Representations, 2020.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Stephen J Montgomery-Smithh. The distribution of rademacher sums. Proceedings of the American Mothe- matical Society, 109(2):517-522, 1990.
Mor Shpigel Nacson, Suriya Gunasckar, Jason D Lee, Nathan Srebro, and Daniel Soudry. Lexico- graphic and depth-sensitive margins in homogeneous and non-homogeneous deep models. orXiv preprinl arXiv:1905.07333 2019a.
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 3051-3059. PMLR, 2019b.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401, 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-bayesian approach to spectrally- normalized margin bounds for neural networks. In International Conference on Learning Representations, 2018.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LoCun, and Nathan Srebro. The role of por-paraanttizaaioon in generalization of neural networks. In International Conference on Learning Rep- resentations, 2019.
16

---

Published in Transactions on Machine Learning Research (10/2022)
B. Polyak. Gradient methods for the minimisation of functionals. Ussr Computational Mathematics and Mathemalical Physics, 3:864-874 878, 1963.
Vladimir Privman. Finite size scaling and numerical simulation of statisticol systems. World Scientific, 1990.
Omar Rivasplata, Ilja Kuzborskij, Csaba Szepesvári, and John Shawe-Taylor. Pac-bayes analysis beyond the usual bounds. Xr preprint ar::::0006. 13057, 2020.
Mark Rudelson and Roman Vershynin. Smallest singular value of random rectangular matrix. Commu- nications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 62(1)):170 1739, 2009.
Mark Rudelson and Roman Vershynin. Non-asymptotie theory of random matrices: extreme singular values. In Proceedings of the International Congress of Mathematiciaas 2010 (ICM 2010) (In 4 Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II-IV: Inviled Lectures, pp. 1576-1602 World Scientifie, 2010.
Daniel Soudry, Elad Holler, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1):2822 2878, 2018a.
Daniel Soudry, Flad Hoffer, and Nathan Srebro. The implicit bias of gradient descent on separable data. International Conference on Learning Representations, 2018b.
Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. arXiv:2009114886 2020.
arXiv preprint
Holger Wendland. Scottered Data Approzimation. Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, 2004.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint arXi::1605.071 07.460 2016.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: 1.05500 2016.
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, and Peter Orbanz. Non-vacuous generaliza- (ion bounds the imagenet scale: a PAC-bayesian compression approach. In International Conference Learning Representations, 2019.
Difan Zou and Quanquan Gu. An improved analysis training over-parameterrzzed deep neural networks.
In Advances Neural Information Processing Systems, 2019.
17

---

Published in Transactions on Machine Learning Research (10/2022)
A Experiments
In this section, we provide statistical rosults for the Uniform-LGI constants obtained by Algorithm and details of the numerical evaluation of Figure and 3
Experiments details for Figure 1 All the three models are trained with gradient descent with fixed learning rate 7). Specifically, the following lypee--aaaameeers are used for training: for model (a), initialization
w()) = 0.1, 77 0.1, epoch K 10", start point Ko 50, step 109; for model (b), w( = L, 1 0.01, epoch K = 10a start point Kg = 50, step 10; for the linear regression model (c), the dataset contains 100 points {(2,, 4)) 100 |2000 R, where r. (vi [100]) are uniformly drawn from the 200-dimensional unit sphere, and y: (Vi E [100]) are generated by linear target function y/ 3 xg for some 3 E 1R200 with ||]|= We train with random initialization, 0.1, epoch K = 10 start point Ko = 50, step s = 100.
Next, we list experiments details for Figure
Dataset. We use the CTFARI0 dataset our numerical evaluation. In particular, we only select the first two classes (airplane versus automobile) with totally 10000 training images. For the experiments in Figure 3 (a) and (b), we randomly choose the sample from the whole 10000 training images with size 1000, 2000, .... 10000, where each class has the same sample size. For the experiment in Figure 3 (c), WC use the whole 10000 training images.
Model. We use two-layer fully connected neural network (no bias) with width m = 512, ReLU activation as the training model.
Optimizer. We optimize the cross entropy loss by full batch gradient descent with random initialization and leaning rate 0.01. We stop training once the training loss is less than 0.001 epoch reaches 20000. We do not use weight decay, dropout or batch normalization.
Label flip. We only flip the training labels with different ratio.
Uniform-LGI constants. We calculate the Uniform-IGI constants by the finite sample test (Algorithm I after the training. For the obtained training parameters wx(k) at epoch for E K], we estimate the optimum w* of [(w) as arg arg kin To avoid division by zero, we delete the parameter w" in w
..... wK)) Then we apply the finite sample test (Algorithm) 1 with start point Kg 1000, step = 100 to obtain the estimated Uniform-LCG constants. We set (cn,5, 6n,5) to be the final estimation (cK+1, 0x1). We report the results with the mean and standard deviation over 5 independent runs.
The following table shows the statistical results of different models' Uniform- constants obtained by Algorithm !
Model
c*
Linear Regression
0.496 + 0.001
0.063 = 0.0015
2-layer MLP
0.785 + 0.005
0.066 = 0.013
RosNet18
0.751 = 0.019
0.068 = 0.016
Wide ResNet
0.514 + 0.011
0.169 0.037
Table 1: Mean and standard error for the Uniform-LGI constants 0* c* obtained by finite sample test (Algorithm over 10 independent runs over random initialization and data reshuflling.
B Proof of Theorem 2.2
In this section we will prove Theorem 2.2 The proof contains two parts, one is the convergence of the gradient flow, and another is the convergence rate derivation.
18

---

Published in Transactions on Machine Learning Research (10/2022)
Proof. First, by the gradient flow (3), we have
d. (uoll))))
duit) - [Vn 20,
dl
dt
which indicates that the loss value Lu (w((t) is non-increasing for t. Since Ln(w(t) is always non-negative, then (w(+)) converges to some limit Lox, which is also the optimal loss value along the gradient flow path. For the convergence rate, by the Uniform-LGI condition,
d (Cn(10()) -ooo)
((n(()))) du(t))
dt
dt /(Cn(co(()))) - (Cn( - 600 -co))
(11)
28.
Therefore
(w)( - Lxx) -0 d (CCn(u(0)) - foo
-c,
Integrating on both sides of the equation, we can get 14 E 00),
when On = 1
(n(w(0) L.o Se - (Cn( - foo);
(12)
when 1 0n < 1,
(n(10))) Loo S (1+ Mt) 11((0 (t)--11(00-))
(w)()) foo)
(13)
where M = (2 - 1) (Cn(w)()) Loo) 2 20
For the distance bound, we consider to bound the gradient flow path length
1 du(lt)
dt. Notice that
di
dln(w(())
V L. (1) dwl())
VCn (VC((w(())] dull))
dt
S -c (Cn((o(()) - ) on dww())
)ar dl
Hence Vt [0, o0),
/" -
|
ds <
(Cr(w(t)) L20) dLn (wos))
ds
j On
1
[(Culed0)) - 6xx )-00 (Cn((w()) - -Loo 1-8,7 )
1-0n
c, (.(1-0
Now we begin to prove that (t) converges. Notice that for any & > 1. 2 0, we have
(T)
dr < (Cn(w(()) - Loo 1-0n 1-0)1-0 (Cn(wl))) Loe 1-8n
dr
Cn 0n)
19

---

Published in Transactions on Machine Learning Research (10/2022)
Then for any discrete time sequence t1, ,.....,t........................ that increases to infinity, we have Vp >9>9 0,
dw(s)
(Ln(w(t))) Coo) 1-8, - -Lnn(ull))) Coo) G. - (n)
1-6n 6
ds -
ds
w(tn),... .... a Cauchy sequence in the Euclidean space with & metric. Notice that (Cntw((n))) Lxx) )m-n converges to zero, thus it is Cauchy sequence. Then for any 0, Cn (1-
Now we prove that the sequence w(tt),,
there exists M such that vp > q M,
ty dwll))
|1000)) - w <
ds
1/4 ds
(Cn(w(t))) L(x)) 1-0n - -(nn(ull))) f(x))
-600)= 1-
Cr - Pn)
E.
Therefore, wllfal is a Cauchy sequence, and then it converges. This mcans that for any increasing sequence In + oo, wolaa converges. Hence, the limits -i w(ta) must be the same for any sequence In - xc. Other- wise, take two sequences bn : Em (k = .... with different limits limg->oo w(tr)) lims->> w(tms), then there exists an increasing sequence uy that contains two subsequences of ngg my, such that these two subsequences have different limits (since lima->o ((lne) & limæ-> w((m))), which contradicts with the con- vergence of uo(fuz). This yields that for any increasing discrete sequence ln + oc, ro((a) converges to the same limit. Finally, we conclude that the continuous dynamics w(() converges to some limit w(>)), which is stationary point with L, (1o(o))) = f Then we can replace Coo L, (w)())) in all the above equations. Finally, note that the length is always an upper bound for the distance, which completes the proof.
C Discrete time analysis
In this section, we provide optimization results for the gradient descent algorithm, i.c., we consider (t++)) w 1/ (nn
t 1,
where 7j is a fixed learning rate. We assume that the loss function is 3g-smooth its whole domain W, i.e.,
Bc 1 v/13, Vw, E W. W.
- - (VLa()),
0)15 -
Note that a continuously differentiable function is 8-smooth its gradient is 8-Lipschitz. In our analysis, we only focus on the bounded region of the gradient descent path, and the gradient (L)(w) usually locally Lipschitz inside this region. Hence, this is reasonable assumption given that W is a compact set. Now we present our main theorem over the gradient descent algorithm.
Theorem C.1. For a fized initialization w()), suppose that there erist 0n E 11/2,1) and on > 0 such that the loss function (u(w) satisfies the Uniform-LGGT on (w(*) : tt= 0, 1, with Ony Cn. Let the learning rate 17 E (0, 2/3c), then with converges to a stationary point w((x) with convergence rate given by
0, = 1/2: ()) (n( Se - P ( - (c)(((()))
0, E (1/2,1) (n(w0))) (ullo)) 5 (1+ (1) 11(20n-)) (1/
(Cr(w(()) - L(wlloo)) -(((oo))(((()))))))
where M (20, - 1) (n--2gp (wn( - L. (mo(00))) 20.-1 The distance between the inatialization
()) and the parameter w at step is bounded by
(0) - w0(1)) C, (1-8,)(1 3/c22) (En(wo()) - (n(w(oo))) 1-0 - -(En((o00)) L. (ullooo)))) 1-6m7
20

---

Published in Transactions on Machine Learning Research (10/2022)
Proof. First, by the Bc-smoothness, we have
La(wltt))) S Cn(wo(0)) + (VLn(w)()), w(++)) -w(1))
3C +
w w(()) 1
2
= Ln( - ( BC
[1o((tt) - w0
2
< (x
Therefore, (w((t))) is strictly decreasing for By the above argument, we can also get
Ln (x((()) (a(w(ttt)
(14)
17 1
Since (n((9)) is non-increasing, then (n(w!) converges to some limit Lxo, which is also the optimal loss value along the gradient descent, path.
For the convergence rate, by the Uniform-LGi condition and equation 14
s- - 82
Ca(w(t+1)) (2)()))
(xo()))
2
3/ ) (Ln(wutt)) fro
28
S - cn
17
2
Notice that
n2²Bc
fm(w(()) L (x)(((+1))
2 17
(Ln (wolt)) )(x0) 228
(n(w()))
Cn (n(w((-1)) (En(w(())) - L(x)) 20n (w)
(w(())
1
Cn ()) (Cn(w) - Coo) 20 dL (w).
when 0n 1. we have
C. (w)(()
L Ln(w(()) - -Loo L, (w((+(1) Loo
Ln (vcteta)) (Ln(w)) - foxc) 28, dCn(w) = -log
which yields that
(m((((t1)) - Lox
-0- 22gk)
Ln (n(w(()) Cox
Hence,
(n(w(()) - Los Se -221 1282)) (c) - Loo)
When 1/2 < On < 1, we have
(n(w((+)) (Ln(w) 20 (w) (Ln(zo(()) - Lco) Loo) 1-28m (Ln (wr(t11) fox) 1-28.
(n((w()))
28,,
which yields that
1 (Ln (w(((11)) Lox)
1
1738
2 2,000, -1) 7
n--
29,-1 -T
(cl(t)))) - Lox)
20 -
2
21

---

Published in Transactions on Machine Learning Research (10/2022)
Hence,
(n(w(0) - Lox S (1 -t) 1111101111011 (Cx(w) - -Loo)
where M = -2 - 1) (1 (1= rige) (Cn (w(()) Coo) 2000)a0-1
For the distance bound, by the 3c-smoothness and the Uniform-Loe -GI condition, we have
(n(w(() ((w(t+2))
[ w(t))
1 782
|| | (w)(t)))
L (n(((()) - ((1l((+1))
1 n&
Cn Cn(Cn(u((t) )00)
1
(Cn(zo(t)) - foo) 0x dRn(w)
nãc Cn
f (1ol++1))
En(wo())
1 (Ln(w) - )-z0) Jn dCn(w)
Cp (1
nBe
(ofttt))
1
Cn (2)(1)))) - 6x0) 10 - -(Cn(u((tt))) - 6c0 1000
C, 01)(1
ngg
Now we look at the sequence w(()) (()) (- on
Notice that (n(w(()) converges to Loo, hence (c.( cn(1-0a]1- converges zero as goes to infinity. Therefore, the sequence Sx(1-0.11 11-1888))))) Cauchy sequence. Then for any E > 0, there is M > 0 such that
is a
(L)( - Loo) 2-
(wn(w( - Loo)
Loo) 1--0
<E, <e>t> M.
Cn(1 0n)(1 313222
On (1 0,) 113c22)
Hence Vs > >>>>>> M,
(Cn(w(()) - -Loo) 1-0, (Cn(w(()) - Loo) 1-
(w()) (t)
(((+1)
will| -
E.
en - (x)(1-18c/2) cn(1 0n)(1 - mmcc/)
Therefore, (0) (1) (t) is Cauchy sequence in the Euclidean space with &g metric. Thus, w(t) converges to some limit (x)), which is a stationary point with Ln (wloo)) = Lox. Then we can replace Lxo to (n((())) in all the above equations. Finally, we have
1 [0] w0 v (1 (1 )
[(Cn(u - (n((w(o))) 1-0n - (Cn((u(()) -c((w((o))) 1-0n
Proof of Theorem 2.3
In this section, we will prove Theorem 2.3 This proof based on the Rademacher complexity theory and the covering number of &g balls. The key idea is to use the Uniform-LGl condition to bound the gradient flow path length 5-' (t) de dt. Then since the path length is always an upper bound for the distance, the
parameter (T) lies in a norm-constrained parameter space {w: || - w - fo us to use Rademacher complexity theory to obtain the generalization results.
dultt) di
dt This allows
Now we introduce some known technical lemmas that are used to build our proof. In the first lemma, we derive an explicit estimate for the gradient flow path length over the random choice of the training sample S.
22

---

Published in Transactions on Machine Learning Research (10/2022)
Lemma D.1. Under the same conditions and notations in Theorem 2.3 let T be the time when the empirical loss Ln ()) = e eLn(w (w for some E [0, 1], then with probability al least 1 - 6/2 over S we have
dt v (Ma M8) 1- (c M&) 1-0n.
dw dt
cn ((.)
Proof. By the Uniform-LGI condition, we have
dC((w()))
v Ln (w! dwl()
dt
dt
VCn(2((t)]] duole)
dt
- Lan (a(wwo))) S -n -Ca((()))Cn(ulo))) 0n dw((t
Hence with probability least 1 5/2 over S
T
(t)
-
1
(Ln(w(t))
La (u(loo))) -80 dln(w(())
dt
dt
0
Cn
1
(Cn(w/(0) La(w(oc))) 1-0,
- -(Cn(u - La(wv(o))) 1-0.
Cn(1
- 0n)
1
(En(ur(0) La (u((oo))) 1-0n
- (EEn( L. (mo(o0))) 1-pp
cn
8n)
(Ms Cn(w (n(w((o)) 1-0z
- (eMM L.
1oMs--n(uii (w))))) 1-6n
Cn(1
- 0n)
[Ms Ma)1-B1, - Ms) 1-
Gn
0n)
The last inequality is by the fact that the function f(x) 1=))=-00 - (s =)1-0 is non-decreasing on [0,s] given that t 2 s.
The second lemma gives a generalization bound of a function class based on the Rademacher complexity, which is proved in Mohri et al. 20188)
Lemma D.2. Consider a family of functions F mapping from Z to la, bj. Let D denote the distribution according which samples are draun. Then for any 0, with probability at least 8 over the draw of an i. sample S (21....,24 2n} of size n, the following holds for all F:
log(2/8)
E [f(z)]
Σ ( 3(b - a)
2n
where RF(F) is the empirical Rademacher complerity with respect to the sample S, defined as:
1 n
Σa Easles)
Rs(F) E. sup fEF n
Here {or) are i.i.d. random variables drawn from U1.
In the next lemma, we prove a shifted version of the Ledoux- Talagrand contraction inequality (Leooux & Talagrand 2013), which is useful to bound the length-based Rademacher complexity.
Ledoux-Talagrand
23

---

Published in Transactions on Machine Learning Research (10/2022)
Lemma D.3 (Shifted contraction inequality). Let 9 R - R be conver and increasing function. Let @: IR - IR be I.- I--Tipschilz functions, then for any bounded set T C IR. and any (00) E IR, we have
(L
B
9
sup (1-1())
a Σ oi (dilt.)) - ( (4 ()9))
S B
9
L
sup
Σe
os t; - (10)
im1
(1-r )
ET iml
and
2 100
Eg
sup (e-11)))
oi (di(t)) - ds (1:0
S 2T.
sup (L-("))ET
Σ oi 14 16-44)) i=1
k=1
The special case for (00) = 0 corresponds to the original Ledoux- prove a shifted version.
Ledoux-Talagrans Talagrand contraction inequality. Here we
Proof. First notice that
a Σ oe (c((l)) (4: 0b (10) ) Eo Eo,,
n
Er 9
sup (1-110)EET
9
sup (1-200)
Σ
oi (dills) - $z (1.
ET
Let (1)= Et=== di (de(ts) $5 (1,0) then
Eg
9
sup
Σ
(oi(ti)= - 0i (1(00
(t-r(0)) ET 1=1
Un un-1 (1) + (m(ln) - on ((0))
un-1(1) (Dn(ln) On (110)
9
sup (t-r(0))
+ 2
sup (t-
Suppose that the above two suprema can be reached l' and i respectively, i.e.,
sup un (t)) + ( - on ((()) )) un-1 + (pn (t,,) - on ({(0) (T-
Un un-1(1) (1) (mn(t)) - on (1()) un-1 (1) On (in) On (100)
sup (t-(0))er
Otherwise we add arbitrary positive number in the above equations. Therefore,
Σ oe (2((1)) - Φb (1:0) 1)
n
E 9 sup (T-
1
9 Un- (t') + (0n (t'm) - 6n (1()) ))} + 2
1 9
(un-1 (f) - -Oon (Em) - on (000
2
Without loss of generality, we assume
Un (t') + (pn (th,) - 6n (10) 2 un- (i) + @p (Fm) - on
(15)
Up-1 (1) - pp (Im) - 6n (0) > Un-1 (t') - (b (1')) dn
(0)
24

---

Published in Transactions on Machine Learning Research (10/2022)
For the other cases, the method remains the same. We set
a = un-1 1 (7) On (fx)
Qn nn
(())
b = Un-1 1 (1) L In (10
d' un 1 (t') + L (t/, (10)
b' = 1 (1') + (on (1%) On (10)
Now our goal is to prove:
3(a) - 9b) S ga - (b)).
(16)
Considering the following four cases:
1. ty 2 e and &n 2 t By the Lipschitzness of on and equation 15 we know a a b, 2 and
(a- b) (a' - -b) on (t')) On (En) (t, En).
If 2 in, we can get a b S d' -V. By the fact that is convex and increasing, we have gly + x) g(z)
is increasing in y for every x 2 Hence for x = b,
g(a) (b) = g(b + x) g( s g + +) g(b) s و (a') -
If f < En, we change on into - and switch I' and i, and the proof is similar.
2. 1, S 1 and in < (1) Similarly, by changing the signs we can get the same result.
3. f, 2 (n) and in < tu)) For this case we have a < b and D' s a', so g(a) + g (8') S ((6) + (a').
4. f, < (0) and in z th For this case we can change on to -nn, then have 2 b and a' S v, and
finally we get g(a) + 9 (b') I gb)) + (a').
Thus equation 16 yields that
Σ oi (0((1:) - -0: (0)
E,,.
g
sup
(1-210)) ET i=1
un- (t') + (0n (t'm) -
- Φn (#.0) ))}]
1
Un (1) - Φn (fn) - Φn (I!")
9
+
g
2
2
1
9
Un-1 (t') (t'a -t00) )] + 1 2/2 (
Un-
(8)
L (in {(0)
2
Un-1 (t) + I (tn- - (200 )1
sup un- (t) (t - (1a=())) )
1
$
2
9
sup (e-(10))ET
+ 2
(1-100))ET
un- (t) + tnL (th-t100) +(00 )
=Eon
9
sup
(1-100)ET
Applying the same method to On-l:..., successivvll, we obtain the first incquality
oi (i((t)) - 0: (1. ) < E.
(L
)
(o - (t=-((00) (0)
E, 9
sup Σ (1-100)
L sup Σ (o-
σ.
E=1
t=1
25

---

Published in Transactions on Machine Learning Research (10/2022)
For the second inequality, since |2|| = [x]= [a:]_ with [x]4 max(0, and [x]]_ max(0, -x),
Σ (di(tt) - 0: (t:
Eg
sup (1-100) ET
i=1
" Σ oi (t,)t) - 0: (4%0)
oi (t,tt) - 0: (t(0)
S
sup
+ E
sup (1-
(1-260) eT
Li
JET
Liml
Σ σi (dilti) - Φ2 (000
22
sup (t-TT0))ET
where the last equality is by [-xs] = [x04 and a has the same distribution with -a.
A simple fact is that
Σ oi (1((t)) 0: (19) (t-) = 1=1
sup Σ os da (0(0))()))) (::)) (1-())) t=1
sup (1-
di
Since max(0, x) is convex and increasing, then by the first inequality have
Σ oe (i((t)) - 0: ( ((00) li=1
Σ os (0i(t)) - 0i (0)
Eg
sup (t-r(0))
= Er
sup
(t-r(0) EET i=1
15,
T, sup
4: 14-14 (
(1-1(0) ET 1=1
< I.B.g
sup (1-1(0))
Σ
oi
(
1=1
This completes the proof.
Now apply Lemma D.3 to bound the empirical Rademacher complexity of element-wise distance constrained function class. In the following lemma, all the notations consistent with Theorem 2.3 unless stated otherwise.
Lemma D.4. Given function class Fab = fx + f(w,z) w E Sabt and sample S = {ar,... Fn with ||||||| = for all E [n]) then we have
||al|2 + ||b1l
Rs (Fa,). S
[| (Sa.b)ll
n
Proof. By definition,
RRs(F..)) E,
sup
S. t=1
E,
sup
f., 244)
IE, Σ (0,
wES.,
i=1
E,
sup
oi (f S(0, -(0.,x)))(((0z:))
wES.,
1=1
26

---

Published in Transactions on Machine Learning Research (10/2022)
Now we decompose the term f(w, 24) f(0, 2;)
f(w, x4)
= (o) a1 al....,, x apps ,I,..., Bq) - v ..,.... 0,.,...,
([((x] an. ap. ..) v (O...... Pp..........) A.). ) (o..... ap .a) (0.00.... ap..e.......)) (a.....
+.. (V (0, 0,0, 0, Byy) v (0,.... ..... 0, 0, ................................ 0))-
Then by the above decomposition and Lemma D.3. we have
Eg
sup wESa.h
os (f(w, f(0, f(0,
1=1
<T. (1)
(Sa,)) Ba
sup Σ
o on +... 1p+0)) (Su (.
sup Σ Jg
WESo.b 1=1
w.S..h i=
Notice that
Eg
sup
T J13 01
Egg
sup
0 a1
wES
i=1
|| I|sa: i=1
a
Σ 0
(1
Egg
0
i=1
01 nn
And
Eg
sup
Σ
3r33g
= Egg
sup
wESa.b iml
S E.
i=l
< by
Eg
Σ F
Therefore, by the Cauchy-Schwarz inequality, we can get
E
sup S 1=1
Σ
as (f(w x.)) - /(0,2:))
< 1 (Sa,)) v + ... I (p+g)
T (Sab)bayn
S vn (Ia||2+110)) +1111)+ [[
Finally, we have
||a|| 2 + ||b11
(Fa S
|| (Sa.))l
n
27

---

Published in Transactions on Machine Learning Research (10/2022)
Lemma D.4 gives upper bound of the Rademacher complexity based the element-wise distance. To obtain a norm-based generalization bound, we consider to use Sa.b to cover the norm-constrained space {w: | S R), and then taking a union bound. For the lz ball covering number, we use the following result
from Neyshabur et al. 2019 Lemma 11).
Lemma D.5. Given any c, D. > O, consider the set sD E |||||| S $3. Then there crist N sets N
[Ti of the form T; {a RD |2,l S az, Vj [l]] such that S - U T; and ||a'll S B(1 + e), vi
[N] where N = =Kxt ((--T)) and
D
K
+ c)2
Lemma D.6. For any two positive integers n, with k, we have
R:
Proof. Note that
12
7
n
11
&
S
S
e
k:
k. ( - 1:)!
k!
k
The last step is by
k3
k*
e
i!
==0
Now combining Lemma D.1
D.2
D.4
D.5
and D.6
we are ready to prove Theorem 2.3
Proof of Theorem 2.3 Let ān,ō. (Ms Ma) cn (1-6.).
on (s- 6n then by Lemma D.1 we may apply Lemma
D.5 with e = 2 1, 1, D = p + q, and B &n,ō,e then there exist sets Sam.r such that Sg C U SaM and || + ||b-11 < v23, with N = (2D-1).
Therefore, for each parameter space Sat,ut ,t: by Lemma D.4 we have
Rs(F (F S V n
B L (S sx)
Notice that the local Lipschitz constant of l in Sat is Le s²). Hence, by Lemma D.2 and the Ledoux-
Talagrand contraction inequality, for any 5 E (0, 1), with probability at least - 8/2N 22 over the training sample, the following holds for all w E Sat,bA
(o(we) Set 2V23Le se) || (+)) + +3Mg
log(4N//)
Vn
2n
where My = sup |a |1 || $280 SuPweS, ll pe
L (((,w)) v).
Since wa (()) 5p C U Sanp with probability at least 1 - 8/2 over S, by taking the union bound over all sets S.* bt, we can get with probability at least 1 5 over the training samples,
2 2v23L I (Sa.v)) 3.a.
log(4N/0)
(D(ws) SEt
sup ||a|| + 1 s2
Vn
2n
Thus it remains to bound the term log N. For D = 1, N =1 1. For D D22 2, by Lemma D.6
(((2-11) - 1)
c(2D
log N $ (D 1) log
<2. 1) < 3D = 3(p + q)-
D D-1
28

---

Published in Transactions on Machine Learning Research (10/2022)
This completes the proof of Theorem 2.3
E Proofs for Section 3
In this section, our goal is to prove all the theorems Section A crucial part of the proofs the spectral analysis the random matrix X. Therefore, we start with introducing the non-asymptotic results of the smallest and largest eigenvalues of subguassian matrices.
g
The first result is from (Rudelson & Vershynin 2010, Proposition 2.4), characterizing the non-asymptotic behavior of the largest singular value of subgaussian matrices.
Lemma E.1. Let A be an N n random matriz whose entries are independent mean zero subgaussian random variables whose subgaussian moments are bounded by 1. Then for every 1 2 0, with probability al least 1 - 2e at² over the randomness of the entries,
Ammax Amaa((AAT) SCVN Vt
where с and C' are two positive constants that depend only on the subgaussian moment of the entries.
The second result is from [Rudelson & Vershynin 2009 Theorem 1.1), characterizing the non-asymptotic behavior of the smallest singular value of subgaussian matrices.
Lemma E.2. Let A be an N random matriz whose entries independent and identically distributed subgaussian random variables with zero mean and unit variance. N > n, then for every > 0, with probability at least - (C1s)N-nt1 a over the randomness of the entries,
V Amin (ATA) (TA)28(8 ( vn-
where C > O and e₁ E (0, 1) depend only on the subgaussion moment of the entries.
In the next introduce useful lemma to bound Amax (xxx ) and Amin (XX
Lemma E.3. Let X Raxd be matrix with full row rank, Eg E IRaxd be a non-singular matria, then
Amax Amax(XXX) (XXT) < Amax (X (IE xT
Amin (E(EN)
Amin X (AE Ed XT))
Amin (XX
Amax (2x2)
Proof. Since X has full row rank and Eg is non-singular, then X'Es also has full row rank. Notice that
Amax (xxx = sup
||uT NOEEEEET
s sup ||l ||||=1
XEE
2 [2
||]|==
Note that
|3 mll
|Σ vll ||0|||
| Egp
12 = sup
sup
sup 290
||0||
v
x 00
Amin (2x2iT)
Thus,
| ToTxXE
Amax Amax (XE
Amax (X 1x5
||||=
Amiu (2
Auiin (2x21))
29

---

Published in Transactions on Machine Learning Research (10/2022)
For the smallest eigenvalue, note that
Amin ( (XX
=
inf ||0|==1
|10 X'E ||
| E
|10 T XEd ||
inf
|1 X ||]|==1
x' 212
inf
inf |10 xEal
||=||=1
1100 xE
|0|==1
| 112
2 inf 0550
Amin (X2' x²)
||o||
||:/1
inf
Amin (XE xT)
e/0
Amin E T
Amax [x<4)
E.1 Proof of Theorem 333
In this section, we will prove Theorem 3.3 All the notations are consistent with Theorem 3.3 unless stated otherwise.
Proof of Theorem 3.3 For the & linear regression loss function C, (w), notice that
V.n(w) 1
( xz v.) x; _x (Xw (()-))
Then since X has full row rank, we have Veu E Bd
1 n
[[Vr(()]
x (Kw - (KW-
Amin (
| V
7
2mmin (X'X'
(/(w)
Since the optimal loss value is zero for underdetermined linear regression, have
On 2A (XXT) 0, 1/2.
n
The convergence rate be proved by directly plugging on and 0, into Theorem 2.2
Next, prove the generalization bound for ws- Notice that for the linear hypothesis function ʃ and the Lipschitz function f, we have (e(.))) = Ma.b = || (Sc,))l = v2, p 1, 0, MM = O. By the property of the target function, we have for any w())) that satisfics ( || S Co.
(o( = 2n [w - ->11
< |x || + 112112
1
2 + (c
Amax (x
30

---

Published in Transactions on Machine Learning Research (10/2022)
Since in the following, only need to bound the condition number of the data matrix X, with loss of generality, we may assume that the entries of X' have variance 1. Now apply Lemma E.1 with A = N
and t / lo0(1/0), then we have with probability at least 1 - 5/2 over the samples,
Amax (KEST & C(v lo/(4/6)
(17)
where e and C are two positive constants that depend only on the subgaussian moment of the entries.
By Lemma E33 we have with the same probability,
C(va+ Vd)
log(4/6)
(X
(18)
Vuo
Thus,
o + (c))2
d
log en
4/6)
Ms
c1+ V
C 1
A0
n
2 + (c*)2
C' c1+
log(4/6)
1
+
Au
To
Similarly, let T = E (0, 1),e T/C1 > 0, then Lemma
E.2 implies that with probability at least 1
pd-n+1 - 7d over the samples,
Amin (dE xT) 2 (Vd vn 1),
(19)
C1
where C > 0 and 5 E (0, 1) depend only on the subgaussian moment of the entries.
By Lemma E.3
we have with the same probability,
Amin (XXT)
Civh1 (Vd vn - 1).
(20)
Taking the union bound, we have with probability at least 1 - 5/2 - -d-n+1 7d over the training samples,
Tn,6,5 22n Ms VEMO
Amii (X(TT)
VMA
22 - =)
(Vd vn T)
CIVAi
cotc
C 1 (c(1+
+
log(4/5)
v
cm
(21)
S V2(1 - E)
-
ch+c
C
1 +
log(4/8)
V2o
$ /2(1 =)
-1)
c
31

---

Published in Transactions on Machine Learning Research (10/2022)
Notice that l is Vi--iipshhitz on the first argument, then by Cauchy-Schwarc inequality, have
((f(we,
[wee 2:)) 3/1l
71
n
40
f((ee - yol
(22)
21o 21 (Wa)
V 2108 L.n (mo(00)
Combining Theorem 2.3 and the inequality 21 we have with probability at least 1 7d-n+1 the training samples,
7 over
4rn.he vn
3 log(4/8)
B(ay)~D (W((,,)))))))) v)] = (l
+
+ +l0g
2n
4(co + c²)
/211-171
2(1-5)A,
C (C(11 (1+ [/0 +
log(1/5)
Ao
3 + (4/(4/))
v 2l (ml000)))00)
3lp
vn
2n
where c, C, C1 and 5 e (0, 1) depend only on the subgaussian moment of the entries. This completes the proof of Theorem 3.3.
E.2 Proof of Theorem 3.5
In Chis section, we will prove Theorem 3.5
First, we present some useful lemmas for proving our results,
and then give the proofs of Theorem 3.5 for the RBF kernel and the inner product kernel separately.
For the RBF kernel k(2, v) (lly x1), the following two lemmas give non-asymptotic bounds for Amax (k(X) X)) and Amin (k( based on the separation distance SD of X.
The first lemma is from Diederichs Iske 2019 Lemma 3.1), providing an upper bound for Amax((((X Lemma E.4. For the RBF kernel, if Q 20
R20 is a decreasing function, then
Amax (k(X)))) s e(0) + 3d Σ (t 1 SD),
e(t
(23)
and the sum of the infinite series in equation
23
finite and only if e ([x11) L (RR.).
The next lemma is from (Wendland 2004 Theorem 12.3), giving lower bound for Amin (k(X,
Lemma E.5. Suppose that is a positive- -osttive-defimite RBF kernel. If e ([[=)) E L'(R",, one can define the ww ddw. With decreasing function eo(M) and two
Fourier transform of as î(w) = dd/ Jgo e(w)e-to' constants Ma, Ca defined as
Ma 23/2
(o(M)
inf 0(x), Ma 6.38d, Ca= (T +1) ||x]] 22M
where T is the gammaa function.
Then lower bound on Amin Amin(k(A (k(X' is given by
Amin (k(X, 2)) Ca eo (Ma/SD) SD-4
32

---

Published in Transactions on Machine Learning Research (10/2022)
For the imner product kernel, it is shown in El Karoui et al. (2010) that the kernel matrix can be approximated by the linear combination of all-ones matrix 11 sample covariance matrix and identity matrix. To obtain
non-asymptotic results on the spectra of the kernel matrix, we borrow the technique from (Liang & Rakhlin 2020 Proposition A. and show the result for subgaussian entries in the next lemma.
Lemma E.6. For the inner product kernel, under Assumption 3.2. we have with probobility at least 1-8 1-8-11 d over the entries,
[Ix k (20 (2, S d (5-1/2 log 0.51 log d).
where hlln (2) is defined as
[0(0) + e'(0) d
11 + d0()) X2GNT
" (X
(e(1) e(0) e'(0)) Inxn-
Proof. Note that the sample covariance of X'E is Taxd: then by applying (Liang & Rakhlin 2020 Proposition A.2) with subgaussian random entries we can prove this lemma.
Lemma E.7. Suppose that A, B E Raxn are two symmetric matrices, then we have
Amin (A B) Amin + Amin (B).
Proof. Note that for any R" with ||a||| =1
aT(A+ + B)x T Ax x Bx 2 (A) + Amin (B).
By definition, we have
Amin (A+ (A+B). = inf x. T(A+ + B)x 2 Amin (A) + Amin (B),
||=||=1
which completes the proof.
Now we are ready to prove Theorem 3.5
Proof of Theorem
3.5 First, notice that Ve E IR"
(L)ll) [|x) (o())w-)1) 2/]|
/ Amin (1(2)))((2)
1kp(X() VI
Amia (b((x))))
C, 1/2
Since the optimal loss value is zero for kernel regression, we have
2Amin(k(XX k((x O, 10=1/ 1/2.
Since k is a positive-definite kernel, the convergence rate can be proved by directly plugging e, and On into
Theorem 2.2
The proof of the generalization bound two-sided. First, since Vr X. [|p(2)]1 /ka, x) S 1, then the kernel regression model (8) can be viewed Eg linear regression inputs (x))). Hence, v is identity
33

---

Published in Transactions on Machine Learning Research (10/2022)
function with p 1,9 = 0, and Le(Sa,)) = Ma.b (Sab))) v2 for any a, b. The optimal empirical
loss value Mg- = 0. This means that we only need to bound the terms M, and En,lec
By the property of the target function, for any w(t) that satisfies
||ol0//2 S we have
-3y12=
Lu(w
2n
1 (1((2))0 (0
1, + -12111
(24)
2 + (c')²
Amax )max((((X (k).
For Tn, notice that
Tn.b.c 2nn VMA VEMS
Vmnin (k()
Amax Amax(1(( (k) V Amin (k(X))))
2( - a) (co + x0')
Then for the RBF kernel with fixed input dimension d, Lemma E.4 and Lemma E.5 indicate that Amax (M(X,)) and Amin (6(X))) are uniformly bounded with bounds depend only on g, d, smin Imax. Hence, there exists a positive constant Cle, d, Imin: (max) that only depends on d, Jmin Imax, such that
Tn,8,c S 22 a) (co + (e) C(e, d, Imin: (max).
Therefore, by equation 22 samples,
Theorem 2.3 and Lemma
D.2 with probability at least 1 - over the training
B(z.))D [ (f(we, & v 2= (w(00) + 4rn,d.
3 + log (4/8)
+ +31
Vn
2n
4 2(1 2) (co c*) Cle, d. quin Imax) 3l0
3
(4/()
s v 2l
+
Vn
2n
which completes the proof for the RBF kernel. For the inner product kernel, first notice that
Amax (k(X' = ||((X, XI
(25)
(xx, 23)1 [[(xxxx)- - 1 (x,,
By Lemma
E.7
we can get
Amiu (H:(
2 Amin (k (x2 + )minn((2 - x kinn (X, x))
(26)
Amin(k lin (X, - ||((2, - lim 1m (x,x))]
Under Assumption 3.2 &
3.4
Lemma
E.6 implies that
(0())
e' | (e(1) d'(0))
| lin (X, 2011
d 1|11
d
ng" (0)
Ammax (XE33X')
+ d'(0)
+ (e(()) - d()))
d
d
Amax (2222
<me" + (0)
(e(1) e'())),
d
34

---

Published in Transactions on Machine Learning Research (10/2022)
and
Amin (A Him (x2, 2 e(1) d'()>
Thus, by equation 26 we have
min (b( 2 (e(1) d'()) | b. (X(,
(27)
Under Assumption 3.2
by equation
17
have with probability at least 1 5/3 over the samples,
2
Amax (X'E
V n 1) +
1og(6/8)
cd
log(6/6)
C (vn + +1)
cn
Therefore, by equation (25 with probability at least 8/3 over the samples,
(c(V++1)+ log(6/5) + +1)1) -((0) |,(,, (X', x))
Amax (B:())2)) m + e'(0)
(28)
By Lemma E.6 for large and small å such that d-1/2 (v38- 1/2 + log 0.51 d) S 0.5(e(1) - e'())), we have with probability at least 1 8/3 3 d-2 over the entries,
|(X &-lim (x x)| s 0.5(g(1) e'())).
Then equation 27 and 28
yields that with probability at least - 26/3 d= over the samples,
Amin (k(X, x)) 2 0.5(e(1) - d'(0)),
2
n log(4/0) en
Amax (k(X, x)) < (0) e'(0) (C(V++)))
+ -1(e(()- e'()).
Hence, we have with probability at least - 28/3 d=2 over the samples,
MM VEMo
Tn,5, 2n V Amin (k()')
Amax (k()(())) Amin (k(X)()))
2211 56) (co +c') (c0+
(0) e(())
(C(TT + 1) v 0.5(e(1) e'(O))
log(4/8) en
1.5(e(1) -(
$ - (co +c')
Therefore, there exists constant that depends on co, e², M1 e" (0), e0),,, e(1) and the subgaussian moment of the entries such that with probability at least 25/3 d over the samples,
Ta.ds 5C (1+
log(1/0)
1+
/1 -
35

---

Published in Transactions on Machine Learning Research (10/2022)
Combining equation 22 and Theorem 2.3 we get with probability at least 1 1 - dt= over the samples,
(ayyyDD ( x),1)) S OheLn(wlo)) + Arnis +
3 + log(4/))
+360V
vni
2n
C c(1 vlog(1/8)/n)
vI-
3 + log(4/0)
S v (lloon(w(0) +
+ 3l0
vn
2n
where depends on co. ",,",,,,"000 (0), o(1) and the subgaussian moment of the entries, which completes the proof.
E.3 Proof of Proposition 3.6
In this section, will prove Proposition 3.6
00). First, notice that the loss function L. (w) is a subanalytic function, thus it satisfies the classic LGI (Bolte et al. 2007). The classic LGI yiclds that there exist cx (S,) > 0, (S,) E [1/2, 1) such that the Uniform-LGI holds some neighbor U of the stationary point w(x)), Thus, there exists T > 0 such that (w) satisfies the Uniform-LGi on {w((t) :tE (I, [o)] with (S,), (S..) Now we consider the gradient flow curve that is outside U", i.c., t E [0, where the gradient norm has a positive infimum. Then there exist (S,),,), (S,) such that the Uniform-Lo holds for E [0. Let (S,) satisfies Uniform-LGI along the whole gradient flow curve with (S.) and (S.).
Proof. We consider two phases: E [0,
and
> O, (S,) max(0; 0,, [1/2, then (w)
For the population loss function Lp(w) = ((((e, vdd((r, y) with the probability measure du((,,) y) over the data distribution D, if it is subanalytic, then it satisfics the classic LGI (Bolte et al. 2007] around the stationary point = By the same argument, there exist ep 0,0p [1/2, 1) such that (Dww) satisfies the Uniform-LGI along (w] .1 0} with CD,0p.
E.4 Proof of Theorem 3.8
In this section, we will prove Theorem
3.8 for two-layer neural networks.
Proof of Theorem 3.8 The convergence rate can be directly obtained by Theorem 2.2
For the generalization
result, we first give an upper bound for f. (w) Notice that
1 Σ (1110) (o(()))())) x:)) vi)
Cn
2n
1=1
Σ 1=1 ((v(0)) (T(((())):)) V?
n
(c*)² Amax (X
(o(0)) (T(((=22)))
< (0) (0) 12 Σx | x2
(ct)²
A (T
n
n2
||l 22 ITI.
(c7)2
- (X(2
1110001 Ip 1211 + (c*)2
Xmaae (X22
n
Amax (T
(0) (c²)2)
n
36

---

Published in Transactions on Machine Learning Research (10/2022)
Then by equation 18
have with probability at least 56/2 over the samples,
C(1 + /d/n) +
log(4/8)
Ln (n(w0()) 1 (11100011 (00)
Vuo
C(1+1/V 70
1o/(1/6)
(2 + (0)g))
V
(11100012 + 2(c))) 12 2 log(4//8)
Therefore, we can set Ms to be
Ms = δ 8(1+ log(1/0)
where Ò is constant that depends only depends e², 7o, Ao, || and the subgaussian moment. of the entries.
Next, we bound the term /up/|all |21l n.6, || (S Note that
V ($), (s....... smi t1, mm)
stb(tt).
Hence
m
sup +||l>+||0** 2rr m.6.
[1,t()))))]
sup ||a||*+||b| - s2r
Σ 87 + 2(4)2
t=1
(29)
Σ 87 13
sup ||a|| +16|)+++1''2++++
:=1
V2
Now it remains to bound Fn,d,. Notice that with probability at least 1 - 8/2 over the training samples, we have
M On. - (eMs - Ma) 1
Tn,s,
cn, 0n,6)
Lastly, for the global Lipschitz evaluation loss function and the two-layer neural network, we have Lr(S,,b)
Ma.b = 1, = q = m. By equation (22) and Theorem 2.3 we can get with probability at least over the training samples,
(C(1 log(1/8)/n)) 1-8n, (eMs Ms) -0.0
6m log
BayyDD [e ( x), s / 21 (no(0))))))))))
+310
In
Cn,5( 0n,6)
2n
where Ò is constant that depends only on c², 7o, Ao. [0) and the subgaussian moment of the entries.
E.5 Results for overparameterized two-layer neural networks
In this section, we derive the generalization result for the overparameterized two-layer neural networks, where our generalization bound (Theorem 2.3) becomes non-vacuous. The generalization bound is based the
37

---

Published in Transactions on Machine Learning Research (10/2022)
Rademacher complexity theory in Arora et al 2019 in the NTK regime. To simplify the analysis, we only consider the case when = 0, i.e, the final convergence model.
Following the setting in Du et al. (2019), we only train the hidden layer U and leave the output layer v as random initialization to simplify the analysis.
NTK matrix. The NTK matrix (t)) is defined as: (ty(t) = (Vuf(w 2.), Vu Vwllo and denote e by the limiting matrix A o,j = x!! 2, [d'(w' x;) (w [w]T,))]] x Vi,j E [m].
Standard random initialization. To get a clean non-asymptotic bound for the initial loss value, we consider the following random initialization scheme. U10) is drawn from Gaussian N/ { and v/ are drawn i.idd from uniform distribution U[-1/vm. 1/ J. Vi E [m]] These random initialization schemes are also known as Xavier initialization (Glorot & Bengio, 2010) and Kaiming initialization
(He et al.) 2015
Theorem E.8. Consider un overparameterizee bwo-layer ReLU neural network
70
For any ô (0, 1), if
2 poly (n, A (1,\ (0) then we have the Sollowings:
With probabilily al least - over training samples and random inilialization, fa(w!!)) salisfies the Uniform-LGi on {wit) tt 2 0} with
On = V Amin (m)n( On = 1/2.
(w)()) converges to zero linearly:
Cn(w(()) exx expp(>xmii (-)tmn(@)t/n)) (w))))))
Under Assumption 3.2. for any target function that satisfies 7. 71 (0, 1), then with probability at least - nd a over the samples and random énitialization,
(
E ie (F(wllo)) .)). so
72
where 7 E 10, depends only on the subgaussian moment of the entries.
we first introduce some important lemmas for proving our final results. The first two lemmas are used get an estimate for the initial loss value under the random initialization.
To prove Theorem E.8
Lemma E.9 ( (Montgomery-Sniiig 1990 ). If {ar)i are i.i.d. drawn from 11,,11, then for any x )x E RR, with probability at least 1 - over o,
Σ 0 1=1
S / log(2/6) |
The following lemma gives a sharp bound for a Chi-square variable, which from (Laurent Massart 2000 Lemma 1).
Lemma E.10. Let (Y,...., YD) be i.d. Gaussian variables, with meon 0 and variance 1. Then with probability at least 8 over Y,
Σ Et² Dlog ( log (1) )
4 Here Amin changes with
38

---

Published in Transactions on Machine Learning Research (10/2022)
Lemma E.11 shows that the smallest eigenvalue of the NTK matrix ( has lower bounded given the overparameteriiation, by which we can prove the optimization result. In Lemma E.12 we show that the eigenvalues of the NTK matrix are related to the data covariance matrix. Then by combining Lemma E.13 and Lemma E.9 we can prove the generalization result.
Lemma E.11. For any ô E (0, if m 2 poly n2, Ami (0), then with probability at least - ô over the random inilialization,
Amin (+(1)) Amin (+),
V1 0.
Proof.
The proof is the same as the proof of Du et al. 2019 Lemma 3.4).
Lemma E.12.
Amin ( 2 Amin (xx*) /4.
Proof. Notice that for ReLU activation o, a simple fact is that ('(ar) d'(x) holds for any R given that 0. Therefore,
2g = x. F. w~ [d' xs)o xz)]]
x. x, (w [d'(w ( (;) 2,)]
Ij I arccos x xzy))
2x arcsin xz))
T. Ijj
3. Tj
2x
(2k)
(x. (zTTz)22ts 2h-
2T k=0
(*:)))2
Then
X
4 (2k + (X22T
(2k)
(x(T))((a+22) 0(22+2)
4
2TT
k=0
XXT
20
(2k)
(1TT)012422) (x (012042)2))
4
2T
(k!) + 1)
where is the clement-wise product, and @ is the Khatri-Rao product Since (0122)))))))) (0(2+)))))) is positive semidefinite, we have
Amin Amin(()) 2 Amin (XX1 /4,
which completes the proof.
The next lemma quoted from (Arora et al. 2019 Lemma 5.4), giving an upper bound for the empirical Rademacher complexity one has an accurate estimate for the distance with respect to each hidden unit
Forr (a1....,0n) RmXn, (bi,...,hu bm) e Rpxn, then A (aj bn. & bn), where & is the Kronecker product.
39

---

Published in Transactions on Machine Learning Research (10/2022)
Lemma E.13. Given R O, consider the following function class
F= { + f(w,x)) u4 -
- 1 - R(vr E [m]), | u100) | - B)
Then for an i.i.d. sample S (I1,...,II'l Fnk and every B >> 0, with probability al. least 1 5 over the random initialization, the empirical Rademacher complerity bounded as:
B 22n
(1
1/4 221g((20))
Rs(F) S
1
2R² V + (ogg(22)
m
Now we are ready to prove Theorem
E.8
if m 2 poly (n. Ao. (o), (0), 8-1). then with probability at least
Proof of Theorem E.8 By Lemma E.1 over the random initialization,
1,,,((100))
(f(w)))) - yi) Vf(w!),
12
1
Vlw ,2) (f(w("), ,2) 21
72
(s(wl), x)) 3) (V)() X)T (s(wl(), -)) - 2 2mmin (e()))
V Cn(w((t)
Amiu (
(w(())
n
holds for any t 2 O, which means that (n((()) satisfies the Uniform-LGl for any t 2 with
Cn Amin ())/n, On 1/2.
For the convergence rate, by equation 11 we can directly get Ca (wi(t) converges zero with a linear convergence rate:
(w(()) < exp (-Amin())t// (w
For the generalization bound, first bound the initial loss value under the random initialization. By the property of the target function, we have
(w() 2n
Σ TO( v.)
i=1
Σ m
1=1 ((v(0)) (T(((())x=)) + vē
n
(ct)2 Amax (xXT).
(1) (o00)TT((00 (((1(022))
n
Since the entries of (9) drawn i.i.d. from Uf-1/ 1/ Mm), then by Lemina E.9 for each [n], with probability at least 6/12n over v((0)
1 ((((()))))))))))
24n 8
|((((0))) x:))
log
mn
40

---

Published in Transactions on Machine Learning Research (10/2022)
Taking the union bound over all i 1.2..... n, we have with probability at least 8/12 over the random initialization,
(T(00))(((00))))) x(U()))))))
2 2log(2An/5)
2 log((2nn/))
11
21og(24n/8)
( X²
(30)
mn 2 2log(2An/8)
[1(00 2 ||
mn 20g((2n)/8)
|
Amax (XXT).
mn
For the Gaussian random matrix U()) NO, mmxxd)) by Lemma E.10 we have with probability at least 24 over the random initialization,
||::111 m
log(24/6)
21og(24/6) md
S 2
(31)
md
Taking the union bound of equation samples and the random initialization,
18
30 and
31
we have with probability at least 1 - 8/6 over the
2 21og(24n/0)
(c*)² [ |
Cn (n(w10)) v
Amax (XXT)
mn
1+ 1 log(24/6)
2 222g(24/6)
( + +(o))) ( (c(1 (C1++ /d/n) +
log(48/5)
)
2 log 24n/o)
/A0
md
md
2 3 1og((21/)) + (()))) (ou+11VTT)
log(48/0)
2
21og(24n/6)
1No
md
on
2 371 log(24/0) + (07))
(CL+11/70)+
log(48/0)
2 (2og(24)/8)
1
where e and C two positive constants that depend only on the subgaussian moment of the entries. Therefore, there exists constant Ô that depends only Yo, 7ı, Åo and the subgaussian moment of the entries, such that with probability at least - 5/6 over the samples and the random initialization,
()) s Ōlo((n/8).
(32)
Thus, we can set M,- Ö log(n/8)).
By Lemma E. when & = 0, Tn,6, can be bounded as
nMs
n.Vs
Fn,ō,z = 2 2/ Amin (
I VV
Amia(Xe
41

---

Published in Transactions on Machine Learning Research (10/2022)
Taking the union bound equation (20) and (32. if m 2 poly n, (o) then with probability at least 1 - -d-n+1 7d - 5/6 over the samples and random initialization
n&ss
Tn, S 4 V Amin (XXTT
nC' log(n/6)
S 4
Amin (X
(33)
4v nõ log(n/6)
C. C.VA, (vd vn (n-1)
Now we begin to bound the distance
|ul" up for each r E [m].
Notice that
(t) duy
| uso La (wnlt))
dt
1 n1
n2 Σ (fw .x)) - vs or (ut
[(ml1) 205) va
n m
[ , (x)--/1 -28l
/um
2L, (w()0)
(-Xanin (
exp
m
Hence,
u000 - 400 $ {-/ du
2n Amin (7)
26 (w))))
2n
S
Tn,5,
ds
m
mdmiu
Now we apply Lemma F. with B = Tnbbo R over the random initalization,
2n
Tn,bee we get with probability at least 1 8/12
medmmn (9)
B
2 1log(24/0) 1+
1/4
Rs(F) <
2nd R
22n
m
Then by equation (33 if m 2 poly (n, An, (G), we have with probability at least 1 - 1-74-10 - - 7dd -8/4 over the samples and random initialization,
Rs(() Rs(FssO (
(lg(n//0) 71
Finally, by Lemma D.2 we have with probability at least 1- -d-n+1 ntl 7d initialization,
8 over the samples and random
(Dog(in/0)
Eer.yND [ (f((o(00, 50
42

---

Published in Transactions on Machine Learning Research (10/2022)
for some constant (0,1) 1) that depend only the subgaussian moment of the entries. This completes the proof.
Comparison. This result is related to Arora et al. (2019). which gave an NTK-based gencralization bound for overparameterized two-layer ReLU neural networks. This result matches with theirs the sense that we discover some underlying functions that are provably learnable. Examples of learnable target. functions Arora al. (2019) include polynomials y (8"x)², non-linear activations y cos(BTx) 1, y "(3 x) with ((2) = arctan(z/2), || S 1. Our result, furthermore, expands the target function class that is provably learnable since only require é to be Tipshcitz. In addition, they set. the standard deviation of the initialization to be at most O(1/n), whereas we use different initialization with order ((1/vd) that is more often applied in practice. This result is also related to Liu et al. (2020), which proved that overparameterized deep neural networks satisfy the PL condition. Further, we extend this work by analyzing the generalization.
43


Reviews:
[{"review_id": "WkGE6PefRo", "reviewer": "Reviewer_85er", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1- The paper is written clearly and the ideas have been presented in the proper order.\n\n2- The paper's numerical results validate the Uniform-LGI assumption for several standard deep learning settings, which can be useful for other deep learning theory studies as well. \n\n3- The Uniform-LGI convergence and generalization results provide a unified theoretical framework for analyzing various machine learning problems.\n\nWeaknesses:\n\n1- The paper's analysis focuses on the gradient flow (Equation 3) instead of the standard gradient descent steps. It is a little unclear whether the analysis can be extended to standard gradient descent algorithms.\n\n2-  Theorem 3.3's presentation needs to be improved. First of all, I do not understand why the authors define $\\mathcal{L}_n(\\omega_\\epsilon) = \\epsilon \\mathcal{L}_n(\\omega^{(0)})$ and then replace $\\mathcal{L}_n(\\omega_\\epsilon)$ with $\\epsilon \\mathcal{L}_n(\\omega^{(0)})$ in the bound in Equation (5). \n\nWhy do not the authors just present Equation (5) as a bound on $\\mathcal{L}_{\\mathcal{D}}(\\omega_\\epsilon)-\\mathcal{L}_n(\\omega_\\epsilon)$ which is the standard generalization error definition for $\\omega_\\epsilon$. As I said, the theorem's presentation seems unnecessarily complicated.\n\n3- The last sentence in Theorem 3.3 is vague and needs further clarification. The sentence says \"Then for any parameter $\\omega_\\epsilon$ with $\\mathcal{L}_n(\\omega_\\epsilon) = \\epsilon \\mathcal{L}_n(\\omega^{(0)})$ for some $\\epsilon\\in[0,1]$, we have with\nprobability at least $1-\\delta$ over $S$, ...\". \n\nDoes this sentence apply to every $\\epsilon\\in[0,1]$ or only a specific $\\epsilon$ value? Also, does the bound hold uniformly with\nprobability $1-\\delta$ for all $\\omega_\\epsilon$'s or does it hold for every individual $\\omega_\\epsilon$ with\nprobability $1-\\delta$? The current presentation of this theorem is somewhat vague and the answer to these questions is unclear.\n\n4- The model assumed in Equation (4) looks inefficient for multilayer neural nets with more than one hidden layer, because it requires including all the neural net weights after layer $1$ as $\\beta$ parameters. Also, the number of $\\beta$ parameters ($q$) appears in the generalization bound which will be unsatisfactorily large for multilayer neural nets. Is there a way to replace $q$ with the norm of weight matrices for a multilayer neural net?\n\n5- It seems unintuitive to me that $\\sqrt{2\\epsilon \\mathcal{L}_n(\\omega^{(0)})}$ appears in the bounds in Theorems 4.3, 4.4, and 4.7. \n\nShould not the point of generalization analysis be to bound  $\\mathcal{L}_{\\mathcal{D}}(\\omega_\\epsilon)-\\mathcal{L}_n(\\omega_\\epsilon)$? \n\nThen, why do the authors bound $\\mathcal{L}_{\\mathcal{D}}(\\omega_\\epsilon) - \\sqrt{2\\epsilon \\mathcal{L}_n(\\omega^{(0)})}$ in Theorems 4.3, 4.4, and 4.7?", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper aims to analyze the interplay between optimization and generalization aspects of training machine learning models. To do this, the analysis is developed based on the Uniform-LGI condition lower-bounding the gradient norm with a power of the distance to the function's optimal value. First, the paper discusses the results of several numerical experiments suggesting that the Uniform-LGI condition indeed holds in standard deep learning experiments. Next, the paper presents Theorems 3.2 and 3.3 bounding the convergence rate of the gradient-flow optimization and the generalization error of the optimized weights. Finally, the paper applies the Uniform-LGI-based convergence and generalization results to standard linear and kernel regression settings as well as one-layer neural nets. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Based on the weaknesses mentioned above, I request the following changes:\n\n1- The presentation of Theorem 3.3 needs to be improved by making the final sentence clearer and explaining in more detail how Theorems 3.2 and 3.3 can be interpreted together to reveal the connections between optimization and generalization aspects of training machine learning models.\n\n2- Some explanation is needed to justify why $\\sqrt{2\\epsilon \\mathcal{L}_n(\\omega^{(0)})}$ appears in Theorems 4.3, 4.4, and 4.7's generalization bounds. \n\nIn a standard generalization analysis, one expects the error term to be $\\mathcal{L}_{\\mathcal{D}}(\\omega_\\epsilon)-\\mathcal{L}_n(\\omega_\\epsilon)$ which is not the case in the mentioned theorems. The paper should explain why the theorems look different from standard generalization bounds in that sense.", "broader_impact_concerns": "Not applicable to this paper", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "VZS6p9eG8a", "reviewer": "Reviewer_2YTV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. This paper takes a rather general approach to study the generalization of machine learning models. The results are not derived using very specific structures of the model, but for a general class of models that satisfies a certain property (the LIG). Discussions in section 4 shows that the analysis framework can be applied to different models. \n\n2. Optimization is taken into consideration during the study of generalization. This is important especially for over-parameterized models, for which the implicit regularization is crucial for the model to generalize. \n\n\nWeakness:\n\n1. The reviewer does not see the different of the formulation of the LIG with the well-known PL-condition. The way to bound the convergence rate and parameter displacement is also the same as what people did with the PL condition. In this sense, this work does not derive new theoretical tools for the analysis of machine learning models. The reviewer hopes the authors can provide a detailed explanation if the above understanding is wrong.\n\n2. The Algorithm 1 used to estimate the parameters in the LIG does not have theoretical guarantee. Hence, the numerical experiments do not prove that the test loss functions satisfy the LIG. Also, the estimated \\theta and c might not be the real \\theta and c. They might not even be close given the lack of theoretical results. If theoretical analysis is hard, the authors should at least provide some discussion on the intuition that why this algorithm may work and find the correct \\theta and c. \n\n3. Still in Algorithm 1. The reviewer does not understand why a linear regression is used to compute the \\theta. In my understanding, the \\theta here should work in the worst case, i.e. the same LIG should hold for all parameters along the GD trajectory. Hence, the most straightforward method should be directly checking the \\theta and c satisfied by each point on the GD trajectory, and then taking a maximum. The linear regression obviously does not catch the worst case, and the resulting \\theta is large enough for some points, while not large enough for the other points. Therefore, it cannot be used as the \\theta in the uniform LIG. \n\n4. The results in section 4.3 for two-layer neural networks are not convincing. The proposition 4.5 is only an existence result. This is why its proof is quite simple and does not use any special structure of the neural networks. But the problem is we do not have any control on the c_n and \\theta_n. They may depend on n, giving vacuous bounds. For the generalization bound here to make sense, the authors need to give an estimate of these values and study their dependency with n. ", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the uniform Łojasiewicz Gradient Inequality (LIG) on the loss function of several machine learning models, as well as the implication of the LIG property. In the first part, the LIG is defined in global and local sense. An algorithm is proposed to check the LIG property on the trajectory of gradient descent, using points on the trajectory. The algorithm depends on a linear regression to obtain the \\theta parameter in the LIG. The algorithm is applied on several synthetic and realistic problems, showing its ability to get an estimate of the \\theta and c in the LIG. In the second part, based on the assumption that the uniform LIG holds,  the convergence and generalization performance of machine learning models are studied. The convergence results are derived from the LIG, similar to that from the PL-condition. Together with the convergence, the displacement of the parameters from the initialization is also bounded, which helps derive a generalization bounds by controlling the complexity of the Hypothesis space in a ball in the parameter space. The generalization bounds are studied in more detail for several specific models, including linear models and two-layer neural networks. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Most problems are listed in the \"weakness\" part above. The reviewer hope the authors could address the questions there. Some other questions are listed in the following:\n\n1. In page 7, below Theorem 3.3, the authors mentioned \"there are 6 key terms in (5)\", but later discussion only mentioned 4. \n\n2. What is the \\tilde{M}_\\delta in Theorem 3.3 and later theorems? It seems its a bound for the empirical risk when the time tends to infinity. However, for gradient flow the empirical risk is always decreasing. Why we need this \\tilde{M}_\\delta?\n\n3. In Theorem 3.3, the first term on the right hand side is \\epsilon*L. However, in Theorem 4.2, 4.4, and 4.7, they are all square root of \\epsilon*L. What is the reason of this mismatch in the theory.\n\n4. In the introduction, the authors say \"Therefore, the connection between optimization and generalization still remains largely misunderstood in general scenarios\". The reviewer does not see any misunderstanding in the connection between optimization and generalization. There is just not enough understanding. ", "broader_impact_concerns": "The reviewer does not have broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "eST3qSYHQK", "reviewer": "Reviewer_47yc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* This paper is clearly written and the theoretical results are well presented and evaluated by experiments.\n* The developed finite sample test for Uniform-LGI can be applied to measure other useful metrics.\n* This paper develops rigorous optimization and generalization guarantees for the problems under the uniform-LGI framework, which is new and seems to complete the prior works on some particular problems (e.g., linear regression with square loss, NTK with square loss).\n\nWeakness:\n\n* One weakness is that this paper cannot handle the case of $\\theta=1$, which corresponds to the classification problem with cross-entropy loss or hinge loss. Under this setting, the developed generalization bound will explode as there is a term $1-\\theta_n$ in the denominator.\n\n* Besides, In theorem 3.3 (and the discussion afterward), the parameter $\\\\|L_{\\psi}(S_{a,b})\\\\|$ can be super large when the model is complicated. The authors only discuss the case of the linear model to mention that $\\\\|L_{\\psi}(S_{a,b})\\\\|$ is a constant, it would be necessary to consider a more complicated model (i.e., deep linear model).\n\n* The authors only consider gradient flow, which is indeed a simpler version of the standard gradient descent algorithm. A detailed discussion on the extension to gradient descent should be added.\n\n* After Theorem 4.2, the authors mention that this paper also uncovers some scenarios for benign overfitting in linear regression. However, I cannot see this from Theorem 4.2 since the authors do not give any discussion about when benign overfitting (small training error and small test error for over-parameterized linear model) will occur.\n\n* Note that the constant $c_{n,\\delta}$ and $\\theta_{n,\\delta}$ depend on the sample size $n$, then the developed generalization error bound can still explode if these two parameters have some bad dependency on $n$. The authors may need to discuss this point and perform experiments to reveal the relationship between the parameters and sample size. \n\n* Lastly, in practice, the regularization will be involved during the training, can the developed framework cover the training on the regularized empirical risk?\n\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a general framework to study the optimization and generalization of machine learning problems that satisfy the so-called Uniform-LGI. Accordingly, the authors develop the optimization and generalization guarantees for linear regression, kernel regression, and two-layer neural network models. Numerical simulations support the theoretical presumptions (i.e., Uniform-LGI).", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "See the weaknesses section.", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the optimization and generalization of machine learning problems which satisfy the Uniform-LGI condition. As the theoreical application, the authors derived interesting bounds for linear regression, kernel regression, and two-layer neural network models. The concerns raised by the reviewers are well addressed in the response. Two reviewers recommended "accept". One reviewer recommended borderline rejection since he still has concerns about the novelty of the paper.  Based on the overall recommendations of all the reviewers, I therefore recommend its acceptance. 
Decision: Accept (poster)