Short optimization paths lead to good generalization
Authors: Fusheng Liu
Haizhao Yang
Qianxiao Li
Venue: ICLR 2022 Submitted (2022)
Keywords: optimization
generalization
machine learning theory

Abstract: Optimization and generalization are two essential aspects of machine learning. In this paper, we propose a framework to connect optimization with generalization by analyzing the generalization error based on the length of optimization trajectory under the gradient flow algorithm after convergence. Through our approach, we show that, with a proper initialization, gradient flow converges following a short path with an explicit length estimate. Such an estimate induces a length-based generalization bound, showing that short optimization paths after convergence indicate good generalization. Our framework can be applied to broad settings. For example, we use it to obtain generalization estimates on three distinct machine learning models: underdetermined $\ell_p$ linear regression, kernel regression, and overparameterized two-layer ReLU neural networks.

Under review as a conference paper at ICLR 2022
SHORT OPTIMIZATION PATHS LEAD TO GOOD GENER- ALIZATION
Anonymous authors Paper under double-bling review
ABSTRACT
Optimization and generalization are two essential aspects of machine learning. In this paper, we propose framework to connect optimization with generalization by analyzing the generalization error based on the length of optimization trajectory under the gradient flow algorithm after convergence. Through our approach, we show that, with proper initialization, gradient flow converges following a short path with an explicit length estimate. Such an estimate induces length-basee generalization bound, showing that short optimization paths after convergence indicate good generalization. Our framework can be applied to broad settings. For example, we use it to obtain generalization estimates on three distinct machine learning models: underdetermined l linear regression, kernel regression, and overparameterized two-layer ReLU neural networks.
INTRODUCTION
From the perspective of statistical learning theory, the goal of machine learning is to find a predictive function that give accurate predictions risk minimization (ERM) is a common practice to achieve this goal. The idea of ERM is to minimize cost function observed data by an optimization algorithm. Therefore, fundamental question is whether an optimization algorithm produces a solution with good generalization.
data. For supervised learning problems, empirical
Recent works have shed light providing theoretical explanations this question from different angles. One line of works considered the case when gradient methods converge to minimal norm solutions (Bartlett al. 2020 Tsigler & Bartleti 2020 [Ling & Rakhlin 2020 Liang al. 2020) on kernel regression, and then analyzed the generalization of those minimal norm solutions. However, the phenomenon of norm minimization has been known to happen only for the quadratic loss with an appropriate initialization. Another line of works focused on overparameterized models, e.g., neural networks under the Neural Tangent Kernel (NTK) regime (Allen -Zhu et al.) 2019 Arora et al., 2019, Cao & Gu 2020 Ji & Telgarsky 2020) Chen et al. 2021), proving that overparameterized neural networks trained by (stochastic) gradient descent ((S GS)GD) have good generalization performance on certain target functions (for example, polynomial functions).
Although existing works have made significant progress on the interplay of optimization and gen- cralization, they focused on studying specific models, such the NTK and models possessing minimal norm solutions. In this paper, instead, we study general loss function conditions that induce interesting connections between optimization and generalization.
We start with a simple observation, as shown in Figure D that under a generic random initialization, the generalization performance for both linear regression model and random feature regression model is closely related to the length of the optimization patt]] after convergence. In particular, short optimization path are associated with good generalization. Here, by length we mean the trajectory or path length of the parameter evolution during training. This is not the "length of time" used for training, as is usually analyzed carly-stopping type of algorithms. Thus, the generalization error concerns the weights of model trained to completion by empirical risk minimization. This empirical investigation motivates us to use the trajectory length to connect optimization and generalization. Intuitively, the length of the optimization path can be viewed as kind of capacity control, and
For discrete iterations, use the sum of the distance hetween every two consecutive iterations to represent the length of the optimization path (See details Appendix A.

---

Under review as a conference paper at ICLR 2022
linear regression model
random feature regression model
training enor
10t
training error
test error
tast error
10a
error
eroo
10-1
10
10-1
10-
10
20
2
24
26
2
len(w oz)
len(w(0) =)
Figure I: Illustrations of the relationship between optimization path lengths and generalization. (Left) Linear regression model. (Right) Random feature regression model with the feature extracted by neural network. We train both models by gradient descent under Gaussian initialization. N M(,, o²) with varied μ and and record the trajectory lengths len(w("), oc) from initialization until convergence. We observe that short optimization paths lead to good generalization. See experiment settings and more numerical results in Appendix A. & A.2
short path signifies low "complexity". In other words, a general condition that guarantees a short optimization path can be used induce good generalization performance. Thus, inspired by the theory in (Bolte et al. (2007) that Lojasiewicz gradient inequality (LGI) induces an explicit bound for the gradient flow path, we consider Uniform-LGi (Definition D]. This a modified version of LGI and plays critical role in obtaining length estimate for the gradient flow trajectory. Once the length estimated, we can use our length-based generalization bounds to show the generalization performance.
Contributions. summarize our contributions as follows:
We focus on the gradient flow algorithm and propose a framework for combining optimization and generalization. This framework is based on the length of the gradient flow trajectory, and its key component the Uniform-LGG property.
We then prove that under appropriate conditions, gradient flow returns a global minimum and gives explicit length-estimate for the gradient flow trajectory (Theorem IT. If this length-estimate has an uniform bound for certain initialization method, then we can give length-basse based generalization bound (Theorem 2.
We further show applications of Theorem T and Theorem 2 to obtain generalization bounds underdetermined E, linear regression (Theorem 3, kernel regression (Theorem 4 and overparame- terized two-layer ReLU neural networks (Theorem (5). These bounds match expand the type of scenarios where we can rigorously establish the phenomenon of benign overfitting.
RELATED WORKS
Optimization. Theoretically analyzing the training process of most machine learning models is challenging problem the loss landscapes are highly non-convex. One approach studying (PL) condition (Polyak] 1963).
non-convex optimization problems is to use the Folyak-Eoojsiewvin which characterizes the local geometry of loss landscapes and ensures the existence of global minima. It is shown in (Kaimmi et al. 2016) that GD admits linear convergence for class of optimization objective functions under the PI. condition. inequality (Lojasiewicz) 1965). extended version of the PL condition that can be applied to more cases. In particular, we modify the original LGI to get length estimates the optimization paths, which will be used derive length-based generalization bounds.
this paper, we consider the łojasiewicz gradient
Generalization. Traditional VC dimension based generalization bounds depend on the number of parameters and will be vacuous for huge models such overparameterized neural networks. To overcome this limitation, several non- non-vacuous generalization bounds are proposed. For example, the norm/margin-basse generalization bounds (Neyshabur et al. 2015 Bartlett al. 2017 Golooich
2

---

Under review as a conference paper at ICLR 2022
et al. 2018; Neyshabur et al. 2019), and the PAC- PAC-Bayes- based bounds (Diuugaiee & Roy 2017 Neyshabur et al. 2018 Zhou et al. 2019 Rivasplata et al. 2020). However, these bounds tend to tocus less optimization, e.g., norm- norm-based generalization bounds may not discuss how small-norn solutions are obtained through practical training. In this paper, we connect the optimization and generalization by deriving generalization bounds based on the optimization trajectory length.
Interface between optimization and generalization. Implicit bias builds the bridge between optimization and generalization, which has been widely studied explain the generalization ability of machine learning models. Recent works (Soudry et al. 2018a by 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 separating hyperplanes and therefore generalizes well. Other works (Arora et al.) 2019 Zou & Gu 2019] Cao & Gu, 2020, Ji & Telgarsky 2020) Chen al.) (02TT) concentrated on overparameterized neural networks, showing that GD/SGD trajectories fall within the NTK regime, where the minimizer has good generalization due to the small "complexity" of the parameter space. In
this work, we focus specific conditions loss functions under which we can connect optimization and generalization based on the lengths of optimization paths.
MAIN RESULTS
In this section, we aim address optimization and generalization together by proving results based on the Uniform-LGi property. We begin with describing notations and the problem setting in Section 3.1 Then we give an explicit length estimate for the gradient flow trajectory Section 3.2 Lastly, we show a length-based generalization bound in Section 3.3
3.1 SETUP AND NOTATIONS
Consider a supervised learning problem on a hypothesis space F [[ IR -R w E W). where W is parameter set in Buclidean space. Given a loss function é R x R - IR, and a training set S = (z,, y)]]"= S IR x with n independent and identically distributed (i.i.d)) samples from joint distribution D, the goal of ERM is to optimize the empirical loss function L, (w) on S:
arg min C, (w)
(f(wwxx))))
We assume that each input vector and label have bounded norms. Specifically, we assume that, for any (x, y) following D, ||æ||| = 1, |y| < 1. This can be achieved by data normalization. To simplify the analysis, we optimize the empirical loss by gradient flow!)
(t) di -VL E [0, +00),
(I)
where w(()) is the parameter value at time i, (") is the initialization parameter set, and V.,, (w) is the gradient of L. (w) with respect to w. Given the gradient flow, we may define the length of the
gradient flow curve from (())) to (t) as (en(w("), .t) : 16 dw( ds.
Notations. We use || to denote the le norm of a vector or the spectral norm of matrix, and use Ir to denote the Fronenius norm of a matrix. For a set S E R", we use as to denote its boundary. We use d(S,, S2) to represent the Euclidean distance between
sets S1, S2. which is defined as
(() = {inf [|8] - s2 81 E S1, 82 E S2) } For two vectors, we use (.) to denote their inner product. Let Amin (A) and Amax(AA (A) be the smallest and largest eigenvalues of a symmetric matrix A. For any positive integer n, we denote [n] = {1, 2, n. We use ((-) to stand for Big-O notation.
The classical LGI gives a lower bound of the gradient of differentiable function based on its value above its minimum. Many functions, e.g., real analytic functions and subanalytic functions, satisfy this property, at least locally (Bolte al., (207]) Here, we require global version of this inequality as condition to control the gradient flow trajectory. Let us define this notion below.
Definition (Uniform-LGI). A function L(w) satisfies Uniform-LGe LGI on a set with two constants
> 0 and 0 E [1 1), if [[]))l 2 e(C(w) win L(v))" Yu E S.
Heee we assume the existence of the gradient flow and the limit lim (!)
3

---

Under review as a conference paper at ICLR 2022
In the special case when 8 1/2 and 2p,, the Uniform-La LGG corresponds to the μ-PL condition (Karimi et al. 2016p. Here we give examples of functions satisfying the Uniform-LGi but not the PL condition: L 2 k 2 When k 2 2, [(w) satisfies the Uniform-LGi on IR with 2/
and = 1 1/2k.
3.2 GRADIENT FLOW TRAJECTORY LENGTH ESTIMATE
Our first result shows that under the uniform- LGI condition, gradient flow returns global minimum with an explicit estimate of the gradient flow trajectory length as in the following theorem.
Theorem 1. For any initialization w(),, if Ln (w) satisfies Uniform-Loe LGI on closed set Sn with constants Ca. On such that S. 2 B (w:(0,, (w((0))) where
I' (n) (Ln(wo()) ming (w))
(u))) 1-0k
(2)
Cr 0x))
then w(t) converges to global minimum w w(o) with the trajectory length upper bounded by len( (0)) (0) I r. ra(w(")). The convergence rate of C., (w)()) is given by:
on 2
Ca(w()) - min (n(w) Se - (Cn( - minn min Cn(ww)
1
On <1: (n(w()) - min Ln (w) S (1 Mnt) 1/(2 Mnnt)-11(2h-1 (Ln(w(()) minn Cn (w))
2
where M,,- = (20,, 1) (Cn(w(()) min Cu (w)) 20,-1
The proof of Theorem is given in Appendix B
This theorem yields that once the loss function satisfies the Uniform-LGI around the initialization, gradient flow returns global minimum with an explicit trajectory length estimate. Moreover, for any fixed n, (en(w(() oo) decreases as the initial loss value decreases. The calculation of C,, 0, for different should be analyzed case by case based on the loss landscape, shown in Section 4
3.3 How DOES THE OPTIMIZATION PATH LENGTH AFFECT GENERALIZATION?
The Uniform-LGi property allows us to have upper bound for the gradient flow trajectory length.
In this subsection, we use the length estimate we get in Theorem T to study generalization.
Throughout this subsection, we assume that there exists an almost everywhere differentiable function IgPt + R. such that f(w,, -) can be represented in the following form,
Vz Rd f(w,x) x)) V (a x, ............................. a B 3.))
(3)
with a1....,, Opp Rdd B By R. and vec (fa1, Cpp 31 .1,..., ,,,)).,,g)), E Rpd.+g Here vec is the vectorization operator that concatenates all elements into a column vector.
wide class of functions be represented in the form (3). Examples include linear functions [ww .) = w x and two-layer neural networks [(w x) = a To (Wx) with a E Rmm W E Rmxd
For the loss function f, maximal gradient norm) on S with respect to its first argument. For V in 3 we define L (S) ==
Additional notations.
(S) to denote its Lipschitz constant (the
(L) ... (P) (S), ( (S). ... L. ((0+t) (5)) where L (5) is the Lipschitz constant of on S with respect to the i-th variable. Let (0) == vec (fa1))...... :...., .a...p
T
(0) g(()) ,..., 34 and
use (w(w) to denote the expected loss EawwD [e( (w, v)]. For a = (a), ap) and
b = (b....., TT) we define Sa,5 = {w: Vi E [p].j E [q]. ||ssll & a, |3, s b,), and Ma. = (f(w, z).9).
su
In the following theorem, we give a path-based generalization bound if one has length estimate for optimization trajectory length len (0) oc). Based the Uniform-LGi property. Theorem serves as a sufficient condition to ensure that the trajectory length can be estimated. that sense, we connect optimization with generalization. The rigorous statement follows:
]
4

---

Under review as a conference paper at ICLR 2022
Theorem 2.
Consider an initialization method that w0 is independent of the training samples and suppose that for any E (0, 1). there exist Ms. R,,5 >> such that ||=[o]]|| S Ms. len(w oo) I Rn, with probability at least 1 - 5 over the initialization and the training samples. Then, have with probability at least 1 - over initialization and the training samples, the generalization error of the global minimum (x)) is bounded as:
2RL [| (S.,b))
3(p + q) + log (og((/6))
(D(w(m)) I <min Cn (2)++
sup
+3Mo,
Vn
2n
(4)
where R = 22(M2 + R
The proof of Theorem 2 is given in Appendix C casier to understand, we discuss them in sequence:
There are five key terms in (4. To make the bound
Mg: This is high probability upper bound for the Eg norm of the initialized vector [ ||- practice, for commonly used initialization methods in deep learning, such as Xavier initialization
In
Glorot & Bengio 2010) and Kaiming initialization (He et al. 2015), the norm || (0((0) is uniformly bounded with high probability.
Rn.s: This is an high probability upper bound for the optimization path length over the initialization and training samples. Theorem assummss that such bound exists, and show that immediately implies generalization estimate based on this bound. Theorem [ gives sufficient condition to obtain such a path estimate, in which case depends on the Uniform-L-Gl constants Cn. 0n and data distribution D. The asymptotic analysis of Rn,5 is moblem-depeeddet, and we provide several examples in Section
assumes
L,(,,,)) and Ma.s: They depend on the loss function L. For example, for any loss function R - [o, 1] that is I-Lipschitz in the first argument, (2( = Ma,6 = 1.
|| (Sa.t) This term relies on the structure f. For example, when f linear, vi (x () = x x then [L = 22.
Remark 1. Theorem 2 shows that if the optimization trajectory length is small, then this implies good generalization bound. First, note that our generalization bound concerns the weights of the final model. Nevertheless, by the convergence analysis in Theorem] [ our framework can be extended to derive generalization estimates that evolves according the length of time of training. See Appendix
C.1 for additional results. Second, emphasize again that the generalization bound in Theorem only relies on a path length estimate, and theorem 1 gives a sufficient condition to ensure that long as
obtain path length estimates (say from stochastic analysis of SGD), one can still apply Theorem 2 to obtain generalization estimates. Path length estimates for other types of training algorithms is interesting future direction.
such an estimate exists. Consequently,
4 APPLICATIONS
In this section, we apply the framework to three models. To obtain clean expressions of the gener- alization bound in terms of the sample size n, it is helpful to consider range of relating the dimension d. In particular, we consider underdetermined systems where the ratio n//d remains finite unless stated otherwise:
3 20.2 71 E (0, co), s.t. Vd, 7od = n(d) S nid.
Note that this setting is non-asymptotic since we do not require d to be infinite. For each application, to simplify the analysis, we evaluate the test error on a loss function ē: R x R + [o, 1] is 1-Lipschitz (on the first argument) with Ely, 3) = 0. The following steps are taken in our framework:
Step Establish the Uniform-LGI property and find the Uniform-LGI constants c, and O..
Step 2.
Apply Theorem to get optimization results to estimate path length.
Step 3. Apply Theorem get generalization results from the path length estimates.
5

---

Under review as a conference paper at ICLR 2022
4.1 UNDERDETERMINED Ep LINEAR REGRESSION
We begin with an underdetermined linear regression model f(w,x) w with an Ep loss function (p 2 2 an even positive integer):
arg min L (w)) wEkd
pm Σ (w xi yi)²
(5)
where the input data matrix - (Ii, nn) E Rnxd has full row rank. 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 : R + R with y ((x),, Vi E [n]]. Let y = (y1, ,Bh) and assume that there exits c* > 0 such that
|| S c² V'
(6)
The inequality 6 actually indicates that is Lipschitz with dimension independent Lipschitz constant. Functions satisfying 6 include linear/non-linear functions. For example, g(x) <(x w=), where w" E IRd with ||w* ll2 S e* for some constant c*, and @(-) is Lipschitz with <(0) 0.
Assumption 1. The entries of X are i.i.d. subgaussian random variables with zero mean, unit variance, and subgaussian moments nomentSbounneed by 1.
This assumption allows to study the spectral properties of the sample matrix by random matrix theory. Especially, when n n(d) (d) converges to some constant 7 E (0, 1), the Marchenko- Pastur law (Marčenko & Pastur 1967 shows that Amin Aanin(XX (XX //n converges to (1 /y)² almost surely. The
hon-asympiotic results are provided in (Rudelson & Vershynin 2010).
Performing our three-step analysis, get the following results:
Theorem 3. Consider the undertermined Ep linear regression model Suppose that there exists universal constant co 2 1 such that Vd, || I co-
Step 1. Ln (w) satisfies the Uniform-LGI globally on Rd with
Amin (X(X')
Cn = pp1-1/p
=1
Step 2. Cn (wl converges to zero linearly for = 2 and sublinearly for 2 4, iee.
p 2, (1) S exp (-2Amin )t/n)) C. Cw (w)
p p24, 4, (0) < (1 Mt) = (n)
where M -3- 2) Amin Ln (w)
Step 3. Under Assumption for any target function that satisfies 0o. we have with probability at least 1 - 8 nd -dn 7d over the samples,
(V log(1/0)
(1og(1/0)
B( (stwloo), x),8)) (((w)o))xx,,)) So s0(n00000000000 (n-1//) + +0
71
where 7 E (0, 1) depends only on the subgaussian moment of the entries.
The proof of Theorem given in Appendix D.I. This theorem shows that compared the PI. condition that corresponds to 2, the uniform-I.Gi is more general and can be applied to more cases.
Comparison. This result is related to (Bartlett et al. 2020) that studied the phenomenon of benign overfitting in high-dimensional & linear regression. Our result coincides with theirs as both results uncover some scenarios for benign overfitting in linear regression. In particular, (Bartlett al.
"The subgaussian moment of X is defined inf {M 2 0 0 MPB,2, Vt R

---

Under review as a conference paper at ICLR 2022
2020) focused on the minimum &g norm estimator. They showed that, if the eigenvalue sequence of the covariance operator Σ := E E(rx" "J have suitable decay rates, then the generalization error will decrease to zero as increases. In contrast, Specifically, we do not assume the minimum norm property and consider the optimization process that neglected in (Bartlett et al. (020). Also, we evaluate the generalization error of the convergence point on a globally Lipschitz loss function. In our settings, entries of each input I are i.i.d. random variables, meaning that > dxx without decaying eigenvalues. The requirement of i.idd. entries for each input is a limitation due to the lack of non-asy -an-smtptotic results of the spectral properties for random matrices with non-i.i.d. entries. However, this limitation can be overcome if one considers the asymptotic results. Moreover, our result works for Ep loss functions with any even positive integer p. This expands the understanding of benign overfitting in the high-dimensional setting.
result differs from theirs in the problem settings.
4.2 KERNEL REGRESSION
Consider positive definite kernel ls : X x X' - R with its corresponding feature map yp R FF satisfying (f(()) ((y)) k(x, y). We assume that [k(2, x)1 I 1, Va E X. Let H. be the reproducing kernel Hilbert space (RKHS) with respect to k. If RR, then the kernel regression model with l loss is to solve the following problem
1 2n
arg Ln (w) ==
[w p(z)) -()))-=)"
wER
where p 2 2 an even integer. Similar to the Ep linear regression case, we consider the following target function class:
Target function. Suppose the training data is generated from an underlying function g Rd + R with yi- g(x:), Vi E [n]]. We further assume that there exits a constant c* >> 0 Ouchh that
| S c" Amaax (k(X, X)),
where k(X,, X²) is the n x kernel matrix on X' with ((, = k( 24)).
Here, we list an example of class of functions that satisfies 8 g(z) ((((()) Tw²) where w" e R with (Vs) || ||2 S c² for some constant c*, and o(-) is Lipschitz with @ = 0.
To get the generalization results of kernel regression, we will discuss two types of kernels separately: radial basis function (RBF) kernel and inner product kernel.
RBF kernel. We study the RBF kernel of the form k(æ, y) = e (Cly - x=I) for certain RBF p. For the input data, we define the separation distance of X' as SD := / min;y; ||=; vi, E [n].
Inner product kernel. For the inner product kerne,, consider k(z,
e
Following El Karoui et al. 2010), we make the following assumption on the function Ø:
Assumption 2. @ is C in a neighborhood of 0 with e(0) O. e(1) d(()) 2 0. (0) 0.
Now we are ready to apply our three-step analysis to get optimization and generalization results. For the RBF kernel, the generalization result depends on the separation distance of the samples. For the inner product kernel, we study the digh-dimensional random kernel matrix.
Theorem Consider the kernel regression model 7 Suppose that there exists a universal constant
co 2 such that Vs, || 1|2 co.
Step 1. L (w) satisfies the Uniform-I.Gl globally on R with
On = =p=pp/1/p Amin (K(X X))
On 11
n
where c, is controlled by the kernel and input samples.
Step 2. Cn (wl converges to zero linearly for p- = 2 and sublinearly for p 2 4. i.e.
p p= 2, ()) S expp (-2Amin (k(2, x)))/n)))))))))))))))))))))))) L. (w)) p 2 4, (n(w()) < (1 Mt) - L. (w
7

---

Under review as a conference paper at ICLR 2022
1ppppppp 2) Amtna (2)) Step 3. For any target function that satisfies (8) we have:
where M -
Ln (w(w0)))
"
For the RBF kerne suppose that @ I2z0 - Rzo a decreasing function and ((|=)) E I, (TR.). If there exists two positive constants Quin and Qmax such that SD E (quin Imax for all then with probability at least å over the samples.
B(E,))D [ (1) 0 (0 +0
log 1og(1/5)
For the inner product kernel, under Assumption 7 and Assumption 2 is large enough and 6 0 is small enough such that d d-1/2 (v35-1/2 + log" 0.51 d) I 0.5(e(1) - o 20()), then with probability
at least 1 - 8 - d over the samples, we huve
B(r.g)/D [ (f(w(s)), so =0 (1 -0
log (1/5)
The proof of Theorem is given in Appendix D.2
Example RBF kernels satisfying the conditions and assumptions in Theorem include (1)
Gaussian: e(r) = p p > 0; (2) (inverse) Multiquadrics: e(r) = (p + r2 p 0, B RA2N, < <dd.
iincude (1) Polynomial Inner product kernels satisfying the conditions and assumptions in Theorem 4
kernel: e(T) r3, 3 Et 3 2; (2) NTK corresponding to Two-layer ReLU neural networks on gd-1 (vd): e(r) r(n (r)c
2
Comparison. The who derived generalization bounds for the minimum RKHS norm estimator. They showed that when the data covariance matrix and the kernel matrix enjoy certain decay of the eigenvalues, the generalization bound vanishes as n goes to infinity. For example, for exponential kernel and the covariance matrix Σ == E Eixx' ] with the j-th eigenvalue (y( j the & generalization bound becomes O(n za-1) when a E (0,1) 1) and n > In comparison, we get an optimal generalization bound O (111) for identity covariance matrix on globally Lipschitz loss function. Again, we emphasize that the i.idd assumption can be relaxed if more
result of the inner product kernel is related to (Liang & Rakhlin 2020
results of random matrix theory available. Further, we extend 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- digh-iinnnsional setting; thus it not a direct adaptation of (Liang & Rakhlin 2020), and the proof itself is independent interest.
4.3 OVERPARAMETERIZEA TWO-LAYER NEURAL NETWORKS
The first two applications are on traditional machine learning models. Indeed, our framework can be applied not only to linear/kernel regression but also to neural network models. In this subsection, we use our framework to study shallow neural networks in an overparameterization regime.
First, define two-layer ReLU neural network under the NTK parameterization (Lee et al. 2019
f(w, x) / mm
wa @W1xx)
where ø(x) = max(0, x E Rd is the input, W1 E Rdd Wy E R are parameters, w = vec ([W1, w2)) E (d+(11)) and m is the width (number of hidden units).
We consider minimizing the quadratic loss by gradient flow:
arg min Ln (w) = 2n Σ (fww, xx)) - y1)
(9)
'Here d is fixed and is varied.
8

---

Under review as a conference paper at ICLR 2022
Random initialization. W1 is drawn from Gaussian (0, m and w221 are drawn i.idd. from uniform distribution U V1-1,,1) 13, Vi [m].
Following the setting in (Du et al. 2019), we only train the hidden layer W and leave the output layer w2 random initialization simplify analyses.
NTK matrix. The NTK matrix @(t) is defined as: Oty(t) (Vw, x.). and denote by the limiting matrix 5 G. - =x] E.. [d'(w x:) (wo =;)] Vi,j E [n].
x1)) Vw, f(w(") ,xy)).
Similarly, we apply our three-step analysis to derive the following results.
Theorem Consider the two-layer ReLU neural network model
( For any 8 (0,1), if
poly (n, A (0),5-1. then
Step I. With probability at least over training samples and random initialization, C., (u((() satisfies the Uniform-LGi on {witt) 2 0} with
Cn Amin (m)/n, O2 1/2.
Step 2. Lu (w(lt)) converges to zero with a linear convergence rate:
(n(w(t) exp exp((x (-Amin(6))/n)) C. (w)
Step 3. Under Assumption 7 for any target function that satisfies T. if E (0, 1), then with
probability at least - 8 7thh on11 Ta over the samples and random initialization,
B( ( (1(w()0)x))))) so (V
/log(n/0)
where (0, 1) depends only on the subgaussian moment of the entries.
The proof of Theorem 5 is deferred to Appendix D.3
Comparison. Our result is related to (Arora et al. 2019), which gave NTK-based generalization bound for overparameterized two-layer ReI.U neural networks. This result matches with theirs the sense that discover some underlying functions that are provably learnable. Examples of learnable target functions in (Arora et al. 2019) include polynomials = (3" r)², non-linear activations arctan(2 (2/2), || < 1. Our result, furthermore, expands the target function class that is provably learnable since we only require Ø to be Lipshcitz. In addition, they set the standard deviation of the initialization to be at most ((1/n), whereas we use a different initialization with order O(1/ (d) that is more often applied in practice. Our result is also related (Liu et al.) 2020), which proved that overparameterized deep neural networks satisfy the PI. condition. Further, we extend this work by analyzing the generalization based on the length of optimization trajectories.
co z) - 1, = o(3 x)) with é(2)
CONCLUSION
In this work, address when and why does optimization algorithm finds minimum with good generalization performance. For this problem, we propose framework to bridge optimization and generalization based the trajectory length. The pivotal component is the Uniform-LGi property: a condition on the loss function, by which we show that gradient flow returns a global minimum with an explicit length estimate. Further, derive length-based generalization bound given such length estimate. Finally, we apply the framework to three machine learning models with certain target functions. By estimating the trajectory lengths, we get non- non-vacuous generalization bounds that do suffer from the curse of dimensionality. This framework is not a direct variant of the NTK method, and the results show that our framework favorable for inducing connections between optimization and generalization.
'Her Amin @ changes with

---

Under review as a conference paper at ICLR 2022
6 REPRODUCIBILITY STATEMENT
For the experiments, details about the models and the synthetic data are described in Appendix[A.. and Appendix A.2 For the theoretical results, we have included clear explanations of all assumptions.
The complete proofs are provided in Appendix B & D
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. In Advances 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. In International Conference on Machine Learning, pp. 322-332. PMLR, 2019.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normalizne 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, 1177448:33003-330070 2020.
Jérôme Bolte, Aris Daniilidis, and Adrian Lewis. The tojasiewicz inequality for nonsmooth subana- lytic functions with applications to subgradient dynamical systems. SIAM Journal on Optimization, 17(4):1205-4 1223, 2007.
Yuan Cao and Quanquan Gu. Generalization error bounds of gradient descent for learning over- parameterized deep relu networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3349-3356, 2020.
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much over paramcterriiinnoonnnn is sufficient to learn deep relu networks? In International Conference on Learning Representations, 2021.
Benedikt Diederichs and Armin Iske. Improved estimates for condition numbers of radial basis function interpolation matrices. Journal of Approximation Theory, 238:38-53 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 Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many 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.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the Thirteenth International Conference Artificial Intelligence and Statistics, 2010.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. 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-1034, 2015.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks. International Conference on Learning Representations, 2020.
10

---

Under review as a conference paper at ICLR 2022
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- condition. In Joint European Conference on
gradient methods under the Machine Learning and Knowledge Discovery in Databases, pp- Springer, 2016.
Beatrice Laurent and Pascal Massart. Adaptive estimation of quadratic functional by model selection.
Annals of Statistics, pp. 1302-1338, 2000)
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes. Springer Science Business Media, 2013.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in Neural Information Processing Systems, volume 32, 2019.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. The Annals of Statistics, 48(3):1329-1344 2020.
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the multiple descent of minimum-nome norm interpolants and restricted lower isometry of kernels. In Conference Learning Theory, pp. 2683-2711. PMLR, 2020.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. arXiv preprint arXiv:2003.00300 2020.
S. Lojasiewicz. Ensembles semi-analytiques. IHES notes, 1965.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2020.
V A Marčenko and L A Pastur. Distribution of cigenvalues for some sets of random matrices. Mathematics of the
1(4):457-49) apr 1967.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018
Stephen J Montgomery-Smith. The distribution of rademacher sums. Proceedings of the American Mathematical Society, 109(2): 1990.
Mor Shpigel Nacson, Suriya Gunasekar, Jason D Lee, Nathan Srebro, and Daniel Soudry. Lexico- graphic and depth-sensitive margins in homogeneous and non-homogeneous deep models. arXiv preprint arxiv: / /02///005000333 07325, 2019a.
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent on separable data: Exact convergence with fixed learning rate. In The 22nd International Conference 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-normalzzed margin bounds for neural networks. In International Conference on Learning Representations, 2018
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of pver-parametrization in generalization of neural networks. In International Conference on Learning Representations, 2019.
B. Polyak. Gradient methods for the minimisation of functionals. Ussr Computational Mathematics and Mathematical Physics, 3:864-877 8788 1963.
Omar Rivasplata, Ilja Kuzborskij, Csaba Szepesvári, and John Shawe-Taylor Pac-bayes analysis beyond the usual bounds. arXiv preprint arXiv:2006. 13057, 2020.

---

Under review as a conference paper at ICLR 2022
Mark Rudelson and Roman Vershynin. Smallest singular value of random rectangular matrix. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 62(12):1707-1739, 2009.
Mark Rudelson and Roman Vershynin. Non-asymptotic theory of random matrices: extreme singular values. In Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II-IV: Invited Lectures, pp. 1576-1602. World Scientific, 2010.
Daniel Soudry, Elad Hoffer, 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, Elad Hoffer, and Nathan Srebro. The implicit bias of gradient descent separable data. In International Conference on Learning Representations, 2018h 8b.
Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. arXiv preprint arXiv:2009. 14286, 2020.
Holger Wendland. Scattered Data Approximation. Cambridge Monographs on Applied and Compu- tational Mathematics, Cambridge University Press, 2004.
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, and Peter Orbanz. Non-vacuous gen- eralization bounds at the imagenet scale: a PAC-bayesian compression approach. International Conference Learning Representations, 2019.
Difan Zou and Quanquan Gu. An improved analysis of training over- parammeteriized deep neural networks. In Advances in Neural Information Processing Systems, 2019.
12

---

Under review as a conference paper at ICLR 2022
A EXPERIMENTS
A.I EXPERIMENTS SETTINGS
In this subsection, we describe the details of our experiments in the introduction part (Figure
Linear Regression model. The model that we use is underdetermined & linear regression without
130 S R2000 x RR The inputs (;i [130]) are uniformly drawn from the 200-dimensional unit sphere. All labels y:(vi E [330]) generated by linear target function y, 8 x; with some 3 |2000 that satisfies || = 1.
regularization. The data set consists of 130 data points ((I,, Jt)),
We train this model by gradient descent (*++1)
((( -1 Ln, (w(lk) with step size 1) 0.05
on the mean square loss (MSE). Entries of w (0) are initialized i.i.d. from Gaussian distribution N(H, d²) with = 2- 5-553 2,2 2,22,, 2,2!, 24 and a = 2 2 2.22222 2,2", ,2 respectively. We stop the training once the difference loss between two consecutive steps |An (w (w(K+1)) +11) - (wx())) < 10 Then
(wn( oc) is approximated by Ek=1 || - w((-1)) 1) || For each pair of and a. we record the length len(w oo), the training error after convergence and the test error on the convergence point.
Random feature model. this experiment, the model that we consider is two-layer ReLU neural network wh d(Waa)) Here & is the ReLU function, W1 E 200x W02 E R2000, We only train the last layer W2, and thus this can be viewed as random feature model with features extracted by 6( oW1x). The data set consists of 130 data points {(z;, } 130
i==1 S R2200 x R. The inputs (vi [130]) are uniformly drawn from the 200-dimensional unit sphere. All labels (vi E [130]) are generated by a teacher network Wi Φ a;) with the same architecture for some W2z W We train only the top layer by gradient descent with momentum 0.9 and step seize 0.05 under the mean square loss (MSE). Entries of w. are initialized i.i.d. from A N(1, d²) with μ = -, 22 1,4 and = 2-5 2-2, 21 2 respectively. We stop the training once the difference of loss between two consecutive steps is less than 10-8, For each pair of ju and a, we use the same method as on linear regression to approximate the trajectory length. Then record the training error after convergence and the test error on the convergence point.
Varied learning rate. In this experiment, we provide additional results by only changing the learning rate. Figure 2 and correspond to step size 7 = 0.01, 0.1, 0.3 respectively. We observe that the optimization path lengths nearly the same for both small learning rate and moderate learning rate, and the numerical results are associate with our theory.
linear regression model
random feature regression model
104
training error test enror
training
10a
test error
10-1.
10-1
error
10-2
10-3
10-3
10-4
21
23
22
(en(w/01
len(wlo) x))
Figure 2: learning rate = 0.01
13

---

Under review as a conference paper at ICLR 2022
linear regression model
random feature regression model
training enror Lest enrrr
training error
10"
test error
10a-
error
10
10-2
10-1
10-4
23
2
2a
len(w oz)
len(w(0) =)
Figure 3: learning rate = 0.1
linear regression model
random feature regression model
10a
training error
training error
test
10"
test error
10-1
10
10"2.
10
10-
10
23
2-1
2 len(w(0), o))
27
len(w oz)
Figure 4: learning rate = 0.5
A.2 MNIST CLASSIFICATION
In this subsection, we calculate the trajectory length on the MNIST classification problem show the relation between optimization and generalization under different initializations.
Experiment settings. In this experiment, we train two-layer ReLU neural network with 100 hidden units. We use stochastic gradient descent with mini-batch 64, momentum 0.9 and initial learning rate 0.1 train the model. Parameters the hidden layer are initialized by standard random initialization method in Pytorch, and the parameters of the top layer are initialized i..d. from Gaussian distribution
N N(u, d²) with = 2 2 2 and σ = 2-5 5,2 22221
21 24 respectively. During training the model, reduce the learning rate by factor 0.1 once learning stagnates. We stop the training once the cross-entropy loss decreases to 0.01 or the number of epochs reaches 1000. For each pair of
and a, we calculate the trajectory length by Σ [|w(() (k) We plot the relation between optimization and generalization in terms of the trajectory length in Figure
0.5
training enror error
0.4
0.3
error
0.2
0.1
0.0
0.0
0.5
1.0
1.5
2.0
2.5
len(w)1),
Figure 5: MNIST classification
14

---

Under review as a conference paper at ICLR 2022
From this figure, associated with good generalization gap. This numerical result exhibits the generality of our theory and suggests that the path length plays an important role to connect optimization and generalization.
that for different random initializations, short optimization paths is
B PROOF OF THEOREM! 1
In this section will prove Theorem I proof is based the next lemma, showing that the gradient flow trajectory is always inside Sn.
Lemma B.I. For any initialization w((), if (w( satisfies Uniform-ILGi closed set Sn. 2
B (w )a( with constants Cn. On where (n(w(()) (Cn(w) ) (n)w)) 1-00
then
(n(1-0,, 0,,
w S A1 E (0).
Proof. Let
T = inf(1 w()) & S.),
then it is sufficient to prove that T = co. Otherwise, 7 co, then by the continuity of the curve (o(())20 we know that (2') is in the boundary of Sn, therefore
len( (,T)) 2 ((w((), ,,,s) 2 In (w)
(10)
Now consider the following two cases.
Case (i). (w) min, Cn (w). Since (n(((t) is non-increasing, we have L (w((t)) min, fon (w) and w(() w(T) for 1 2 T. Notice that S, is a closed set, thus w(() E Sn. for I E [0, TJ, meaning that 7 oo, which contradicts with < cc.
Case (ii). Ln(w(T)) min C. (w).. By chain rule, we have for all E [0, T).
dLn (w!9))
V V (wol)), dr)())
dwl(t)
- --
di
0n (v)(()
$ -nn (Lo(tt))))
min I(w))
dt
Then bound the trajectory length (w) T)
(t(
len(w (0) .T)
dt
dt
-min c(w)) -0p dL, (wit))
<
(zl( min
0
On
cn - [n) [( (Cnl(ro00) - min L(w) -n
1
(fn(w)()) - min L(w))
1-P.
(n(w(())
(11)
which contradicts with
10
Now begin to prove Theorem
15

---

Under review as a conference paper at ICLR 2022
Proof. By Lemma B.1 we know that Ln (wo(1) satisfies Uniform-LGH for all [0, oo). Then by the proof of Lemma B.1 we have Vt E [0),
C1 - 0n) (C.n(w
min [(w)) 1-0p - (Cn min [(w) 1-
(
w
(12)
For the convergence rate, note that
(Cn(w(()) min ((w))
dw!t)
V Co (w dt
dt
- VLn (x)(t)) 1
(13)
- (Cn(wul - -min L(w)) 28
Therefore
(En((ol()) min ((w)) 20.
d "(Cn(u(t)) -mn min ((w)) - s -c
Integrating on both sides of the equation, we can get Vt (0),
when O2 1
Lu(w!))) min (w) S -ie (Ln( - min La (w))
(14)
when 1 < 8n < 1,
Cn(w(9) - minn Ln (w))= 1 (1 Mt) 11/(20.)) (Cn(w) - -min Lu Su)
(15)
where M (20,, - 1) (C,, (w())) - min L, (w)) 20.
Taking the limit both sides of 14 and (5). since w is the limit of (((), we have
Cn (wol)) min C, (w).
Hence (mo) is a global minimum. Taking the limit on both sides of 12 we get ( ())))))) o0) S (w))
This completes the proof.
C PROOF OF THEOREM 2
In this section, we will prove Theorem This proof is based on the Rademacher complexity theory and the covering number &g balls. Now we introduce some known technical lemmas that are used to build our proof.
The first lemma gives a generalization bound of function class based on the Rademacher complexity, which is proved in (Mohri et al. 2018).
Lemma C.1. Consider family functions F mapping from Z to [a, b). Let D denote the distribution according to which samples are drawn. Then for any > O, with probability at least over the draw of an i..dd sample S = {21..... 2n} of size n, the following holds for all f F
log(2/6)
E [f(z)]
Σ f(2)) < 2Rs(F) 3(b 2)
2m
16

---

Under review as a conference paper at ICLR 2022
where (F) is the empirical Rademacher complexity with respect the sample S, defined as:
1 _ Σ all(E)) ni
Rs(FF
sup fEF
Here {or)i=1 are ii.d. random variables drawn from U{-1,1}.
In the next lemma, we prove shifted version of the Ledoux Ledoux-Talagrann Talagrand contraction inequality (Ledoux & Talagrand 2013), which is useful to bound the length- based Rademacher complexity.
Lemma C.2. Let 9 R Th be a convex and increasing function. Let Φ5 R - TR be T--Lipschitz functions, then for any bounded set C B and any (00) E R. we have
Σ Øs (bi(1:) di (1,0) ))
n
n
(1-0 (.01) )
E.
9
sup (1-1(0))T
E
g
sup (1-110))ET
Σ
ai (1 -
JET
1=1
i=1
and
Σ oi (p((()) - di (1:0) i=1
n
(19)
Σ ai 112 (1=
Eg
sup (t-r(0))
S
2
sup (t-r(0) ET
The special case for (()) 0 corresponds to the original Ledoux-Talle Talagrand contraction inequality. Here we prove a shifted version.
Proof. First notice that
sup Σ oi (1.(.) -ci di (1,0) (1))
Σ (si(ti) di (1(0)
Eg
9
Ex Lun
Bon 9
sup (1-110)) i=1
(1-100))T
1=1
Let un-1(1) Dm 0i (t,(t)) 0i (1.0)) then
Eg n
sup (L-cl0)) ET i=1
as (o:(t)) - di (1:0)
U u + (Dn(tn) On (1200)
sup un-1(t) - (On(tn) - On (1:00 )) (t-rio))ET
= 2
sup (ETT
79
Suppose that the above two suprema can be reached at t' and respectively, i.e.
sup Un (t) + (pn(t.)) on (<()) un (t') (gn (t',) on (((0)
(1-100))T
sup un-1(t)- (tn) - on (t-to))er
-on (2(0) )) un-1 (7) (0n (En) - on ((())
Otherwise we add an arbitrary positive number& in the above equations. Therefore,
n
Σ oe (bi(t)) - Φb (1(0)
E E
9
sup (1-C(0))ET
t=1
g Un- (1') (0n (V')) - Φn (100) ))}}
1
9 Un- (1) -(on (7x) on (10)) )))]
+
2
2
17

---

Under review as a conference paper at ICLR 2022
Without loss of generality, we assume
Un-1 (t') + Φn (1/) - on (100) 2 un-1 (1) +
(nn (Fx) On
(100
(16)
Up (8) On (In) - On (1) 2 un-1 (t') Φn (t/)) - Φn (())
For the other cases, the method remains the same. We set
a = Un 1 On (fx) 2n (())
b un-1 1 (i) L tin (10)
d' un-1 1 (t') + L (th {10)
b' un (1') + (on (12) on (1))
Now our goal is to prove:
g(a) - 9(b) S g(')) (8)).
(17)
Considering the following four cases:
1. ty 2 ( and En 2 (0) By the Lipschitzness of on and equation 16 we know a 2 b, 2
and
(a b) (a' -b') on (th) on (fx) (t, fn)
If t/2 2 in. we can get a b S a' b. By the fact that g is convex and increasing, we have g(v + x)) g(x) is increasing in y for every x 2 0. Hence for x = a b,
g(a) (b)) g(b x) (b)) s g (b' + x) g( (a') g (b').
1, < in we change on into Rr and switch and i, and the proof is similar.
2. t, < tn and f, < tn Similarly, by changing the signs we can get the same result.
3. K, (0) and i. t For this case have b and D' d', so g(a) + 9 (8) S g(b) g (a').
e < (0) and i, 2 (0) For this case we can change on to on. then we have a 2 b and d' s V.
and finally we get ((a) + y (b') < g(b) + (a').
Thus equation
yields that
os (ps(t)) - di (1.0))
Eg
9
sup
(1- ET 1=1
1
Un (t') + On (t,)) - Φn (010) ))
Un- (7) - (On (Ex) - on (1.0)
g
+
9
2
2
1
un (t') (tn - -x(00) )] + + 9
1
L (in {10 ))
g
un-1
2
{000 + )1
Un (t) L (t,, - (aa-(:.)) =
1
un (t) (t,
2
9
(1-) ET
sup
ET
2
g
(M- ET
sup
]
Un (1) + onL (nn (11-11))
9
sup (1-(0))
18

---

Under review as a conference paper at ICLR 2022
Applying the same method to on-1:...; successively, obtain the first inequality
Eg
9
sup (TT
N Σ σi
(si(()) - -di (440) ((19) s E
sup (1-110)) i=1
Σ
(1 14-44 -4-
==1
For the second inequality, since |ar| [at] + [2]] with [x] max xx) and [x:] = max(0, xx),
E
sup
Σ oi
(1,)
01 (100
(t-r(0) ET
ET
Σ (di(ti) $3 (1.0)
Σ oi (di(t.) 21 (1:9) i=1
<E,
sup
E,
sup ((-C(0))TT
ET
1=1
=2E,
sup (1-10))
Σ os
(o.(t.) di (1)0)
ET
Li=1
where the last equality is by |-x]_ [2]] and has the same distribution with simple fact that
sup (1-1(0) ET E
Σ os (p.(t.) 0e
(44 -
sup ((-(0)))
n Σ os d (i (110)
di
Since max(0, x)) is convex and increasing, then by the first inequality we have
Eg
sup (1-1(0)EE
Σ ai (di(tt)) - Φz (1.) +i=1
E.
sup
Σ os
(oi(ts) - di (4
(L-r(0) i=1
< IF
L sup (1-r(0) ET i=1
t; -
Σ oi 44 1 (.0)
< LIE,
sup
((-((0) )T
T=1
This completes the proof.
Now apply Lemma C.2 bound the empirical Rademacher complexity of element-wise distance constrained function class. In the following lemma, all the notations are consistent with Theorem unless stated otherwise.
Lemma C.3. Given function class Fab fx + f(w, .)) Subb and sample S {#1...., FnJ with ||x||| = forr all i E [m], then we have
||a||2 + ||b11
Rs(Fa. S
|| (S..
19

---

Under review as a conference paper at ICLR 2022
Proof. By definition,
(F.b) E.g
sup
oe (w,, Rii)
wESa, i=1
Eg
sup
Σ ows xi))
EE
Σ
(0
a
Eg
sup mESa, i=1
Σ oi (f(w, xz) - (00));))
Now we decompose the term ((r, [(0, as:
f(, f(0,
Ir Cpp ,1,..., - v (0, 0, ,), 0) =(v(x] au S Ba) v ( a a. .......... ( (o...... a ... (0.0.... (... (ap.
=V (a]a), (r
+...+ (v (O. 0, 0, (q) V/ (0, 0, 0.0.....01 0)).
Then by the above decomposition and Lemma C.2 we have
E, sup WES..A
Σ
os (f(w, f(0,
<1.g
(Sn,))
Σ onag on +... T.60 (Sa weS
sup
sup
Σ B
W.S...
Notice that
n
Eg
sup
OgH 01
sup =Eg
WES..h
1=1
|| Saal i=1
12
a
0
< Q1
E,
Σ
0
i=1
d1 nn.
And
Eg
sup
Σ
Eg
sup
WES. i=1
1 Sb
12
S by 0
< by
Eg
h V n.
Therefore, by the inequality, we can get
F
sup Σ
as (f( - /(0,z:))
< r. (Sa.))a / + + T. (p+9) 7 (Sa,b)byV
W 1=1
S s (1al) + [1611²) (10))11100 (Sa,6)))
20

---

Under review as a conference paper at ICLR 2022
Finally, we have
||a|l2 + -|b11
R.s R.((Fab) S
Lemma C.3 gives an upper bound of the Rademacher complexity based on the element-wise distance.
Notice that | S [o)0 + len(w(") oo). To obtain a length-bat based generalization bound, we consider use Sa, to cover the length-constrained space {w ||w||| S R). and then taking union bound. For the l ball covering number, we use the following result from (Neyshabur al. 2019 Lemma 11).
Lemma C.4. Given any D > O, consider the set S fu E |||||| S 3). Then there exist
N sets {T] i=1 of the form T; = {-r E RD, Lzg I a) Vj E [ia] such that $ S U T and
||||| $ 3(1 + c), Vi E [N] where N (K+D-1) and
D
K [
Lemma C.S. For any two positive integers n, k with 2 k, have
Proof. Note that
11
7
n
11
&
k.
k!(n
k))!
k!
S
E
k
The last step is by
k
e
i!
h!
Now combining Lemma C.I
C.3
C.4 and
C.5
we are ready prove Theorem 2
Proof of Theorem First we apply Lemma
C.4
with v2 1, == p q, and B M2 + Ra.5-
then there exist N sets Sax y such that SD N = (2D-1)-
C U A= Sat bt and / |1ab11 +1bb112 S v23, with
Therefore, for each parameter space Sarpr, by Lemma C.3 we have
2 Rs(F (4) = V 3 Le sz )
Notice that the local Lipschitz constant of in S²t or is (S Hence, by Lemma C.1 and the Ledoux- Talagrand contraction inequality, for any 5 > O. with probability at least - 8/N over the training sample, the following holds for all Sau.be:
LD(w)= S (w) 2v23Lr sr) | (S + +3Ma
log(2N/0)
2n
where M3 = suP 1 2 supweS, ( (f(W,
Since (xx) E Sp C U S.u yr, by taking the union bound over all sets Sat sr. we can get with probability at least 1 over the initialization I the training sample,
2 b) L (Sa.b)l + 3.abb
1og(2N/6)
(o(w < C, C,( +
||||| mal +1b12
2n
21

---

Under review as a conference paper at ICLR 2022
Theorem 1 already showed that C, (wo min (u).. Thus it remains to bound the term log N.
For D 1, I,N . = 1. For D 2 2. by Lemma C.5
(e2D -1 1)
log N $ (D 1) log
< 2) 3D 3(p q).
D-1
Finally, let = V23, we complete the proof of Theorem
C.I ADDITIONAL OF RESULTS FOR THE GENERALIZATION DURING TRAINING THE MODEL
Theorem 2 gives length-based bashd generalization bound for the final model. In this subsection, we apply our framework to derive generalization estimates that evolves according to the length of time (number of epochs) of training by combining the length estimate obtained in Theorem [T
The approach is to give a generalization bound for early stopping when the loss value first reaches 0. The idea that, when there exists T > such that (w"))) E, then by the inequality 11 in the proof of Lemma B.1 can get an upper bound for the length len I')) in terms
of Ln (w!")), min,, L(w), e, Cny On. Finally, can get generalization bound by our length estimate.
To get a clean expression for the generalization bound, we assume the optimal value of the empirical loss function (w) is zero. Then the rigorous statement is stated as follows:
Corollary 1. Consider training criterion of early stopping that the training is stopped once the empirical loss value first reaches 2 0. Then for any given 2 under the notations and conditions in Theorem ! suppose that for any 5 E (0. 1), there exists Tn.5 such that Tn (n( S Tn,5 with probability least 1 6 over the initialization and the training samples. Then, we have with probability at least 1 over initialization and the training sumples, the generalization error for the stopping parameter w is given by:
2n. S.n.Le(( (S ( (L + +3M 3(p + q) + log (2/))
(w( S
sup [|a] (+|b+ S. e.n.s
(18)
Vn
2n
where Te,n,8 v2 Ma + rn.8
-1-Pn
en 2m11-00 0
Remark 2. Corollary 7 shows a trade-off between and the term Te,n, The case for corresponds to the combining results of Theorem and Theorem 7
Proof. The proof is straightforward. Notice that by the inequality len( (0) w) as
we can bound the length
8 1-0n
(w w) S (n(
Cn 0m)
where ra (w)( is specified in equation 2 Then by the same argument in the proof of Theorem 2
we may directly replace r., (w)()) with r, (w) en to get the desired bound.
11
D PROOFS FOR SECTION
In this section, goal is to prove all the theorems in Section 4 crucial part of the proofs is the spectral analysis of the random matrix X. Therefore, we start with introducing the non-asymptotic results of Xmax (XXX) and Amin (XX*) from (Rudelson & Vershynin 2010).
The first result is from Rudelssn & Vershynin, 2010 Proposition 2.4). characterizing the non- asymptotic behavior of the largest singular value of subgaussian matrices.
22

---

Under review as a conference paper at ICLR 2022
Lemma D.1. Let A be an Xn random matrix whose entries independent mean subgaussian random variables whose subgaussian moments are bounded by 1. Then for every t 2 0, with probability at least - 2e af over the randomness of the entries,
V Amma C(VN + vn) +t,
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 D.2. Let A be N random matrix whose entries independent and identically distributed subgaussian random variables with zero mean and unit variance. If N >> n, then for every >> 0, with probability at least (Ci=) N-+++ - cN over the randomness of the entries.
(Cit)N-nt1
V Amain (TTA)2
vn 1),
where C1 > and 0j E (0,1) depend only on the subgaussian moment of the entries.
D.1 PROOF OF THEOREM
3
In this section, we will prove Theorem based on the three steps in our framework. All the notations are consistent with Theorem unless stated otherwise.
Proof of Theorem First, we prove the result for Step 1.
For vector a (a1...., an)" R", we use amm to denote the dlmment-wise power, i.c., _0m (aT" ,..., 0% For the Ep linear regression loss function C,(w), notice that
(n)(w) 1 Σ (w a; - y1) p-) Is
1 -x (Nw - 2)0(1-1). n
Then since X' has full row rank, we have Ves E Rdd
1 ! n2
x (Xww 1)1(p-111
Amin (XXT
(X'10 - -0)00-11)
Amiu (XX
1 - ->11pp-2
Amia (XX
|| - -111 1/p--112//
Amin (X'x'
1 1-1/p 1/p
Ln(w)--1/p
Therefore,
On p0 -1/0/ Amin (XXT)
On = 1==1-111 1/p.
For Step 2. note that min,, L, (w) = 0, then the result can be proved by directly plugging c, and 6, into Theorem 1
23

---

Under review as a conference paper at ICLR 2022
Next, we prove the result for Step 3. By Theorem
1 and the property of the target function, we have
for any (0) that satisfies ||ıx(00) [22 S co.
I' (w) vn (pC, (w)())) 1/p
v Amiin (x
['u(l)) -3111
n -2 1/p
Vamin
S Sn 1/2 1/p || (/ - -311/
Amin (K
Amax (XX()
S n 1/2 1/p
Amiu (X (co + c²)
Now apply Lemma D.I 1 6/2 over the samples,
with A = X and t v 1o2(1/8) then we have with probability at least
log(4/8)
Amax (XXT) C(vn+ Va)
(19)
where and C' are two positive constants that depend only on the subgaussian moment of the entries.
Similarly, let = ci E (0, 1 d-n+1 -7 over the samples,
> O, then Lemma
D.2 implies that with probability at least
Vanin(X (XXT)
T
-n-1)
(20)
Ci
where C₁ > 0 and r E (0, 1) depend only on the subgaussian moment of the entries.
n+1 Taking the union bound, we have with probability at least 1-6/2-74 --==+ -7 over the initialization and the training samples.
(n) Vn
C(VI+ vd) + log(4/8)
zn-1p (co + 0*)
c (Vd vn 1)
C C(V 15 + 1) +
log(1/0) od
Sn 1n-1/p 1/8 (co +C*)
& 1 -
(21)
CC1(V7 + 1) + C
21 log(4/8)
In 1/p (co + 6*)
7(1 vn)
log(1/8)
$ 0
n 111 + n -1/1//
Recall for the linear regression model (5. f(w, x²) w x. Thus (xx) = x is identity function with p 1, 0, and (S..,))) 1 for any a, b. Since the loss function é is bounded by 1 and 1-Lipschitz, we know that (S,,), = MR = 1 for any a and b. Finally by Theorem and ē(y. y) = 0, we have with probability at least 1 - 5/2 over the samples,
E( i (f(w(m), v)) = (2(( + cu)
3 + 1og(4/6)
+3/
Vn
2n
Combining the inequality (11) we have with probability at least 1 1 5 samples,
-d--+1 m-1 d over training
(0VVB((10)
(Log(L/0)
ELWNYD j (f(uolo), < (n-1/1) +0
71
24

---

Under review as a conference paper at ICLR 2022
This completes the proof of Theorem
D.2 PROOF OF THEOREM 4
In this section, we will prove Theorem First, we present some useful lemmas for proving our results, and then we give the proofs of Theorem freorem@forr for the RBF kernel and the inner product kernel separately.
For the RBF kernel k(z, y) e (1v -/)), the following two lemmas give non-asymplotic bounds for )max(((22 X)) and Amin (k( x)) based on the separation distance SD X.
The first lemma is from (Diederichs & Iske Amax (k(X,
2019
Lemma 3.1), providing an upper bound for
Lemma D.3. For the RBF kernel, if g R20 > Rg0 a decreasing function, then
Amax (kxX, - (0)) + 3d
(t (t+2)0 e(t--
(22)
and the sum of the infinite series in equation 22 is finite if and only i ([æ|]) L (R²)).
The next lemma is from (Wenlland 2004 Theorem 12.3), giving a lower bound for Amiu ( 22 2)).
Lemma D.4. Suppose that ls positive-defiiite RBF kernel. If ([|=l)) E T. (RR)), one can define the Fourier transform of as Ø(w) := (2x) d/2 Jg o(w)e- dw. With decreasing function go M) ) and two constants Ma, Ca defined as
Ma
(o(M) = inf ((x), Ma = 6.38d, ||
Ca = 2T (d/22++
23/2
where 1' is the gamma function. Then a lower bound on Amin (k(X,X)) is given by
Amin (kx 2 C. 2o (Ma/ SD) SD-
For the inner product kernel k(z, y) = (7²²) it is shown in Karoui et al. 2010) that the
kernel matrix &(X'', X²) can be approximated by the linear combination of all-ones matrix 11 sample covariance matrix XXY and identity matrix. To obtain non-asymptotic results on the spectra of the kernel matrix ((, we borrow the technique from (Liang & Rakhlin 20200 Proposition A.2), and show the result for subgaussian entries the next lemma.
Lemma D.5. For the inner product kernel, suppose that the entries of X are i..dd. subgaussian random variables with zero mean and unit variance, then with probability at least 1 - 8 - d over the entries,
(X' |x(X X) - Ri (X, (x, < 1/2 (8-1/2 +log 0.51
10g a).
where klin (X, X) is defined as
e((0) d
XXT + (e(1) e(0) -e'-eell e'(0)) Taxn-
lin (x (e(0) +
11 e'(0)
Proof. Note that the sample covariance matrix E, Laxds then by applying (Liang & Rakhlin 2020 Proposition A.2) with subgaussian random entries we can prove this lemma.
Lemma D.6. Suppose that A, B xu are two symmetric matrices, then we have Amin (A B) Amin (A) + Amiu (B)..
25

---

Under review as a conference paper at ICLR 2022
Proof. Note that for any R" with ||>:|| 1,
(A + B) T Ar - x Bx 2 Bx
(A) + Amiu
By definition, we have
Amin (A ()+
inf x (A B)x 2 Amin + Amin (B), ||
which completes the proof.
Now are ready to prove Theorem 4
Proof of Theorem
For Step 1. Notice that Vw E R"
1 n
|((() (x((X) -)) 20)00-10/
Amin (x)
((0(X)) -
Amiu (k(
1(p(XL) 2211pp-2
2 Aii (k((''
1(p(2() - -111/-- -011--1.11// 1/00-11110-112 1/1-1112
Amin (k()) (w)
=p" 1/0 1///////
n
Therefore, (w) satisfies the Uniform-LGG globally IR with
Amii Muin(k(A (k(X,, x)) On 11 1/p.
On = ppppp11M -1/p
Since & is a desitive-defintte kernel, and O, = 1 - 1/p, then min C, (w) 0, thus by Theorem we can directly get the result.
For Step 2.
The proof of Step
two-sided. First, since Vo E X. [|p(2))] /k(z, < then the kernel regression model (7) can be viewed as Ep linear regression on inputs (XX)) Hence, v is an identity function with p = 1.9 = O, and (Sa.t)
(S(,),)) MR for any a, b. This means that we only need to bound the term r,, (w)) //vn
By Theorem and the property of the target function, for any (0) that satisfies | S co. we have
Tn (0) vn (pL., (n) (pC.(( (0))) 1/p
V (kt X, xx)))
-n 1/p (xX)) -V11
Amiin (k(x)
< 1/2-111 1/p (1 -3/112
(23)
Annin (k())))))
(2 + ||
< nn 1/2-1/p 1/pp
Ammin (k(22))))
Amax 1c(X'))))
< n 1/2 1/9
(cu +c)).
Amin (k(
26

---

Under review as a conference paper at ICLR 2022
Then for the RBF kernel, Lemma D.3 and Lemma (aaamaaD44inaa indicate that there exists a positive constant (g, d, qmin fmax) that only depends on o, d, 9min Iwax such that
Xmaax
< C(e, d, qmins Imax), Vn 1,
Amin Main(ki (k(X)
which implies that for all initialization w:(0),
In (n((0))
S O (0(n 1/0)
(24)
vn
Therefore, by Theorem and Lemma samples, E (ay ? (f(wlo)),) v)) so (n-1//) +o log(1/6)
C.1 we have with probability at least over training
which completes the proof for the RBF kernel.
For the inner product kernel, to obtain an upper bound for
Amaze (A:(X..) first notice that
Amin (k()
mmax (A(X, x"1 (X, (2,, + ()( 4nmh (2,
(25)
By Lemma D.6
we can get
Amin (A(
2 Amin Amin(k (X, + Amin
- k (2K, 2))
(26)
2 Amin (K (X) - ||((,, - 15t (X, (x)
Under Assumption
Lemma D.5 implies that
< ("
60( | + (e(1)
lin (X, x)
d
d
ng"(0)
Amax Amax (XXT) e'(0)
+ (@(1) - e'(0))
d
d
< (0) + (0) Xmxx
(e(1) e'()))
d
and
Amin (K (x',') 2 e(1) - e'(0) > O.
Thus, by equation
(66) have
Amiu (2,, x)) 2 (e(1) e'())) | wim (x (x,x))
(27)
Under Assumption
by equation
19 we have with probability at least 1 - 5/3 over the samples,
2
Amax (XXX)
n +1)
log(6/8) ed
C
V
d
M1 log 6/6) en
C( 11)+
Therefore, by equation (25). with probability at least
8/3 over the samples,
(((+++))+ (C(V++1)+
/
(m n log(6//) + +(())=6(0++|)((xxx) - 1 (x, (x,2x) x1)1
2
Amnae (k(2,, S me (0)((()+((()))
cn
(28)
27

---

Under review as a conference paper at ICLR 2022
0.51 By Lemma D.5 for large d and small 6 such that d/1/2 (v35-1/ + log log..51 d) = 0.5(e(1) d'(0)). have with probability least 5/3 d=2 over the entries,
[< x) - 1n (2,,
" xx) - 0.5( e'()).
Then equation 27 and 28 yields that with probability at least 28/3 - d= over the samples,
Amin (k(2,R) 2 0.5(e(1) - d'())),
2
Amax (k(XX S n d'(o) (CVTI+I)++ n log(4/0)
+ 1..((((1) 1.5()(1)- e'(0))
cn
Hence, by equation
23
with probability at least 1 - 28/3 d
over the samples, we have
F' (w))))
0 n 1/1 /log(1/6)
(29)
n
n2/2+1/p
Combining Theorem 2 we get with probability at least 1 5 - d-2 over the samples,
E (ay)) (x) s so 00:0 vv) + o
log (1g(
72
which completes the proof.
D.3 PROOF OF THEOREM 5
In this section, we will prove Theorem We first introduce some important lemmas for proving our final results. Lemma D.7 shows that the smallest eigenvalue of the NTK matrix O has lower bounded given the overparamelerization, by which we can prove the optimization result. Lemma D.8, show that the eigenvalues of the NTK matrix are related the data covariance matrix. Then by combining Lemma D.II and Lemma D.9 we can prove the generalization result.
Lemma D.7. For any (0, 1), if m 2 poly (n, --1 (0),5-1)
then with probability at least
1 8 over the random initialization.
Amin (0()) 2 2
Amin (θ):
14 2 0.
Proof. The proof is the same as the proof of (Du et al.
2019 Lemma 3.4).
Lemma D.8.
Amin (θ) 2 Amin (XX*) /4.
Proof. Notice that for ReLU activation é, a simple fact is that d' (aax)) d'(x) holds for any x e IR given that > 0. Therefore,
i = x. x. ((o [d'(w x:) 2;)]
x ny (wr (o' (www a;) Txy)]
I Iz arccos( x xT)))
2x arcsin(1:, (,.T)))))))))))))))) 1z))
5. Jz
2x
(2k)
(x. 22-2
2T
4 (k!))
k==
28

---

Under review as a conference paper at ICLR 2022
Then
XXT
(2k)
(2 o(2k+2)
+
4
2TT
4th (24)
k=0
XXT
(2k)
(ZTT0022)2))
(X' (2TTocaktt
4
2T
4 (k!) (2k (2k+1)
where is the clement-wise product, and @ is the Khatri-Rao produc (0(k++2) is positive semidefinite, we have Amin (+) 2 Amin (XXx) /4,
Since (( 2) T (X
which completes the proof.
In the next lemma, we adopt an inequality from (Montgomery-Smitn 1990). Lemma D.9. If [a:Ji= are i.i.d. drawn from U1-1,1, 1}, then for any x (x1,..., ,..... k.. E IR",
with probability at least 1 over a,
O
S V 22oog(2/)) |
The following lemma gives a sharp bound for a Chi-square variable, which is from (Laurent & Massart 2000 Lemma 1).
Lemma D.10. Let (Y,,..,, YD) probubility least ö over Y.
be i..dd Gaussian variables, with mean and variance 1. Then with
D Σ
E Dlog { + 2 log {
The next lemma is quoted from (Arora al. 2019 Lemma 5.4), giving an upper bound for the empirical Rademacher complexity if one has an accurate estimate for the distance with respect to each hidden unit.
Lemma D.11. Given 0, consider the following function class
w/P F F= fo x + f(w,x) ||W ([W,,--(9)) s R(Vr E [m]),, - w s D}
with Wi.r Rdd the r-th row of Wt. Then for an i.i.d. sample S = (xI,..., Ind and every B > 0. with probability at least 8 over the random initialization, the empirical Rademacher complexity is bounded as:
1/4 2log(2/0) m
B 22
Rs(F) S
1+
2R² / RV log(2/6)
Now we are ready to prove Theorem 5
For A (aj...., an) E mm B = (bi,..., the Kronecker product.
(....,,,)) bn) E RPxn then A@ B = [ay @ bi. @ bn), where
29

---

Under review as a conference paper at ICLR 2022
Proof of Theorem 5 For Step 1. By Lemma D.7
if m 2 poly Am. ( then with proba-
bility at least
ō over the random initialization.
VLn (w)(0)
1
n (f(w,x,)) - ys) vf(ww(,,..)
72
V [wo ,2) (o(o((), ,2) x2) -
(f(wl), X) 3) T Vs(wol)) X (( X)T (s(wol), X) - -)
2 2mmi (0(1))
V f.
Amia
V (w((t))
n
holds for any 2 O, which means that Ln (w) satisfies the Uniform-LGI for any 2 with
Amiu (t)/n, 0₂ 1/2.
Cy =
For 2t 2. By equation 11 rate:
can directly get get (w())) converges zero with linear convergence
L. (w)()) S exp (-Xmin (-Xmin(()11n)) L. (1)
For Step 3. By equation
12 and Lemma D.8 the length len(w oo) can be bounded as
nCC. (wo(U))
nCn, (w)())
len (0) 00) S rn(w = 2/
S VV Amii (X(
Amin (
By the property of the target function, we have
n
(nC)(w(0))
wi ((W (( x2) 81
2
m
m
wh d(W 2:1) )²
2
+ yp
n
2
Wh d(W//) a.))
Σ y
+
mm
n
2:))² + c /mmxxx
m
Since the entries of W2 are drawn i.i.d from U(-1,1) 1}. then by Lemma D.9 for each v E [m]. with probability least 1 ö/6n over w2,
[w) ((W(())..)) < 2 log
12n
(o(w10) x.)) )
8
30

---

Under review as a conference paper at ICLR 2022
Taking the union bound over all 1,2,.... n, we have with probability at least 1 å over the random initialization,
2 2log(12n,4
72
W2 @W
[(W xx))
7
m
log((1n//1 (2n//))
16 (W x
m
log( 2n/8)
W (0) X
(30)
m
log( 2
|
||-11|
F
log 12//6)
[
V Amax (X.
m
For the Gaussian random matrix W( (0, fmmxd), by Lemma D.10 we have with probability
least 1 5/6 over the random initialization,
log(6/6) md
2 log(6/8)
1 2
(31)
m
md
Taking the union bound of equation
19
20
30 and 31), if m 2 poly (n.A_in (0), then
56 6 over the samples and random initialization I, with probability at least dd-++1
n.n(w(() Amin (XX
(1))
sup w (F
sup w1 (x.g)ED
log(1/5) md
+ log(1/8)
log(n/6) V V vlog(1/0)
md
Vd
vn 1
71 +1+ Vlg((1/0) (1/0)/ 1 vni
log(n/8)
S 0 (log(n/66)
Therefore, with probability at least
d-n+1 164-55) 58/6 over the samples and random initialization,
T' (n(wi())
(
log(n/8)
00
(32)
nn
n
For the r-th row of ((()) we begin to bound the distance
|w10 - w/(0)
for each E [m].
31

---

Under review as a conference paper at ICLR 2022
Notice that
dw (0)
Cn (amlt)))
dt
(((w(()),)) 221) -wi)
vm w2, of (W
-
1
[(w("), 20), 19:)--11 -va vs
nym m
f(wll)) , - 2/1l
nm
2 (Cn(w(
--xmin (0)t/2n)
exp
Hence,
1 1/²
dw
26n (wi(0)
W11 - w1o
1,r
(n((2(0))
S
ds
Amin (e)
m
mdmin (
Now we apply Lemma D.11 with B = Tn (w R sup (u
2n mediia (8)
(n((1))), we
with probability at least
6/12 over the random initalization,
B
2 1og((24/))
1/4
Rs(F) S
+
+ 2R² Vnd + RV 2log(2/88)
22
Then by equation (32 if m poly (n, -o,>aia (0),5-)) (0), n 118/18 12 over the samples and random initialization.
then with probability least pd-n+1
(V
(VoB((n/0)
(og((n/))
Rs( so
7
Finally, by Lemma C.1 we have with probability at least pd-n+1 7d random initialization,
over the samples and
/log(n/0) (V)
B( [ (f(w((o), so
for some constant T E (0, 1) that depend only on the subgaussian moment of the entries. This completes the proof.
32


Reviews:
[{"review_id": "wRVDi8zyBxA", "reviewer": "Reviewer_xkEt", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper inscribes in the relevant research direction aiming at understanding the interplay between efficient optimization and good generalization performances by identifying complexity measures that are implicitly minimised during training. \n\nThe analysis is sound and presented in a clear way. Overall, I found the results interesting and worth of publication although some improvements are needed. \n\nIn my opinion, the main weakness of the work regards the numerical experiments. I find that the authors could have provided better evidence than Figure 1. It is not clear to me whether each point in Figure 1 comes from an average (at fixed initialisation variance) or is the result of a single simulation starting from random Gaussian initialization with that variance. The first option does not make much sense to me, so I am assuming the second. However, in this case, since the initialization is random I do not understand why the authors need to change also the variance instead of comparing the optimization paths starting from different initializations from the same distribution. The way the figure is presented suggests that the length of the optimization path trivially depends on initialization, and similarly the generalization gap. \n\nMoreover, all the experiments are performed for a learning rate $\\eta=0.05$. Since the theory is valid in the limit of gradient flow, I would be interested in seeing how Figure 1 changes for different learning rates.\n\nFinally, it would be interesting to test the generality of the proposed framework by checking the relation between short optimization paths and good generalization in more realistic data model. Has this relation been previously observed in applications?   ", "summary_of_the_paper": "The authors study the connection between optimization and generalization for gradient flow (GF) on loss functions that satisfy a global version of the Lojasiewicz gradient inequality. Under this assumption, they prove convergence of GF to a global minimum and they find an upper bound on the optimization length — measured as the integral of the $\\ell_2-$norm of the gradient from time $t=0$ to the final time. This upper bound depends on the specific choice of the loss function and on the number of samples. With an additional assumption on the hypothesis class (encompassing, e.g., linear shallow networks, two-layer networks) the first result is used to derive an upper bound on the generalization gap. The bound depends on the choice of the loss function, its initial value, and the length of the optimisation path. This leads to the main result that shorter optimization paths induce smaller generalization gap. The authors apply this result to three models (underdetermined $\\ell_p$ linear regression, kernel regression, and overparametrized two-layer networks with ReLU activation) with a given target function. They compute non-asymptotic expressions for the generalization bounds at fixed ratio between sample size and ambient dimension, and show that in these cases the bounds are non-vacuous when the dimension increases.\n", "summary_of_the_review": "I find that this paper is worth of publication since it provides an interesting contribution to a relevant research direction in the theory of machine learning. However, I believe that the authors must improve their numerical results to provide a convincing final version of the work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "E8DxyFQ3y9", "reviewer": "Reviewer_shcV", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well organized and easy to follow. My main concern is regarding the claim \"short optimization paths lead to good generalization\" which I feel misleading. The reason is that\n\na. The upper bound $r_n(w)$ is not path-length related. In contrast, it only depends on the function value gap $L_n(w) - L_n^*$. In other words, we first upper bound the path length by the function value gap, which is expected under Łojasiewicz gradient inequality, then use the later function value gap to derive the generalization bound. Unless the path-length is used in the proof of Theorem 2, I wouldn't call it a length-based generalization bound. Please provide more details on this point. \n\nb. I am not sure whether the following case is possible: there are $w_0$ and $w_1$ that for any $L_n$, the gradient flow from $w_0$ always pass through $w_1$. In this case, they always share the same solution but the path length of $w_1$ is always shorter than the path length of $w_0$. Even though this might be impossible, what I want to say is I don't find the shorter length-path as the cause (in terms of causality) of better generalization, instead, I think the function value gap is the real cause of it, which I believe is well studied in the literature. (it might be wrong but I am happy to further discuss it)\n\nOverall, I can't see how explicitly the length of optimization path influence the generalization bound in the current analysis, instead it is based on the function value gap. I am willing to raise my score if my concern is addressed in the rebuttal. ", "summary_of_the_paper": "The paper provides a novel generalization bound for the gradient flow equation related to the length of the optimization path. The bound is valid for loss function that locally satisfies Łojasiewicz gradient inequality, which is applicable to different machine learning models such as underdetermined $\\ell_p$ linear regression, kernel regression, and overparameterized two-layer ReLU neural networks. Explicit derivations are provided for these three models to show that the length-based generalization bound is non-vacuous. ", "summary_of_the_review": "My major concern is how explicitly the length of optimization path influence the generalization bound in the current analysis, instead it is based on the function value gap.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "54quulh2VwS", "reviewer": "Reviewer_ZB5L", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper develops a convergence and generalization analysis of machine learning models under Uniform-LGI loss functions. The concept of Uniform-LGI loss functions extends the well-known PL condition in the optimization literature and as the paper shows leads to a nice theoretical setting for analyzing the optimization and generalization aspects of different machine learning models. The paper shows applications of the framework to norm-p regression and kernel regression problems as well as one-hidden-layer neural network learning problems.\n\nOverall I think this is an interesting work which shows some insightful generalization results under Uniform-LGI loss functions. My main concern with the paper is that while the paper's title, abstract, and introduction claim that the analysis helps to understand the connection between the length of optimization and the generalization error of learned models, the theoretical results in Theorems 2-5 seem to only bound the generalization error of the final model and do not have anything to say about how the generalization error changes during training the model. I, therefore, suggest the authors either clearly explain how the theorems analyze the role of optimization length in the final generalization performance or change the title and introduction appropriately to reflect the main contributions of the work. \n\nIn addition to the above comment, I am wondering whether the gradient flow simplification in Equation (1) results in a realistic analysis of gradient-based optimization in non-convex deep learning problems. It seems to me that the analysis may not be suitable for stochastic gradient methods which have been shown to achieve a significantly better generalization performance than full-batch gradient descent modeled in the paper. As my final comment, the paper has no numerical results validating the theoretical generalization bounds over standard supervised learning problems. Therefore, it is unclear whether the theory results are useful to bound the generalization error of practical deep learning experiments.", "summary_of_the_paper": "The paper studies generalization and optimization of kernel-based and one-hidden layer neural network models. The convergence guarantee is shown for a Uniform-LGI loss function in Theorem 1. Then, in Theorem 2 the paper proves a generalization guarantee assuming a particular parametric model in Equation (3). Finally, the paper applies these results to p-norm regression, kernel regression, and one hidden layer neural network learning problems.  ", "summary_of_the_review": "The paper shows several interesting generalization results for Uniform-LGI loss functions. While the paper proves several insightful generalization bounds, it seems Theorems 2-5 do not explain the connection between the optimization length and generalization error. Also, the paper has no numerical results validating the generalization results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "2eC-f-pbHOa", "reviewer": "Reviewer_8Scj", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well organized following the approach from optimization to generalization. The theorems and proofs are clearly stated and easy to follow. However, my main concern is that it seems to put two separate results (one for optimization and the other for generalization) together directly, and the novelty of each of the two results may not be significant enough. Also, the results may not support the claim “short optimization paths lead to good generalization” exactly.\n\nFor the optimization part, the definition of the Uniform-LGI (with parameter $\\theta$) is inspired by the original Lojasiewicz inequality, and the proof of convergence is straightforward and similar to Bolte et al. (2007). Nevertheless, I think it is good to introduce the result to the community as an extension to the widely-used PL condition. The sublinear convergence rate is also interesting. It would be better to have more applications satisfying the Uniform-LGI but not the PL condition. In Section 4 only the $l_p$ linear regression has $\\theta > 1/2$, and the other two models still fall into the PL condition.\n\nFor the generalization part, the estimation of generalization error follows the Rademacher approach. The proof is nontrivial while the idea is not complicated: the Rademacher complexity scales with the diameter of the parameter set, i.e., the optimization path length. To claim “short optimization paths lead to good generalization”, I may expect a path-based generalization bound; ~~I think the good generalization here comes more from the good “local landscape” (Uniform-LGI) rather than the “path”.~~ (Edit: my statement was not accurate—Theorem 2 does not require the Uniform-LGI. I mean the generalization bound does not depend on the whole optimization path, but only the endpoint, and the generalization is good if the endpoint falls in a small region.)\n\nIn addition, I think the numerical result in Figure 1 may not illustrate the relationship between the optimization path length and generalization—the larger $\\sigma$ in the initialization (Appendix A) leads to both larger optimization path length and larger generalization gap. I think it would be more fair to compare them with the same $\\sigma$ in the initialization.\n\n**Update**\n\nI appreciate the detailed response from the authors and the careful improvement of the manuscript. Here is my summary of the contributions of the paper:\n* Optimization: it is good to propose the Uniform-LGI as an extension of the PL condition and show the sublinear rate. However, the Uniform-LGI is similar to the original Lojasiewicz inequality, and the proof is straightforward (similar to Bolte et al., 2007?).\n* Generalization: Theorem 2 is equivalent to the following: given a region $S$ with radius $R$, with probability $1 - \\delta$ over the training samples, for all $w \\in S$, the generalization gap $$L_D(w) - L_n(w) \\le \\frac{A R + B \\sqrt{3(p + q) + \\log(2 / \\delta)}}{\\sqrt n}$$ where $A$ depends on the Lipschitz constants in $S$ and $B$ depends on the upper bound of $l$. Similar approach is taken by some previous work (e.g., Allen-Zhu et al., 2019); nevertheless, it is good to state the result precisely. I think the result would be better summarized as “small parameter region leads to good generalization bound”, and this is not surprising as the Rademacher complexity increases w.r.t. $R$.\n\nTherefore, I would like to keep my original score given my concern about the significance of the novelty.", "summary_of_the_paper": "This paper proposes a framework to analyze both optimization and generalization properties under the Uniform-LGI condition (Def 1). From my understanding, the main results consist of two parts:\n\n* Optimization: define the Uniform-LGI as an extension of the PL condition, prove the corresponding convergence result with a sublinear rate, and bound the optimization path length.\n* Generalization: use the Rademacher complexity to estimate the generalization error. The Rademacher complexity scales with the diameter of the parameter set, thus can be bounded by the optimization path length, which connects with the optimization results.\n\nThen the paper apply this framework to three application models: first establish the Uniform-LGI, then calculate the optimization path length and estimate the generalization error.", "summary_of_the_review": "The paper is well organized and clearly written. It is interesting to introduce the Uniform-LGI as an extension to the PL condition. However, I think the novelty of each of the two main results is not significant enough, and putting them together may not support the claim “short optimization paths lead to good generalization” exactly.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents several interesting generalization results for Uniform-LGI loss functions (a generalization of PL functions). Some of these bounds seem useful, but the overall connection with the optimization length remains unclear. This concern and other points of criticism remain present after the rebuttal phase. Other minor concerns seem fixable, but in a larger timeline compared to the camera ready one. The paper should be revised for a future venue.
Decision: Reject