Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernel
Authors: Dominic Richards
Ilja Kuzborskij
Venue: NeurIPS 2021 Poster (2021)
Keywords: Gradient Descent
Neural Networks
Stability
Generalisation
Implicit Regularisation
Neural Tangent Kernel

Abstract: We revisit on-average algorithmic stability of Gradient Descent (GD) for training  overparameterised  shallow  neural  networks  and prove  new  generalisation and  excess  risk  bounds  without  the  Neural  Tangent  Kernel  (NTK)  or  Polyak-Łojasiewicz (PL) assumptions. In particular, we show oracle type bounds which reveal that the generalisation and excess risk of GD is controlled by an interpolating network with the shortest GD path from initialisation (in a sense, an interpolating network with the smallest relative norm).  While this was known for kernelised interpolants, our proof applies directly to networks trained by GD without intermediate kernelisation. At the same time, by relaxing oracle inequalities developed here we recover existing NTK-based risk bounds in a straightforward way, which demonstrates that our analysis is tighter. Finally, unlike most of the NTK-based analyses we focus on regression with label noise and show that GD with early stopping is consistent

Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernel
Dominic Richards Department of Statistics University of Oxford 24-29 Giles', Oxford, OX1 3LB Dominic, Ri Richarra944@mmill.ccommmm
Ilja Kuzborskij DeepMind London
i1 11jaaOddeepmind.com com
Abstract
We revisit on-average algorithmic stability of Gradient Descent (GD) for train- ing overparameterised shallow neural networks and prove new generalisation and excess risk bounds without the Neural Tangent Kernel (NTK) or Polyak- Łojasiewicz. (PI.) assumptions. particular, we show oracle type bounds which reveal that the generalisation and excess risk of GD is controlled by interpolating network with the shortest GD path from initialisation (in sense, an interpolating network with the smallest relative norm). While this known for kernelised interpolants, our proof applies directly to networks trained by GD without inter- mediate kernelisation. At the same time, by relaxing oracle inequalities developed here we recover existing --Keba risk bounds in a straightforward way, which demonstrates that our analysis is tighter. Finally, unlike most of the NTK-based analyses we focus on regression with label noise and show that GD with early stopping is consistent.
1 Introduction
In a canonical statistical learning problem the learner is given a tuple independently sampled training examples S = (Zi...., 2n). where each example label yi jointly distributed according to some unknown probability measure P. In the following we assume that inputs belong Based on training examples the goal the learner is to select parameters W from some parameter space W in order to minimise the statistical risk
(x,, y1) consists of an input x; and
Euclidean ball B (Cz) of radius C. and labels belong to [-Cy- Cy]-
L(W) def / (fw(x) y)² dp
where fw is a predictor parameterised by W. The best possible predictor in this setting is the regression function f*, which is defined f*(x) f y while the minimum possible risk equal the noise-rate of the problem, which is given by 0² Jz (f y)² dP.
In this paper we will focus on a shallow neural network predictor that takes the form
(x(x)
d ((W
(x Rd W Rdxm)
defined with respect to some activation function and tunable (possibly randomised) hidden layer W. In particular, we will consider fw,, where the
oinintooiofuuncctonn ò : + R, fixed output layer u E [+//m))"
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

hidden layer is obtained by minimising an empirical proxy of L called the empirical risk Cs( Cs( def (2n) Σi= (fw(x)) -y:)² by running Gradient Descent (GD) procedure: For t E [T) steps with initial parameters Wo and a step size > 0, we have iterates W++1 = W. (W,) where (L, is the first order derivative of L.(W).
Understanding the behaviour of the statistical risk for neural networks has been long-standing topic of interest in the statistical learning theory [Anthony and Bartlett, 1999]. The standard approach to this problem is based on uniform bounds on the generalisation gap
Gen (WT) def ((Wr) ((Wr))Cs(Wrr)
which, given a parameter space W, involves controlling the gap for the worst possible choice of W E W under some unknown data distribution. The theory then typically leads to the capacity-based (Rademacher complexity, VC-dimension, metric-entropy based) bounds which hold with high probability (w.h.p.) over S [Bartlett and Mendelson, 2002, Golowich et al., 2018, Neyshabur et al., 2018]:"
capacity(W)
sup 1c Gen (W) S WEW
(1)
Thus, if one could simultaneously control the empirical risk and the capacity of the class of neural networks, one could control the statistical risk. Unfortunately, controlling the empirical risk Lr turns out to be a challenging part here since it is non-convex, and thus, it is not clear whether GD can minimise it up to a desired precision.
This issue has attracted considerable attention in recent years with numerous works [Du et al., 2018, Lee et al., 2019, Allen-Zhu et al., 2019, Oymak and Soltanolkotabi, 2020] demonstrating that overparameterised shallow networks (in a sense m 2 poly(n)) trained on subgaussian inputs converge to global minima exponentially fast, namely, (W() Z (1 - 17- "/44,)".' Loosely speaking, these proofs are based on the idea that sufficiently overparameterised network trained by GD initialised at Wo with Gaussian entries, predicts closely to a solution of a Kernelised Least-Squares (KIS) formulation minimised by GD, where the kernel function called the Neural Tangent Kernel (NTK) [Jacot et al., 2018] is implicitly given by the activation function. This connection explains the observed exponential rate in case of shallow neural networks: For the NTK kernel matrix K the convergence rate of GD is (1 - 77mmin (K))², where Amin (K) is its smallest eigenvalue, and as turns out, for subgaussian inputs Amii (K) 2 d/n [Bartlett et al., 2021]. Naturally, the convergence was exploited to state bounds on the statistical risk: Arora et al. [2019] showed that for noise-free
regression (o² = -)) when T 2 1/ 1/(1/>min (K)).
/ y. (nK) 'y)
((WT)
(2)
Clearly, the bound is non-vacuous whenever (y.K-'y 'y) 2 n² for some E [0. 1), and Arora al. [2019] present several examples of smooth target functions which satisfy this. More generally, for fr which belongs to the Reproducing kernel Hilbert space (RKHS) induced by NTK one has (y, K--y) S. 1| [Schölkopf and Smola, 2002]. The norm-based control of the risk standard in the literature on kernels, and thus, one might wonder to which extent neural networks are kernel methods in disguise? At the same time, some experimental and theoretical evidence (Bai and Lee, 2019, Seleznova and Kutyniok, 2020, Suzuki and Akiyama, 2021] suggest that connection to kernels might be good only at explaining the behaviour of very wide networks, much more overparameterised than those used in practice. Therefore, interesting possibility is to develop alternative ways to analyse generalisation neural networks: Is there a more straightforward kernel- free optimisation-ble based perspective?
In this paper we take a step in this direction and explore a kernel-free approach, which at the same time avoids worst-case type uniform bounds such as Eq. (1). In particular, we focus on the notion of the algorithmic stability: If an algorithm is insensitive to replacement (or removal) of an observation
'Throughout this paper, we use f S to say that there exists a universal constant c >> 0 and some k E N such that f E eg log" (g) holds uniformly over all arguments.
"Which is tightest known bound, Oymak and Soltanolkotabi [2020] prove looser bound without distribu- tional assumption on the inputs.

---

in training tuple, then it must have small generalisation gap. Thus, a natural question is whether GD is sufficiently stable when training overparameterised neural networks.
The stability of GD (and its stochastic counterpart) when minimising convex and non-convex smooth objective functions first explored by Hardt et al. [2016]. Specifically, for time-dependent choice of step size T) = 1/t and a problem-depender constant a E (0, 1) they show that
E Gen (Wr) Wo, u] S In(T))"
Unfortunately, when combined with the NTK-based convergence rate of the empirical risk we have a vacuous bound since Ls( (s(W)) S 1. This is because the stability is enforced through quickly decaying step size rather than by exploiting a finer structure of the loss, and turns out to be insufficient to guarantee the convergence of the empirical risk. That said, several works Charles and Papailiopoulos [2018], 8], Lei and Ying [2021] have proved stability bounds exploiting an additional structure in mildly non-convex losses. Specifically, they studied the stability of GD minimising praddientddminaaie empirical risk, meaning that for all W in some neighbourhood W and problem-dependent quantity μs, it is assumed that Ls (W) minw Ls (W") S [ (W)ll (2p). Having iterates of GD within W and assuming that the gradient is p-l.ipccht this allows to show
P 1 p
[ Gen (Wr) Wo. ul
E
<
n
As it turns out, the condition is satisfied for the iterates of GD training overparameterrssed networks (Du et al., 2018] with high probability over Wo- The key quantity that controls the bound is p/u S 1/ 1/Amin (K) which be interpreted as condition number of the NTK matrix. However, it is known that for subgaussian inputs the condition number behaves as n/d which renders the bound vacuous [Bartlett al., 2021].
2 Our Contributions
In this paper we revisit algorithmic stability of GD for training overparameterised shallow neural networks, and prove new risk bounds without the Neural Tangent Kernel (NTK) or Polyak- Eojasiewicz (PL) machinery. In particular, we first show a bound on the generalisation gap and then specialise to state risk bounds for regression with and without label noise. In the case of learning with noise we demonstrate that GD with form of early stopping is consistent, meaning that the risk asymptotically converges to the noise rate o².
Our analysis brings out key quantity, which controls all our bounds, the Regularised Empirical Risk Minimisation (R-ERM) Oracle defined as
oracle def S
min WER
Cs(W)+
W
Woll T/
as 7f 00, 00,
(3)
which means that Agracl essentially an empirical risk of solution closest to initialisation (an interpolant when for m large enough). We first consider bound on the generalisation gap.
2.1 Generalisation Gap
For simplicity of presentation the following we assume that the activation function d, first and second derivatives are bounded. Assuming parameterisation 2 (177)5 we show (Corollary 1) that the expected generalisation gap is bounded as
Wo. u] C 7T (1+ '/
E
Gen (Wr)
I+
E A oracle
Wo u]
(4)
where C' is a constant independent from n, T.
'If v/+ 1 we have Ls (Wr) S exp(μ Ej 7F thus, if o R 1 we then require T ~ cm for Ls(Wr) S c. Plugging this into the Generalisation Error bound we get that log(?") nn''")"= -a = n log(1/c) which is vacuous grows.
3

---

Dependence of m on the total number of steps T might appear strange at first, however things clear once we pay attention to the scaling of the bound. Setting the step size 1j to be constant, n²" and overparameterisation m Z na for some free parameter
(0, 1] we have
E G (WT) Wo. u = = [ [ W - Wolls
W Wo. ul)
T1 - 00,
where W is chosen as parameters of a minimal-norm interpolating network, in a sense W E argminweRexm { [|W- Woll? Ls(W) = 03. Thus, Eq. (4) suggests, the generalisation gap controlled by a minimal relative norm of an interpolating network. comparison, previous work in the NTK setting obtained results of a similar type where in place of W one has an interpolating minimal-norm solution an NTK least-squares problem. Specifically, in Eq. (2) the generalisation gap is controlled by (y, (n ly), which is a squared norm of such solution.
The generalisation gap of course only tells partial story, since the behaviour of the empirical risk unknown. Next, we take care of this and present bounds excess risk bounds.
2.2 Risk Bound without Label Noise
We first present bound on the statistical risk which does not use the usual NTK arguments to control the empirical risk. For now assume that o² 0 meaning that there is no label noise and randomness is only in the inputs.
NTK-free Risk Bound. In Corollary 2 we show that the risk is bounded as
E (C(T)) Wo, u| - (I+C- T/T
n/T
[
E
A oracle
W u
(5)
Note that this bound looks very similar compared the bound on generalisation gap. The difference lies in a "1+" term which accounts for the fact that L(Wr) I graacl as we show in Lemma 2.
As before we let the step size be constant, set T' n², and let overparameterriatioo be m 2 n 5a for some a E (0, 1]. Then our risk bound implies that
E (C((T)) Wo. u] O
( 1 E - a
Wo.u] ul) as 70000
which comes as a simple consequence of bounding Ag while choosing W to be parameters of minimal relative norm interpolating network as before. Recall that yı (x:):: The bound suggests that target functions /* are only learnable if na B(JWW Woll Wo. u] 0 as n co for fixed a and input distribution. A natural question is whether a class of such functions is non-empty. Indeed, the NTTK theory suggests that it is not and in the following will recover NTK-hased results by relaxing our oracle inequality.
Similarly as in Section 2.1 choose T' = n and so require 2 Sa which trades off overparameterisation and convergence rate through the choice of a E (0, 1]. To the best of our knowledge this is the first result of this type, where can achieve smaller overparamettrrisation compared to the NTK literature at the expense of slower convergence rate of the risk. Finally, unlike the NTK setting we do not require randomisation of the initialisation and the risk bound obtain holds for any Wo. 4
Comparison to NTK-based Risk Bound. Our generalisation bound can be naturally relaxed to obtain NTK-based empirical risk convergence rates. In this case we observe that our analysis is general enough recover results of Arora et al. [2019] (up difference that our bounds hold in expectation rather than in high probability).
By looking at Eq. (5), task is in controlling Agracle by its definition in Eq. (3) that it can be bounded by the regularised empirical risk of any model, and we choose a Moore- Penrose pseudo-inverse solution to the least-squares problem supplied with the NTK feature map x + (Vw/w (x)) (Wo). Here, entries of Wo are drawn from (0, v for some appropriately
'In the NTK literature randomisation of Wo is required to guarantee that Amin (K) [Du al., 2018).

---

chosen 1/ Vigit and entries of the outer layer u are distributed according to the uniform distribution over /m independently from each other and the data. It is hard to see that aforementioned pseudo-inverse solution WPine will have zero empirical risk, and so we are left with controlling [WPlav Woll? as can be seen from the definition of A Note that it straightforward to do since Wpine has an analytic form. Theorem 2 we carry out these steps and show that with high probability over initialisation (Wo.u) u).
A oracle = Ör
(x,()))))))) (
as
00,
which combined with Eq. (5) recovers the result of Arora et al. [2019]. Note that we had to relax the oracle inequality, which suggests that the risk bound give here is tighter compared to the NTK- based bound. Similarly, Arora et al. [2019] demonstrated that |Wr holds w.h.p. over initialisation and ReLU activation function, however their proof requires a much more involved "coupling" argument where iterates (Wo) are shown to be close to the GD iterates minimising a KLS problem with NTK matrix.
Woll Woll
Op (<y, (nK)-ly)
2.3 Risk Bound with Label Noise and Consistency
So far we considered regression with random inputs, but without label noise. In this section use our bounds to show that GD with early stopping is consistent in the regression with label noise. Here labels are generated y/ (x,) + E; where zero-mean random variables (s,) are i.i.d., almost surely bounded, and E(e?]= = o2.
For now will the same settings of parameters as in Section 2.2: Recall that v is constant, T= n²" m Z na for a free parameter a E (0, 1]. In addition assume a well-specified scenario which means that is large enough such that for some subset of parameters W achieve L(W*) = o² for some parameters W Employing our risk bound of Eq. (5), we relax R-ERM oracle as
B oracle
Wo u| S 0² + n /
W - Woll where W argminweRex. L(W).
Then we immediately have an a-dependent risk bound
E [C(WT) | Wo. u| - (1+ (1+ ni-a )
(02+0
II Woll n
as 1 00 (6)
is important to note that for any tuning a E (0, 1). as long as W* is constant in n (which is the case in the parametric setting), have E [[C(W)) Wo. consistency. Adaptivity to the noise achieved here is due to early stopping: Indeed, recall that we take T = n² steps and having smaller a mitigates the effect of the noise can be seen from Eq. (6). This should come as no surprise as early stopping is well-known to have a regularising effect in GD methods [Yao et al., 2007]. The current literature the NTK deals with this through kernelisation perspective by introducing an explicit L2 regularisation [Hu et al., 2021] I. while risk bound of [Arora al., 2019] designed for noise-free setting would be vacuous in this case.
o² + co, and
achieve
2.4 Future Directions and Limitations
We presented generalisation and risk bounds for shallow nets controlled by the Regularised Empirical Risk Minimisation oracle A graace, By straightforward relaxation of graicl, we showed that the risk can be controlled by the minimal (relative) norm of an interpolating network which is tighter than the NTK-based bounds. There are several interesting venues which can be explored based our results. For example, by assuming a specific form of a target function f (e.g.. a "teacher" network), one possibility is to characterise the minimal norm. This would allow understand better which such target function are learnable by GD.
One limitation of our analysis is smoothness of the activation function and its boundedness. While boundedness can be easily dealt with by localising the smoothness analysis (using a Taylor approxi- mation around each GD iterate) and randomising (Wo, u), extending our analysis non-smooth activations (such as ReLU ((x) = max(z: (z, 0)) appears to be non-trivial because our stability analysis
We assume boundedness of labels throughout our analysis to ensure that Ls (WW) is bounded almost surely for simplicity. This can be relaxed by introducing randomised initialisation, e.g. in [Du et al., 2018].
5

---

crucially relies on the control of the smallest eigenvalue of the Hessian. Another peculiarity of our analysis is time-dependent parameterisation requirement m 2 (n22)² Making parameterisation n-dependent introduces implicit early-stopping condition, which helped us to deal with label noise. On the other hand, such requirement might be limiting when dealing with noiseless interpolating learning where one could require to have TyT - oo while keeping n. finite.
Notation
In the following denote f(w, (x, y)) (xw(()-- -y) Operator norm is denoted as I1--lopp while L2 norm is denoted by -|- ll2 or || ||.. We use notation (a V b) def max fa, b) and (a A b) def min {a, b}
throughout the paper. Let (W()) ) be the iterates of GD obtained from the data set with a resampled
data point:
5(i) def (21...., 2-11 24 24 2n)
where žn is independent copy of ze. Moreover, denote remove-one version of S by
s def (21, 24-1 23+1.-.. 2n.
Main Result and Proof Sketch
This section presents both the main results well as a proof sketch. Precisely, Section 3.1 presents the main result and Section 3.2 the proof sketch.
3.1 Main Results
We formally make the following assumption regarding the regularity of the activation function. Assumption (Activation). The activation 6(u) continuous and twice differentiable with constant Bs, By, By 2 0 bounding lo(u) < B (d' < By and (Ø"(u) S Bor for any u E R.
This is satisfied for sigmoid well as hyperbolic tangent activations.
Assumption 2 (Inputs, labels, and the loss function). For constants Czs C., Co > 0, inputs belong to B (C2), labels belong to [-C,, Cy). and loss is uniformly bounded by Co almost surely.
A consequence of the above is an essentially constant smoothness of the loss and the fact that the Hessian scales with 1/ym (see Appendix for the proof). These facts will play a key role in our stability analysis.
Lemma (Smoothness and curvature). Fix W, W E dx Consider Assumption 1, Assumption and assume that Ls( (W+ & CO. Then, for any S.
BByC Vm
Amnox 2 Ls (W) S p where cº By. + B BB
min Amin L2Ls + a W W))) Boy (Bo Co) (
(1V - -[]])
Vm
Given these assumptions we are ready to present a bound on the Generalisation Error of the gradient descent iterates.
Theorem (Generalisation Error).
Consider Assumptions and 2. Fixt > 0. Ifn $ 1/(2p) and
m 2 144(n))
By,
(4Bx CZVTl v2)²
(7)
then
E Gen (We+1) Wo <b
?
n2t me
Σ
E
[C Wo.u]
3=0
where b 1 C2 B2 C2 Bz.)
We use notation (a 6) def max {a, b) and (a Ab) def min fa, b} throughout the paper.

---

Proof. For full proof see Appendix C with sketch proof in Section 3.2.
Theorem then provides a formal upper bound on the Generalisation Gap of a shallow neural network trained with GD. Specifically, provided the network is sufficiently wide the generalisation gap can be controlled through both: the gradient descent trajectory evaluated at the Empirical Risk Wo. ul, as well as step size and number of iterations in the multiplicative factor. Similar bounds for the test performance of gradient descent have been given by Lei and Ying [2020], although in our case the risk is non-convex, and thus, more delicate bound on the Optimisation Gap is required. This is summarised within the lemma, which is presented in "oracle" inequality manner.
Σ El
Lemma (Optimisation Error). Consider Assumptions I and 2. Fix t 0. If S 1/(2p), then
Σ
Cs(WW)
min WER-Xm
{<s(W)
||
Woll nt
Woll } ] bCo
(nt) vm
m
1=0
where b CzBa" C
Proof. Full proof is given in Appendix with sketch proof in Section 3.2.
By combining Theorem and Lemma 2 we get the following where Agracl is defined in Eq. (3):
Corollary 1. Assume the same in Theorem and Lemma' 2. Then, oracle Wo,
E (eC)e Wo, u] SC. T/T (1 (1+ 1/"" E Agaaclo
where Agracle is defined in Eg. (3) and C is a constant independent from n, T,
The above combined with Lemma 2, and the fact that Ls(Wrr) m Ls (W.) gives us: Corollary 2. Assume the same as Theorem and Lemma 2. Then,
E ((((T) Wo. S C+C. T/ (1 1+ n )) n
1/T
E Arecle Wo. u
Proof.
The proof is given in Appendix E.
Finally, Agracle is controlled by the norm of the NTK solution, which establishes connection the WTK-based risk bounds:
Theorem (Connection between A oracle and NTK). Consider Assumption I and that TTT n. Moreover, assume that entries of Wo are i..dd. that (m)) 2 1/n, and assume that u ~ unif ((+1/(/ //m))//)) independently from all sources of randomness. Then, with probability least 1 for 10, over (Wo, u),
gracle Öp (x,))))))))) as n-> 00.
AS
Proof. The proof is given in Appendix D.
3.2 Proof Sketch of Theorem and Lemma
Throughout this sketch let expectation be understood E[-] El- Wo, u]. For brevity will also vectorise parameter matrices, so that W E Rm and thus || ||2 || ||F.
Let us begin with the bound on the generalisation gap, for which we use the notion of algorithmic stability [Bousquet and Elisseeff, 2002]. With ( denoting a GD iterate with the dataset with the resampled data point (K)), the Generalisation Gap can be rewritten Chalev-Shwarts and Ben-David, 2014, Chap. 13]
Gen = E[((W,) Ls (Wr) = Σ Ble(wr,)) e e(W 2,)

---

The equality suggests that if trained parameters do not vary much when a data point is resampled, that is WT W then the Generalisation Gap will be small. Indeed, prior work [Hardt al., 2016, Kuzborskij and Lampert, 2018] has been dedicated to proving uniform bounds on L2 norm max WT W
2|2- In our case, we consider the more refined squared L2 expected stability and consider a bound for smooth losses similar to that of Lei and Ying [2020]:
Lemma 3. Consider Assumptions and Then,
R WT
n2
Gen (VL(L((WT)
ΣE
E
W
12
E
WT
w 1
Proof. The proof is given in Appendix C.I.
To this end, we bound Wr w recursively by using the definition of the gradient iterates and applying Young's inequality (a b)² [1+ }]a² + t)6? to get that for any i [n]]
We+1 wffl1
(8)
= -| - W! - (VLsss - VL (w
I|W - w(()) - VVLsv (W,) VCSu (W, (0) + (V
$ (1 + W: w! 1 VLs (W)) s (w( 11
Expansiveness of the Gradient Update
+ 2 +) (IVE(W,, =012 (V 12) n
The analysis of the expansiveness of the gradient update then completes the recursive relation- ship [Hardt et al., 2016, Kuzborskij and Lampert, 2018, Lei and Ying, 2020, Richards and Rab- bat, 2021]. Clearly, a trivial handling of the term (using smoothness) would yield a bound (1 + || W. w( 12 which leads to an exponential blow-up when unrolling the recursion. So, we must ensure that the expansivity coefficient is no greater than one. While the classic analysis of Hardt et al. [2016] controls this by having a polynomially decaying learning rate schedule, here we leverage on observation of Richards and Rabbat [2021] that the negative Figenvalues of the loss's
Hessian V ()) E pdmxddm can control the expansiveness. This boils down to Lemma 1:
Amin (L/
( + a(W, w( >
1 ||, m
T
m
where |W w(( 12 S vIl comes from smoothness and standard analysis of GD (see Lemma 6). Note that the eigenvalue scales 1/ym because Hessian has block-diagonal structure.
Controlling expansiveness of GD updates. Abbreviate A = VL (W,) VL (W( and 2 So V2 L2 (w.") + a (.- (( ))d))d da. Now we "open" the squared norm
W w a 2 W. - 77 | - 2n W. WW:
and use Taylor's theorem for gradients to have
2 | 2n W. w! ( A
A, (T222 2nT1 (W, -w!"))
W. w V² (n - 21) (W. w(!))
V2
Tt
+
rf m
|W, w
where we noted that (n/V2 21) has only negative eigenvalues due to assumption 7) S 1/(2p).
8

---

By rearranging this inequality one can verify that the gradient operator is approximately co- coercive [Hardt al.. 2016]. This result, crucial to our proof, is supported by some empirical evidence: In Fig. we show a synthetic experiment where we train shallow neural network with sigmoid activation. Our handling of expansiveness eventually gives
(
Iw w m x
nl m
Iw. W
my
Plugging this back into Eq. (8)-(9) we unroll the recursion:
[W w 1
(1+7)
1+ 1) 1V
Ttt "V m
(IVE(W 22) (r(W)..))13
The above suggest that prevent exponential blow-up (and ensure that the expansiveness remains under control), it's enough to have vy < 1/t, which is assumption of the theorem, enforcing relationship between yyt and m.
On-average stability bound. Now are ready to go back to Lemma 3 and complete the proof of the generalisation bound. Since we have squared loss we have || VV(WW j. 2, 2,31 2 ((W 2i), and thus, when summing over i [m]] we recover the Empirical risk 1,j E [ < (s(
Finally, noting that B[{(W,; =:]] E[((W)) Ei]] expected squared L2 stability
we then arrive at the following bound on the
E W
w (
Note that the Generalisation Gap is directly controlled by the Optimisation Performance along the path of the iterates, matching the shape of bounds by Lei and Ying [2020]. Using smoothness of the loss well as that Ls (WT) I + Σj- (s(W), the risk is bounded when m 2 (17t) as
E(C(Wr)] (1+ TTT (1 ""
))
1 T
Σ ==
T
E[Cs(W,))-
Optimisation error. We must now bound the Optimisation Error averaged across the iterates. Following standard optimisation arguments for gradient descent on smooth objective then get
Ls Ls( & Ls (W.) - " (V
At this point convexity would usually be applied to upper bound Cs(W)) S Cs(W) (V,) w W.) where W is minimiser of L.(.). The analysis differs from this approach in two respects. Firstly, we do not consider minimiser of Cs(-) but general point W. which is then optimised over at the end. Secondly, the objective is not convex, and therefore, we leverage that the Hessian negative Eigenvalues are the order of Vm
to arrive at the upper bound (Lemma I):
Ls( Ls (W) (VLs W W
W
W
m
Convex Component
Negative Hessian Eigenvalues
After this point, the standard optimisation analysis for gradient descent be performed i.e. -(VLs(W.)) W W,) - 3 (w..) I (I|W-Wo
- w - w Wz+1ll)), which then
yields to a telescoping sum over 0, 1. 1. This leads the upper bound for W Rxxd
M
ElCs( (w(
W W
1
1
1
W
W
T
T/
Vm
T
where we plug this into the generalisation bound and take minimum over W E pmd

---

16000
LADE AL 2.044)
22*
30'4
16
3309
40:00
8000 2.000 2000 4.00
1003
Figure 1: The gradient operator of an overparameterised shallow neural network is almost-monotone: Here, inputs are uniformly distributed on a 10-sphere and labels are generated by x + 1+e( where W* is once sampled from (O, at the beginning of the training. The initialisation W, is sampled from (0, 1o)) and each experiment is performed 10 times (which is reflected by standard deviation). The shallow network is then trained by GD with 1) 1, T 10t, and sigmoid activation.
e ( xx)
4 Additional Related Literature
Stability of Gradient Descent. Algorithmic stability [Bousquet and Elisseeff, 2002] has been used to investigate the generalisation performance of GD in a number of works [Hardt et al., 2016, Kuzborskij and Lampert, 2018, Chen al., 2018, Lei and Ying, 2020, Richards and Rabbat, 2021]. While near optimal bounds are achieved for convex losses, the non-convex case aligning with this work is more challenging. Within [Hardt et al., 2016, Kuzborskij and Lampert, 2018] in particular a restrictive 1/1 step size is required if t iterations of gradient descent are performed. This was partially alleviated within [Richards and Rabbat, 2021] which demonstrated that the magnitude of Hessian's 's negative eigenvalues can be leveraged to allow for much larger step sizes to be taken. In this work we also utilise the magnitude of Hessian's 's negative Eigenvalue, although a more delicate analysis is required as both: the gradient is potentially unbounded in our case; and the Hessian's 's negative eigenvalues need to be bounded when evaluated across multiple points. We note the scaling of the Hessian network has also previously been observed within [Liu et al., 2020a,b), with empirical investigations into the magnitude of the Hessian's 's negative Eigenvalues conducted within [Sagun et al., 2016, Yuan generalisation bounds were also shown for certain types of non-convex
et al., 2019]. Stability- functions, such Polyak- -ojssiiwiii functions [Charles and Papailiopoulos, 2018, Lei and Ying, 2021] and functions with strict saddles among stationary points [Gonen and Shalev-Shwarke 2017]. In line with our results, Rangamani et al. [2020] shows that for interpolating kernel predictors, minimizing the norm of the ERM solution minimizes stability.
Several works have also recently demonstrated consistency of GD with early stopping for training shallow neural networks in the presence of label noise. The concurrent work [Ji et al., 2021] also showed that shallow neural networks trained with gradient descent are consistent, although their approach distinctly different to ours e.g. leveraging structure of logistic loss as well as connections between shallow neural networks and random feature models/ NTK. Earlier, Li et al. [2020] showed consistency under a certain caussian-mixture type parametric classification model. In more general nonparametric setting, Kuzborskij and Szepesvári [2021] showed that carly-stopper GD is consistent when learning Lipschitz regression functions.
Certain notions of stability, such the uniform stability (taking sup over the data rather than expectation) allows to prove to be optimal up to log-terms [Feldman and Vondrak, 2019, Bousquet et al., 2020]. this work we show bounds in expectation, or equivalently, control the first moment of a generalisation gap. To prove a h.p. bounds while enjoying benefits of a stability in expectation, one would need to control higher order moments [Maurer, 2017, Abou-Moustafa and Szepesvári, 2019], however often this done through a higher-order uniform stability: Since our proof closely relies on the stability in expectation, it is not clear whether our results can be trivially stated with high probability.
risk bounds (h.p.) [Bousquet and Elisseeff, 2002] which are known
10

---

Acknowledgements
D.R, is supported by the EPSRC and MRC through the OxWaSP CDT programme (EP/L016710/1), and the London Mathematical Society ECF-1920-61.
References
K. Abou-Moustafa and Cs. Szepesvári. An exponential efron-stein inequality for l.q stable learning rules. In Algorithmic Learning Theory (ALT), 2019.
Z. Allen-Zhu, Y. Li, and Z. Song. A convergence theory for deep learning via over-parameeterizatoon. In International Conference on Machine Learing (ICML), 2019.
M. Anthony and P. Bartlett. Neural network learning: Theoretical foundations. Cambridge University Press, 1999.
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 Learing (ICML). 2019.
Y. Bai and J. D. Lee, Beyond linearization: On quadratic and higher-order approximation of wide neural networks. In International Conference Learning Representations (ICLR), 2019.
L.. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482, 2002.
P. L. Bartlett, A. Montanari, and A. Rakhlin. Deep learning: statistical viewpoint. Acta Numerica, 2021. URL httph::t//// //tp://///xiiv/// httppp////aaavo.or/aaa////////// httgg//bs/103..0/0
To appear.
O. Bousquet and A. Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2:499-526, 2002.
O. Bousquet, Y. Klochkov, and N. Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference Computational Learning Theory (COLT), 2020.
Z. Charles and D. Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In International Conference on Machine Learing (ICML), 2018.
Y. Chen, C. Jin, and B. Yu. Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint
2018
S. S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient descent provably optimizes over- peeemaarameeeeeeedd neural networks. In International Conference on Learning Representations (ICLR), 2018.
V. Feldman and Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Conference on Computational Learning Theory (COLT), 2019.
N. Golowich, A. Rakhlin, and Shamir. Size-independent sample complexity of neural networks. In Conference on Computational Learning Theory (COLT), 2018.
A. Gonen and S. Shalev-Shwartz. Fast rates for empirical risk minimization of strict saddle problems. In Conference on Computational Learning Theory (COLT), 2017.
M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. International Conference on Machine Learing (ICML), 2016.
T. Hu, W. Wang, C. Lin, and G. Cheng. Regularization matters: A nonparametric perspective overparametrized neural network. In International Conference Artificial Intelligence and Statistics (AISTATS), 2021.
A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: convergence and generalization in neural networks. Conference on Neural Information Processing Systems (NeurIPS), pages 8580-8589, 2018.

---

Z. J. D. Li. and M. Telgarsky. Early-stopped neural networks are consistent. Conference on Neural Information Processing Systems (NeurIPS), 2021.
I. Kuzborskij and C. H. Lampert. Data-dependent stability of stochastic gradient descent. In International Conference Machine Learing (ICML), 2018.
I. Kuzborskij and Cs. Szepesvári. Nonparametric regression with shallow overparameterized neural networks trained by GD with early stopping. In Conference on Computational Learning Theory (COLT), 2021.
J. Lee, L. Xiao, S. S. Schoenholz, Y. Bahri, R. Novak. J. Sohl-Dickstein, and J. Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Conference on Neural Information Processing Systems (NeurIPS), 2019.
Y. Lei and Y. Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learing (ICML), 2020.
Y. Lei and Y. Ying. Sharper generalization bounds for learning with gradient-dominated objective functions. In International Conference on Learning Representations (ICLR). 2021.
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 on Artificial Intelligence and Statistics (AISTATS), 2020.
C. Liu, L. Zhu, and M. Belkin. On the linearity of large non-linear models: when and why the tangent kernel is constant. Conference on Neural Information Processing Systems (NeurIPS), 33, 2020a.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over parameterized non-linear systems and neural networks. arXiv preprint N00.:::0003000000 2020b.
A. Maurer. A second-orde look at stability and generalization. Conference on Computational Learning Theory (COLT), 2017.
Y. Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
B. Neyshabur, Z. Li, Bhojanapalli, Y. LeCun, and N. Srebro. The role of over-parametrization in generalization of neural networks. In International Conference on Learning Representations (ICLR), 2018
S. Oymak and M. Soltanolkotabi. Toward moderate overparameteriizaton: Global convergence guarantees for training shallow neural networks. IEEE Journal Selected Areas in Information Theory, 105, 2020.
A. Rangamani, L. Rosasco, and T. Poggio. For interpolating kernel machines, minimizing the norm of the ERM solution minimizes stability, arXiv:2006. 15522, 2020.
D. Richards and M. Rabbat. Learning with gradient descent and weakly convex losses. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
L. Sagun, I.. Bottou, and Y. LeCun. Eigenvalues of the hessian in deep learning: Singularity and beyond. arXiv preprint arXiv:1611.07476 2016.
B. Schölkopf and A. J. Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. The MIT Press, 2002.
M. Seleznova and G. Kutyniok. Analyzing finite neural networks: Can we trust neural tangent kernel theory? arXiv preprint (XXi::0022.04477 2020.
Shalev-Shwartz and Ben-David. Understanding machine learning: From theory to algorithms.
Cambridge University Press, 2014.
T. Suzuki and S. Akiyama. Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methods. In International Conference on Learning Representations (ICLR), 2021.
12

---

Y. Yao, L. Rosasco, and A. Caponnetto. On early stopping in gradient descent learning. Constructive Approximation, (6(2):289-3155 2007.
Z. Yuan, Y. Yan, R. Jin, and Yang. Stagewise training accelerates convergence of testing error over SGD. Conference on Neural Information Processing Systems (NeurIPS), 2019.
13


Reviews:
[{"review_id": "iza423S9Pw1", "reviewer": "Reviewer_8wG3", "summary": "This paper provides a novel generalization guarantee for over-parameterized one-hidden-layer neural network by using oracle-based stability analysis instead of NTK. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "The paper provides a new type of non-vacuous generalization bound for over-parameterized shallow neural network. It's original and novel and may provide a new direction for generalization guarantees for over-parameterized models. \n\nMost parts of the paper is easy to follow. The organization of the paper could be improved, such as moving main results section earlier so that we can remove some equation/statement duplication in both Sec. 2 and Sec. 3, such as the duplication of Eq. (4) and Corollary 1. \n\nLine 154 mentioned that the oracle-based bound in this paper is tighter than NTK-based bounds because some relaxation of oracle-based bound is applied to achieve an equivalence to NTK-based bound. I am wondering if the authors can provide some examples showing the tighter-ness. For example, does there exist a target function such that oracle-based bound is non-vacuous while NTK-based bound is vacuous?\n\nA few proof steps are not clear to me. For example, in footnote 3 in Page 3, why $L_S (W_T) \\lesssim exp(\\mu\\sum_{j=1}^T 1/j)$ ? Also, I didn't find the proof of Corollary 1 and it's not straight forward to me that Corollary 1 can be derived directly from Theorem 1 and Lemma 1. \n\nOverall, I believe the paper and its techniques will be interesting to the deep learning theory community.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations of the theorems are addressed in the paper. Since this is a theory paper, the societal impact can be negligible. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "hx0KyaG99_", "reviewer": "Reviewer_Rrma", "summary": "This paper presents a bound on the expected risk of a two-layer neural network with smooth activation, where the first layer is trained by gradient descent. The bound is in terms of the smallest L2 distance of the weights to initialization among interpolating solutions. When choosing the total number of iterations to be $n^\\alpha$ ($\\alpha \\in(0,1]$), and the width to be bigger than $n^{5\\alpha}$, the bound essentially scales like $n^{-\\alpha}$ times the squared L2 distance. The analysis is based on stability, and relies on controlling the smallest eigenvalue of the Hessian of the loss.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "While much of the stability-based generalization analysis is for convex cases, the current paper is able to obtain a nontrivial result for two-layer neural networks, including the optimization part. I think the result is generally interesting, because there are few results that can guarantee optimization and generalization together. One representative set of such results are based on the NTK, but the current paper uses a different approach and might allow the network to escape the NTK regime.\n\nThat said, a few things are unclear to me:\n1. How does the bound in this paper compare with the line of work that uses distance to initialization to bound the generalization gap, e.g. [1] below? (BTW, this line of papers are not cited in the current paper.) Admittedly, these papers typically don't have optimization guarantees, but it would still be good to have a careful comparison between the bounds.\n2. In the theorem where the NTK bound is recovered from the result in this paper (Theorem 2), why can you assume $\\lambda_{\\min}(K) \\gtrsim 1/n$? This is not assumed in the paper of Arora et al. Furthermore, the result in [Arora et al. 2019] does not require bounded or smooth activation.\n3. It would be good to have some discussion about the tightness of the bound. For example, in Lemma 2 and Lemma 3, spectral norm is relaxed to Frobenius norm, which seems loose.\n4. One main point the paper stresses is that the analysis is not based on the NTK. However, the result does require the width to grow polynomially with the number of iterations, and it's possible that the network still operates in or close to the NTK regime. Is there an explicit nontrivial theoretical example where the current paper gives an explicit nontrivial bound while NTK cannot? \n\n[1] The role of over-parametrization in generalization of neural networks. Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, Nathan Srebro. ICLR 2019.\n\n\nThe writing in this paper needs significant improvement. There are many small errors and typos throughout the paper. I'd suggest proofreading the entire paper carefully. Some examples I noticed:\n- Inconsistency of conditioning: at some places, $(W_0, u)$ are conditioned on, while at other places only $W_0$ is conditioned on.\n- Line 20: should be $|y_i| \\le C_y$, not $=$.\n- Theorem 2: what does $\\tilde{O}_P$ mean? Also, $K$ is never defined.\n- Assumption 2: you can't assume the loss is uniformly bounded since this is square loss. It seems that what you really need is that the initial loss $L_S(W_0)$ to be bounded by a constant $C_0$. Is this correct, or am i missing something?\n- Assumption 1: there should be absolute values on the 0th, 1st, and 2nd derivatives.\n- Line 450: the definition of $\\ell$ here is for a linear model...\n- Line 477, second step: it should be $\\sqrt{L_S(W_s)}$, instead of ${L_S(W_s)}$.\n- Line 120: \"meaning theat\"\n- Line 160: \"a random inputs\"\n- Line 161: \"use our bounds to we show that\"\n- Line 164: \"recall that that\"\n- Line 198: \"$\\phi(u)$ continuous\" --> \"$\\phi(u)$ is continuous\"\n- ...", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The discussion is mostly adequate. See main review for some additional questions to be addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "TAgax0lWgEr", "reviewer": "Reviewer_9Lej", "summary": "The authors propose to apply stability-based bound on the overparameterized neural networks and reach non-vacuous bound with early stopping. The authors show that the excess risk can be bounded by an interpolating network with the shortest GD path from initialization. The proof can be extended to NTK regimes and brings some interesting conclusions, e.g., GD with early stopping is consistent. Overall, I think this paper is interesting, and I tend to accept this paper.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "【contributions】\n\n(a.) The authors propose to apply stability-based bound on the overparameterized neural networks and show that the excess risk can be bounded by an interpolating network with the shortest GD path from initialization (Theorem 1).\n\n(b.) There are some interesting conclusions based on the analysis. For example, (1) GD with early stopping is consistent; (2) one can recover the NTK-form generalization gap via early stopping (Theorem 2). (The early-stopping requirements, in my opinion, are the intrinsic weakness of stability-based bound.)\n\n(c.) The proof is clear and easy to follow. The authors provide some intuitions behind the proof and the theorems. I enjoy reading such a paper.\n\n\n【questions】\n\n(a)   Line 20, maybe I missed some details. Why do we need |y| = C a constant? \n\n(b)   Does the results of Arora et al. require \\eta T = n? If not, I do not think the claim “our analysis is general enough to recover the results of Arora et al.” is fair.\n\n【some typos】\n\n(a.)  The formula between Line 244-245 lacks “+”\n\n(b.) The motivation of the paper can be significantly improved. I am a little puzzled about whether the authors want to do optimization or generalization when reading the introduction. For example, Line 40-41, “thus, it is not clear whether GD can minimize it up to the desired precision,” makes me think the authors want to do optimization.\n\n(c.)  Maybe I lose some details. Line 101, the condition is m>T^5, while in Theorem 1, the condition is T^3. Could the authors clarify this mismatching?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No potential negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical issues.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "J9qATtjwL92", "reviewer": "Reviewer_EoLw", "summary": "This paper derives bounds for generalization gap of two-layer neural networks using algorithmic stability. The bounds covers noisy and noiseless cases, and depend on the distance of the interpolation solution which is closest to the initialization. With properly chosen number of iterations and network width (with respect to the number of data n), the bounds decay as n increases. \n\nThe bounds requires the width of the networks to be bigger than a polynomial of the number of iterations (specifically, number of iterations times the step size). Hence, it works out of the NTK regime. Through, the bounds can also yield reasonable results in the NTK regime. ", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "This paper derives generalization bounds which covers broader cases than the NTK. Though, the assumptions for the network seems to be stronger than NKT. For example, the output parameters u are fixed, and the activation function is smooth and bounded. Under these assumptions, bounding the Hessians of the loss function becomes easy, and thus bounding the stability of GD also becomes easy. However, with the assumptions no special structure or property of neural network models is employed in the analysis, and the same technique can hardly be extended to deep neural networks without producing exponential terms of the depth. \n\nOther major comments:\n1. Although the bounds work out of the NTK regime, but since the width m should be greater than (\\eta T)^5, it can easily fall into the NTK regime. As is mentioned in the paper, taking T=n^\\alpha, then m>n^{5\\alpha}. When \\alpha>=0.5, the case is already in the NTK regime. So it seems the new bounds do not extend much from the NTK.\n\n2. The deduction from equation 4 to the equation between line 106 and 107 looks confusing to me. Replacing E\\Delta with equation 3 gives ||W-W_0||/(\\eta*T), this cancels with the (\\eta*T) on the denominator on the right hand side of equation 4, and leaves a 1/n. Why the result has 1/n^\\alpha instead of 1/n?\n\n3. It seems the proof part, Section 3, is written in a rush. There are many hard-to-read sentences and typos. For example, in line 198 \"The activation \\phi(u) continuous and twice differentiable \", and in line 205 \"the main theorem a bound on for the gradient descent iterates\", and line 211-213 \"the generalisation gap can be controlled through both: the step size and number of iterations through the factor alongside the trajectory taken by gradient through the Empirical Risk\". ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations of the work. Since this is a pure theoretical work, there's no potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4h"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a bound on the expected risk of a two-layer neural network with smooth activation, where the first layer is trained by gradient descent. The bounds cover noisy and noiseless cases and depend on the distance of the interpolation solution which is closest to the initialization. 

The reviewers agree that the paper provides a theoretical analysis for the generalization gap of two-layer neural networks using algorithmic stability using a proof technique that is not based on the Neural Tangent Kernel, while obtaining results that have a similar generality of the ones of NTK for two layers networks. Moreover, as observed by some reviewers, the bounds require the width of the networks to be bigger than a polynomial of the number of iterations (specifically, number of iterations times the step size), observing that it also works out of the NTK regime. 

In any case, according to the reviewers, the paper provides a relatively novel proof strategy in the context of theoretical analysis of the generalization of deep learning that is conceptually simpler, and also able to shed light on the properties of the first non-trivial example of a dnn, i.e. a 2-layer nn. We think that this contribution is enough for publication.

However, we strongly encourage the authors to improve the writing of the paper, in particular Section 3, as observed by some reviewers. 
Decision: Accept (Poster)