Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks
Authors: Yunwen Lei
Rong Jin
Yiming Ying
Venue: NeurIPS 2022 Accept (2022)
Keywords: Statistical Learning Theory
Algorithmic Stability
Shallow Neural Networks
Generalization Error

Abstract: While significant theoretical progress has been achieved,  unveiling the generalization mystery of overparameterized neural networks still remains largely elusive. In this paper, we study the generalization behavior of shallow neural networks (SNNs) by leveraging the concept of algorithmic stability. We consider gradient descent (GD) and stochastic gradient descent (SGD) to train SNNs, for both of which we develop consistent excess risk bounds by balancing the optimization and generalization via early-stopping. As compared to existing analysis on GD, our new analysis requires a relaxed overparameterization assumption and also  applies to SGD. The key for the improvement is a better estimation of the smallest eigenvalues of the Hessian matrices of the empirical risks and the loss function along the trajectories of GD and SGD by providing a refined estimation of their iterates.

Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks
Yunwen Lei'* Rong Jin Yiming Ying
Department of Mathematics, Hong Kong Baptist University, Kowloon, Hong Kong, China Machine Intelligence Technology Lab, Alibaba Group
3 Department of Mathematics and Statistics, State University of New York at Albany, USA yunwenChkbu. edu. hkk rongjinemail@gue com yyingSalbany.co edu
Abstract
While significant theoretical progress has been achieved, unveiling the generaliza- tion mystery of overparameterized neural networks still remains largely elusive. In this paper, study the generalization behavior of shallow neural networks (SNNs) by leveraging the concept of algorithmic stability. We consider gradient descent (GD) and stochastic gradient descent (SGD) to train SNNs, for both of which we develop consistent excess risk bounds by balancing the optimization and generalization via early-stopping. As compared to existing analysis on GD, our new analysis requires a relaxed overparameterization assumption and also applies to SGD. The key for the improvement is better estimation of the smallest eigenvalues of the Hessian matrices of the empirical risks and the loss function along the trajectories of GD and SGD by providing refined estimation of their iterates.
Introduction
Neural networks have achieved remarkable success in solving large-scale machine learning problems in various application domains such as computer vision and natural language processing [33]. First- order methods such gradient descent (GD) and stochastic gradient descent (SGD) are mainstream optimization algorithms for training neural networks due to their simplicity and efficiency 33 50) Although the associated optimization problems are nonconvex and nonsmooth, GD/SGD can still find a model with very small or even zero training error [16, 20 34 39 64 66). At the same time, the models found by such first-order methods has demonstrated good generalization performance on test data despite neural networks are often highly overparameterized in the sense that the number of parameters much larger than the size of training examples
These surprising phenomena have triggered surge of research activities in understanding the gener- alization ability of neural networks. Generalization analysis typically uses complexity measures such as VC dimension, covering numbers or Rademacher complexities to develop capacity-depender which, however, may explain well the generalization of overparameter- ized neural networks. Impressive alternatives have been proposed which include the compression approach (4) the norm-based analysis [8] 25], the PAC-Bayes analysis [21] and the neural tangent kernel (NTK) approach [5] (8). In particular, the NTK approach shows that the overparameterization pulls the dynamic of GD on neural networks close to its counterpart on kernelized machine with the least-square loss 5 20), which shows how overparameterizztion can help both optimization and generalization. However, this approach often requires very high overparameterization gain useful
bounds 8 25 42 48),
results 6 55 60).
'The work done when Yunwen the University of Birmingham CCorresoonding author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The recent appealing work [51] presents a kernel-free approach to study how overparamelerizzttin would improve the generalization for shallow neural networks (SNNs). Their basic tool is the algorithmic stability [12], which measures how the replacement of an observation would change the algorithm output. The authors showed the excess risk of GD is controlled by an interpolating network with the shortest GD path from the initialization, which is able to recover the existing NTKK-aaed risk bounds as an application. This result achieved under an overparameteriiation assumption m 2 (nfZ)s where is the number of hidden nodes, 1/ is the learning rate (step size) and 'I' is the number of iterations. While this result is very interesting and impressive, the overparameterization requirement 2 (n/T)² may still be more restrictive than that used in practice. Furthermore, the analysis in 51 is restricted to the case of the bull-batch GD. One natural question thus arises:
Can we relax the overparameterization requirement for GD in [T] and further establish the stability and generalization of SGD for neural networks?
In this paper, provide an affirmative answer to the above question by establishing refined stability analysis for the gradient methods (GD and SGD) for training SNNs. Our contributions are summarized follows.
We develop excess risk bounds for GD on SNNs under a relaxed overparameterization. In more details, we show that GD can achieve the excess risk bounds of the order O(1/vn) if m Z (nIT),, where is the sample size. This improves the existing overparameterizattin condition m Z (1/T)s [5T]. Under a low noise condition, our excess risk bounds improve to O(1/n).
One key technical novelty in relaxing the overparameterization condition for GD in 51 is to improve the existing bounds on the norm of iterate sequence (W;). As we soon show in Section 4.1 below, this improvement is achieved by a better estimation of the smallest eigenvalue of the
Hessian matrix of the empirical risk. Specifically, the analysis [5]] uses |W, w ll2 = =(vT))
to nower-bound the smallest eigenvalue at aW, (1 a) W by
W. w 112 1).
where a E (0, 1) and (W(")) is an iterate sequence on a neighboring dataset. As a comparison, we show ||W- ( || O(n (m)()² which can be much better than (vvnt)) if is large. Furthermore, our bound depends on the training errors and would improve in a low noise condition. Under some specific cases, we can further show that EE| W. 1 O(), which independent of the iteration number.
3. We extend our analysis to SGD under the relaxed overparameterization condition m 2 (nTT'² As compared GD, SGD has a computational advantage the sense that it can achieve the same risk bounds with less computational cost. The key analysis of SGD relies on the estimation of the Hessian spectrum of the loss over the individual training datum. This is more challenging than estimating the counterpart of the empirical risk of GD since several properties of GD do not hold for SGD such as the monotonicity of the objective functions along the optimization process. To overcome this technical hurdle, we provide a refined analysis to control the bounds of the iterates of SGD which further leads to the estimation the Hessian spectrum of the loss.
The remaining parts of the paper are organized as follows. We present the related work in Section and illustrate the formulation of the problem in Section 3 We present the main results in Section and sketch the idea of the proof in Section 5
We conclude the paper in Section
2 Related Work
In this section, we group the related work into two categories: the related work on stability analysis and the related work on generalization analysis of neural networks.
Stability and generalization. As a fundamental concept in statistical learning theory, algorithmic stability considers how the perturbation of training examples would affect the output of an algo- rithm (53] which has close connection to the learnability [46 [56). The framework of using the concept of algorithmic stability to derive generalization bounds was established in influential paper 12), where the uniform stability was introduced and was studied for regularization schemes.
Since then, various concepts of stability have been introduced to study the generalization gaps,

---

including the hypothesis stability 12 [22]. on on-average stability [32 [5], Bayes stability [38, locally
elastic stability [19] and argument/mmode stability [3] [3 A very successful application of stability
analysis is to use it to study SGD for smooth, Lipschitz and convex problems [26]. which motivates
a lot of follow-up studies on stochastic optimization K I0 15
R5
36 49). The smoothness
assumption in [26] was recently removed by taking very small step sizes 1T 35 while the convexity
assumption was relaxed to a weak convexity assumption [52]. Under a Lojasi-wo (PL) condition, it was shown that any algorithm converge to global minima would generalize without con- vexity conditions 05 (36. . The trade-off between stability and optimization was studied in [17]. Other
than stochastic optimization, stability has found wide applications in structured prediction 44 meta
learning [45] transfer learning [32), hyperparameter optimization [7], minimax problems [23 37 65
and adversarial training [61]. While most of the stability analysis imply generalization bounds in
expectation, recent studies show that uniform stability can yield almost optimal high-probability
bounds K 24 30
Generalization analysis of Neural Networks (NNs). Generalization analysis of NNs has attracted increasing attention to understand their great success in practice. A popular approach to study the generalization of SNNs is via the uniform convergence approach, which studies the uniform 67]. However, this approach leads to sapacity-basee bounds which do not well explain why overparameterizes models can still generalize well to testing examples [47). To address this problem, researchers turn to other approaches such as the compression approach [4]. the PAC-Bayes approach [2T], the NTK approach [28] and the
generalization gaps in a hypothesis space g 25
41
48
neural tangent random feature approach [14.. The key idea of the NTK approach is that, under sufficient overparameterivation and random initialization, the dynamics of GD on SNNs is close to the dynamics of GD generalization bounds based on a data-dependent complexity measure, which can distinguish the difference between learning with random labels and learning with true labels (5) Meanwhile, recent studies suggest the connection to kernels might be only good at interpreting the performance of very wide networks 6 55 660, much more overparameterized than those used in reality [51]. The most related work is the recent analysis of GD for SNNs without either the NTK condition or the PL condition [51] They developed nontrivial generalization bounds under an overparameteriizatio assumption m 2 (n/T")5 Furthermore, their analysis allows for improved bounds if there is no label noise, and shows an interesting connection to NTK-based risk bounds. It should be mentioned that
least-squares problem associated to the NTK 5 20 'Tis leads to
the analysis in (5] considers the ReLU activation function, while the discussions in 51 focus on smooth activation functions.
3 Problem Setup
Let P be a probability distribution defined on a sample space Z := X x y. where X C Rd and Y C R. Let S = {zz (x,,4) : I,....,,, n be a sample drawn from P. Based on we wish to build model f : X' + R. The performance of f can be measured by the population risk defined as
1 //xe xxy (1x))=))dP((xx v), 2
L(
which is unknown and can be approximated by the empirical risk Ls(f) E (f(x.) - vi) 2
A minimizer of the population risk is the regression function fx(x) = Blyl x]. where E|-||] denotes the conditional expectation given x. this paper, we consider a shallow neural network of the form
m
fw = Σ uoo((we. x)),
where we fix M4 E v/m v
(1) 1. R IR is an activation function and W (W1 W..
ddxmm is the weight matrix. In the above formulation, wt denotes the weight of the edge connecting the input to the k-th hidden node, and μe is the weight of the edge connecting the k--th hidden node to the output node. Here m is the number of nodes in the hidden layer and (,,-) denotes the inner product operator. For simplicity, we denote
L(W)= = T.(Sw) and Ls(W)= = T.s (Jw).
Let W x = arg minw (WW. We choose a minimizer of I.(W) with the smallest norm. The relative behavior of model W w.n.t W is quantified by the excess population risk L(W) L(W"). We
3

---

denote by ((: = (x)((x) y)² the loss function of W on single example z = (x, y). Two representative algorithms to minimize the empirical risk are GD and SGD. Definition (Gradient Descent), Let Wo RRdx be initialization point. GD updates {W:) by
W441 s+1 W. (We))
(3.1)
where 7) > 0 is the step size and V denotes the gradient operator. Definition 2 (Stochastic Gradient Descent). [W,) as follows
Let Wo E Iddxm be an initialization point. SGD updates
W W4+1 W. 7V (.:
(3.2)
where & is drawn from the uniform distribution over [n] =- n..
We are interested in the excess population risk of models trained by GD/SGD with iterations. We begin with the introduction of some assumptions activations and loss functions. Assumptions were also imposed in [5T]. We denote by || ||2 the Frobenius norm.
Assumption 1 (Activation). The activation ((u) is continuous and twice differentiable with constant Bg, BBg B > O bounding [Ø(u] S Bg, ( (u)) & Bar and (""()] S B&r for any u E IR.
Activation functions satisfying Assumption[[ include sigmoid and hyperbolic tangent activations (51. Assumption 2 (Inputs, labels, and the loss function). There exists constants Cz, Cy: Co > 0 such that ||x|| S Cz. |u| S Cy and ((Wo; z) I Co for any y and z.
Our third assumption on the regularity of the learning problems. For any 0, we define {L(W) + A|[W - Woll3].
W = arg min WERdim
Note we use the asterisk to differentiate W and the GD iterate W, Assumption 3 (Regularity). Assume there exist (0, and ca 0 such that
Ax = L(W;)) - L(W') + W| Woll2 S co..
Assumption related to the approximation error which characterize how well the SNNs approximate the least population risk, which is motivated from the approximation analysis in kernel learning. [ (6). In more details, a typical assumption in kernel learning is miny O(x"), where E (0, 1] depends on the regularity of target function f and || IIx denotes the norm in a reproducing kernel Hilbert space. If W ||2 = O(1), then is clear that
=
L(WX) L(W") A| Woll = L(W") L(W") + A||W W O()) (3.3)
and therefore Assumption holds with a 1. Our analysis is based on the following error decomposition of the excess risk:
B(L(W)))-<(w') = (EIL(W))) W )] +E Ls Lss
W
Woll3]
7T
L(W / w
Woll - (3.4)
where we have used [[[ss(( (WL L(W" due the independence between W and S. We refer to the first term E[L(W 77 and the second term E. L.
77
r)] E| (T)) as the generalization error (generalization gap) (sW T/ W Woll as the optimization error.
As in [51], we will use the on-average model stability to control the generalization error and tools in optimization theory to control the optimization error. We will use Assumption 3 to control the last term L(W* + + + Wolk L(W"). The on-average model stability considers the
sensitivity of the output models up to the perturbation of single example, and the sensitivity is averaged by traversing the single example throughout the sample set. Let A(S) be the output model by applying an algorithm A to S.
Definition 3 (On-average Model Stability (35)). Let {ZI,..., .......,. ,,, and S' (z),..., 2 be drawn independently from P. For any E [n]. define S(i) = (zi,.... Zi- 1, 2/1 Zitl,.... Zn as the set formed from S by replacing the i-th element with z/. We say randomized algorithm A is
on-average model e-stable if Es,s A [1 Σx_ |IA(S) A(S()) < e.

---

The connection between the generalization error and the on-average model stability was established the following lemma. We say function W + g(W) is p-smooth if, for any W and W', we have
(V) Vy(W"))) 1 S p p/ W'
Lemma 1 (Stability and Generalization 35 ). Let A be algorithm. If for any the map W - ((W;z) is p-smooth and nonnegative, then
P
B(IA(()) (2
2p ([IA(S)-
Main Results
In this section, present our main results the risk bounds of GD and SGD which are summarized
in Table [ We denote B x B' if there exist some universal constants 0j and 0o > such that
a, < B' B c2 We denote B 2 B' if there exists universal constant >> 0 such that B 2 cB'.
Algorithm
Excess risk bound
Low noise
overparameterizztion
Computation
O T+3)
No
ž (nTT' x .+1
O(n
GD 51
O(nJa)
Yes
m 2 (1TT)
O
GD
O(n 145)
No
ž (n/T'²² n
O(n
This work
O(n=a)
Yes
m 2 (T/T)² x n
O(
SGD
O(n rīa)
No
Z (n/T'² x n i
O
This work
O(n-a)
Yes
2 (nTT)3 n
O
Table I: Summary of results. Low noise means L. ((W)) inf L(W O. Computation means the complexity of the gradient computation, which is n7 for GD and T for SGD. The results in second and third rows for GD are derived by combining Assumption 3 with the risk bounds in [51]. In particular, if a = 1, our results indicate both GD and SGD for 2-layer SNNs with subquadratic overparamettrization m 2 3/2 can lead optimal risk rate On ((/))/2) while the results in [46] need superquadratic overparametrization m Z 5/2
4.1 Gradient Descent
We first study the excess risk of the GD algorithm for SNNs. Let e the base of the natural logarithm.
Let C% + BBr BB
BgnCy) and b = C (By Ca + Co).
Theorem (Generalization Error). Let Assumptions ! hold. Let (We) be produced by Eq. 3.1
In < 12p) and
m 2 32Cor 12n-1Vp(ppi + (1 mp) + +1);
(4.1)
then for any E [T] we have
1e2 n²
4emp
E[L(W,) Ls(W.)] <
E W Wl
Remark Under an assumption m > 3, a bound similar to Theorem was established in [T]. We relax this assumption to 2 (177)²/ /n² + 27 in Eq. (4.1) As will show, typical choice is
ofT X n -.. In this case, the assumption in Eq. 14.1 becomes m 2 (nT))n -.. + T72 which is
milder than the assumption m 2 (,T)² in [51]. This improvement is achieved by better estimation
of the smallest eigenvalue of Hessian matrix. Indeed, the smallest eigenvalue at a W, + (1-a) w:(" is lower bounded by -.m (l) w 1) (up to constant factor), where E (0, 1) and {w! } is the SGD sequence on S(0), The analysis (51 uses || w 1|2 O to control the smallest eigenvalue. Instead, show [W,- w l| O(n (nnt) (Lemma B.I
5

---

A key step to relax the overparameterization is to build bound on E|| W. W' [2). The existing analysis shows that IW, Woll O(r)) [51], which grows infinity we more and more iterations. In the following lemma to be proved in Section B.1 we improve it to
B W [2] O nLT n Ej= [[Ls( [W", Wo 2 In particular, if 1/T = O(vn)
Wo 3 = 01), this bound becomes [I| W. W 47
T | = O(1). This explains why we relax the overparameterization assumption from m 2 (1)7)) in 51 to m Z (177)² Furthermore, the bound involves دコ ([Ls(W,) which would improve if the training errors are small, which is critical to get fast rates in low noise case. Our basic idea to prove Lemma B is to first control in terms of training errors. Our novelty is to replace these training errors with testing errors by using Theorem 2 which allows to use Eq.
and [ 7p
B[[WW W [|
remove some terms. The proof
is given in Section B.2 For simplicity we assume [W
2 1.
Lemma 3. Let Assumptions 1
hold. Let [W,) be produced by Eq. 3.1 If 1/(p), Eq.
4.1
holds,
[L L(W") ) Vs (0, (0.1.......
1}
(4.2)
and
M (v
Bl| W Woll2))
(4.3)
then for any E [T] we have
88 88E2p2
Sen"Tp Σ
W W. W S RT ==
ELLs (|
+ w 77
- Woll.
112
Remark 2.
We impose the assumption (W.(
.) 2 L(W, vs "
T 1}. T
this
assumption does not hold, then Assumption 3 implies further
min .E .' B[.(W.)] - E[L((W)] s L(W", 3 B[L(W")] O(TiT))").
This shows the violation of Eq. (4.2) already implies a model W., f E [Z]] with a very small excess risk, and therefore the assumption Eq. (4.2) does not essentially affect our results.
It should be mentioned that if W 12 (1) we can derive similar results by replacing W in क the analysis with W (note W already satisfies the inequality L L(W*) - L(W") + / l Wol = ((1((rT)) and therefore can play the role of W", ). In this case, we no longer require the assumption 4.2) Indeed, Eq. 4.2) always holds with W "1 replaced by W due to the inequality
L(W.) N L(W"). It should be mentioned that the bound in Lemma 3 is stated in expectation. Therefore, we cannot directly combine this bound and the uniform convergence analysis to derive generalization bounds.
Now we present the optimization error bounds for GD. Recall Ry defined in Lemma The proof given in Section B.2
Theorem 4 (Optimization ErTor). Let Assumptions 7 with r < 1/(2)) Eg.
2 hold. Let (W,) be produced by Eq.
3.1
and (.3) hold, then
bRT Vm
ELLs(W,)) S L(W",
W T/
Woll
(IW",
Wollz / CT)T.))
oT
Remark 3. The following optimization error bounds were established in 51
W - Woll
bCo(nn)))
Ls(WT) < min W [L((W) +
(4.4)
n/
m
A key difference between the above bound and Theorem is that Eq. (4.4 involves term
(m7')
vm
while Theorem involves a term of /vII Rr vm
If Rv o(1T)), then the optimization error bounds

---

in Theorem would be tighter than Eq. the following optimization eтror bounds
4.4
Indeed, the analysis in [1] requires m 2 (nI) to get
Ls(Wr) S min!
{ Lss(W) {
+
Woll
Woll
+ o
1 n/T
W
Vm
As comparison, if Rt = (1), Theorem
requires the assumption m Z (nT)'s to derive
I Woll
|W
Wol
B[4s(Wr)) S L(W"
L(W"
T/
m
1/T
T/
We combine the above discussions generalization and optimization error bounds together to derive the following excess risk bounds. Note the right-hand side of Eq. (4.1). 4.3) and Eq. 44.5) are of the order of (n)T)a if ryT O(n) and [ Wollz = O(vi)) The proofs of Theorem 5 and
Corollary 6 are given in Section B.3
Theorem 5 (Excess Population Risk). Let Assumptions 1
hold. Let (Wr} be produced by Eq. hold and
3.1
with 17 1/(2)). If On). Eq. 4.1
Se² Be²p²"11" T
T)n (7 (T([I",
Wollz + v2niI(Co
m N
(4.5)
n²
n
then
((L(WT)) L(W") =0 (TTL(W)) )
where Ax is defined in Assumption 3
The bound in Theorem was also obtained in [51 under the assumption Z (1)7)5. As direct corollary, we can use Assumption to show that GD can achieve excess risk bounds the order which
O(n I== in the general case, and bounds of the order O(n-*) in the case L(W*)
due to the incorporation of empirical risks in the generalization bounds. The basic idea is to balance the optimization and generalization via early-stopping (29 40 58
63 Similar bounds can
be derived by the analysis in [51] under Assumption
Corollary 6. Let Assumption 3 hold and assumptions in Theorem 5 hold.
(a) Iewe choose TiT n and m (1/T)3 nn+T, then B(I((T)) I.(W)) O(n I+a
(b) L(W") O, choosing nT and (1TT))3 n implies that E(L(W,)) On)
Remark 4. Other than the stability analysis [51] there are some discussions on the stability analysis for nonconvex functions that can be applied to SNNs [15] 26 36 68). The discussions (26) use step sizes 7 O(1/t) /t to get meaningful stability bounds, which, however, is not sufficient for good convergence optimization errors. The discussions in [5| 36 68 impose a PL condition. and their error bounds depend condition number which can be large practice. A recent paper (27) studies SGD for one-hidden-laye -laer ReLU network with L2 regularization from the NTK perspective and derives the appealing minimax optimal rate under the assumption that is sufficiently large (e.g., m is at least larger than O ). However, it is hard to derive a direct comparison since we study one- mee-iddden-layrr network with smooth activation function. Furthermore,
result holds if & 12p2,, which is independent of m and n and outside of the NTK regime. As a comparison, the analysis based on NTK [34] requires 1) S 2/> (maxmm)) where θ E R (mmd) ((md) is an neural tangent kernel and therefore the learning rate there very small.
4.2 Stochastic Gradient Descent
As compared to GD, the analysis of SGD is more challenging since several properties of GD do not hold for SGD. For example, the analysis in (51) relies critically the monotonicity of the sequence (Ls(W.) which does not hold for SGD. Furthermore, the introduced randomness {i, increases the variance of the iterates, which increases the difficulty of controlling the norm of iterates.
We first develop stability and generalization bounds of SGD. In particular, we are interested in
generalization bounds incorporating the training errors in the analysis 332 35 51] This shows
7

---

how good optimization would improve generalization, which is consistent with the analysis of SGD convex setting [35]. Eq.
(.7) gives on-average model stability bounds, which imply
generalization bounds in Theorem 7 The proof of Theorem 7 is given in Section C.2 Without
loss of generality we assume 47'CCo 1. Let R. max (2 |W", OF -Woll23 and
8' = C. Bo + V2Co). Let S be defined as in Definition 3
Theorem (Stability and Generalization). Let Assumptions 1
2 hold. Let {Wi)e and (W h be
produced by SGD with S 1/(2)) on S and ((1,, respectively, If
m 161 (6' )2 )2(1 +2mp)²
(4.6)
then for any T we have
8eap(1 + 1/n)//²
w E B[I
t41 S
R [.ss (W,)
(4.7)
Furthermore, we have the following generalization bounds
4e pe t/n)mn
B(L(W,) Ls (w.))
(W)s(W
n
==0
(1 E|+s
B[Ls(W,))) $
4epmy
j=0
We now consider the optimization bounds of SGD for SNNs. In the following theorem, give a bound on the average of the optimization errors for the sequence of SGD iterates. Recall that Rr is defined above Theorem Let A max,==0....
[[[[ W
2 for any N.
Theorem (Optimization Error). Let Assumptions " 1/p)). Eq. (4.6) and Eq. 4.2 hold, then
hold. Ler (We)e be produced by SGD with
T-1
2T Rr
21
E (W,,)
W.) Ls( W 22
S R[[
W 2
+ 2p
([.)(
vm
4.8 be satisfied by choosing m = (1 since RG O( O(VTT), which matches the overparameterization requirement of GD and improves the requirement Z (n/ in (3I] The proofs of Theorem 9 and Corollary I0 are given in Section C.3
Finally, develop the excess risk bounds for SGD SNNs. Note Eq.
Theorem (Excess Population Risk). Let Assumptions and hold. Let [We) be produced by and Eq 4.2 hold. nf 1/(2p),
(6 R2) (1 + 2np)² m max T6
4e mp?nTT(1 + T/n) 4oT (1 + +//m)//
)
4(8UT )
(4.8)
Vn
and T = ((n then we have
-(WW)))-(W')>--- O (T(W))..
Corollary 10. Let Assumption 3 hold and assumptions in Theorem 9 hold. We choose appropriate
m = 3,
(a) We can choose 11 = T - and T x to gel 1 Er- B(L(W.)] L(W*) O(n T
(b) If ((W)) 0, we can choose T x and 1 to get 1 -.D B[L(W)) = Onn

---

SGD achieves excess risk bounds of the same order to that of GD in Corollary 6 An advantage SGD over GD that it requires less computation. To illustrate this, let us consider the general case for example. In this case, GD requires T x n to achieve the error bound (n (,) ). Since GD requires (n)) gradient computations per iteration and therefore the total gradient computation complexity is O(n 1+ ). As a comparison, SGD requires O(n) gradient computations and therefore saves the computation by a factor of (n ( ). Note Corollary connsiders the risk for the last iterate, while Corollary T0 considers the average of risks for all iterates. The underlying reason is that GD consistently decreases the training errors along the optimization process, while SGD does not enjoy this property. Note that the overparameterization requirement becomes
Remark 5. By Corollary 10
m x no+1 and m x n² Part (a) and Part (b), respectively.
Main Idea of the Proof
5.1 Gradient Descent
In this subsection, we sketch our idea on the proof on gradient descent.
Generalization errors.
The starting point of our proof is the following bound given in Lemma A.4
W W 11 2 p1+
|W w W.
(1+ (1+17 1/D)
(I17((:::))3++1V( 2)1B
n²
Vm
To apply the above inequality, we need to give a lower bound of ml/W. w
The analysis
Vm
in [1 uses the crude bound ||W, w lle S l: - Wollp + W. w/ 11 Vtt which
does not use the fact that W and W 1+1 are produced by SGD on neighboring datasets. By the
generation W and (()) (-1, we show that [, w!" 2 = ( è /n) (Lemma B.1 This
explains why we get relaxed overparamettrization in the stability analysis compared to 51
Optimization errors. The starting point of our proof is the following bound given in Eq. (B.8)
E W",
W
E LS
[W)]
of
<
LL
W
)
nt
W
Wolki
7
Vm Σ
[[ or
w.ll)). (5.1)
The analysis in 55 controls
|| W
W follows
7
W Wf
W WI
Wol W.
W.B.
W
W 02
Woll + (115)
B/Il W111
As comparison, we use be bounded from above by
W.
Woll2 (V775)
Eq. [.I and show that 175)
can
m
E W
Woll
b nE mt ==
L(W" 72
L W.)
(IVE
IVEE[W:
W or
w.13)
ntt
==
||| W
Wo
< L(W
E W
+
max
V E W
w.lll))
Ty
2nj
aE((]
where we have used the overparameterization m 2 (nT)). then follows that
W'|
-w (1)) (E "3
E[JW", EL W wI)
or Woll))

---

Furthermore, we can apply stability analysis to relate (W,)(W.)) to E(L(W.)) w)], and get (Lemma)
E W.
W
E L
Ls(ww))
(w;)
W
W
which is sharper than the bound W
w O in
51
This explains why we get
relaxed overparameterization in the optimization error analysis as compared to [5T].
5.2 Stochastic Gradient Descent
Our starting point is to prove || | - Woll - O(viT)) for t E [T]. This was shown for GD
in [5I. However, the analysis there relies heavily the following inequality Ls (s(Wi+)) S
Ls (WW LW which does not hold for SGD. We use the induction strategy to show
IW,- Woll (VVi)) If I|W, Woll O(vi7"), Lemma A.1 implies Amin MoninV2 (V2((Wr;z)) Z voT If m Z (1)7)² we can use the update strategy of SGD and the induction assumption to show Vm
++ W Woll O(viT). The bound || - Woll O(viTT) is a crude estimate the norm of iterates. To get our results, we show the following sharper bound on the norm of iterates by considering bounds expectation (Lemma
11 + f2/n))
+ Vi/I+t/n Vn
W| - W 47
Wo
W NT
12 +
E Ls (W,) W)
n
j=0
(5.2)
To show this, use E.
W ++1
W 1 S B W, W
+ (W.)
(W"
(w.)] .)
E nV T/m
W
W (Eq. C.5 up to constant factor). We take a summation of
this inequality and use m Z
(1T)) to get
B| W
L
Ls W
max E W -W,12),
5El4
7
j=0
from which we get Eq.
5.2
The bound in Eq.
5.2
requires to estimate Σÿ= E|Ls W W)] Our
next step is then to control
Σ EE Ls W5] as follows (Lemma C.3
BLL((W)) ) 1
Wo - W W
77
6 Conclusion
In this paper, present stability and generalization analysis of both GD and SGD to train neural networks. Under a regularity assumption, we show both GD and SGD can achieve excess risk bounds of the order (n -))) ), which further improve to the order On -a under a low noise condition. As compared to the existing stability analysis [51], we achieve our bounds under relaxed overparameterizztion assumption and extend the existing analysis on GD to SGD. Our improvement is achieved by developing sharper bounds norm of the GD/SGD iterate sequences.
There remain several interesting questions for further discussion. The first question is whether the overparanterrzzation requirement Z (177)3 can be further improved, and whether the overparame- terization requirement can be independent T'. Second, our analysis applies to SNNs with a smooth activation function. It would be very interesting to extend activation function. A key challenge in this direction is to control the smallest eigenvalue of the associated Hessian matrix [5]]. Third, our bounds are stated in expectation. It would be useful to develop high-probability bounds to understand the robustness of the algorithm. Finally, our analysis requires early-stopping in low noise-setting. It would be very interesting develop risk bounds in a low-noise setting without early-stopping [54].
analysis to SNNs with the ReLU
Acknowledgement. The authors are grateful to the anonymous reviewers for their thoughtful comments and constructive suggestions. Yiming's 's work is supported by NSF grants (IS--1003500, IIS 21 10546 and 210-2110036).
10

---

References
[1] Z. Allen-Zhu, Y. Li, and Y. Liang. Learning and generalization in overparameteriiee neural networks, going beyond two layers. Advances in neural information processing systems, 32, 2019.
[2] Z. Allen-Zhu, Y. Li, and Z. Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pages 242-252. PMLR,
2019.
[3] Amir, T. Koren, and Livni. Sgd generalizes better than gd (and regularization doesn't help). In Conference on Learning Theory, pages 63-92. PMLR, 2021.
[4] S. Arora, R. Ge, B. Neyshabur, and Y. Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Learning, pages 254-263.
PMLR, 2018.
[5] S. Arora, S. Du, W. Hu, Z. Li, and R. Wang- Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332. PMLR, 2019.
[6] Y. Bai and J. D. Lee. Beyond linearization: On quadratic and higher-order approximation of wide neural networks. arXiv preprint arXiv:1910.01611 2019.
[7] F. Bao, G. Wu, C. Li, Zhu, and B. Zhang. Stability and generalization of bilevel programming in hyperparameter optimization. Advances in Neural Information Processing Systems, 34, 2021.
[8] L.. Bartlett, D. J. Foster, and M. Telgarsky. Spectrally
margin bounds for neural networks. In Advances in Neural Information Processing Systems, pages 6240-6249, 2017.
[9] P. L. Bartlett, A. Montanari, and A. Rakhlin. Deep learning: statistical viewpoint. Acta numerica, 30:87-201, 2021.
[10] R. Bassily, V. Feldman, C. Guzmán, and K. Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33, 2020.
[11] L. Bottou, F. E. Curtis, and Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-31. 2018.
[12] O. Bousquet and A. Elisseeff. Stability and generalization. Journal of Machine Learning Research, 29Mar):4995526 2002.
[13] O. Bousquet, Y. Klochkov, and N. Zhivotovskiy, Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pages 610-626, 2020.
[14] Y. Cao and Q Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in neural information processing systems, 32, 2019.
[15] Z. Charles and D. Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In International Conference on Machine Learning, pages 744-753, 2018.
[16] J. Chen, D. Zhou, Y. Tang, Z. Yang, Y. Cao, and Q Gu. Closing the generalization gap of adap- tive gradient methods in training deep neural networks. In 29th International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 3267-3275. International Joint Conferences on Artificial Intelligence, 2020.
[17] Y. Chen, C. Jin, and B. Yu. Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint arXiv: 100.0:880400111, 2018.
[18] F. Cucker and D.-X. Zhou. Learning Theory: Approximation Theory Viewpoint. Cambridge University Press, 2007.
[19] Z. Deng, H. He, and W. Su. Toward better generalization bounds with locally elastic stability. In International Conference on Machine Learning, pages 2590-2600. PMLR, 2021.
[20] S. S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient descent provably optimizes over- parameterized neural networks. In International Conference on Learning Representations, 2018.
[21] G. K. Dziugaite and D. M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703.1 1008, 2017.
[22] A. Flisseeff, T. Evgeniou, and M. Pontil. Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(Jan):55-79, 2005.

---

[23] F. Farnia and A. Ozdaglar. Train simultaneously, generalize better: Stability of gradient-based minimax learners. In International Conference on Machine Learning, pages 3174-3185. PMLR,
2021.
[24] V. Feldman and J. Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Conference on Learning Theory, pages 1270-1279,
2019.
[25] N. Golowich, A. Rakhlin, and O. Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pages 297-299. PMLR, 2018.
[26] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pages 1225-1234, 2016.
[27] T. Hu, W. Wang. C. Lin, and G. Cheng. Regularization matters: A nonparametric perspective on overparametrized neural network. In International Conference on Artificial Intelligence and Statistics, pages 829-837. PMLR, 2021.
[28] A. Jacot, Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[29] Z. Ji, J. Li, and M. Telgarsky. Early-stopped neural networks are consistent. Advances in Neural Information Processing Systems, 34, 2021.
[30] Y. Klochkov and N. Zhivotovskiy. Stability and deviation optimal risk bounds with convergence
rate o(1/n). /n). Advances in Neural Information Processing Systems, 34, 2021.
[31] T. Koren, R. Livni, Y. Mansour, and U. Sherman. Benign underfitting of stochastic gradient descent. arXiv preprint arXiv:2202. 13361, 2022.
[32] I. Kuzborskij and C. Lampert. Data-dependee stability of stochastic gradient descent. In International Conference on Machine Learning. pages 2820-2829, 2018.
[33] Y. LeCun, Y. Bengio, and G. Hinton. Deep learning. Nature, 521(7553):436 4444,44444464 2015.
[34] Lee, L.. Xiao, S. Schoenholz, Y. Bahri, R. Novak, Sohl-Dickstein, and J. Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Advances in neural information processing systems, 32, 2019.
[35] Y. Lei and Y. Ying. Fine- tne-ggrined analysis of stability and generalization for stochastic gradient descent. In International Conference Machine Learning, pages 5809-5819, 2020.
[36] Y. Lei and Y. Ying. Sharper generalization bounds for learning with gradient-dominat objective functions. In International Conference on Learning Representations, 2021.
[37] Y. Lei, Z. Yang, T. Yang, and Y. Ying. Stability and generalization of stochastic gradient methods for minimax problems. In International Conference on Machine Learning, pages 1175-6186, 2021.
[38] J. Li, X. Luo, and M. Qiao. On generalization error bounds of noisy gradient methods for non-convex learning. In International Conference on Learning Representations, 2020.
[39] M. Li, M. Soltanolkotabi, and S. Oymak. Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks. In International conference artificial intelligence and statistics. pages 4313-4324. PMLR, 2020.
[40] J. Lin, R. Camoriano, and L. Rosasco. Generalization properties and implicit regularization for multiple passes SGM. In International Conference on Machine Learning, pages 2340-2348, 2016.
[41] S.-B. Lin, Y. Wang, and D.-X. Zhou. Generalization performance of empirical risk minimization on over-parameterized deep relu nets. arXiv preprint arXiv:2111.14033 2021.
[42] B.B Lin, K. Wang, Y. Wang, and D.-X. Zhou. Universal consistency of deep convolutional neural networks. IEEE Transactions on Information Theory, 2022.
[43] T. Liu, G. Lugosi, G. Neu, and D. Tao. Algorithmic stability and hypothesis complexity. In International Conference on Machine Learning, pages 2159-2167, 2017.
[44] B. London, B. Huang, and L. Getoor. Stability and generalization in structured prediction. The Journal of Machine Learning Research, 17(1):78087785 78599 2016.
[45] A. Maurer. Algorithmic stability and meta-learning Journal of Machine Learning Research, 6 (Jun):967-994, 2005.
[46] S. Mukherjee, P. Niyogi. T. Poggio, and R. Rifkin. Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization. Advances in Computational Mathematics, 25(1):111-193, 2006.
12

---

[47] V. Nagarajan and J. Z. Kolter. Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems, 32, 2019.
[48] B. Neyshabur, Z. Li, S. Bhojanapalli, Y. LeCun, and N. Srebro. Towards understanding the role of over-paraametrization in generalization of neural networks. In International Conference Learning Representations (ICLR), 2019.
[49] K. E. Nikolakakis, F. Haddadpour, A. Karbasi, and D. S. Kalogerias. Beyond lipschitz: Sharp generalization and excess risk bounds for full-batch gd. arXiv preprint arXiv:2204.12440 2022. 2019. [51] D. Richards and I. Kuzborskij. Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel. Advances in Neural Information Processing Systems,
[50] F. Orabona. A modern introduction to online learning. arXiv preprint 19xXiv::92..13
34, 2021.
[52] D. Richards and M. Rabbat. Learning with gradient descent and weakly convex losses. In International Conference on Artificial Intelligence and Statistics, pages 1990-1998, PMLR, 2021.
[53] W. H. Rogers and T. J. Wagner. A finite sample distribution--ire free performance bound for local discrimination rules. The Annals of Statistics, pages 506-514, 1978.
[54] M. Schliserman and T. Koren. Stability implicit bias of gradient methods separable data and beyond. In Conference on Learning Theory, pages 3380-3394, 2022.
[55] M. Seleznova and G. Kutyniok. Analyzing finite neural networks: Can we trust neural tangent kernel theory? arXiv preprint arXiv:2012. 044777 2020.
[56] Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research, 11(0ct):263-2256 2010.
[57] N. Srebro, K. Sridharan, and A. Tewari. Smoothness. low noise and fast rates. In Advances in Neural Information Processing Systems, pages 2199 2207, 2010.
[58] B. Stankewitz, Mücke, and L.. Rosasco. From inexact optimization to learning via gradient concentration. Computational Optimization and Applications, pages 1-30, 2022.
[59] I. Steinwart and A. Christmann. Support Vector Machines. Springer Science & Business Media, 2008.
[60] T. Suzuki and S. Akiyama. Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methods. arXiv preprint arXiv:20/2.03224, 2020.
[61] Y. Xing, Q. Song, and G. Cheng. On the algorithmic stability of adversarial training. Advances in Neural Information Processing Systems, 34, 2021.
[62] Y. Yao, L. Rosasco, and A. Caponnetto. On early stopping in gradient descent learning.
Constructive Approximation, 26(2):289-315 2007.
[63] Y. Ying and M. Pontil. Online gradient descent learning algorithms. Foundations of Compula- tional Mathematics, 8(5):561-596 2008
[64] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017.
[65] J. Zhang, M. Hong, M. Wang, and S. Zhang. Generalization bounds for stochastic saddle point problems. In International Conference on Artificial Intelligence and Statistics, pages 568-576.
PMLR, 2021.
[66] D.-X. Zhou. Universality of deep convolutional neural networks. Applied and computational harmonic analysis, 48(2):787-794, 2020.
[67] T.-Y. Zhou and X. Huo. Learning ability of interpolating deep convolutional neural networks.
Available at SSRN 4/09419 19, 2022.
[68] Y. Zhou, Y. Liang, and H. Zhang. Understanding generalization error of sgd in nonconvex optimization. Machine Learning,
((11::34-37755 2022.
[69] D. Zou, Y. Cao, D. Zhou, and Q Gu. Stochastic gradient descent optimizes weraparameterize deep relu networks. arXiv preprint 10/i::/8//.0888. 2018
Checklist
1. For all authors...
13

---

(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you'l 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "rqkQrjcnZiW", "reviewer": "Reviewer_2XHq", "summary": "This paper calculates a bound on the generalization error of a committee machine (i.e., a two layer neural network with weights of the top layer fixed to all 1s). It shows O(1/sqrt(n)) generalization gap if the number of hidden neurons is m > (eta T)^3 where eta is the learning rate of gradient descent/stochastic gradient descent and T is the number of gradient updates. This improves a previous result (m > (eta T)^5) slightly. The analysis relies on using algorithmic stability and constructing a lower bound on the smallest eigenvalue of the Hessian.", "questions": "1. There is a typo on Line 120, the empirical risk should be divided by n.\n\n2. The relevance of the results rests crucially on alpha. Can you give an intuitive explanation of what the parameter is?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ The analysis is sound as far as I could check.\n\n+ The analysis of SGD follows along very similar lines of [46] and the analysis of GD, but I believe it is novel, in principle.\n\n- I believe this work makes very minor improvements, both technical and methodological ones, on top of existing work, in particular [46]. I will give an example below.\n\nThe authors note on Line 182 the bound in [46] is m > (eta T)^3; this is very close to the bound in this paper of m > (eta T)^3 n^{-2 alpha/(1+alpha)}. This comment also applies to the comment on Line 189 where the bound on the eigenvalue of the Hessian is improved from O(sqrt(eta T)) to O(n^{-1} eta T). These are minor technical improvements and one wonders whether we are learning anything new about the problem that gives a unique insight. The proof of Lemma 3, the comments on Lines 196-200 and Remark 3 suggest that W^*_{1/eta T} or W^* are close to the initialization W_0 and thereby close to W_t as well. I have similar reservations about Theorem 5.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "pa2aTKfkNEJ", "reviewer": "Reviewer_6YAP", "summary": "The paper improves algorithmic stability analysis of GD-trained shallow neural networks of [46]. In particular, [46] required overparameterization of order $\\text{width} \\geq (\\text{step-size} \\cdot \\text{GD-steps})^3$ for the stability/generalization bound, whereas in the current paper this is improves till $\\text{width} \\geq (\\text{step-size} \\cdot \\text{GD-steps})^2$ when the problem is 'easy'. Moreover [46] showed an excess risk bound which required overparameterization of order $\\text{width} \\geq (\\text{step-size} \\cdot \\text{GD-steps})^5$, whereas in the current paper this is improved till exponent of 3. In this paper (as in [46]) the theory works for an early stopped GD (i.e. $\\text{step-size} \\cdot \\text{GD-steps}$ is taken to be a sublinear function of the sample size), which makes sense since otherwise consistency is not achievable. The excess risk bound scales with the `niceness' exponent of the problem. The analysis is also extended to SGD.", "questions": "How large the width should be in terms of the sample size when $\\text{step-size} \\cdot \\text{GD-steps}$ is set w.r.t. sample size? Is overparameterization mild (i.e. subquadratic)?\nActually, Table 1 could also include the order of the width in terms of the sample size.", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* Improves overparameterization rates compared to [46] (see details below).\n* Excess risk analysis avoid oracle-type arguments of [46] and makes bound more specialized (see details below).\n* Extends analysis to SGD.\n\nWeaknesses:\n* Comparison to the literature is somewhat lacking, in particular in terms of rates (e.g. to [46] and/or to [1*]), or at least a discussion why it is challenging is missing.\n* Sometimes the narrative is unclear, bits of the proof ideas are introduced here and there. Perhaps it would be beneficial to have a separate proof idea section.\n\nRate improvements achieved in this paper are rather technical. The key observation is that the smallest eigenvalue of the Hessian matrix of the empirical risk between two parameters $\\mathbf{W}$ and $\\mathbf{\\tilde{W}}$ scales as $-\\frac{1}{\\sqrt{\\text{width}}} (\\|\\mathbf{W} - \\mathbf{\\tilde{W}}\\| + 1)$. When these parameters are taken to be iterates of GD with intact and perturbed training sample, [46] controlled $\\|\\mathbf{W} - \\mathbf{\\tilde{W}}\\|$ in a pessimistic way through descent-lemma type argument. The current paper delves into a more elaborate argument and shows that both iterates converge to the regularized solution + some offset which is expected to be much smaller than in the pessimistic case.\n\nThe second contribution of the paper is control of the excess risk which is based on the certain regularity of a problem. [46] showed an oracle-type bound where the excess risk scales with the $\\ell 2$-norm of a minimal-norm interpolating network (here norm is understood as relative to initialization, i.e. always involves $\\cdot -\\mathbf{W}_0$). In the current paper, instead, the control is done w.r.t. the minimizer of $\\ell 2$-penalized risk and then the paper assumes that the approximation error of the true risk behaves nicely, i.e. as $\\lambda^{\\alpha}$ where $\\lambda$ is a regularization parameter and where $\\alpha$ is a niceness exponent. This is a common technique in analysis of the ridge regression. Finally $\\alpha$ makes its way into the exponent of the excess risk rate (as in the ridge regression case).\nAt this point one would expect some comparison of rates: for instance [46] showed some rates where is on RKHS or GD in nonparametric setting [1*].\n\n[1*] Hu, T., Wang, W., Lin, C., & Cheng, G. (2021, March). Regularization matters: A nonparametric perspective on overparametrized neural network. In International Conference on Artificial Intelligence and Statistics (pp. 829-837). PMLR.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "nYV1gDB6ZRq", "reviewer": "Reviewer_Tj5f", "summary": "The paper studies the generalisation of shallow neural networks using algorithm stability. The work provides a tighter analysis of [1], obtaining a similar generalization for smaller width $ m \\sim O ((\\eta T) ^ {3}) $ in comparison to $ O ((\\eta T) ^ {5}) $ in [1]. The paper also extends the results for SGD with a similar over-parameterization requirement. ", "questions": "One potential concern is Assumption 3, which is crucial to control $R_{T}$. The justification for Assumption 3 is not very convincing as $ \\| W^* \\|  = O(1) $ is a strong requirement as the $ \\| W^{*} \\| $ is a $ d \\times m $-matrix. Can the authors provide more justification for this as this seems central to the analysis, e.g. Theorem 6?", "limitations": "The limitations are adequately addressed. ", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1) This work identifies crucial quantities in the analysis of analysis as [1] majorly, $ \\| W_ {t} - W_{1/\\eta T}^{*} \\| $ or $R_{T}$. Using these quantities, the paper produces a finer analysis reducing the overparameterisation required to obtain similar generalisation guarantees. \n\n2) Also extend the stability analyses to SGD. \n\nWeakness:\n1) The paper clearly extends the results of [1] and mostly follows a similar framework. Hence, it also suffers from the same limitations as the original paper where the number of parameters still depends on $T$ and early stopping is required even for the noiseless or low noise case. As these questions still remain, it is hard to evaluate the impact of reducing the scale of width from $O((\\eta T)^5)$ to $O((\\eta T)^3)$ . \n\n\n[1] Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel, NeurIPS 2021. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PBxpm46PYkm", "reviewer": "Reviewer_fbHj", "summary": "This paper focuses on deriving stability-based generalization bound for shallow neural networks. Specifically, the authors improve the previous bounds by relaxing the requirement for the width from (\\etaT)^5 to (\\eta T)^3, where \\eta denotes the step size and T is the training iterate. The key technical difference from the previous works is a more fine-grained estimation of the smallest eigenvalue of the Hessian matrix. The authors also apply their methods to the SGD regimes. \n\nI think this paper has the potential to be accepted. However, there are still some questions to be answered. \nMy major concern falls in comparing this paper's bound with the norm-based generalization bound (uniform convergence).\nIn Line 194-195, the authors show E\\|W_t\\| = O(1) in their analysis.\nHowever, this case might be solved by norm-based bound trivially. \nFor more details, see the question part. \n", "questions": "As said above, could the authors provide a specific case where we can apply the proposed bound when $|W_t|$ is not bounded?\nThis may also require another example for Assumption~3.", "limitations": "No potential negative societal impact.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Contributions.\n1. The authors improve the previous stability-based bound on the shallow neural networks. Specifically, the authors improve the requirements for the width from (\\etaT)^5 to (\\eta T)^3.\n2. The authors also extend their analysis to SGD, which is more challenging. \n3. To reach the bound, the authors provide a more fine-grained analysis of the smallest eigenvalue of the Hessian matrix.\n4. This paper is clearly written, and the authors provide many insights. \n\nFlaws:\nAs said before, in Line194-195, the authors show that if etaT = O(\\sqrt n) and |W^* - W_0| =O(1), we can show that |W_t – W*| = O(1).\nThe first choice of etaT is used later, and the second condition of |W^* - W_0| is just the special case proposed in Assumption~3. \nTherefore, it seems that $|W_t| = O(1)$ easily holds in practice. \nHowever, with the bounded norm, one can apply norm-based bounds in uniform convergence without applying stability-based bound.\nTherefore, could the authors provide a specific case where $|W_t|$ is not bounded? \n\nNot important:\nThe authors need to distinguish between the subscript W_T and W_{1/\\eta T}.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8Zxp6IzO-T_", "reviewer": "Reviewer_nG3J", "summary": "The authors study excess risk bounds for one hidden-layer neural networks where the last layer is fixed to the initialization and only the first layer is trained by gradient descent. The resulting bounds significantly improve the overparametrization requirements of previous work while preserving the same rates. They achieve this by splitting the excess risk into a generalization part, the optimization part and a left-over part, and controlling each with separate techniques. More precisely, the generalization part is analysed through the notion of on-average stability, and it is here where a more careful control over the smallest Hessian eigenvalue leads to improvements over previous works. The atuhors further show that the optimization can be similarly controlled with weaker overparametrization than previously, showing that under some assumptions they can recover the same results as [1] under smaller widths. The final part is largely controlled by a regularity assumption not made in previous works  Moreover, they extend their results also to the setting of stochastic gradient descent, something which was not possible in previous work. \n\n[1] *Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel, D. Richards and I. Kuzborskij*", "questions": "The NTK is mainly associated with large width but it also strongly relies on small learning rates. How do the learning rates in this work (\\eta T \\approx n in the noiseless case) compare to the minimal learning rates needed to be in the NTK regime (provided we have a wide enough network), i.e. Theorem 2.1 in [1]? Are we also operating outside of the NTK regime in terms of learning rate size? \n\n[1] *Wide Networks of Any Depth Evolve as Linear Models Under Gradient Descent, Jaehoon Lee et al.*", "limitations": "The authors discuss limitations, some more insight into Assumption 3 would be helpful to the reader however.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n1. In my opinion the paper pushes several directions that are worth pursuing to improve over current state-of-the-art generalization bounds. First, this work aims to move away from the so-called NTK regime by not relying on the heavy overparametrization usually required in these works, similarly to [1]. This is important since in practice, neural networks have been observed to outperform their kernel counterparts in realistic settings. Second, analyzing stability bounds moves away from the paradigm of uniform convergence and the implied capacity bounds relying on notions such as Rademacher complexities and VC-dimensions. Not relying on uniform convergence may be crucial to achieve non-trivial progress in the field of generalization, as the work [2] has shown. I think it is worth to add that citation to the related works since uniform convergence-based bounds are already discussed.\n2. The technical contributions seem highly non-trivial improvements over previous works and the width requirement is strongly reduced without incurring too much loss in terms of the achieved rates, both in noisy and noiseless settings. Moreover, the extension to SGD also seems technically very involved and is something that could not be achieved in [1].   \n\n**Weaknesses:**\n1. The role of assumption 3 is not clear to me on several levels. What does it encapsulate on an intuitive level? Mathematically, it is the difference between the optimal regularized the optimal non-regularised generalization loss. The assumption imposes a polynomial upper bound in the regularization parameter lambda. The authors show that this assumption is satisfied if the optimal weights W* have constant (i.e. not growing ) norm, something also not completely obvious. For instance if I think of some image classification task such as MNIST, is assumption 3 met? If yes, with what alpha? This seems tricky to check unfortunately since we need to know the optimal model W^*.  On the other hand, it’s also not obvious how the analysis in this paper profits from assumption 3 which is not present in previous works. Theorem 2 and Theorem 5 don’t seem to explictily need assumption 3 but I guess the optimization part analyzed in this paper is not the same as in [1] and assumption 3 hence implicitly shows up here too? I would find it very helpful if the authors could clarify the role and intuiton of assumption 3 and whether we can gain any numerical insights into it.\n2. While the paper is well-written, I think its readibility would greatly benefit from reducing the number of Theorems, Lemmas and Corollaries in the main text (there are 14!). Restricting this to the main results (Generalization gap, Optimization error, excess bound, novel key lemma etc.) would already make the read more enjoyable, without losing too much of the content and story-line. While I appreciate that the main text is extremely precise about all constants, I also think that explicitly writing out the exact width requirements as well as other bounds, hinders readibility as well and makes statements rather cluttered. Listing the main dependencies in big-O fashion in the main text would make it simpler to get an understanding of the terms. The exact forms of the terms could for instance be listed in the appendix.\n\n[1] *Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel, D. Richards and I. Kuzborskij*\n\n[2] *Uniform Convergence May be Unable to Explan Generalization in Deep Learning, Vaishnavh Nagarajan, Zico Kolter*", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept