Sharp Generalization for Nonparametric Regression by Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate
Authors: Yingzhen Yang
Venue: ICML 2025 spotlightposter (2025)
Keywords: Nonparametric Regression
Over-Parameterized Neural Network
Gradient Descent
Minimax Optimal Rate
Primary area: deep_learning->theory
TL;DR: We show that an over-parameterized two-layer neural network trained by gradient descent (GD) exhibits minimax optimal convergence rates for nonparametric regression, and our results are distribution-free in spherical covariate.

Abstract: Sharp generalization bound for neural networks trained by gradient descent (GD) is of central interest in statistical learning theory and deep learning. In this paper, we consider nonparametric regression
by an over-parameterized two-layer NN trained by GD. We show that, if the neural network is trained by GD with early stopping, then the trained network renders a sharp rate of the nonparametric regression risk of $\mathcal O(\epsilon_n^2)$,  which is the same rate as that for the classical kernel regression trained by GD with early stopping, where $\epsilon_n$ is the critical population rate of the Neural Tangent Kernel (NTK) associated with the network and $n$ is the size of the training data. It is remarked that our result does not require distributional assumptions on the covariate as long as the covariate lies on the unit sphere, in a strong contrast with many existing results which rely on specific distributions such as the spherical uniform data distribution or distributions satisfying certain restrictive conditions.
As a special case of our general result, when the eigenvalues of the associated NTK
decay at a rate of $\lambda_j \asymp j^{-\frac{d}{d-1}}$ for $j \ge 1$ which happens under certain distributional assumption such as the training features follow the spherical uniform distribution, we immediately obtain the minimax optimal rate of
$\mathcal O(n^{-\frac{d}{2d-1}})$, which is the major results of several existing works in this direction. The neural network width in our general result is lower bounded by a function of only $d$ and $\epsilon_n$, and such width does not depend on the minimum eigenvalue of the empirical NTK matrix whose lower bound usually requires additional assumptions on the training data.
Our results are built upon two significant technical results which are of independent interest. First, uniform convergence to the NTK is established during the training process by GD, so that we can have a nice decomposition of the neural network function at any step of the GD into a function in the Reproducing
Kernel Hilbert Space associated with the NTK and an error function with a small $L^{\infty}$-norm. Second, local Rademacher complexity is employed
to tightly bound the Rademacher complexity of the function class comprising all the possible neural network functions obtained by GD. Our result
formally fills the gap between training a classical kernel regression model and training an over-parameterized but finite-width neural network by GD for nonparametric regression without distributional assumptions about the spherical covariate.

Sharp Generalization for Nonparametric Regression by Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate
Yingzhen Yang'
Abstract
results are built upon two significant technical results which are of independent interest. First, uniform convergence to the NTK established during the training process by GD, so that we can have a nice decomposition of the neural network function at any step of the GD into function in the Reproducing Kernel Hilbert Space associated with the NTK and an enror function with small -orm. Second, local Rademacher complex- ity is employed to tightly bound the Rademacher complexity of the function class comprising all the possible neural network functions obtained by GD. Our result formally fills the gap between training a classical kernel regression model and training over parameterized but finite-wdth neural network by GD for nonparametric regres- sion without distributional assumptions about the spherical covariate.
Sharp generalization bound for neural networks trained by gradient descent (GD) is of central interest in statistical learning theory and deep learning. In this paper, consider nonpara- metric regression by perrparameterized two- layer NN trained by GD. We show that, if the neural network is trained by GD with early stopping, then the trained network renders a sharp rate of the nonparametric regression risk of (=)), which is the same rate as that for the classical kernel regression trained by GD with early stopping, where En is the critical popula- tion rate of the Neural Tangent Kernel (NTK) associated with the network and n is the size of the training data. It is remarked that our re- sult does not require distributional assumptions on the covariate as long as the covariate lies on the unit sphere, in strong contrast with many existing results which rely on specific distribu- tions such as the spherical uniform data distribu- tion or distributions satisfying certain restrictive conditions. As a special case of our general re- sult, when the eigenvalues the associated NTK decay at rate of >ラ x -ーق for j 2 1 which happens under certain distributional assumption such as the training features follow the spheri- cal uniform distribution, we immediately obtain the minimax optimal rate of O(n If)), which is the major results of several existing works in this direction. The neural network width in our general result lower bounded by function of only d and Ens and such width does not depend on the minimum eigenvalue of the empirical NTK matrix whose lower bound usually requires ad- ditional assumptions on the training data. Our
1. Introduction
With the stunning success of deep learning in various areas of machine learning (LeCun et al., 2015), generalization analysis for neural networks is of central interest for sta- tistical learning learning and deep learning. Considerable efforts have been made to analyze the optimization of deep neural networks showing that gradient descent (GD) and stochastic gradient descent (SGD) provably achieve van- ishing training loss (Du al., 2019b; Allen-Zhu et al., 2019b; Du al., 2019a; Arora et al., 2019; Zou & Gu, 2019; Su & Yang, 2019). There are also extensive efforts devoted to generalization analysis of deep neural networks (DNNs) with algorithmic guarantees, that is, the general- ization bounds for neural networks trained by gradient de- scent or its variants. It has been shown that with sufficient over- paraaaaateeiiiiionn that is, with enough number of neu- rons in hidden layers, the training dynamics deep neural networks (DNNs) can be approximated by that of kernel method with the kernel induced by the neural network ar- chitecture, termed the Neural Tangent Kernel (NTK), while other studies such as (Yang & Hu, 2021) show that infinite- width neural networks can still learn features. The key idea of NTK based generalization analysis is that, for highly
'School of Computing and Augmented Intelligence, Arizona State University, Tempe, AZ 85281, USA. Correspondence to: Yingzhen Yang <yingzhen.yang asu.edu>>
Proceedings of the 1nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate
over-parameterizee networks, the network weights almost remain around their random initialization. As a result, one can use the first-order Taylor expansion around initializa- tion to upproximate the neural network functions and ana- lyze their generalization capability (Cao & Gu, 2019; Arora et al., 2019; Ghorbani et al., 2021).
open questions or concerns do not require distributional as- sumptions about spherical covariate. Section 3 summarizes our main results with their significance and comparison to existing works.
We organize this paper as follows. We first introduce the necessary notations in the remainder of this section. We then introduce in Section 2 the problem setup for nonpara- metric regression. Our main results are summarized in Sec- tion 3 and detailed in Section 5. The training algorithm for the wver-parameterized two-layer neural network is intro- duced in Section 4. The roadmap of proofs, the summary of the technical approaches and the novel results in the proofs, and the novel proof strategy of this work are presented in Section 6. The detailed proofs are deferred to Section A- Section C of the appendix, and Section D of the appendix presents the simulation results.
Many existing works in generalization analysis of neural networks focus on clean data, but it is a central problem in statistical learning that how neural networks can obtain sharp convergence rates for the risk of nonparametric re- gression where the observed data are corrupted by noise. Considerable research has been conducted in this direc- tion which shows that various types of DNNs achieve op- timal convergence rates for smooth (Yarotsky, 2017; Bauer & Kohler, 2019; Schmidt-Hieber, 2020; Jiao al., 2023; Zhang& & Wang, 2023) or non-smooth (Imaizumi & Fuku- mizu, 2019) target functions for nonparametric regression. However, most of these works do not have algorithmic guarantees, that is, the DNNs in these works are con- structed specially to achieve optimal rates with no guar- antees that an optimization algorithm, such as GD or its variants, can obtain such constructed DNNs. To this end, efforts have been made in the literature to study the mini- max optimal risk rates for nonparametric regression with peeepparameterized neural networks trained by GD with either early stopping (Li et al., 2024) or (e-regularization (Hu et al., 2021; Suh et al., 2022). However, most existing works either require spherical uniform data distribution on the unit sphere (Hu et al., 2021; Suh et al., 2022) or certain restrictive conditions on the data distribution.
Notations. We use bold letters for matrices and vectors, and regular lower letter for scalars throughout this paper. The bold letter with a single superscript indicates the corre- sponding column of a matrix, c.g., A ()) is the i-th column of matrix A, and the bold letter with subscripts indicates the corresponding rows or elements of matrix or a vec- tor. We put arrow top of a letter with subscript if it denotes vector, e-g., x, denotes the i-th training fea- ture. I|-II= and II-Il, denote the Frobenius norm and the vector (P-norm the matrix p-norm. [m : n] denotes all the natural numbers between m and n inclusively, and [1 : n] is also written as [n]. Var [+] denotes the vari- ance of a random variable. I, is a n x n identity ma- trix. { is an indicator function which takes the value of if event E happens, or O otherwise. The complement of set A is denoted by AS, and |A] is the cardinality of the set A. v.c denotes the vectorization of matrix or set of vectors, and tr (.) is the trace of matrix. We denote the unit sphere in d-dimensional Euclidean space by gd-1 = {x: x E Rd ||x||2 = 1}. Let L3 . denote the space of square-integrable functions on gd-1 with probability measure μ,, and the inner product (:, (, and I1-1|" are defined as (J.9) == sor 1 (x)))())du and II/ == sge-1 ((())d((z) <0. Fuclidean closed ball centered at x with radius Given a function g: gd-1 + R. its - -norm is denoted by Ioll = supxese-1 lg(x)]- L is the function class whose elements almost surely have bounded I norm. (, and 11 denote the inner product and the norm in the Hilbert space H. a = O(b) or a S b indicates that there exists constant > 0 such that I cb. Ô in- dicates there are specific requirements in the constants of the O notation. a = o(b) and a = w(b) indicate that lim |a/b] = 0 and lim la/b] = xc, respectively. or a = @(b) denotes that there exists constants C1, C2 > 0 such that b I a S czb. Throughout this paper we let the
It remains an interesting and important question for the statistical learning and theoretical deep learning literature that if an over-parameterizee neural network trained by GD can achieve sharp risk rates for nonparametric regres- sion with milder assumptions or restrictions on the distri- bution of the covariate, so that theoretical guarantees can be obtained for data in more practical scenarios. In this paper, we give a confirmative answer to this question. We present sharp risk rate for nonparametric regression with an over-parameterized two-layer NN trained by GD with early stopping, which is distribution-free in spherical covariate. Throughout this paper, distribution-free in spherical covari- ate means that there are no distributional assumptions about the covariate as long as the covariate lies on the unit sphere. Furthermore, our results give confirmative answers to cer- tain open questions or address particular concerns in the literature of training over-parameterized neural networks by GD with early stopping for nonparametric regression with minimax optimal rates, such as the characterization of the stopping time in the early-stopping mechanism, the lower bound for the network width, and the constant learn- ing rate used in GD. Benefiting from our analysis which is distribution-fiee in spherical covariate, our answers to these
co. B (x;r) is the
x b
2

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate
input space be X' gu-1, and Unif (2) denotes the uni- form distribution on X. The constants defined throughout this paper may change from line to line. For a Reproducing Kernel Hilbert Space H. M(Ho) denotes the ball centered at the origin with radius (Ao in H. We use Ep [-] to denote the expectation with respect to the distribution P.
which is in fact the NTK associated with the two-layer NN (1) when only the first layer is trained, and K is a positive- definite (PD) kernel. Let the gram matrix of K over the training data S be K E R=x= Kiy K (x,, xy) for i E [n], and K,, == K/n is the empirical NTK ma- trix. Let the eigendecomppoition of K,, be K,, = UEUT where U is n x n orthogonal matrix, and Σ is a di- "
2. Problem Setup
agonal matrix with its diagonal elements { 1=1 be- ing eigenvalues of K,, and sorted in a non-increasing or- der. is proved in existing works, such as (Du et al., 2019b), that K,, is non-singular, and it can be verified that Xι E 1/2). Let HK be the Reproducing Ker- nel Hilbert Space (RKHS) associated with K. Because K is continuous on the compact set X' X, the inte- gral operator Tk: L L2 u)) + L2 p)) (Tkf) (x) = Sx K(x,x') (x) (dxx)) is positive, self-adjoint, and compact operator on L2 u)). By the spectral theo- rem, there is a countable orthonormal basis {6z S L nu) and {Az},21 with 1/2 2 A1 2 X2 ... > 0 such that ej is the eigenfunction of Tx with X, being the corresponding eigenvalue. That is, Txej = >yey.j 2 1. Let {uehez1 be the distinct eigenvalues associated with Tk. and let me be the be the sum of multiplicity of the eigenvalue {ue V That is, my - -m--1 is the mul- tiplicity of pe, It is well known that {u² = /Ajes,, 21 is an orthonormal basis of Hx. For positive con- stant Pa. we define Hx (Po) = {f E Hx: IIfllx S no as the closed ball in Hx centered at 0 with radius no- We note that H. is also specified by Hx (po) = f E (2), f f 3re,, Ey B3/2, S m3)
We introduce the problem setups for nonparametric regres- sion in this section.
2.1. Two-Layer Neural Network
We are given the training data {(x: " where each data point is tuple of feature vector x; E X' and its re- sponse y E R. Throughout this paper we assume that no two training features coincide, that is, x, * x, for all i E [n] and # j. We denote the training feature vec- tors by S = { {xi (=1"
i=1
and denote by Pn the empirical distribution over S. All the responses are stacked as a vee- tor y = [M.... yn]" E TR.". The response yi is given by y: = [xx,,) + W, for i E [n]. where {w;]== are i..d. sub-Gaussian random noise with mean 0 and vari- ance proxy of. that is, EE [exp(>w:)] I exp(A"a3/2) for any À F. f is the target function to be detailed later. We define y = [MI................ ynl. W == [Wi...., wn]] and use ((x.)) to denote the clean tar- get labels. The feature vectors in S are drawn i.i.d. accord- ing to an underlying unknown continuous data distribution P with μ being the probability measure for P. We consider a two-layer NN (NN) in this paper whose mapping function is
(*(S) =
The Task of Nonparametric Regression. With I' E H the task of the analysis for nonparametric re- gression is to find an estimator f from the training data 27
{ ((
" i=1 so that the risk Ep (f- [f-)))
f(W,x)=
a
Wr x
(1)
can con- verge to O with fast rate. In this work, we aim to establish sharp rate of the risk where the peeeterramteri neural network (1) trained by GD with early stopping serves the estimator f.
m
where X X is the input, a.) max f. is the ReLU activation function, W W= [wr --1
m
with w, Rd for r E [m] denotes the weighting vectors in the first layer and m is the number of neurons.
[01,-..,,mml E T denotes the weights of the second layer. Throughout this paper we also write W as Ws so as to indicate that the weighting vectors in W are trained on the training features S.
Sharp rate of the risk of nonparametric regression us- ing classical kernel regression. The statistical learning lit- erature has established rich results in the sharp convergence rates for the risk of nonparametric kernel regression (Stone, 1985; Yang & Barron, 1999; Raskutti et al., 2014; Yuan & Zhou, 2016), with one representative result in (Raskutti et al., 2014) about kernel regression trained by GD with early stopping. Let en be the critical population rate of the PD kernel K, which is also referred to as the critical ra- dius (Wainwright, 2019) of K. (Raskutti et al., 2014, The- orem 2) shows the following sharp bound for the nonpara- metric regression risk of a kernel regression model trained
2.2. Kernel and Kernel Regression for Nonparametric Regression
We define the kernel function
(u, v)
K(u, v) = 2T
(π arccos (u, v)). Vu,e,,
3

---

Sharp Generalization for Over-Parameterixee Neural Networks: A Distribution-Free Analysis in Spherical Covariate
by GD with early stopping when f* Hx (Mo). That is, with probability at least @ (exp(-0(nee))
result of a series of existing works in nonparametric regres- sion by training over-parameterized neural networks (Hu et al., 2021; Suh et al., 2022; Li et al., 2024) when the tar- get function f belongs to H the RKHS associated with the NTK K of the network in each particular existing work. We note that K is the NTK of the network considered in a particular existing work which may not be the same as our NTK in (2). We also note that one needs to set 8 = in (Li et al., 2024, Proposition 13) so that f E Hg. and in this case the risk rate for nonparametric regression (Li et al., 2024, Proposition 13) is O(n X To the best of our knowledge, Theorem 5.1 presents the first sharp risk rate for nonparametric regression which is distribution-fiet in spherical covariate, which is closer to practical scenar- ios. In contrast, the minimax rates in (Hu al., 2021; Suh et al., 2022) require spherical uniform data distribution on X. The recent work (Ko & Huo, 2024) also requires certain distributional assumptions for the results about regression convergence rates which does not have algorithmic guar- antees. Although the minimax rate in another recent work (Li et al., 2024) does not need the spherical uniform dis- tribution. still requires a restrictive condition on the data distributions detailed in Table 1, and such condition is met by sub-Gaussian distributions. It is under this condition that (Li et al., 2024) derives the polynomial EDR. Table I compares our work to existing works for nonparametric re- gression with a common setup, that is, f E Hg and the responses {y: } are corrupted by i.i.d. Gaussian noise. We further note that although the result in (Kuzborskij & Szepesvári, 2021, Theorem 2) does not require distribu- tional assumptions about the covariate, its risk rate under this common setup is not minimax optimal due to the term of in the risk bound. Furthermore, the other term (n in its risk bound suffers from the curse of dimension with slow rate to O for high-dimensional data. We also note that (Kuzborskij & Szepesvári, 2021, Theorem 1) shows the minimax optimal rate of O(n afa). however, this rate is derived for the noiseless case where the responses are not corrupted by noise.
Ep (Jz /-) S
Sen e..
(3)
where T is the stopping time whose formal definition is deferred to Section 5.1, and Sp is the kernel regressor at the T-th step of GD for the optimization problem of ker- nel regression. The risk bound (3) is rather sharp, since it is minimax optimal in several popular learning setups, such as the setup where the eigenvalues {>: exhibit a certain polynomial decay. Such risk bound (3) also holds for a general PD kernel rather than the NTK (2), and the risk bound (3) is also minimax optimal when the PD kernel is low rank. It is also remarked that the risk bound (3) is distribution-fri in the bounded covariate, that is, there are no distributional assumptions about the covariate when it is in a bounded input space. Interested readers are referred to (Raskutti et al., 2014) for more details.
The main result of this paper is that the over-parameterized two-layer NN (1) trained by GD with early stopping achieves the same order of risk rate that in (3) with ar- bitrary continuous distribution of the spherical covariate, which are summarized in the next section.
3. Summary of Main Results.
Our main results are summarized in this section. Through- out this paper, we consider fixed dimension d 2 4.
First, Theorem 5.1 in Section 5.2 shows that the neural net- work (1) trained by GD with early stopping using Algo- rithm 1 enjoys sharp rate of the nonparametric regression risk, O (e2), which is the same as that for the classical kernel regression in (3). Such rate of nonparametrie re- gression risk in Theorem 5.1 is distribution- free in spher- ical covariate, and it immediately leads to minimax opti- mal rates for certain special cases. For example, when the eigenvalues of the integral operator associated with K has a particular polynomial eigenvalue decay rate (EDR), that is, \ラ x -ーンー z for j 2 1. then in this case 2 x n = according to (Raskutti et al., 2014, Corollary 3), and The- orem 5.1 renders the rate of the nonparametric regression risk of On 2-)) which is minimax optimal for this spe- cial case (Stone, 1985; Yang & Barron, 1999; Yuan & Zhou, 2016). We refer to such EDR the polynomial EDR in the sequel. It is shown in (Bietti & Mairal, 2019; Bietti & Bach, 2021; Li al., 2024) that the polynomial EDR holds for our NTK in (2) if P = Unif (X'), or P satisfies the dis- tributional assumption for (Li et al., 2024, Proposition 13) in Table 1.
Second, our results provide confirmative answers to several outstanding open questions or address particular concerns in the existing literature about training over- wwer-parameterized neural networks for nonparametric regression by GD with early stopping and sharp risk rates, which are detailed be- low.
Stopping time in the early-stopping mechanism. An open question raised in (Kuzborskij & Szepesvári, 2021; Hu et al., 2021) is how to characterize the stopping time in the carly-stopping mechanism when training the over- parameterized network by GD. Let T be the stopping time, (Li et al., 2024, Proposition 13) shows that the stopping time should satisfy T x n nd under the distributional as-
We remark that such a minimax optimal rate O(n zá I) is derived from Theorem 5.1 under the special case of polyno- mial EDR, and this minimax optimal rate is also the major
4

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribation-Free Analysis in Spherical Covariate
Table 1: Comparison between our result and the existing works on the risk rates and assumptions for nonparametric regression by training over- over-parameten perr-aramttereee neural networks with algorithmic guarantees, and the listed results here are under common and popular setup that f E Hg and the responses {ue)__ are corrupted by i.i.d. Gaussian noise with zero mean and variance o--
Existing Works and Our Result
Distributional Assumptions
Eigenvalue Decay Rate (EDR)
Rate of Nonparametrie Regression Risk minimax optimal, + ((N
(Kuzborskij Szepesvári, 2021, Theorem (Hu et al,, 2021, Theorem 5.2). (Suh et al., 2022, Theorem 3.11)
No
is Unit (2')
A +
minimax optimal. ( )
P satisfies restrictive condition:
(Li et al., 2024, Proposition 13)
A A
minimax optimal, O(nail))
the density p(x) for R satisfies
p(z) (1 )
(=4). which leads the minimax optimal rate (( claimed (Hl al. 2021: Suh et al., 2022) and (Li ct al., 2024)
distributional assurpption about long X' 34-1
Our Result (Thoorem 1.
No requirement for EDR
as special cases.
sumption in Table 1. In contrast, Theorem 5.1 provides characterization of T showing that T x ,,²2, which is distribution-free in spherical covariate. Theorem 5.1 fur- ther suggests that for each neural network function ft ob- tained at the t-th step of GD with t x en? the sharp risk rate of O (c?) is obtained.
sition 13) suggests that m 2 n2 (1og m) Both lower bounds for m in (Suh et al., 2022, Theorem 3.11) and (Li et al., 2024, Proposition 13) are much larger than our lower bound for m, n 33 d3, when n - oo and d is fixed, which is the setup considered in (Li et al., 2024). It is worthwhile mention that (Suh et al.,, 2022; Li al., 2024) use DNNs with multiple layers for nonparametric regres- sion. As shown in Table 1, through our careful analysis, a shallow two-layer NN (1) exhibits the same minimax risk rate as its deeper counterpart under the same assumptions with much smaller network width. This observation fur- ther support the claim in (Bietti & Bach, 2021) that a shal- low over- weerpparamttriiee neural networks with ReLU acti- vations exhibit the same approximation properties as its deeper counterpart, in our nonparametric regression setup.
Lower bound for the network width m. Our main re- sult, Theorem 5.1, requires that the network width m, which is the number of neurons in the first layer of the network, satisfies m ž d /En" Such lower bound for m solely depends on and E.- Under the polynomial EDR, Corollary 5.2, which is a direct consequence Theo- rem shows shows that should satisfy m Z n n 3 with
a a= d=d/(2(d-1) 1)) (see (11)) so that GD with early stopping leads to the minimax rate of On -()). We remark that this is the first time that the lower bound for the network width is specified only in terms of n and d under the polynomial EDR with minimax optimal risk rate for non- parametric regression, which can be easily estimated from the training data. In contrast, under the same polynomial EDR, all the existing works (Hu et al., 2021; Suh et al., 2022; Li et al., 2024) require m Z poly (n. 1/xx). The problem here is that one needs additional assumptions on the training data (Bartlett et al., 2021; Nguyen et al., 2021) to find the lower bound for X which is the minimal eigen- value of the empirical NTK matrix K,, to further estimate the lower bound for m using the training data.
Training the network with learning rate 17 = +(1). It is also worthwhile to mention that our main result, Theo- rem 5.1, suggests that a constant learning rate rj ((1) can be used for GD when training the two-layer NN (l), which could lead to better empirical optimization perfor- mance in practice. Some existing works in fact require an infinitesimal 17. For example, (Li et al., 2024, Proposition 13) is obtained by gradient flow where + 0 instead of the practical GD. Furthermore, (Hu et al., 2021, Thcorem 5.2) requires the learning rates for both the squared loss and the
é e-regularization term to have the order of o(n 34-1 0 as + oc. We note that (Nitanda & Suzuki, 2021) also employs constant learning rate in SGD to train neural net- works.
Corollary 5.2 also gives competitive and smaller lower bound for the network width than some existing works which give explicit orders of the lower bound for m. For example, under the assumption of uniform spherical dis- tribution, (Suh et al., 2022, Theorem 3.11) requires that m/ log" m Z 2, where L is the number of layers of the DNN used in that work, and m/ llg" m Σ 220n2 even with J. = 2 for the two-layer network (1) used in our work. Furthermore, the proof of (Li et al., 2024, Propo-
More discussion about this work and the relevant lit- erature. We herein provide more discussion about the results of this work and comparison to the existing relevant works with sharp rates for nonparametric regression. While this paper establishes sharp rate which is distribution-free in spherical covariate, such rate still depends on bounded input space (X' = sd-1) and the condition that the target
5

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate
function I* E Hx (Mo). Some other existing works con- sider target function f not belonging to the RKHS ball centered at the origin with constant or low radius, such as (Haas et al., 2023; Bordelon et al., 2024). However, the tar- get functions in (Haas et al., 2023; Bordelon et al., 2024) escape the finite norm or low-norm regime of RKHS at the cost of either restriction condition on the density function of the covariate distribution or the training process. In par- ticular, (Haas et al., 2023, Theorem G.5) requires the con- dition for bounded density function (in its condition (D3) ) of the distribution P. which is not required by our result. Moreover, the training process of the model in (Bordelon et al., 2024) requires information about the target function (in its Eq. (4)) and certain distribution P which admits cer- tain polynomial EDR, that is, A x =j == with a > I, which happens under certain restrictive conditions on P.
We define (1) E Rmmdx which is computed by
Vm ll (w.(t) x.20 X;0r
(6)
for all i E [n] and r E [m]. where [Zs(t) [tr
Algorithm 1 Training the Two-Layer NN by GD
1: (T)) < Training W(O)
input: T. ((0)
3: for / 1= 1=,,..., do
4: Perform the t-th step of GD by (5)
5: end for
6: return W())
Fd is a vector with elements in the i-th column of Zs(t) with indices in [(r - 1)d + 1 : rd]. We employ the fol- lowing particular symmetric random initialization so that y (0) O, which has been used in existing works such as (Chizat et al., 2019; Zhang et al., 2020). In our two-layer m/2
We also note that in this work, only the first layer of an over- wverpparameterized two-layer neural network is trained, while the weights of the second layer are randomly ini- tialized and then fixed in the training process. In existing works such as (Hu et al., 2021; Suh et al., 2022; Allen- Zhu et al., 2019a), all the layers of a deep neural networks with more than two layers are trained by GD its vari- ants. However, this work shows that only training the first layer still leads to sharp rate for nonparametric regression, which supports the claim in (Bietti & Bach, 2021) that a shallow over peee-paramtterieed neural networks with ReLU activations exhibit the same approximation properties as its deeper counterpart.
NN, m is even, (2- ~-1 {0)) and (azr 1m/2 } are initial-
ized randomly and independently according to W2. (0) N(, x. k²Ia), Agr unif (f- Vr' E [m/2]. where (H, Σ) denotes a Gaussian distribution with mean j and covariance E, unif ({-1,1}) denotes a uniform distribu- tion over {1. 11). 0 < K S 1 controls the magnitude of initialization, and x. x 1. We set (2) Wer (0) and 02r--1 ugr for all r' E [m/2]. It then can be verified that (0) O. Once randomly initialized, a is fixed during the training. We use ((0) to denote the set of all the random weighting vectors at initialization, that is, W(0) = (w(()) -= the two-layer NN by GD for T steps. Early stopping is enforced in Algorithm through bounded T via T S T.
4. Training by Gradient Descent and Preconditioned Gradient Descent
We run Algorithm 1 to train
In the training process of our network (1), only W is op- timized with a randomly initialized to #1 and then fixed. The following quadratic loss function is minimized during the training process:
5. Main Results
We present the definition of kernel complexity in this sec- tion, and then introduce the main results for nonparametric regression of this paper.
((W, x;) - 9:) 2
Z(W)= = 2n
Σ i=1
(4)
In the (1 1)-th step of GD with 2 O, the weights of the neural network, Ws. are updated by one-step of GD through
5.1. Kernel Complexity
The local kernel complexity has been studied by (Bartlett et al., 2005; Koltchinskii, 2006; Mendelson, 2002). For the PD kernel K, we define the empirical kernel complexity Rx and the population kernel complexity Rx as
vec (Ws(t+ 1)) - vec (Ws())- = -Zzs(0)((1)- y),
(5)
where y; = Vr. (1) E RD with (7)), = ((W()), s((1), x:). The notations with the subscripts S indicate the de- pendence on the training features S. We also denote (() as f(()) as the neural network function with weighting vectors W(t) obtained after the i-th step of GD.
Rx(E)=
1
min (Nn
n i=1
1
Rx(s)= =
min 62)
n
i=1
6

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate
It can be verified that both og og (s) and oo RgRx(e) (e) are sub- root functions (Bartlett et al., 2005) in terms of e². The formal definition of sub-root functions is deferred to Defi- nition A.2 in the appendix. For a given noise with variance proxy of the critical empirical radius en > 0 is the small- est positive solution to the inequality (s) S e² //o. where En is the also the fixed point of (E) as a func- tion of e²: ooRx(E,, = e. Similarly, the critical popu- lation rate en is defined to be the smallest positive solution to the inequality (x(e) < =2/00, where = is the fixed point of oe Rx (s) as a function of e²: on (en) = < In this paper we consider the case that ne - 0o as n -> oc, which is also used in standard analysis of nonparametric re- gression with minimax rates by kernel regression (Raskutti et al., 2014).
a 1/2. Let cr, E (0, be positive constants, and of S T s T. Suppose m satisfies
50o m 2 n 312 ds,
(11)
and the neural network S(W -) is trained by GD using Algorithm 1 with the learning rate 17 [1,2) and T < T. Then for every t E [e,T: T), with probability at least 1 - exp(-((n) - 7 exp (-@(ne)) 2/nn over the random noise w, the random training features and the random initialization (()), the stopping time satisfies T x x
1 12
Ep [(ft (
(12)
The significance of Corollary 5.2 is also detailed in Sec- tion 3. Section D) of the appendix shows the simulation results with the empirical early stopping time and the theo- retically predicted early stopping time, 1/22, x n d2d-21)) 1), for a neural network trained by Algoirthm 1.
Let the = nt for all t 2 0, we then define the stopping time T as
min f t: Rx Rx(VI/m) > (oon)-
1. (8)
The stopping time in fact limit the number of steps T in for Algorithm as be shown in Section 5.2, which in turn enforces the early stopping mechanism.
6. Roadmap of Proofs
We present the roadmap of our theoretical results which lead to the main result, Theorem 5.1 in Section 5. We first present in the next subsection our results about the uniform convergence to the NTK (2) and more, which are crucial in the analysis of training dynamies by GD.
5.2. Results
Theorem 5.1. Let CT, Ct (0, be arbitrary positive con- stants, and 7 < T S T. Suppose s E Hx and m satisfies
6.1. Uniform Convergence to the NTK and More
We define functions
d3 /en
(9)
h(w,x,y) == x y I ( [20) I (wT
and the neural network f (W((). .) is trained by GD using Algorithm with the learning rate 7) E (1,2) and T < T. Then for every / E [c,T: T]. with probability at least 1 - exp (=)( - 7ex (-O(ne2)) - 2/n over the random noise w, the random training features S and the random initialization ((),, the stopping time satisfies f x x and ((W(((W)))))))))) (1), fa satisfies
?( = 1 k(W,,, x,y),
(13)
m
un(w, x) = [[ En W x) =
Σ
Dn (r,, x).
(14)
Then we have the following theorem stating the uniform convergence of h T(WW(0) (W)).,,) ) to K(,,)) and uniform con- vergence of TR( (W)),, x) to 2R for a positive num- ViTe
Ep [(e - [- S e
(10)
Significance of Theorem 5.1 and comparison to existing works. To the best of our knowledge, Theorem 5.1 is the first theoretical result which proves that over werr-aarameterized neural network trained by gradient descent with early stop- ping achieves sharp rate of (E))), without distributional assumption on the covariate long as the input space X' is gd-1 More discussions about the significance with com- parison to existing works are detailed in Section 3.
ber R A mTT//mm While existing works such as (Li et al., 2024) also has uniform convergence results for over- parameterized neural network, our result does not depend on the Hölder continuity of the NTK.
Theorem 6.1. The following results hold with 1) S L, 1, Z max (n2/d, T }. and m/ log 2 d.
(1) With probability at least 1/n over the random ini- tialization W(O)- = (w)(()) |
When the polynomial EDR holds, we can apply Theo- rem 5.1 to obtain the following corollary.
sup -ity)) x,>> dC x yEx
Corollary 5.2 (Applying Theorem 5.1 to the special case of polynomial EDR). Suppose X; = ; 2a for j Z and
7

---

Sharp Generalization for Over-Parameterizee Neural Networks: A Distribution-Free Analysis in Spherical Covariate
d dogg m
cantly novel and different from the existing works in train- ing over-parameterized neural networks for nonparametric regression with minimax rates (Hu et al., 2021; Suh et al., 2022; Li et al., 2024). In particular, the common proof strategy in these works uses the decomposition ft f" = (f+ - (ENTK) + (fPNTK)) - f*) and then show that both ft - / (TTTK) and | --11
(15)
m
(2) With probability at least 1 - 1/n over the random ini-
tialization W(0) = ={ [0) m
- 1 are bounded by cer-
2R
sup xEX
pR (0) v
+ (.
1,2
2TK
tain minimax optimal rate, where ((NTK) the kernel re- gressor obtained by either kernel ridge regression (Hu et al., 2021; Suh et al., 2022) or GD with early stopping (Li et al., 2024). The remark after Theorem C.8 details formulation of f. fANTK)
S Vdm T
(16)
where Ci (m/2, d, fmm/2,d1/nn) 1/n), C2 (m/22 d, 1/n) are two positive numbers depending (m, d, n),, with their formal defini- tions deferred to (39) and (42) in Section C.2 of the ap- pendix.
| f* r.a
is bounded by the minimax optimal rate under certain distributional assumptions in the covariate, and this is one reason for the distributional as- sumptions about the covariate in existing works such (Hu et al., 2021; Suh et al., 2022; Li et al., 2024). In strong contrast, our analysis does not rely on such decomposition of ft - fr. Instead of approximating fo by f(NTK), we have new decomposition of fa by Se h; + ex where fe is approximated by h2 with e, being the approximation error. As suggested by the remark after Theorem C.8, we have h4 = f.NTKK + (- t) so that ft = fINIK) + @2(+,t) + ez. Our analysis only requires the network width mn to be suit- ably large so that the Hnrm of (. is bounded by a positive constant and ||e S w, while the common proof strategy in(Hu et al., 2021; Suh et al., 2022: Li et al., 2024) needs m be sufficiently large that both (; and ||eell 2o are bounded by an infinitesimal number (a minimax
Proof. This theorem follows from Theorem C.1 and Theorem C.2 in Section C22 of the appendix. m Ex= x.W,...))
Note that ((W,,, y)
m/2 EmL? h(w2r (0), then part (1) directly follows from Theorem C.I. Similarly, part (2) directly follows from Theorem C.2.
n
6.2. Roadmap of Proofs
Because our main result, Theorem 5.1, is proved by The- orem C.10 and Theorem C.11 deferred to Section C.2, we illustrate in Figure 1, deferred to the appendix, the roadmap containing the intermediate theoretical results which lead to our main result, Theorem 5.
optimal rate such as O(n xह-)) and then J - J.NK)
L2
Summary of the technical approaches and novel results in the proofs. Theorem C.8 the first novel result in the proofs of this work, showing that with high probability, the neural network function (()()),) -) at step t of GD can be decomposed into two functions by -t) = f. = h + e, where h E Hx is function in the RKHS associ- ated with K with bounded -nom. The error function e has a small L -nrm,, that is, ||e||x= I w with w being a small number controlled by the network width m, that is, larger m leads smaller w. Theorem C0 is the sec- ond novel result in the proofs, where we derive sharp and novel bound for the nonparametric regression risk of the neural network function (t)()),) in Theorem C.10, that is, Ep [[fe - ]² 2Ep, [(++ - [+]] S 2 +w. To the best of our knowledge, Theorem 10 is among the first in the literature to employ local Rademacher complexity so as to obtain sharp rate for the risk of nonparametric regression which is distribution-free in spherical covariate, and local Rademacher complexity is employed to tightly bound the Rademacher complexity of the function class comprising all the possible neural network functions obtained by GD.
is bounded by such minimax optimal rate. Detailed in Sec- tion 3, such novel proof strategy leads to our sharp analysis, rendering a smaller lower bound for m in our main result compared to some existing works.
7. Conclusion
In this paper, we show that an over over-oarannnn parameterized two-layer neural network trained by gradient descent (GD) with early stopping renders a sharp rate of the nonparametric regres- sion risk with the order of ((=)) with e. being the critical population rate or the critical radius of the NTK, which is distribution-free in spherical covariate. We compare our re- sults to the current state-of-the- art with detailed roadmap of our technical approaches and results in our proofs.
Acknowledgments
This work is supported by the 2023 Mayo Clinic and Ari- zona State University Alliance for Health Care Collabo- rative Research Seed Grant Program under Grant Award Number AWD00038846.
Novel proof strategy of this work. We remark that the proof strategy of our main result, Theorem 5.1, is signifi-
8

---

Sharp Generalization for Over-Parameterizee Neural Networks: A Distribution-Free Analysis in Spherical Covariate
Impact Statement
Cao, Y. and Gu, Q- Generalization bounds of stochas- tic gradient descent for wide and deep neural networks. In Wallach, H. M., Larochelle, H., Beygelzimer, A., d' Alché-Buc, F,, Fox, E. B., and Gamett, R. (eds.), Ad- vances in Neural Information Processing Systems, pp. 10835-10845, 2019.
This paper presents work whose goal is to advance the the- oretical understanding of the generalization capability of over-parameterized neural networks trained by gradient de- scent.
References
Chizat, L., Oyallon, E., and Bach, F. On lazy training in differentiable programming. Curran Associates Inc., Red Hook, NY, USA, 2019.
Allen-Zhu, Z., Li, Y., and Liang, Y. Learning and gen- eralization in overparameterized neural networks, going beyond two layers. In Wallach, H. M.. Larochelle, H., Beygelzimer, A., d' d'Alché-Buc F., Fox, E. B., and Gar- nett, R. (eds.), Advances in Neural Information Process- ing Systems 32: Annual Conference on Neural Informa- tion Processing Systems 2019, NeurIPS 2019, Decem- ber 8-14, 2019, Vancouver, BC, Canada, pp. 6155-6166, 2019a.
Du, S. S., Lee, J. D., Li, H.,, Wang, L.,, and Zhai, X. Gradi- ent descent finds global minima deep neural networks. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Interna- tional Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp- 1675- 1685. PMLR, 2019a.
Du, S. S., Zhai, X., Poczos, B., and Singh, A. Gradient de- scent provably optimizes aver-parameterized neural net- works. In International Conference on Learning Repre- sentations, 2019b.
Allen-Zhu, Z., Li, Y., and Song, Z. A convergence theory for deep learning via werr-praamtterization. In Interna- tional Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 242- 252. PMLR, 2019b.
Ghorbani, B., Mei, S., Misiakiewicz, T., and Montanari, A. Linearized two-layers neural networks in high di- mension. Ann. Statist., 49(2):1029 1054, 2021.
Arora, S., Du, S. S., HU, W., Li, Z., and Wang, R. Fine- grained analysis of optimization and generalization for overparameterized two-layer neural networks. Inter- national Conference on Muchine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 322- 332. PMLR, 2019.
Haas, M., Holzmüiller, D., von Luxburg, U., and Steinwart, I. Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension. In Oh, A., Nau- mann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Pro- cessing Systems 36: Annual Conference on Neural In- formation P Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10- 16, 2023, 2023.
Bartlett, P. I.., Bousquet, O., and Mendelson, Lo- cal rademacher complexities. Ann. Statist., 33(4):1497- 1537, 08 2005.
Hu, T. Wang, W., Lin, C., and Cheng, G. Regular- ization matters: A nonparametrie perspective on over- parametrized neural network. In Banerjee, A. and Fuku- mizu, K. (eds.), International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 829-837. PMLR, 2021.
Bartlett, P. L.,, Montanari, A., and Rakhlin, A. Deep learn- ing: statistical viewpoint. Acta Numerica, 30:87-201, 2021. doi: 10.1017/800024422220000
Bauer, B. and Kohler, M. On deep learning remedy for the curse of dimensionality in nonparametric regression. Ann. Statist., 47(4):2261 2285, 2019.
Imaizumi, M. and Fukumizu, K. Deep neural networks learn non-smooth functions effectively. In Chaudhuri, K. and Sugiyama, M. (eds.), International Conference on Artificial Intelligence and Statistics, volume 89 of Pro- ceedings of Machine Learning Research, pp. 869-878. PMLR, 2019.
Bietti, A. and Bach, F. R. Deep equals shallow for relu networks in kernel regimes. In 9th International Confer- ence on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
Bietti, A. and Mairal, J. On the inductive bias of neu- ral tangent kernels. In Wallach, H. M., Larochelle, H., Beygelzimer, A., d' Alché-Buc, F., Fox, E. B., and Gar- nett, R. (eds.), Advances in Neural Information Process- ing Systems, pp. 12873- 2019.
Jiao, Y., Shen, G., Lin, Y., and Huang, J. Deep nonparamet- ric regression on approximate manifolds: Nonasymp- totic error bounds with polynomial prefactors. Ann. Statist., (1()))6 716, 2023.
Bordelon, B., Atanasov, A. B., and Pehlevan, C. How fea- ture learning can improve neural scaling laws. CoRR, Abs/2409.17855 2024.
Ko, H. and Huo, x. Universal consistency of wide and deep relu neural networks and minimax optimal con- vergence rates for kolmogorov- optimal function

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribation-Free Analysis in Spherical Covariate
classes. In Forty-first International Conference on Ma- chine Learning, ICML. 2024, Vienna, Austria, July 21-27, 2024. OeenRevi, 2024.
Stone, C. J. Additive Regression and Other Nonparametric Models, Ann. Statist., 13(2):689 -05,, 1985.
Su, L. and Yang, P. On learning over averppaaameterized neural networks: functional approximation perspective. In Advances in Neural Information Processing Systems, pp. 2637-2646, 2019.
Koltchinskii, V. Local rademacher complexities and oracle inequalities in risk minimization. Ann. Statist., 34(6): 2593-2656, 2006.
Kuzborskij, I. and Szepesvári, C. Nonparametric regres- sion with shallow overparameterized neural networks trained by GD with early stopping. In Belkin, M. and Kpotufe, S. (eds.), Conference on Learning The- ory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research. pp. 2853-2890. PMLR, 2021.
Suh, N., Ko, H., and Huo, X. A non non-parametric regression viewpoint Generalization of overparametrized deep RELU network under noisy observations. In The Tenth International Conference Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenRe- view.net, 2022.
Wainwright, M. J. High-Dimensional Statistics: Non- Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
LeCun, Y., Bengio, Y., and Hinton, G. Deep learning. Na- ture, 521: 444, 2015.
Ledoux, M. Probability in Banach Spaces [electronic resource] : Isoperimetry and Processes / by Michel Ledoux, Michel Talagrand. Classics in Mathematics. Springer Berlin Heidelberg, Berlin, Heidelberg, 1st ed. 1991. edition, 1991.
Wright, F. T. Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables Whose Distri- butions not Necessarily Symmetric. Ann. Probab., 1 (6): 1068 1070, 1973.
Yang. G. and Hu, E. J. Tensor programs IV: feature learn- ing in infinite-width neural networks. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 11727-11737. PMLR, 2021.
Li, Y., Yu, Z., Chen, G., and Lin, Q. On the eigenvalue decay rates of a class of neural netwol related kernel functions defined on general domains. Journal of Ma- chine Learning Research, 25(82):1 47, 2024.
Mendelson, S. Geometric parameters of kernel machines. In Kivinen, J. and Sloan, R. H. (eds.), Conference Computational Learming Theory, volume 2375 of Lec- ture Notes in Computer Science, pp. 43.43. Springer, 2002.
Yang, Y. and Barron, A. Information-theoreti determina- tion of minimax rates of convergence. Ann. Stafist., 27 (5):1564 - 1599, 1999.
Nguyen, Q. Mondelli, M., and Montúfar, G. F. Tight bounds the smallest eigenvalue of the neural tangent kernel for deep relu networks. In Meila, M. and Zhang, T. (eds.), International Conference on Machine Learn- ing, volume 139 of Proceedings of Machine Learning Research, pp. 8119-8129, PMLR, 2021.
Yang. Y. and Li, P. Gradient descent finds over- parameterized neural networks with sharp generalization for nonparametric regression, 2025.
Yarotsky, Error bounds for approximations with deep relu networks. Neural Newworks, 94:103-114, 2017.
Nitanda, A. and Suzuki, T. Optimal rates for averaged stochastic gradient descent under neural tangent ker- nel regime. In 9th International Conference on Learn- ing Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
Yuan, M. and Zhou, D.-X. Minimax optimal rates of estimation in high dimensional additive models. Ann. Statist., 24(6):2564 2593, 2016.
Zhang, K. and Wang. Y. Deep learning meets nonparamet- ric regression: Are weight-decayed dnns locally adap- tive? In International Conference on Learning Repre- sentations. OpenReview.net, 2023.
Raskutti, G., Wainwright, M. J., and Yu, B. Early stop- ping and non- con-paraeetric regression: optimal data- dependent stopping rule. J. Mach. Learn. Res., 15(1): 335-366, 2014.
Zhang, Y., Xu, Z. J., Luo, T., and Ma, Z. A type of general- ization error induced by initialization in deep neural net- works. In Lu, J. and Ward, R. A. (eds.), Proceedings of Mathematical and Scientific Machine Learning, MSML 2020, 20-24 July 2020, Virtall Conference Princeton,
Schmidt-Hieber J. Nonparametric regression using deep neural networks with ReLU activation function. Ann. Statist, 48(4):1875 1897, 2020.
10

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribution-Fres Analysis in Spherical Covariate
NJ, USA, volume 107 of Proceedings of Machine Learn- ing Research, pp. 144-164. PMLR, 2020.
Zou, D. and Gu, Q. An improved analysis of training over- parameterized deep neural networks. In Wallach, H. M., Larochelle, H., Beygelzimer, A., d' A'Ach-BBuu,, F., Fox, E. B., and Garnett, R. (eds.), Advances in Neural Infor- mation Processing Systems, pp. 2053-2062, 2019.

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate
We present the basic mathematical results required in our proofs in Section A, then present proofs in the subsequent sections.
A. Mathematical Tools
We introduce the basic definitions and mathematical results as the basic tools for the subsequent results in the next sections of this appendix.
Definition A. Let {o:) be i.i.d. random variables such that Pr(o; 1] = Pr(a, = =-1 = 1 The Rademacher
complexity of a function class F is defined as
R(F) = E (x:), do
sup Σ (x)(
(17)
JEF n2
The empirical Rademacher complexity is defined as
R(F)= = (or))
sup - fEF
Σ
(18)
For simplicity of notations, Rademacher complexity and empirical Rademacher complexity are also denoted by E
supser n Σ (x,) and E, supjer Σ (x;)
respectively.
For data
{
and a function class F, we define the notation R by R = supjer + E fx).) i=1
Theorem A.1 ((arttlett al., 2005, Theorem 2.1)). Let X, P be probability space, { x
be independent random
i=1 variables distributed according to P. Let F be class of functions that map X' into [a, b). Assume that there is some 0 such that for every f E Far fxx:)
s r. Then, for every > 0, with probability at least 1 - -_
sup (Er[[(x)] Ex-P, - [xx))] & inf
2(1 + a)R ()) [x:]" 10
RR +
2rx + (b a)
(
1 3
+
x
(19)
FEF
aso
and with probability at least 1 - -0-
sup (Ep]f(x)] - Ex~P,I((x]]] < inf feF
2(1 + a)
E (or R +V + (b - a)
2rr
1
+ +
1 1+ a
r
aE(0.1)
1 a
3
2a - a)
(20)
with Ex [f(x)] = 1 " Σ f(.)). Moreover, the same results hold for
Pn is the empirical distribution over sup (Ex-P,, [[(x)] - [x)s)
i=1
In addition, we have the contraction property for Rademacher complexity, which is due to Ledoux and Talagrand (Ledoux, 1991).
Theorem A.2. Let ø be a contraction,that is, 10(x) - o(y)) S xr - y/ for μ > 0. Then, for every function class F,
Eq [Rn Fl S pol [RnF],
(21)
where @ the function class defined by Φ == (0 o f: f F.. Definition A.2 (Sub-root function, et al., 2005, Definition 3. 1)). A function wh: (0, - [0, oo) sub-root if
nonnegative, nondecreasing and if vir) is nonincreasing for r > 0.
vF
Theorem A.3 ((artlett et al., 2005, Theorem 3.3)). Let F be a class of functions with ranges in Ja, b] and assume that there are some functional T: F >> RR+ + and some constant B such that for every I E F, Var [f] T()) s BP()).
12

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribation-Free Analysis in Spherical Covariate
Let de be sub-root function and let r' be the fixed point of v. Assume that satisfies, for any r v(r) 2 BR F: T()) S r)). Fix 0, then for any Ka 1, with probability at least 1 -e
Ko
704Ko r (11(b a) + 1-2BkK)
vf F. Ep ifls
Ep Ifl
Ko
n
Also, with probability at least 1 -
Ko +
704Kg B
p" x (11(b a) + 26BKo)
VFEF, Ep. [f]
Ep [f] +
Ko
Proposition A.4. Let F be class of functions with ranges in [0, b] for some positive constant Let 1p be a sub-root function such that for all 2 0. R(f E F: Ep [f(x]] S r]) S (b(),, and let r" be the fixed point of v. Then for any Ko 1, with probability exp( (xp every E F satisfies
Ko
704Kn
x (11 a) + 26bKo)
Er S
Ep, [ +
r +
(22)
Ko
b
B. Proofs for Theorem 5.1 and Corollary 5.2
Optimization
Lemma C.4
Generalization
Lemma C.5
Lemma C.3
Lemma C.6
Theorem C.8
Theorem C.10
Theorem 5.1
Lemma C.9
Lemma C.7
Theorem C.11
Roadmap of major results leading to the main result, Theorem 5.1. The uniform convergence results Theo- rem 6.1 are used in all the optimization results and Theorem C.8.
Figure I:
Proof of Theorem 5.1. We use Theorem C.10 and Theorem C.11 to prove this theorem.
First of all, with the condition on m, d in this theorem, Theorem 6.1 hold, and Pr (W(0) E Wol 2 1 - 2/n.. It follows by
Theorem C.11 that with probability at least exp (-O(nE?))
Er. [(5+ - {z]
<
+
ntt
2e
Plugging such bound for Ep, [(fe [+] in (118) of Theorem C.10 leads to
6
Ep [(f- - p-
+
3
( ww)
(23)
nt
2e
Due to the definition of T and 62 we have
2
22
<
<
< 25
(24)
nT
{ + 1)
13

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribation-Free Analysis in Spherical Covariate
Lemma C.14 suggests that with probability least 1 eepp 4exp(==(nee)) over S, Ex c Since T T, for any
t [&,T 7) we have
1
(25)
nt
n/T
nT
We have Pr [ol > 1- 11-2/ 2/n. Let = en verify that (0, 1). Due the definition of the fixed point, 0.
Since Σ A fx (xx, x)dx(xx = 1/22, we have
12
0 < w
Σ 12
min
En S
A S < 1.
2n
22
(10) then follows from (23) with o (25) and the union bound. The condition in (87) in Theorem C.10, together with ex and (25) leads to the condition in (9). Furthermore, T x=x e follows from (25) and ry +(1).
Proof of Corollary 5.2. We apply Theorem 5.1 prove this corollary.
is well known, such as (Raskutti et al., 2014, Corollary 3), that e x n _ā_1, It then can be verified by direct calculations that the condition m, (9) in Theorem 5.1, is satisfied with the given condition (11). It then follows from (10) in Theorem 5.1 that Ep [(7 - [*)²] S n 2
C. Detailed Proofs
Because Theorem 5.1 is proved by Theorem C.10 and Theorem C.I1, in this section, we establish and prove all the theo- retical results which lead to Theorem C.10 and Theorem C.11, along with the proof of Theorem C.10 and Theorem C.11.
C.1. Basic Definitions
We introduce the following definitions for the proof of Theorem 5.2. We define
(t) f(t) yy
(26)
Let < be a positive number, and 6o E (0, 1) is an arbitrary positive constant. For t 2 0 and T 2 1 we define the following quantities (or recall their definitions if defined before),
Cn mo/min {2, 2en) to0 + +1,
== n T
(27)
Vm
V. v-= = v R"
(I, n,,K), (S)).
(28)
E,r = e= e R", (I, - rT,,''''' w, S V
(29)
We define the set of neural network weights and the set of functions represented by the neural network during training follows.
W(S, w(O) = W: Et E [T] s.t. vec (W) = vec (W(0))
Σ
Zs (t' (t'))(t'),
14

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate
u((') E ERR, u((() - v())) + +((), v(() E Vy, e(l') E Ev. for all l' E [00,--113
(30)
W(s. w T) is the set of weights of the neural network trained by GD on the training data S and random initialization (O)) with the preconditioner M generated by Q and the steps of GD no greater than T. The set of functions represented by the two-layer NN with weights in W(s, W()), 7) is then defined as
FNN (S. (()), T) = {J+ = f(W()).) 3t E (T), W(I) e W(s, ((0).)))
(31)
We define the function class F(B, w) for any B, w 0 as
F(B,w) = [J: f +e, h Hx(B), leell s Sw].
(32)
We define the constant
Bn : nO + 1+ v2.
(33)
will be shown in Theorem C.8 that with high probability, the two-layer NN (1) trained by GD lies in the function class F(B,, w) where be sufficiently small with sufficiently large network width m.
We define
W. = (W)): (15), (16) hold]
(34)
be the set of all the good random initializations which satisfy (15) and (16) in Theorem 6.1. Theorem 6.1 shows that
we have good random initialization with high probability, that is, Pr [W (0) E Wo] 2 2/n. When W(0) E Wo. the uniform convergence results, (15) and (16), hold with high probability, which is crucial for our main result Theorem 5.1.
C.2. Theorem C.10, Theorem C.11, and their proofs with related theoretical results
Theorem C.10 (repeat). Suppose w E (0, 1) and m satisfy
m 2 max T d
16 /w3 T d33.
(35)
and the neural network ((W()),) is trained by GD in Algorithm with the learning rate = 0(1 E (0, 10,1/ on random initialization W(0) E Wo. and T < T. Then for every t E [7]. with probability at least exp (-O(n)) exp (-O(nE%)) exp (-ne,) over the random noise w and the random training features S,
1/2
Σ q=Q+1
Ag
BaQ n
Q +1 V
Ep [(fc- - 2Ep, ( < co min
+ w
+ Bn
+ COE (36)
oSQsa
n
Furthermore, with probability at least 1 - cxp (-O(n)) - exp (-O(nE))) - exp (-ne?) over the random noise w, the random training features S,
Er [(fe f^) 2Ep, [(ft - --) 66 w))
(37)
Here Bo, Co de are absolute positive constants depending on (oo and do also depends on do-
Theorem C.11 (repeat). Suppose the neural network trained after the 1-th step of gradient descent, Jr = (IW(),,) satisfies u(t) fc(S)- -y v(t) + ett with v(t) E V; and e(t) EG,r and T < T. If
1
E (1,2),
T T T/T
then for every t [TT, with probability least 1- exexp (-O(nE?)) ) over the random noise w, we have
3
mm +3) +3)
Er, - [2]
v
nt
2c
15

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribattion-Fee Analysis in Spherical Covariate
We have the following two theorems regarding the uniform convergence of ((W()) to (:.-) and the uniform con- vergence of Vn Fn( (W()).) to 2R Noting that d 2 4, Theorem C.1 and Theorem C.2 can be proved by using the proofs v2=x
of (Yang & Li, 2025, Theorem VI.7,Theorem VI.8).
Theorem C.1 (Adapted from (Yang & Li, 2025, Theorem VI.7) for d 2 4). Let (()) w, (w,(0)), m
where each
-=
w, (0) ~ (O, xaI)
for r E [m]. Then for any ò (0, 1), with probability least 1 ô over W(O),
sup XEX,EEX
K(x,y) - To (0)0),x.))) & (1(m,d,0)
(38)
where
2(1+2m) add
1 Vm
6(1+ 6(L+2BVV) + 11122ogg 2 2(1 + 2mm22
14log
+ 18
Ci d,
(39)
3m
and B is an absolute positive constant. In addition, when m 2 /(2d)) m/ log 2 d, and 6 x 1/n,
dlogm
Ci d,
(40)
m
Theorem C.2 (Adapted from (Yang & Li, 2025, Theorem VI88) for d 2 4). Let W(0) =0 m
where each
r=1
(0) ~ ~N(00 for E [m]. Suppose v 1, 2 1. Then for any 8 E (0, 1), with probability at least 5 over (()),
2R
sup xEX
ÜR( [())), x)
S C2 d)
(41)
2
where
C2(m, d, = =3/ d m to T
21og 2(1+2/m)
7
2( 2(122mm)
(42)
3m
In addition, when m 2 2/d, lo/log m 2 d, and 8 x 1/n,
C2(m, d, 6) S v ddm ,
(43)
Lemma C.3. Suppose
m m 7 / 16
(44)
and the neural network (t))), trained by gradient decent with the learning rate n O(1) E (0. 1/2) on the random initialization (0)) Wi. Then with probability at least exp (-O(n) over the random noise w, W(1) W(S, (O)), T). Moreover, for all l E [0, u(l) v() e(l) where u(l) 5() y, v(() E VK.. e(t) E EKAT. and [u((t]]2 cuvn.
Proof. First, when m 2 / with a proper constant, it can be verified that Em,n. S /TnnTT where Em.n. is defined by (54) of Lemma C.5. Also, Theorem C.1 and Theorem C.2 hold when (44) holds. We then use mathematical induction to prove the lemma. We will first prove that u(l) v() e(L) where v(l) Vr, e(l) E &L,,, and [|u((]]l2 s cu for for all & E [0,
When = 0, we have
((0) - ---=vv(0) v(0) cc0),
(45)
where v(0)= = -f) = (I (I- r,,,), f (S). e(0) = - = (0) + e0) with (0) = -(1 (I-,k, w and (0) = 0. Therefore. v(0) E Vo and e(0) E Eo Also, it follows from the proof of Lemma C.4 that ||u(0)]lz S cu with probability least 1 - exp ( (n)) over the random noise w.
16

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribatiio-Free Analysis in Spherical Covariate
= u(t)) with v(4i Vi, and e(f1) e, and [|](())]l2 Cuv'n for all [0, (). Then it follows from Lemma C.5 that the recursion u(t' +1 (I 1/Kk.) u(t) + E(t' +1) holds for all 1' E [0,t]. As result, we have
+e(i) where v(t1) Vr, and e(t1) (1(+))+ (22))) u(t1) Suppose that for all 1 [0, with t e [
u(t + 1) = [I 7)K (t) + E(t+
[I n) ) r+1 (*) (I- (I)) (+
+ Σ I
n R
1+1-1 E(t')
+ [) + e(t 1),
(46)
where v(t + and e(t 1) are defined
m)KK)*+ f*(S) Vit1.
(47)
e(I+1) == (I n/K,,, ++1
-1-nkk,,))
1y km) ++1-1 E((".
(48)
(1+1)
c2(++1)
We now prove the upper bound for e2(1 + 1). With v E (0, 1/21,, we have | 11-///nll2 E (0, 1). It follows that
[e2((+))) 13
I K
[E(())]2 3 TVM,
(49)
P=1
where the last inequality follows from the fact that [((1]22 S Em.n. S TVa/T for all 1 E [T] and the induction hypothesis. It follows that e(t + 1) E Elt1, Also, it follows from Lemma C.4 that
||u(t + 1)]12 S [[v([+ + 1) + @e((++ 1) + (02((+1){b
Ho
+ oa +r++) vn -n=-ovi coVi.
<
2en
which completes the induction step and also the proof.
Lemma C.4. Let t E [T]. v = (I nk,''' (S), e= -I- nIn)))))' w, and ry E (0, 1/21). Then with probability at least 1 - exp (-)(n)) over the random noise w,
||vll2 + ||ell2
Mo
oo +1 Vn.
(50)
/2em
Proof. When / 2 1, we have = - (I- m/,k'''' (*(S), and
Σ (1 nx:) 2t
n
2 nup (S)]
lv(()
[UT (S)]
Σ
(51)
2endal
2ent
==1
Here ! follows Lemma C.13, 2 follows by Lemma C.12.
Moreover, follows from the concentration inequality about quadratic forms of sub-Gaussian random variables (Wright, 1973) that
Pr || 112 - E [| n s (-x(())(n))
(52)
and E
[1 [ww] <
w/l Vioo. Therefore, Pr [l/w|22 Vnoo V (xp(-)(n))
17

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate
As result, have
||v|2 + ||e|l2 S
mpp 2en
||w|2 S
( /2e
Mu
+ o0 200+1) vn.
Lemma C.S. Let < for T 2 1, and suppose that [15((") yll2 S Cav/ holds for all S S S and the random initialization W(0) Wo Then
((t + y- KI, (5(11) - y) E(t
(53)
where |EE(t 1)122 E,,,, and E, E is defined by
E Em,,.r = 1/CuVn (a (1(22R, 2
2R + C2(m//2,,11/)) Ci(m/2,d,1//)) 2 ncuVdum TTT.
(54)
y112 Proof. Because - S
vnc, holds for all t' E [0, by Lemma C.6, we have
wT((t) w0/ R. vt
(55)
Define two sets of indices
EiR = fr E
w,(0) x > RR. E EiR
We have
1)
1
Ws (t (1+1)x;
T
Ws. (t)x;
VII
Σ ar TEEia
(t + +1)x1)
T
(ts.
TT
=D!1)
ar at (o(o
TT (1),
Ws. + 1)x:) (11x)
rEFiR
E
D +E E
(56)
and (2),, E() E RR" is vector with their i-th element being D (.") and E defined on the RHS of (56). Now we derive the upper bound for E For all i E [r]] we have
Σ (o (t), x;) (t) x3)
rEE.
Ws. (t + +1) x, -ts, Tx
Σ
Ws,r (1 (/+1) -ws,
V m
T
1 Σ
Zg ( (8(1) y3/18
T
18

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate
R
S
1/Cn
(57)
m
m
m
T
Here D, 2 follow from (74) and (75) in the proof of Lemma C.6.
Let m be sufficiently large such that R Ro for the absolute positive constant Ro x specified in Theorem 6.1. Since
((0) Wo. have
2R
sup
UR (((),
I C2(m//2,d,1mm
(58)
xEx
V2TK
where ū (W), (1 (o) =R) that (R() x.) -|Ei /mm. It follows from (57), (58) and the
induction hypothesis that
E (1)
S v/uu
2R
(22(m/22d.1//))
(59)
VTT
It follows from (59) that |E can be bounded by
2R
S ncuvv
+ C2(m/2,d:1/mn)
(60)
/2TK
D (1) on the RHS of (56) is expressed by
D = mm
Σ or
(o
T (s, -a (0(
rEE.R
Σ 0 (1)xx20)) (ws.r(++1) (1sr((+1)-ws.,(())) x;
V E
(1) 22200 (-" [Zs(0) 12ddrrdd (5(1) - y)) T x;
a,
( 2 Zs (t) [(- (f(t) - -y) T
+ Vm
Σ
ar II (s..
n
x,
rEE,
H()),, (5(11) y)
D
Σ
a Il (t) Tx200 (7 Zs(tt) Zs(()) (f(1) ((()--))) xi
mm
r
E
(61)
where H(t) E Raxa is a matrix specified by
H (tg
p X
m 2 I (0 2,20) 11 2,,00)
Vp in], [n].
2,20
Let (2), 2 E RD be vector with their i-the element heing o(2)) and E defined on the RHS of (61). E(2) can be
expressed by ((2) (2) (1)) y) with E(2) E gnxx and
5 (2)
1
Σ
T
(0T,000) 7( (w) (o) q220
Xg xp
< 1
Σ 1
E
E,
19

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate
for all p [n], [n]. The spectral norm of E(2) is bounded by
Fa.nl
! S n
2R V2TK
<
S
+ C,((m/2,d.1/n))
(62)
m
where I follows from (58). Also, [H) s [H())|: S VnN for all 2 0. It follows from (62) that | bounded by
||, can be
E
<
"
2 [lx(() yyll2 S nanv (2
2R
(2((m/2,d11/n))
(63)
12TKK
D on the RHS of (61) is expressed by
D --==- - (F(1) -y) -- (5 y)+ 7 (K H()) (5(() y) + 7 (H(0) H(() -1 y)
n
D(3)
B(8)
= D + 3 + E(4)
(64)
On the RHS of (64), D E E(4) E R are vectors which are analyzed as follows.
((3) is bounded by
K - H(O)) S K - H(O) S (m
(65)
where the last inequality holds due to W(0) E Wo-
In order to bound E(4), we first estimate the upper bound for (H, Hi)( for all i,j E [n]. We note that
11
[.] + II {1 [w.. (ww..(()- (0)-00]))))]])
(66)
( ( x.J (m)r)) Tx
It follows from (66) that
H
(t) (0)
TT
X xj
11 (05. 2.20 T (1.,000
I (w ( (w.(0) 2,20))
m
1
1 +
111 r=1
(1w xTx0 (w:.000 2,
( x2,20) #1 (wir(r))) x
1 m
(0) x [R]
+ 1 w. x, [R)
+ 2II
m
1
4R
$ UR( (0(), x.) (W(()) x,)
(C)(m/2,d.11m))
(67)
2TK
where ① follows from (58).
follows from (65) and (67) that (3)
| 1|, are bounded by
77 K (()))l21) yll2 7 n nC (m/2 /,, 1/n)) [|y(t) y1l2 ncu (
(68)
R
E
7
H())- H(t)ll2 15(t)
-1l2 -
7
4R
+ 222g(m/2, d. 1/m) d.,
(y((t) - -yl2
n
n
2mT
4R
I
nnvvn
+ (Cs(mm/2d,11//))
(69)
22m
20

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribation-Free Analysis in Spherical Covariate
E It follows from (61) and (64) that
D = ! + +E, E
+ E
+ E.
(70)
then follows from (56) that
= -D + E = D E + E + E
(3)
E,
" =- (f()) -y) E,,
(71)
where R" with its i-th element being E,, and = E(2) + E(2) + E(3 + EE()) then follows from (60), (63), (68), and (69) that
Ell2 S n/u Mua (1(2
2R
(2(V V2TK
+ C2(m/2,d,11/n) + (c1(m/2,d.1/mm)
(72)
Finally, (71) can be rewritten as
y) y) (1-+)-y-11""k) (
-(++))- "
BLL++))
which proves (53). The upper bound for 12 in (54) follows from (72), Theorem 6.1, and noting that rjCu S +(1).
Lemma C.6. Suppose that / E [0:T TO:T-111
- 1] for T 2 and ((') yl1 S vncu holds for all 0 s t' S t. Then
ws.r (t') (t.)- < R
0A stt1.
(73)
Proof. Let [Zs(() 1)d:rd denotes the submatrix of Zs(() formed by the the rows of ZQ(() with row indices in [(r- 1)d
rd]. By the GD update rule we have for every t" E [0, T 1] that
(t" +1) Ws. (t")
[zs (t") M (f((t)) - -y),
(74)
We have [Zs((")) [[ -1)drd 1 vnmm It then follows from (74) that
ws.r (1" + -s. (1") ||- s n
| [ts (("))) 18((")) yll2 S
1uCu vm
VI" [0:4]
(75)
Note that (73) trivially holds for t' = O. For t' [1, 1]. it follows from (75) that
ws.. (t))
Ws (t" 1 (s.) s
17 m
Cu S
noT vm
R.
(76)
1s
which completes the proof.
Lemma C.7. Let h(.) Ei= h(,,t') fort E [T].T < f where
h(,(() = v(,,t') + +(),(),
o(,t') = Σ K(x,, (t)) 1=l
a(,tt) = x(x,,x)e,(t),
j=1
where v(t') E Ve, e(t') Ee.r for all 0 < t' < 1. Suppose that S 1/(7T), then with probability at least 1 - exp (-O(nEt)) over the random noise w.
|1lllxx Bn = No +1 V2,
(77)
and B3 is also defined in (33).
21

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate
Proof. We have y = f(S) w.
w. v(t) - -
"k,,,,,,' f*) et) + +z(() with e1(() (I )-1)ka) w.
o & vnt. We define
" x (o((t)) (2(,8)= = "> n n
Σ x(x [o2(1),
(.,t)
n
Let Σ be the diagonal matrix containing eigenvalues of Kn, we then have
Σ oxxx(')= 3 (1 (k-)),))* v),)) [()))) K(X,,x)= " U UTr()) K(x,,x). (78)
P==
j=
j=1(=0
follows from (78) that
1p (S)
Σ -==
v (()t')
(-- ) U KU
XuΣen
[I --- Eー) U (S)
n
Hx
p==
p==
(1 (1-
(1=n nタ.1 n
-
- (K,,,
(K,)
1/2
Σ -I-
t-1
U (S)
S
[UT r())], S 1/.
(79)
r'=0
i=1
where the last inequality follows from Lemma C.12.
Similarly, we have
1- 11 n121) (1(1))))))
)²
Σ K=0
a ( ()
[U w]?
(80)
X;
1=1
It then follows from the argument in the proof of (Raskutti al., 2014, Lemma 9) that the RHS of (80) is bounded with high probability. We define a diagonal matrix R E Rax" with R. = (1 - (1 (1-11 (1-nA))) 2 /%, for E [n]. Then the RHS of (80) is 1/n- tr (URUT T.RUWww]] It follows from (Wright, 1973) that
Pr [1/n (URUT wwT - [1/n (URUT ww T)] 2 u| S exp (-emin {
nu/ R112, n2u? [/2
(81)
for all u >> 0, and c a positive constant. Recall that 17: nyt for all 2 0, we have
11- - v/A,)
E [1/n- (URUT wiRU 00
Th X
oie
min
{
mede
71
2;
n
med,
of
min
11
T
min
1/1 X = o.
R2
(1/m)) $1.
(82)
1=1
Here ! follows from the fact that (1 - ,T7.)'' 2 max (0, - 1n and 2 follows from min {a. b) S vab for any
nonnegative numbers a, b. Because t < T' < T. have Rx( 1//m) 1/(o)))) so the last inequality holds.
Moreover, we have the upper bounds for RR|/2 and |R]| as follows. First, we have
- (1-1At nZd)) (1-n%)) )²,))²
R 1g < max
max min
- th 7
n
(83)
/E|n]
X;
eE ml
Ai
22

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate
We also have
1 ( m2,) (1-nx)) x)))²
|R|
7/
min
72
(2,)2
==1
min
X;:
-
1
=
Rxx
( V 1/1x)
S
0
1/1
(84)
where 2
follows from
Tidd }
1
min
The
X2
X, min
j
n//28
Combining (80)-(84) with u in (81), we have
Pr |1/n- tr (URU) www] ) - E |/n tr (URU ww ]] S exp (-cmin {n/m, n
S exp (-ne' /m)) S exp ( (-c' nE
where c' = cmin {1. [ and the last inequality is due to the fact that 1/m, 2 Ea since t s TT- S f. It follows that with
probability at least 1 - exp ( (-O(nE))) | 2 t')
2
Ax
We now find the upper bound for
Σt ēσ(. 07
We have
Hx
-T
|0z( 1lx
(()))((t)
I
n2
n²
so that
STIVAITSI S1,,
Σ (2()
(85)
Hx
if T 1/(TT)
Finally, we have
[1bll 1
Σ P==
((1z)
+ Σ aa(t))
Σ te( o=
+10 v2 = Bb.
Hx
76x
HK
Theorem C.8. For every & E [T]. let the neural network f()) = ((W()),) be trained by gradient descent with the learning rate 0(1) E (0. 1/x)) on the random initialization (()) E Wo with T < T. Then with probability at least 1 - exp (n)) exp (-)()))) over the random noise w, f E (N W(O), T"), and f can be decomposed by
f h + F(Bn, w)
(86)
where h E Hx (Br) with Bn defined (33), e E L When
m 2 max
16 T d3 [T w T d3
(87)
then
||e|l.c I w.
(88)
In addition,
B
1l <
+
(89)
22
23

---

Following from the proof of Lemma C.6 and Theorem C.8, under the conditions of Sharp Generalization for Over-Parameterized Neural Networks: A Distribation-Free Analysis in Spherical Covariate
Remark. We consider the kernel regression problem with the training loss L(a) =1/2- | yll Letting K. a and then performing GD on & with this training loss and the learning rate 17. it can be verified that the kernel regressor right after the t-th step of GD is
f-1 n K(,
(UNTK)
! n1 L'=0
(
(90)
where (e()) = (In nk,))²
Theorem C.8 we have
h1 = Ft ANIKI + +,2(,,t)
- @2((t) and et appears in the definition of Et,r in (29). It is remarked that in our analysis, we approximate ft by hr (B(B)) with small approximation eπror w, and we do not need to approximate fi by the kernel regressor jt (iNIK) with sufficiently small approximation error which the common strategy used existing works (Hu al., 2021; Suh et al., 2022; Li et al., 2024). fact, our analysis only requires m is suitably large so that the Hk-norm of (2(,,t) t) = f4 - f.NTK) is bounded by a positive constant rather than an infinitesimal number as m - xc, that is, [ 0l S 1, which is revealed by the proof of Lemma C.7.
where ē2(,,t) n Er K(,,x,)
Proof. It follows from Lemma C.3 and its proof that conditioned on an event with probability at leastl exp (n). E (S, W(O), with W(0) E Wo. Moreover, f(-) = s(W,)) with w = W vec (W)- vec (Ws) vec (W(0)) Ee=D n//n Zs ((')) for some / (T]. where u(t') R. u(() v(()+e(!) with v(t') Ve and e(t') E E for all t' E {0,t - 1].
m
r=1 E W(S, W()), and
W, expressed as
H- Σ
W, (t. (0)
" Zs ((r)) 1)drrd u(t'),
(91)
n
where the notation Ws,r emphasizes that w, depends on the training data S.
We define the event
(R) = {[ (-( S <R. E [m].
We now approximate S(W, x) by g(x) = 1
Em ar II
(0) W. x. We have
vm
If(W x) - g(x)
m
a,o x x - Σe ar ( (0) x
m
wr
m
ar (I(E,(R)) + 11 1(
(0
(0(w,)
0
w w.
TT
11 (0) W,
m
TT wxX)
(R))
- I (w.(00)xx0) W
V
W x - o (w) [x) - [ (w, (w.- (0))
(E)(
0
2R
m2
(())
(92)
m
24

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate
Plugging R neaI vm
in (92), have
2R m
1 m
If(W, x) - g(x) -
[E) = 2njouT.
1 (R)
m
r=1
2R
= 2ma 0R( (W(O), S 2nc
+ (2(mm/2,d11/n))
(93)
V2TK
Using (91), we can express gxx) as
g(x)
1
a
11
w.(
Σ p==
w. [x) 22 [Zs(t 1[d-r)
1)dird] u(t?)
V m
112
R
Σ [x20
II (w.(e) uy xt)xxxxxx X,
(94)
Tum
Gx)(x)
where ! follows from the fact that
Em=1 a, 11 [w x = due to the particular initial-
x f(W(O),
vm
ization of the two-layer NN. For each Gy the RHS of (94), we have
n Σ
m
n
Gp (x)
Σ
II w- x20]
u, x+
"
(- 22,00 Tx,00) xx)x x
nm
nm
(0
x20
5=1
m
n
K K(x, x; ), + ? Σ
9 u (t') +
11 (0) xx20 Σ de (t))x,
(95)
n
1= (x))
-x(x
where
de 11 [..(00] x,20] 1( (0,200)3,20))
in 2, and and for all j [n] in A
qj = (W(),, (0),, - x(x,,))
We now analyze each term the RHS of (95). Let h(, t'): X + E be defined by
n
4(x, (') = 1
K K(x, (t), Σ
j=1
then h((,tt) is an element in the RKHS Hx for each t' E 10, - 1). We further define
1-1
k(-) = Σ M(,
(96)
Since W(0) E Wo. qj S Ci(mm/2 /, d, 1/n) for all E [m] with (1 d, 1/n) defined (39). Moreover, u(t) S cuvn with high probability, so that we have
E 10
= !
(t)
< !
[
( 1/n).
(97)
25

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate
We now bound the last term on the RHS of (95). Define X E Fdx= with its j-column being X 1 E (oel"[(w000 (0) x (x)x))) de de nnx x for all j E [m]. then Ex(x) = (X'u(t)) x.
We need to derive the upper bound for |X 1l.-
Because
(w))
S R. it follows that 11 (..(e)Tx,22)
I [w. when w.(() > for all j' E [n]. Therefore.
Idv
11 (w-(0)Tx220f -I
( x,200 S 11
and it follows that
1l w. (0) (0)0))x 2, 2,200 desrss
de
I [.))
UR (()), x,)
2R m
m
+ C2(m//2,d11/))
(98)
2
where Un is defined by (14), and the last inequality follows from Theorem C.2. It follows from (98) that | 112 S
vn
2R V2Kk
+
C2(mm/2,,, 1/1)). and we have
- " x (11ll((())l22xx(( 7/uu
2R
+ (2(m/22,,11/))
(99)
2TT
Combining (95), (97), and (99), for any e' E 10, - 1],
|[,r(x) - h(x, t') 1l) $ || + | 1xx
2R C2(mm/2,d1//))
S nCu (m, d, +
(100)
/2TK
Define e(-) = /(W,-) - -h.)), then follows from (93), (94), and (100) that
[e(x)]l & Ilf(WW :) glooo + l1g l1
t-1
< 11f((,,.) 2l1 + Σ
|c - -h(-, -'(,,t)lloo
==0
2R
< TTcaT
+ C2(mm/2,d, 1/m)
/2TK
2R
+ nat
(m//2,d,11m) + V2Tk
+ +C/(m/2,d:1/m)
2R
S n T
(1(m/2,d.1/n) +3
+ +22(m/2,d,1/m))
2TT
(101)
We give estimates for Am,,,Mo.m.. Since W(0) E Wo. it follows from Theorem 6.1 that Ci (m//2,,, S log ddm Ti, and 2R/(V22R2)))) + C2(m/2 d, 1/n) S Vdm frrb. As a result,
m
A Amn.N.amt S ddm T//2
By direct calculations, for any w > 0, when
m 2 8 40
18
26

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate
have A, w.
It follows from Lemma C.7 that with probability at least - exp (-O(nE))) over the random noise
||lllux - Bn,
(102)
where B, is defined in (33), and 7 are required to satisfy
T 1/(nT)
Lemma C.3 requires that 2 T9/3/7 As result, have
m T d
It also follows from the Cauchy-Schwarz/ inequality that || S Br/V2. This together with (101) proves (89).
The following lemma gives the upper bound for the Rademacher complexity of localized function class in F(B, w) comprising functions with their norm bounded by every > 0.
Lemma C.9. For every B, w 0 everry > 0,
Hi [[B, Ep [5]] sr]) S (r),
(103)
where
1/2
Σ A
(VF+ Q
9=Q+1
(r) = min Q: Q20
BB
+
(104)
Proof. We first decompose the Rademacher complexity of the function class {f E F(B,w): Ep [ta] S sr) into two terms as follows:
H (ff: E E w), Er [s²] {r}
E
sup (EF(B,w):
+ +-E
sup
Σ [,((x;))
(105)
PS 1=1
(E) Edlfisr s=1
R2
We now analyze the upper bounds for R1, R2 on the RHS of (105).
Derivation for the upper bound for R1.
For any / E F(B,w) w). we have f = h with h E Hx(B), E L ./ello S w. When Ep [s?] & r. follows from the triangle inequality that [|A]| I [lfllr= + ||l|| S vr + = Th.
We now consider (B) with |AAl S Th the remaining of this proof. We have
a Σ σi (M(x;) + e(xi)) h, Σ o.
[a.((x)
a,e(xx).
(106)
HK
Because (ug)12) an orthonormal basis of HK, for any 0 < Q S n, we further express the first term on the RHS (106)
as
Hx
27

---

Sharp Generalization for Over-Parameteriaee Neural Networks: A Distribution-Free Analysis in Spherical Covariate
1
v Ag (h, Ux Ug
o,K(, xi), U1
Uq
h
(1 x:),
Uq
Ag
HK
HK
?>
i=1
HK
Hx (107)
Due to the fact that HK. h
Σ
00
Bi
(1)
0q
Σ
8
v 11 (k)
cq
with Ulg
20 Ngego Therefore, ||
Σ
2 / and
q=1
q=1
Q
Q X G
Dg (h, vod Uig
Ag (h)
Uq
( S &1bbll1> S TM
(108)
Hk
9=1
Hx
9=1
According to Mercer's Theorem, because the kernel is continuous symmetric positive definite, it has the decomposition
k(,,x,) (xx)),
so that we have
Σ
of
Xzeje;(Xi),,
Σ i=1
Xxe)(x;)
10g. U1
1=1
Hx
i=1
j=1
Hx
j=1
HK
n
Σ
(109)
Combining (107), (108), and (109), we have
1
x
h
(-K x())
Ag (h, vg) Vo
Σ
o, xx)) U0
Vq
9=1
7x
9=1
HK
HK
+ *|MllH
Σ
a K xi), Uq
Q=Q+1
HK
HK
Q
< | 12
+ B
a (x
9=1 i=1
Hx
@+++i=1 i=1
HK
STh
Σ
Σ
J,Co (xi)
(xx)
+ +B,
Σ @=++1
Σ oi A
(110)
where ① is due Cauchy-Schware inequality. Moreover, by Jensen's 'ss inequality we have
Q
n
2
Q
27
Q
E
Σ
Σ
(x:i
S
E
oie
<
xx))
VnQ.
(111)
q=1
and similarly,
2
x
30
Σ
o, / Ag c (x))
E
Σ
A
2 xx,
n1
Xg
(112)
q=Q 11
1=1
c=Q+1
1=1
q=Q+1
Since (110)-(112) hold for all Q 2 0, it follows that
1
E
sup (B). Sri,
xx)(
<
min
TbV TTVRQQ nQ + B
Σ Ag
(113)
Q: Q20
9=Q+1
28

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate follows from (105), (106), and (113) that
Σ
Xg
R1 n
sup (B) blll Smh
Σ (x))
min Q: Q20
Th
B
q=
(114)
n
71
Derivation for the upper bound for R2.
Because 1n o;e(xx) I w when leeloo S w, have
R₂ v -E
sup
Σ ,e(x)))
S w.
(115)
EELMM ||ell Sw
follows from (114) and (115) that
1/2
Ag
n (( [ sT))
min
Th
+
B
q=Q+1
+ W.
Q: Q20
n
Plugging Ta in the RHS of the above inequality completes the proof. Theorem C.10. Suppose 10 and m satisfy
m 2 max T / /w r
(116)
and the neural network ((W()),) is trained by GD Algorithm with the learning rate rj O(1) (0, 1/A1) on random initialization (0)) E Wo. and T < T. Then for every t E [T], with probability at least cxp ( (-((n))
exp (-O(nE?)) exp (-ne over the random noise w and the random training features S,
1/2 2
x
Ep [Ift f -2Ep. [Ife f- <
min 05Q5n
BoQ +
Q +1 (
+ Br
q=Q+1
+ cus
n
(117)
Furthermore, with probability at least 1 exp (-A(n) - exp (-O(nE?)) exp (-n=?) over the random noise w, the random training features S,
Er ( 21Er, - (()e - cG(E? + ww)
(118)
Here Bo, Co do are absolute positive constants depending on Po. and dp also depends on do-
Proof. We first remark that the conditions on m, (116), is required by Lemma C.3 and Theorem C.8.
follows from Lemma C.3 and Theorem C.8 that for every t E [T], conditioned on an event with probability at least exp (n)) exp (-O(nER) over the random noise w, we have W(I) E W(S, W T), and
J(W()),)
((0),
Moreover, conditioned on the event Q
ft F(Bn,w)
29

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate
We then derive the sharp upper bound for Ep [(/e ] by applying Theorem A.3 to the function class
F= { F= (f- E w)
Let Bo = B2/v2+1++ + 2 Bn/V2 + w + uo/ 222 then we have || < B with F F, so that Ep [Fa]] S
BP [F]. Let T(F)= = BBEp [F] for F E F. Then Var [F] S Ep F2] - T(F) = B [F].
We have
2 ( E F: T()) (r)) = 28 ( f W) -(f 1E & r
(11-F:SEF(B, Rr Ep [(s
m3 B7 )
RB
4B
{( w): Ep
[
r
(119)
4B3
where ① due to the contraction property Rademacher complexity in Theorem A.2. Since f E F(Bn, w). f F(Bn, w), we have I-ft E F(B,, w) due to the fact that F(B,, w) is symmetric and convex, and follows that 2 holds. follows from (119) and Lemma C.9 that
(( {f: F(Bn, W. [ S
2 E F: T(F) s1))
4B3
r
4Bg
B
= (rr).
(120)
4B3
s defined as the RHS (120) a sub-root function since it is nonnegative, nondecreasing and *(r) VF
is nonincreasing. Let
r* be the fixed point of vi and 0 r* follows from (Bartlett al., 2005, Lemma 3.2) that S s vbrr) Therefore, by the definition of in (104), for every 0 < Q S we have
4 B 1B
1/2
Σ Ag
VF
q=
+ w
V
+
Br
+ W.
(121)
4B3
2Bo
72
Solving the quadratic inequality (121) for we have
8
1/2
Σ
Ag
8B$Q + 8B
Q V n
g=Q+1
<
+1
+ Br.
(122)
71
(122) holds for every S Q S n, so we have
1/2
Σ Na
1 Q ( +1
r S 8B min 0sQsn
BoQ + w
+ Bb
9=Q+1
(123)
n
n2
It then follows from (120) and Theorem A.3 that with probability least 1 exp(-xx over the random training features
S.
Ko
s$ x (11B3 + +6B3
704Ko
Ep [(fe
Ep,
[[fe
(124)
Ko 1
B
30

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate
or
Ep [[fe f-)]] p, [(fe 2 r
(125)
with Kg = 2 in (124).
follows from (123) and (125) that
Ep [[1
- -M p, [(Se --]
1/2
Σ 2y 9=Q+1
BoQ
Q + w (V +1
S
min ogQSn
+ Bh
+ =
n
Let x = net the above inequality, and we note that the above argument requires Theorem C.8 which holds with probability least 1 exp (-O(n)) - exp (-O(nE))) ) over the random noise w, then (117) is proved.
We now prove (118). First, it follows from the definition of B in (104) that
(rr)
4B m
ABB
x
1/2
Σ
An
4B min Q: Q20
VF
V
+ B
Q+1
+ 4B
2Bu
n2
1/2
Ag
< 4B BR
min
Qr
+
q=Q+1
4 4B3 w
(v2 +1
Q: Q20
4 4V2B Br
ooRk + 8B8 = (1)),,
where the last inequality follows from the Cauchy-Schward Schwarz inequality. can be verified that 4/1 (r) is a sub-root function. Let the fixed point of vi (r) be ri. Because the fixed point of oo (v((vrrr function of is e it follows from the properties about the fixed points of sub-root functions in (Yang & Li, 2025, Lemma B.9) that
32B B 2
r < max
1 E 16 w.
(126)
then follows from Theorem A.3 with Ko = 2 that with probability at least - exp(-xp
Ep [(f: } 2Ep, [(fi - f() -ri+ x n
Letting nez, then plugging the upper bound for rf. (126), in the above inequality leads to
Ep ((fe-fti 2E,. [Ife - 16
(127)
which proves (118). Again, we note that the above argument requires Theorem C.8 which holds with probability at least - exp (-O(n)) exp (-O(nE)) over the random noise w.
Theorem C.11. Suppose the neural network trained after the 1-th step of gradient descent, St = S(W()))) :), satisfies u(t) fe(S) = v(t + e(t) with v(t) E V2 and e(t) E E,rr and T < T. If
1
"1 (1,2),
T
(128)
r/T'
31

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribution-Free Analysis in Spherical Covariate
then for every & (T), with probability at least 1 exp (-O(nE))) over the random noise w, have
3
L
Ep. [(f= - f-)
+3
(129)
2
Proof. We have
f(()) v(t) + e(t),
(130)
where v(t) E V4 e(t) & ē()
ē()= = e1 + ē2(() with e1( -II, k)) w and @e20)]1 Vir. We have
mn () n E (). It follows from (130) that
Bp. [If - ,7) 1 [1 (S)]] n [[(((() + +
1 n
(I - (1m) (*) (In (In -(KK)') w = ||-
! Σ (1 n2,) 2 U
[ (*) [S) | + 3 n Σ 1 (1 (1- =2,)) -1--
[U w] =
3p0
3 Σ
(1 - (1-(1-1)) (1-1)=))))) [U')]] 2
+
w
+ 3T²
2enl
π1
3
1D
+
Σ
(1- (1- ))o))) 71-)))) w
7/
2c
17
n i=1
Ex
3
HD
+1]
+ 3B
(131)
ntt
2e
Here ① follows from the Cauchy-Schwarr inequality, @ follows from (51) in the proof of Lemma C.4. We then derive the
upper bound for Eg on the RHS of (131). We define the diagonal matrix R E Raxn with R = (1 - (1 - -)x)))) Then
2
have
Eg = 1/n tr (URUT ww])
It follows from (Wright, 1973) that
Pr [1/n- tr (URUT ww T) E [1/m- tr (URUJ ww T)] 2 u] S exp (-emin [nn/ n2uu² n222 /||]] -132)
for all u > 0, and c is positive constant. With m = myt for all 1 1 0, we have
oā n (1- 17,1)
1
o
ob Σ min
1 {
E [1/n (URUTTm ww "]
min
1,
m
X2
{
The
X3
72
n
1/1
1
1
min
on
1/m) <
(133)
K
1/1
Here ① follows from the fact that (1 - 7) > max (0, (0,1 - indi }. and 2 follows from min {a. S vab for any nonnegative numbers a, b. Because t < T < T. we have Rx( / 1/me)) S 1/(0)))), so the last inequality holds.
Moreover, we have the upper bounds for |RIl, and |R]| as follows. First, we have
1 (1-(1- (1-n%))) s min {1, 1
R| Σ max
(134)
xe|n|
32

---

Sharp Generalization for Over-Parameterizee Neural Networks: A Distribution-Free Analysis in Spherical Covariate
We also have
1- R Σ (1- (1-(1-n2))
n
n = n
min
71
min
1 17t X1,
- R (V1/n)) -
n
T
(135)
If 1/1 S (),) then min { 1/me: n1 (x,)*) - 1/me- Otherwise, we have of-77 < 1, so that n/ < and follows that
min
(1/m, n (2,))) & npp $ 7e. As a result, @ holds.
Combining (132)-(135), have
Pr [1/ tr (URU*) ww T) - [1/n (URU wwwwwww *)] 2 u/ S exx (-en {u, nZ
Let 1/n in the above inequality, we have
exp (-on cn min {u, u² mPog))) exp(-cn/ S exp (-d'nz))
where c' = emin {1, [1,0)} } and the last inequality is due to the fact that 1/me 2 E since t S T S T. It follows that with probability at least 1 exp (-)(
2
E. S u
(136)
11t 7
then follows from (131)-(136) that
3 77
BB 2e
Ep, [[ee |-)
S
+
holds with probability at least exp (=d
C.3. Auxiliary Results about Reproducing Kernel Hilbert Spaces
Lemma C.12 (In the proof of (Raskutti al., 2014, Lemma 8)). For any Hx (Ko), we have
UT f(S))
1
2
(137)
X
i=1
[UT |(S))
Similarly, for f E Hgs (Ho), we have 1 E
S n
A;
Lemma C.13. For any positive real number a E (0, 1) and natural number f, we have
- a)² se tta S cta
(138)
Proof. The result follows from the facts that log(1 - a) S for E (0, 1) and suPweR ue < 1/e.
Lemma C.14. (Yang & Li, 2025, Lemma B.7)] With probability at least 2exp(-O(ns
e S c
(139)
Furthermore, with probability at least 1 - 2 (xxp(-)(ne22))
C x
2
(140)
Here e₁ is an absolute positive constant depending on do-
Remark. Lemma C.14 shows that with probability at least 4 4exp(-0(ne))) =3 x En which is also a fact used in kernel complexity or local Rademacher based analysis for kernel regression in the statistical learning literature.
33

---

Sharp Generalization for Over-Parameterized Neural Networks: A Distribation-Free Analysis in Spherical Covariate
D. Simulation Study
as a i.i.d. sample random variables distributed uniformly on the unit sphere in R ranges within [100, 1000] with a step size of 100. We set the larget function to (x) = s x where 8 ~ Unif (X) is randomly sampled. We also uniformly and independenly sample 1000 points on the unit sphere in 1250 as the test data, We train the two-layer NN (1) using either GD by Algoirthm 1 or GD by Algoirthm with m > n² on NVIDIA A100 GPU card with learning rate 1 0.1, and report the test loss in Figure 2. It can be observed that early-stopping is always helpful in training neural networks with better generalization, the test loss initially decreases and then increases with over-training. Figure 2 illustrates the test loss with respect the steps (or epochs) of GD for of GD where minimum test loss is achieved, denoted by En. which is the empirical early stopping time. We note that the theoretically predicted early stopping time is 1 x n2/(22))), and we compute the ratio of early stopping time for each n by t,, (,./)/(2d-11,, Such ratios for different values of n are illustrated in the bottom right figure Figure is observed that the ratio of early stopping time roughly stable and distributed between [8, 10]. suggesting that predicted early stopping time is empirically proportional the empirical early stopping time.
We present simulation results for GD this section. We randomly sample n. points x
i=1
100, 500, 1000. For each n in [100, 1000] with step size of 100,
find the step
Training Data 100
Training
0.7-
0.6
Test Los
0.4
0.3
0.4
0.2
0.1
200
400
600
800
1000
500
1000
1500
2000
Step GD
Step GD
Training Data Size
1000
Ratio of Early Stopping Time
0.6
15
Text Loos
0.4
10
0.2
5-
500
1000
1500
2000
0-
Step of GD
200
400
600
800
1000
Training Data Size
Figure Illustration of the test loss by GD
34


Reviews:
[{"review_id": "uJqpx2kp6x", "reviewer": "Reviewer_pA14", "summary": "The authors study risk rate convergence of the infinite-width NTK for two-layer neural networks with ReLU activations trained with gradient descent and early stopping. The authors present theoretical results that relax some assumptions made in prior work: specifically it is common for results to be derived on data sampled uniformly from the hypersphere and the authors recover these results under data on the sphere that does not require uniform sampling.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We appreciate the review and the suggestions in this review. The raised issues are addressed below. In the following text, the line numbers are for the revised paper.\n\n**(1)\"... It seems like the authors here are trading off one somewhat restrictive assumption (uniform spherical data) for another (fix the second weight layer to random +1/-1 weights).\"**\n\nWe respectfully point out that the training setup (fixing the weights of the second layer to random +1/-1 weights) is not an assumption, and such training setup reduces the training cost by not training the second-layer while obtaining a neural network with sharp risk bound. Such training setup has also been used in the prior analysis of the generalization of two-layer neural network such as [Du et al., 2019].\n\n**(2)\"The paper Ko & Huo (2024)…\"**\n\nIn this paper, we focus on the generalization analysis of neural networks with algorithmic guarantees, that is, the generalization bounds for neural networks trained by gradient descent or its variants. Such analysis is of particular practical importance since the neural networks used in practice are mostly trained by GD or its variants.  Although the work mentioned in this review, Ko & Huo (2024), provides certain risk rates, as mentioned in lines 181-182, it does not provide algorithmic guarantees and the neural networks achieving such rates are not trained by GD or its variants.\n\n**Novelty of This Paper**\n\nWe would like to emphasize the novelty of this paper, which gives the first sharp nonparametric regression risk bound without distributional assumptions on the unit sphere. Our analysis introduces new proof techniques including the new uniform convergence results for NTK and the novel local Rademacher complexity based analysis (acknowledged by Reviewer EyzF Reviewer JB4U) which lead to the distribution-free generalization bounds with spherical covariate. Our results also give better lower bound for the network width compared to the existing literature. Furthermore, in our response to Reviewer JB4U (points (1) and (2)), we provide detailed discussions about (1) how to extend our work from a two-layer neural network to a deeper neural network, and (2) how to relax the assumption that the target function $f^*$ is in a ball RKHS of constant radius. The current novelty and contributions together with such extension and relaxation would benefit the theoretical deep learning literature with new insights and proof strategies.\n\n**References**\n\n[Du et al., 2019] Du, S. S., Zhai, X., Poczos, B., and Singh, A. Gradient descent provably optimizes over-parameterized neural networks. ICLR 2019.", "claims_and_evidence": "The claims are well supported by proofs which do not rely on uniform spherical data. The scope of the paper itself seems fairly incremental and the results seem to be largely a verification of existing theoretical results in this slightly relaxed setting. It looks like the proofs offer some novelty in proof techniques.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "Did not check proofs in detail but skimmed them & the proof overview and it looks reasonable", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This work contextualizes their results in many related work", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "It seems the main results of this paper are moving from uniform spherical data to spherical data (not necessarily uniform), and showing that this setting recovers optimal rates from existing work. Further this paper works in the setting where only the first layer weights are trained and the second layer weights are initialized randomly and fixed whereas it seems the prior work trains all layers of the network. It seems like the authors here are trading off one somewhat restrictive assumption (uniform spherical data) for another (fix the second weight layer to random +1/-1 weights). I'm not sure if I see one assumption as more restrictive than the other.\n\nThe authors also reduce the lower bound on the width of the network required to achieve optimal rates, which seems to be a new contribution (I am not familiar enough with the literature to know). \n\nOverall the contributions seem incremental but altogether can provide a useful basis for future work studying generalization bounds, hence my score.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "The paper Ko & Huo (2024) seem to have different relaxations of the data distribution that don’t even require data being on the hypersphere either, are they comparable to the results in Table 1? If so, would the authors consider explaining more the relationship between these two? As far as I can see they also give some rates?", "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": "", "extra_scores": {}}, {"review_id": "cGDsQUZFlH", "reviewer": "Reviewer_EyzF", "summary": "This manuscript contributes to the generalization analysis of overparameterized ReLU neural networks (with one hidden layer) in the context of nonparametric regression tasks.  The training data $\\{(\\overrightarrow{x_i}, y_i)_{i=1}^n\\}$ is assumed to be such that $\\overrightarrow{x_i}$ are drawn from a unit sphere $\\mathbb{S}^{d-1}$ in $\\mathbb{R}^d$, while the response $y_i$ is generated by a target function $f^*$ belonging to an RKHS ball $\\mathcal{H}_K$, perturbed with random sub-Gaussian noise. \nSpecifically, consider $\\widehat{f}$ to be such a neural network trained by gradient descent with constant learning rate and early stopping, it is proved that the expected risk $\\mathbb{E}[(\\widehat{f} - f^*)^2]$ converges to $0$ at a rate $\\mathcal{O}(\\varepsilon_n^2)$, where $\\varepsilon_n$ is the critical population rate of the NTK associated with the network, and $n$ is the number of the training data. Notably, this result holds without imposing any additional distributional assumptions on the input $\\overrightarrow{x_i}$. As a corollary of the above-mentioned main result, consider the special case when the eigenvalues of the integral operator associated with the reproducing kernel $K$ decays polynomially, the minimax optimal rate $\\mathcal{O}(n^{-\\frac{d}{2d-1}})$ in nonparametric regression can be obtained.  \n\nSimulation studies are presented at the end of the Appendix to illustrate that the ratio between the \"empirical early stopping time\" and the \"theoretically predicted early stopping time\" remains stable across different values of $n$. This stability suggests a proportional relationship between empirical observations and the theoretical predictions of early stopping time.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We appreciate the review and the suggestions in this review. The raised issues are addressed below.\n\n(1) \"Can the authors provide any other examples as extensions of Theorem 5.1? For example, if the target function belongs to an RKHS ball induced by the Gaussian kernel, what should be the convergence rate of the expected risk?\"\n\nIt is known that the eigenvalue decay rate (EDR) of the Gaussian kernel on the unit sphere in $\\mathbb R^d$ is $\\lambda_j \\asymp j^{-C j^{2/d}}$ ( the super-geometric decay in [Scetbon et al., 2021]) where $C$ is a positive constant depending on $d$, and the kernel regression with the Gaussian kernel has a regression risk of the order $O(\\log n/n)$ by Theorem 3.1 of [Scetbon et al., 2021].\nFurthermore, Theorem 10 of [Li et al., 2024] suggests that the polynomial eigenvalue decay rate (EDR) of $\\lambda_j \\asymp j^{-(d+1)/d} $ is achieved by learning the bias in a neural network, which is different from the EDR of $\\lambda_j \\asymp j^{-d/(d-1)} $ discussed in this paper. In this case, the main results (Theorem 5.1 and Corollary 5.2) can be applied to obtain the minimax optimal nonparametric regression risk of $O(n^{-(d+1)/(2d+1)})$.\n\n\n(2) \"If one does not know which RKHS the target function $f^*$ lies in (or more specifically, if one has no information on the behaviour of eigenvalues $\\lambda_i$), how should one estimate $\\hat R_K$\"?\n\nWe respectfully point out that $\\hat R_K$ in Eq. (7) is defined in terms of the (empirical) eigenvalues $\\hat \\lambda_i$ ($i \\in [n]$) of the kernel gram matrix $\\mathbf K \\in \\mathbb R^{n \\times n}$ defined on the training data. In the case that one does not know the behavior of the population eigenvalues $\\lambda_i$ for $i \\ge 1$, one can still estimate the stopping time $\\hat T$ by the fixed point of $\\hat R_k$ with the eigenvalues $(\\hat \\lambda_i )_{i=1}^n$ of the gram matrix $\\mathbf K$. To do so, we can estimate the fixed point by approximating the numerical solution to the equation $\\hat R_K(\\hat \\epsilon) = \\hat \\epsilon^2/\\sigma_0$.\n\n**References**\n\n[Scetbon et al., 2021] M. Scetbon, Z. Harchaoui. A Spectral Analysis of Dot-product Kernels. AISTATS 2021.", "claims_and_evidence": "Yes, the claims made in the submission are supported by clear evidence. All theoretical results are backed by proofs that appear correct based on my assessment. I did not identify any problematic claims.", "methods_and_evaluation_criteria": "The paper primarily focuses on shallow yet overparameterized ReLU neural networks with a single hidden layer, a well-studied setting in theoretical analysis. The hidden layer is trained using gradient descent with a constant learning rate, while the second-layer weights remain fixed. This network architecture and training approach are reasonable choices. While considering deeper neural networks (i.e., those with multiple hidden layers) would better align with practical applications, the use of a shallow network is understandable given the theoretical focus of the study.", "theoretical_claims": "Yes, I have reviewed the proofs presented in the paper. Based on my assessment, they appear to be correct.", "experimental_designs_or_analyses": "This paper is a theoretical work and include only a simple simulation study. It does not include any real-data experiments.", "relation_to_broader_scientific_literature": "This paper contributes to a deeper understanding of the generalization analysis of overparameterized neural networks with algorithmic guarantees.", "essential_references_not_discussed": "I am not aware of any essential reference that is missing so far.", "other_strengths_and_weaknesses": "Strengths:\n1. I appreciate the presentation of this work. The theoretical proofs are easy to follow. The authors did a good job emphasizing the novelty of their results, comparing to previous works such as (Hu et al., 2021; Suh et al., 2022), which is achieving the same rate of convergence in nonparametric regression without imposing distribution assumption on the input covariate as long as it lies in a $d$-dimensional sphere. \n\n2. As a follow-up of the previous point, I believe the novelties (from a technical viewpoint) of this work include:\n\n(i) Adopt a new error decomposition $f_t = h_t + e_t$ such that $e_t$ is an error function bounded by the width $w$, $h_t$ lies in a bounded RKHS ball. With this decomposition, the author no longer requires approximating the kernel regressor $\\widehat{f}_t^{(NTK)}$ and no longer need the uniform distributional assumption on the input covariate.\n\n(ii) Establish a lower bound of the network width depending on $d$ and $\\epsilon_n$, and does not depend on $(\\widehat{\\lambda}_i)$\n\n(iii) Use local Rademacher complexity to, in turn,  bound the Rademacher complexity of the hypothesis space consisting of all\nthe neural network functions trained by GD.\n\n3. Admittedly, studying the theoretical guarantees of training neural networks via gradient descent in the NTK regime is not entirely new. However, overall, I believe this work is technically solid.\n\nFor other weaknesses, please refer to the questions below.", "other_comments_or_suggestions": "See questions below.", "questions_for_authors": "1. In the paper, the authors presented a special example when the eigenvalues decay polynomially as $\\lambda_j \\asymp j^{-\\frac{d}{d-1}}$, a convergence rate of the expected risk of $\\mathcal{O}(n^{-\\frac{d}{2d-1}})$ can be obtained, which is considered minimax optimal as claimed by previous papers like (Yang and Barron, 1999; Yuan and Zhou, 2016). Can the authors provide any other examples as extensions of Theorem 5.1? For example, if the target function $f^*$ belongs to an RKHS ball induced by the Gaussian kernel, what should be the convergence rate of the expected risk?\n\n2. I have some concerns about the practicality of implementing the early stopping rule for the algorithm. The early stopping time $\\widehat{T}$ defined at (8) relies on the empirical kernel complexity $\\widehat{R}_K$. If one does not know which RKHS the target function $f^*$ lies in (or more specifically, if one has no information on the behaviour of eigenvalues $\\lambda_i$), how should one estimate $\\widehat{R}_K$?", "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": "", "extra_scores": {}}, {"review_id": "fOcdjieYxy", "reviewer": "Reviewer_JB4U", "summary": "This paper addresses the generalization capabilities of over-parameterized two-layer neural networks (NNs) trained by gradient descent (GD) with early stopping for nonparametric regression. The authors establish a sharp generalization bound for the nonparametric regression risk. This result is distribution-free, meaning it does not rely on specific distributional assumptions about the covariate, as long as the covariate lies on the unit sphere. The authors also provide minimax optimal rates for specific cases, such as when the eigenvalues of the NTK decay polynomially. The paper contributes to the theoretical understanding of over-parameterized NNs by bridging the gap between classical kernel regression and finite-width NNs trained by GD.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We appreciate the review and the suggestions in this review. The raised issues are addressed below. In the following text, the line numbers are for the revised paper.\n\n(1) “Can the results be extended to deeper neural networks? If so, what additional challenges arise in the analysis?”\n\nYes, this work can be extended to deeper neural network. The key roadmap is presented as follows. (1) We can establish the uniform convergence to the NTK of the deeper neural network using the existing uniform convergence results in [Li et al., 2024] and still apply the proof strategy in Theorem C.8 of this paper to decompose the neural network function $f$ by $f = h+e$, where $h \\in \\mathcal H_K$ is the “kernel part” of $f$ and $e$ is the error function. (2) Lemma C.9 of this paper then can still be used to bound the local Rademacher complexity of all such  neural network function, and we can use Theorem C.10 of this paper together with the convergence results about the training loss of the deeper neural network widely studied in the literature such as [Li et al., 2024, Allen-Zhu et al. 2019] to prove the sharp nonparametric risk bound of $O(\\epsilon_n^2)$, where $\\epsilon_n$ is the critical population rate of the NTK of the deeper neural network.  \n\nWe would like to emphasize that the two-layer neural network studied in this paper still achieves the sharp risk bound of $O(\\epsilon_n^2)$, supporting the claim in [ Bietti & Bach, 2021] that shallow over-parameterized neural networks with ReLU activations exhibit the same approximation properties as its deeper counterpart.\n\n(2) \"The assumption that $f^* \\in \\mathcal H_K$  may not hold in practice. How robust are the results if this assumption is relaxed? Are there any results for target functions outside the RKHS?\"\n\nWe would like to point out that our generalization results can be extended to the relaxed case that the target function $f^* \\in \\mathcal H_K(\\mu_n)$ with $\\mu_n$ diverges, that is, $\\mu_n \\to \\infty$ as $n \\to \\infty$. In this relaxed case, $f^*$ is not in the RHKS of constant norm, that is, $f^* \\notin \\mathcal H_K(\\mu_0)$ with $\\mu_0$ being a positive constant considered in this paper. We remark that in this relaxed case, the RKHS norm of $f^*$ goes to $\\infty $ as $n \\to \\infty$, which is close to the setup considered in [Bordelon et al., 2025] where the RKHS of $f^*$ goes to $\\infty$ (with $\\beta < 1$ in their work). \nWe note that Theorem C.10 still holds with $B_h = \\mu_n+1+\\sqrt 2$ and $B_0 = (B_h+\\mu_n)/{\\sqrt 2} + 1$, and Theorem C.10 with such new $B_0$ can be used to prove the main result, a new version of Theorem 5,1, for this relaxed case. The new version of Theorem 5.1 would have a nonparametric regression risk bound, $Q(B_0) \\epsilon_n^2$, which has a multiplicative factor  $Q(B_0)$ depending on $B_0$ before $\\epsilon_n^2$, and this risk bound still converges to $0$ if $Q(B_0) \\epsilon_n^2 \\to 0$ as $n \\to \\infty$. For example, when $P$ is the spherical uniform distribution, we have $\\epsilon_n^2 \\asymp n^{-d/(2d-1)}$, and such risk bound converges to $0$ if $Q(B_0) n^{-d/(2d-1)} \\to 0$.\n\n(3) \"The paper suggests that a constant learning rate can be used. Are there any conditions under which a varying learning rate might be beneficial, or is a constant rate always sufficient?\"\n\nVarying learning rate could be beneficial compared to constant learning rate in the nonconvex optimization literature such as the optimization of DNNs, which will be discussed in the final version of this paper. In this paper, we state that the constant learning rate $\\eta = \\Theta(1) $ leads to an empirically faster convergence speed for training the neural network than the literature where the infinitesimal learning rate $\\eta \\to 0$ is used. \n\nFurthermore, we will fix the typos, and $r’$ should be $r$ in line 409. We will also discuss the suggested works in “Essential References Not Discussed” in the final version of this paper.\n\n**References**\n\n[Li et al., 2024] Li, Y., Yu, Z., Chen, G., and Lin, Q. On the eigenvalue decay rates of a class of neural-network related kernel functions defined on general domains. JMLR 2024.\n\n[Allen-Zhu et al., 2019] Allen-Zhu, Z., Li, Y., and Song, Z. A convergence theory for deep learning via over-parameterization. ICML 2019.\n\n[Bietti & Bach, 2021] Bietti, A. and Bach, F. R. Deep equals shallow for ReLU networks in kernel regimes. ICLR 2021.\n\n[Bordelon et al., 2025] B. Bordelon, A. Atanasov, C.Pehlevan. How Feature Learning Can Improve Neural Scaling Laws. ICLR 2025.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "No", "relation_to_broader_scientific_literature": "The contributions of this paper are related the community of deep learning theory.", "essential_references_not_discussed": "Some related papers.\n\n1. Dinghao Cao, Zheng-Chu Guo, and Lei Shi. Stochastic gradient descent for two-layer neural\nnetworks. arXiv preprint arXiv:2407.07670, 2024.\n\n2. Mike Nguyen and Nicole M¨ucke. How many neurons do we need? a refined analysis for shallow\nnetworks trained with gradient descent. Journal of Statistical Planning and Inference,\npage 106169, 2024.", "other_strengths_and_weaknesses": "Strengths:\n1. The authors establish sharp generalization bounds for over-parameterized neural networks based on weaker assumptions, including distributional assumptions and the eigenvalues of the empirical NTK matrix.\n\n2. The proof techniques, particularly the use of local Rademacher complexity and uniform convergence to the NTK, are novel and provide a fresh perspective on analyzing the generalization of over-parameterized NNs.\n\nWeaknesses:\n1. The analysis is restricted to covariates lying on the unit sphere.\n\n2. The results assume that the target function lies in the RKHS associated with the NTK. This assumption may not hold in practice.\n\n3. The paper focuses exclusively on two-layer NNs.", "other_comments_or_suggestions": "1. Page 1, line 34, right, \"learning learning\" should be \"learning\"\n\n2. Page 7, line 348, \"limit the number of steps T in for Algorithm\" delete for\n\n3. Page 8, line 409, r or r'?", "questions_for_authors": "1. Can the results be extended to deeper neural networks? If so, what additional challenges arise in the analysis?\n\n2. The assumption that $f^*\\in\\mathcal{H}_K$ may not hold in practice. How robust are the results if this assumption is relaxed? Are there any results for target functions outside the RKHS?\n\n3. The paper suggests that a constant learning rate can be used. Are there any conditions under which a varying learning rate might be beneficial, or is a constant rate always sufficient?", "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": "", "extra_scores": {}}, {"review_id": "YUQ5DeBtC8", "reviewer": "Reviewer_Fjrf", "summary": "This paper studies the generalization bounds of two-layer neural networks under the neural tangent kernel (NTK) regime.\nUsing the critical radius as an error measure, this paper establishes distribution-free generalization bounds of the network, which recovers the optimal bounds derived in the previous literature in certain distributional cases.\nMoreover, this paper also reduces the requirement of the neural network width in the literature using a new error decomposition.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We appreciate the review and the suggestions in this review. The raised issues are addressed below. In the following text, the line numbers are for the revised paper.\n\nRegarding the weakness, we emphasize that the two-layer neural network studied in this paper still achieves the sharp risk bound of $O(\\epsilon^2)$, supporting the claim in[ Bietti & Bach, 2021] that shallow over-parameterized neural networks with ReLU activations exhibit the same approximation properties as its deeper counterpart.\n\nRegarding the suggested reference and the wording suggestion, we will discuss [Yuan et al. 2007], and use “early stopping” consistently in the final version of this paper.\n\nBelow is our response to the questions.\n\n**(1) \"What does \"preconditioned\" in Section 4 heading \"Preconditioned Gradient Descent\" refer to?\"**\n\nThe \"preconditioned\" in Section 4 heading is a typo, and we have fixed it which will be reflected in the final version of this paper.\n\n**(2) \"It seems that in the literature the EDR remains to be $d/(d-1)$  for varous data distributions. Can you provide concrete examples of other EDRs of the NTK under some distribution?\"**\n\nTheorem 10 of [Li et al., 2024] suggests that the polynomial eigenvalue decay rate (EDR) of\n$\\lambda_j \\asymp j^{-(d+1)/d} $ is achieved by learning the bias in a neural network, which is different from the EDR of $\\lambda_j \\asymp j^{-d/(d-1)} $ discussed in this paper. In this case, the main results (Theorem 5.1 and Corollary 5.2) can be applied to obtain the minimax optimal nonparametric regression risk of the order $O(n^{-(d+1)/(2d+1)})$.\n\n**(3) \"Regarding the simulation, what is the performance of the neural network under the theoretical stopping time $\\hat T$?\"**\n\nIn the following table we report the minimum test loss and the test loss at the theoretical stopping time $\\Theta(\\hat T) = 9 n^{d/(2d-1)} $ of the neural network trained in our simulation study (in Section D of the appendix) with the training data size $n$ ranges within $[100,1000]$ with an increment of $100$. It can be observed that the test loss at the theoretical stopping time $\\Theta(\\hat T)$ is only marginally higher than the minimum test loss for each training data size $n$, justifying the good generalization of the model at the stopping time $\\Theta(\\hat T)$. \n\n| Training Data Size ($n$)     | 100    | 200    | 300    | 400    | 500    | 600    | 700    | 800    | 900    | 1000   |\n|:----------------------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|\n| Test Loss at Step $\\Theta(\\hat T)$  | 0.3269 | 0.1901 | 0.1735 | 0.1425 | 0.1127 | 0.1058 | 0.0853 | 0.0771 | 0.0769 | 0.0665 |\n| Minimum Test Loss      | 0.3265 | 0.1889 | 0.1732 | 0.1419 | 0.1098 | 0.1039 | 0.0850 | 0.0771 | 0.0767 | 0.0663 |\n\n**References**\n\n[Li et al., 2024] Li, Y., Yu, Z., Chen, G., and Lin, Q. On the eigenvalue decay rates of a class of neural-network related kernel functions defined on general domains. JMLR 2024.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "NA", "theoretical_claims": "The proof seems to be solid with clear proof roadmap and justified technical improvements.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "This paper improves the results in the literature, establishing distributional-free generalization bounds for two-layer neural networks under the NTK regime, while previous literature mainly focuses on specific distributions. \nAlso, this paper reduces the requirement of the neural network width by using a new error decomposition.\nThe contributions are mainly technical improvements.", "essential_references_not_discussed": "I recommend adding this paper, which, as far as I know, is the first to study early stopping under the RKHS framework.\n\n> Yao, Yuan, Lorenzo Rosasco, and Andrea Caponnetto. “On Early Stopping in Gradient Descent Learning.” Constructive Approximation 26 (August 1, 2007): 289–315. https://doi.org/10.1007/s00365-006-0663-2.", "other_strengths_and_weaknesses": "### Weaknesses\n\nThe setting of problem seems to be quite simplified in this paper. For example, the neural network is a two-layer network with only trainable inner weights. Also, while the distribution of the data can be arbitrary, the distribution is required to be supported on the sphere.\nThese could impact the generality of the results.", "other_comments_or_suggestions": "Minor: The choice of word \"early stopping\" or \"early-stopping\" should be consistent throughout the paper.", "questions_for_authors": "1. What does \"preconditioned\" in Section 4 heading \"Preconditioned Gradient Descent\" refer to?\n\n2. It seems that in the literature the EDR remains to be $d/(d-1)$ for varous data distributions. Can you provide concrete examples of other EDRs of the NTK under some distribution?\n\n3. Regarding the simulation, what is the performance of the neural network under the theoretical stopping time $\\hat{T}$?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies over-parameterized ReLU networks with one hidden layer, trained with gradient descent and early stopping. The paper contributes theoretical convergence analysis with minimax optimal rate, using the tools of neural tangent kernel and local Rademacher complexity. Reviewer Fjrf roughly reviewed the technical details, and Reviewer EyzF carefully checked the proofs. No technical mistake was identified. Although Reviewer pA14 commented the work as "incremental", the novelty was appreciated by Reviewers EyzF and JB4U. Other minor concerns include the "when-to-stop" issue of early stopping (Reviewer EyzF), unit-sphere assumption being restrictive (Reviewers JB4U and Fjrf).
Decision: Accept (spotlight poster)