Early-stopped neural networks are consistent
Authors: Ziwei Ji
Justin D. Li
Matus Telgarsky
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Neural Networks
Deep Networks
calibration
consistency
nonseparable
gradient descent

Abstract: This work studies the behavior of shallow ReLU networks trained with the logistic loss via gradient descent on binary classification data where the underlying data distribution is general, and the (optimal) Bayes risk is not necessarily zero.  In this setting, it is shown that gradient descent with early stopping achieves population risk arbitrarily close to optimal in terms of not just logistic and misclassification losses, but also in terms of calibration, meaning the sigmoid mapping of its outputs approximates the true underlying conditional distribution arbitrarily finely.  Moreover, the necessary iteration, sample, and architectural complexities of this analysis all scale naturally with a certain complexity measure of the true conditional model.  Lastly, while it is not shown that early stopping is necessary, it is shown that any classifier satisfying a basic local interpolation property is inconsistent.


Early-stopped neural networks are consistent
Ziwei Ji
Justin D. Li
Matus Telgarsky
$i mjttmmiiioiiiiii University of Illinois, Urbana-Champaige
Abstract
This work studies the behavior of shallow ReLU networks trained with the logistic loss via gradient descent on binary classification data where the underlying data distribution is general, and the (optimal) Bayes risk is not necessarily zero. In this setting, it is shown that gradient descent with early stopping achieves population risk arbitrarily close optimal in terms of not just logistic and misclassification losses, but also in terms of calibration, meaning the sigmoid mapping of its outputs approximates the true underlying conditional distribution arbitrarily finely. More- over, the necessary iteration, sample, and architectural complexities of this analysis all scale naturally with certain complexity measure of the true conditional model. Lastly, while is not shown that early stopping is necessary, it is shown that any univariate classifier satisfying local interpolation property is inconsistent.
Overview and main result
Deep networks trained with gradient descent seem to have no trouble adapting to arbitrary prediction problems, and steadily displacing stalwart methods across many domains. In this work, provide a mathematical basis for this good performance on arbitrary binary classification problems, considering the simplest possible networks: shallow ReLU networks where only the inner (input- facing) weights are trained via vanilla gradient descent with a constant step size. The central contributions are as follows.
1. Fully general classification tasks. The joint distribution generating the (a. y) pairs only requires x to be bounded, and is otherwise arbitrary. In particular, the underlying distribution may be noisy, meaning the true conditional model of the labels, Pr(Y 1|X = 2²). arbitrary.
In this setting, we show that as data, width, and training time increase, the logistic loss measured over the population converges to optimality over all measurable functions, which moreover implics that the induced conditional model (defined by a sigmoid mapping) converges to the true model, and the population misclassification rate also converges to optimality. This is in contrast with prior analyses of gradient descent, which either only consider the training risk [Allen-Zhu
et al. 2018b
Du et al. 2019 Zou et al. 2018, Oymak and Soltanolkotabi 2019 Song and Yang
2019
or can only handle restricted conditional models Allen--Zhu et al. 201 8a Arora et al.
2019
Cao and Gu
2019 Nitanda and Suzuki 2019 Ji and Telgarsky 2020b Chen et 2021]
2. Adaptivity to data simplicity. The required number of data samples, network nodes, and gradient descent iterations all shrink if the distribution satisfies a natural notion of simplicity: the true conditional model Pr[Y 1|X æ] is approximated well by low-complexity infinite-width random feature model.
Rounding out the story and contributions, firstly we present a brief toy univariate model hinting towards the necessity of early stopping: concretely, any univariate predictor satisfying local interpolation property can not achieve optimal test error for noisy distributions. Secondly, our analysis is backed by a number of lemmas that could be useful elsewhere; amongst these are
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

multiplicative error property of the logistic loss, and separately technique to control the effects of large network width over not just finite sample, but over the entire sphere.
1.1 Main result: optimal test error via gradient descent
The goal in this work is to minimize the logistic risk over the population: letting j denote an arbitrary Borel measure over (x. y) pairs with conpactly-supports marginal μs and conditional Py. with a data sample ((z,, y4 )))) and a function f, define the logistic loss, empirical logistic risk, and logistic risk respectively as
{(r) = In +e R() == Σ ((ve)
:- B
We use the logistic loss not only due to its practical prevalence, but also due to interesting multiplicative error property which strengthens our main results (cf. Lemma B.1 and Theorem all while being Lipschitz.
We seek to make the risk R(f) small as possible: formally, we compare against the Bayes risk
R = inf ((()) measurable f:R + RR
While competing with R may seem strenuous goal, in fact it simplifies many aspects of the learning task. Firstly, due to the universal approximation properties of neural networks [Funahashi 1989
Hornik et al. 1989 Cybenko 1989 Barron 1993]. we are effectively working over the space of all measurable functions already. Secondly, as will highlighted in the main result below, via the theory of classification calibration (Zhang 2004 Bartlett et al., 22066]. competing with the Bayes (convex) risk also recovers the true conditional model, and minimizes the misclassification loss; this stands in contrast with the ostensibly more modest goal of minimizing misclassification
restricted class of predictors, namely the agnostic learning setting, which suffers a variety of computational and statistical obstructions [Goel et al.) (2020a Yehudai and Shamir [020 Frei al. 2020].
Our predictors are shallow ReLU networks, trained via gradient descent - the simplest architecture
which is not convex in its parameters, but satisfies universal approximation. In detail, letting (a,)7= be uniformly random +1 signs, (w,)z= with wy 1dd be standard Gaussians, and p 0 be temperature, we predict on an input x E Rd with
m aaor(w)))
P Vm
w)
where 0z(2) == max(0, 2} is the ReLU; since only W is trained, both and a are often dropped. To train, we perform gradient descent with a constant step size on the empirical risk:
W+11 == W - vw(w),
where R(W) = R (- f(x:W)
Our guarantees are for an iterate with small empirical risk and small norm: Wst := arg min min(R(WW) (R,)). i i 1, IIW; Woll S Rga). where Rgd is our early stopping radius: if R&a is guessed correctly, rates improve, but our analysis also handles the case Rgi = oo where no guess is made, and indeed this is used in our final consistency analysis (a pessimistic, fully general setting).
Our goal is to show that this iterate Wst has approximately optimal population risk: R(Wsg) = R. Certain prediction problems may seem simpler than others, and we want our analysis reflect this while abstracting away as many coincidences of the training process as possible. Concretely, we measure simplicity via the performance and complexity of an infinite-width random feature model over the true distribution, primarily based on the following considerations.
By measuring performance over the population, random effects of the training sample are removed, and it is impossible for the random feature model to simply revert to memorizing data, as it never sees that training data.
The random feature model has infinite width, and via sampling can be used as a benchmark for all possible widths simultancously, but is itself freed from coincidences of random weights.

---

In detail, our infinite- width random feature model is as follows. Let U. : R² + R be an
(uncountable) collection of weights (indexed by Rd), and define a prediction mapping via
f<x:U>)) (T< (
2 01) dN(c),
whereby R(Uxx) := R(x f(x; U.o))
Note that for each Gaussian random vector N,, construct random feature + 21 1u'xx This particular choice is simply the gradient of a corresponding ReLU V v (x' (+'z), 2), and is motivated by the NTK literature (Jacot et al. 2018 Li and Liang, 2018 Du et al. 2019]. A similar object has appeared before in NTK convergence ana yses Nitanda and Suzuki 2019 Ji and Telgarsky 2020b].
0].
but the conditions on Ux.. were always strong (e.g., data separation with a margin).
What, then, does it mean for the data to be simple? In this work, it is when there exists Ux with R(Ux,))= ~ R, and moreover U. has low norm; for technical convenience, we measure the norm as the maximum over individual weight norms. meaning sup, [[)x(())]: To measure approximability. for sake of interpretation, we use the hinary Kullback-Leibb divergence (KI.): defining a conditional probability model 6oo corresponding to Use via
(x) = (x(f(x;U~)))
where o(r) =
1 exp(-r))
then the binary KL can be written as
KoinnPp 2xo) = /
Py Pu + +1 Dx0
1 1 Py
Pv) In
duz = R(Uco) - R.
This relationship between binary KI. and the excess risk is a convenient property of the logistic loss, which immediately implies calibration as consequence of achieving the optimal risk.
The pieces are all in place to state our main result.
Theorem 1.1. Let width m 2 In(emd), temperature p > O, and reference model U.o be given with R == max [4, sup, [v)]l < oc, and define a corresponding conditional model (x) == (ff(x; (). Let optimization accuracy Cgd and radius Rys 2 R/p be given, define effective radius vtyeen ((U)) RRT,) and generalization, linearization, and sampling a errors (Ta, T1, TO) as
B min { Rgd.
3R
+ 4e
p
(dln(1/6))8/2
|BB/3 (dlm(1/8)
TD = (on((1001/)) + m m/14
(115(1/
To Ō
==:=
m/66
where it is assumed Tı < 2, and Ô hides constants and In(nend. Choose step size == 4/p², and run gradient descent for t == 1/(8gga) iterations, selecting iterate Wst == arg min (R(W,) 3) : I|W, Woll s Rga). Then, with probability at least 1 256.
R(W5i) R
(logistic error)
Krin (Py, (oo) + (c - (e) R(U,0)
(reference model error)
T R'c
(optimization error) (generalization error),
(pB R)T
where the classification and calibration errors satisfy
R(W5)) R
(logistic error)
2 / (o(f(z) -Pv)² dx)
IV Iv
(calibration error)
2 (R((Ws))- -R,)²
1
(classification error).
Lastly, for any >> 0, there exists U't) with sup. [T(((1)) (v)] and whose conditional model
0 (z) == (lf((1, V2; U!O))) satisfies Koin(py, 2200 S
3

---

Remark 1.1. The key properties of Theorem 1.1 are as follows.
1. (Achieving error (c)) in three different regimes.) As Theorem 1.1 is quite complicated, consider three different situations, which vary the reference model Uh and its norm upper 3o, well the early stopping radius Rgd. Let target population (excess) risk > 0 be given, set Egd = E and t = 1/(8ega) as in Theorem I.1 and suppose n 2 1/e" samples: in each of the three following settings, the other parameters parameters (namely p and m) will be chosen to ensure final error R(W - R = O(e).
bound R max 4, p. sup, [0 (1))l)
(a) (Easy data.) Suppose a setting with easy data: specifically, suppose that for chosen target accuracy 0, there exists Ux with Koin (Py, Poo) R(U,)) R s R(U,s) S If we set = 1 and m 2 R then (Tn: TI, To) are all constant, and we get final bound R(Wss:) - R ((c).
Note crucially that m z R$ sufficed for this setting; this was a goal of the present analysis. as recovers the polylogaritmiic width analyses from prior work (Ji and Telgarsky| 2202bb Chen et al. 2021]. Those works however either used separation condition due to Nitanda and Suzuki [209]] in the shallow case, or an assumption on the approximation properties of the sampled weights (a random variable) in the deep case, and thus the present analysis provides not just a re-proof, but a simplification and generalization. This was the motivation for the strange multiplicative form of the errors in Theorem [.] had we used the more common additive errors with standard linearization tools, a poly polylogarithmic width proof would fail.
(b) (General data, clairvoyant early stopping radius Rga.) Suppose that we are in the general noisy case, meaning any U we pick has a large error Koin (Pg. so but we magically know the R corresponding to a good Ux.. and can choose Rgd = R/ p. Unlike the previous case, to achieve some target error e, we need work harder to control the term [exp(T] + To) 1] RU.,).. since no longer have small R(Ux):; this end, since Ti = O (mp²) 1/6) and To = Ö(p + 1/m choosing p = m 11/8 and m = 1/c² gives 71 = O and To = Ōc). and together R(W - R = Occ)
(c) (General data, worst-case early stopping.) Suppose again the case of general noisy data with large error Kain xx) for any Ux we pick, but now suppose we have no early stopping hint, and pessimistically set Rig = co. As a consequence of all of this, the term B can scale (2/3/p 1/(pe thus control T (((1/))2/3 (0tl//e22//mmmm))) (mp2)1/0) and To Ö(p + 1/m3 we can again choose = m 1/8 but need a larger width m = 1/e 10/4 Together, we once again achieve population excess risk R(Ws..) R = (c).
Summarizing, a first key point is that arbitrarily small excess risk O(e) is always possible; as discussed, this is in contrast to prior work, which either only gave training error guarantees, or required restrictive conditions for small test error. A second key point is that the parameters of the bound, most notably the required width, will shrink greatly when either the data is easy, or an optimal stopping radius Red known.
2. (Consistency.) Consistency is a classical statistical goal of achieving the optimal test error almost surely over all possible predictors Theorem 1.1 namely the preceding argument that we can achieve excess risk OEe) even with general prediction problems and no early stopping hints (Rza oo). The consistency guarantee is stated formally in Corollary 2.3 The statement takes the width to infinity, and demonstrates another advantage of using infinite-wind width reference model: within the proof, after fixing target accuracy, the reference model is fixed and used for all widths simultaneously.
oo; here it is proved as consequence of
3. (Non-vacuon) generalization, and an estimate of R.) There is extensive concern throughout the community that generalization estimates are hopelessly loose [Neyshabur et al.) 2014 Zhang et 2016 Dziugaite and Roy| 2017]: to reduce the concern here, we raise two points. Firstly. these concerns usually involve explicit calculations of generalization bounds which have terms scaling with some combination of [[W]] (not ||W - Woll and m;; e.g.- one standard bound has spectral norms ||W]|a and (2, matrix norms II(W - Wo)Tll,,n which are upper bounded by
||W - Woll ym [Bartlett et al. 2017]. By contrast, the present work uses new generalization

---

bound technique (ef. Lemma B.8) which first de-linearizes the network, then applies a linear generalization bound which has only [WW and no explicit poly(m). and then re-linearizes.
Secondly, there may still be concern that the story here is broken due to the term R. and namely the non-existence of good choices for Uso For this, we conducted a simple experiment. Noting that we can freeze the initial features and train linear predictors of the form (()) (a;; V) for weights V [m (cf. section 1.4). and that the performance converges to the nafinite-widte performance as m - oc, we fixed a large width and trained two prediction tasks: an easy task of until Reasy//i
1/2, and hard task of MNIST 3 vs 5 until Reard/ / se 1/2. After training, we obtained test error R(Vauy)) = 0.01 and RVinn ~ 0.08. Plugging all of these terms back in to the bound, firstly these techniques can yield a non- non-vacuous generalization bound, secondly they do not exhibit bad scaling with large width, and thirdly they do reflect the difficulty of the problem, as desired.
MNIST
4. (Early stopping and the NTK.) As discussed above, when the data is noisy, the method is explicitly early stopped, either by clairvoyantly choosing Rgg. or by making / small. In this setting, the optimization accuracy éga is an excess empirical risk, meaning in particular that O training error (the interpolation regime [Belkin et al.) 2018a) will not reached. This is in stark contrast to standard NTK analyses Allen-Zhu et al. [0188]], which guarantee zero training error, but can not ensure good test error in general. Since the NTK itself is an early stopping (as in, if one continues to optimizes, one exits the NTK), then the early stopping in this work is even earlier than the NTK early stopping; this situation is summarized in Figure [ in the appendix, and will be revisited for the lower bound in Section 1.2
5. (Classification and calibration.) The relationship to classification and calibration errors is merely a restatement of existing results [Zhang] 2004 Bartlett et al.) [2006), though it is reproved here in an elementary way for the special case of the logistic loss. Similarly, the guarantee that
Koin (Py, 2b2) can be made arbitrarily small is also not a primary contribution, and indeed most of the heavy lifting is provided both by prior work in neural network approximation [Barron [993), and by the existing and reliable machinery for proving consistency (Schapire and Freund 2012 As such, the consistency result is stated only much later in Corollary 2.3 and our focus 18 the exact risk guarantees in Theorem
I.1
6. (Inputs with bias: (x, 1)/v2 E Rd+ The end of Theorem 1.1 appends constant to the input (and rescales), which simulates a bias term inside each ReLU; this is necessary since our models are (sigmoid mappings of) homogeneous functions, whereas Py is general. Biases are also simulated in this way in the consistency result in Corollary 2.3
Further discussion of Theorem I.I including the formal consistency result (ef. Corollary 2.3 and proof sketch, all appear in Section 2 Full proofs appear in the appendices.
1.2 Should we early stop?
Theorem 1.1 uses early stopping: it can blow up if R 0 and the two gradient descent parameters Rys and I/Egd are taken to 30 in an uncoordinated fashion. Part of this is purely technical: as with many neural network optimization proofs, the analysis breaks when far from initialization. It is of course natural to wonder what happens if one trains indefinitely. entering the sttudid interpolation regime [Belkin al., 2018b a Bartlett et al. 2019]. Furthermore, there is evidence that gradient descent on shallow networks limits towards a particular interpolating choice, one with large
margins (Soudry et al. 2018 Lyu and Li 2020 Chizat and Bach 2020 Ji and Telgarsky 2020a Is
this behavior favorable?
While we do not rule out that the interpolating solutions found by neural networks perform well, we show that at least in the low-dimensional (univariate!) setting, if a prediction rule perfectly labels the data and is not too wild between training points, then it is guaranteed to achieve poor test loss on noisy problems. This negative observation is not completely at odds with the interpolation literature, where the performance of some rules improves with dimension [Belkin et al., (0018))
Proposition 1.2. Given a finite sample ((r,, y: with x; E R and ye E (+1), let Fa denote the collection of local interpolation rules (cf. Figure 2 in the appendix): letting (()) index examples in
5

---

sorted order. meaning 2(11 S (2) S ... S T()), define Fn as
Fn:= Vi (()) (()), and
y()) = ((++1), then inf f (az(1) + +11 ())((1)) v(i) > 00.. aE(0.1)
Then there exists a constant C > 0 so that with probability at least 1 - over the draw of ((0;, U:))
with n 2 ln(1/6)/c, /c, every E Fr, satisfies R2( 2 (J) +
Although a minor contribution, this result will be discussed briefly in Section with detailed proofs appearing in the appendices. For similar discussion for nearest neighbor classifiers albeit under a few additional assumptions, see [Nakkiran and Bansal 2021].
1.3 Related work
Analyses of gradient descent. The proof here shares the most elements with recent works whose width could be polylogarithmic in the sample size and desired target accuracy 1/c [Ji and Telgarsky 2020b. Chen et al. 2021]. Similarities include using a regret inequality as the core of the proof, using an -iith target network (Nitanda and Suzuki 2019 Ji and Telgarsky [022bb) and using linearization inequality [Chen et al. [202]] Allen-Zhu et al. 2018b.. On the technical side, the present work differs in the detailed treatment of the logistic loss, and in the linearization inequality which is extended to hold over the population risk; otherwise, the core gradient descent analysis here is
arguably simplified relative to these prior works. It should be noted that the use of a regret inequality here and in the previous works crucially makes use of negated term which was dropped in some
classical treatments; this trick is now re-appearing in many places (Orabona and Pal 2021 2020].
Frei et al.,
There many other, somewhat less similar works in the vast literature of gradient descent on neural
networks, in particular in the neural tangent regime (Jacot et al. 2018 Li and Liang] 2018 Du et al.
2019]. These works often handle not only training error, but also testing error (Allen-Zhu et al. [0 Sa
Arora et al. 2019 Cao and Gu 2019 Nitanda and Suzuki 2019 Ji and Telgarsky [020b] Chen et al. 2021]. As was mentioned before, these works do not appear to handle arbitrary target models; see for instance the modeling discussion in [Arora et al. 2019 Section 6]. As another interesting recent example, some works explicitly handle certain noisy conditional models, but with error terms that do not go to zero in general [Liang et al. 2021]
Consistency. Consistency of deep networks with classification loss and some training procedure is classical; e.g., in [Farago and Lugosi| 1993), the authors show that it suffices to run a computationally intractable algorithm on an architecture chosen to balance VC dimension and universal approximation. Similarly, the work here makes use of Barron's 's superposition analysis in an infinite-width form to meet the Bayes risk [Barron 1993 Ji al. 2020b]. The statistics literature has many other works giving beautiful analyses of neural networks, e.g., even with minimax rates [Schmidt- 2017). though it appears this literature generally does not consider gradient descent and arbitrary classification objectives.
In the boosting literature, most consistency proofs only consider classification loss (Barllttt and Traskin 2007 Schapire and Freund, (2022). though there is a notable exception which controls the convex loss (and thus calibration), although the algorithm has number of modifications (Zhang and Yu 2005). In all these works, arbitrary Py are not handled explicitly as here, but rather implicitly y via assumptions on the expressiveness of the weak learners. One exception is the logistic loss boosting proof of Telgarsky (2013), which explicitly handles measurable Py via Lusin's 's theorem as is done here, but ultimately the proof only controls classification loss.
Following the arXiv posting of this work, a few closely related works appeared. Firstly, Richards and Kuzborskij [202 show that the expected excess risk can scale with IW Wo WollF/10 though in contrast with the present work, is not shown that this ratio can go to zero for arbitrary prediction problems, and moreover the bound is in expectation only. Secondly, the work of lBruun et al. [021] is even closer, however it requires a condition on the Fourier spectrum of the conditional model Py, which is circumvented here via a more careful Fourier analysis due to Ji et al. [0206].
Calibration. There is an increasing body of work considering the (in)ability of networks trained with the logistic loss to recover the underlying conditional model. Both the empirical side [Guo

---

et al. |017 and on the theoretical side [Bi et al. 2021], the evidence is on the side of the logistic loss doing poorly, specifically being overconfident meaning the sigmoid outputs are too close 0 or 1. This overconfident regime corresponds to large margins; indeed, since gradient descent can be proved some settings to exhibit unboundedly large unnormalized margins on all training points [Ly and Li 2020], the sigmoid mapping of the predictions will necessarily limit to exactly 0 or On the other hand, as mentioned in [Bai et al., 2021]. regularization suffices to circumvent this issue. In the present work, combination of early stopping and small temperature are employed. As mentioned before, calibration proved here as an immediate corollary of meeting the optimal
logistic risk via classification calibration (Zhang
2004
Bartlett et al. 2006
1.4 Further notation and technical background
The loss l, risks R. and R, and network f have been defined. The misclassification risk R2(S) = Pr[sgn(f(X)) * Y] appeared in Theorem I.] where sgn(f(x)) 1 [[f(2) 2 0] 1.
Next, consider the "gradient" of f with respect to weights W:
vf(=:W) = Σ a 10]l/wf 2 0je
may seem the nondifferentiability 0 concerning, but in analyses close initialization (as the one here), few activations change, and their behavior is treated in a worst-case fashion. Note that, as easily checked with this expression, [VW) S p. which convenient many places in the proofs. Here || denotes the Frobenius norm; || |/2 will denote the spectral norm.
Given weight matrix W, at time i, let (wi,))== refer to its rows. Define features f() at time and a corresponding empirical risk R() using the features time as
(z; = (F)((, (VV()) = P Σ
CajufalluT
Vm
= R(x + (x)
By 1-homogeneity of the ReLU,, f (x; Wi) = f(;; W.). which will also be used often. These features at time i, meaning ((6 and R are very useful in analyses near initialization, they do not change much. As such, (()) and (( and (0) will all appear often as well.
To be a bit pedantic about the measure μ.: as before, there is a joint distribution μr, which is over the Borel alagebrra on IR x {11] where ||>||||| < 1 almost surely. This condition suffices to grant both disintegration of fu into marginal μı and conditional Py [Kallnberrg] 2002, Chapter 6]. and also Lusin's 's theorem [Folland 1999. Theorem 7. 7.10], which is used to switch from a measurable function
to continuous one the consistency proof (cf. Corollary 2.3
2 Discussion and proof sketch of Theorem
This section breaks down the proof and discussion into four subsections: section with common technical tools, then sections for the analysis of generalization, optimization, and approximation.
2.1 Key technical lemmas
There are two main new technical ideas which power many parts of the proofs: a multiplicative error property of the logistic loss, and linearization over the sphere.
The logistic loss property is simple enough: for any a 2 b, it holds that {(-a)/e(-b) S cxp(a b). On the surface, this seems innocuous, but this simple inequality allows us to reprove existing polylogarithmic width results for easy data (Ji and Telgarsky 2020b Chen et al. 2021), however making use of proof scheme which is slightly more standard, or at the very least more apparently a smooth convex proof with just this one special property of the logistic loss (as opposed to a few special properties).
7

---

The second tool is more technical, and is used crucially in many places in the proof. Many prior analyses near initialization bound the quantity
f<; V) fz;; W) (V
W).
where V and W are both close to initialization Allen- Zhu et al. 2018b Cao and Gu 2019 Chen et al. 202T]. These proofs are typically performed on a fixed example dgs and then union bound carries them over to the whole training set. Here, instead, such bound is extended to hold over the entire sphere, as follows.
Lemma 2.1 (Simplification of Lemma B.7
Let scalars 8 and Ry 2 and RB 2 be given.
1. With probability at least 1 3nd,
(B) S exp
6p GR(BB + 2Rv) ) R./ In(e/8)1/4
IW: W: Ry (B)
sup
m m//6
W Ry
A Woll
2. Suppose m 2 In(edm). With probability at least 1 - (1+ 3()
R(W,) (W)) S exp
225pk An(edm/0
sup Woll
m
The preceding lemma combines both the linearization technique and multiplicative error property: it bounds how much the empirical and true risk change for fix weight matrix if we swap in and out the features at different iterations. That these bounds are a ratio due to the multiplicative error property. That the second part holds over the true risk, in particular controlling behavior over all ||>|| < 1, is a consequence of the new more powerful lincarization technique. This lincarization the sphere is used crucially in three separate places: use it when controlling the range in the generalization proofs, when de-linearizing after generalization, and when sampling from the infihite-width model Uno- The method of proof is inspired by the concept of co-VC dimension [uurvits and Koiran 1995]: the desired inequality is first union bounded over a cover of the sphere, and then relaxed to all points on the sphere. key difficulty here the non-smoothness the ReLU, and key lemma establishes a smoothness- inequality (cf. Lemma B.5). These techniques appear in full in the appendices.
2.2 Generalization analysis
The generalization analysis ends up being easy thanks to the multiplicative error control in Lemma B. and the aforementioned linearization over all points in the sphere. Specifically, to prove general- ization, the network is first linearized, then generalization of linear predictors is applied, and then de-linearization applied on the population risk side. This generalization bound only pays logarith- mically in the width m.
Typically the casiest step in proving generalization is to provide worst-case estimate on the range of the predictor. Here, since there is a goal of controlling the logistic loss over the population, brute foreing this range estimate incurs a polynomial dependence on network width. The solution here is again to apply the aforementioned Lemma B.3) the generalization statement appears in full as Lemma B.8 together with its proof in the appendices.
2.3 Gradient descent analysis
A common tool in linear prediction is the regret inequality
|| z112 + 2m Σ R((1+1) S 1l:0 - =|12 + +2)
SEt
which can be derived by expanding the square in || - 211 and applying smoothness and convexity. The term I|e, - =|I2 is often dropped, but can used very convenient way: by the triangle inequality, if ||u voll > 2||z voll. then the norm terms above may be canceled from both sides,

---

which leaves only the empirical risk terms; overall, this argument ensures both small norm and small empirical risk. This idea has appeared in a variety of works [Shamir 2020 Ji et al.] 2020a], and is used here to provide a convenient norm control, allowing linearization and all other proof parts to go through. Combining this idea with the earlier generalization analysis and a few other minor tricks gives the following bounds, which in turn provide most of Theorem 1.1.
Lemma 2.2. Let temperature > O, step size 1 S 4/p², optimization accuracy Egd > 0, ra- dius Rys > O, network width m 2 In(emd), reference matrix Z E Rmxxd corresponding scalar Rz I Rga where Rz 2 max (1 np, W 21I), and I. 2 1/(2np²)a)) be given; correspond- ingly define Wst arg min (R(W.) i 1, Woll Rgd). Define effective radius
B 3:=min min Ryd. 3Rz + 2e nt (Z)) and linearization and generalization errors
25pB4/3 dlu m/
Tn 80 (d'In(em²(/6)) 3/2
Vni
and suppose T S 2. Then, with probability at least 1 - 3nd, the selected iterate Wer satisfies [|W5: Woll S B, along with the empirical risk guarantee
R(We)) = (Z)) e (pRz))²
and by discarding an additional 165 failure probability, then (1) S (Z) + pR2TT, and R(W s() S (T))( + e (pR2)) + 4T eB Rz)pTa-
This version of the statement, unlike Theorem [.] features an arbitrary reference matrix Z. This is powerful, though it can be awkward, since Wo is a random variable.
2.4 Approximation analysis, consistency, and the proof of Theorem 1.1
Rather than trying to reason about good predictors which may happen to be close to random initializa- tion, the approach here is instead to start from deterministic predictors over the population (e.g., U.o). and to use their structure to construct approximants near the initial iterate, the random matrix Wo- Specifically, the approach here is fairly brute force: given initial weights Wo with rows (w),)) the rows (u,))"1 of the finite width reference matrix U E Rmxd intended to mimic Uho (which is after all a mapping Uno Rd + Rd are simply
aj agUac Wo.s-
Ty
P/m
By construction, Wwll < R/p, where := = sup, 10 (w) To argue that R. ()) (U) and RU,,,))
are close, the abstract control over the sphere in Lemma B.3 is again used. Plugging this U into Lemma 2.2 and introducing Kain (Py, &o0) via Lemma B. gives the first part of Theorem I.1 and the
second part of Theorem 1.1 is also from Lemma B.I
Py (we must include a bias term, as mentioned in Remark [.I). Pf were continuous, there is variant of Barron's Is seminal universal approximation construction which explicitly gives an infinite- width network of the desired form [Barron| 1993 Ji et al. 2020b). To address continuity is even easier: Lusin's 's theorem [Folandd, 1999 Theorem 7.10 lets us take the measurable function Py, and obtain a continuous function that agrees with it all but negligible fraction of the domain. This completes the proof.
remains to prove that for any Py. there exists Uso with d(x ((xx,))//2;
As mentioned, a key property of the reference model Uno is that it depends on neither the random sampling of data, nor the random sampling of weights. This vastly simplifies the proof of consistency, where the proof scheme first fixes > 0 and chooses U... and leaves it fixed as and n vary. Corollary 2.3. Let early stopping parameter & E (0,1) be given, and for each sample size define a weight matrix W., (Rm ((d+1) and corresponding conditional probability model Hh (2) == ((f((z, 1)/v2; W.)) as follows. For each sample size n, let (W(")) Yio denote the corresponding sequence of gradient descent iterates obtained with parameter choices n!n) = (m and

---

ml() n (1-5), and n/(*) := 4/(pln)3, and (n)
"gl := ==- and g(m) = -=ntt1/88 and choose the
empirical risk minimizer over the sequence, meaning W,, arg min (R( : S t(m) (in the T.I this is Wet with
notation Theorem
with Rgd = oo). Then
La(me) Py a.s.
RW))
R a.s.,
R2)
R2 a.s.
on
where the last convergence is in the (p(z)) metric.
The of parameter & 10,1) is standard in similar consistency results; for instance the analogous parameter in the consistency analysis of AdaBoost [Bartlett and Traskin 2007]. Proofs, as usual, are in the appendices.
3 Discussion and proof sketch of Proposition 1.2
Proposition asserts that univariate local interpolation rules - predictors which perfectly fit the data, and are not too wild between data points of the same label will necessarily achieve suboptimal population risk. The proof idea seems simple enough: if the true conditional probability Py is not one of {0, 1/2, } everywhere, and is also continuous, then there must exist a region where it is well separated from these three choices. It seems natural that a constant fraction of the data in these regions will form adjacent pairs with the wrong label; local interpolation rule will fail on exactly these adjacent noisy pairs, which suffices to give the bound. In reality, while this indeed the proof scheme followed here, the full proof must contend with many technicalities and independence issues. It appears in the appendices.
While the motivation in Section 1.2 focused on neural networks which interpolate, and also maximum margin solutions, the behavior on this noisy univariate data is also well-illustrated by k-nearest- neighbors classifiers (k-nn). Specifically, 1-nn is a local interpolant, and Proposition a.plppiies. On the other hand, choosing & = (In(n)) is known to provide enough smoothing to achieve consistency and avoid interpolation [Dvrooye et al. 1996].
should be stressed again that even if the remaining pieces could be proved to apply this result to neural networks, namely necessitating early stopping, it would still be a univariate result only, leaving open many interesting possibilities in higher dimensions.
4 Concluding remarks and open problems
Empirical performance. Does the story here match experiments? E.g., often the case that neural network performs well, then so does random feature model? Do neural networks fail on noisy data care not taken with temperature and early stopping? Most specifically, this part of what happens in existing results reporting such failures [Guo al. 2017
Temperature parameter p. Another interesting point of study is the temperature parameter p. arises here in a fairly technical way: if Py is often close to 1/2, then the random initialization of Wo gets in the way of learning Py. The temperature p is in fact brute-force method of suppressing this weight initialization noise. On the other hand, temperature parameters are common across many works which rely heavily on the detailed real-valued outputs of sigmoid and softmax mappings; e.g.. in the distillation literature (Hinton et al., 2015). The temperature also plays the same role as the scale parameter the lazy training regime [Chizat and Bach] 2019). generally useful, and does the analysis here relate to its practical utility?
Random features, and going beyond the NTK. The analysis here early stops before the feature learning begins to occur. How do things fare outside the NTK? Is there an analog of Theorem [.I still stopping shy of the interpolation pitfalls of Proposition 1.2 but managing to beat random features with some generality?
The logistic loss. One reason the logistic is used here is its simple interplay with calibration (e.g.. see the elementary proof of Lemma B. as compared with the full machinery of classification calibration [Zhang] 2004 Barttett et al. 2006)). The other key reason was the multiplicative error property Lemma B. Certainly, the logistie loss widely used in practice; are the preceding technical points at all related to the widespread empirical use of the logistic loss?
10

---

Acknowledgments and Disclosure of Funding
The authors are grateful for support from the NSF under grant 115-1750051. MT thanks many friends for illuminating and motivating discussions: Daniel Hsu, Phil Long, Maxim Raginsky, Fanny Yang.
References
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. arXiv: 1011:0111..000 04918 [ca LG], 2018
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv: 1811 03962
[cs LG]. 2018b.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine- Fine-grained anal- ysis of optimization and generalization for overparameterized two-layer neural networks. arXiv: 08584 [cs.LG] 2019.
Yu Bai, Song Mei, Huan Wang, and Caiming Xiong. Don't just blame over- wvr-paaraeetrization for over-confidence: Theoretical analysis of calibration in binary classification. 2102. [cs LC], 2021.
Andrew Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information Theory, 39(3):930-945, May 1993.
Peter L. Bartlett and Mikhail Traskin. AdaBoost is consistent. Journal of Machine Learning Research, 8:2347-2368, 2007.
Peter L.. Bartlett, Michael I. Jordan, and Jon D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(4))) 2006.
Peter L Bartlett, Dylan Foster, and Matus J Telgarsky. Spectrally- normalized margin bounds for
neural networks. In Advances in Neural Information Processing Systems, pages 6240-6249, 2017.
Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. arXiv: 1906. 11300 [stat. NM], 2019.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning practice and the biri-vari trade-off. 2018a. arXiv: 1812. 11118 Sstat.ML)
Mikhail Belkin, Daniel J. Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate. NeurlPS, 2018b.
Avrim Blum, John Hopcroft, and Ravindran Kannan. Foundations of Data Science. Cambridge University Press, 2020.
Alina Braun, Michael Kohler, Sophie Langer, and Harro Walk. The smoking gun: Statistical theory improves neural network estimates. 2021. arXiv:2107 .95550 [math.ST] ST].
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In NeurlPS, 2019.
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much pvrrpaaramttriization is sufficient learn deep relu networks? In ICLR, 2021.
Lénaïic Chizat and Francis Bach. A Note Lazy Training in Supervised Differentiable Programming. arXiv: 1812. 07956v2
[math.OC]] 2019.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In COLT, 2020.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 304)3303- 1989.
Kenneth Davidson and Stanislaw Szarek. Local operator theory, random matrices and Banach spaces. In Handbook of the geometry of Banach spaces, volume 1, pages 317-366, 2001.
11

---

L. Devroye, L. Györfi, and G. Lugosi. A probabilistic theory of pattern recognition. Springer, 1996.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In ICLR, 2019.
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. 2017. [cs.LG]
arXiv: 1703. 11008
A. Farago and G. Lugosi. Strong universal consistency of neural network classifiers. IEEE Transac- tions on Information Theory, 39(4): 146-1151, 1993. doi: n...109998..23333...
Gerald Folland. Real analysis: modern techniques and their applications. Wiley Interscience, edition, 1999.
Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic learning of single neuron with gradient descent. arXiv: :205 14426 [cs LG], 2020.
K. Funahashi. On the approximate realization of continuous mappings by neural networks. Neural Netw, 183):183-12,, May 1989. ISSN 0893-6080.
Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. Superpolynomial lower bounds for learning one-layer neural networks using gradient descent. In ICML, 2020a.
Surbhi Goel, Adam R. Klivans, Pasin Manurangsi, and Daniel Reichman. Tight hardness results for training 2epth-2 relu networks. arXiv: 2011 13550 [cs. 2020b.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weiinerger. On calibration of modern neural networks, 2017.
Leonid Gurvits and Pascal Koiran. Approximation and learning of convex superpositions. In Paul Vitányi, editor, Computational Learning Theory, pages 222-236 Springer, 1995.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network.
arXiv:1503. 02531 [stat. ML] 2015.
K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal approxi- mators. Neural Networks, 255):359-366, july 1989.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In NeurlPS, pages 8571-8580, 2018.
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. arXiv: 06657 [cs. LG], 2020a.
Ziwei and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks. In ICLR, 2020b.
Ziwei Ji, Miroslav Dudík, Robert E Schapire, and Matus Telgarsky. Gradient descent follows the regularization path for general losses. In COLT, pages 2109-2136, 2020a.
Ziwei Ji, Matus Telgarsky, and Ruicheng Xian. Neural tangent kernels, transportation mappings, and universal approximation. In ICLR, 2020b.
Olav Kallenberg. Foundations of modern probability. Probability and its Applications (New York). Springer- Verlag, New York, second edition, 2002.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In NewrlPS, pages 8157-8166, 2018.
Shiyu Liang, Ruoyu Sun, and R. Srikant. Achieving small test error in mildly overparameterizee neural networks. arXiv:2104. 11895 [cs.LG], 2021.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In ICLR, 2020.
12

---

Preetum Nakkiran and Yamini Bansal. Distributional generalization: A new kind of generalization. 2021. 200iv:2009... 08092 [cs.LG]
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. search of the real inductive bias: On role of implicit regularization in deep learning. arXiv:1412 6614 [cs.LG] 2014.
Atsushi Nitanda and Taiji Suzuki. Refined generalization analysis of gradient descent for parameterized two-layer neural networks with smooth activations on classification problems. arXiv: 09870 [stat.Min
Francesco Orabona and Dávid Pál. Parameter-free stochastic optimization of variationally coherent functions, arXiv: 00236 [math. OC] 2021.
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameteriiztton:: global conver- gence guarantees for training shallow neural networks. arXiv: 1902. 04674 [cs.LG], 2019.
Dominic Richards and IIja Kuzborskij. Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel. 2021. arXiv:2107 12723 [stat.ML]
Robert E. Schapire and Yoav Freund. Boosting: Foundations and Algorithms. MIT Press, 2012.
Johannes Schmidt-Hieher Nonparametric regression using deep neural networks with relu activation function. 2017. arXiv: 1708. 16633
[math.ST].
Shai Shalev-Shwariz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
Ohad Shamir. Gradient methods never overfit on separable data. 2020.
[cs.LG],
Zhao Song and Xin Yang. Quadratic suffices for over-parametrizztion via matrix chernoff bound. [cS.LG]
2019. arXiv: 03593
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. ICLR, 2018.
Matus Telgarsky. Boosting with the logistic loss consistent. COLT, 2013.
Gilad Yehudai and Ohad Shamir. Learning a single neuron with gradient methods. arXiv:2001 05205 [cs.LG]. 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: 16 1.03530, 2016.
Tong Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32:56-85 2004.
Tong Zhang and Bin Yu. Boosting with early stopping: Convergence and consistency. The Annals of Statistics, 33:1538-1579, 2005.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv: 1811.08888 [ca. LG), 2018.
13


Reviews:
[{"review_id": "mv-Rm2gUTR7", "reviewer": "Reviewer_oWmh", "summary": "This paper gives a theoretical analysis of the neural networks under the logistic loss on binary classification task. It considers the setting of training a shallow two-layer neural network with ReLU activation, and proves a core theorem that gives a high probability bound on the difference between population risk and Bayes risk. The obtained results imply consistency, since all parameters can be made arbitrarily small. It also proves a proposition related to 1d datasets, where if the neural network interpolates the training data perfectly and is not too wild between training points, then it is guaranteed to perform badly on noisy test data.", "questions": "", "limitations": "", "rating": 6, "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": "Strength:\n\n1. This paper gives a very strong theoretical result regarding the impact of early-stopping on training a shallow neural network. Specifically, it associates a multiplicative factor on the term R(\\overline U_\\infty), suppose this term is smaller than eps_gd then \\tau_0 can be ignored and the KL divergence term is also smaller than eps_gd. This recovers a result for data separable setting [Ji and Telgarsky, ICLR’2020] but generalizes it into the non-separable setting.\n\n2. The technical lemma regarding comparing a neural network to a local linear approximation has been improved, rather than an additive error term as in prior works, it yields a multiplicative error term. This is the key to ensure this paper to get a similar result as in data separable setting.\n\n3. To prove the linearization approximation, it bounds an expression \\langle \\nabla f(x;W)-\\nabla f(x;W_0), W \\rangle for all \\|x\\| \\leq 1. This is in contrast to the standard practice where the quantity f(x;V)-f(x;W)- \\langle \\nabla f(x;W), V-W \\rangle for a fixed data point x and use a union bound. The technique employed in this paper is novel and from a different perspective compared to the convergence analysis of gradient descent on over-parametrized neural networks [Allen-Zhu, Li and Song, ICML’2019]. This co-VC dimension inspired technique has potentially to be used in other analysis, e.g., the convergence analysis of NTK and other variants.\n\nWeakness:\n\n1. The paper layout is a bit unusual and hard to follow. It spends a very small amount of paragraphs to set up the problem tentatively, then discuss the major contributions. These contributions are discussed in more details later with some of the notations left undefined until a later section. Section 2 and 3 are dedicated to present the essentials of the proof. It might be better to first introduce the problem background, its formal setup and some of the related literature on this problem in more detail. Then present a preliminary version of the main result. More details of the result can be laid out after introducing the notations.\n\n2. It might be better to summarize and compare the results obtained in this paper with various previous works under different settings. For example, this paper obtains a similar popular risk loss result for data non-separable setting as some early works addressing data separable setting. Also, what’s the difference between the results obtained using the co-VC dimension technique compared with the standard analysis which makes use of the fact that weights are not far away from the initialization?\n\n3. The early-stopping discussion in this paper is very preliminary. It is suggested on line 132 that this is due to technical reasons in the proof of Theorem 1.1, however, I don’t see an explicit mention or discussion related to early-stopping for this Theorem. A negative 1d result is also discussed as in Proposition 1.2. Due to the limited paragraphs involving this topic, it is hard to understand the importance and impact of early-stopping. \n\nIf authors can address the above 2 and 3, and provide further clarification on the subject, I can raise the score.\n\nTypos: On line 144, the definition of {\\cal F}_n should be f: \\R\\rightarrow \\R since the proposition considers 1d data.\n\nMinor:\n\nSome missing NTK citations:\n\nQuadratic suffices for over-parametrization via matrix Chernoff bound.\n\nOn the Convergence Rate of Training Recurrent Neural Networks.\n\nTraining (over-parameterized) neural network in near linear time.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, it discusses limitations. It does not discuss societal impact, however, since it's a pure theory paper, it does not have a direct impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "lQBJ1Hgw8G", "reviewer": "Reviewer_sDSa", "summary": "This work shows that a certain neural network learning procedure\n(a single trainable layer, trained via gradient descent)\nis consistent, meaning it asymptotically converges to the Bayes optimal classifier.\nAlthough certain algorithms on neural networks were known to be consistent before, this result was not know for *gradient descent*\nfrom random initialization.\nThis paper thus contributes to our fundamental understanding\nof the power of gradient methods on neural networks.", "questions": "", "limitations": "", "rating": 8, "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": "## Recommendation\n\nI recommend acceptance.\nThe result is clean, the paper is very well-written,\nand the conclusion is significant.\n\nAs a disclaimer, I did not get a chance to check all of the proofs.\nHowever, the overall proof strategy appears sound.\n\n## Strengths\n\n- The writing is clear, and outlines the proof strategy.\n- The result is, as far as I know, not known before.\n(Although the tools involved are used in many related papers, as is acknowledged).\n- The result is \"good to know\": gradient methods are often used in practice, and having such consistency results can be a first step towards justifying them.\n- The theoretical requirement of early-stopping may be related to certain relevant practical phenomenon, and could shed light on differences between interpolating and non-interpolating classifiers.\n\n## Weaknesses\n\n- As with all consistency results, it is not clear how much this result says about why neural networks\nare actually successful in practice.\n(For example, k-nearest-neighbors are also asymptotically consistent...). The quantitative bounds on generalization may very well diverge exponentially fast, depending on the problem setting.\nIn general, \"consistency\" is a fairly weak property, but it is still good to establish.\n\n- The results on \"adaptivity to data simplicity\" does not seem like a major contribution, since results of this form were already known in the past (as the paper indeed cites), for various notions of \"simplicity.\" And it is not clear how this result contributes beyond what is already known in the area.\n\n### Relevant Citations\n\nThe following empirical paper shows that, complementary to your results, interpolating networks are *not* consistent on noisy distributions:\nhttps://arxiv.org/abs/2009.08092\n\nThis in particular addresses your stated open question of\n\"Do neural networks fail on noisy data if care is not taken with temperature and early stopping?\"\n\nTheorem 1 in the above paper may also be seen as a certain analogue of your Proposition 1.2, for the case of nearest-neighbor classifiers.\nIn general, the fact that 1-nearest-neighbors is not asymptotically consistent is related to your claims about local interpolation rules.\n\n\n----\nEdit after rebuttal: score increased from 7 to 8.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Suggestions on limitations are in the \"weakness\" section above.\nSocietal impacts N/A.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "f_VfkVYAFXG", "reviewer": "Reviewer_PKyu", "summary": "The paper studies 1-hidden layer ReLU networks trained with SGD and logistic loss on arbitrary classification tasks, showing optimality given that early-stopping is adopted. An interesting complexity measure for the underlying mapping is shown to play a key role in how the generalization error is affected by relevant factors such as number of iterations and network neurons. Insights on interpolation capacity of networks are given along with new and exciting questions.", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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 is very well-written, clear, and the discussion on both implications and limitations of the analysis is impeccable.\n\nI see the main Theorem as a strong contribution, showing optimality of shallow ReLU networks w.r.t. the population loss under very mild assumptions. The need for early-stopping for the main result is thought-provoking, and the provided discussion on its relation to the interpolation regime and NTK (where both have gained a lot of attention recently) draw exciting connections and open new questions for future research.\n\nThe complexity measure presented here is also exciting, as it seems to interact in a very desirable way with the relevant model & training factors and is also seems intuitive and is strongly connected to the NTK. A key question is how much the behavior changes once actual learning is taking place, but I can see this analysis requiring considerable additional technical effort and it being appropriate to leave it completely to future work.\n\nAlthough I haven't checked the proofs in detail, it seems that there is considerable technical contribution as well.\n\nI believe this is a strong submission, with a solid contribution which is presented extremely well and raises interesting questions, therefore I recommend acceptance. However, I would like to note that I am not very familiar with the topic and might have missed possible limitations / concerns.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "O6n3_1-NHsC", "reviewer": "Reviewer_afNw", "summary": "The paper studies the convergence properties of the gradient descent (GD) algorithm for training two layers neural networks. The convergence is established wrt the population loss and under essentially no constraint on the underlying data distribution. Moreover, the simplicity of a given data distribution is determined by measuring the complexity of infinite-width random feature models which approximate the underlying distribution. It is shown then that less complex is the data the less samples, network nodes and iterations are needed.\n", "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": "One of the current great challenges in deep learning is to understand the ability of GD to converge to models which exhibit good generalization capabilities--despite the nonconvexity of the training loss. Thus, the strong convergence results established in this work are rather interesting. In addition, tying the convergence properties of GD to the structure of the underlying data distribution seems to be a step in the right direction of abandoning\\refining the distribution-free paradigm presently governing the machine learning literature, and I find it very it encouraging. \n\nTo me, the two main issues are: 1. large parts of the analysis seem rather incremental when compared to previous works. 2. The positioning of early-stopping, the main selling point of the paper, are not entirely clear: the negative result (possible failures of DL learning in the interpolation regime) addresses a nearly-negligible part of the regime to which the positive result (convergence rates of GD) applies. Thus, I believe that the analysis of early-stopping in the paper cannot be regarded as conclusive. \n\nAssorted comments:\n* I feel that, due to their importance in the paper, the very notion of early-stopping and interpolation regime (the phenomenon of double descent, in particular) should be introduced and discussed more explicitly. \n\n* L41, the predictor function f is not explicitly introduced.\n\n* Perhaps discuss the implications of the modeling choice of drawing the weights of the second layer at random more thoroughly. In particular, can you characterize a large deterministic set of 2nd-layer weights to which similar convergence results apply?\n\n* Theorem 1.1, use of n instead of m (above L96).\n\n* Theorem 1.1, is there a practical way of estimating the quantities involved in the upper and lower bound presented in the theorem for a number of interesting settings to see if they behave nicely? In the nearby realm of sample complexity, bounds are, by and large, vacuous when instantiated to practical settings. See, e.g., https://arxiv.org/abs/1703.11008 (and references therein).\n\n* L151 \"recent works whose width\"\n\n* L284 : \n-- What other models can be used to measure simplicity instead of the infinite-width random features model? \n-- What are the upsides and downsides of the current choice? \n-- Quantitively, how 'simple' are MNIST, CIFAR and other conventional datasets in ML when measured using the method proposed in the paper?  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "9MCRXqgPwyW", "reviewer": "Reviewer_9b2J", "summary": "This paper studies the training of single layer neural networks trained with gradient descent. The authors provide an upper bound on the logistic loss function using a reference infinite-width random feature model (which does not depend on the sampling of the training set). They also show that if a classifier in the 1-dimensional setting is in the interpolating regime, then the classification error is (depending on the number of consecutive wrong labeled samples) large. \n\nThe proof is lengthy and quite involved and in appendix. On the one hand, a sketch of each result is provided in the main paper: it sheds light on the novel ingredients and technicalities used in the proof, which is useful (and explains for instance why the paper is restricted to logistic losses). On the other hand, the paper could make a better job to explain the gist behind the main result in (Theorem 1, which is half a page long just to be stated) in Section 1, by complementing the interesting remark 1.1 with a more practical discussion on how the parameters $m,\\rho, R, \\delta, \\epsilon_{gd}$ are to be chosen as a function of $n, d$ to bring the three terms of the bound close to zero (simultaneously), and how the reference model $\\overline{U}_\\infty$ is obtained from the data. An interesting feature of this bound is indeed that it decomposes in three errors (on the model, optimization convergence, and generalization).\n\nWhile the results are definitely worth publishing, I wonder if a journal in ML theory (where enough time is given to review the proofs in appendix) might not be a more appropriate venue than a conference for such a purely theoretical paper.", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "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 proof of Theorem 1.1, as stated in line 107, lets the training iterations increase. Yet the classifier chosen in Theorem 1.1 is the one with the lowest empirical (training) loss ($R(W_{\\leq t})$). The authors refer to this as the early stopped model, but the model is more the best model obtained on the training data up to time $t$. However, in practice an early stopped model does not have the lowest training loss: a low training loss is avoided by early stopping, which should not interpolate all the training samples and therefore the noise that could be present in the training set. Could you make the connection between the model $W_{\\leq t}$ and early stopping?\n\nMinor nit: In the equation between the lines 41 and 42: $l(r)$ should be $l(z)$.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not relevant, the paper is purely mathematical on a theoretical model.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is very well-written, clear, and the reviewers found the main theorem a strong contribution.

Please take into consideration the reviewers comments and suggestions in the final version.
Decision: Accept (Spotlight)