Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods
Authors: Hossein Taheri
Christos Thrampoulidis
Arya Mazumdar
Venue: ICLR 2025 Poster (2025)
Keywords: generalization bounds
neural networks
optimization
feature learning
Primary area: learning theory
TL;DR: We present new guarantees for the generalization behavior of neural networks in classification tasks.

Abstract: In this paper, we study the data-dependent convergence and generalization behavior of gradient methods for neural networks with smooth activation. Our first result is a novel bound on the excess risk of deep networks trained by the logistic loss via an alogirthmic stability analysis. Compared to previous works, our results improve upon the shortcomings of the well-established Rademacher complexity-based bounds. Importantly, the bounds we derive in this paper are tighter, hold even for neural networks of small width, do not scale unfavorably with width, are algorithm-dependent, and consequently capture the role of initialization on the sample complexity of gradient descent for deep nets. Specialized to noiseless data separable with margin $\gamma$ by neural tangent kernel (NTK) features of a network of width $\Omega(poly(\log(n)))$, we show the test-error rate $e^{O(L)}/{\gamma^2 n}$, where $n$ is the training set size and $L$ denotes the number of hidden layers. This results in an improvement in the test loss bound compared to previous works while maintaining the poly-logarithmic width conditions. We further investigate excess risk bounds for deep nets trained with noisy data, establishing that under a polynomial condition on the network width, gradient descent can achieve the optimal excess risk. Finally, we show that a large step-size significantly improves upon the NTK regime's results in classifying the XOR distribution. In particular, we show for a one-hidden layer neural network of constant width $m$ with quadratic activation and standard Gaussian initialization that SGD with linear sample complexity and with a large step-size $\eta=m$ reaches the perfect test accuracy after only $\lceil\log(d)\rceil$ iterations, where $d$ is the data dimension.

Published as a conference paper at ICLR 2025
SHARPER GUARANTEES FOR LEARNING NEURAL NET- WORK CLASSIFIERS WITH GRADIENT METHODS
Hossein Taheri
Christos Thrampoulidis,
Department of Computer Science and Engineering, University of California, San Diego.
Department Electrical and Computer Engineering, University of British Columbia. cthrampo @ecampo@@ee..om wwtpppoccceeuu....
htaheri uusd.edu
Arya Mazumdar
Department of Computer Science and Engineering, University of California, San Diego
arya@@use www.@uuc.deell. edu
ABSTRACT
In this paper, we study the data-dependent convergence and generalization behavior gradient methods for neural networks with smooth activation. Our first result is novel bound on the excess risk of deep networks trained by the logistic loss, via an alogirthmic stability analysis. Compared to previous works, our results improve upon the shortcomings of the well-established Rademacher complexity- based bounds. Importantly, the bounds we derive in this paper are tighter, hold even for neural networks of small width, do not scale unfavorably with width, are algorithm-dependen and consequently capture the role of initialization on the sample complexity of gradient descent for deep nets. Specialized to noiseless data separable with margin by neural tangent kernel (NTK) features of network of width ((poly(log(n))))
we show the test-error rate to be (LL)) />²n, n, where n is the training set size and denotes the number of hidden layers. This is an improvement in the test loss bound compared to previous works while maintaining the logarithmic width conditions. We further investigate excess risk bounds for deep nets trained with noisy data, establishing that under polynomial condition on the network width, gradient descent can achieve the optimal excess risk. Finally, we show that large step-size significantly improves upon the NTK regime's results in classifying the XOR distribution. particular, we show for a one-hidden layer neural network of constant width with quadratic activation and standard Gaussian initialization that SGD with linear sample complexity and with a large step-size 7 reaches the perfect test accuracy after only [d)] iterations, where is the data dimension.
INTRODUCTION
1.1 OVERVIEW
Neural networks, with their vast capacity for capturing intricate patterns in data, have triggered a paradigm shift in machine learning. Despite the power of these networks in modeling complex relationships, the interplay between their optimization and generalization behaviors (that is the gap between training and test errors) continues to be a compelling area of research. In practice, training neural networks using gradient-based optimization methods often leads to interpolation. That is, deep networks can meticulously fit the training data, driving empirical loss to near-zero and training error to perfect classification. However, these networks also demonstrate the capability to generalize well to unseen data. Various recent research endeavors have explored the training and test error guarantees of deep networks, with focus the Neural Tangent Kernel (NTK) regime Jacot et al. (2018); Du et al.) (2019). One prominent feature of such works is that during gradient descent iterates the network's weights are constrained move most constant distance with respect overparameterizaatin i.e.,

---

Published as a conference paper at ICLR 2025
Activation
Width N(poly( (
Train Loss
Test Loss ocl)
Chen et al. (2021):
ReLU
(GOT))
Ō
V 7"
Bartlett et al. (017)
Thm. 2.1 Cor. 1
Smooth
Oppoly (og(m))
oLL) 7
Table 1: Comparison of our results on learning deep nets with GD under NTK separability condition to related prior results. Here m network width, network depth, 7 NTK-margin, number of samples and T number of iterations.
Activation Width all
Iteration
Sample
Tel Telgarsky 22233); Chen et al. 2021
((poly(d)
d²
((P))
Taheri Thrampoulidis (2024): :orl
Glasgow 2024
ReLU
((poly(log(d)) poly(log(d)) log(d)
((d)
Thm. 2.4
Quadratic
S211)
Ö(d)
Table 2: Comparison of our findings on learning the d-dimensional XOR distribution with SGD to relevant prior results.
||w* - woll= O0 (1), where w* E R denotes the vector of target weights, We is the initial weight vector, and is the network width Chen et al. 202T: Di & Telgarsky (2220) Telgarsky (2023)
Yet, even for the relatively simple setting of learning deep nets in the kernel regime, the existing gen- eralization bounds still suboptimal. Moreover, the boundaries of the kernel regime still largely unknown and an active area of research Liu et al. (2022); Banerjee et al. (022); ) Telgarsky (023).
While the kernel regime can partially demonstrate the behavior of neural networks, the resulting guarantees often require large width, small step-size or large iteration and sample complexities. There increasing evidence in recent years that for certain class data distributions neural networks can overcome these limitations by using large step-size which allows the network's 's parameters to move a long distance from initialization, often leading to better sample and computational complexities
Damian et al. 2022 Ba et al. (2022).
In this work, we study the generalization and convergence behavior of gradient-based algorithms in neural nets with smooth activation functions for a wide class of data distributions. Our first result characterizes the test and train loss rates for classification problems under the condition that deviation from initialization is bounded depending the network's width. In particular, for L-hidden layer networks our results hold under ||w* wo S m (11LL) allowing the network's 's weights to move from initialization a distance increasing with m. This shows that the kernel regime continues to hold restricted to be constant
for wider range of setups than previous results for which the deviations in m. The key reason for this improvement exploiting the objective's 's Hessian structure in the gradient-descent path. More importantly, using the Hessian information enables first time, algorithm- deppeddemmdeeedenntt generalization bounds of deep neural networks. As will be discussed throughout the paper, the bounds we derive via geoorithii--stabile are tighter than previous relevant bounds in the literature. We specialize these results to a well-known NTK separability condition tailored for noiseless data and show that our results substantially improve the prior results on the test error performance while still allowing the width to be small, specifically pogy-loga on sample size (Table D. A more detailed comparison deferred Section 1.2 We also consider the case of noisy data distributions and show that deep models are consistent, i.e., they can achieve the optimal test loss in the presence of noise as the sample size grows.
develop, for the
While these results improve upon the existing bounds within the NTK regime, we show in Section 2 that using a large step-size can further improve both the computational and sample complexities. In particular, we show for the stylized setup of data following the XOR distribution, two-layer neural network with quadratic activation reaches zero test error after only log(d) steps of SGD with an aggressive step-size 7 A comparison of our findings with the guarantees of the kernel regime with both GD Taheri & Thrampoulidis (2024) and one- one-pass SGD Telgarsky (202)); Chen et al. (22TT) and the most relevant work in the feature learning regime Glasgoo 2024 summarized in Table
2

---

Published as a conference paper at ICLR 2025
Below is summary of our contributions.
In Theorem 2.1 we develop sufficient conditions for the global convergence of gradient descent in deep and smooth networks and show that if = S'[| woll w 12+ the training loss is bounded by O 10" -wll"" ) where 7, is the step-size and w* can be any choice of network weights that xfT
achieves small training loss. Under similar conditions on m, we show the generalization error is bounded by O [ww"-wal 200 where Gy is the Lipschitz parameter of the network at initialization.
margin-based NTK separability condition. The results of the corollary and comparison to previous works in literature are summarized Table [ A promising feature of our approach is that the test loss bound does not have an unfavorable dependence on the width while still maintaining minimum poly-logarithmic width conditions, which is new in the context of deep learning. To the best of our knowledge this is the tightest test error bound for deep nets trained by GD in the NTK regime.
In Corollary D we interpret these results by specializing them to a commonly
We consider the more general case of noisy data with non- non-vanishing optimal test loss in Theorem 2.3 and show that under polynomial growth condition on network width, GD achieves a convergence rate of 1/vn to the optimal loss after T = vn iterations.
In Section 2.2 we consider the d-dimensional XOR distribution and show that a one-hidden layer network of constant width after exactly log(d) iterations of SGD with step-size 7) = m achieves perfect test accuracy with n = (d) samples, considerably improving kernel regime's s limitations.
1.2 PRIOR WORKS
Generalization of deep nets. Among prior works the generalization capabilities of deep networks, the only initialization dependent bounds were provided in [Bartlett et al. (017) obtaining bounds of order O ((R) where the Rademacher complexity is derived R
10S [W, -W,-MM 1222 ya/2. Here ||Wa]|2 is the spectral norm of the weight matrix of |W
layer (typically constant) and M,s are any data-independent matrices. Thus one can choose M; = W... i.e., the initialization weight matrix. In fact, the above bound resembles the bound that obtained via an coemiization-depeddee
stability analysis. However, note that R depends on the distance traversed by weights through the f2.1 norm which is always larger than the Frobenius norm, and in the worst case, the gap can be significantly large depending on the width. To this, note that for a matrix V E Rm it holds that V VIl2.15 /m V pr. We note that innttaalzaationnnddeeeedee
bounds (e.g.. Neyshabur et al. 2018) Golowich al. 2018 that are usually proportional to ||w: (rather than W. We ) are strictly looser than the bound we obtain. This is primarily due to the fact that | wol is of constant order and can even decrease with width. Whereas, ||w/|]| (or ||wx]]/ m due to the normalization in our setup) grows by increasing m, making the ietialliaaiionnndpeeeete potentially grow with width the rate O(ym), despite lacking an explicit dependence on m. Hence, for wide networks, prior generalization bounds of deep neural nets based on Rademacher complexity are larger than the bound we derive in Theorem
|I can be much smaller than well and in fact as our experiments show ||ur - woll
bounds
Test rates under the NTK separability condition. Other works that provide generalization bounds and optimization guarantees for neural nets include Cao & Gu (2019) Nitanda al. (001)
Ji & Telgarsky/ (2020); Chen et al. (2021); Richards & Rabbat (021); Taheri & Thrampoulddis
(2024); Wang al. (023). In particular, Di & Telgarsky (2020) derived the width condition
2 [oly(] for achieving the - -test error rate in two-layer nets via a uniform-convergenee
argument Shalev-Shwariz & Ben-David (014). This bound was extended to deep networks in Chen ct al. (202h) with a generalization gap of order
13/2
L11/3
72/n
2/6
where A takes the minimum of two quantities. As discussed earlier. this bound is dependent on width since it is derived essentially by taking the minimum of two generalization bounds based on Rademacher complexity derived in Bartett et al. (2017) and Cao & Gu (201)). Importantly, in the which has an undesirable dependence on
small width regime the bound simplifies into Ó
3

---

Published as a conference paper at ICLR 2025
O(L) the width. In this paper, we improve the generalization gap Ö "an under the width condition m = (I(poly(log()//))) To the best of our knowledge, these are the smallest generalization bound and width condition in literature up to now for learning deep neural nets. The key reason behind the improvement is leveraging the Hessian structure of the objective throughout the gradient descent iterates. The improved generalization guarantees result from the algorithmic dependency of our bounds and in fact the bounds can even be expressed such that they solely depend on the cumulative training loss (c.f. Eq. D As the training loss captures the role of initialization and independent of width, the resulting gencralization bounds share the same favorable properties.
Feature learning and the XOR distribution. Some recent works have pointed out the limitations of the kernel regime in understanding the full power of neural networks Abbe et al. (2022). In particular, as in the kernel regime, the networks weights are bounded not to move significantly from initialization, the learned features are not considerably different from those learned at initialization. On the other hand, it is hypothesized that neural networks can learn the true underlying features of the data distribution if the network weights are allowed (by large step-sizes or avoiding early-stopping) to move a large distance from initialization. This phenomenon was first proved for specific regression
tasks where the labels essentially only depend on a small number of features, such as when y = ((Uw)
for U E Rx where k < d Damian al. 2022);; Ba et al. 2002)); Abbe et al. (2022 Cui et al.
(2024). by one large SGD step leading to superior sample complexities compared to the kernel regime.
For classification tasks, some focus has been the XOR distribution(a.... parities) Wei et al. (209)).
Recent works have studied the problem of learning the d-dimensional XOR distribution using neural networks in both NTK and feature learning settings |Barak et al. (2022); Telgarsky (2023); Taheri
& Thrampoulidis (022)); Glasgow (2024). Specifically, it has been shown that under NTK with a sufficienly small step size, a polynomially wide network requires dl GD steps and de sample size.
Some studies have achieved linear sample complexity for learning XOR Bai & Lee (201)); Glasgow (2024) Telgarsky (203)); but these methods involve more computational effort compared to our results. The work most related to ours is Glasgow
(2024). which demonstrated that with particular Gaussian initialization, ReLU network requires poly (oly(lo((d)) large SGD steps and poly (log(1)) neurons to learn XOR with linear sample complexity. In contrast, we show that by using a quadratic activation, learning this distribution requires only log(d) large steps with a constant-wide network, while maintaining the same linear sample complexity.
NOTATION
Probability and expectation with respect to the randomness in random variable x are denoted by (ra(-) and Ez]-]. We use Eg [wy] to represent the weights after & steps of gradient descent using the population's gradient. We use the standard complexity notation S, o(-), O()), O()), and use o(-). O()), (()).2(-) to hide polylogarithmic factors. We denote A b == min(a. b}. The gradient and Hessian of the model t : RRxxd + R with respect to the first input (that is, weights) are denoted by 4 and 42 respectively. The minimum eigenvalue of symmetric matrix is denoted by Amin (-)- We use ||+I| for the Euclidean norm of vectors and ||-1|2 for the spectral norm of matrices. We denote [wi, w2] := {w w awl + (1 a) w2, a E [0, 1]] the line between Wi, W2 R..
2 MAIN RESULTS
Throughout the paper, we consider the following unregularized objective for neural network classifier parameterized with E R",
min F(w)= = 1 ((w,) WEBP
with data points satisfying ||>|| 1, the binary labels y: {+1} and f(.) is loss function for
classification tasks such as the logistic loss, f(t == log [1 te =) and ((,zz) is the network's 's output.
We also define the test loss as F(w)= = Ez,y (1
4

---

Published as a conference paper at ICLR 2025
2.1 TRAIN AND TEST LOSS BOUNDS IN DEEP NETS
In our first theorem, we establish conditions for the width and target weights of the network that guarantees the training loss decays zero the network can interpolate the training set. We consider gradient descent update rule where at any iteration t Σ T: wt+1 = wy ((r)) Before stating the theorem, we note that this result is valid under the standard descent-lemma condition for the step-size, as stated in Lemma S satisfies the standard Eq.
in the appendix. In particular, the descent lemma holds if the step-size the appendix.
34
Theorem 2.1 (Train Test loss of deep nets). Consider L-layer network where D(w, x))
a (W, v x)) and a is a 1-smooth and 1-Lipschitz activation func- tion such that (0) O. Moreover, let 3r. be a constant that only depends on let all parameters of the network be initialized as ii.d standard Gaussian and assume the step-size satisfies the condition RR that obtain small training
1 W. ym
vm
of the descent lemma. Fix and assume the target weights vector E
loss such that
p N max { {VVTF(WW) V n (ww)))
where p² = =1|w== Wool. Moreover, assume the width m is large enough such that it satisfies,
2 (6p")
Then, ||uxe - woll= O(p*) and the training loss satisfies with high probability over initialization.
4pt2 n/T
F(WT)) S
Moreover. assume for every samples from the data distribution there exists w" satisfying Eqs. Then, the expected generalization gap satisfies with high probability over initialization,
Es ((urr)-((up) 2.2 1/.o
1/4)²
Σ
Es
F
where the expectation is over the randomness in the training set denoted by S and Go the Lipschitz parameter of network at initialization i.e., ||V
[ (wo, )]s Go-
In words, the main condition of the theorem is the existence of network weights denoted by w= that
achieves small training error (Eq, 2 and its distance from initialization is at most Omm2/(62+4)) as
implied by Eq. 3 Under these conditions, the training loss is controlled solely by || * woll and
has no explicit dependence on the width or depth of the network. As it will be stated in Corollary !
the NTK regime with margin 7 holds ||w- woll (llog(1)) (1))7,, leading to the width condition v (ppll (log(n)/2) This is unlike previous results which either required polynomial width
(such as (Liu et al. 2022 Cao
Gu 2019) or led to sub-optimal bounds (c.g., (Chen et al. 2021 Ji
& Tel Telgarsky 2020
In general, the theorem valid for any feasible minimizer w² IR. Thus, we can choose w" with smallest value for ||=* wall to optimize the bounds. With such choice of w*, the distance the weights obtained by GD travel is also minimized as Vt E [T] ||w, w woll= [ol]=O([] gradient descent tends toward solutions which attain small loss and lie at minimum possible distance from initialization. This is in line with related prior observations in several other works such as (Du
woll) Thus,
al. 2019 Oymak & Soltanolkotabi, 2019).
The theorem also shows the sample complexity and iteration complexity of learning deep networks with gradient descent and demonstrates the role of initialization and weight's norms on the test error. Note that by replacing the time-averaged training loss guarantees (cf. Theorem B. the generalization gap simplifies into:
Es [(WT)) - F(WT)) S g00 + 1/4)2
(6)
n Hence, the test loss after T (n)) iterations takes the form of Iw= wo
G2
w
wi
Es [(WT))
(7)
7
5

---

Published as a conference paper at ICLR 2025
where the first term is the generalization error and the second term is the training loss. Remarkably, Eq. shows the tight correlation between the two terms, as the generalization gap is virtually the optimization error scaled by the squared Lipschitz constant Gg This is indeed the consequence of Eq. 5 which bounds the generalization gap based on the cumulative optimization error.
At a high-level, the test loss essentially depends on two quantities: (i) the Euclidean distance between the target weights and the initialization and (ii) the Lipschitz parameter of network at initialization. Due to the algoritmmic-dependent nature of our generalization bounds and unlike the prior bounds in literature, the bound in Eq. / captures the role of initialization on the test error: smaller deviations from initialization lead smaller test error bounds and in particular the bound approaches zero as p" goes to zero, As discussed earlier, gradient descent favors such solutions with small deviations from initialization. on the squared I. Lipschitz parameter of the network. For standard Gaussian initialization, it can be shown (cf. Section A.2 that Go S eLL) which introduces an exponential dependence on depth to the generalization bound. We remark that this dependence also appears in the corresponding bounds derived via uniform convergence and Rademacher complexity (e.g., (Bartlett et al. 2017: Golowich
addition to "distance from initialization", the test error bounds also depend
ct al.
2018 Chen et al. 2021b) through the term ||, ||
An interesting feature of our approach is the algorithmic dependent bound Eq. S This bound is generally tighter than the bound in Eq. 6 With the descent lemma condition on the step-size (c.f.
Lemma 3 holds that < 1/(GG + 1/4) which simplifies the bound into:
T-1 Σ
Es F(Wr) - F(wr)) 1
2.2
Es
F(w.)
88)
Hence, we have a bound which only depends on the training performance and the number of training samples. In our experiments in Section B we compute this bound for real-world data and compare it with the empirical results for generalization and test loss.
Remark 2.2. Our analysis relies on the recent progress in characterising the spectral norm of the deep net's s Hessian during GD updates (Liu et al. 2020 Banerjee et al. 2022). In particular, Liu et al. (020) proved that with standard Gaussian initialization, the model's 's Hessian is bounded with high probability by (
if ||w wolls S R. These guarantees can also be used to study the convergence rate of deep networks trained by quadratic loss done by (Liu al. 2020: 2022) but their approach leads to excessively large width conditions. In contrast, here we consider classification tasks with an improved poly-logarithmie width requirement and also study the generalization performance.
(w, x) 0 n=" pm
Recently, the algorithmic stability has been employed for two-layer neural nets in TTheri & Thram- poulidis 2024 Richards & Rabbat whihh is an improved analysis of the stability- based approach typically used for convex objectives in (Bousquet & Elisseeff 2002) Hardt al.] 2016 Lei & Ying 2020). Here, we essentially extend the stability analysis to deep networks. Compared to the two-layer nets, here every iterate of gradient descent, the Hessian's norm guarantees depend on the network's 's weights. In particular, the analysis has to take into account that both ||w, wol ll and I|l, - w remain small during GD updates. This is necessary in order to ensure the Hessian's 's norm guarantees and the approximate quasi convexity property hold during all GD iterates. We do this by an induction based argument which bounds these terms based on the fixed quantity I|w" - woll. which is guaranteed to be bounded based on width by assumption.
2.1.1 SPECIALIZING TO THE NTK-SEPARABLITY CONDITION
The results in the last section can be specifically applied to a class of data distributions that includes the XOR distribution which will be discussed more through the rest of the paper. Before stating our result in the corollary, we state the neural tangent kernel (NTK) separability assumption. Assumption
-epa-ssparyy (Nitanda et al. 2019 Assume the tangent kernel of the model at initialization separates the data with margin 7 L.e., for unit-norm vector Rp it holds for all i E [n] ys (V (Wo, .T.). w) 2 7.
In words, the above assumption implies that the features learned by the gradient at initialization can be linearly separated by some weights w. This assumption is commonly used in deep learning literature for studying classification tasks (Chen et al. 2021 Ji & Telgarsky 2020)

---

Published as a conference paper at ICLR 2025
Corollary 1 (NTK results). Consider the same setup Theorem 2.1 and let Assumption hold.
Define constant B >> O that bounds the model's 's ouput at initialization ie.. Vi E
[m]] | ( 24 < B.
Assume the width is large enough such that m f8 (2B+)og(1/e)
6L+1 -Then there exists w TRP
such that F(w*) < and w² lies at a bounded Euclidean distance from initialization such that I|!= - woll - (2B + log(1/e)).
To interpret this result, we apply this result to Theorem 2.1 and fix c = 1/T. First note that the output of network initialization is constant with high-probability over initialization (e.g., see (Liu et al.) 2020 Lemma F.4), (Cao & Gu 2019 Lemma 4.4)) which implies B Õ(1). Overall, with the stopping condition T (n) and recalling that Go (LL) Corollary yields the expected test
error rate of order
(OLL 1
n
22T
under the condition that = ((po)y())g(n)) Br./7oL+1), We remark the bound does not have any explicit dependence on m. This in itself is not surprising as one intuitively expects the bound not to scale unfavorably with width. Although recent works have derived width independent generalization
bounds for two-layer networks (Ji & Telgarsky 2020 Telgarsky 2023] Taheri & Thrampoulidis! 2024), not aware of any prior work proving width- inttde-nddeeedeent bounds for learning multi- layer networks with GD. As discussed earlier in the introduction, the bound derived in the closely related
work (Chen et al. 2 scales unfavorably with m as it grows at the rate / /m/n. n. In fact, the authors refer deriving width- indeeededdeendentt bounds as an open problem in (Chen et al. 2021 Sec 3.1).
2.1.2 CONSISTENCY OF GD WITH NOISY DATA
The results of the last section mainly apply to data settings when the network can find the optimal solution within a bounded distance from initialization that depends on the network's width. This setting was specially tailored to the noiseless case where achieving vanishing test loss was possible. We discuss next the case learning deep nets by noisy data and show that achieving optimal test loss might be feasible in this setting.
Theorem 2.3 (Test error for noisy data). Consider the same setup and notation as Theorem 2. and assume the width of the network satisfies m BL nLL+3 and the step-size satisfies the conditions of the descent lemma. Then, with high probability over initialization the expected test loss at iteration T /n bounded as:
Es F( < (1+ 4
(F(W'))
p²2
0
1
+
(9)
Vnl
where p²' : -| wool and w* is the minimizer of the population loss i.e., w* arg min F(w).
The result above shows that GD reaches optimal level given that vn >> it leads to the simplified expression
I|w 2 as for large n,
Es [(wx)) F(w=)= ( w - wo
+ F(w*)
Thus, even in non-interpolating regime, GD can still achieve the optimal solution of over- parameterized deep networks.
The bound in Eq. 2 is derived via stability argument which bounds the generalization gap based on the training performance. However, contrary to the conditions of Theorem 2.T here we do not have the interpolation condition F(w*) is not vamishing. This comes at the expense of larger width condition where the width is polynomial in n whereas poly-logarithmic width was sufficient in Theorem 2.1 The condition early stopping further guarantees that the test loss reach the Bayes error given n is sufficiently large. It worth noting that the setting above still is operating almost in the NTK regime. This can be verified by the observation that for the bound be meaningful should per the theorem's s width condition. Finally, remark that the result of Thm 2.3 nicely connects to recent empirical and theoretical results (Li et al. 2020) which show that with early-stopping, GD can find good solution for clustered data with label noise.
hold that | woll || < /n < (()/),
7

---

Published as a conference paper at ICLR 2025
2.2 OVERCOMING NTK LIMITATIONS FOR XOR DATASET
Next, we show the previous NTK guarantees can be improved by using large step-sizes. We consider the stylized set-up of learning the d dimensiiional XOR data distribution. Consider one-hidden layer network with quadratic activation where x E Re We E R4
m
2 1. x)
Σ (x wy
2m
In the above, a, E {+1} are fixed during training and satisfy E, a; and only the first layer weights are trained. For initialization of first layer's weights we have Vi S m, S d wp,ij ~ (O, 4)- The data points (I, y) E {+1]d x (+1} are uniformly drawn from the resulting d- dimensional distribution of 2 points where the labels are determined as xx1) =2).. For the result in the next theorem, we assume the loss function the linear loss f(t tt and consider mini-batch SGD with the update rule w²+1 = w² 17 (w=), where at each step, n data points are drawn i.i.d. from the distribution to form F-)). The next theorem shows the computational and sample complexities of learning this dataset for the aforementioned setup.
iid
Theorem 2.4 (Improved guarantees for learning XOR). Assume mini-batch SGD with batch-size d (d) and step-size 7) m. Then, after T log(d) iterations the test accuracy satisfies with probability at least e (logm)) and data sampling,
- os(1) over the randomness of initialization
Ex.1 [ 21 -0a(1)
(10)
Hence, with logarithmic number of SGD steps we use ((d) samples in total to reach almost perfect test accuracy. We remark based on the guarantees of Theorem 2 the network's width can be constant and at most must be polynomial in d in order for Eq. 10 to hold with high probability. This aligns with experiments in Fig. 4 demonstrating that the network's width be independent of data dimension as a network of constant width (where m = 20) suffices for learning arbitrary high- dimensional XOR data. We also note the considcrable gains in iteration, sample and computational complexities by Theorem 2.4 resulting from escaping the NTK regime with our step-size selection. Contrary to Theorem 2.1 which required small step-size in accordance with the descent lemma, here the step-size is proportional to width. For comparison with recent results for this dataset we refer to Table To the best of our knowledge these are the best complexities on iteration and network width for this setup.
Remark 2.5. The proof of Theorem 2.4 (provided in Appendix E is nuanced and involves computing expected weights and their corresponding error terms due to SGD sampling noise for each parameter Vd
of the network. It is then showed that signal strength (i.e., the strength of important features) grows as 2' whereas the error terms due to sampling noise and initialization grow at most at the
Va rate (1 + poly(log(d]) )' (oly() +
2'x
Therefore, after log(d) steps the noise strength
(llgoly
reaches (log()) whereas the signal's 's magnitude is at least vd, letting the signal outgrow the noise and leading to the network classifying every point correctly.
Vd
3 NUMERICAL RESULTS
Experiments on learning under NTK with small step-size. In this section, we present numerical results on the behavior of the generalization bound derived Theorem 2. for real-world data (FashionMNIIST and MNIST datasets) and compare it with the empirical generalization gap.
For demonstrating our theoretical results, we are interested in the algorithmic- generalization bound (Eq. derived as,
Es F(Wr) f(wr))
2.2
Es
Σ F(w.))
(11)
n
8

---

Published as a conference paper at ICLR 2025
12 and fons (e
2.
14
24
Figure 1: Iteration-basee distance from initialization (fla,, woll training loss, test loss and generalization gap (i.e., test loss train loss) for training a two hidden-layer neural network with FushionMNIST dataset and two choices of step-size. Here n. 12 10 yn 500, and total number of parameters p 105.
Figure 2: Iteration- distance from initialization, training loss, test loss and generalization gap for training two hidden-layer neural network with FashionMNIST dataset and m 200.500. 500. Here 10a p ~ 2 (blue line), 6 x 10 (red line), and rj = 0.02.
Figure 3: Iteration- based distance from initialization, training loss, test loss and generalization gap for training two hidden-layer neural network with MNIST dataset and m 300, 600. Here 2 x 10 R 3 x (blue line), 8 x 10 (red line) and 0.02.
We find it helpful to note that the bound above requires the width condition in the theorem (i.e., =R[[==" woll () to be valid. However, verifying this condition is not feasible in general. Moreover, the bound is valid for expected generalization gap where the expectation is taken over data sampling. Therefore computing the exact values of both sides of the above inequality is computationally exhaustive. For our experiments we consider one realization to estimate these values. Due to both of these reasons, the theoretical test loss and generalization loss that we present in this section should only be taken as approximations of the general behavior of the bound and not as an actual verified bound on the generalization. However, order reduce these impacts we conduct several experiments with varying network's 's width.
We consider binary classification with 2-hidden layer network with softplus activation (a((t log(1 + e²)) trained by the logistic loss function. Figure 1 presents train, test and generalization behavior GD for learning a such a model with FashionMNIST dataset. The two lines each figure correspond to 77 0.01, 0.1. In the two rightmost plots, the resulting theoretical generalization and test loss curves derived from Eq. IT are compared with the empirical values. Note the good alignment between theoretical and empirical behavior for the generalization and test loss.
we consider a similar setup but we reduce the sample size 4000 training data in order to allow larger test-loss behavior. The resulting plots
similar behavior is observed in Figures S
In Figure 2
show the training and test loss performance for two choices of m = 250 and m = 500. In Figure 3 consider the MNIST dataset for 300 and m 600 and let the sample size be 2000. It

---

Published as a conference paper at ICLR 2025
n- step size -
120
Figure 4: Left: Misclassification error based on iteration in learning the dddimnenioonal XOR distri- bution with SGD. Right: Total number of SGD steps based on data dimension to reach approximately zero test error.
noteworthy that the findings in both figures bear similarities, with the theoretical bounds providing non-vacuous and accurate approximations for the test loss and generalization gap.
Experiments on learning the XOR distribution with large step-size. Figure S demonstrates the
test error curves associated with learning the XOR distribution according to the setting of Theorem
2.4 particular, we fix n 6d, 7) = m = 20 and set the total number of SGD steps as = [log(d)] Note that the number of iterations required to reach perfect accuracy grows with d. The right side of Figure provides further insight into the relationship between dimensionality and convergence rate. It displays the total number of SGI) steps required to reach test error below 0.01 for different values of d using n = 3d, m = 20. The results are averages over five independent experiments and highlight the logarithmic dependence of the total SGD iterations data dimension for achieving near-zero test error.
4 CONCLUSIONS AND FUTURE DIRECTIONS
We explored the convergence and generalization of smooth neural networks trained with gradient methods. Our first goal in this paper was derive generalization bounds through new stability- based approach which had not been discussed in the vast literature of deep learning. These findings represent an improvement over previous results that either required substantial over-parameterizatto or provided suboptimal generalization rates that depended on the network width. For general noisy data distributions, we also derived generalization guarantees showing that GD can reach the optimal test loss. We also showed that orders of magnitude improvements in sample and computational complexity are possible by surpassing the NTK limitations and using SGD with large step-size. Several directions remain open to future research:
It remains open to explore whether the minimum width conditions of Theorems be improved in terms of or n.
It is also interesting to extend the XOR analysis to the noisy setting where a fraction of the data points have corrupted labels.
The feature learning phenomenon in multi-index classification tasks remains largely un- explored. While we believe the XOR setup is must-take first step, extensions to other multi-index models can shed further light on the strengths and limitations of neural networks.
We also aim to understand the potential benefits of network depth in either the NTK regime feature learning i.e., whether adding a single layer can improve sample complexity or reduce the total number of SGD iterations.
ACKNOWLEDGEMENTS
This works was supported by NSF grant CCF 2217058.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. The merged-staircase property: necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks. In Conference on Learning Theory, pp. 4782 4887. PMLR, 2022.
Jimmy Ba, Murat Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang. High- dimensional asymptotics of feature learning: How one gradient step improves the representation. Advances in Neural Information Processing Systems, 35:37932-37946, 2022.
Yu Bai and Jason D Lee. Beyond linearization: On quadratic and higher-order approximation of wide neural networks. arXiv preprint arXiv: 2019.
Arindam Banerjee, Pedro Cisneros- Risncros-Velarde, Libin Zhu, and Mikhail Belkin. Restricted strong convexity of deep learning models with smooth activations. arXiv preprint arXiv:2209.15100
2022.
Boaz Barak, Benjamin Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang. Hidden progress in deep learning: Sgd learns parities near the computational limit, Advances in Neural Information Processing Systems, 15:21750--2100 2022.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-norrmaizedd normaliize margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
Olivier Bousquet and André Flisseeff. Stability and generalization. Jourmal of Machine Learning Research (JMLR), 2:499-526, 2002.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in neural information processing systems, 32, 2019.
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much over-parameterization is sufficient learn deep re (lu) networks? In International Conference on Learning Representations, 2021. URL htt.h:tts:/oooom http///pppp//eee/////////// net wwr.moirrmmooooo foe u2a6
Hugo Cui, Luca Pesce. Yatin Dandi, Florent Krzakala, Yue Lu, Lenka Zdeborová, and Bruno Loureiro. Asymptotics of feature learning in two-layer networks after one gradient-step. arXiv preprint arXiv:2402. 04980, 2024.
Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn representations with gradient descent. In Conference on Learning Theory, pp. 5413-5452. PMLR, 2022.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pp. 1675-1685. PMLR, 2019.
Margalit Glasgow. Sgd finds then tunes features in two-layer neural networks with near-optimal sample complexity: A case study in the xor problem. In The Twelfth International Conference on Learning Representations, 2024.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pp. 297-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 (ICML), volume 48, pp. 1225-1234, 2016.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Neural Information Processing Systems (NeurIPS), volume 31, 2018.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks. International Conference on Learning Representations, 2020.
11

---

Published as a conference paper at ICLR 2025
Beatrice Laurent and Pascal Massart. Adaptive estimation of quadratic functional by model selection. Annals of statistics, pp. 1302-1338, 2000.
Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference Machine Learning (ICML), volume 119, pp. 5809-5819, 2020.
Mingchen Li, Mahdi Soltanolkotabi, and Samet Oymak. Gradient descent with early stopping is provably robust label noise for overparameterizee neural networks. In International conference artificial intelligence and statistics, pp. 4313-4324, PMLR, 2020.
Chaoyue Liu, Libin Zhu, and Misha Belkin. On the linearity of large non-linear models: when and why the tangent kernel constant. Advances in Neural Information Processing Systems, 33: 15954 15964, 2020.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59: 85-116, 2022.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-hayesian approach to spectrally- normalized margin bounds for neural networks. In International Conference on Learning Repre- sentations, 2018.
Atsushi Nitanda, Geoffrey Chinot, and Taiji Suzuki. Gradient descent can learn less over-parameterized two-layer neural networks classification problems. arXiv preprini arXiv:1905.09870, 2019.
Samet Oymak and Mahdi Soltanolkotabi. Overparameterized nonlinear learning: Gradient descent takes the shortest path? International Conference on Machine Learning, pp. 4951-49666 PMIR, 2019.
Dominic Richards and Mike Rabbat. Learning with gradient descent and weakly convex losses. In International Conference on Artificial Intelligence and Statistics, pp. 1990-19999 1998. PMLR, 2021.
Matan Schliserman and Tomer Koren. Stability vs implicit bias of gradient methods on separable data and beyond. In Conference on Learning Theory (COLT), volume 178, pp. 3380-3394, 2022.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Hossein Taheri and Christos Thrampoulidis. Generalization and stability of interpolating neural networks with minimal width. Journal of Machine Learning Research, 25(156): 1-1,, 2024.
Matus Telgarsky. Feature selection and low test error in shallow low-rotation relu networks. In The Eleventh International Conference Learning Representations, 2023.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science,
volume 47. Cambridge university press, 2018
Puyu Wang, Yunwen Lei, Di Wang. Yiming Ying, and Ding-Xuan Zhou. Generalization guarantees of gradient descent for multi-layer neural networks. arXiv preprint arXiv:2305. 2023.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. Advances in Neural Information Processing Systems, 32, 2019.
12


Reviews:
[{"review_id": "yAqSkoqsoK", "reviewer": "Reviewer_hUr4", "summary": "This paper obtains convergence and generalization bounds for gradient descent training of neural networks with smooth activation functions. An algorithmic stability analysis exploiting the Hessian properties in the gradient descent path allows to bound the generalization gap with the cumulative optimization error.  Ultimately, the bound on the test loss depends on the Euclidean distance with initialization and the Lipschitz constant of the network at initialization. Experiments with a 2-hidden layer network on MNIST and FashionMNIST show that the theoretical bounds provide accurate approximations for the test loss and generalization gap.  Under an NTK separability condition, the results of the paper (with smooth activations) lead to a better bound on the test loss then previous results with ReLU activation functions ($\\sqrt{\\frac{m}{n}}$ is replaced with $\\frac{1}{n}$). Furthermore, on the specific problem of a d-dimensional XOR distribution, using quadratic activations with a large step size, only log(d) iterations (and constant width) are needed to obtain perfect test accuracy with n = O(d) samples. An experiment also confirms the logarithmic dependency on data dimension.", "questions": "1) Do you think that the bounds holding for ReLu networks could be improved to match the bounds of your paper, or is the smoothness assumption necessary to obtain the improvement?\n\n2) Could you clarify the main novel techniques or approaches used in the proofs of your main results, particularly in relation to previous work in this area?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-The paper is clearly written and well organized.\n\n-The paper provides novel convergence and generalization bounds for neural networks with smooth activations, which are significantly better than prior bounds derived for ReLU networks (the test loss bound obtained is width independent). This is important for understanding how generalization of neural networks with smooth activations compares to generalization of ReLU neural networks.\n\n-The result showing efficient learning for the XOR problem with linear sample complexity is a notable contribution.", "weaknesses": "-Experiments on deep networks are done on a small neural network. Also, the expectations over S are estimated with one realization of S.\n\n-The method to bound the spectral norm of the Hessian based on the distance from initialization is not new, limiting the novelty of the approach.\n\n-The paper does not clarify whether the improved bounds are fundamentally due to the smoothness of the activation functions or if they result from limitations in the proof techniques used in previous bounds for ReLU networks, which may have led to weaker results in the non-smooth case.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "h4QjhQxRrG", "reviewer": "Reviewer_gGtd", "summary": "This paper studies the training convergence guarantee and the generalization error of deep MLPs with quadratic activation when applied to binary classification tasks. The paper considers the parameterization of the neural network in the NTK regime, and shows a tigher generalization bound together with a smaller over-parameterization requirement compared with previous work. In addition to the analysis of the noiseless separable data scheme, the paper also considers a noisy data scheme and a XOR classification task. In particular, the paper shows that for the XOR classification, using a large step size and effectively escape the NTK regime and learns useful features. The paper also provided experimental results to verify its theoretical conclusion.", "questions": "1. In Eq. (5), consider the special case of $n=1$, where we have only one sample. Suppose we initialize $w_0$ at $w^\\star$ and suppose $w^\\star$ achieves zero training error. Then by Eq. (5), the generalization error will be $0$. This means that even in the case where we have only one trainig sample, every neural network parameter that achieves zero training error will generalize well, which is counter-intuitive. Am I missing something here?\n\n2. In Eq. (6), plugging in $\\hat{F} \\leq \\frac{4\\rho^{*2}}{\\eta T}$, should we have an additional $\\log T$ on the right-hand side due to a summation of $\\frac{1}{t}$ for $t = 1,\\dots, T-1$?\n\n3. In the cited paper Lei and Ying (2020), I did not found Lemma B.3, which is used in the proof of the generalization error. Is the paper referring to a different lemma? Also, it seems that the leave-one-out error in Lei and Ying is defined by replacing the $i$th sample with another random sample, not deleting the $i$th sample.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper obtains a tigher bound on the generalization error compared with previous work. In particular, while previous work usually achieves a $O(\\frac{1}{\\sqrt{n}})$ generalization error, this paper achieves a $O(\\frac{1}{n})$ error.\n\n2. In the noiseless data scheme, the paper derives favorable convergence guarantee under only a constant over-parameterization requirement.\n\n3. The paper has a nice extension of their theoretical work from the noiseless data scheme to the noisy data scheme as well as the XOR classification task.", "weaknesses": "1. In Theorem 2.1, the over-parameterization requirement scales with $\\\\Omega(\\\\rho^{*6L+4})$. Later in the discussion, the paper stated $\\\\rho = O(\\\\log n / \\\\gamma)$, where $\\\\gamma$ is the margin width. When we treat $L$, the network depth, not as a constant, the over-parameterization requirement can be as large as $\\\\Omega(\\\\frac{(\\\\log n)^{6L+4}}{\\\\gamma^{6L+4}})$, which might be unfavorable.\n\n2. The setting studied in the paper are not clearly explained, and some notations are not introduced before use. For instance, it is not clear what is $\\mathcal{S}$ is in Eq.(5), and what it means to take expectation over it. Moreover, in Section 2.1.2, it is not clear how the noise in the data are generated.\n\n3. In Assumption 1, the separability condition is defined over the tangent feature at initialization. Because the separability is defined in this random feature model, it would naturally imply an implicit lower bound on the over-parameterization: for instance, the more parameters we have, the more random features we will have, and a higher probability the data will be separable when mapped to the feature space.\n\n4. Some theoretical results seems confusing; see Questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LF7JMxG7GL", "reviewer": "Reviewer_Udj5", "summary": "This paper studies the data-dependent convergence and generalization of gradient methods in neural networks with smooth activations. The authors provide a tighter, algorithm-dependent bound on excess risk for deep networks trained with logistic loss, improving on Rademacher complexity-based bounds. These results emphasize the role of initialization, particularly in small-width networks and margin-separable data.", "questions": "1.\tTable in page 2 is mis-labeled as Table 2. \n2.\tThe authors claim that leveraging the Hessian structure in the gradient descent path is the key for their theoretical improvements over the past literature. But I feel the mathematical intuition is not well stated in the main paper. When it is compared with the previous literature (for instance Chen et al, 2021), how does considering the hessian structure benefit the author to prove Theorem 2.1? \n3.\tIn least-squares regression, the Neural Tangent Kernel (NTK) benefits from the fact that gradient descent keeps weight updates close to their initialization, which linearizes the dynamics in parameter space and makes the analysis more tractable. I suspect this approach will similarly apply to classification tasks if the authors use the NTK framework. Given this, the role of initialization mentioned in the main paper isn't particularly surprising. Could the authors elaborate on the unique insights that arise when studying classification problems, which might not be evident when analyzing regression problems, specifically in terms of the role of initialization?\n4.     Somehow, I felt Subsection 2.2 is disconnected to the remaining part of the paper, as the problem settings seem to be different from the previous parts. I suspect this is because of technical difficulties authors might have encountered, but it would be great if authors can make connections between this Subsection and previous parts. For example, how are the particular techniques from earlier sections linked to the XOR distribution analysis in 2.2?\n5.\tIn Theorem 2.4, the step size is equal to the width of the network. Can it be arbitrarily large? Are there any restrictions on the step size?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, the contribution of this paper is great filling the gap between practice and theory.", "weaknesses": "Please see the questions below", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FRQ6arRdws", "reviewer": "Reviewer_zVMC", "summary": "This paper studies convergence and generalization for deep neural networks with smooth activation trained by gradient descent. This paper shows several improved results on test error compared with previous works for the following scenarios: (1) noiseless data with separable NTK feature, and (2) noisy data and (3) XOR distribution.", "questions": "None.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This work presents several improved results from prior works. In particular, the authors are able to show an improved bound on the network width by requiring $\\lvert w^\\star - w_0 \\rvert \\lesssim m^{O(1/L)}$, which implies that the NTK regime can happen under a far more relaxed conditions than what previous work suggested. Such results can be important and interesting. The authors then utilize this improvement to derive improved bounds for several classical NTK settings like NTK separable data and noisy data.", "weaknesses": "Although the results in this work are impressive, a more detailed description on how the authors achieved this improvement is needed. In particular, the authors mentioned in line 84, 85 that the reason for the improvement in the network's width is by exploring the objective's Hessian structure in the gradient descent path. This sounds very interesting. However, I didn't find any high level discussion/description on this in the main text. I would like the authors to explain how they get this improvement. How does your analysis compare with the prior work that also utilized the Hessian structure? What is the novelty in your analysis such that you can achieve this improvement?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)