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,)}= 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((;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/8)
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(W5() 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 Uxe 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 7 (((1/))2/3 (0tl//e2///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-wine 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
: 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 AAllen-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; = (7)((, (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.I 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
ag 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 I.1 is also from Lemma B.I
Py (we must include 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::111..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 pvrrparramttrrization 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..23433...
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 [G], 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. a00iv: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": "uBNESB9F6dQ", "reviewer": "Reviewer_Q5eH", "summary": "This paper presents a mathematical analysis of the behavior of neural networks trained with the logistic loss via gradient descent on binary classification data. ", "questions": "", "limitations": "", "rating": 6, "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": "This paper gives a rigorous analysis of the shallow network for binarty classificiation with gradient descent. Generally, it is well-written and technically sound. The result is stated clearly. The only concern is a lack of discussions of its practical significance in real-world deep neural networks, which are almost all beyond the ideal assumptions in the analysis. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main part of the paper focuses on the shallow network for binary classification, while the title refers to a more general topic related to general networks. Given that the current analysis is highly restricted to a specific setting, it is suggested to change the title to a more specific one. \n\nAnother point, for technical convenience, the paper focuses on networks with infinity width, it could be appreciated if some discusssions on finite width neural networks are given. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5 hours"}, "extra_text": {}}, {"review_id": "i3Yf1Q4ieqv", "reviewer": "Reviewer_7mdj", "summary": "This work analyzes the performance of a shallow neural network trained with logistic loss via gradient descent on binary classification data for general data distribution. The authors prove that as data, width, and training time increases the logistic loss measured on population converges to optimality at early stopping. The required resources (number of iterations, samples, and width) are shown to be scaling with some complexity measure of the true conditional model.", "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": "To measure the simplicity of the true conditional model while abstracting other training factors such as training sample or random weights, the authors adopt an infinite-width random feature over the true distribution and represent the complexity of the model in terms of the maximum of individual weight norms. Then, the logistic error and classification error are bounded as a function of this complexity measure as well as of width, number of samples, dimension, and iterations. Thanks to the particular form of the logistic loss, the calibration error is also effectively bounded from the logistic error bound. \n\nStrength\n- Theorem 1.1 shows consistent results (bounds) for three different losses (logistic error, classification error, and calibration error), all of which are bounded in terms of the model complexity measure.\n- The proved result applies to more general model distributions compared to previous works that mainly assumed separable distributions. \n\nWeakness\n- The analysis is still restricted to “binary” classification as like many previous works. \n- Without any experiments, it is not clear whether the main message of this paper matches experimental results, i.e., whether the performance of neural networks have any correlation with that of a random feature model.\n- The complexity measure for the conditional model is not a term that can be calculated from data, so that the main theorem may not provide any guidance in designing neural network architectures, which makes the implication of the theorem weaker. \n\nOverall, this paper provides unified theoretical guarantees for binary classification test for three different losses and for general data distribution, which generalizes previous results in several aspects. However, without any experiments, it is hard to see whether the message of the main theorem indeed aligns with the true experimental results. Moreover, it is not clear how to evaluate/estimate the complexity measure of the model from the data in practical scenarios if one wants to use the intuition from the main theorem as some guidance in designing neural network training. \n\n\nUPDATE: response read. Thank you for the response!", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are provided in Section 4.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "HfX9S3Lau_", "reviewer": "Reviewer_ab3Y", "summary": "The authors in this work provide generalization bounds for random  features models trained with gradient descent and logistic loss. They revisit some known results on calibration and classification errors and provide new proofs based on elementary techniques. They also provide some indications in low-dimensional settings about the necessity of early stopping.\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": "Overall I think this is a good paper and solid work however there were admittedly several parts that were hard to follow. While the theorems are very heavy on notation the explanations following are very high level and it’s difficult to get what’s happening and why are some assumptions necessary. For example, I am not sure that I followed why early stopping is important for the generalization bound. Section 1.2 that is meant to give some intuition about it refers to a very restrictive setting of 1-dimensional input that I don’t think is enough to extract meaningful and convincing evidence of what happens in practice (of course the authors mention that this is not the main contribution of their work), it might even be misleading and the behavior in higher dimensions could be completely different (since in practice interpolation seems to help).\n\nAs for the main result, do the bounds of theorem 1.1 refer only to some particular regime? They do have a notion of the complexity of the model (the quantity R) and hence can the bound be vacuous if the complexity is very high and we don’t have enough data? Or they work for all regimes and I am missing something here?\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "BzAjtixT58S", "reviewer": "Reviewer_hyJf", "summary": "This paper shows that early stopped neural networks achieves the same population risk as the Bayes optimal classifier, including the probability distribution output after sigmoid. They show this for a shallow neural network with one hidden layer, for data distributions that are ''simple\" in the sense that they are separable by a random features model.", "questions": "", "limitations": "", "rating": 7, "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": "Strengths:\n1. This is a strong result. Even though the paper is analyzing the case of shallow networks and 'simple' distributions, the statement that an SGD trained network will converge to Bayes optimal classifier is a strong statement worthy of publishing\n2. The paper is technically strong. I thought the technique used for comparing to linearized network, proving generalization and de-linearizing again is pretty neat\n\n\nWeaknesses:\n1. The paper could benefit from more discussion on the regime in which in this analysis is valid. The open questions mentions that this analysis works only if the network is not in the feature learning regime, but the main body of the paper does not discuss this explicitly. This is specially important since 'early stopping' in practice is taken to mean the time when validation loss starts to diverge, and that may occur well after the lazy regime (depending on other parameters) \n2. The discussion of inconsistency of interpolating classifiers should cite Nakkiran & Bansal ( https://arxiv.org/abs/2009.08092 ) who give arguments that interpolating networks converge to samplers of the conditional distribution and hence are inconsistent  \n\n\nMinor comments:\n1. Line 41: $l(z)$ instead of $l(r)$\n2. In Lemma 2.1, is the $f$ on line 216 and 217 supposed to be $h$?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hrs"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper analyzes shallow neural networks trained with gradient descent on logistic loss and shows that early stopping achieves optimal population risk.  The reviewers and I are all in agreement that the results are strong and technically interesting, and will be valuable for the NeurIPS community. I encourage the authors to address the reviewers' minor comments and recommend acceptance.
Decision: Accept (Spotlight)