summaries: 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:  * 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. * 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.  Then 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. 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.   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.  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. 
abstractText: 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 lp linear regression, kernel regression, and overparameterized two-layer ReLU neural networks.
references.authors: Zeyuan Allen-Zhu Yuanzhi Li Yingyu Liang
references.title: Learning and generalization in overparameterized neural networks, going beyond two layers
references.venue: In Advances in neural information processing systems,
references.authors: Sanjeev Arora Simon Du Wei Hu Zhiyuan Li Ruosong Wang
references.title: Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks
references.venue: In International Conference on Machine Learning,
references.authors: Peter L Bartlett Dylan J Foster Matus J Telgarsky
references.title: Spectrally-normalized margin bounds for neural networks
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Peter L Bartlett Philip M Long Gábor Lugosi Alexander Tsigler
references.title: Benign overfitting in linear regression
references.venue: Proceedings of the National Academy of Sciences,
references.authors: Jérôme Bolte Aris Daniilidis Adrian Lewis
references.title: The łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems
references.venue: SIAM Journal on Optimization,
references.authors: Yuan Cao Quanquan Gu
references.title: Generalization error bounds of gradient descent for learning overparameterized deep relu networks
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Zixiang Chen Yuan Cao Difan Zou Quanquan Gu
references.title: How much over-parameterization is sufficient to learn deep relu networks
references.venue: In International Conference on Learning Representations,
references.authors: Benedikt Diederichs Armin Iske
references.title: Improved estimates for condition numbers of radial basis function interpolation matrices
references.venue: Journal of Approximation Theory,
references.authors: Simon S. Du Xiyu Zhai Barnabas Poczos Aarti Singh
references.title: Gradient descent provably optimizes over-parameterized neural networks
references.venue: In International Conference on Learning Representations,
references.authors: Gintare Karolina Dziugaite Daniel M. Roy
references.title: Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data
references.venue: In Proceedings of the 33rd Annual Conference on Uncertainty in Artificial Intelligence (UAI),
references.authors: Noureddine El Karoui
references.title: The spectrum of kernel random matrices
references.venue: Annals of statistics,
references.authors: Xavier Glorot Yoshua Bengio
references.title: Understanding the difficulty of training deep feedforward neural networks
references.venue: In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics,
references.authors: Noah Golowich Alexander Rakhlin Ohad Shamir
references.title: Size-independent sample complexity of neural networks
references.venue: In Conference On Learning Theory,
references.authors: Kaiming He Xiangyu Zhang Shaoqing Ren Jian Sun
references.title: Delving deep into rectifiers: Surpassing human-level performance on imagenet classification
references.venue: In Proceedings of the IEEE international conference on computer vision,
references.authors: Ziwei Ji Matus Telgarsky
references.title: Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks
references.venue: In International Conference on Learning Representations,
references.authors: Hamed Karimi Julie Nutini Mark Schmidt
references.title: Linear convergence of gradient and proximalgradient methods under the polyak-łojasiewicz condition
references.venue: In Joint European Conference on Machine Learning and Knowledge Discovery in Databases,
references.authors: Beatrice Laurent Pascal Massart
references.title: Adaptive estimation of a quadratic functional by model selection
references.venue: Annals of Statistics,
references.authors: Michel Ledoux Michel Talagrand
references.title: Probability in Banach Spaces: isoperimetry and processes
references.venue: Springer Science & Business Media,
references.authors: Jaehoon Lee Lechao Xiao Samuel Schoenholz Yasaman Bahri Roman Novak Jascha SohlDickstein Jeffrey Pennington
references.title: Wide neural networks of any depth evolve as linear models under gradient descent
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Tengyuan Liang Alexander Rakhlin
references.title: Just interpolate: Kernel “ridgeless” regression can generalize
references.venue: The Annals of Statistics,
references.authors: Tengyuan Liang Alexander Rakhlin Xiyu Zhai
references.title: On the multiple descent of minimum-norm interpolants and restricted lower isometry of kernels
references.venue: In Conference on Learning Theory,
references.authors: Chaoyue Liu Libin Zhu Mikhail Belkin
references.title: Loss landscapes and optimization in over-parameterized non-linear systems and neural networks
references.venue: arXiv preprint arXiv:2003.00307,
references.authors: S. Lojasiewicz
references.title: Ensembles semi-analytiques
references.venue: IHES notes,
references.authors: Kaifeng Lyu Jian Li
references.title: Gradient descent maximizes the margin of homogeneous neural networks
references.venue: In International Conference on Learning Representations,
references.authors: V A Marčenko L A Pastur
references.title: Distribution of eigenvalues for some sets of random matrices. Mathematics of the USSR-Sbornik
references.authors: Mehryar Mohri Afshin Rostamizadeh Ameet Talwalkar
references.title: Foundations of machine learning
references.venue: MIT press,
references.authors: Stephen J Montgomery-Smith
references.title: The distribution of rademacher sums
references.venue: Proceedings of the American Mathematical Society,
references.authors: Mor Shpigel Nacson Suriya Gunasekar Jason D Lee Nathan Srebro Daniel Soudry
references.title: Lexicographic and depth-sensitive margins in homogeneous and non-homogeneous deep models
references.venue: arXiv preprint arXiv:1905.07325,
references.authors: Mor Shpigel Nacson Nathan Srebro Daniel Soudry
references.title: Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate
references.venue: In The 22nd International Conference on Artificial Intelligence and Statistics,
references.authors: Behnam Neyshabur Ryota Tomioka Nathan Srebro
references.title: Norm-based capacity control in neural networks
references.venue: In Conference on Learning Theory, pp
references.authors: Behnam Neyshabur Srinadh Bhojanapalli Nathan Srebro
references.title: A PAC-bayesian approach to spectrally-normalized margin bounds for neural networks
references.venue: In International Conference on Learning Representations,
references.authors: Behnam Neyshabur Zhiyuan Li Srinadh Bhojanapalli Yann LeCun Nathan Srebro
references.title: The role of over-parametrization in generalization of neural networks
references.venue: In International Conference on Learning Representations,
references.authors: B. Polyak
references.title: Gradient methods for the minimisation of functionals
references.venue: Ussr Computational Mathematics and Mathematical Physics,
references.authors: Omar Rivasplata Ilja Kuzborskij Csaba Szepesvári John Shawe-Taylor
references.title: Pac-bayes analysis beyond the usual bounds
references.venue: arXiv preprint arXiv:2006.13057,
references.authors: Mark Rudelson Roman Vershynin
references.title: Smallest singular value of a random rectangular matrix
references.venue: Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences,
references.authors: Mark Rudelson Roman Vershynin
references.title: Non-asymptotic theory of random matrices: extreme singular values
references.venue: In Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In 4 Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II–IV: Invited Lectures,
references.authors: Daniel Soudry Elad Hoffer Mor Shpigel Nacson Suriya Gunasekar Nathan Srebro
references.title: The implicit bias of gradient descent on separable data
references.venue: The Journal of Machine Learning Research,
references.authors: Daniel Soudry Elad Hoffer Nathan Srebro
references.title: The implicit bias of gradient descent on separable data
references.venue: In International Conference on Learning Representations,
references.authors: Alexander Tsigler Peter L Bartlett
references.title: Benign overfitting in ridge regression
references.venue: arXiv preprint arXiv:2009.14286,
references.authors: Holger Wendland
references.title: Scattered Data Approximation
references.authors: Wenda Zhou Victor Veitch Morgane Austern Ryan P. Adams Peter Orbanz
references.title: Non-vacuous generalization bounds at the imagenet scale: a PAC-bayesian compression approach
references.venue: In International Conference on Learning Representations,
references.authors: Difan Zou Quanquan Gu
references.title: An improved analysis of training over-parameterized deep neural networks
references.venue: In Advances in Neural Information Processing Systems,
sections.heading: 1 INTRODUCTION
sections.text: 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 by an optimization algorithm. Therefore, a fundamental question is whether an optimization algorithm produces a solution with good generalization.
  Recent works have shed light on providing theoretical explanations to this question from different angles. One line of works considered the case when gradient methods converge to minimal norm solutions (Bartlett et al., 2020; Tsigler & Bartlett, 2020; Liang & Rakhlin, 2020; Liang et 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)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 generalization, they focused on studying specific models, such as 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 1, 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 path1 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 in early-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 a kind of capacity control, and a
  1For discrete iterations, we use the sum of the distance between every two consecutive iterations to represent the length of the optimization path (See details in Appendix A.1).
  short path signifies low “complexity”. In other words, a general condition that guarantees a short optimization path can be used to induce good generalization performance. Thus, inspired by the theory in (Bolte et al., 2007) that Łojasiewicz gradient inequality (LGI) induces an explicit bound for the gradient flow path, we consider Uniform-LGI (Definition 1). This is a modified version of LGI and plays a critical role in obtaining a length estimate for the gradient flow trajectory. Once the length is estimated, we can use our length-based generalization bounds to show the generalization performance.
  Contributions. We 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 is the Uniform-LGI property.
  • We then prove that under appropriate conditions, gradient flow returns a global minimum and gives an explicit length-estimate for the gradient flow trajectory (Theorem 1). If this length-estimate has an uniform bound for a certain initialization method, then we can give a length-based generalization bound (Theorem 2).
  • We further show applications of Theorem 1 and Theorem 2 to obtain generalization bounds on underdetermined ℓp linear regression (Theorem 3), kernel regression (Theorem 4), and overparameterized two-layer ReLU neural networks (Theorem 5). These bounds match or expand the type of scenarios where we can rigorously establish the phenomenon of benign overfitting.
sections.heading: 2 RELATED WORKS
sections.text: Optimization. Theoretically analyzing the training process of most machine learning models is a challenging problem as the loss landscapes are highly non-convex. One approach to studying non-convex optimization problems is to use the Polyak-Łojasiewicz (PL) condition (Polyak, 1963), which characterizes the local geometry of loss landscapes and ensures the existence of global minima. It is shown in (Karimi et al., 2016) that GD admits linear convergence for a class of optimization objective functions under the PL condition. In this paper, we consider the Łojasiewicz gradient inequality (Lojasiewicz, 1965), an extended version of the PL condition that can be applied to more cases. In particular, we modify the original LGI to get length estimates of the optimization paths, which will be used to derive length-based generalization bounds.
  Generalization. Traditional VC dimension-based generalization bounds depend on the number of parameters and will be vacuous for huge models such as overparameterized neural networks. To overcome this limitation, several non-vacuous generalization bounds are proposed. For example, the norm/margin-based generalization bounds (Neyshabur et al., 2015; Bartlett et al., 2017; Golowich
  et al., 2018; Neyshabur et al., 2019), and the PAC-Bayes-based bounds (Dziugaite & Roy, 2017; Neyshabur et al., 2018; Zhou et al., 2019; Rivasplata et al., 2020). However, these bounds tend to focus less on optimization, e.g., norm-based 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 trajectory length.
  Interface between 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 separating hyperplanes and therefore generalizes well. Other works (Arora et al., 2019; Zou & Gu, 2019; Cao & Gu, 2020; Ji & Telgarsky, 2020; Chen et al., 2021) 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 on specific conditions on loss functions under which we can connect optimization and generalization based on the lengths of optimization paths.
sections.heading: 3 MAIN RESULTS
sections.text: In this section, we aim to 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 in Section 3.2. Lastly, we show a length-based generalization bound in Section 3.3.
sections.heading: 3.1 SETUP AND NOTATIONS
sections.text: Consider a supervised learning problem on a hypothesis space F = { f(w, ·) : Rd −→ R | w ∈ W } , where W is a parameter set in Euclidean space. Given a loss function ℓ : R× R −→ R, and a training set S = {(xi, yi)}ni=1 ⊆ Rd × R with n independent and identically distributed (i.i.d.) samples from a joint distribution D, the goal of ERM is to optimize the empirical loss function Ln(w) on S:
  argmin w
  Ln(w) := 1
  n n∑ i=1 ℓ (f(w, xi), yi) .
  We assume that each input vector and label have bounded norms. Specifically, we assume that, for any (x, y) following D, ∥x∥ = 1, |y| ≤ 1. This can be achieved by data normalization. To simplify the analysis, we optimize the empirical loss by gradient flow2:
  dw(t)
  dt = −∇Ln(w(t)), t ∈ [0,+∞), (1)
  where w(t) is the parameter value at time t, w(0) is the initialization parameter set, and ∇Ln(w) is the gradient of Ln(w) with respect to w. Given the gradient flow, we may define the length of the gradient flow curve from w(0) to w(t) as len(w(0), t) := ∫ t 0 ∥∥∥dw(s)ds ∥∥∥ ds. Notations. We use ∥·∥ to denote the ℓ2 norm of a vector or the spectral norm of a matrix, and use ∥·∥F to denote the Fronenius norm of a matrix. For a set S ∈ Rn, we use ∂S to denote its boundary. We use d(S1,S2) to represent the Euclidean distance between two sets S1,S2, which is defined as d(S1,S2) = {inf ∥s1 − s2∥ : s1 ∈ S1, s2 ∈ S2}. For two vectors, we use ⟨, ⟩ to denote their inner product. Let λmin(A) and λmax(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 O(·) to stand for Big-O notation. The classical LGI gives a lower bound of the gradient of a 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 et al., 2007). Here, we require a global version of this inequality as a condition to control the gradient flow trajectory. Let us define this notion below. Definition 1 (Uniform-LGI). A function L(w) satisfies Uniform-LGI on a set S with two constants c > 0 and θ ∈ [ 12 , 1), if ∥∇L(w)∥ ≥ c (L(w)−minv∈W L(v)) θ , ∀w ∈ S.
  2Here we assume the existence of the gradient flow and the limit limt−→∞ w(t).
  In the special case when θ = 1/2 and c = √ 2µ, the Uniform-LGI corresponds to the µ-PL condition (Karimi et al., 2016). Here we give examples of functions satisfying the Uniform-LGI but not the PL condition: L(w) = w2k, k ∈ Z+. When k ≥ 2, L(w) satisfies the Uniform-LGI on R with c = 2k and θ = 1− 1/2k.
sections.heading: 3.2 GRADIENT FLOW TRAJECTORY LENGTH ESTIMATE
sections.text: Our first result shows that under the uniform-LGI condition, gradient flow returns a global minimum with an explicit estimate of the gradient flow trajectory length as in the following theorem.
  Theorem 1. For any initialization w(0), if Ln(w) satisfies Uniform-LGI on a closed set Sn with constants cn, θn such that Sn ⊇ B ( w(0), rn(w (0)) ) , where
  rn(w (0)) =
  ( Ln(w(0))−minw Ln(w) )1−θn cn(1− θn) , (2)
  then w(t) converges to a global minimum w(∞) with the trajectory length upper bounded by len(w(0),∞) ≤ rn(w(0)). The convergence rate of Ln(w(t)) is given by:
  θn = 1
  2 : Ln(w(t))−min w Ln(w) ≤ e−c
  2 nt ( Ln(w(0))−min
  w Ln(w)
  ) ,
  1 2 < θn < 1 : Ln(w(t))−min w Ln(w) ≤ (1 +Mnt)−1/(2θn−1)
  ( Ln(w(0))−min
  w Ln(w)
  ) ,
  where Mn = c2n(2θn − 1) ( Ln(w(0))−minw Ln(w) )2θn−1. The proof of Theorem 1 is given in Appendix B.
  This theorem yields that once the loss function satisfies the Uniform-LGI around the initialization, gradient flow returns a global minimum with an explicit trajectory length estimate. Moreover, for any fixed n, len(w(0),∞) decreases as the initial loss value decreases. The calculation of cn, θn for different n should be analyzed case by case based on the loss landscape, as shown in Section 4.
sections.heading: 3.3 HOW DOES THE OPTIMIZATION PATH LENGTH AFFECT GENERALIZATION?
sections.text: The Uniform-LGI property allows us to have an upper bound for the gradient flow trajectory length. In this subsection, we use the length estimate we get in Theorem 1 to study generalization.
  Throughout this subsection, we assume that there exists an almost everywhere differentiable function Ψ : Rp+q −→ R such that f(w, ·) can be represented in the following form,
  ∀x ∈ Rd, f(w, x) = Ψ ( α⊤1 x, . . . , α ⊤ p x, β1, . . . , βq ) (3)
  with α1, . . . , αp ∈ Rd, β1, . . . , βq ∈ R, and w = vec ({α1, . . . , αp, β1, . . . , βq}) ∈ Rpd+q. Here vec is the vectorization operator that concatenates all elements into a column vector.
  A wide class of functions can be represented in the form (3). Examples include linear functions f(w, x) = w⊤x and two-layer neural networks f(w, x) = a⊤ϕ (Wx) with a ∈ Rm,W ∈ Rm×d. Additional notations. For the loss function ℓ, we use Lℓ(S) to denote its Lipschitz constant (the maximal gradient norm) on S with respect to its first argument. For Ψ in (3), we define LΨ(S) :=( L (1) Ψ (S), · · · , L (p) Ψ (S), L (p+1) Ψ (S), · · · , L (p+q) Ψ (S) )⊤ , where L(i)Ψ (S) is the Lipschitz constant of
  Ψ on S with respect to the i-th variable. Let w(0) := vec ({
  α (0) 1 , . . . , α (0) p , β (0) 1 , . . . , β (0) q
  }) and
  use LD(w) to denote the expected loss E(x,y)∼D [ℓ(f(w, x), y)]. For a = (a1, . . . , ap)⊤ and b = (b1, . . . , bq)
  ⊤, we define Sa,b = {w : ∀i ∈ [p], j ∈ [q], ∥αi∥ ≤ ai, |βj | ≤ bj}, and Ma,b = supw∈Sa,b,∥x∥≤1,|y|≤1 ℓ (f(w, x), y).
  In the following theorem, we give a path-based generalization bound if one has a length estimate for optimization trajectory length len(w(0),∞). Based on the Uniform-LGI property, Theorem 1 serves as a sufficient condition to ensure that the trajectory length can be estimated. In that sense, we connect optimization with generalization. The rigorous statement is as follows:
  Theorem 2. Consider an initialization method so that w(0) is independent of the training samples and suppose that for any δ ∈ (0, 1), there exist Mδ, Rn,δ > 0 such that ∥∥w(0)∥∥ ≤ Mδ, len(w(0),∞) ≤ Rn,δ with probability at least 1− δ over the initialization and the training samples. Then, we have with probability at least 1− δ over initialization and the training samples, the generalization error of the global minimum w(∞) is bounded as:
  LD(w(∞)) ≤ min w Ln(w)+ sup ∥a∥2+∥b∥2≤R2 2RLℓ(Sa,b) ∥LΨ(Sa,b)∥√ n +3Ma,b
  √ 3(p+ q) + log(2/δ)
  2n ,
  (4) where R = √ 2(Mδ +Rn,δ).
  The proof of Theorem 2 is given in Appendix C. There are five key terms in (4). To make the bound easier to understand, we discuss them in sequence: • Mδ: This is a high probability upper bound for the ℓ2 norm of the initialized vector ∥∥w(0)∥∥. In
  practice, for commonly used initialization methods in deep learning, such as Xavier initialization (Glorot & Bengio, 2010) and Kaiming initialization (He et al., 2015), the norm ∥∥w(0)∥∥ is uniformly bounded with high probability.
  • Rn,δ: This is an high probability upper bound for the optimization path length over the initialization and training samples. Theorem 2 assumes that such a bound exists, and show that it immediately implies a generalization estimate based on this bound. Theorem 1 gives a sufficient condition to obtain such a path estimate, in which case it depends on the Uniform-LGI constants cn, θn and data distribution D. The asymptotic analysis of Rn,δ is problem-dependent, and we provide several examples in Section 4.
  • Lℓ(Sa,b) and Ma,b: They depend on the loss function ℓ. For example, for any loss function ℓ : R× R −→ [0, 1] that is 1-Lipschitz in the first argument, Lℓ(Sa,b) = Ma,b = 1.
  • ∥LΨ(Sa,b)∥: This term relies on the structure of f . For example, when f is linear, Ψ(x, y) = x+y, then ∥LΨ(Sa,b)∥ = √ 2.
  Remark 1. Theorem 2 shows that if the optimization trajectory length is small, then this implies a good generalization bound. First, note that our generalization bound concerns the weights of the final model. Nevertheless, by the convergence analysis in Theorem 1, 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, we emphasize again that the generalization bound in Theorem 2 only relies on a path length estimate, and theorem 1 gives a sufficient condition to ensure that such an estimate exists. Consequently, as long as one can 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 an interesting future direction.
sections.heading: 4 APPLICATIONS
sections.text: In this section, we apply the framework to three models. To obtain clean expressions of the generalization bound in terms of the sample size n, it is helpful to consider a range of n relating to the dimension d. In particular, we consider underdetermined systems where the ratio n/d remains finite unless stated otherwise:
  ∃ γ0, γ1 ∈ (0,∞), s.t. ∀d, γ0d ≤ n = n(d) ≤ γ1d.
  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×R −→ [0, 1] is 1-Lipschitz (on the first argument) with ℓ̃(y, y) = 0. The following steps are taken in our framework:
  Step 1. Establish the Uniform-LGI property and find the Uniform-LGI constants cn and θn.
  Step 2. Apply Theorem 1 to get optimization results to estimate path length.
  Step 3. Apply Theorem 2 to get generalization results from the path length estimates.
  4.1 UNDERDETERMINED ℓp LINEAR REGRESSION
  We begin with an underdetermined linear regression model f(w, x) = w⊤x with an ℓp loss function (p ≥ 2 is an even positive integer):
  argmin w∈Rd
  Ln(w) := 1
  pn n∑ i=1 ( w⊤xi − yi )p , (5)
  where the input data matrix X = (x1, . . . , xn)⊤ ∈ Rn×d has full row rank. Then the above regression model has at least one global minimum with zero loss.
  Target function. Suppose the training data is generated from an underlying function g : Rd −→ R with yi = g(xi), ∀i ∈ [n]. Let Y = (y1, · · · , yn)⊤, and assume that there exits c∗ > 0 such that
  ∥Y∥ ≤ c∗ √ λmax(XX⊤). (6)
  The inequality (6) actually indicates that g is Lipschitz with a dimension independent Lipschitz constant. Functions satisfying (6) include linear/non-linear functions. For example, g(x) = ϕ(x⊤w∗), where w∗ ∈ Rd with ∥w∗∥2 ≤ c∗ 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 moments3 bounded by 1.
  This assumption allows us to study the spectral properties of the sample matrix by random matrix theory. Especially, when n(d)/d converges to some constant γ ∈ (0, 1), the Marchenko–Pastur law (Marčenko & Pastur, 1967) shows that λmin(XX⊤)/n converges to (1− √ γ)2 almost surely. The non-asymptotic results are provided in (Rudelson & Vershynin, 2010).
  Performing our three-step analysis, we get the following results: Theorem 3. Consider the undertermined ℓp linear regression model (5). Suppose that there exists a universal constant c0 ≥ 1 such that ∀d, ∥∥w(0)∥∥ 2 ≤ c0.
  Step 1. Ln(w) satisfies the Uniform-LGI globally on Rd with
  cn = p 1−1/p
  √ λmin(XX⊤)
  n , θn = 1− 1/p.
  Step 2. Ln(w(t)) converges to zero linearly for p = 2 and sublinearly for p ≥ 4, i.e., p = 2, Ln(w(t)) ≤ exp ( −2λmin(XX⊤)t/n ) Ln(w(0));
  p ≥ 4, Ln(w(t)) ≤ (1 +Mt)− p p−2 Ln(w(0)),
  where M = p1− 2 p (p− 2)λmin(XX ⊤) n Ln(w (0))1− 2 p .
  Step 3. Under Assumption 1, for any target function that satisfies (6), we have with probability at least 1− δ − τd−n+1 − τd over the samples,
  E(x,y)∼D [ ℓ̃ ( f(w(∞), x), y )] ≤ O ( n−1/p ) +O
  (√ log(1/δ)
  n
  ) ,
  where τ ∈ (0, 1) depends only on the subgaussian moment of the entries.
  The proof of Theorem 3 is given in Appendix D.1. This theorem shows that compared to the PL condition that corresponds to p = 2, the uniform-LGI 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 ℓ2 linear regression. Our result coincides with theirs as both results uncover some scenarios for benign overfitting in linear regression. In particular, (Bartlett et al.,
  3The subgaussian moment of X is defined as inf { M ≥ 0 | EetX ≤ eM 2t2/2, ∀t ∈ R } .
  2020) focused on the minimum ℓ2 norm estimator. They showed that, if the eigenvalue sequence of the covariance operator Σ := E[xx⊤] have suitable decay rates, then the generalization error will decrease to zero as n increases. In contrast, our result differs from theirs in the problem settings. Specifically, we do not assume the minimum norm property and consider the optimization process that is neglected in (Bartlett et al., 2020). Also, we evaluate the generalization error of the convergence point on a globally Lipschitz loss function. In our settings, entries of each input x are i.i.d. random variables, meaning that Σ = Id×d without decaying eigenvalues. The requirement of i.i.d. entries for each input is a limitation due to the lack of non-asymptotic 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 ℓp loss functions with any even positive integer p. This expands the understanding of benign overfitting in the high-dimensional setting.
sections.heading: 4.2 KERNEL REGRESSION
sections.text: Consider a positive definite kernel k : X × X −→ R with its corresponding feature map φ : Rd −→ F satisfying ⟨φ(x), φ(y)⟩F = k(x, y). We assume that |k(x, x)| ≤ 1,∀x ∈ X . Let H be the reproducing kernel Hilbert space (RKHS) with respect to k. If F = Rs, then the kernel regression model with ℓp loss is to solve the following problem
  argmin w∈Rs
  Ln(w) := 1
  2n n∑ i=1 ( w⊤φ(xi)− yi )p , (7)
  where p ≥ 2 is an even integer. Similar to the ℓp 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(xi), ∀i ∈ [n]. We further assume that there exits a constant c∗ > 0 such that
  ∥Y∥ ≤ c∗ · √ λmax(k(X ,X )), (8)
  where k(X ,X ) is the n× n kernel matrix on X with k(X ,X )ij = k(xi, xj).
  Here, we list an example of class of functions that satisfies (8): g(x) = ϕ(φ(x)⊤w∗) where w∗ ∈ Rs with (∀s) ∥w∗∥2 ≤ c∗ for some constant c∗, and ϕ(·) 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) kernel and inner product kernel.
  RBF kernel. We study the RBF kernel of the form k(x, y) = ϱ (∥y − x∥) for a certain RBF ϱ. For the input data, we define the separation distance of X as SD := 12 mini̸=j ∥xi − xj∥ ,∀i, j ∈ [n]. Inner product kernel. For the inner product kernel, we consider k(x, y) = ϱ ( x⊤y d ) .
  Following (El Karoui et al., 2010), we make the following assumption on the function ϱ: Assumption 2. ϱ is C3 in a neighborhood of 0 with ϱ(0) = 0, ϱ(1) > ϱ′(0) ≥ 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 high-dimensional random kernel matrix. Theorem 4. Consider the kernel regression model (7). Suppose that there exists a universal constant c0 ≥ 1 such that ∀s, ∥∥w(0)∥∥ 2 ≤ c0.
  Step 1. Ln(w) satisfies the Uniform-LGI globally on Rs with
  cn = p 1−1/p
  √ λmin(k(X ,X ))
  n , θn = 1− 1/p,
  where cn is controlled by the kernel and input samples.
  Step 2. Ln(w(t)) converges to zero linearly for p = 2 and sublinearly for p ≥ 4, i.e.,
  p = 2, Ln(w(t)) ≤ exp (−2λmin(k(X ,X ))t/n)Ln(w(0)); p ≥ 4, Ln(w(t)) ≤ (1 +Mt)− p p−2 Ln(w(0)),
  where M = p1− 2 p (p− 2)λmin(k(X ,X ))n Ln(w (0))1− 2 p .
  Step 3. For any target function that satisfies (8) we have:
  • For the RBF kernel4, suppose that ϱ : R≥0 −→ R≥0 is a decreasing function and ϱ (∥x∥) ∈ L1(Rd). If there exists two positive constants qmin and qmax such that SD ∈ [qmin, qmax] for all n, then with probability at least 1− δ over the samples,
  E(x,y)∼D [ ℓ̃ ( f(w(∞), x), y )] ≤ O ( n−1/p ) +O
  (√ log(1/δ)
  n
  ) .
  • For the inner product kernel, under Assumption 1 and Assumption 2, if d is large enough and δ > 0 is small enough such that d−1/2 (√ 3δ−1/2 + log0.51 d ) ≤ 0.5(ϱ(1)−ϱ′(0)), then with probability
  at least 1− δ − d−2 over the samples, we have
  E(x,y)∼D [ ℓ̃ ( f(w(∞), x), y )] ≤ O ( n−1/p ) +O
  (√ log(1/δ)
  n
  ) .
  The proof of Theorem 4 is given in Appendix D.2. Example 1. RBF kernels satisfying the conditions and assumptions in Theorem 4 include (1) Gaussian: ϱ(r) = e−ρr 2
  , ρ > 0; (2) (inverse) Multiquadrics: ϱ(r) = (ρ + r2)β/2, ρ > 0, β ∈ R\2N, β < −d. Inner product kernels satisfying the conditions and assumptions in Theorem 4 include (1) Polynomial kernel: ϱ(r) = rβ , β ∈ Z+, β ≥ 2; (2) NTK corresponding to Two-layer ReLU neural networks on Sd−1( √ d): ϱ(r) = r(π−arccos(r))2π .
  Comparison. The p = 2 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 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[xx⊤] with the j-th eigenvalue λj(Σ) = j−α, the ℓ2 generalization bound becomes O(n− α 2α+1 ) when α ∈ (0, 1) and n > d. In comparison, we get an optimal generalization
  bound O ( n−1/2 ) for identity covariance matrix on a globally Lipschitz loss function. Again, we emphasize that the i.i.d. assumption can be relaxed if more new results of random matrix theory are 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-dimensional setting; thus it is not a direct adaptation of (Liang & Rakhlin, 2020), and the proof itself is of independent interest.
sections.heading: 4.3 OVERPARAMETERIZED TWO-LAYER NEURAL NETWORKS
sections.text: 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 a two-layer ReLU neural network under the NTK parameterization (Lee et al., 2019):
  f(w, x) = 1√ m w⊤2 ϕ(W1x),
  where ϕ(x) = max{0, x}, x ∈ Rd is the input, W1 ∈ Rm×d, w2 ∈ Rm are parameters, w = vec ({W1, w2}) ∈ Rm(d+1), and m is the width (number of hidden units). We consider minimizing the quadratic loss by gradient flow:
  argmin w
  Ln(w) := 1
  2n n∑ i=1 (f(w, xi)− yi)2. (9)
  4Here d is fixed and n is varied.
  Random initialization. W (0)1 is drawn from Gaussian N (0, 1d Im×d) and w (0) 2,i are drawn i.i.d. from uniform distribution U{−1, 1},∀i ∈ [m]. Following the setting in (Du et al., 2019), we only train the hidden layer W1 and leave the output layer w2 as random initialization to simplify analyses.
  NTK matrix. The NTK matrix Θ(t) is defined as: Θij(t) = 〈 ∇W1f(w(t), xi),∇W1f(w(t), xj) 〉 ,
  and denote Θ̂ by the limiting matrix5: Θ̂ij = x⊤i xjEw∼N (0, 1d Id) [ ϕ′(w⊤xi)ϕ ′(w⊤xj) ] ,∀i, j ∈ [n].
  Similarly, we apply our three-step analysis to derive the following results. Theorem 5. Consider the two-layer ReLU neural network model (9). For any δ ∈ (0, 1), if m ≥ poly ( n, λ−1min(Θ̂), δ −1 ) , then
  Step 1. With probability at least 1− δ over training samples and random initialization, Ln(w(t)) satisfies the Uniform-LGI on { w(t) : t ≥ 0 } with
  cn = √ λmin(Θ̂)/n, θn = 1/2.
  Step 2. Ln(w(t)) converges to zero with a linear convergence rate: Ln(w(t)) ≤ exp ( −λmin(Θ̂)t/n ) Ln(w(0)).
  Step 3. Under Assumption 1, for any target function that satisfies (6), if γ1 ∈ (0, 1), then with probability at least 1− δ − τd−n+1 − τd over the samples and random initialization,
  E(x,y)∼D [ ℓ̃ ( f(w(∞), x), y )] ≤ O
  (√ log(n/δ)
  n
  ) ,
  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 an NTK-based generalization bound for overparameterized two-layer ReLU neural networks. This result matches with theirs in the sense that we discover some underlying functions that are provably learnable. Examples of learnable target functions in (Arora et al., 2019) include polynomials y = (β⊤x)p, non-linear activations y = cos(β⊤x) − 1, y = ϕ̃(β⊤x) with ϕ̃(z) = z · arctan(z/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 O(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 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 based on the length of optimization trajectories.
sections.heading: 5 CONCLUSION
sections.text: In this work, we address when and why does an optimization algorithm finds a minimum with good generalization performance. For this problem, we propose a framework to bridge optimization and generalization based on 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, we derive a length-based generalization bound given such a length estimate. Finally, we apply the framework to three machine learning models with certain target functions. By estimating the trajectory lengths, we get non-vacuous generalization bounds that do not suffer from the curse of dimensionality. This framework is not a direct variant of the NTK method, and the results show that our framework is favorable for inducing connections between optimization and generalization.
  5Here λmin(Θ̂) changes with n.
sections.heading: 6 REPRODUCIBILITY STATEMENT
sections.text: For the experiments, details about the models and the synthetic data are described in Appendix A.1 and Appendix A.2. For the theoretical results, we have included clear explanations of all assumptions. The complete proofs are provided in Appendix B, C & D.
sections.heading: A EXPERIMENTS
sections.text: A.1 EXPERIMENTS SETTINGS
  In this subsection, we describe the details of our experiments in the introduction part (Figure 1).
  Linear Regression model. The model that we use is underdetermined ℓ2 linear regression without regularization. The data set consists of 130 data points {(xi, yi)}130i=1 ⊆ R200 × R. The inputs xi(∀i ∈ [130]) are uniformly drawn from the 200-dimensional unit sphere. All labels yi(∀i ∈ [130]) are generated by a linear target function yi = β⊤xi with some β ∈ R200 that satisfies ∥β∥ = 1. We train this model by gradient descent w(k+1) = w(k) − η∇Ln(w(k)) with step size η = 0.05 on the mean square loss (MSE). Entries of w(0) are initialized i.i.d. from Gaussian distribution N (µ, σ2) with µ = 2−5, 2−2, 21, 24 and σ = 2−5, 2−2, 21, 24 respectively. We stop the training once the difference of loss between two consecutive steps |Ln(w(K+1))−Ln(w(K))| < 10−8. Then len(w(0),∞) is approximated by ∑K k=1 ∥w(k) − w(k−1)∥. For each pair of µ and σ, we record the length len(w(0),∞), the training error after convergence and the test error on the convergence point. Random feature model. In this experiment, the model that we consider is a two-layer ReLU neural network w⊤2 ϕ(W1x). Here ϕ is the ReLU function, W1 ∈ R200×200, w2 ∈ R200, We only train the last layer w2, and thus this can be viewed as a random feature model with features extracted by ϕ(W1x). The data set consists of 130 data points {(xi, yi)}130i=1 ⊆ R200 × R. The inputs xi(∀i ∈ [130]) are uniformly drawn from the 200-dimensional unit sphere. All labels yi(∀i ∈ [130]) are generated by a teacher network ŵ⊤2 ϕ(Ŵ1xi) with the same architecture for some ŵ2, Ŵ1. 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(0)2 are initialized i.i.d. from N (µ, σ2) with µ = −5,−2, 1, 4 and σ = 2−5, 2−2, 21, 24 respectively. We stop the training once the difference of loss between two consecutive steps is less than 10−8. For each pair of µ and σ, we use the same method as on linear regression to approximate the trajectory length. Then we 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, 3 and 4 correspond to step size η = 0.01, 0.1, 0.5 respectively. We observe that the optimization path lengths are nearly the same for both small learning rate and moderate learning rate, and the numerical results are associate with our theory.
  A.2 MNIST CLASSIFICATION
  In this subsection, we calculate the trajectory length on the MNIST classification problem to show the relation between optimization and generalization under different initializations.
  Experiment settings. In this experiment, we train a 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 to train the model. Parameters of the hidden layer are initialized by standard random initialization method in Pytorch, and the parameters of the top layer are initialized i.i.d. from Gaussian distribution N (µ, σ2) with µ = 2−5, 20, 25 and σ = 2−5, 2−2, 21, 24 respectively. During training the model, we reduce the learning rate by a 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 σ, we calculate the trajectory length by ∑K k=1
  ∥∥w(k) − w(k−1)∥∥. We plot the relation between optimization and generalization in terms of the trajectory length in Figure 5.
  From this figure, we can see that for different random initializations, short optimization paths is 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.
sections.heading: B PROOF OF THEOREM 1
sections.text: In this section we will prove Theorem 1, our proof is based on the next lemma, showing that the gradient flow trajectory is always inside Sn. Lemma B.1. For any initialization w(0), if Ln(w) satisfies Uniform-LGI on a closed set Sn ⊇
  B ( w(0), rn(w (0)) ) with constants cn, θn, where rn(w(0)) = (Ln(w(0))−minw Ln(w)) 1−θn
  cn(1−θn) , then
  w(t) ∈ Sn, ∀t ∈ [0,∞).
  Proof. Let
  T = inf{t ≥ 0, w(t) /∈ Sn},
  then it is sufficient to prove that T = ∞. Otherwise, if T < ∞, then by the continuity of the curve {w(t)}t≥0, we know that w(T ) is in the boundary of Sn, therefore
  len(w(0), T ) ≥ d(w(0), ∂Sn) ≥ rn(w(0)). (10)
  Now we consider the following two cases.
  Case (i). Ln(w(T )) = minw Ln(w). Since Ln(w(t)) is non-increasing, we have Ln(w(t)) = minw Ln(w) and w(t) = w(T ) for t ≥ T . Notice that Sn is a closed set, thus w(t) ∈ Sn for t ∈ [0, T ], meaning that T = ∞, which contradicts with T < ∞.
  Case (ii). Ln(w(T )) > minw Ln(w). By chain rule, we have for all t ∈ [0, T ],
  dLn(w(t)) dt =
  〈 ∇Ln(w(t)), dw(t)
  dt 〉 = − ∥∥∥∇Ln(w(t))∥∥∥∥∥∥∥dw(t)dt ∥∥∥∥
  ≤ −cn ( Ln(w(t))−min
  w L(w) )θn ∥∥∥∥dw(t)dt ∥∥∥∥ .
  Then we can bound the trajectory length len(w(0), T ) as
  len(w(0), T ) = ∫ T 0 ∥∥∥∥dw(t)dt ∥∥∥∥ dt
  ≤ ∫ T 0 − 1 cn ( Ln(w(t))−min w L(w) )−θn dLn(w(t))
  = 1
  cn(1− θn)
  [( Ln(w(0))−min
  w L(w)
  )1−θn − ( Ln(w(T ))−min
  w L(w) )1−θn] < rn(w
  (0)), (11)
  which contradicts with (10).
  Now we begin to prove Theorem 1.
  Proof. By Lemma B.1, we know that Ln(w(t)) satisfies Uniform-LGI for all t ∈ [0,∞). Then by the proof of Lemma B.1, we have ∀t ∈ [0,∞),
  len(w(0), t) ≤ 1 cn(1− θn)
  [( Ln(w(0))−min
  w L(w)
  )1−θn − ( Ln(w(t))−min
  w L(w)
  )1−θn] .
  (12)
  For the convergence rate, note that d ( Ln(w(t))−minw L(w) ) dt = 〈 ∇Ln(w(t)), dw(t) dt 〉 = −
  ∥∥∥∇Ln(w(t))∥∥∥2 ≤ −c2n ( Ln(w(t))−min
  w L(w)
  )2θn .
  (13)
  Therefore ( Ln(w(t))−min
  w L(w)
  )−2θn d ( Ln(w(t))−min
  w L(w)
  ) ≤ −c2ndt.
  Integrating on both sides of the equation, we can get ∀t ∈ [0,∞), when θn = 12 ,
  Ln(w(t))−min w
  Ln(w) ≤ e−c 2 nt ( Ln(w(0))−min
  w Ln(w)
  ) ; (14)
  when 12 < θn < 1,
  Ln(w(t))−min w
  Ln(w) ≤ (1 +Mt)−1/(2θn−1) ( Ln(w(0))−min
  w Ln(w)
  ) , (15)
  where M = c2n(2θn − 1) ( Ln(w(0))−minw Ln(w) )2θn−1. Taking the limit on both sides of (14) and (15), since w(∞) is the limit of w(t), we have
  Ln(w(∞)) = min w Ln(w).
  Hence w(∞) is a global minimum. Taking the limit on both sides of (12), we get
  len(w(0),∞) ≤ rn(w(0)).
  This completes the proof.
sections.heading: C PROOF OF THEOREM 2
sections.text: In this section, we will prove Theorem 2. This proof is based on the Rademacher complexity theory and the covering number of ℓ2 balls. Now we introduce some known technical lemmas that are used to build our proof.
  The first lemma gives a generalization bound of a function class based on the Rademacher complexity, which is proved in (Mohri et al., 2018). Lemma C.1. Consider a family of functions F mapping from Z to [a, b]. Let D denote the distribution according to which samples are drawn. Then for any δ > 0, with probability at least 1− δ over the draw of an i.i.d. sample S = {z1, . . . , zn} of size n, the following holds for all f ∈ F:
  Ez∼D [f(z)]− 1
  n n∑ i=1 f(zi) ≤ 2RS(F) + 3(b− a) √ log(2/δ) 2n ,
  where RS(F) is the empirical Rademacher complexity with respect to the sample S, defined as:
  RS(F) = Eσ [ sup f∈F 1 n n∑ i=1 σif(zi) ] .
  Here {σi}ni=1 are i.i.d. random variables drawn from U{−1, 1}.
  In the next lemma, we prove a shifted version of the Ledoux-Talagrand contraction inequality (Ledoux & Talagrand, 2013), which is useful to bound the length-based Rademacher complexity.
  Lemma C.2. Let g : R −→ R be a convex and increasing function. Let ϕi : R −→ R be L-Lipschitz functions, then for any bounded set T ⊂ R and any t(0) ∈ R, we have
  Eσ g  sup (t−t(0))∈T n∑ i=1 σi ( ϕi(ti)− ϕi ( t (0) i )) ≤ Eσ g L sup (t−t(0))∈T n∑ i=1 σi ( ti − t(0)i ) , and
  Eσ  sup (t−t(0))∈T ∣∣∣∣∣ n∑ i=1 σi ( ϕi(ti)− ϕi ( t (0) i ))∣∣∣∣∣  ≤ 2LEσ  sup (t−t(0))∈T ∣∣∣∣∣ n∑ i=1 σi ( ti − t(0)i )∣∣∣∣∣  .
  The special case for t(0) = 0 corresponds to the original Ledoux-Talagrand contraction inequality. Here we prove a shifted version.
  Proof. First notice that
  Eσ g  sup (t−t(0))∈T n∑ i=1 σi ( ϕi(ti)− ϕi ( t (0) i )) = Eσ1,...,σn−1 Eσn g  sup (t−t(0))∈T n∑ i=1 σi ( ϕi(ti)− ϕi ( t (0) i )) . Let un−1(t) = ∑n−1 i=1 σi ( ϕi(ti)− ϕi ( t (0) i )) , then
  Eσn g  sup (t−t(0))∈T n∑ i=1 σi ( ϕi(ti)− ϕi ( t (0) i )) = 1
  2 g  sup (t−t(0))∈T un−1(t) + ( ϕn(tn)− ϕn ( t(0)n ))+ 1 2 g  sup (t−t(0))∈T un−1(t)− ( ϕn(tn)− ϕn ( t(0)n )) . Suppose that the above two suprema can be reached at t′ and t̃ respectively, i.e.,
  sup (t−t(0))∈T
  un−1(t) + ( ϕn(tn)− ϕn ( t(0)n )) = un−1 (t ′) + ( ϕn (t ′ n)− ϕn ( t(0)n )) ;
  sup (t−t(0))∈T
  un−1(t)− ( ϕn(tn)− ϕn ( t(0)n )) = un−1 ( t̃ ) − ( ϕn ( t̃n ) − ϕn ( t(0)n )) .
  Otherwise we add an arbitrary positive number ε in the above equations. Therefore,
  Eσn g  sup (t−t(0))∈T n∑ i=1 σi ( ϕi(ti)− ϕi ( t (0) i )) = 1
  2
  [ g ( un−1 (t ′) + ( ϕn (t ′ n)− ϕn ( t(0)n )))] + 1
  2
  [ g ( un−1 ( t̃ ) − ( ϕn ( t̃n ) − ϕn ( t(0)n )))] .
  Without loss of generality, we assume
  un−1 (t ′) + ( ϕn (t ′ n)− ϕn ( t(0)n )) ≥ un−1 ( t̃ ) + ( ϕn ( t̃n ) − ϕn ( t(0)n )) ;
  un−1 ( t̃ ) − ( ϕn ( t̃n ) − ϕn ( t(0)n )) ≥ un−1 (t′)− ( ϕn (t ′ n)− ϕn ( t(0)n )) .
  (16)
  For the other cases, the method remains the same. We set a = un−1 ( t̃ ) − ( ϕn ( t̃n ) − ϕn ( t(0)n )) ,
  b = un−1 ( t̃ ) − L ( t̃n − t(0)n ) ,
  a′ = un−1 (t ′) + L ( t′n − t(0)n ) ,
  b′ = un−1 (t ′) + ( ϕn (t ′ n)− ϕn ( t(0)n )) .
  Now our goal is to prove: g(a)− g(b) ≤ g (a′)− g (b′) . (17)
  Considering the following four cases:
  1. t′n ≥ t (0) n and t̃n ≥ t(0)n . By the Lipschitzness of ϕn and equation (16) we know a ≥ b, b′ ≥ b,
  and (a− b)− (a′ − b′) = ϕn (t′n)− ϕn ( t̃n ) − L ( t′n − t̃n ) .
  If t′n ≥ t̃n, we can get a − b ≤ a′ − b′. By the fact that g is convex and increasing, we have g(y + x)− g(x) is increasing in y for every x ≥ 0. Hence for x = a− b,
  g(a)− g(b) = g(b+ x)− g(b) ≤ g (b′ + x)− g(b′) ≤ g (a′)− g (b′) .
  If t′n < t̃n, we change ϕn into −ϕn and switch t′ and t̃, and the proof is similar.
  2. t′n ≤ t (0) n and t̃n ≤ t(0)n . Similarly, by changing the signs we can get the same result.
  3. t′n ≥ t (0) n and t̃n ≤ t(0)n . For this case we have a ≤ b and b′ ≤ a′, so g(a)+ g (b′) ≤ g(b)+ g (a′).
  4. t′n ≤ t (0) n and t̃n ≥ t(0)n . For this case we can change ϕn to −ϕn, then we have a ≥ b and a′ ≤ b′,
  and finally we get g(a) + g (b′) ≤ g(b) + g (a′).
  Thus equation (17) yields that
  Eσn g  sup (t−t(0))∈T n∑ i=1 σi ( ϕi(ti)− ϕi ( t (0) i )) = 1
  2
  [ g ( un−1 (t ′) + ( ϕn (t ′ n)− ϕn ( t(0)n )))] + 1
  2
  [ g ( un−1 ( t̃ ) − ( ϕn ( t̃n ) − ϕn ( t(0)n )))] ≤1 2 [ g ( un−1 (t ′) + L ( t′n − t(0)n ))] + 1 2 [ g ( un−1 ( t̃ ) − L ( t̃n − t(0)n
  ))] ≤1 2 g  sup (t−t(0))∈T un−1 (t) + L ( tn − t(0)n )+ 1 2 g  sup (t−t(0))∈T un−1 (t)− L ( tn − t(0)n
  ) =Eσn g  sup (t−t(0))∈T un−1 (t) + σnL ( tn − t(0)n )
  Applying the same method to σn−1, . . . , σ1 successively, we obtain the first inequality
  Eσ g  sup (t−t(0))∈T n∑ i=1 σi ( ϕi(ti)− ϕi ( t (0) i )) ≤ Eσ g L sup (t−t(0))∈T n∑ i=1 σi ( ti − t(0)i ) . For the second inequality, since |x| = [x]+ + [x]− with [x]+ = max(0, x) and [x]− = max(0,−x),
  Eσ  sup (t−t(0))∈T ∣∣∣∣∣ n∑ i=1 σi ( ϕi(ti)− ϕi ( t (0) i ))∣∣∣∣∣ 
  ≤Eσ  sup (t−t(0))∈T [ n∑ i=1 σi ( ϕi(ti)− ϕi ( t (0) i ))] + + Eσ  sup (t−t(0))∈T [ n∑ i=1 σi ( ϕi(ti)− ϕi ( t (0) i ))] −  =2Eσ  sup (t−t(0))∈T [ n∑ i=1 σi ( ϕi(ti)− ϕi ( t (0) i ))] +
   , where the last equality is by [−x]− = [x]+ and σ has the same distribution with −σ. A simple fact is that
  sup (t−t(0))∈T
  [ n∑
  i=1
  σi ( ϕi(ti)− ϕi ( t (0) i ))] + =  sup (t−t(0))∈T n∑ i=1 σi ( ϕi(ti)− ϕi ( t (0) i )) + .
  Since max(0, x) is convex and increasing, then by the first inequality we have
  Eσ  sup (t−t(0))∈T [ n∑ i=1 σi ( ϕi(ti)− ϕi ( t (0) i ))] +  = Eσ  sup (t−t(0))∈T n∑ i=1 σi ( ϕi(ti)− ϕi ( t (0) i )) +  ≤ Eσ L sup (t−t(0))∈T n∑ i=1 σi ( ti − t(0)i ) +
   ≤ LEσ  sup (t−t(0))∈T ∣∣∣∣∣ n∑ i=1 σi ( ti − t(0)i )∣∣∣∣∣ 
  This completes the proof.
  Now we apply Lemma C.2 to bound the empirical Rademacher complexity of an element-wise distance constrained function class. In the following lemma, all the notations are consistent with Theorem 2 unless stated otherwise.
  Lemma C.3. Given a function class Fa,b := {x 7→ f(w, x) : w ∈ Sa,b} and sample S = {x1, . . . , xn} with ∥xi∥ = 1 for all i ∈ [n], then we have
  RS(Fa,b) ≤
  √ ∥a∥2 + ∥b∥2
  n ∥LΨ(Sa,b)∥ .
  Proof. By definition,
  nRS(Fa,b) = Eσ [ sup
  w∈Sa,b n∑ i=1 σif(w, xi)
  ]
  = Eσ [ sup
  w∈Sa,b n∑ i=1 σif(w, xi)
  ] − Eσ [ n∑
  i=1
  σif(0, xi)
  ]
  = Eσ [ sup
  w∈Sa,b n∑ i=1 σi (f(w, xi)− f(0, xi))
  ] .
  Now we decompose the term f(w, xi)− f(0, xi) as: f(w, xi)− f(0, xi)
  =Ψ ( x⊤i α1, . . . , x ⊤ i αp, β1, . . . , βq ) −Ψ(0, . . . , 0, 0, . . . , 0)
  =(Ψ(x⊤i α1,...,x ⊤ i αp,β1,...,βq)−Ψ(0,...,x ⊤ i αp,β1,...,βq))+(Ψ(0,...,x ⊤ i αp,β1,...,βq)−Ψ(0,0,...,x ⊤ i αp,β1,...,βq))
  + · · ·+ (Ψ (0, . . . , 0, 0, . . . , 0, βq)−Ψ(0, . . . , 0, 0, . . . , 0)) .
  Then by the above decomposition and Lemma C.2, we have
  Eσ [ sup
  w∈Sa,b n∑ i=1 σi (f(w, xi)− f(0, xi))
  ]
  ≤L(1)Ψ (Sa,b)Eσ
  [ sup
  w∈Sa,b n∑ i=1 σix ⊤ i α1 ] + · · ·+ L(p+q)Ψ (Sa,b)Eσ [ sup w∈Sa,b n∑ i=1 σiβq ] .
  Notice that
  Eσ [ sup
  w∈Sa,b n∑ i=1 σix ⊤ i α1
  ] = Eσ [ sup
  ∥α1∥≤a1 n∑ i=1 σix ⊤ i α1
  ]
  ≤ a1Eσ [∥∥∥∥∥ n∑
  i=1
  σixi ∥∥∥∥∥ ]
  ≤ a1 √√√√√Eσ ∥∥∥∥∥ n∑ i=1 σixi ∥∥∥∥∥ 2  = a1 √ n.
  And
  Eσ [ sup
  w∈Sa,b n∑ i=1 σiβq
  ] = Eσ [ sup
  |βq|≤bq n∑ i=1 σiβq
  ]
  ≤ bqEσ [∣∣∣∣∣ n∑
  i=1
  σi ∣∣∣∣∣ ]
  ≤ bq √√√√√Eσ ∣∣∣∣∣ n∑ i=1 σi ∣∣∣∣∣ 2  = bq √ n.
  Therefore, by the Cauchy-Schwarz inequality, we can get
  Eσ [ sup
  w∈Sa,b n∑ i=1 σi (f(w, xi)− f(0, xi)) ] ≤ L(1)Ψ (Sa,b)a1 √ n+ · · ·+ L(p+q)Ψ (Sa,b)bq √ n
  ≤ √ n ( ∥a∥2 + ∥b∥2 ) ∥LΨ(Sa,b)∥ .
  Finally, we have
  RS(Fa,b) ≤
  √ ∥a∥2 + ∥b∥2
  n ∥LΨ(Sa,b)∥ .
  Lemma C.3 gives an upper bound of the Rademacher complexity based on the element-wise distance. Notice that ∥∥w(∞)∥∥ ≤ ∥∥w(0)∥∥+ len(w(0),∞). To obtain a length-based generalization bound, we consider to use Sa,b to cover the length-constrained space {w : ∥w∥ ≤ R}, and then taking a union bound. For the ℓ2 ball covering number, we use the following result from (Neyshabur et al., 2019, Lemma 11). Lemma C.4. Given any ϵ,D, β > 0, consider the set SDβ = { x ∈ RD : ∥x∥ ≤ β } . Then there exist
  N sets {Ti}Ni=1 of the form Ti = { x ∈ RD : |xj | ≤ αij ,∀j ∈ [D] } such that SDβ ⊆ ⋃N i=1 Ti and∥∥αi∥∥ ≤ β(1 + ϵ),∀i ∈ [N ] where N = (K+D−1D−1 ) and
  K =
  ⌈ D
  (1 + ϵ)2 − 1
  ⌉ .
  Lemma C.5. For any two positive integers n, k with n ≥ k, we have( n
  k ) ≤ (en k )k .
  Proof. Note that ( n
  k
  ) =
  n! k!(n− k)! ≤ n
  k
  k! ≤ ek (n k )k .
  The last step is by
  ek = ∞∑ i=0 ki i! ≥ k k k! .
  Now combining Lemma C.1, C.3, C.4 and C.5, we are ready to prove Theorem 2.
  Proof of Theorem 2. First we apply Lemma C.4 with ϵ = √ 2− 1, D = p+ q, and β = Mδ +Rn,δ ,
  then there exist N sets Sak,bk such that SDβ ⊆ ⋃N k=1 Sak,bk and √ ∥ak∥2 + ∥bk∥2 ≤ √ 2β, with
  N = ( 2D−1 D−1 ) .
  Therefore, for each parameter space Sak,bk , by Lemma C.3 we have RS(Fak,bk) ≤ √ 2 n β ∥∥LΨ(Sak,bk)∥∥ .
  Notice that the local Lipschitz constant of ℓ in Sak,bk is Lℓ(Sak,bk). Hence, by Lemma C.1 and the Ledoux-Talagrand contraction inequality, for any δ > 0, with probability at least 1− δ/N over the training sample, the following holds for all w ∈ Sak,bk :
  LD(w) ≤ Ln(w) + 2 √ 2βLℓ(Sak,bk) ∥∥LΨ(Sak,bk)∥∥√ n + 3Mβ √ log(2N/δ) 2n ,
  where Mβ = sup∥ak∥2+∥bk∥2≤2β2 supw∈Sak,bk ,∥x∥≤1,|y|≤1 ℓ (f(w, x), y).
  Since w(∞) ∈ SDβ ⊆ ⋃N
  k=1 Sak,bk , by taking the union bound over all sets Sak,bk , we can get with probability at least 1− δ over the initialization I the training sample,
  LD(w(∞)) ≤ Ln(w(∞)) + sup ∥a∥2+∥b∥2≤2β2
  2 √ 2βLℓ(Sa,b) ∥LΨ(Sa,b)∥√
  n + 3Ma,b
  √ log(2N/δ)
  2n .
  Theorem 1 already showed that Ln(w(∞)) = minw Ln(w). Thus it remains to bound the term logN . For D = 1, N = 1. For D ≥ 2, by Lemma C.5,
  logN ≤ (D − 1) log ( e(2D − 1) D − 1 ) < 2.1(D − 1) < 3D = 3(p+ q).
  Finally, let R = √ 2β, we complete the proof of Theorem 2.
  C.1 ADDITIONAL OF RESULTS FOR THE GENERALIZATION DURING TRAINING THE MODEL
  Theorem 2 gives a length-based 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 1.
  The approach is to give a generalization bound for early stopping when the loss value first reaches ε ≥ 0. The idea is that, when there exists T > 0 such that Ln(wT ) = ε, then by the inequality (11) in the proof of Lemma B.1, we can get an upper bound for the length len(w(0), T ) in terms of Ln(w(0)),minw L(w), ε, cn, θn. Finally, we can get a generalization bound by our new length estimate.
  To get a clean expression for the generalization bound, we assume the optimal value of the empirical loss function Ln(w) is zero. Then the rigorous statement is stated as follows: Corollary 1. Consider a training criterion of early stopping that the training is stopped once the empirical loss value first reaches ε ≥ 0. Then for any given ε ≥ 0, under the notations and conditions in Theorem 1, suppose that for any δ ∈ (0, 1), there exists rn,δ such that rn(w(0)) ≤ rn,δ with probability at least 1 − δ over the initialization and the training samples. Then, we have with probability at least 1− δ over initialization and the training samples, the generalization error for the stopping parameter w is given by:
  LD(w) ≤ ε+ sup ∥a∥2+∥b∥2≤r2ε,n,δ
  2rε,n,δLℓ(Sa,b) ∥LΨ(Sa,b)∥√ n +3Ma,b
  √ 3(p+ q) + log(2/δ)
  2n , (18)
  where rε,n,δ = √ 2 ( Mδ + rn,δ − ε 1−θn
  cn(1−θn)
  ) .
  Remark 2. Corollary 1 shows a trade-off between ε and the term rε,n,δ. The case for ε = 0 corresponds to the combining results of Theorem 2 and Theorem 1.
  Proof. The proof is straightforward. Notice that by the inequality (11), we can bound the length len(w(0), w) as
  len(w(0), w) ≤ rn(w(0))− ε1−θn
  cn(1− θn) ,
  where rn(w(0)) is specified in equation (2). Then by the same argument in the proof of Theorem 2, we may directly replace rn(w(0)) with rn(w(0))− ε 1−θn
  cn(1−θn) to get the desired bound.
sections.heading: D PROOFS FOR SECTION 4
sections.text: In this section, our goal is to prove all the theorems in Section 4. A crucial part of the proofs is the spectral analysis of the random matrix X . Therefore, we start with introducing the non-asymptotic results of λmax(XX⊤) and λmin(XX⊤) from (Rudelson & Vershynin, 2010). The first result is from (Rudelson & Vershynin, 2010, Proposition 2.4), characterizing the nonasymptotic behavior of the largest singular value of subgaussian matrices.
  Lemma D.1. Let A be an N×n random matrix whose entries are independent mean zero subgaussian random variables whose subgaussian moments are bounded by 1. Then for every t ≥ 0, with probability at least 1− 2e−ct2 over the randomness of the entries,√
  λmax(AA⊤) ≤ C( √ N + √ n) + t,
  where c 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 nonasymptotic behavior of the smallest singular value of subgaussian matrices.
  Lemma D.2. Let A be an N × n random matrix whose entries are independent and identically distributed subgaussian random variables with zero mean and unit variance. If N > n, then for every ε > 0, with probability at least 1− (C1ε)N−n+1 − cN1 over the randomness of the entries,√
  λmin(A⊤A) ≥ ε( √ N − √ n− 1),
  where C1 > 0 and c1 ∈ (0, 1) depend only on the subgaussian moment of the entries.
  D.1 PROOF OF THEOREM 3
  In this section, we will prove Theorem 3 based on the three steps in our framework. All the notations are consistent with Theorem 3 unless stated otherwise.
  Proof of Theorem 3. First, we prove the result for Step 1.
  For a vector a = (a1, . . . , an)⊤ ∈ Rn, we use a◦m to denote the element-wise power, i.e., a◦m = (am1 , . . . , a m n ) ⊤. For the ℓp linear regression loss function Ln(w), notice that
  ∇Ln(w) = 1
  n n∑ i=1 ( w⊤xi − yi )p−1 xi = 1 n X⊤ (Xw − Y)◦(p−1) .
  Then since X has full row rank, we have ∀w ∈ Rd,
  ∥∇Ln(w)∥ = 1
  n ∥∥∥X⊤ (Xw − Y)◦(p−1)∥∥∥ ≥ √ λmin(XX⊤)
  n ∥∥∥(Xw − Y)◦(p−1)∥∥∥ = √ λmin(XX⊤)
  n ∥Xw − Y∥p−12p−2 ≥ √ λmin(XX⊤)
  n ∥Xw − Y∥p−1p · n 1/p−1/2 = p1−1/p √
  λmin(XX⊤) n Ln(w)1−1/p.
  Therefore,
  cn = p 1−1/p
  √ λmin(XX⊤)
  n , θn = 1− 1/p.
  For Step 2, note that minw Ln(w) = 0, then the result can be proved by directly plugging cn and θn into Theorem 1.
  Next, we prove the result for Step 3. By Theorem 1 and the property of the target function, we have for any w(0) that satisfies ∥∥w(0)∥∥ 2 ≤ c0,
  rn(w (0)) =
  √ n ( pLn(w(0)) )1/p√ λmin(XX⊤)
  = n1/2−1/p ∥∥Xw(0) − Y∥∥ p√
  λmin(XX⊤) ≤ n1/2−1/p ∥∥Xw(0) − Y∥∥
  2√ λmin(XX⊤)
  ≤ n1/2−1/p √
  λmax(XX⊤) λmin(XX⊤) (c0 + c ∗) .
  Now we apply Lemma D.1 with A = X and t = √
  log(4/δ) c , then we have with probability at least
  1− δ/2 over the samples,√ λmax(XX⊤) ≤ C( √ n+ √ d) + √ log(4/δ)
  c , (19)
  where c and C are two positive constants that depend only on the subgaussian moment of the entries.
  Similarly, let τ = c1 ∈ (0, 1), ε = τ/C1 > 0, then Lemma D.2 implies that with probability at least 1− τd−n+1 − τd over the samples,√
  λmin(XX⊤) ≥ τ C1 ( √ d− √ n− 1), (20)
  where C1 > 0 and τ ∈ (0, 1) depend only on the subgaussian moment of the entries. Taking the union bound, we have with probability at least 1−δ/2−τd−n+1−τd over the initialization and the training samples,
  rn(w (0))√ n ≤ n−1/p (c0 + c∗) C(
  √ n+ √ d) +
  √ log(4/δ)
  c
  τ C1
  ( √ d− √ n− 1)
  ≤ n−1/p (c0 + c∗) C (√ n d + 1 ) + √ log(4/δ) cd
  τ C1
  ( 1− √ n−1 d ) ≤ n−1/p (c0 + c∗) CC1( √ γ1 + 1) + C1 √ γ1 log(4/δ) cn
  τ(1−√γ1)
  ≤ O ( n−1/p + n−1/p √ log(1/δ)
  n
  ) .
  (21)
  Recall for the linear regression model (5), f(w, x) = w⊤x. Thus Ψ(x) = x is an identity function with p = 1, q = 0, and ∥LΨ(Sa,b)∥ = 1 for any a, b. Since the loss function ℓ̃ is bounded by 1 and 1-Lipschitz, we know that Lℓ(Sa,b) = MR = 1 for any a and b. Finally by Theorem 2 and ℓ̃(y, y) = 0, we have with probability at least 1− δ/2 over the samples,
  E(x,y)∼D [ ℓ̃ ( f(w(∞), x), y )] ≤ 2 √ 2(rn(w
  (0)) + c0)√ n + 3
  √ 3 + log(4/δ)
  2n .
  Combining the inequality (21), we have with probability at least 1− δ − τd−n+1 − τd over training samples,
  E(x,y)∼D [ ℓ̃ ( f(w(∞), x), y )] ≤ O ( n−1/p ) +O
  (√ log(1/δ)
  n
  ) .
  This completes the proof of Theorem 3.
  D.2 PROOF OF THEOREM 4
  In this section, we will prove Theorem 4. First, we present some useful lemmas for proving our results, and then we give the proofs of Theorem 4 for the RBF kernel and the inner product kernel separately.
  For the RBF kernel k(x, y) = ϱ (∥y − x∥), the following two lemmas give non-asymptotic bounds for λmax(k(X ,X )) and λmin(k(X ,X )) based on the separation distance SD of X . The first lemma is from (Diederichs & Iske, 2019, Lemma 3.1), providing an upper bound for λmax(k(X ,X )). Lemma D.3. For the RBF kernel, if ϱ : R≥0 −→ R≥0 is a decreasing function, then
  λmax(k(X ,X )) ≤ ϱ(0) + 3d ∞∑ t=1 (t+ 2)d−1ϱ(t · SD), (22)
  and the sum of the infinite series in equation (22) is finite if and only if ϱ (∥x∥) ∈ L1(Rd).
  The next lemma is from (Wendland, 2004, Theorem 12.3), giving a lower bound for λmin(k(X ,X )). Lemma D.4. Suppose that k is a positive-definite RBF kernel. If ϱ (∥x∥) ∈ L1(Rd), one can define the Fourier transform of ϱ as ϱ̂(ω) := (2π)−d/2 ∫ Rd ϱ(ω)e
  −ix⊤ωdω. With a decreasing function ϱ0(M) and two constants Md, Cd defined as
  ϱ0(M) := inf ∥x∥≤2M
  ϱ̂(x), Md = 6.38d, Cd = 1
  2Γ(d/2 + 1) ( Md 23/2 )d ,
  where Γ is the gamma function. Then a lower bound on λmin(k(X ,X )) is given by
  λmin(k(X ,X )) ≥ Cd · ϱ0 (Md/SD) · SD−d.
  For the inner product kernel k(x, y) = ϱ (
  x⊤y d
  ) , it is shown in (El Karoui et al., 2010) that the
  kernel matrix k(X ,X ) can be approximated by the linear combination of all-ones matrix 11⊤, sample covariance matrix XX⊤ and identity matrix. To obtain non-asymptotic results on the spectra of the kernel matrix k(X ,X ), we borrow the technique from (Liang & Rakhlin, 2020, Proposition A.2), and show the result for subgaussian entries in the next lemma.
  Lemma D.5. For the inner product kernel, suppose that the entries of X are i.i.d. subgaussian random variables with zero mean and unit variance, then with probability at least 1− δ − d−2 over the entries, ∥∥k(X ,X )− klin(X ,X )∥∥ ≤ d−1/2 (δ−1/2 + log0.51 d) , where klin(X ,X ) is defined as
  klin(X ,X ) := ( ϱ(0) + ϱ′′(0)
  d
  ) 11⊤ + ϱ′(0) XX⊤
  d + (ϱ(1)− ϱ(0)− ϱ′(0)) In×n.
  Proof. Note that the sample covariance matrix Σd = Id×d, 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 ∈ Rn×n are two symmetric matrices, then we have
  λmin(A+B) ≥ λmin(A) + λmin(B).
  Proof. Note that for any x ∈ Rn with ∥x∥ = 1,
  x⊤(A+B)x = x⊤Ax+ x⊤Bx ≥ λmin(A) + λmin(B).
  By definition, we have
  λmin(A+B) = inf ∥x∥=1
  x⊤(A+B)x ≥ λmin(A) + λmin(B),
  which completes the proof.
  Now we are ready to prove Theorem 4.
  Proof of Theorem 4. For Step 1. Notice that ∀w ∈ Rs,
  ∥∇Ln(w)∥ = 1
  n ∥∥∥φ(X )⊤ (φ(X )w − Y)◦(p−1)∥∥∥ ≥ √ λmin(φ(X )φ(X )⊤)
  n ∥∥∥(φ(X )w − Y)◦(p−1)∥∥∥ = √ λmin(k(X ,X ))
  n ∥φ(X )w − Y∥p−12p−2 ≥ √ λmin(k(X ,X ))
  n ∥φ(X )w − Y∥p−1p · n 1/p−1/2 = p1−1/p √
  λmin(k(X ,X )) n Ln(w)1−1/p.
  Therefore, Ln(w) satisfies the Uniform-LGI globally on Rs with
  cn = p 1−1/p
  √ λmin(k(X ,X ))
  n , θn = 1− 1/p.
  For Step 2. Since k is a positive-definite kernel, and θn = 1− 1/p, then minw Ln(w) = 0, thus by Theorem 1 we can directly get the result.
  The proof of Step 3 is two-sided. First, since ∀x ∈ X , ∥φ(x)∥ = √ k(x, x) ≤ 1, then the kernel regression model (7) can be viewed as ℓp linear regression on inputs φ(X ). Hence, Ψ is an identity function with p = 1, q = 0, and ∥LΨ(Sa,b)∥ = Lℓ(Sa,b) = MR = 1 for any a, b. This means that we only need to bound the term rn(w(0))/ √ n.
  By Theorem 1 and the property of the target function, for any w(0) that satisfies ∥∥w(0)∥∥
  2 ≤ c0, we
  have
  rn(w (0)) =
  √ n ( pLn(w(0)) )1/p√ λmin(k(X ,X ))
  = n1/2−1/p ∥∥φ(X )w(0) − Y∥∥ p√
  λmin(k(X ,X )) ≤ n1/2−1/p ∥∥φ(X )w(0) − Y∥∥
  2√ λmin(k(X ,X ))
  ≤ n1/2−1/p ∥∥φ(X )w(0)∥∥+ ∥Y∥√
  λmin(k(X ,X )) ≤ n1/2−1/p √
  λmax(k(X ,X )) λmin(k(X ,X )) (c0 + c ∗) .
  (23)
  Then for the RBF kernel, Lemma D.3 and Lemma D.4 indicate that there exists a positive constant C(ϱ, d, qmin, qmax) that only depends on ϱ, d, qmin, qmax such that
  λmax(k(X ,X )) λmin(k(X ,X )) ≤ C(ϱ, d, qmin, qmax), ∀n ≥ 1,
  which implies that for all initialization w(0),
  rn(w (0))√ n
  ≤ O ( n−1/p ) . (24)
  Therefore, by Theorem 2 and Lemma C.1, we have with probability at least 1 − δ over training samples,
  E(x,y)∼D [ ℓ̃ ( f(w(∞), x), y )] ≤ O ( n−1/p ) +O
  (√ log(1/δ)
  n
  ) ,
  which completes the proof for the RBF kernel.
  For the inner product kernel, to obtain an upper bound for λmax(k(X ,X ))λmin(k(X ,X )) , first notice that
  λmax(k(X ,X )) = ∥k(X ,X )∥ ≤ ∥∥klin(X ,X )∥∥+ ∥∥k(X ,X )− klin(X ,X )∥∥ . (25)
  By Lemma D.6, we can get
  λmin(k(X ,X )) ≥ λmin(klin(X ,X )) + λmin(k(X ,X )− klin(X ,X )) ≥ λmin(klin(X ,X ))− ∥∥k(X ,X )− klin(X ,X )∥∥ . (26) Under Assumption 2, Lemma D.5 implies that∥∥klin(X ,X )∥∥ ≤ ϱ′′(0)
  d ∥∥11⊤∥∥+ ϱ′(0) d ∥∥XX⊤∥∥+ (ϱ(1)− ϱ′(0)) ≤ nϱ ′′(0)
  d + ϱ′(0) λmax(XX⊤) d + (ϱ(1)− ϱ′(0))
  ≤ γ1ϱ′′(0) + ϱ′(0) λmax(XX⊤)
  d + (ϱ(1)− ϱ′(0)) ,
  and λmin(k lin(X ,X )) ≥ ϱ(1)− ϱ′(0) > 0.
  Thus, by equation (26) we have λmin(k(X ,X )) ≥ (ϱ(1)− ϱ′(0))− ∥∥k(X ,X )− klin(X ,X )∥∥ . (27)
  Under Assumption 1, by equation (19), we have with probability at least 1− δ/3 over the samples,
  λmax(XX⊤) d ≤
  ( C (√ n
  d + 1
  ) + √ log(6/δ)
  cd
  )2
  ≤ ( C ( √ γ1 + 1) + √ γ1 log(6/δ)
  cn
  )2 .
  Therefore, by equation (25), with probability at least 1− δ/3 over the samples,
  λmax(k(X ,X )) ≤ γ1ϱ′′(0)+ϱ′(0) ( C ( √ γ1 + 1) + √ γ1 log(6/δ)
  cn
  )2 +ϱ(1)−ϱ′(0)+
  ∥∥k(X ,X )− klin(X ,X )∥∥ . (28)
  By Lemma D.5, for large d and small δ such that d−1/2 (√ 3δ−1/2 + log0.51 d ) ≤ 0.5(ϱ(1)− ϱ′(0)), we have with probability at least 1− δ/3− d−2 over the entries,∥∥k(X ,X )− klin(X ,X )∥∥ ≤ 0.5(ϱ(1)− ϱ′(0)). Then equation (27) and (28) yields that with probability at least 1− 2δ/3− d−2 over the samples,
  λmin(k(X ,X )) ≥ 0.5(ϱ(1)− ϱ′(0)),
  λmax(k(X ,X )) ≤ γ1ϱ′′(0) + ϱ′(0) ( C ( √ γ1 + 1) + √ γ1 log(4/δ)
  cn
  )2 + 1.5(ϱ(1)− ϱ′(0)).
  Hence, by equation (23), with probability at least 1− 2δ/3− d−2 over the samples, we have
  rn(w (0))√ n ≤ O
  ( n−1/p + √ log(1/δ)
  n1/2+1/p
  ) . (29)
  Combining Theorem 2, we get with probability at least 1− δ − d−2 over the samples,
  E(x,y)∼D [ ℓ̃ ( f(w(∞), x), y )] ≤ O ( n−1/p ) +O
  (√ log(1/δ)
  n
  ) ,
  which completes the proof.
  D.3 PROOF OF THEOREM 5
  In this section, we will prove Theorem 5. We first introduce some important lemmas for proving our final results. Lemma D.7 shows that the smallest eigenvalue of the NTK matrix Θ(t) has a lower bounded given the overparameterization, by which we can prove the optimization result. In Lemma D.8, we show that the eigenvalues of the NTK matrix are related to the data covariance matrix. Then by combining Lemma D.11 and Lemma D.9 we can prove the generalization result.
  Lemma D.7. For any δ ∈ (0, 1), if m ≥ poly ( n, λ−1min(Θ̂), δ −1 )
  , then with probability at least 1− δ over the random initialization,
  λmin(Θ(t)) ≥ 1
  2 λmin(Θ̂), ∀t ≥ 0.
  Proof. The proof is the same as the proof of (Du et al., 2019, Lemma 3.4).
  Lemma D.8. λmin(Θ̂) ≥ λmin ( XX⊤ ) /4.
  Proof. Notice that for ReLU activation ϕ, a simple fact is that ϕ′(ax) = ϕ′(x) holds for any x ∈ R given that a > 0. Therefore,
  Θ̂ij = x ⊤ i xjEw∼N (0, 1d Id)
  [ ϕ′(w⊤xi)ϕ ′(w⊤xj) ]
  = x⊤i xjEw∼N (0,Id) [ ϕ′(w⊤xi)ϕ ′(w⊤xj) ] = x⊤i xj(π − arccos(x⊤i xj))
  2π
  = x⊤i xj 4 + x⊤i xj 2π arcsin(x⊤i xj) = x⊤i xj 4 + 1 2π ∞∑ k=0 (2k)! 4k(k!)2(2k + 1) (x⊤i xj) 2k+2.
  Then
  Θ̂ = XX⊤
  4 +
  1
  2π ∞∑ k=0
  (2k)!
  4k(k!)2(2k + 1)
  ( XX⊤ )◦(2k+2) = XX⊤
  4 +
  1
  2π ∞∑ k=0
  (2k)!
  4k(k!)2(2k + 1)
  ( (X⊤)⊙(2k+2) )⊤ (X⊤)⊙(2k+2),
  where ◦ is the element-wise product, and ⊙ is the Khatri-Rao product6. Since ( (X⊤)⊙(2k+2) )⊤ (X⊤)⊙(2k+2) is positive semidefinite, we have
  λmin(Θ̂) ≥ λmin ( XX⊤ ) /4,
  which completes the proof.
  In the next lemma, we adopt an inequality from (Montgomery-Smith, 1990).
  Lemma D.9. If {σi}ni=1 are i.i.d. drawn from U{−1, 1}, then for any x = (x1, . . . , xn)⊤ ∈ Rn, with probability at least 1− δ over σ,∣∣∣∣∣ n∑ i=1 σixi
  ∣∣∣∣∣ ≤√2 log(2/δ) ∥x∥ . The following lemma gives a sharp bound for a Chi-square variable, which is from (Laurent & Massart, 2000, Lemma 1).
  Lemma D.10. Let (Y1, . . . , YD) be i.i.d. Gaussian variables, with mean 0 and variance 1. Then with probability at least 1− δ over Y ,
  D∑ i=1 Y 2i ≤ D + 2
  √ D log ( 1
  δ
  ) + 2 log ( 1
  δ
  ) .
  The next lemma is quoted from (Arora et 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 R > 0, consider the following function class F = { x 7→ f(w, x) : ∥∥∥W1,r −W (0)1,r ∥∥∥ ≤ R(∀r ∈ [m]),∥∥∥W1 −W (0)1 ∥∥∥ F ≤ B } with W1,r ∈ Rd the r-th row of W1. Then for an i.i.d. sample S = {x1, . . . , xn} and every B > 0, with probability at least 1− δ over the random initialization, the empirical Rademacher complexity is bounded as:
  RS(F) ≤ B√ 2n
  ( 1 + ( 2 log(2/δ)
  m
  )1/4) + 2R2 √ md+R √ 2 log(2/δ).
  Now we are ready to prove Theorem 5.
  6For A = (a1, . . . , an) ∈ Rm×n, B = (b1, . . . , bn) ∈ Rp×n, then A⊙B = [a1⊗b1, . . . , an⊗bn], where ⊗ is the Kronecker product.
  Proof of Theorem 5. For Step 1. By Lemma D.7, if m ≥ poly ( n, λ−1min(Θ̂), δ −1 )
  , then with probability at least 1− δ over the random initialization,
  ∥∥∥∇Ln(w(t))∥∥∥ = 1 n ∥∥∥∥∥ n∑
  i=1
  (f(w, xi)− yi)∇f(w(t), xi) ∥∥∥∥∥ = 1
  n ∥∥∥∇f(w(t),X )⊤ (f(w(t),X )− Y)∥∥∥ = 1
  n
  √( f(w(t),X )− Y )⊤ ∇f(w(t),X )∇f(w(t),X )⊤ (f(w(t),X )− Y) ≥ √ 2λmin(Θ(t))
  n
  √ Ln(w(t))
  ≥
  √ λmin(Θ̂)
  n
  √ Ln(w(t))
  holds for any t ≥ 0, which means that Ln(w(t)) satisfies the Uniform-LGI for any t ≥ 0 with
  cn = √ λmin(Θ̂)/n, θn = 1/2.
  For Step 2. By equation (13), we can directly get Ln(w(t)) converges to zero with a linear convergence rate:
  Ln(w(t)) ≤ exp ( −λmin(Θ̂)t/n ) Ln(w(0)).
  For Step 3. By equation (12) and Lemma D.8, the length len(w(0),∞) can be bounded as
  len(w(0),∞) ≤ rn(w(0)) = 2 √ nLn(w(0)) λmin(Θ̂) ≤ 4 √ nLn(w(0)) λmin(XX⊤) .
  By the property of the target function, we have
  √ nLn(w(0)) = √√√√1 2 n∑ i=1 ( 1√ m w⊤2 ϕ(W (0) 1 xi)− yi )2
  ≤ √√√√ n∑ i=1 ( 1√ m w⊤2 ϕ(W (0) 1 xi) )2 + y2i
  ≤ √√√√ n∑ i=1 ( 1√ m w⊤2 ϕ(W (0) 1 xi) )2 + √√√√ n∑ i=1 y2i
  ≤ √√√√ 1 m n∑ i=1 ( w⊤2 ϕ(W (0) 1 xi) )2 + c∗ √ λmax(XX⊤).
  Since the entries of w2 are drawn i.i.d. from U{−1, 1}, then by Lemma D.9, for each i ∈ [n], with probability at least 1− δ/6n over w2,(
  w⊤2 ϕ(W (0) 1 xi)
  )2 ≤ 2 log ( 12n
  δ
  )∥∥∥ϕ(W (0)1 xi)∥∥∥2 .
  Taking the union bound over all i = 1, 2, . . . , n, we have with probability at least 1 − δ over the random initialization,
  √√√√ 1 m n∑ i=1 ( w⊤2 ϕ(W (0) 1 xi) )2 ≤ √√√√2 log(12n/δ) m n∑ i=1 ∥∥∥ϕ(W (0)1 xi)∥∥∥2 = √ 2 log(12n/δ)
  m
  ∥∥∥ϕ(W (0)1 X⊤)∥∥∥ F
  ≤ √ 2 log(12n/δ)
  m
  ∥∥∥W (0)1 X⊤∥∥∥ F
  ≤ √ 2 log(12n/δ)
  m
  ∥∥∥W (0)1 ∥∥∥ F ∥X∥
  =
  √ 2 log(12n/δ)
  m
  ∥∥∥W (0)1 ∥∥∥ F √ λmax(XX⊤).
  (30)
  For the Gaussian random matrix W (0)1 ∼ N (0, 1d Im×d), by Lemma D.10, we have with probability at least 1− δ/6 over the random initialization,
  ∥∥∥W (0)1 ∥∥∥2 F
  m ≤ 1 + 2
  √ log(6/δ)
  md +
  2 log(6/δ)
  md . (31)
  Taking the union bound of equation (19), (20), (30) and (31), if m ≥ poly ( n, λ−1min(Θ̂), δ −1 ) , then with probability at least 1− τd−n+1 − τd − 5δ/6 over the samples and random initialization I,
  sup w(0)∈I,(x,y)∈D
  rn(w (0)) ≤ sup
  w(0)∈I,(x,y)∈D 4 √ nLn(w(0)) λmin(XX⊤)
  ≤ O  √√√√(1 +√ log(1/δ)
  md +
  log(1/δ)
  md
  ) log(n/δ) √ n+ √ d+ √ log(1/δ)√
  d− √ n− 1  ≤ O (√ log(n/δ) √ γ1 + 1 + √ log(1/δ)/n
  1−√γ1 ) ≤ O (√ log(n/δ) ) .
  Therefore, with probability at least 1−τd−n+1−τd−5δ/6 over the samples and random initialization,
  rn(w (0))√ n ≤ O
  (√ log(n/δ)
  n
  ) . (32)
  For the r-th row of W (t)1 , we begin to bound the distance ∥∥∥W (t)1,r −W (0)1,r ∥∥∥ for each r ∈ [m].
  Notice that ∥∥∥∥∥dW (t) 1,r dt ∥∥∥∥∥ = ∥∥∥∇W (t)1,rLn(w(t))∥∥∥ = ∥∥∥∥∥ 1n n∑
  i=1
  ( f(w(t), xi)− yi ) 1√ m w2,rϕ ′(W (t) 1,rxi)xi ∥∥∥∥∥ ≤ 1
  n √ m n∑ i=1 ∣∣∣f(w(t), xi)− yi∣∣∣ ≤ 1√
  nm ∥∥∥f(w(t),X )− Y∥∥∥ ≤ √
  2Ln(w(0)) m
  exp ( −λmin(Θ̂)t/2n ) .
  Hence,∥∥∥W (t)1,r −W (0)1,r ∥∥∥ ≤ ∫ t 0 ∥∥∥∥∥dW (s) 1,r ds ∥∥∥∥∥ ds ≤ 2nλmin(Θ̂) √ 2Ln(w(0)) m = √ 2n mλmin(Θ̂) rn(w (0)). Now we apply Lemma D.11 with B = rn(w(0)), R = supw(0)∈I,(x,y)∈D √ 2n
  mλmin(Θ̂) rn(w
  (0)), we
  get with probability at least 1− δ/12 over the random initalization,
  RS(F) ≤ B√ 2n
  ( 1 + ( 2 log(24/δ)
  m
  )1/4) + 2R2 √ md+R √ 2 log(24/δ).
  Then by equation (32), if m ≥ poly ( n, λ−1min(Θ̂), δ −1 )
  , then with probability at least 1− τd−n+1 − τd − 11δ/12 over the samples and random initialization,
  RS(F) ≤ O
  (√ log(n/δ)
  n
  ) .
  Finally, by Lemma C.1, we have with probability at least 1− τd−n+1 − τd − δ over the samples and random initialization,
  E(x,y)∼D [ ℓ̃ ( f(w(∞), x), y )] ≤ O
  (√ log(n/δ)
  n
  ) ,
  for some constant τ ∈ (0, 1) that depend only on the subgaussian moment of the entries. This completes the proof.