Optimal Rates  for Generalization of Gradient Descent for Deep ReLU Classification
Authors: Yuanfan Li
Yunwen Lei
Zheng-Chu Guo
Yiming Ying
Venue: NeurIPS 2025 poster ()
Keywords: statistical learning theory
generlization analysis
SGD
neural tangent kernel
optimal rates
Primary area: theory
TL;DR: we established optimal risk bound of $1/(\gamma^2 n)$ for GD with deep ReLU networks

Abstract: Recent advances have significantly improved our understanding of the generalization performance of gradient descent (GD) methods in deep neural networks. A natural and fundamental question is whether GD can achieve generalization rates comparable to the minimax optimal rates established in the kernel setting. Existing results either yield suboptimal rates of $O(1/\sqrt{n})$, or focus on networks with smooth activation functions, incurring exponential dependence on network depth $L$. In this work, we establish optimal generalization rates for GD with deep ReLU networks by carefully trading off optimization and generalization errors, achieving only polynomial dependence on depth. Specifically, under the assumption that the data are NTK separable from the margin $\gamma$, we prove an excess risk rate  of $\widetilde{O}(L^4 (1 + \gamma L^2) / (n \gamma^2))$, which aligns with the optimal SVM-type rate $\widetilde{O}(1 / (n \gamma^2))$ up to depth-dependent factors.
A key technical contribution is our novel control of activation patterns near a reference model, enabling a sharper Rademacher complexity bound for deep ReLU networks trained with gradient descent.

Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classification
Yuanfan Li School of Mathematical Sciences Zhejiang University 223350708zju. edu. cn
Yunwen Lei Department of Mathematics The University Hong Kong leiywhhku .k
Zheng-Chu Guo School of Mathematical Sciences Zhejiang University guozcōzju. edu. cn
Yiming Ying School of mathematics and statistics Univerity of Sydney yiming. yingosydneyyy edu. au
Abstract
Recent advances have significantly improved our understanding of the generaliza- tion performance of gradient descent (GD) methods in deep neural networks. A natural and fundamental question is whether GD can achieve generalization rates comparable the minimax optimal rates established in the kernel setting. Exist- ing results either yield suboptimal rates of ( (()/Vn), or focus on networks with smooth activation functions, incurring exponential dependence L. In this work, we establish optimal generalization rates for GD with deep ReLU networks by carefully trading off optimization and generalization errors, achieving only polynomial dependence on depth. Specifically, under the assumption that the data NTK separable from the margin y, prove excess risk rate of OLL8/(n7") which aligns with the optimal SVM-type rate ((L((n²²) up depth-dependen factors. A key technical contribution is our novel control of acti- vation patterns near reference model, enabling sharper Rademacher complexity bound for deep ReLU networks trained with gradient descent.
network depth
Introduction
Deep neural networks trained through first-order optimization methods have achieved remarkable empirical success diverse domains (Krizhessky et al. 2012). Despite their widespread adoption, rigorous theoretical understanding of their optimization dynamics and generalization behavior remains incomplete, particularly for ReLU networks. The inherent challenges arise from the non- smoothness and non-convexity of the loss landscape induced by ReLU activations and network architectures, which complicate the classical analysis. Intriguingly, empirical evidence demonstrates that over- peeepparamterrized models often achieve zero training error but still generalize well even in the absence of explicit regularization [Zhang et al. 2016). This phenomenon has spurred significant theoretical research understand its underlying mechanisms.
prominent line research uses the neural tangent kernel (NTK) framework to analyze neural network training [Jacot et al.) 2018). In the infinite-width limit, gradient descent (GD) dynamics can characterized by functions the NTK's 's reproducing kernel Hilbert space (RKHS), with convergence guarantees established for both shallow and deep networks (Du et al. 2019b a). These results demonstrate that GD converges to global minima within a local neighborhood of initialization,
"Corresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Activation
Width
Training error
Generalization
Network
error
and Telgarsky
ReLU
Shallow
TT
Lei al.
ReLU
Shallow
Chen et al.
ReLU
m
Deep
TT
Taheri et al.
Smooth
Ö
CoL)
Deep
P
Ours
ReLU
Deep
7
Table 1: Comparison of learning neural networks with GD on NTK separable data with prior works.
Here m is the network width, the network depth, n the sample size, 7 the NTK-margin, T the number of iterations.
provided that the network width is sufficiently large. In particular, the appealing work (Arora et al. 2019a showed that, if the network width m (n, 1/ L)), then the generalization error is
of the order L y (H-) by where H denotes the NTK gram matrix over the training data and
Ao = Amin (H However, the assumption Ào > 0 is strong assumption because it tends to zero if the size of the training data tends to infinity as shown by [Su and Yang (2019). and Telgarsky [2020) achieved logarithmic width requirements for NTK-separable data with a margin They derived the risk bound of order 1/(>" Vn) for two-layer ReLU networks using Rademacher complexity. The
recent work Chen et al. [2021] extended their results from shallow to deep neural networks, the
Recently, Lei et al. 2026) derived the bound of 1/(72n) for two-layer ReLU networks. However, all the above bounds explicit suboptimal Vx dependence the sample size n only focus on shallow networks.
authors considered the NTK feature learning and proved the bound of Ō o(1)
m
Complementing the NTK framework, another line of research employs algorithmic stability to analyze neural networks. In particular, Liu et al. [2020) demonstrated that the Hessian spectral
norm scales with width m as Ō
mm providing the theoretical basis for subsequent studics on
generalization in overparameterized networks Richards and Kuzborskij kij [02 Lei et al. 2022 Taheri
and T'hrampouiddis 2024 Taheri et al. 2025 The work ('Taheri and T'rramooliddis 2024 achieves
the bound of O(1/2>²) for shallow neural networks, which is almost optimal, as illustrated by Shamir [021], Schliserman and Koren [023]. More recently, (aaeri al. (2025) extended this line of work
to deep networks, obtaining a generalization bound of (le)))) (mn²)). However, this approach often assume smooth activation functions and can not apply to the non-smooth ReLU networks. In summary, these works either consider smooth neural networks or develop generalization bounds with exponential dependency on L. These limitations motivate two fundamental questions:
Can we develop optimal risk bounds of of 1/(22n) for deep ReLU networks through refined Rademacher complexity analysis? Furthermore, is it possible to replace the exponential dependence on L with (Lly(L) by using neural networks with width as a polylogarithmic function of n.?
In this paper, we provide affirmative answers to both questions. Our main contributions are listed below.
1. We prove that gradient decent with step size 7 and T iterations achieves the convergence rate of Fs (s(W)/(rZ), where Fs( (W 33)T's((W)+ | W()) W is reference model, W (0) is the initialization point and (s()) is the training error. This indicates that all iterates remain within a neighborhood of W. By refining the analysis of ReLU activation patterns, we reduce the overparameterizatioo requirement by factor of L as compared to Chen et al. 2021 (sec Remark IT).
2. We establish population risk bound of O(L+F(W)/n) where F(W) extends the empirical counterpart Fs (W) to the population setting. Our analysis introduces two key technical con- tributions. First, we derive sharper Rademacher complexity bounds for the hypothesis class encompassing all gradient descent iterates. A central innovation is representation of the

---

complexity via products of sparse matrices, whose norms are tightly controlled using optimization- informed estimates (see Remark[] 2 Second, by leveraging the covering number techniques, we
prove that ReLU networks remain O'ps)-iisschitz continuous in a neighborhood around the initialization substantial improvement over previous exponential bounds [Xu and Zhu 2024
Taheri et al. 2025 (see Remark().
3. For NTK separable data with a margin % we show that neural networks with m can achieve Ō(T,/(7²n)) risk. This improves on Chen et al. 2021 I's 0( ((m/m)) by simultaneously (a) removing the exponential depth depen- dence. (b) climinating the /m width factor and (c) achieving the optimal dependence on sample complexity (see Table T for a comparison with existing work).
Ō (0))
2 Related Works
2.1
Optimization
The foundational work of Jacot et al. [2018) introduced the Neural Tangent Kernel (NTK) framework, demonstrating that in the infinite-width limit, neural networks behave linear models with fixed tangent kernel [Liu et al. 2020 Lee et al.) 2019]. This lazy training regime [Chizat et al. 2019]. where parameters remain close to initialization, enables gradient descent to converge to global optima near initialization [Du et al., 2019a Arora et al. 2019a]. These analyses showed that the training dynamics be governed by the NTK Gram matrix, which leads to substantial overparameterization (m 2 n² /At). This was later improved by Oymak and Soltanolkotabi [2020). They showed that if the square-root of the number of the network parameters exceeds the size of the training data, randomly initialized gradient descent converges at a geometric rate to a nearby global optima. The work (Ji and a Telgarsky| (2020) achieved polylogarithmic width requirements for logistic loss by leveraging the I-homogeneity of two-layer ReLU networks. However, it should be mentioned that this special property does not hold for deep networks. The NTK framework was extended to deep architectures by Arora et al. 2019b] for CNNs and by Du et al. (20196) for ResNets using the last-layer NTK. Xu
and Zhu 2024 pointed out that such a characterization is loose, only capturing the contribution from the last layer. They further gave the uniform convergence of all layers as m - oo and convergence guarantee for stochastic gradient descent (SGD) in streaming data setting, Allen-Zhu
al.) [2019] showed that the optimization landscape is almost-conver and semi-smooth, based on which they proved that SGD can find global minima. Cao and Gu 2019 introduced the neural tangent random feature and showed the convergence of SGD under the overparameterized assumption m Z n².
2.2 Generalization
The NTK framework has yielded generalization bounds scaling as v (Ha))-y// |Arora et al. Cao and Gu 2019]. This data-dependent complexity measure helps to distinguish between random labels and true labels. Li and Liang (2018) showed that SGD trained networks can achieve small test error on specific structured data. A very popular approach to studying the generalization of neural networks is via the uniform convergence, which analyzes generalization gaps in a hypothesis space using tools such as Rademacher complexity or covering numbers (Neyshabur et al.) 2015
2019a
Bartlett et al. 2017 Golowich et al. 2018 Liu et al. 2024 However, this could lead to vacuous generalization bound some cases NNaarajaan and Kolter 2019]. Moreover, these bounds typically exhibit exponential dependence on depth 7., thus often leading to loose bounds [Chen et al. 2021
This capacity- based method usually results in the generalization rate of the order O(1/ n). Recent work has also exploited stability arguments for generalization guarantees [Richards and Kuzborskij
2021 Lei et al. 2022 Taheri and Thrampoulidis; 2024| Deora al., 2023 Taheri al. [025]] The main idea of algorithmic stability is to study how the perturbation of training samples would affect 1978). The connection
the output of an algorithm (Rogers and Wagner
generalization bound
was established in Bousquet and Elisseefi [2002] Hardt et al. (2016) gave the stability analysis of
SGD for Lipschitz, smooth and convex problems. Lei and Ying 2020 further studied SGD under
much wilder assumptions. Liu et al. [2020) identified weak convexity of neural networks, enabling stability analyses with polynomial width requirements for quadratic loss [Richards and Kuzborskij 2021 Lei et al. 2022). Moreover, Taheri and Thrampoulidis (224 Taheri et al. [2025] obtained
generalization bounds of order Ö(1/n) by using generalized local quasi-convexity property for
3

---

sufficiently parameterized networks. However, these methods depend on smooth activations, and whether similar or even better bound can be established for deep ReLU networks is still unknown. The recent work derived excess risk bounds order ((1/n) for shallow ReLU networks [Lei et al. 2026].
3 Preliminaries
Notation Throughout the paper, we denote a S if there exists a constant c > O such that a S eb, and denote = b if both a & b and b I hold. We the standard notation (()),(()) and use (()) to hide polylogarithmic factors. Denote by I{-} the indicator function (i.e., taking the value if the argument holds true, and 0 otherwise). We use Wu, o²) to denote the Gaussian distribution of mean l and variance o². For a positive integer ni we denote [m] := (l....,7) n.). For use ||>]|2 to denote its Euclidean norm. For a matrix
vector x E Fd, ||ll|2 and ||A|| the corresponding spectral norm and Frobenius norm respectively. The (2, 1) - of is defined as ||Al|2,1 Σ |Aggl2. Let (:--) be the inner product of vector or a matrix, ie.. for any matrices A, B E m we have ||A|| = tr(AT A) and (A, B) tr(AT B). Let L E N, A (A1, .o,,,...,.4. AL) and
R=*" we denote
(BI...., BL) be two collections of arbitrary matrices such that A, and B; have the same size for all i E [L]. We define (A,B) = Σ tr(4, B.). Denote |22.s max; || |/A1l22. For a matrix W, we define (w,) the r-th row of W. Denote || llo the -o-morm which is the number of nonzero entries of a matrix or a vector. We denote C' 1 as an absolute value, which may differ from line to line.
Let X C Rdd be the input space. y = {1, 11, be the output space, and Z == X x D. Let p be probability measure defined on Z. Let S = {z; = (x,: vi) I...., n. be training dataset drawn from Let W == R x (1=xm)L-1 be the parameter space. W E 1mxd and W mm for ( 2, ..... L is the weight of the (-th hidden layer. W (W2 ...., W4) W denotes the collection of weight matrices for all layers. Let (A1.... am ) Rm be the weight vector of the output layer and (.)) = max(- : 0} denote the ReLU activation function. For x E X, we consider the L-layer deep ReLU neural networks with width m follows,
fw(x) = a V W
2 V m
Given an input x E and parameter matrix W- (WI,.. ... WL of an L-layer ReLU network [w()). We denote the output of the 1-th layer by 11(x) v /oo (x)) with (x(x) =
Then fw(x) a (x). We define BR(W) {w E W max: || w < R). The performance of the network fw(x is measured by the following empirical risk Ls (W) and population risk L(W), respectively:
= 1 n Σ (xnf((x))) and L(W) (x((yf((x),,
(s(W)
where we use logistic loss ((=) = log(1 + exp( throughout this paper. We further assume the following symmetric initialization (Nitanda and Suzuki 2020, Kuzborskij and Szepesvári] 2023 Xu and Zhu 2024]:
Assumption (Symmetric initialization). Without loss of generality, assume the network width m is even, and 0,4 = aa, E {-1, +1, for 1 I r S m/2. W(0) E W satisfies
w/ ~ NN Lt). (0 ~ NO Imm) 2 2 - and r E [m], w ( ~ ~N for -= (1...., 2
m,
and w r+ (0) w (0).
We remark that this initialization is for theoretical simplicity, using general initialization techniques will not affect the main results. We fix the output weights {a,) and use Gradient Descent (GD) to train the weight matrix W Ji and Telgarsky 2020 Arora al. 2019a Zou et al. 2018

---

Definition (Gradient Descent). GD updates {W by
I'(++1== w(() aLs(
for all E [4], 0,... , 7
Ow
where oj >> 0 the step size.
Note that in each layer we employ 2 as the regularization factor instead the conventional /1/m m (li and Telgarsky 2020], which is due to 10= (x)))))))))))))))))))))))))))( = 1/2 for our activation function (.). This scaling matches both the theoretical framework of Du et al. [0199]] and the initialization scheme of [He et al. 2015] (where weights w ~ (00, 2/m)). As will be shown later (Appendix A this regularization ensures stable gradient propagation and maintains consistent variance across layers.
The following assumption is standard in the literature [Cao and Gu 2019 Ji and Telgarsky 2020
Chen et al. 2021).
Assumption 2. We assume X = Stt1 be the sphere.
Throughout the paper, we assume that Assumptions and always hold true.
Error decomposition In this work, we analyze the performance of gradient descent through the lens of population risk. To facilitate this analysis, decompose the population risk (TW( as follows
(TW(T)) = (L(W(T)) L. (W(())) + Ls(
where the first term captures the generalization gap, quantifying the network's 's performance unseen data. The second term represents the optimization error, which reflects GD's ability to find global minima. We will tools in the optimization theory study the optimization error (Ji and Telgarsky Schliseannn and Koren 2022), and Rademacher complexity to control the generalization gap [Mohri al. 2018).
Main Results
In this section, we present the main results. Section 4.1 we show the optimization analysis of gradient descent. In Section 4.2 Rademacher complexity to control the generalization gap. In Section 4.3 we apply our generalization results to NTK-separable data with a margin 7.
4.1
Optimization Analysis
We introduce the following notations for a reference model W
1 n
n Σ
Fs(W) = 3rTLLs(W + [W W (s(W)
((::/w(xi))-
Without loss of generality, we assume Fs
2
Theorem 1. Let Assumptions I
2 hold. If m 2 (loggmm)* log(nL/))nLLLnn W).n I
min (4444//).1(22.....)) 1/(201.Fs( then with probability at least 8, for all t S T we have
max w
1 < ((t) W 2 < ( and Σ & FWW. k=0
Remark 1.
Our theorem shows that the convergence rate is bounded by the optimization error of reference model, implying that any low-loss reference point guarantees good convergence. While
prior works relied on NTK-induced solutions [Richards and Kuzborskij] 2021 Arora et al.) 2019a). we prove that there exists a reference model near initialization under the milder Assumption 3 Furthermore, our analysis implies that all training iterates remain within neighborhood of the reference point, and thus near initialization, aligned with previous observations but without studying the kernel or the corresponding Gram matrix directly [Du et al. 2019ab)
5

---

Here we provide the proof sketch and compare it with previous works. The starting point is to show deep ReLU networks admit almost convexity [Lemma
fw(x,) - fw(xx) - -( ()f((x))
W = =ō - (19/844/8
OW W
(4)
m//6
for W. W E BR(BWRWWW (W))))
Then we can show all the iterates remain B 2 Fs (W(0)) and the following inequality holds
(Lemma 21
(( wii W() W (Ls(((())))) 3nCs(W) (W).
Telescoping gives the theorem. Chen al. 2021] introduce the following neural tangent random feature (NTRF) function class:
F(W R) = (w(o).(()) F (w( (w(j)))) +
ff (x) W w()) W W BR (R(()) (W(
They show that gradient descent achieves a training loss of at most 3ENTRF, where ENTRE denotes the minimal loss the NTRF function class (see Theorem 3.3 therein). In contrast, approach directly analyzes the GD iterates and shows that the existence of a nearby reference point with small training error sufficient ensure convergence. For a fair comparison, under Assumption 3 both analyses yield an optimization error of O(1/T). However, our method significantly relaxes the overparameterizztion requirement, improving the width dependence by factor of L (see Remark 5)
4.2 Generalization Analysis
We use Rademacher complexity to study the generalization gap, which measures the ability function class to correlate random noises.
Definition 2 (Rademacher complexity). Let F be a class of real-valued functions over space X,
S = (xi,"" C X. We define the following empirical Rademacher complexity as
Rg (F) = (F)
1 JEF n (E(M)
sup
Σ cx((x))
where = (m)) {+1)" independent Rademacher variables, iee, taking values in {+1} with the same probability.
We further define the following worst-case Rademacher complexity,
Rs (F)
sup
RF.
$c5
We define G = sup, ((yfw(x)) and
7Glog(2/8)
F(W) 3n/ (2(W))
+ ((()) W
(6)
6n
We consider the following function space
F fx fw(x): W W.l,
(7)
where the parameter space is defined as
Wi WWEWW: |W WWW-WB- S F(W)).
(8)
Here use F(W) instead of Fs W) get data-independent hypothesis space. We will show F(W) is upper bound of (W( with high probability. According to Theorem [ all the iterations fall into Wi with high probability. We use the following lemma to relate the generalization gap of smooth loss function with Rademacher complexity.

---

Lemma 1 (rrebro et al. (0100). Let G' = w.ww, (x)f For any 0 < 8 < 1, we have
with probability at least - -072 over for any W E W1,
( 1/2
((W) (W) 2 c (W)
(log (logg))/2990)) ///2 Rn (F)
n
G' log(2/6)
(logn) 3
(F)
n
Now we need control R (F) and G'. As will be shown in Lemma 22 with high probability there holds
F(W)
()) 1,2
(9)
To estimate G", we employ covering numbers to derive a uniform upper bound of /w(x) - (x).
Then we use the smoothness of i to show that for all G' - -22- S L mog (W) Plugging these bounds into Lemma [ gives the generalization gap. Combined with Theorem we derive the following excess risk error. The full proofs are provided in Appendix
Theorem 2. Let Assumplions
hold. If Z 1 d.olo m) logg)ll/gnn/)/) min(4/(5L), (22 (W))) x then with probability at least 6, we have
S
L L+F(W) ( (log((/0)
((w()) -
n
Remark 2 (Improved Rademacher complexity). In previous work [Chen et al. 2021]. they derived
the bound of (4'LLV/ mF(W)/n). Specifically, they use the generalization analysis in Bartlett al. [2017). which requires estimate the following term
3/2
((W)) (W') 1
II W 12
Σ
[WI2// 2/3
Note that I [ ||2 could lead to exponential dependence on the depth. Moreover, I(W)) W / /mll Toll''-WWl -W inducing an explicit ymm term. However, reduce the dependence of L to polynomial (L?). Furthermore, we sharpen the dependence on width from /mm to logarithmic terms. The key idea is to introduce the following expression
L
द ())))) fw(x,) - (x,) = Σ
- ('(0))n
1=1
where G/ (x;) is a matrix defined in (36). hy the output of 1-th layer of fw(o)- We further G (x;) is of the order Ö(L//m) with high probability, from which can derive Rs i.s ( /n). We will show that this improved Rademacher complexity is crucial to get almost optimal risk bounds NTK separable data.
show that G
Remark 3 (Analysis of Lipschitzness). To bound the term G' = =sup,.wew (yffw we analyze the difference [w(x) -fw (x). Since both W, W E BR( for some R, we only need to study [wro (x). This approach necessitates characterizing the uniform behavior of deep networks B W (0)). specifically establishing control over their Lipschitz constants near initialization. Existing works usually lead to an exponential dependence T. [Xu and Zhu 2024 Taheri et al. 2025 thus resulting in a e(L) term in the generalization bound. In particular, Lemma F.3 and F.5 Liu et al. (2020) pointed out that || (x)] C², 1l00fl (x))l2 < C4-1+ [+1 V
the local variation fw(x) (x)-xxxopp
Based on these observations. Taheri et al. 2025 showed that
0 F (x)
SOL.
aW

---

On the other hand, to analyze the output difference near initialization, we observe that
fw (x) fw(o) (x) = a (h'(x) hx)) S vmilh"(x hg (x)1l2.
reducing our task bounding the hidden layer perturbation. Previous approaches, including Xu and Zhu [0224] and Du et al. [2019b]. employ a recursive estimation:
V
11+ (x) - 1o (x) l22
- (o
m
2 (1(w2 -
- (x)12))
C² R
- 115-- + 0². + 111~~1())
(x) - 11-11 (x))12 S
vm
where in the second incquality they used [1)]12 C and || & vm. Although this method provides a straightforward bound, it leads to an exponential dependence on depth due to the recursive nature of the estimation.
In contrast to previous work, we develop the covering dependence on depth. Specifically, we first show that for any finite set of size N: K {x),,.. ,x=
everinggnummbr number strategy to avoid the exponential
if m "0 (og(N))t²), then [|x'(x')
(xx)
Ill Ō
L2R vm
holds for i E [N], E [4]
(Lemma 15). We further take a /m)) D = {xx = l.... [D]}
of the input space.
Recall that the input space X' = Sd-1, is well known from Corollary 4.2.13 in Vershynin (2018)
that the number of 1/ V -coverin is given by [D] < (1+ 20" Vm)". Applying Lemma 15
D derives that if m = S0L log( then
L.R Vm
| (xx) 11 |12 = Ō
x E D
Note that although the covering number could be exponential in L, we only require logarithm of it, thus leading to polynomial dependence. For any input x, we use the closest cover point x² E D to approximate (x) h (xxx))l2, [ 1)(x)) )l2- Combining these yields the key technical
lemma (Lemma 16
L (
sup 11 (x)x2 ő xEX
vm
This implies that the network is Lemma 16 and its proof.
near initialization. More details can be found in
4.3 Optimal rates NTK-separable data
In this section, we apply our general analysis to NTK separable data [Ji and Telgarsky 2020 Nitanda
ct al. 2020 Chen al. 2021 Taheri and Thrampoulidis 2024 Deora et al. 2023 and obtain the optimal rates.
Assumption 3. There exists y 0 and a collection of matrices W. {W! w satisfying
>/ ! IB 1, such that
(x.) W., X1 (W(D)
7 e [n].
This means that the dataset is separable by the NTK feature at initialization with margin Ty Nitanda et al. [2020) pointed out that this assumption is weaker than positive eigenvalues of NTK Gram matrix, which has been widely used in the literature [Du et al. [219b]a Arora et al.) [019a]. With the above assumption, we have the following optimal risk bound on NTK separable data. The proof is given in Appendix D
Theorem 3. Let Assumptions 4/(5L), 1/f x n, then with probability at least 1 6, we have
2 3 hold. If m Z dd m) log(nL/o)(log
S
T-1
I. (log T)²
Σ
c(w
ō
nn2
1=
8

---

Remark 4 (Proof sketch). To apply the result in Theorem 2 we need to estimate F(W). for which it suffices to bound ((W) and G = sup_ (x)) For the first part, we control it by (W( using Bernstein inequality (Eq, (4g. Let W ( + 2 log 7/ plugging into f obtains (x.)) S 1/T and further Cs (W) S L/T,, implying (w) ((1/r²). In order to control (Lyl((x) we leverage the Oippsiiisschhizznsss of (x). Indeed, for any x E X, there holds
L2
lfw(x) S (fwro (x) lfw(x) fw(o) (x)) =
7
L32 and F (W) Ō (1og (1oST)223) then follows that G G= (
?²
Remark 5 (Discussion on optimization error). Under Assumption 3 Theorem 3.3 and Proposition 4.2
Chen et al. [2021] show that when the network width satisfies m 52((L22/// / the training error is of the order (I)/T). We achieve the same guarantee under a significantly milder width condition of m = (2(L22/~²) This improvement is enabled by two key technical advances: sharper bound for 44. and a tighter estimate of the iterate distance [t) W Fr. Specifically, we improve the bound in (4) by a factor of 1 and show that (t))
W = Ö(1/7), improving upon the previous O(VL/7) bound. Together, these refinements reduce the required network width by factor
of L
Remark (Comparison). Under similar assumptions, Ji and Telgarsky 2020 derived the bound
δ yivn for shallow networks, which was recently improved to Ó (,,)) based on an improved
control of the Rademacher complexity [Lei ct al. 2026). For deep ReLU networks, Chen et al. 2022
developed the bound of the order Ö
OOL)
via Rademacher complexity [Bartlett et al.
2017
suffering from exponential depth dependence, explicit width requirement and suboptimal V1nn
scaling. Taheri et al. 2025) improved the result to Ô
for deep networks. The dependence on
7'
n. is optimal up to a logarithmic factor (Shamir 2021 Schliserman and Koren 2023]. However, their results require smooth activations and exponential width in L. Our rate is almost-optimal and enjoys polynomial dependence over the network depth. Furthermore, our bound holds under the
overparameterization S0(1/>*), matching the requirement in Ji and Telgarsky [2020], Chen et al. 2021I.. This is much better than 1/7 //-64444 in Taheri al. [2025] J. To the best our knowledge, these are the best generalization bound and width condition for deep neural networks.
5 Experiments
In this section, we make some experimental verifications to support our theoretical analysis. Our excess risk analysis in Theorem 3 imposes an NTK separability assumption, which has been validated the literature. For example, [Ji and Telgarsky, 2020) demonstrates that Assumption 3 holds for noisy 2-XOR distribution, where the dataset is structured as follows:
(21, V...V...,y Fa) ) {(( ((á=T. 0,1) (o, Jo-
(-V2-00.1
vā-T 1 ..1,) 0.1) (0.-vit--1)) x
d-2
Here, the factor V ensures that ||>||2 1, above denotes the Cartesian product, and the label y only depends on the first two coordinates of the input x. As shown in and Telgarsky (202)), this dataset satisfies Assumption 3 with 1// O(d), which implies that excess risk bound in Theorem becomes (dd /n) for this dataset. We conducted numerical experiments and observed that the test error decays linearly with d? /n. The population loss for the test error is computed over all 2d points in the distribution.
Settings We train two-layer ReLU networks by gradient descent on noisy 2-XOR data. We fix the width m 128, T = 500, / 0.1. We have conducted two experiments. With fixed dimension 6, we vary the sample size n. The results are presented in Figure Ta With a fixed sample size 64, we vary the dimension d and the corresponding table is provided in Figure lb

---

(a) Test error different
(b) Test enror for different d
In both experiments, we observe that the test error is of the order d' /n (approximately 0.15d 0.15.P/n). This shows the consistency between our excess risk bounds in Theorem S and experimental results. We conducted the experiments on Google Colab. simple demonstration reproducing our numerical experiments is available a Google Colab notebook at: https:///itthb: com/ Yuanf wwt.l/ooo/mmaaaeeeeeee 22233/ 2233/ -
Conclusion and Future Work
In this paper, present optimization and generalization analysis of gradient descent-trained deep ReLU networks for classification tasks. We explore the optimization eтror of Fs(Wi (W)) (n)") under milder overparametterizaton requirement than before. We establish sharper bound of Rademacher complexity and Lipschtiz constant for neural networks. This helps to derive generalization bound of order rate of ((1/(n²²) We improve the existing analysis and require less overparameterizztion than previous works.
For NTK-separable data with margin 7, our methods lead to the optimal
There remain several interesting questions for future works. First, is interesting question to extend our methods to SGD). Second, while we establish polynomial Lipschitz constants near initialization, investigating whether similar bounds hold far from initialization would deepen theoretical understanding, Finally, we only consider fully-connected neural networks. It is interesting study the generalization analysis of networks with other architectures, such as CNNs and Resnets Du et al. 2019b].
Acknowledgement
The authors are grateful to the anonymous reviewers for their thoughtful comments and constructive suggestions. The work of Yuanfan Li and Zheng-Chu Guo is partially supported by the National Natural Science Foundation of China (Grants No. 12271473 and U21 A204266.. The work by Yunwen Lei is partially supported by the Research Grants Council of Hong Kong [Project No. 17302624]. Yiming's work is partially supported by Australian Research Council (ARC) DP250101359.
References
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over-paraaetterizatinn. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 Proceedings of Machine Learning Research, pages 242-252. PMLR. 09-15 Jun 2019. https: ptrtpp://proceedinggs mlr, press/v97 wttg//allenzihii
httl
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameteriize two-layer neural networks. Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 322-332. PMLR. 09-15 Jun 2019a. URL https //proceedings. mlr. wwwps/eee111 wtwp:///a//////..aa//aa htmll html
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances in neural information processing systems, 32, 2019b.
10

---

Peter L. Bartlett, Dylan J Foster, and Matus J Telgarsky. Opectrally-nomaalle margin bounds for neural networks. Advances in neural information processing systems. 30, 2017.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of machine learning research, 2 (Mar):499-522 526, 2002.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer. F. d'Alché-Buc, Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019. URL httape://proceedinng.. htwp:eeeeeddnnnnennnndeeee httpa/ppa...ppppp.eeee/////pppee
pdf
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much over-paaaaetttiiiaaionn sufficient to learn deep relu networks?, 2021. httLhhttps//aaat
org/ http//bb/19911...1/
1911 12360
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in neural information processing systems, 32, 2019.
Puneesh Deora, Rouzbeh Ghaderi, Hossein Taheri, and Christos Thrampoulidis. On the optimization and generalization of multi-head attention. arXiv preprint arXiv:2310. 12..6800, 2023.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai Gradient descent finds global minima of deep neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedingy of Machine Learning Research, pages 1675-1685. PMLR, 09-15 Jun 2019a. URL http:::://ppoeeeeeeeiiiee
mlr pwwps//v7e/uuee 99c html
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over- parameterized neural networks, 2019b. URL httpt:///ax::i wwwp:vv..rga/ab//////ea 02000
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pages 297 997-299. PMLR, 2018.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pages 1225-125 1234, PMLR, 2016.
Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pages 1026-1034, 2015.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemnl: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks, 2020. URL httpsstttsxx.i...t.p
1tt.1199991111 12292
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In F. Percira, C.J. Burges, L. Bottou, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012. URL httptps::/pprceeeeeeeeee
neurips .pff]
Iija Kuzhorskij and Csaba Szepeswári. I Learning lipschitz fumetioon by gd-trained shallow overparameterized relu neural networks, 2023. URL https:
http:////aaziv.oor//////2/1//// wwtp/or/////////////e 13848
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. Advances neural information processing systems, 32, 2019.
Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, pages 5809-5819. PMLR, 2020.
Yunwen Lei, Rong Jin, and Yiming Ying. Stability and generalization analysis of gradient methods for shallow neural networks. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 38557-38570. Curran Associates, Inc., 2022. URL httttp:://procedinggs neurips. www.nes..c.paaapppepeeee http:/pprr_..lleeeppprr///////// Paape//erreeeeeppapeeeoorrrreeee Conference pdf
Yunwen Lei, Puyu Wang. Yiming Ying. and Ding- Xuan Zhou. Optimization and generalization of gradient descent for shallow relu networks with minimal width. Journal of Machine Learning Research, 27(34): 35, 2026. Utthttp: //jmlr 2rg/papers/v2T/24- 2030.

---

Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data, Advances neural information processing systems, 31, 2018.
Chaoyue Liu, Libin Zhu, and Misha Belkin. On the linearity of large non-linear models: when and why the tangent kernel is constant. In H. Larcchelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems. volume 33, pages 15954-15964. Curran Associates, Inc., 2020. URL httpps:// www.rddiinnnn.nnus...... http://pw...caapp....epppppppppp b7 Vaaalfeffbbbbcccccccaeaaaall----
Fanghui Liu, Leello Dadi, and Volkan Cevher. Learning with norm constrained, over-parameterizeed.eooooo two-lyye neural networks. Journal of Machine Learning Research, 25(138):1 2024, URL http:///:/
papers/v25/22 1250. html
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Vaishnavh Nagarajan and J Zico Kolter. Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems, 32, 2019.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm- based capacity control in neural networks. In Conference on learning theory. pages 1401. PMLR, 2015.
Atsushi Nitanda and Taiji Suzuki. Optimal rates for averaged stochastic gradient descent under neural tangent kernel regime. arXiv preprint 2tt.:2000.12299.. 2020.
Atsushi Nitanda, Geoffrey Chinot, and Taiji Suzuki. Gradient descent can leamn less over-paramettrrize two-layer neural networks on classification problems, 2020.
Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparameteriizatio::: Global convergence guar- antees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 1(1); 84-105, 2020.
Dominic Richards and Iija Kuzborskij. Stability generalisation of gradient descent for shallow neural networks without the neural tangent kernel. Advances in neural information processing systems, 34:8609-8622 -6209, 2021.
William H Rogers and Terry J Wagner. A finite sample distrihution-free performance bound for local discrimina- tion rules. The Annals of Statistics, pages 506-516 514, 1978
Matan Schliserman and Tomer Koren. Stability vs implicit bias of gradient methods on separable data and beyond. In Conference Learning Theory, pages 3380-3394, PMLR, 2022.
Matan Schliserman and Tomer Koren. Tight risk bounds for gradient descent on separable data. In A. Oh, T. Naumann, A. Globerson, K. Sacnko, M. Hardt, and S. Levine, editors, Ad- vances Neural Information Processing Systems, volume 36, pages 18749-68755 Curran Asso- ciates, Inc., 2023. URL https: /tttps://prroot httpp:://proceeddngg..ee neurip cccpppper_flleepppprr////ee datp/aa2ccaabb0000070000-----op-
pdf
Ohad Shamir. Gradient methods never overfit on separable data. Journal of Machine Learning Research, 22(85): 1-20, 2021.
html
Nathan Stebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. Advances in neural information processing systems, 23, 2010.
Lili Su and Pengkun Yang. On learning over-parameterized neural networks: A functional approximation perspective. Advances Neural Information Processing Systems, 32, 2019.
Hossein Taheri and Christos Thrampoulidis. Generalization and stability of interpolating neural networks with minimal width. Journal of Machine Learning Research, 25(156):1-41, 2024. URL htjtp://jmlr oorgg////lr///////////////
2opera/v25/23-040 0422. html
Hossein Taheri, Christos Thrampoulidis, and Arya Mazumdar, Sharper guarantees for learning neural network classifiers with gradient methods. In The Thirteenth International Conference on Learning Representations, 2025. URL http:t/tt////eeeeeeieeee htt.:aaaw.....oommddddacaaaaaaaa
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47.
Cambridge university press, 2018.
Jiaming Xu and Hanjing Zhu. Overparametrizeed layer neural networks: Uniform concentration of neural tangent kernel and convergence of stochastic gradient descent. Journal of Machine Learning Research, 25 (94):1-83 83, 2024. http: wttppppppg//vaaaeee setpperrs////// html
12

---

Chiyuan Zhang, Sany Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint 1..15:161..0330.. 2016.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over- parameterized deep relu networks, 2018. URL aattps://aree org/ 08888
13

---

A
Technical Lemmas
We define the diagonal sign matrix (xx with E [L] by
E' (x) diag(" (w",, h/- (x)) 2 0}} E R"""
(10)
Then the deep ReLU network has the following matrix product representation:
2 (x)
... 2 (x)'xx
fw(x) a T V
(11)
together with the presentation of (xx):
n'(x) -V 2 (x)
2 (')'x, [T]
(12)
m
m
We further define G)(x) /2/mE(((x) and
Gf(() V 2 (x)
2 /x)()) 1sasbsl,
V
(13)
from which we can rewrite /w (x) as
fw(x)= = T ([C
w
Hence, for E [L], we have
0fw(x) OW
Similarly, define
(x) V 2 Σか (x) W
(x)
V
2 (x)
25asbs L.
(14)
We denote (x), 1g (x), (x), (x) as 10
and 14 with w = W(0).
A.1 Properties of the Initialization
Given set of N points the sphere K (xr ... finite set K, then it can be applied to specific choices of K, for example, the training dataset S1 = (xi,-.. Xn).
..
We provide general results for any
Lemma 2 (Theorem 4.4.5 in Vershynin (2018). With probability at least 1 L expl over the random choice of W (0), there exists an absolute constant co > 1 such that for any E [L]. there holds
| S covm.
(15)
For sub-exponential random variable X, its sub-exponential norm is defined follows:
|||| inf 0: E (xxp((X1/1) < 2).
X E. is sub-exponential too, satisfying
||X EX|lo, S ||
(16)
If Y is sub-gaussian random variable, we define the sub-gaussian norm of Y by
|Yll = in Eexpeeex/PX/e_ee /12) < 2).
Suppose Y ~ NN(0 r2), then oYY) also sub- guassian and we have (Y) < ||Yll S Cr.
(17)
We have the following lemma:
14

---

Lemma (Lemma 2.7.6 in Vershynin 2018 ) A random variable X is sub-gaussian if and only if X² is sub-exponential. Moreover,
X 0z
||
Now we introduce Bernstein inequality with respect to || 11
Lemma 4 (Theorem 2.8.2 in Vershynin 2018)). Let X1, .... Xm be independent, mean zero, sub-
exponential random variables, and d (d1,"" dm) E RRm K max, || |r ll Then for every t t 0, we have
172 Σ
t²
Xr 2t
exp
-emin
K
for some absolute constant
We introduce the following technical lemma related to the conditional expectation of Gaussian indicator function.
Lemma 5. Suppose w is m-dim Gaussian random vector with distribution (0, Let e + 0, be two given vectors of m-dim. Then have the following property
||bl2
B[[((w, c) 2 ()(
Proof. Let (), v (w, b). Then NoO. |||| [22 v ~o [[b(2). We decompose into a component dependent on and an independent residual
Cov(u, v) Var(u) u 1 z
(c,
u u z,
|
where z N (0. |bb/2 (c.b)²) is independent of u. Hence, we have
[[ c) 03 (w, b) B[ll 2 0}v2]
(c, b)
Eli(u 2 0lu²] + 2(c, b)
||c|| E[[ 2 0Juz] + E[[(u 2 032²)
||
(c. b)²
+0+
-
EEz²
2
2
(c, b)²
(c. b)²
|bl 2
+
||b]3
2||c|
2
|cc]
where the second equality is due to E[I(u 2 0Ju²]=
|لا and the independence of u, z. The third
equality follows from the distribution of z. The proof is completed.
The following lemma studies the output of initialization at each layer. Lemma 6. For any > O. if m 2 L L/ then with probability at least 8,
(1b)(x²) 1l2 E
V
V
3 1,
N and 1 1,
Proof. This result directly follows Corollary A.2 in Zou et al. 2018 and we give the proof here for completeness. Note that for $ í < N, $1 L.
| V (w(()))) (x-))
20 (0), (()))))(()))))
Condition on h/- (x'), we have
~ N(0, - |13). hence
c20"(( (0), (x))))
|| (x (x]) Em. (u) ||Ab 1-1 'xx))
(18)
15

---

By 16 and Lemma 3 we have
( ho (2))) (
|16/ 1x))) (x))1
$2| ((w) A/- (x))))lo - (l (0), (x') 2 <iIh (0'001(()'13
(x)
where the last incquality is due to 17 Let X, = 20 (0), AJ (x')) (x)),,,,
1/m, K = C. 1/ -x= and apply Lemma
We have for any 0 -
(x)))(()))) (x')) Ctllbb 118)110 (x'))
=P IE20 2 ((w) (0), (x')) - [| (x')l
(x') (x))
21 2 exp( Cm min (1, (1)
expp( ( -Cml²)
Taking union bounds over i, I, there holds for any S S N and 1 S L,
P(IIIA) )|2 [1 (xx) - Ctilhb (x) 2 2nL ExLexpp(-Mmi
Since m Z 1 (o L/6), let L = holds
we have with probability at least 1 5, there
[ 110 (x)) < CV / (oo0) 114 (x'))
ISigN.ISILL (19)
Now we show the following inequality holds with probability at least 1 - 6,
4IC
1
|1 x 112 1
(20)
m
3
When - 0, it is true. (20) holds for 1 E [L 1). then | (x')
)13 - 4/3. Combined with (99 we
have with probability at least - 6,
|| (xx) (x'))12 1 S (x 112 - 11 11 2+ (x') 112 11/6(x))
40C
log(NL/0)
log(NNL/5
+ +C
1 (x))))
3
4(1 + 1)C
(NL))
1
Hence, (20) holds for all i E [N], E [L], which implies the lemma.
Lemma 7. For any x E X, we have
@fwr, (x) O, LE [L-1]. (W
xx = 0 and
Proof. Note the r-th row of 1 (x) (z) is (( (w)) 1/-1/()))))))))) 2 O)) Since a, = -ar+ and (0) w4 (0) for all r E [+], we have (x)
a (lW (x) 2 (0)
a, ((W( (0)
ar+ m [T( (( (0)) 2 (0)
(a, m )T{ (w) 2 0)w = 0.
It then follows that for all / E [L-1],
() No (x)a (G)) 11 2 (x)(x)
22) 0.
m m
Hence, the proof is completed.
16

---

Lemma 8. Suppose m 2 L log( (og(),))), then with probability at least 1 6, for all i E [M]
0 @f (x²)
S V2
aw
Proof. By Hoeffding inequality, condition on h with probability least 1 6, there holds
(og(N/6) 3
- a
(x
(0) 2 03 - + Cv
m 4
Combined with Lemma we have
i fw (x)
2
1 1
4 ( ja S
= 2. 3
(WL(0)
The proof is completed.
Let Σ1, E2 RR be two diagonal matrices with entries in {0, 10. Lemma 9. Suppose m we have for all i [N], L
~ L Log(N s S m/ (L2 m), then with probability at least 1
sup Pa
H ( 1/2 S 1.
(21)
Proof. We need to prove that for any 5m-1 there holds
H (x' ) Z 1.
(22)
Note that Elo S and ||zu|l2 3
Let = {u E sm-1 ||o|la S S). We only need to prove that the following inequality holds with probability at least - 6:
)olla x 1.
(23)
rEP
Let S be a subspace of 5m-1 that has most s non-zero coordinates. For such a subspace, we choose a 1 1/2-cover of it and denote this cover by Q. By Lemma 4.2.13 in Vershynin (2018).
5*.
The number of such subspaces is M = (""). We denote all subspaces by Sj,-.- ,SM. and the corresponding covers Q1,- QM Let U - (u,,... ... vwr) with M' < (".)", We first prove that (23) is true for all By. then it holds simultancously for all elements in P.
For unit vector v, we define
v (x,) Hi, aslsb.
and 1x-1((') (x*) v. Note that condition on 1 (xx), x (xx),, we take expectation over w/
applying Lemma 5 implies that
E[211 (w/ (0), 11 (x')) 2 O)(( u' (10
It then follows that
|/ |o'(x') || (x') (2=
m
E21 (w (0), (x²)) ()(( (0), x')))) -
Similar to the proof of Lemma for every Uj و < M', we apply Lemma 4 to get
Cllof- (x+)
[1le)(x (xx)) 112 -lo -Ix/--(x<
1 (x') 2 1-2eex (-Cm
L L )
L
17

---

Taking the union bounds for all j. 4, yields
C (xx)
P
(1ee) (x) 112 1el
L
m
Cm
-1-2.
5 cxp
L
-Cm
21 - 2- (5em)² exp
exp
L2
2NL
C L
=1 exp log 6 + log m + s 1og((5)) + log
2 - 5,
where we have used ("") 2 (em/s)² I (em)* in the second inequality and the last inequality is due
m Z I log {) & I m/ [I,² log m). Hence, we have with probability least 1 8,
(x) [+ -) 1105 (x))1 1+ +)
For any unit vector with |Bv|| S s, consider the subspace S containing it and the corresponding 1/2- cover Q. There exists a unit vector uj.j E [M'], 1/u uy llo S and |/U 0jl1a S 1/2. Thus,
(x)())))ll < <(
11yl22+ (x
| (x)
(v - ug)112
=1lu)(x*) 1|2 +
H (xx)) v w- Dj
1|u -2yl12
21 + ||0 - uyار2 sup | (x)))("))ll Wlll +1+ sup vEP
|H (x Jull2.
VEP
Taking sup to the both sides yields
sup P
(x Doll2 x 11+
sup MEP
(H",,('')oll
which implies suptep
| 6.0
(x
Jull2 2 S 1. Hence (3 holds and the proof is completed.
Remark 7. Our proofs are inspired by Lemma A.9 in Zou al. 2018). which establishes the estimates under the condition s Z log(. However, eliminate this assumption via more refined analysis.
Lemma 10. Suppose
L L/)),, then with probability least 8, we have for all
i E [N]. 2 < a L.
H (x))(x') S log m.
Although the left-hand side of above inequality could be the production of L terms, it is bounded by ÖL). This lemma shows that the introduction of ReLU activation can avoid exponential explosion.
Proof. For any unit vector v, we decompose it as v = en + Ug where U5 E [q] are all s-sparse vectors on different coordinates. Therefore,
| 1
11,
j=1
Here we choose x m/(L2 (og m.. then a S mm/ S 12 log m. Applying Lemma 9 we have
H ( (x))u|12
H Ha (x*)
$ ==1
H H (x (x)l2
0.0 (x' xx)),y1
111113 = Vallel12 v S I. Tog m.
18

---

where we have used Shuuchy-Schwartz's 's inequality in the second inequality. Hence,
[H, S Lv Lologmo
The proof is completed.
From the above lemma, we know that if m Z L log( log m, then
112 S Lv log m
G G (xxx
(24)
Remark 8. In Lemma 10 we introduce a useful technique that decomposes the unit vector into sparse components. This approach reduces the covering number from 5 to 5 5*.). making it easier for high-probability bounds to hold. A related method appears in Lemma 7.3 of AAllen-Zhu et al. [2019], but their width exhibits polynomial dependence on n. contrast, our analysis achieves polylogarithmic width, substantially relaxing the overparameterization requirement.
Using similar techniques we can obtain the following lemma:
Lemma 11. Suppose Z L L/8), then with probability al least ö, for all i E [N].2 a S L, [E oo |2lloo S 8 S m/(L (L2log log m).
2 E
1
W (O)H
m
L
Proof. If 8 = 0, the above inequality becomes 0 S 1/L, which holds true. Now we assume 2 1. Similar to Lemma 9 we only need to prove that for any s-sparse unit vector there holds
2
1
Eiv (O)H
$
(25)
L
2
We use the same notation as in Lemma 9 then follows that for all j E SiSi,a [N]
P (x)) 110 (x*)) Ollu) (x)) 10 (622((3)) 12122xpp (-Cm min
L }
For a fixed Et we assume 2n = diagidi, ... dm with de E {0, d, s, E [m]. We have
2 Σiv m
(o)
= d ((w" -xx)))) (xt))))
m
2
(26)
Condition on 0 (x'), there holds
2 (1w (1w (0), (3 (x²)))
2 1 (xx))
E
Let X, 2 ((w (x))) 2 || - (x+) 11 and d (di ... dm). Then X, mean-zero
sub-exponential random variables, following similar discussions in Lemma 6 we have || ll S
C m have
-- (x+) Moreover, |d]] m d3 Em dr S s, ||d| 1. Applying Lemma 4 we
2 (( (0), (x)))) 10 (xx) 113) 'x-'(x''11'
2 (())) ((x))
P
dr
1=
12m
<2 exp
-C -in
tm
(27)
19

---

Choosing t = 1/L2 and note that s I m/(22 log m), we have
2
P
Σ1
(0)o (xx)
_
2s
+
1
11og
(xx) (xx))1111 ((e)) (xx))
m
m
L
m
m
2dr
2PP
((w) (0), 1 (x²)))
+ I (x))
r m
m
Cm
21 - 2 exp
L
where the first inequality is due to (6) and Em= d, S 8, the last inequality results from (7
Taking union bounds over all x', Σ, Uj. and note that
m
m
Cm
8
2nL
5ah
exp
s
L
2
We have with probability at least 1
8.
Σ1 (0(0))
2
(x-))
1
28
+
1
11
(x(")()))
(xx)
11
L
2
2s + 12
2s
1
<
1+ L
1105 (xx')
+
1+
10y113 s
m
2
L
Hence, we have
Σ1 (0)
S
T
2
Following same techniques of using 1/2--over in the proof of Lemma complete the proof of the lemma.
we can prove 25 and then
Additionally, apply similar methods in Lemma 10 by decomposing the unit vector into s-sparse vectors, we have
Σ1
- < Vlogm. m.
(28)
Remark 9. To analyze the influence of the sparse matrix 21 on 25 we propose a key technical
improvement: instead of resorting to covering number arguments as in Zou et al. [2018) Allee-
al. 2019, we leverage a weighted Bernstein inequality. Particularly, existing methods require taking another union bound over both all s-sparse subspaces and their covers (of size ("))"), whereas our analysis only needs to union over the sparse subspaces themselves (of cardinality (T)). Our method directly demonstrates that sparsity inherently lowers computational costs by avoiding the need for dense covers. The simplicity of our technique also underscores the intrinsic benefits of sparse structures in optimization.
A.2 Properties of Perturbation Terms
Recall that
(x) V V
2 m
xxxx)
V
2 (x)Wa+1())) m
2 xx((x).
m
For any E [r,, let W and the diagonal matrix E (x) be the matrices with the same size of W (0) and (x), respectively. Define
(g(x)= = V 2
2 (E)(x) + (x)) W
2 (2g (x) + Sxt1(x))
m
2 (X) + (x)), IsasbsL
x (Wa+1(0) (0) +
(29)
and (((x)= = / (x)()) + (x)) for all / E [Z].
20

---

Lemma 12. Let G (x) with - S b S L be the matrix defined in 29
Assume
max W 2 I X (Lo/lol m Z L' lolog(NL and E. (x'), (x') (xx)
[-1,1]mxm, | (x*)ll I 2 mm/(,,² m) for all i E [N].1 E [L]. Then, with probability at
least for all I a I Li [ there holds
( TV
log
m
Proof. The proof is similar to that of Lemma 8.6 in Allen- et al. 2019). the differences lie in the dependence of We first prove that for any S a < b L.
V m
V 2 (xx))(())) m
Ed (x))
50-1 (x') w S L L m.
(30)
We define diagonal matrix (E) 11""(()) + 0}. and [S Ilo S s. Therefore, f'(x') (x))))(x>))))) (x'). We decompose the left term of (30) into 2 terms and control them respectively. Each matrix can be written (ignoring the superscripts and x').
20y /
2 w (w 51)
2 W(O)
2 BWODE, S...S V
E Eiy
2 W(O) ... Eoy. w(0))
Σ
x
Then, with probability at least 8, there holds:
By Lemma
9
No
2 (0)
... Σ S1
m
By Lemma
11
E
W(0)
(() 1/, 1//L.
By
S m
2w(0)
Eay m
W(0) Vlogm. m.
When there is no Σ, by Lemma
10 /
W(0)
Eoy
2 w(0)
$ LvVog m.
Combined with these results, counting the number of Σ, we obtain
V (E)(x)) + (xx))
V (Ia+l(x)) (x') + Ea+1 (a++(xe))) wo+1 Wott)
b-a
j-1
SLV log
P. Vlog m
j
eL ;
SLylogm
1+ Σ
I L Wlogm
j
7.
where in the second inequality we have used (779) S (e(b- a)55) s (eL/j)², the last inequality
is due to プ (e/j)² converges and it is bounded by constant. Now we have proved 30
Denote Σ' = Σn + E. through similar expansion, E' 2 (W(0) + W) ... ..)..))))))) /2 (W
W)
21

---

is the sum of following terms
Σ' 2 W()) ... E'
V/ w ' /
2 W(0) ... Σ'
2 W
2 w
V
2 W(0)
2 w())
Σ
Σn m
Since |E'||2 1, using Eq.
30), we have
2 W
E'
E'
2 L m,
m
2
E' m
(0)) ... -''
(())
S L Evlommm m.
m
Note that m
|W
12 S
R (L² v mJg then by counting the number of W, we have
G
S
1
L
Wollog m Σ 6 a
( 1
))
(L)/ogm))tt
2
m
1 log m
log m
b a)
log m
LV
1+ Σ
S L
i
m
j=1
The proof is completed.
Denote E(x), hx)), (x) as 10
13 when W
W.
Lemma 13 (Claim 11.2 and Proposition 11.3 in Allen-Zhu et al (2019).. For any W, W E BR (O)). There exists series of diagonal matrices ((>n)' E g RELL with entries in 1, 1] such that for any E [L], there holds
(a) nx(x) - [x(x) = Ek_ ++ V
| V [++
(x)
w*))+=((x))
(b) I(("")'1 & [|=((x) (x)
The above lemma shows that the difference of ReLU networks can be expressed explicitly as the operations of matrices. The main idea is to show that (a) (bb) (Lfa > 0] - {) - 6) for
E {- 1]. Now we introduce the following Bernstein inequality under bounded distributions.
Lemma 14 (Thcorem 2.8.4 in Vershynin (2018). Let XI,... ,N be independent, mean-zero random variables, such that Xx] S K for all Then for every 2 O. we have
N
(- - x22 Kt/3)
f2/2
Σ
X, 21
S 2exp
where X²= IN EX? is the sum of the variance.
The following lemma shows that under overparameterized setting, the outputs and activation patterns for deep relu networks near initialization do not change much.
Lemma 15. Suppose m Z 1,10 log(NT. 5T) (log m) R². Then with probability at least 5, for any W E Bn (W)),, [N] and 1. [T), there holds
log m
[I(x'') 16(x'))12 & 122
R and ||E((x))- - -Ex(x))lo S L1/3 m) (M))))) (31)
m
22

---

Proof. We prove these two inequalities by induction. Note that (31 holds for / = 0. Now we suppose
(1) holds for 1 Let & 0 be a constant. For i E [M] and 7 E [L]. we define A (x') = fr E
ml I[(WW, h (x²)) )) 2 0} * (WW) M/ (x)) 2 0}}, then |x'(
(x'xl = |A'(x'))-
Furthermore, we decompose A' (x') into two parts based on the behavior of (0):
A((x)= = frr E A'xx)) ( (0), (x
>>> - x}} and 12(x²) = (r E ('xx) : kW (0), (x((()))) > n).
We will control |A| (x*) and | (xx) respectively.
For r E [m]. we define Fi. (w), (0), -1- 1/ (x')) & s). From Lemma 6 we know that
2/3 < [xx==((>>\B3 1 V 4/3. Condition on (x²),, (w), (x²)) ~ N 1/b 1 )13),
then we have
var( F (3) S
= P(- R S (W,, (0), N/ (x²)) s kk)
3
- 2
3a /d S Ck.
Then by Lemma 14 choose K = = 1,t=mCkk, X2 S mCk, it then follows that
P Σ F mEE(F")) S <mCrilb (x9) 1 exp (mCK + mCn/3/
(-m(mCC))// (mCK)²/2
Hence, taking union bounds over werl,,, with probability at least 1 - -C..-exp(-ma there holds for all i,
14 S Fl r, S mn.
(32)
For r E Ab(x;), since [[(w", (1-11 2 0) + 14 (x))) 2 0}. we have
((w",, h2' (xx)) - (0) (0),
(xx) (1)))) 2 (0), (x)))) > x².
We deduce that
Iw' - N Σ h'",,''''(')) - (w-) (0),
(x.)
Σ x²= ==x22As =1=')a(x')
(33)
(x))(x))
By assumption - -10
$ T.2 R Tog m/ m and Lemma 6 we get
[ - w¹ (0000
<(IW> - (') (x') - - (x*) + (x))) )|2 +
( - 1 (x*)))2
11
<(R(I)"""(>') 11 (x') + 1) + / - (x²) 1/ (x))l22) & T logm. m.
Combined with 33 we have
L R2 log m
[Ab(x')
(34)
x2
From 32 and 34 we know that
1 (x²)
2n (x)) =1 -xx)xx)) = (xx)) [Ax(x')
Smn + R2 log S 1,4/3 (log (m)
(x)²
where in the last inequality we choose k = 1 m) 1/3 R2/3 m 1/3 Hence, due to the overpa- rameterization of m. we have with probability at least 1 - 8, for i iE [N],
|x' (x')ll S 4/3 (log m) 1/3 1/3 (m 2/3 < 1 log m
m
23

---

Applying Lemma 13 we have
n'(x") - 16(xx)) Σ ( -x)))))))--
(35)
where G (x*) (x)) is defined as
2 (-(x) II -=++1
V 2 12 (x*) + (2"")²).
Gf,((') =
(36)
then follows that
|> (x') (Σ")² Ex(x')loo
Σ (x) [x(x))ll + || llo S 2x) EX((') lloo S L L m
Our overparameterizztioo requirement implies that R S vm/ (L2 Vlog m). Hence, by Lemma 12 we have
logm m
( S /
(37)
m
Therefore,
|1 [1'(xx) (x'xx'll lll
(x)))) ( (x')
log Rllng ( 2 L2
log R.
m
m
where the last inequality results from Lemma proof of the lemma.
6 As result,
31 holds for 1. We have completed the
The above lemma and Lemma 6 imply that with probability at least 1 8, for all / [4], e [N],
[x'('')l22 < L2 log
R+151. m
(38)
Remark 10. Although our approach shares similarities with Lemma B.3 in Zou et al. [2018] our analysis relaxes the required conditions. Specifically, we only require R/ Rm/m their result demands the stricter sealing R/ Vmm O(.--1). Furthermore, compared to Lemma 8.2
whereas
in Allen-Zhu et al. [2019), they derive the bound (x*) (xx))ll2 S RL5/2 Vlog mmmm which worse than our result by a factor of VL.
The following lemma shows the uniform concentration property of deep ReLU networks, which is crucial in the generalization analysis.
Lemma 16. Let R 2 1 be constant. Assume m 2 L" d(log log(L/8) Then with probability least 8. for W BR(W(O)), [L], we have
log m m
sup xEX
|| (x) (1(x) 1,2
R.
(39)
Proof. We consider the 1/(CL /m) of gd-1 and denote it by D = [x!,...,xIII) By
Lemma 4.2.13 13 in Vershynin 2018).
DI < (1+20' Vm)²
24

---

Note that Lemma 15 holds for any finite set K = fx', xx' Letting K = D, we obtain that if
m 2 L' L' d'loooo m I' (og(L 2 ' log ( ( (log m)
R then
log
[| (x a|l 2 122
i
(40)
m
For any x E X, there exists x E with ||- x 112 S 1/(C² mm). then follows that - h (x²)
m
(o((w' (x)))())))) - <(w 1-- (xx 1)))²
m
2
m
((w*,, 11'-1 (x)) (w',, //- 1x (x))))
171
2 [ (1-
h1' (x))) C1I - - (x2))l
1
-c 1 - m
where the first inequality is due to a(.) is 1-Lipschitz. In the second inequality we have used
| < [W]ll + R S vm due to Lemma 2 Similarly, we derive that
[1b(()) (x)))
Therefore, combined with 40 have
|h [>(( (x) N/ (x)
< (x) h (x(x))) + 11'' h/(xx)) )lx + [11b(x)) 1x(x2)
+ 2 log m R + mm
log m
$ mm
S L2
R,
m
where the last inequality results from R 2 1.
The proof is completed.
Remark 11. This lemma is property of deep ReLU networks near initialization that does not depend on the training data. Compared to prior work, while Allen-Zhu et al. 2019). Zou et al.) (0018) only establishes bounds for the training data, we prove the uniform convergence over the entire input space. Previous work on uniform concentration demonstrated that supxex | (x) h (x) & C R /m [Xu and Zhu 2024]. We present significant improvement, reducing the dependence on L from exponential to polynomial.
In the following part, we apply previous technical lemmas to K = S₁ and get properties of deep neural networks over the training dataset.
R². Then with probability at least 1 - 8 for all Lemma 17. Suppose m 2 L log(nL/6) (log $R?. W E (R())))) e [L] [n]
55/3 (log m)2/3/222 R1/3
||a T (T G))(()))ll2 S
m
Proof. For the case I = L.
2 V =v
||a (G)().) G(,((x))]122 =
la (x;) Σ/ (xx))l2
m
2
[[T( 2 20 - [w! 11 (xx)) 2 0})
2 Axx)
L 22/3 (log m) ) R2/3
Σ rE)'(x.)
|arl =
S
(41)
m 1/6
25

---

where the last inequality is due to Lemma 15
Now suppose T., then
a a (G))
G (x,)))))
2 E3
2 TT (x:) ( - + V m
2 a [ (xx)))
m
2 (x:) (x) - (x-))
-V (a (x:) (x.))
G (x,) -
(x;; ((())))__
where the last equality is according to Lemma
Applying Lemma and Lemma 15
there holds
logm
[x))-( & IV
m
This implies that
(x,) - (x), (x),(x)))11
2
(Ila alaT(s's -x) (xx)) WL ||a J E
m
aaa (xT(E((x)
E (xx 12
|a|2 E
(x;
W ('(0)la||G) (x,)
1, 12/3 (log m) m) 1/3
log m
log m
mLy
+ L
R
m//6
1 T,5/3 (log 2/3 R1/3
m//6
where we have used 41 in the third inequality. The proof is completed.
Lemma 18. Assume m 1 (/ (logm)* Then with probability at least 6, for any W E (W()),, i e [n] and l [T.) there holds
0 (x,)))) of ow! (0
I flog m)333 R1/3
(42)
m1/6
Proof. Since ||ayy
1F |1zyT|=
|| llull for two vectors x, have
0x:(x:) 0. (. (x:)
oWi
(0) F
-11h (xx)a Gx/(xx) 1 (xx)a (x)))aaaaoox))
< <114 (x,)a (x,) - G')o(x))]l== + (1(x-=1xx) - 1 (xx))a GL,o(x)]le
= =11b (x, ||la|1
la (G.( G2 G\/,(xx)) 1l2 (x,))(xx) mo (xx))aalaa G2,,(xx;lla.
Using
38 and Lemma we have
L 55/3 (log m m2222/2/55
(x:)llla) T (G) G\))(x))) 112
1/6
Applying Lemma 15 and 24 we obtain
(xx) - (xx))l2|aa [ $ L3,
log m
RVmLy
log
Rlll m
m
/m
26

---

It then follows that
(w,())) @f (x,) (0)
L (log m2)3//m//33
1 Rollogm m
1 1 (log m m22/3mm/3
ow
m//6
vm
m//6
The proof is completed.
B Proofs for Optimization
Lemma 19. Suppose m Z ' log(nL/0)(log m))* RR, then with probability least 6, for i [n), W, W E (R(W(O)) we have
Ofw (xi) W
)
B//3 (log m)
(w(x)) fw(x,)
OW
m//6
This lemma shows that deep ReLU networks near initialization almost linear.
Proof. Note that
@xi(xi) OW
W w Σ 05 w (x:)
W w
ow
(x)) Ta(a"a aaah''1(x" (xx)) W w.)
Σ द (x) w') (x))
1=1
Since fw(x:) a 10 (x:). applying Lemma
13 we obtain
fw (xi)
fw (x,) a T (x,) 1 (x,))
L
Σ
II
2 ( (x,) + (E V m
2
((x)))(E'')))))))))))) w
m
with ||E"))/lo < (x.) - (x:)) (xx:) + (E"))
(x.) E | Then
| (x,) + ( - (x,) - [x() (x:) + 2 (x)
S 1 (logm) (m3
the last inequality is due to Lemma 15
We further let
(x)
(x)())) + (xxx (E"))))>
2
V
2 (X*(x)+ V m
m
i=u+1
By Lemma 12
we have
log
m G S LV
Following the proof of Lemma
we have
1 (log m) R1/3
laa TaT(Gl (G),(x,) Gx)o(x)))11 x
1/6
which implies that |a [G) - la (G' - Gx
+1aa [laT(((,o(x) -x,o0))))) +
G (x:))l21
3/3 (log p21/3 S
m//6
27

---

Hence,
ww (xi) - ( -w(())) < @ (xi) (xi)
w - W
OW
a (G)(x)) - GL(())) -W") w')
la (x,) (x,)) Wall W
12112/1/ (xx)122
5//3 (log m) 2/3 22/331//
L8/3 Ra/3
(log m)2/3
R
m/6
m//
where in the last inequality we have used (38)
The proof is completed.
The following lemma shows that Ls is almost convex near initialization. It becomes more convex as the width grows
Lemma 20. Suppose m L log) R?, then with probability least 8, we have for W, W E (O)),.)),
W W. (Ws(W)
n
(W) - (s(W) +
Σ
(x( (((ff((xx))
ow
1=1
(log 20mmm)/////// R4/3
Ls WW.
1/1
Proof. Since is 1/ /-msohh,h, it enjoys the co-coercivity, i.e.,(()) 2 + (a (a-)))(00))))) +((((())
(b))), which implies that
(x)) - fw(x;))
(().fw(xx)) f(w:f((x;)) 2( (1( (x))
We combine the above inequality with Lemma 19 and obtain
W W dLs W) OW
Of ffw(t (x.)
W w,
yie (v(((n(((xx))
1
aw
mel (xnfw((x:)) (fw((x)) (((x))-wwii ( sw(x)) - (fw((x))- Sw(x)) -sxx))) -( (xw) W ww) w)))
OW
(x:) E(v.w((x))) + 2( (uiJw (xi) - ((v)sw(x))))))
@ W w)(eossf6())
Σ (x,) fw(x))
ow
(Cs(W) Ls (W)
n Σ ((() - (x)))(
2
-C 8/3 (log ( m)
(W)),
where in the first inequality we have used [y (1:fw S ((I:f((xx)) The proof is completed.
The following lemma shows how the distance between gradient descent iterators and the reference model would change after single gradient descent.
28

---

? - 4/(5L) and W, W log(nL/0)(lomm)) RR Then with probability at least 1 - 8. for
Lemma 21. Suppose m 2 L
R².
W 0Ls( (W)
W
< W WI? -
OW
+2n 8/3 (log m) 2/3 R L1 LF
Proof. By Lemma and Lemma 18 we know that which implies that
fsw(x)) oW
S
2, hence
@fw(xx) ow
2VV..
F
sL W) UW
3ʃw (xi)
Usl (x;))
OW
(fw(x,)
le' ((xxfw(x))]]
OW
S 4L
(((nfw(x))]]
n
2
2
5L
(xx))1)
+00
ee' (u:sJw (x:)
where we have used the standard inequality (a+ s 5a 5b2/4 /4. Then by applying Lemma 20 we have
@Cs(W)
W 11 OW
W
0Ls W))
2
aLs( (W) W, aw
WIE + v/2
21
ow
2
W + 5
(1((v:f((x)) 18' (0;ff((x))))1 (xx))))
n
1
41 n
220m²L
le' ((nfw(xx)))
-2((Cs(W) Ls(
Σ
+n/C1%/3(logm) 2/3 R 1/0 LW.
Since 77 4/5L) and
Σ (Ie - 1=1
1 < Σ (((nff((x)) - ((x))((x)))))
the proof is completed.
Proof of Theorem We prove it through induction. It holds for t 0. Suppose it holds for 0, ................................ ,t 1, then we have,
- ( < (W)(k) - + - w 2 Fs(
ma
plugging R 2 Fs( W) and into Lemma 21
have
IW +) W < (k)
W 1 ())))
-
//// 2/33
2/3
W
1/6 1/6 Ls(((()))) + (
29

---

Telescoping and note that Fs( (W)
I Ls( W)
we obtain
[W(1) W 2n
- Ls (w)) Ls
= [W W
k=
+ 2nTC1./3 2/3 p2/3 p/
(W)) m
1/6
( (W)
k=
which implies
1-1
[[(()) W + 2n
(log (omgm) m)2 2/13 (W) Jm 1/9
k=0
S
(() W F (2 + T. WW))
Hence, when 2 (lo) "1 S 1/ W )) there holds
1-1
W(() - W + Σ
(Cs (Cs(W(()) F Fs(W).
k=0
This implies that
[w'( - w S ((() W s (W))
n ((C)(W(()) s Fs(W).
k=
Therefore, the induction holds for t, the proof is completed.
C Proofs for Generalization
From 35 we know that there exists G (x.), 1 5111
E [n], such that
(x;) - (x;)) Σ G (x:) -w
1=1
Let F₁ be the event (w.r.t. (O)) that (x I Cl m/mm///ma for all W E Wi. Let Eg be the event such that ||A)- (x,))l < 4/3, < L,i E [ni]. Then we have the following bound on Rademacher complexity:
Lemma 22. Let F and Wi be defined in 7 and (8) respectively, If the events Es, E2 hold, then
F (W) log m
Rs (F) S CL2
SCL3
(43)
where
(F)
sup Sc5
Rg (F).
Proof. Let 5 18,,,... x,).
Then we have
1 "
R Rz(F)= E
sup
Σ (x.) 1=1
WeW; n
E sup WeW;
(&,( (wro) (x:))
+ E,
sup
(fw(o)) (8:)
-WeW
n
-E, sup W WEW,
(x))(())) (w(() (8:1)
= E,
sup weW;
1
e;a
T (1x)
1 (xx1))
i=1
E sup weW;
a
(1h1(()) - 11 (x;)))
[al] 2 E. sup weW;
Σ ((hh((x) - 1 (x:))
(44)
1
30

---

where the last inequality is due to Cauchy-Schwann inequality. Since the event Ej holds, we have for all W Wi. 1 k < L, [n].
logm m
GG),)( (' & ( W (')))l & CIA
m
where we have used |
|||| for matrices A, B. Therefore,
Eg sup Wew
G (1 - (x;))
E, sup WeW!
E
(L. -W-(0)) (8x)
1=1
E, sup WEW1
((x,)
2
For 1 E [Z]. let (oi)T ... (0m) be the rows of matrix G/ L. (X:) (0)) we obtain
()))
- (xc,
(of)
| 112
11 (xx:)
1
Σ euu 11 (xx:)
sup
u:||u||2=1
iim1
Σ 11 Σ chi - (xx,
(x)
-W'-
w')
Σ 1 1- (x:)
Therefore,
G),O -W000 ('(0))
E, sup WEW,
F(W) log m
-CLA
E.
Σ e (xx:)
31

---

This implies that
E. sup wew
Σ c (x;) (x.)
No (x,)))
2
E. sup WeW;
G)))( - (o)]ll
Σ
E 1 (x:)
1=1
log m
SCT
R
Σ
1 (Xx))
1=1
i=1
log m
SCLy
E
c/ 1-1 (x:)
m
12
F ( log m
F(W)n jn log
-CLA
(x:))1 s C
m
m
The last inequality is due to the event Eg. Combined with (44 we have
|al|
F W logm
Rg(F (F)
E. sup WEW1
e.hha(())) (x.))
SCL2
1=1
The proof is completed.
Now provide the proof for Theorem
2
Proof of Theorem We first control G' = sup, weW. f(yfw(x)), We denote h'(x) as the output
of 1-th layer of the network fw(x), Then (w(x) = a 1 By the definition of F (W),
we have max; W -W'00)l2 I W W(0)lr S F((W). For W E W1, there holds
|w (0)ll & W (o)l + |w W' s 2 F(W) for all E [T]] By the
overparameterizationn of m and Lemma 16
(fw(x)-ww(0) (x))² = (a (x² - -x)))) s mx) - (x) <2m(1lh"(x) 1o (x) + [x] - (x) - CL lo
Since logistic loss é is 1/4-smooth, the following property holds.
[e(x)) $ ((x)/2, zER. then follows that for any W E M1, 2,
((yfw(x)) Slluf (xf(xx) fw(x)) + (fw(x)- (x))2
8
<(lyf((x) 2/ (x)(())) (1( (fw(x) Sw(x))²
4
<2l(yS (x)) + CLA log (WW),
where we have used ab < 2a² + 6² /8 in the second inequality. Hence, G¹ 22++CL LolG+CL-ogmmai (ogmF((W)
According to Lemma 14 have with probability least 1 1- 8,
1/2
2GL(W) log(2/8)
2G 1og(2/6)
(s( L(W) <
+
(45)
n
3n
It then follows that
7G log((2//)
Ls [s(W) 22 W
6n
32

---

which implies that Fs (W) < F(W). ). Combined with Theorem we know that with probability
least 6. W(t) Wi It means that all the iterates are in the hypothsesis space. Furthermore.
events E,. E2 hold due to Lemma 6 and (37 in Lemma 15 Hence, by Lemma and Lemma 22
there holds
S,n (F) + G' 1og(2/8)
((W(O) - 2Cs (W()) S(log ()
L*F(W) + G (lgg(2/0)
n
As result,
((W())) =n Σ
(L(W(t) - (2s(((()) + 2n Σ 1=0
Ls (s(())))
t=0
() + tTI lnTGlo((2/0))
n
from which we derive
(((()) =0 W'F(W)& + G Glog(2/8)
where we have used 1/T x n. The proof is completed.
D Proofs on NTK separability
Proof of Theorrmm 3 We show that there exists W with small F(W) for NTK separable data. Let W W(0) + XW.. *. Choose À 2 log T T/y. Applying Lemma 19 and letting R X, know
that if m Z I, 16 d(og m log(nL//))(ogg /)3/>$, then with probability at least - ō, for all i E [m].
there holds
(x.))) OW())
)
AW
- (x(x)))
2f Ow(0)
[wro) fw(x))
W(0)
W.
8/3 2/3 1/6 (10g m)2/3 1
where we have used (x) = 0 for any X' due to Lemma have
Therefore, by Assumption 3 we
aSwro
(x (x:)
- ((AW., D/w10)(Xi)) - -w(xx))
(x) = Vi AW.,
(W())
OW(0)
(/w1o)(x.) (x:)
/W.. @ fw(xi)
2 2Ay
W 4, aW(0)
Ay
2\7
= log T.
2
2
As result,
1 (xff((x))) < log(1 + exp(-log T)) < T
1
Cs W)
71
where we have used log(1 (1 + x) S x. For any x E X. Lemma 16 implies that
(fw(x) 2 (x) 2 -lf (x)) [xw (x)
2 -a- T 1 -x) 2 -CI2 VlogmA. -
33

---

Hence,
G = sup (x)) E log(1 + exp L2 v log m log T/>)) S L Vlog m log
where the last inequality is due to (1+t) I 12g(2t) - 2lg fort 2 2. Note that if x² - ar+
then x² I a² + 23. Combined with (45) it then follows that (let V ((W)
4G lolog 2/6)
2G 2Glog(2/0)
+ L Vllgm m log T log(2/6)
((W) - 2Cs W)+
3n
n
yn
Thus, we have
1.2
Vog m log T log(2/))
( (log 2) + +1122
F(W) S 3n/T
+ +12 Ō
(46)
T
m
722
Applying Theorem and note that Fs
W = Ls W Σ 7. there holds
1
((W()) = ( 1.A(log T) + 7.1.))
T
ny²
t=
The proof is completed.
34

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
We clarify our contributions and the scope of the paper in the abstract and introduction.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In the conclusion, we list several limitations of the paper, e.g., our analysis is only applicable when the gradient descent iterates stay around the initialization point.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
35

---

Answer: [Yes]
Justification:
We present all the necessary assumptions and include the proof all theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversell, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: As theoretical paper, our main contributions are theoretical analyses and proofs. The numerical experiments are designed solely to provide basic validation of our theoretical findings. We have fully disclosed all experimental details in Section 5 of the paper.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
36

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The details and code of experiments can be found in Section
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. ec/
sublic/guidess hetii//ggiides/oeeeuubmiiseee
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips cc/ pttppppllllllppieeee http://ooooooooossssoooooooeeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The details of experiments provided in Section 5
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should presented in the core of the paper to a leGel of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our paper is primarily theoretical in nature. The simple numerical experiments are designed as deterministic verifications of our theoretical results rather than empirical evaluations requiring statistical analysis.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
37

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Given the simplicity of our numerical experiments (which are minimal and for verification only), conducted our experiments Google Colab.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics /
Answer: [Yes]
Justification:
The research conducted in the paper confirm with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and nevatiGe societal impacts of the work performed?
Answer: [NA]
Justification: This is theoretical paper, and there is no societal impact of the work per- formed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
38

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This is a theoretical paper, which poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This is theoretical paper, and we do not use any existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
39

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
batasets.papersstt
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This is a theoretical paper, which does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not inGolGe crowdsourcing research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper inGolves human subjects, then much detail possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
40

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
We do use LLM in preparing the submission.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy battps://neurre http://rrippcccooooeeeeeeeee//// cc/Connferences/2225//LL for what should or should be described.
41


Reviews:
[{"review_id": "rgFsvWQmjR", "reviewer": "Reviewer_8eNE", "summary": "This paper investigates the generalization error of $L$-th layer ReLU neural networks trained in the NTK regime. On the data that is $\\gamma$-separated by the neural tangent kernel, the authors provide the excess risk of order $O(L^4(1+\\gamma L^2)/\\gamma^2 n)$, which is faster than the well-known suboptimal one $O(1/\\sqrt{n})$ and only depends polynomially on the network depth $L$. They also provide a global convergence guarantee for the network using gradient descent and the NTK framework. In the analysis, they carefully evaluate the dependence on $L$ for the convergence analysis and Rademacher complexity bound, which enables them to obtain a sharper bound.", "questions": "- How is the initialization scheme defined in Assumption 1 crucial for obtaining the sharper bound? For example, while [Chen et al., 2021] considers the standard Gaussian initialization for the weights, can the same bound be derived for such settings?\n- As the authors also mentioned as a future work, extending the results to stochastic optimization, which is covered by [Chent et al., 2021], will be a significant topic. What is the difficulty of such an extension?\n- Another question is about the extension to other models. For example, how is the ReLU activation essential for obtaining the results, and is it possible to extend the results to other activations? Moreover, I am curious about the applicability of this approach to different models, such as ResNet and CNN.", "limitations": "The authors properly address the limitations.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strength**\n- As the authors mentioned in the paper, much of the existing literature on the generalization error bound of deep neural networks exponentially depends on the network depth. This work mitigates this dependence to the polynomial one, which is a significant refinement. \n- This paper is easy to follow, with detailed explanations of theorems and concise proof overviews.\n\n**Weakness**\n- The primary concern is that this paper mainly focuses on NTK-separable data, which imposes a substantial restriction on the data structure. It appears that several refinements, such as the polynomial dependence on the network depth, do not require the separability assumption. Therefore, it would be more plausible to compare the results obtained in this work with other NTK-based results that do not focus on the separability condition.", "was_revised": true, "final_justification": "I would like to maintain my original score.", "rebuttal": "Thanks for acknowledging the strengths of our work. Our point-to-point response to your comments follows next.\n\n> **W1.** This paper mainly focuses on NTK-separable data, which imposes a substantial restriction on the data structure. \n\nOur main contribution is that we are **the first to prove that deep ReLU networks trained by gradient descent can achieve optimal rate** ($1/n$). The existing works either obtain a bound of suboptimal rate $1/\\sqrt{n}$ or focus on smooth activations. Our results hold in **general settings**, not limited to NTK-separable data.\n- Specifically, in Theorem 2, we provide generalization bounds in general cases, i.e., $\\widetilde{O}\\left(\\frac{L^4F(\\overline{W})}{n}\\right)$. Hence, as long as there exists $F(\\overline{W})$ with small error, the performance of the deep network trained with gradient descent is guaranteed. \n- The NTK-separability assumption **is only used to analyze $F(\\overline{W})$ in a concrete case** and to better illustrate our main result. This assumption allows us to derive explicit estimates of $F(\\overline{W})$, rather than being a necessary condition for our general theory. We believe our general generalization bound can be applied to various settings and demonstrate the power of deep learning.\n- The NTK separability assumption has been widely used in the literature [1,2,3,4]. It has been **theoretically justified in a range of settings**. For instance, [2] analyzes the margin through its dual form in different settings, including linearly separable case and the noisy $2$-XOR distribution.\n\n>**W2.** It would be more plausible to compare the results obtained in this work with other NTK-based results that do not focus on the separability condition.\n\nMany NTK-based results assume positive eigenvalues of NTK Gram matrix. [5] points out that NTK separable data is a milder assumption. In general, we need to estimate $F(\\overline{W})$, or construct a predictor $f_{\\overline{W}}(x)$ that achieves low training error under the structural  data assumption. For example, this is closely related to the Neural Tangent  Random Feature (NTRF) model, which has been well studied in the appealing work [3]. \n\n> **Q1.** How is the initialization scheme defined in Assumption 1 crucial for obtaining the sharper bound? For example, while [Chen et al., 2021] considers the standard Gaussian initialization for the weights, can the same bound be derived for such settings?\n\nThe symmetric initialization assumed in Assumption 1 is **a commonly used technique** in the theoretical deep learning literature [6], primarily to simplify the analysis.\n- Specifically, this ensures at the beginning, $f_{W(0)}(x_i)=0, \\frac{\\partial f_{W(0)}(x_i)}{\\partial W^l(0)}=0,l\\in[L-1]$, as illustrated in Lemma 7. This significantly reduces the complexity of bounding the error dynamics.\n- While our current proof uses this symmetric setup, it is not essential. Under standard Gaussian initialization, these quantities can still be shown to be **concentrated near zero** using standard concentration tools. For example, [3] shows that these quantities can be bounded by $\\mathrm{poly}(\\log(n/\\delta))$ terms, which are **negligible in our final bounds**.\n\n> **Q2.** As the authors also mentioned as a future work, extending the results to stochastic optimization, which is covered by [Chen et al., 2021], will be a significant topic. What is the difficulty of such an extension?\n\n- While [3] has studied the online SGD setting, we believe that our theoretical framework can be adapted to **multi-pass SGD**. However, a major difficulty lies in carefully controlling the **trade-off between optimization error and generalization gap**. For example, how the number of updates $T$ grows with the dataset size $n$.\n- Moreover, analyzing **variants of SGD** such as noisy SGD, decentralized SGD, or SGD with momentum introduces additional challenges. These algorithms involve extra sources of randomness, communication constraints, or memory terms, which make it harder to track the evolution of the parameters.\n\n> **Q3.** How is the ReLU activation essential for obtaining the results, and is it possible to extend the results to other activations?\n- ReLU is widely used in practice for its **efficienct signal propagation and sparsity**. Theoretically, it enjoys a **variance-preserving property** at initialization: $\\mathbb{E}\\|h^l_0(x_i)\\|_2^2=\\|h^{l-1}_0(x_i)\\|_2^2$. This property makes it possible to control the hidden layers and activation patterns rigorously (Appendix A).\n- For other activations, the core techniques in our paper **can still be applied**, but **additional assumptions may be needed**. For example, smoothness, convexity, Lipschitzness or other conditions to ensure signal propagation remains well-behaved.\n\n> **Q4.** The applicability of this approach to different models, such as ResNet and CNN.\n\nThanks for raising this interesting point. We agree that the generalization analysis in different models is interesting for understanding deep ReLU networks. **The core techniques such as controlling the Lipschitz constant and Rademacher complexity can be extended to other architectures**. For example, [7] studies the NTK Gram matrix of ResNet and CNN. Building on their insights, it is interesting to explore how our framework can be used in these models, deriving architecture-specific generalization bounds.\n\n\n[1] Ji et al. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks.\n\n[2] Taheri et al. Generalization and stability of interpolating neural networks with minimal width.\n\n[3] Chen et al. How much over-parameterization is sufficient to learn deep relu networks?\n\n[4] Taheri et al. Sharper guarantees for learning neural network classifiers with gradient methods.\n\n[5] Nitanda et al. Gradient descent can learn less over-parameterized two-layer neural networks on classification problems.\n\n[6] Xu et al. Overparametrized multi-layer neural networks: Uniform concentration of neural tangent kernel and convergence of stochastic gradient descent.\n\n[7] Du et al. Gradient descent finds global minima of deep neural networks."}, {"review_id": "MCa3gBxM5S", "reviewer": "Reviewer_iHRn", "summary": "The authors establish a convergence rate for Gradient Descent applied on deep neural network with rail activations that is polynomial in the depth of the network $L$.", "questions": "Why is it necessary to assume that $R \\geq 1$?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n1. The paper is well written and easy to follow.\n2. The authors present their proof technique and the relation to prior work in a very clear manner.\n3. The result is significant and improves the exponential bound given in previous work.\n\n**Weaknesses**\n\n1. My main concern is about the correctness of Lemma 16, which is a central component of the paper. While Lemma 15 is proved only for the data points \\$x\\_i\\$ in the training set, Lemma 16 applies it to points in the covering set \\$D\\$, which includes points outside the training set. Why is this use of Lemma 15 justified? Could the authors elaborate on this point? If I’m mistaken, I will revise my score accordingly. Another reason this transition may not be valid is that the network’s weights depends on the training set. Therefore, a bound that holds for the training set may not necessarily apply to points outside it.\n\n2. Additionally, I am uncertain about the correctness of the proof of Lemma 15. In the inductive argument showing that $A_l \\leq O(B_l) $, it is crucial that the constant hidden in the big-$O$ notation remains uniform across all induction steps. Otherwise, for example, if the constant grows multiplicatively at each step, the resulting bound would be exponential in $ l $. Could you clarify why this issue does not arise in the proof of Lemma 15?\n\n\n3. A minor concern: The authors obtain a bound only in the case where \\$m \\geq d\\$.", "was_revised": true, "final_justification": "The paper is clear and well written. The result is significant and improves results presented in previous work. For these reasons, I consider the paper to be above the acceptance threshold.", "rebuttal": "Thanks for acknowledging the strengths of our work. Our point-to-point response to your comments follows next.\n\n> **W1.** My main concern is about the correctness of Lemma 16, which is a central component of the paper. While Lemma 15 is proved only for the data points $x_i$ \n in the training set, Lemma 16 applies it to points in the covering set $D$, which includes points outside the training set. Why is this use of Lemma 15 justified? Another reason this transition may not be valid is that the network’s weights depend on the training set. Therefore, a bound that holds for the training set may not necessarily apply to points outside it.\n\nWe appreciate the opportunity to clarify the connection between Lemma 15 and Lemma 16. We claim that **all of our technical lemmas (including Lemma 15) hold for any finite set**. In particular, **Lemma 15 should be stated as follows**:\n\n- **Lemma 15'**\n\nGiven a set of $N$ points on the sphere $K=\\{x^1,\\cdots,x^N\\}$. Suppose $m\\gtrsim L^{10}\\log(NL/\\delta)(\\log m)^4R^2$. Then with probability at least $1-\\delta$ over the randomness of initialization, for any $W \\in \\mathcal{B}_R(W(0)),j \\in [N],l \\in [L]$, there holds\n$$\n\\|h^l(x^j)-h^l_0(x^j)\\|_2\\lesssim L^2R\\sqrt{\\frac{\\log m}{m}},\n\\|\\Sigma^l(x^j)-\\Sigma^l_0(x^j)\\|_0\\lesssim L^{4/3}(\\log m)^{1/3}(mR)^{2/3}. \\quad \\text{(1)}\n$$\nAs $K,N$ vary, we could get concentration inequalites on **different sets**.\n- **Applying Lemma 15' to the training set** \n\nWe get the uniform control over $n$ points $x_1,\\cdots,x_n$ (the original Lemma 15):\nSuppose $m\\gtrsim L^{10}\\log(nL/\\delta)(\\log m)^4R^2$. Then with probability at least $1-\\delta$ over the randomness of initialization, for any $W \\in \\mathcal{B}_R(W(0)),i \\in [n],l \\in [L]$, there holds\n$$\n\\|h^l(x_i)-h^l_0(x_i)\\|_2\\lesssim L^2R\\sqrt{\\frac{\\log m}{m}},\n\\|\\Sigma^l(x_i)-\\Sigma^l_0(x_i)\\|_0\\lesssim L^{4/3}(\\log m)^{1/3}(mR)^{2/3} \\quad \\text{(2)}.\n$$\n- **Applying Lemma 15' to the covering set $D$**\n\n Let $D= \\{x^1,\\cdots,x^{|D|}\\}$ to be a $1/(C^L\\sqrt{m})$-cover of the unit sphere ($C$ is a universal constant). Then we have:\nSuppose $m\\gtrsim L^{10}\\log(|D|L/\\delta)(\\log m)^4R^2$, then with probability at least $1-\\delta$ over the randomness of initialization, for any $W \\in \\mathcal{B}_R(W(0)),j \\in [|D|],l \\in [L]$, there holds\n$$\n\\|h^l(x^j)-h^l_0(x^j)\\|_2\\lesssim L^2R\\sqrt{\\frac{\\log m}{m}},\n\\|\\Sigma^l(x^j)-\\Sigma^l_0(x^j)\\|_0\\lesssim L^{4/3}(\\log m)^{1/3}(mR)^{2/3}.\\quad \\text{(3)}\n$$\n- **Uniform control via covering**\n\n For any $x\\in \\mathbb{S}^{d-1}$, there exists $x^j\\in D$ such that $\\|x-x^j\\|_2\\le 1/(C^L\\sqrt{m})$. It then follows that $\\|h^L(x)-h^L(x^j)\\|_2\\le\\frac{1}{\\sqrt{m}}, \\|h^L_0(x)-h^L_0(x^j)\\|_2\\le\\frac{1}{\\sqrt{m}}$. Hence by triangle inequality we have $\\|h^L(x)-h^L_0(x)\\|_2\\lesssim \\frac{1}{\\sqrt{m}}+L^2R\\sqrt{\\frac{\\log m}{m}}$. \n- **On training set dependence**\n\n1. We use (2) to analyze the optimization and estimate the Rademacher complexity. This **depends on the training set**.\n2. We use (3) to prove Lemma 16, which **depends on the covering set $D$ and is independent of the training set.** Lemma 16 demonstrates the $\\widetilde{O}(L^2)$-Lipschitzness of deep ReLU networks near initailization, which is **independent of the optimization trajectory**. The weights here are not updated via gradient descent; they remain within a neighborhood of the initialization. Lemma 16 is mainly used to derive a bound for $G'$ in Lemma 1. It is crucial to obtain a generalization bound that is only polynomial in $L$ (see Appendix C). \n3. As $m\\gtrsim L^{10}(\\log m)^4R^2\\max(\\log(nL/\\delta),\\log(|D|L/\\delta))$, (2) and (3) hold simutaneously with probability at least $1-\\delta$. Both of them are important and they contribute to our theory **from different aspects**.\n\nWe will revise Lemma 15 accoardingly and put (2) as a corollary in the next version.\n>**Q.** Why is it necessary to assume that  $R\\ge1$?\n\nThe assumption $R \\ge 1$ is introduced for **notational simplicity** and does **not affect the generality** of our results. In particular, the bound $\\frac{1}{\\sqrt{m}}+L^2R\\sqrt{\\frac{\\log m}{m}}$ can be written as  $L^2\\sqrt{\\frac{\\log m}{m}}\\max(R,1)$. Indeed, all of $R$ in our results can be replaced by $\\max (R,1)$ by removing the assumption $R\\ge1$.\n\n\n\n> **W2.** Additionally, I am uncertain about the correctness of the proof of Lemma 15. In the inductive argument showing that $A_l\\le O(B_l)$, it is crucial that the constant hidden in the big-$O$ notation remains uniform across all induction steps. Otherwise, for example, if the constant grows multiplicatively at each step, the resulting bound would be exponential in $l$. Could you clarify why this issue does not arise in the proof of Lemma 15?\n\nIn our analysis, **the constants hidden in the big-$O$ notation are uniform across all layers**, i.e., they do **not depend on the layer index $l$**. This is explicitly ensured by Lemma 12, which provides uniform bounds under overparameterization assumptions for all layers.\n\n- Specifically, in eq.(32) of our paper, the bound **holds uniformly** for all $l \\in [L]$. In Lemma 15, we **do not apply a direct recursive argument** where each layer builds on the previous one with new constants. Instead, we **rely on Lemma 12** to establish uniform control at each layer to finish the induction, assuming the preconditions hold (which are guaranteed by a sufficiently large width $m$). \n- More concretely, we assume $\\|h^l(x_i)-h^l_0(x_i)\\|_2\\le c_1L^2R\\sqrt{\\frac{\\log m}{m}}$,$\\|\\Sigma^l(x_i)-\\Sigma^l_0(x_i)\\|_0\\le c_2L^{4/3}(\\log m)^{1/3}(mR)^{2/3},m\\ge c_3L^{10}\\log(nL/\\delta)(\\log m)^4R^2$ in Lemma 15. Let the universal constant in eq.(32) be $c_4$. Within Lemma 12, let $\\|\\widehat\\Sigma^l(x_i)\\|_0\\le \\frac{c_5m}{L^2\\log m},\\|\\widehat G_b^a(x_i)\\|_2\\le c_6L\\sqrt{\\frac{\\log m}{m}}$. We only need to choose $c_1,c_2,c_3$ to satisfy the following inequalities (which are independent of $l$): $c_1\\ge 2, c_4+9c_1^2\\le c_2, c_3\\ge(2c_2c_5)^3, 2c_6\\le c_1$. Hence, **all constants are fixed prior to the induction**, and do not accumulate as $l$ increases. This ensures that the final bounds in Lemma 15 remain polynomial in $L$, as claimed.\n- Similar analyses also appeared in other works [1,2],  which adopt uniform constants to control inductive arguments across layers.\n\n> **W3.** A minor concern: The authors obtain a bound only in the case where $m\\ge d$.\n- We study the generalization performance of deep ReLU networks in the **overparameterized regime**, which aligns with common practical settings. In this case, the landscape is non-smooth and nonconvex, though the models can generalize well. Our work improves the understanding of gradient descent methods in deep neural networks. The assumption $m\\ge d$ has been widely adopted in the existing literature [1,2].\n- Moreover, the assumption that the network has sufficiently many neurons is **often necessary** to ensure expressivity in high dimensions. [3] shows that **$\\Omega(d^p)$ neurons** are required for NTK to learn a degree-$p$ polynomial. In the feature learning regime, even for simple data distribution (e.g., Guassian or boolean), [4,5] demonstrate that neural networks need $\\Omega(d^s)$ neurons to learn single-index or multi-index models, where $s$ denotes the information exponent or leap complexity.\n- We agree that it is an interesting question to study the performance of deep networks in the $m<d$ regime. However, doing so might require **additional structural assumptions**, such as sparsity in the data distribution, low-dimensional manifold structure, or specific architectural biases. We view this as a promising direction for future research.\n\n[1] Zou et al. Stochastic gradient descent optimizes parameterized deep relu networks.\n\n[2] Chen et al. How much over-parameterization is sufficient to learn deep relu networks?\n\n[3] Ghorbani et al. When Do Neural Networks Outperform Kernel Methods?\n\n[4] Bietti et al. Learning single-index models with shallow neural networks.\n\n[5] Abbe et al. SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics."}, {"review_id": "4w8kYVVDvU", "reviewer": "Reviewer_usBV", "summary": "This paper studies the convergence and generalization analysis of deep fully connected neural networks. Specifically, this paper proves that GD achieves a sublinear convergence rate in the order of $1/T$. Furthermore, the derived generalization bound exhibits an optimal rate of $1/n$ with respect to the sample size $n$. Additionally, the dependence on $L$ has been improved from an exponential to a polynomial order by establishing a tighter Rademacher complexity bound.", "questions": "Since the major contribution of this paper is the improvement in the dependence of the generalization bound with respect to $L$, I have several questions:\n  \n1. What are the key insights that this paper aims to convey through this improved bound?\n    \n2. If Assumption 3 holds for real-world data, what would be the practical difference between using a deep neural network versus a shallow one? For example, how does $L$ relate to $\\gamma$ in this context?\n\n3. Could you specify lines that reflect \"novel control of activation patterns near a reference model\"?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength: \n\n1. A tighter and more practically relevant generalization bound.\n\n2. A thorough comparison with existing works.\n\nWeakness:\n\nOverall, I feel that while this paper shows improvements over prior work, it focuses on a less meaningful direction. The insights gained from this improvement are either unclear or do not align well with what is observed in practice. As a result, I am not convinced that this setting is appropriate for studying the generalization error of deep neural networks.\n\n1. The assumption that the data is NTK-separable with a margin $\\gamma$ lacks explanation in practical contexts. Specifically, what kinds of data will succeed or fail in this assumption? In addition, this assumption is extremely strong in the sense that it requires the network to be initialized in such a way that the data, when processed through this predefined model, is already linearly separable.\n\n2. Compared with prior work, the main difference I observe is that the generalization error bound has been improved from an exponential dependence to a polynomial dependence. However, the key insight remains the same as in previous studies: increasing the number of layers leads to worse generalization. I do not see any fundamentally new insights presented in this paper. \n\n3. The theoretical insights presented in this paper do not adequately explain the current success and widespread effectiveness of deep learning models that rely on large and deep architectures.\n\n4. The paper does not include any experiments to validate the theoretical results it presents.", "was_revised": true, "final_justification": "I increased the score from 3 to 4 because the author has addressed my concerns regarding the gap between the theoretical results and real applications by providing numerical experiments. However, I still have concerns about Assumption 3, which deviates significantly from real-world applications.", "rebuttal": "Thanks for acknowledging the strengths of our work. Our point-to-point response to your comments follows next.\n\n>**W2.&Q1.** Compared with prior work, the main difference I observe is that the generalization error bound has been improved from an exponential dependence to a polynomial dependence. However, the key insight remains the same as in previous studies: increasing the number of layers leads to worse generalization. I do not see any fundamentally new insights presented in this paper. What are the key insights that this paper aims to convey through this improved bound? \n- The improvement over $L$ is **only part of** our contribution. **Our key insight is that we are the first to prove that deep ReLU networks trained by gradient descent can achieve optimal rate** ($1/n$). The existing works either obtain a bound of suboptimal rate $1/\\sqrt{n}$ or focus on smooth activations. For more details, please refer to Table 1 of our paper.\n- Despite the success of deep learning in practice, understanding it in theory is often challanging due to its nonconvexity and non-smoothness. We address these problems by **developing two novel techniques**. Firstly, we derive a tighter Rademacher complexity bound for deep ReLU networks based on the control of activation patterns. Secondly, we prove the $\\widetilde{O}(L^2)$ Lipschitzness of deep ReLU networks. These key improvements open the door to further analysis of deep learning, which is beyond the scope of this paper.\n\n>**W1.** The assumption that the data is NTK-separable with a margin $\\gamma$ lacks explanation in practical contexts. Specifically, what kinds of data will succeed or fail in this assumption? In addition, this assumption is extremely strong in the sense that it requires the network to be initialized in such a way that the data, when processed through this predefined model, is already linearly separable.\n\nWe would like to clarify the motivation and interpretation of the NTK-separability assumption, which has been widely used in the literature [2,3,4,5].\n\n- **Role of the NTK separability assumption:**\n\nThe NTK separability assumption is used in our paper as **a tool to analyze $F(\\overline{W})$** in Theorem 2, which reflects the performance achievable by the network class. This assumption enables a clean characterization of generalization in Theorem 2. Importantly, our main result (Theorem 2) does **not** require data to be NTK-separable—it holds for any $F(\\overline{W})$ with bounded complexity. Thus, NTK separability is not a limiting assumption of our theory, but rather a benchmark scenario to **make comparisons** with existing literature.\n- **We believe Assumption 3 is not a strong assumption**\n\nNTK separability has been **theoretically justified in a range of settings**. For instance, [2] analyzes the margin through its dual form in different settings, including linearly separable case and the noisy $2$-XOR distribution. [8] also shows that NTK can learn polynomials. Hence, Assumption 3 holds for data that are separable by polynomials. In practice, it can be verified through random features by solving a regularized linear classification problem.\n\n>**Q2.**  If Assumption 3 holds for real-world data, what would be the practical difference between using a deep neural network versus a shallow one? For example, how does $L$ relate to $\\gamma$ in this context? \n\nThis is a good question. In standard NTK theory, the margin $\\gamma$ does **not explicitly depend on $L$**. However, we **conjecture** that deeper networks tend to induce larger NTK margins $\\gamma$. Our intuition is based on the structure of the NTK and its associated **reproducing kernel Hilbert space (RKHS)**.\n- Let $\\Theta^{(L)}$ denote the NTK of an $L$-layer ReLU network, and $H^{\\infty}_L$ its corresponding RKHS. As shown in [6], the NTK satisfies the recursive relation: $\\Theta^{(L+1)}(x,y) = \\Theta^{(L)}(x,y)*\\dot{\\Sigma}^{(L+1)}(x,y) + \\Sigma^{(L+1)}(x,y)$, where $\\dot{\\Sigma}^{(L+1)}$ is some derivative covirance matrix and $\\Sigma^{(L+1)}$ is the covariance matrix of a Gaussian process. This implies that $\\Theta^{(L+1)}$ contains $\\Theta^{(L)}$ as part of its structure. Consequently, the RKHSs satisfy a nested relationship: $H^{\\infty}_L \\subset H^{\\infty}_{L+1}$. \n- Consider the finite-width version: $$\nH^m_L = \\{f : \\exists\\, W \\in \\mathcal{W} \\text{ s.t. } f(x) = \\langle W, \\partial f_{W(0)}(x)/\\partial W(0) \\rangle \\}.\n$$ As $m\\to \\infty, H^m_{L}\\to H^\\infty_{L}$ (see [7]). Therefore, $H^m_L \\subset H^m_{L+1}$, and an $(L+1)$-layer deep network has a larger NTK-margin than an $L$-layer network, according to the definition of $\\gamma$.\n\n\nTaken together, these suggest that **deeper networks admit richer RKHSs, which can better separate the data and thus lead to a larger margin $\\gamma$**. Therefore, although $\\gamma$ is not explicitly parameterized by $L$, it is indirectly affected through the expressiveness of the induced RKHS. We emphasize that this argument remains **heuristic**, and we leave a precise characterization of how $\\gamma$ scales with $L$ as an important open question for future work.\n\n>**W3.** The theoretical insights presented in this paper do not adequately explain the current success and widespread effectiveness of deep learning models that rely on large and deep architectures.\n\nOur theoretical framework could not explain the effectiveness of large and deep models adequately, but we **provide a partial explanation** here.\n- In Theorem 2, we establish a generalization bound of the form $\\widetilde{O}\\left(\\frac{L^4 F(\\overline{W})}{n}\\right)$, where $F(\\overline{W})$ represents the risk of a well-structured (but fixed) reference model near initialization in the same network class. **As long as there exists a deep network with small $F(\\overline{W})$**, gradient descent is guaranteed to find a predictor with low generalization error.\n- Importantly, the quantity $F(\\overline{W})$ is directly tied to the **expressive power of the network class**. For more complex data distributions, a shallow network may not be able to achieve a small $F(\\overline{W})$, while a deep architecture can do so due to its ability to capture hierarchical structures. In particular, existing results (e.g., [1]) show that deep networks can approximate certain function classes with exponentially fewer parameters than shallow ones. Therefore, our theory does capture the advantage of depth: **deeper architectures can produce smaller $F(\\overline{W})$**, and Theorem 2 ensures that gradient descent can generalize well in such cases. We believe this provides an explanation for why deep models succeed in practice.\n- In addition, our analysis is conducted in the **overparameterized regime**, where the network width $m$ is large. Most of our results require $m \\gtrsim \\mathrm{poly}(L, \\log n)$ to ensure good optimization behavior (e.g., descent direction, weak convexity). From this perspective, **large models also help with optimization**—they make gradient-based methods more effective, which partially explains why large-scale networks work well in practice.\n\n>**Q3.** Could you specify lines that reflect \"novel control of activation patterns near a reference model\"?\n\n- In Lemma 22, we express the Rademacher complexity via products of sparse matrices, whose norms are tightly controlled using optimization informed estimates. This helps to derive a sharper bound, line 704. Please also refer to remark 2, line 214.\n- Specifically, we first levearage the useful expression\n$f_W(x_i) - f_{W(0)}(x_i) = \\mathbf{a}^\\top \\sum_{l=1}^L \\widehat{G}_{L,0}^l(x_i) (W^l - W^l(0)) h_0^{l-1}(x_i).$\n\nThen we control $\\widehat{G}_{L,0}^l(x_i)$ by Theorem 1 and Lemma 15. This leads to a tight bound of Rademacher complexity $\\widetilde{O}\\left(L^2\\sqrt{\\frac{F(\\overline{W})}{n}}\\right)$. \n- However, previous works use the bound on the shelf, ignoring how activation patterns would affect the complexity. For example, [4] derive the bound of $\\widetilde{O}\\left(4^LL\\sqrt{\\frac{mF(\\overline{W})}{n}}\\right)$, which suffers from exponential term and explicit dependence on $m$.\n\n>**W4.** The paper does not include any experiments to validate the theoretical results it presents.\n\nThis is a paper on **learning theory**. We focus on whether and how deep ReLU networks could achieve optimal generalization error. Hence, we do not take experiments. We believe we have improved the understanding of deep neural networks **theoretically**. \n\n[1] Telgarsky et al. Benefits of depth in neural networks.\n\n[2] Ji et al. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks.\n\n[3] Taheri et al. Generalization and stability of interpolating neural networks with minimal width.\n\n[4] Chen et al. How much over-parameterization is sufficient to learn deep relu networks?\n\n[5] Taheri et al. Sharper guarantees for learning neural networkclassifiers with gradient methods.\n\n[6] Arora et al. On Exact Computation with an Infinitely Wide Neural Net.\n\n[7] Xu et al. Overparametrized multi-layer neural networks: Uniform concentration of neural tangent kernel and convergence of stochastic gradient descent.\n\n[8] Arora et al. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks."}, {"review_id": "WnY4Gvn7nu", "reviewer": "Reviewer_e2P1", "summary": "Improved bounds on the excess risk rate for deep ReLU networks.", "questions": "- gradient decent -> gradient descent, line 57", "limitations": "The limitations are the assumptions of their theorems, which are clearly stated.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths. Improved bounds wrt those known that are polynomial in depth.\nWeaknesses. No attempt at an experimental confirmation, but they are on time to present it for the rebuttal.", "was_revised": true, "final_justification": "I confirm the positive evaluation. The point of saying that their contribution is only theoretical is weak, since to my knowledge no work in NeurIPS is only theoretical. The authors could have missed a mathematical step, that the reviewers could have also missed, so a few experimental confirmations never hurt. To my understanding however the article is strong enough to be accepted.", "rebuttal": "Thanks for acknowledging the strengths of our work. Our point-to-point response to your comments follows next.\n>**Strengths And Weaknesses** Strengths. Improved bounds wrt those known that are polynomial in depth. Weaknesses. No attempt at an experimental confirmation.\n\n- The improvement over $L$ is **only part of** our contribution. The main result is that we are **the first to prove that deep ReLU networks trained by gradient descent can achieve optimal rate** ($1/n$). The existing works either obtain a bound of suboptimal rate $1/\\sqrt{n}$ or focus on smooth activations.\n- This is a paper on **learning theory**. We focus on whether and how deep ReLU networks could achieve optimal generalization error. Hence, we do not take experiments. We believe we have improved the understanding of deep neural networks **theoretically**.\n\n>**Q.** gradient decent -> gradient descent, line 57\n\nThank you for pointing it out. We will revise it in the next version."}]

Author rebuttal:

Meta-review: This paper proves optimal generalization rates for deep networks in the NTK regime trained on a classification task. A new method for handling the regularity of the outputs w.r.t. to small changes of the weights around initialization, thus replacing an exponential dependence on depth with a polynomial one. The optimal rates of convergence are then proven assuming that the classes are separable with a certain margin w.r.t. the NTK geometry. The paper mixes approaches from NTK analysis and uniform generalization bounds.

We are happy to accept this paper as a poster at NeurIPS, in line with the recommendations of the reviewers.
Decision: Accept (poster)