Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
Authors: Ziwei Ji
Matus Telgarsky
Venue:  (2020)
Keywords: neural tangent kernel
polylogarithmic width
test error
gradient descent
classification

Abstract: Recent theoretical work has guaranteed that overparameterized networks trained by gradient descent achieve arbitrarily low training error, and sometimes even low test error.
The required width, however, is always polynomial in at least one of the sample size $n$, the (inverse) target error $1/\epsilon$, and the (inverse) failure probability $1/\delta$. 
This work shows that $\widetilde{\Theta}(1/\epsilon)$ iterations of gradient descent with $\widetilde{\Omega}(1/\epsilon^2)$ training examples on two-layer ReLU networks of any width exceeding $\textrm{polylog}(n,1/\epsilon,1/\delta)$ suffice to achieve a test misclassification error of $\epsilon$. 
We also prove that stochastic gradient descent can achieve $\epsilon$ test error with polylogarithmic width and $\widetilde{\Theta}(1/\epsilon)$ samples. 
The analysis relies upon the separation margin of the limiting kernel, which is guaranteed positive, can distinguish between true labels and random labels, and can give a tight sample-complexity analysis in the infinite-width setting.

Published as a conference paper at ICLR 2020
POLYLOGARITHMIC WIDTH SUFFICES FOR GRADIENT DESCENT TO ACHIEVE ARBITRARILY SMALL TEST ER- ROR WITH SHALLOW RELU NETWORKS
Ziwei Ji Matus Telgarsky University of Illinois, Prbaan-CCammaainn fziweiji2, m eiilinoii edu
ABSTRACT
Recent theoretical work has guaranteed that overparameterized networks trained by gradient descent achieve arbitrarily low training error, and sometimes even low test error. The required width, however, is always polynomial in least one of the sample size n, the (inverse) target error 1/s, and the (inverse) failure probability 1/5. This work shows that @(%)) iterations of gradient descent with 2(12)) training examples on two-layer ReLU networks of any width exceeding polylog(n, (n, 1/c, 1/8) suffice to achieve a test misclassification eтror of c. We also prove that stochastic gradient descent can achieve test error with polylogarithmic width and é(1/c) samples. The analysis relies upon the separation margin of the limiting kernel, which is guaranteed positive, distinguish between true labels and random labels, and can give a tight sample-complexity analysis in the infinite- width setting.
INTRODUCTION
Despite the extensive empirical success of deep networks, their optimization and generalization properties still not fully understood. Recently, the neural tangent kernel (NTK) has provided the following insight into the problem. In the infinite-width limit, the NTK converges to a limiting kernel which stays constant during training: on the other hand, when the width is large enough, the function learned by gradient descent follows the NTK (Jacot et al. 2018). This motivates the study of overparameterized networks trained by gradient descent, using properties of the NTK. In fact, parameters related to the NTK, such as the minimum eigenvalue of the limiting kernel, appear to affect optimization and generalization (Arora al. 2019)..
However, in addition to such NTK NTK-dependent parameters, prior work also requires the width to depend polynomially on n, 1/5 or 1/e, where n denotes the size of the training set, denotes the failure probability, and denotes the target eиror. These large widths far exceed what is used empirically, constituting a significant gap between theory and practice.
Our contributions. In this paper, narrow this gap by showing that two-layer ReLU network with ((0n(n)))+([(//e)e) hidden units trained by gradient descent achieves classification error e on test data, meaning both optimization and generalization occur. Unlike prior work, the width is fully polylogarithmic in n, 1/6, and 1/c; the width will additionally depend on the separation margin of the limiting kernel, quantity which guaranteed positive (assuming no inputs are parallel), can distinguish between true labels and random labels, and can give a tight sample-complexity analysis in the -nddhite-width setting. The paper organization together with some details are described below.
Section 2 studies gradient descent on the training set. Using the & geometry inherent in classifi cation tasks, we prove that with any width at least polylogarithmic and any constant step size larger than 1, gradient descent achieves training error in (1/cc iterations (cf. Theorem 2.2). As is common the NTK literature (Chizat & Bach 2019). we also show the parameters hardly change, which will be essential to our generalization analysis.

---

Published as a conference paper at ICLR 2020
Section 3 gives test error bound. Concretely, using the preceding gradient descent analysis, and standard Rademacher tools and exploiting how little the weights moved, we show that with (11/E²) samples and @(1/e) iterations, gradient descent finds a solution with test error (cf. Theorem 3.2 and Corollary 3.3p. (As discussed in Remark 3.4 ((1/e) samples also suffice via a smoothncss-basee generalization bound, at the expense of large constant factors.)
Section 4 considers stochastic gradient descent (SGD) with access standard stochastic on- line oracle. We prove that with width at least polylogarithmic and ((1/c) samples, SGD achieves an arbitrarily small test error (cf. Theorem 4.1.
Section 5 discusses the separation margin, which is in general positive number, but reflects the difficulty of the classification problem in the infinite-width limit. While this margin can degrade all the way down to O(1/ Vn) for random labels, can be much larger when there is a strong relationship between features and labels: for example, on the noisy 2-XOR data introduced in (Wei et al., 2018). we show that the margin is 12(1/ In(n)), and our SGD sample complexity is tight in the infinite-wide wiith case.
Section 6 concludes with some open problems.
1.1 RELATED WORK
There has been a large literature studying gradient descent on overparameterized networks via the NTK. The most closely related work is (Nitanda & Suzuki 2019), which shows that a two-layer network trained by gradient descent with the logistic loss can achieve small test error, under the same assumption that the NTK with respect to the first layer can separate the data distribution. However, they analyze smooth activations, while we handle the ReLU. They require 12(1/e²) hidden units, (((1/e)) data samples, and (11/e) steps, while our result only needs polylogarithmic hidden units, (21/e²) data samples, and ((1/e) steps.
Additionally on shallow networks, Du et al. (0188) prove that on an overparameterizeed two-layer network, gradient descent can globally minimize the empirical risk with the squared loss. Their result requires 22n2/ (/²) hidden units. Oymak & Soltanolkotabi 2019 : Song & Yang (2019) further reduce the required overparameterization, but there is still a poly(n) dependency. Using the same amount of overparameterization as (Du et al. 2018b), Arora et al. 2019) further show that the two- layer network learned by gradient descent can achieve small test error, assuming that on the data distribution the smallest eigenvalue of the limiting kernel at least some positive constant. They also give fine-grained characterization of the predictions made by gradient descent iterates; such a characterization makes use of a special property of the squared loss and cannot be applied to the logistic regression setting. Li & Liang] (2018) show that stochastic gradient descent (SGD) with the cross entropy loss can learn a two-layer network with small test error, using poly(f, 1/c) hidden units, where é is at least the covering number of the support of the feature distribution using balls whose radii are no larger than the smallest distance between two data points with different labels. Allen-Zhu et al. (2018a) consider SGD on a two-layer network, and variant of SGD on a three-layer network. The threr-layer analysis further exhibits some properties not captured by the NTK. They assume ground truth network with infinite-order smooth activations, and they require the width to depend polynomially on 1/c and some constants related to the smoothness of the activations of the ground truth network.
On deep networks, a variety of works have established low training error (Allen-Zhu et al. 2018 8b; Du al. 2018a] Zoo al. 22188) Zou & Gu 2019). Allen-Zhu et al. (2018c) show that SGD can minimize the regression loss for recurrent neural networks, and Allen- & Li (2019b) further prove low generalization error. Allen-Zhu & Li (2019a) show that using the same number of training examples, a three-layer ResNet can learn function class with a much lower test error than any kernel method. Cao & Gu (20T9a) assume that the NTK with respect to the second layer of a two-layer network can separate the data distribution, and prove that gradient descent on deep network can achieve test error with ((1/E*) samples and ((1/e24) hidden units. Cao & Gu 2019b) consider SGD with an online oracle and give general result. Under the same assumption as in (Cao & Gu 2019a), their result requires 221 ((1/)14) hidden units and sample complexity O(1/e).
2

---

Published as a conference paper at ICLR 2020
By contrast, with the same online oracle, our result only needs polylogarithmic hidden units and sample complexity (11/c).
1.2 NOTATION
The dataset is denoted by {(z,, Fi) where 2, E I' and E {-1,+1}. For simplicity, we assume that ||æ: 1 for any S S n, which is standard in the NTK literature.
The two-layer network has weight matrices W E IR and a E R. We use the following parameterization, which also used in (Du al. 2018b Arora et al. 2019)
1 Vm Σ ago ((
a()
with initialization
00,00 ~ NO, Ta), and as unif ((-1,+13).
Note that in this paper, w., denotes the s-th row of W at step t. We fix a and only train W, as in (Li & Liang 2018 Du al. 2018b Arora et al. 2019; Nitanda & Suzuki 2019). We consider the ReLU activation ((2) = max {0, )), though our analysis can be extended easily to Lipschitz continuous, positively homogeneous activations such as leaky ReLU.
We use the logistic (binary cross entropy) loss {(=) == In (1 + exp(-z)) and gradient descent. For any 1 < i S and any W, let f((W) = f(z;; W, a). The empirical risk and its gradient are given
by
n R(W)= = E =
1 Σ l (v.f(WW) VVF(W)) n1 i=1
(v.f(WW). and vR(W)
For any 2 0, the gradient descent step is given by W4+1 == W. - th vŘ(W.). Also define
(w) = (V.(WW)) w), and R() = Σ (v..
Note that (W,) (WW)). This property generally holds due to homogeneity: for any W and any 1 S m,
Of: Ow,
05: Ow,
0, [WW,) xz) > His
and
Ws
aso
((ws, zi)),
VTI
Vmn
and thus (V), w) f((W).
EMPIRICAL RISK MINIMIZATION
In this section, consider a fixed training set and empirical risk minimization. We first state our assumption on the separability of the NTK, and then give our main result and proof sketch.
The key idea of the NTK do the first-order Taylor approximation:
fa; W, a) se f(;; Wo. a) + (Vw/(x; Wo, a), W- Wo)
In other words, want do learning using the features given by (.((W) RRmx A natural assumption is that there exists U mmmxd which can separate { (V()))), 3.) >"= with positive margin:
v. (I.
min Isisn
min 1815a
y/ V m
a (ū,, xz) [( > 0] > 0. (2.1)
The infinite-width limit of eq. 2.11 is formalized as Assumption 2.1 with additional bound on the 00) norm of the separator. A concrete construction of U using Assumption 2. is given in eq. 2.2
3

---

Published as a conference paper at ICLR 2020
Let μN denote the Gaussian measure on R given by the Gaussian density with respect to the Lebesgue measure on Rd. We consider the following Hilbert space
| [1lu(=)BB < c00
H = w: IR" + Rd
For any x E Rd, define or H
Oz (2) x1l (2, > 0].
and particularly define Φ, == Ø2. for the training input z;. Assumption 2.1. There exists ö E H and > O, such that | S for any E R4, and for any 1 ISiSM n,
ys (0, dil = Vi (b(2), duv(z) 2
As discussed in Section 5 the space H. is the reproducing kernel Hilbert space (RKHS) induced by the infinite-width NTK with respect to W, and Φr maps x into H. Assumption 2.1 supposes that the induced training set {(A,, 34) 3=)
be separated by some E H. with an additional bound on [(2)]l2 which is crucial in analysis. It is also possible give dual characterization of the separation margin (cf. eq. (5.2), which also allows us to show that Assumption 2.1 always holds when there are parallel imputs (ef. Proposition 55. However, it is often more convenient to construct i directly; see Section 5 for some examples.
With Assumption 2.1 state main empirical risk result.
Theorem 2.2. Under Assumption 2.1 given any risk target E (0, and any & E 1/31 let
:= 22 (m/6 In(4/c) and M 4096X2
7/4
76
Then for any 2 M and any constant step size r $ 1, with probability 1 38 over the random initialization,
R(W)) se where T= nx/
T
Moreover for any S t < T and any 15 $ m,
4A -ws,t-waool/ wr.0l12 S mmm
-
While the number of hidden units required by prior work all have a polynomial dependency on n, 1/8 or 1/e, Theorem 2.2 only requires m = S2 (In(n/8) + lm(1/e)2). The required width has polynomial dependency on //, which an adaptive quantity: while 1// can be poly(n) for random labels (cf. Proposition 5.2 it can be polylog(n) when there a strong feature-label relationship. for
example on the noisy 2-XOR data introduced in (Wei et al. 2018) (cf. Proposition 5.3). Moreover, we show in Proposition 5.4 that if we want { (. y: Ji-1 to be separable, which is the
starting point of an NTK-style analysis, the width has to depend polynomially on 1/7.
In the rest of Section give proof sketch of Theorem 2.2 The full proof is given in Ap-
pendix A
2.1 PROPERTIES AT INITIALIZATION
In this subsection, give some nice properties of random initialization.
Given an initialization (Wo: a), for any < S m, define
ú, = Vm
a. ((w.o);
(2.2)
where 0 is given by Assumption 2.1 Collect ú, into matrix T E Raxdd It holds that ||
5
1/ 1/ym, and U <
4

---

Published as a conference paper at ICLR 2020
Lemma 2.3 ensures that with high probability U has positive margin initialization.
Lemma 2.3. Under Assumption 2.7 given any ô (0.1) and any 61 E (0, if m 2
(2ln(n/0) feg, then with probability
5, it holds sinultaneously for all S S n that
ln(n//) 2 7 - 61.
v (U) - y (V)((W)) 0) -7-1
m
For any W, any 62 > O, and any S i S n, define
(:(W, = 1 Σ 1 (wan so
Lemma 2.4 controls (W 62). will help us show that T has a good margin during the training process.
Lemma 2.4. Under the condition of Lemma 2.3 for any Cg 0, with probability 1 - 8, it holds simultaneously for all S i is n that
In(n/o)
61
a; (Wo, (2) S
62 +
I 62
+
2m
Finally, Lemma 2.5 controls the output of the network at initialization.
Lemma 2.5. Given any E (0,1), if 2 25 ln(n/2/)) then with probability simultaneously for all < i S that
5, it holds
[s Wo, S 2 (4n/8).
2.2 CONVERGENCE ANALYSIS OF GRADIENT DESCENT
We analyze gradient descent in this subsection. First, define
1 12
Ō(W)
Σ E' (vf((W)). 7
We have the following observations.
For any W and any s s S m, /d. (R(W)
I 1/Vm, and thus [V((W)) S 1.
2
Therefore by the triangle inequality,
S @(W).
The logistic loss satisfies 0 < - < 1, and thus Õ(W) <
The logistic loss satisfics - < l, and thus @(W) < R(W).
The quantity first appeared in the perceptron analysis Novikoff) 1962) for the ReLU loss, and has also been analyzed in prior work (Ji & Telgarsky 2018 Cao & Gu 2019a Nitanda & Suzuki, 2019]. In this work, Q specifically helps us prove the following result, which plays an important role in obtaining width which only depends on polylog(1/c).
Lemma 2.6. For any 2 and any W, if S 1. then
The (W.) s || w I1 W||Wex - w|
2(, (W).
Consequently, if we use a constant step size 17 5 1 < < then
17
Σ R(W,)) + +||W; W/ w/2 < Wo W F
+ 2n
Σ T<1
R(T) (w)
r<t
5

---

Published as a conference paper at ICLR 2020
The proof of Lemma 2.6 starts from the standard iteration guarantee:
W
W
W.
W
2n (VR(W.), W) + Vi(mi
We can then handle the inner product term using the convexity of and homogeneity of ReLU, and control /R( by R(W,) using the above properties of ((W.). Lemma 2.6 is similar to Fact D.4 and Claim D.5), where the squared loss considered.
(Allen-Zhu & Li
2019a
Using Lemmas given Appendix
2.3 to 2.6
we can prove Theorem 2.2 Below proof sketch; the full proof is
1. We first show that as long l|w,, - Wsooll2 S 4X/(1mmm) for all S S m. holds that (1) (Wo + XT) I e/4. To see this, let us consider R()) first. For any 1 S i I n, Lemma 2.5 ensures that KVJa Woll is bounded, while Lemma 2.3 ensures that (WW)..) U concentrated around 7 with a large width. As a result, with the chosen X in Theorem 2.2 can show that (W))..) Wo + XU) is large, and ( AU) is small due to the exponential tail of the logistic loss. To further handle ((,,, we use a standard NTK argument control (V)((W)) V.((W)). Wo XU) under the condition that || ,o,0 42/(7//m).
2. We then prove by contradiction that the above bound on ||w,,- Wa,oll2 holds for least the first I' iterations. The key observation is that as long as ( + AU) < e/4, we can use it and Lemma to control Σr<t Q(W,), and then just invoke ||wa,e wa,olla 1
11 ETer @(W+)/ Vm.
The quantity Erse (W,,) has also been considered in prior work (Cao & Gu 2019a
Nitanda & Suzuki 2019), where it is bounded by vt Ercc ((W,)² using the Cauchy- Schwarz inequality, which introduces a v factor. To make the required width depend only on polylog(1/c). we also need an upper bound on Σrcr ((W=) which depends only on polylog(1 (1/e). Since the above analysis results in vt factor, and in case (1(1/c) steps are needed, it is unclear how to get a polylog(1/e, width using the analysis in (Cao & Gu 2011aa] Nitanda & Suzuki 2019). By contrast, using Lemma 2.6 we can show that Erer Q(W,) S 4X/7, which only depends on In(1/e).
3. The claims of Theorem 2.2 then follow directly from the above two steps and Lemma 2.6
GENERALIZATION
To get a generalization bound, we naturally extend Assumption 2.1 to the following assumption. Assumption 3.1. There exists e E H and > O, such that [i()) S for any 2 E R2, and
y / (o(x), (2,z) > 0l duv(() 2T
for almost all (x, y) sampled from the data distribution D.
The above assumption is also made in (Nitanda & Suzuki 2019) for smooth activations. (Cao & Gu 2019a) make a similar separability assumption, but in the RKHS induced by the second layer az by contrast, Assumption 3.J is on separability in the RKHS induced by the first layer W.
Here is our test error bound with Assumption
3.1
Theorem 3.2. Under Assumption
3.7 given any E 10 and any ā E 1/4), let À and M be
given in Theorem 2.2
2 In((4n/0) + In(4/e)
4096X2
and M ==
7/4
76

---

Published as a conference paper at ICLR 2020
Then for any M and any constant step size n 1, with probability 1 46 over the random initialization and data sampling,
(V22n(4n)) (nnnn/6)))))) + In(4/e)
In((//))
P(raa)-D (zf We a) 20) S 2e
+ 66
2/v/
2n
where & denotes the step with the minimum empirical risk before n2
Below is direct corollary of Theorem 3.2
Corollary 3.3. Under Assumption 3.1 than't 1 and let
given any e, E (0, 1), using a constart step size no larger
1 7422
and m = In(n//)) + In(1/c)2
11
78
it holds with probability 1 5 that P(a (yf(z; Wk, 50) c, where k denotes the step with the minimum empirical risk in the first (1/-pe) steps.
The proof of Theorem 3.2 uses the sigmoid mapping - (2) = 6- ==+///1ee>>> the empirical average
@(Ws), and the corresponding population average Q(W₂) = (x,,)) -6' (yf(2; aa) As noted in (Cao & Gu 2019a), because P(e.v)~ (yf (x; WR, a) s 0) v 2Q(We), it is enough to control Q.W)). As Q(Wi) is controlled by Theorem 2.2 it is enough to control the generalization error ((W,), ((Ws). Moreover, since -!" is supported [0, 1] and I-Lipschitz, it is enough to bound the Rademacher complexity of the function space explored by gradient descent. Invoking the bound on W W. 2 finishes the proof. The proof details are given in Appendix B
Remark 3.4. To get Theorem 3.2 we use a Lipschitz- based Rademacher complexity bound. One can also use smoothness- based Rademacher complexity bound (Srebro et al. 2010 Theorem 1) and get sample complexity (())+t)). However, the bound will become complicated and some large constant will be introduced. It is an interesting open question to give a clean analysis based on smoothness.
STOCHASTIC GRADIENT DESCENT
There some different formulations of SGD. In this section, consider SGD with online oracle. We randomly sample W, and a, and fix a during training. At step i, data example (rr, y:) sampled from the data distribution. We still let f:WW) I (x;;; W, a), and perform the following update
+1 = W; THLl (Wi(WW))) dA V.W,)
Note that here starts from 0.
Still with Assumption 3.1 we show the following result.
Theorem 4.1. Under Assumption 3.1 given any c, 8 E (0, 1), using a constant step size and m ((m(3/))++m(//3))//) ) holds with probability 8 that
n Puw (1; s 50) Sc for n n= Ō(1Pp))))
n
Below is proof sketch of Theorem 4.1 the complete proof is given in Appendix C W. define
For any and
RW(W: = ll (VS(W) w3). and Q((W) == - (y (VI(W)),))
Due to homogeneity, it holds that (...) (W:)(WW)) and (.(,)) = - (v:t(WW)).
7

---

Published as a conference paper at ICLR 2020
The first step is extension of Lemma 2.6 to the SGD setting, with similar proof.
Lemma 4.2. With a constant step size 1 S 1, for any W and any i 2 0,
n Σ (.W.)))
12 -
+
Wo W
+ +2n
Σ K<
RR W
With Lemma we can also extend Theorem 2.2 the SGD setting and get bound on Σ knn (Wa),, using similar proof. To further get bound on the cumulative population risk iien 2(W:), the key observation is that Eien (Q(W,) Q (W)) is martingale. Using mar- tingale Bernstein bound, we prove the following lemma; applying finishes the proof of Theo- rem r.14.1
Lemma 4.3. Given any 8 E (0, 1), with probability
Σ Q(W) 1 Σ Q(())) 41n (7)
5 ON SEPARABILITY
In this section we give some discussion on Assumption 2.1 the separability the NTK. The proofs are all given in Appendix D
Given a training set (i))" the linear kernel is defined as ko(z;, == (Ii, The maximum margin achievable by linear classifier is given by
To := min V vV Ko (g gEa..
(5.1)
where A,, denotes the probability simplex and @ denotes the Hadamard product. In addition the dual definition eq. (5.1). when "/o > 0 there also exists a maximum margin classifier ū which gives a primal characterization of noo holds that || 1 and y (ū, xz) To for all i.
In this paper we consider another kernel, the infinite-width NTK with respect to the first layer: (2 Wo,a) 0f Wo,a) awo
K1 (zi, xz)
E
aw.
(x:1 ( w) > 0] 1,111 [xy, w) > [0}} (ds, 0j) N
Here á and H are defined at the beginning of Section 2 Similar to the dual definition of 70- the margin given by K₃ is defined as
n min V () K1 (g gEan
(5.2)
We can also give primal characterization of " when it is positive.
Proposition 5.1. !f > 0, then there exists é E H such that [|ô]] = 1, and yi (b, di) 2 m for any 1 S i n. Additionally (|)))l < 1/71 for any z E Rd.
The proof is given in Appendix D and uses the Fenchel duality theory. Using the upper bound ||(())], < 1/71, we can see that 71 i satisfies Assumption 2.1 with 7 2 7/ However, such an upper bound [ū(z)]l < 1/71 might be too loose, which leads to bad rate. In fact, as shown later, in some cases we can construct directly which satisfies Assumption 2. with a large 7. For this reason, we choose to make Assumption 2.1 instead of assuming a positive
However, we can use 71 to show that Assumption 2.1 always holds when there are no parallel inputs. Oymak& & Soltanolkotabi (2019) Corollary I.2) prove that if for any two feature vectors z; and æj, we have I z 222 2 and [ + x2yl2 2 for some >> O. then the minimum eigenvalue of Ki at least 9/(100n 2). For arbitrary labels y E [-1,+133 since ||q O ull2 2 1/y7, we have the worst case bound of 9/100m". A direct improvement of this bound is 0/100n3, where ng denotes the number of support vectors, which could be much smaller than n with real world data.
On the other hand, given any training set {(,,, 3t)) [ which may have large margin, replacing with random labels would destroy the margin, which what should be expected.
8

---

Published as a conference paper at ICLR 2020
Proposition 5.2. Given any training set {x,, y:) if the true labels y are replaced with random labels c unif +1)%), then with probability 0.9 over the random labels, it holds that " S 1/v20m.
Although the above bounds all have a polynomial dependency on n, they hold for arbitrary random labels, and thus do not assume any relationship between the features and labels. Next we give some examples where there is strong feature-label relationship, and thus much larger margin can be proved.
5.1 THE LINEARLY SEPARABLE CASE
Suppose the data distribution is linearly separable with margin "oo there exists unit vector such that y (ū, z)) 2 To almost surely. Then we can define 8(2) == u for any 2 E IR. For almost all (xr, v), we have
y / (0(2),2) (2,,2) 0j duv((=) / (ū, x)) 1 [(,,z) > 0] duv(()
27 / 1 [(2,0) > 0] duv((z)
70
and thus Assumption 2.1 holds with 20022.
5.2
THE NOISY 2- 2-XOR DISTRIBUTION
We consider the noisy 2-XOR distribution introduced in (Wei al. 2018). bution over the following 2d points:
the uniform distri-
(I1, T2, T3. Id)
0,1
0,
-
-) ( -1
(vT= 0.1) (o.V
Vd
Vd
Vd-1
d-2
-1
x
vd
Vd -
The factor 1/va-I ensures that ||~||2 1. and x above denotes the Cartesian product. Here the label y only depends on the first two coordinates of the imput x.
To construct E, we first decompose R² into four regions:
A = (2)
21 2 0, |2 2 |22]]
A2 == {(=1, 22)
> 01 < [22]]
Ag := {(11, 22)
S 0, 2 |22]] \ ((0,0)),
A₁ = {(5) 22)
22 0,
[=2]]
Then e can de defined as follows. It only depends the first two coordinates of 2.
(1, (1,0,0,...) 0.0.0....,,0
if (21, A1,
(0,-1,0,.....
if (21, E A2,
0(2)=
(5.3)
(-1,0,0, ..... 0) if (2),22) Ag,
(0,1,0....,,)) if (21,2) E A4-
The following result shows that ((1/d). Note that n could be large 24, in which case 7 is basically O (1/ In(n)). Proposition 5.3. For any (x. y) sampled from the noisy 2-XOR distribution and any d 2 3, it holds that
/ (8(2), x) [2, > 0] dppr(=) 2 60d'
We prove two other interesting results for the noisy 2-XOR data.

---

Published as a conference paper at ICLR 2020
The width needs poly(1/7) dependency for initial separability. The first step of an NTK analysis is to show that { (Wo) 34) ji=1 is separable. Proposition 5.4 gives example where (Vo) va) D is nonseparable when the network is narrow.
Proposition 5.4. Let D = (( denote an arbitrary subset of the noisy 2-XOR dataset such that is's have the same last (d --2) 2) coordinates. For any d 2 20, if m S -/42/4, then with probability 1/2 over the random initialization of for any weights V Igmx it holds that yi (V. (Woo) S for at least one i (1,2,3,4 43.
For the noisy 2-XOR data, the separator 7 given by eq. 5.3) has margin > (11d)) and 1/7 O(d). As result, if we want { (Wo). v.) } to be separable, the width has to be (2(1/ /T). For smaller width, gradient descent might still be able to solve the problem, but beyond-NTK analysis would be needed.
A tight sample complexity upper bound for the infinite-width NTK. (Wei et al. 2018) give d² sample complexity lower bound for any NTK classifier on the noisy 2-XOR data. It turns out that could give a matching sample complexity upper bound for the NTK and SGD.
Wei al. 2018) consider the infinite- width NTK with respect to both layers. For the first layer, the infinite-widit NTK K₁ is defined in Section [ and the corresponding RKHS H and RKHS mapping e is defined Section
2
For the second layer, the infinite width NTK defined by
Of( Wa,a) af ao,a)
K2 (2;, = IE
Da
((w,,z))) The corresponding RKHS IC and inner product (wi, w2)x are given by
((w, ( (o
:= Rd + R / (=2)) duv(2) < x0) and (wi, w2)x = f (2)()22())) dpxr(().
Given any x E Rdd is mapped into the E K. where the (z) == a (z,,))) It holds that K2(2;, = WWe,, tay yr. The infinite-width NTK with respect to both layers is just K₁ + K2. The corresponding RHKS is just H x K. with the inner product
)
((v1, wi), (u2, (2)) = U2)H + w2)x-
The classifier considered in eq. (5.3) has a unit norm (i.e., || = 1) and margin y on the space H. On H. x IC, it is enough to consider (ū, 0), which also has a unit norm and margin y. Since the infinite-width NTK model a linear model H. x KC, (Ji & Telgarsky 2018 Lemma 2.5) can be used to show that SGD on the RKHS H x K. could obtain test error of e with sample complexity of Ö(1/2e). (The analysis in (Ji & Telgarsky 2018) is done in Rd,, but it still works with well-defined inner product.) Since 7 = (11dd), to achieve a constant test accuracy we need Ö(d)) samples. This mathces (up to logarithmic factors) the sample complexity lower bound of df given by Wei et al. 20188)
OPEN PROBLEMS
In this paper, we analyze gradient descent on a two-layer network in the NTK regime, where the weights stay close to the initialization. It is an interesting open question if gradient descent learns something beyond the NTK, after the iterates move far enough from the initial weights. It is also interesting to extend our analysis to other architectures, such as multi-layer networks, convolutional networks, and residual networks. Finally, in this paper we only discuss binary classification; interesting to see if it is possible to get similar results for other tasks, such regression.
ACKNOWLEDGEMENTS
The authors are grateful for support from the NSF under grant IIS- 1750051, and from NVIDIA via GPU grant.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? arXiv preprint arXiv:/905. 10337, 2019a.
Zeyuan Allen-Zhu and Yuanzhi Li. Can sgd learn recurrent neural networks with provable general- ization? arXiv preprint arXiv: /902.0090000// 19902.0002. 2019b.
Zeyuan Allen-Zhu, Yuanzhi Li. and Yingyu Liang. Learning and generalization in overparameter- ized neural networks, going beyond two layers. arXiv preprint arXiv:1811.044 0.0918 2018a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. arXiv preprint arXiv:1811.033 1.33622, 2018b.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. arXiv preprint arXiv: /8/0. /0065 2018c.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv: 2019.
Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. JMIR, 3:463-482 Nov 2002.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pp. 19-26 2011.
Jonathan M. Borwein and Qiji J. Zhu. Techniques of Variational Analysis, volume 20 of. CMS Books in Mathematics, 2005.
Yuan Cao and Quanquan Gu. Generalization error bounds of gradient descent for learning over- parameterized deep relu networks. arXiv preprint arXiv:1902.01338 2019a.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. arXiv preprint arXiv: 13210, 2019b.
Lenaic Chizat and Francis Bach, A Note on Lazy Training in Supervised Differentiable Program- ming. arXivs 81 07956722 [math. [C], 2019.
Simon Du, Jason D Lee, Haochuan Li, Liwei Wang. and Xiyu Zhai Gradient descent finds global minima of deep neural networks. arXiv preprint arXiv:1811.0330 2018a.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXi::1810.02054 2018b.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kerne:: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, pp. 8571- 8580, 2018
Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint 1rXXvv/803.003000 2018.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Neural Information Processing Systems, pp. 8157- 8166, 2018.
Percy Liang. Stanford CS229T/STAT231: Statistical Learning Theory, Apr 2016. URL https:
// /eeb tobb.staffodd. wttp:////llcc/////////////////// pdf
Atsushi Nitanda and Taiji Suzuki. Refined generalization analysis of gradient descent for over- parameterized two-layer neural networks with smooth activations on classification problems. arXiv preprint arXiv: 1905009000000 2019.

---

Published as a conference paper at ICLR 2020
Albert B.J. Novikoff. On convergence proofs perceptrons. In Proceedings of the Symposium the Mathematical Theory of Automaaa, 12:615 1962.
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterization:: global conver- gence guarantees for training shallow neural networks. arXiv preprint wuXiv:1902.044 2019.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to
Algorithms. Cambridge University Press, 2014.
Zhao Song and Xin Yang. Quadratic suffices for over-parametrization via matrix chernoff bound. arXiv preprint arXiv:1906.033300 2019.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. In Advances in neural information processing systems, pp- 2199-229999 2207, 2010.
Martin J. Wainwright. UC Berkeley Statistics 210B, Lecture Notes: Basic tail and concentration
bounds, Jan 2015. URL httptt:tt/://ttt stat. www.at/.....ellly.......//eaeeea
Chap2_ Tap BouuuddssiBouuss_..mmmmm Bounds Bowdlllouudds_aa_2 Jan22 2ttpmmds___aa22221______2
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and
optimization of neural nets vs their induced kernel. arXiv preprint arX1v:1810.05369, 2018.
Difan Zou and Quanquan Gu. An improved analysis of training over-parameterized deep neural networks. arXiv preprint arXiv:196.0044 190.19666.488, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint arXiv:1811.08895 2018.
A
OMITTED PROOFS FROM SECTION 2
Proof of Lemma 2.3 By Assumption
2.1 given any 1 13i5 n.
== (v Mi (ū(w), vi) 1 [wc, x;) > =0] 2
On the other hand,
1 m Σ y (o(wa.)) 2;)) (ws,o xi) > o|
51 (U)
the empirical mean of i.i.d. rvv's supported on [-1, with mean p. Therefore by Hoeffding's inequality, with probability 1 - 6/nn,
(1((188)
y. ( (T) - 7 v.S (0)
(U) - 11
m
Applying a union bound finishes the proof.
Proof of Lemma 2.4 Given any fixed e2 and <is n,
(Wo, c2)] =P (( Sc2) 5
2
2 V
-2:
22T
π
because (w, is standard Gaussian and the density of standard Gaussian has maximum 1/ Since (Wo e2) is the empirical mean of Bernoulli r.v.', by Hoeffding's inequality, with probability 1-6/n,
a. (W (2) 5 E 0: (Wo, (2) + V /In(n/8) 2m
2 1
In(n/8)
S V - c2
2m
Applying a union bound finishes the proof.
To prove Lemma 2.5 need the following technical result.
12

---

Published as a conference paper at ICLR 2020
Lemma A.1. Consider the random vector X (X1...., Xm)) where X, oZ,) for some + R that L-Lipschitz, and Z; are i.id. standard Gaussian rv's. Then the r.V. [| is 1-sub- Gaussian, and thus with probability 1 6.
||x||2 E [||X 22l/()))
Proof. Given a E R", define
f(a) raa)) 2 |0(a))22
where (a) is obtained by applying a coordinate-wisely to a. For any a, E R", by the triangle inequality, have
[f(a) f(b)) = =11 | (b)2 (((a)>-(b)]l22
Σ (a(as) o(bi))²
and by further using the 1- 1-Lipschitz continuity of o, have
[f(a) - f(b) S
Σ
(olas) =
Σ (a: - b,)2 = =I|a -bll2-
As result, f 1-Lipschitz continuous function w.r.t. the l norm, indeed f(X) is 1 1-sub-Gaussia Gaussian and the bound follows by Gaussian concentration (Wainwright 2015 Theorem 2.4).
Given 1 S S n, let h, a (Waz:)) /m. By Lemma A.1 | is sub- Gaussian with variance proxy 1/m, and with probability at least 1 6/2n over Wo.
Proof of Lemma 2.5
2ln(2n/))
In (2n/6)
v2 2
|hill2 - E [114]12] <
5 1
25 (2n/))/))))))
On the other hand, by Jensen's inequality,
V2
E [11all2] S
E [1l
[3]
=
2
As result, with probability - 5/2m, holds that ||Ax||2 1. By a union bound, with probability
1 6/2 over Wo. for all 1 S i S n. we have ||dil|a 1.
For any Wo such that the above event holds, and for any S i S n, the rvv. (he, a) is sub- Gaussian with variance proxy ||6.]|2 < 1. By Hoeffding's inequality, with probability 6/2n over
[h,, a>| = ( Wo. a)) s 2 (4n/8).
By a union bound, with probability - -62 over a, for all S i S n. we have (a.:Wo Wo. S
v In (4n/8).
The probability that the above events all happen is at least (1 - 6/2) - 6/2) 2 1 - 8, over Wo and
Proof of Lemma 2.6
We have
W W
l
W.
W
-2m (VR(W.), W, -W) n/ VR(WW)) (A.1)
13

---

Published as a conference paper at ICLR 2020
The first order term of eq. (A.1) can be handled using the convexity of & and homogeneity of ReLU:
vR(W)), WT W)
(u.f(WW)) ii (V..(W.),W, w. W)
(vrF((W)) (v.:(WW)- ( -vas!" (W)
n
(e(uft(wa)) - (v. (w)) R((W)- -R(1) (W)
n
(A.2)
The second-order term of eq.
A.1 be bounded follows
v VR(W,) S n @(w)) ((W)) S R.(W).
(A.3)
because Vi(W)))
- ((W)) and me. ((w) - 1, and @(W) - R(,,). Combining eqs.
A.1
to A.3 gives
n RWW) < W. W 2 - |ee1 W l F
2m R1)) (W)
Telescoping gives the other claim.
Proof of Theorem 2.2 The required width ensures that with probability - 35, Lemmas 2.3 to 2.5
hold with é: 7 and 62 = 4X/(7ymm..
Let l denote the first step such that there exists S 8 S m with [ - W waoolly > 41/(7//m) m)) Therefore for any 0 S t < f and any 1 S s S m. it holds that W.st - wr.ol12 I 4X/(Tmm)) In addition, let W = Wo XU.
We first prove that for any 0 < 1. < I, holds that R:0) (W) I e/4. Since In(1 r) for any the logistic satisfies {(2) In(1 exp(-2)) I exp(-2), and it is enough to prove that for any
S i sisn n,
34 (VI.(W)) W) In (
We will split the left hand side into three terms and control them individually:
Vi (V..W...W)) W = us (VS(W))) Wo) + s (V.(WW,) - V.((W)). + Au ( (V)(W)))
(A.4)
The first term of eq. A.4) can be controlled using Lemma 2.5
(V)(WW)) Wo) S ln
(A.5)
The second term of eq. A.4 can be written
(Vf(W))) (WW)), Wo) yt Vm ==1
Σe a, (W > 0] - [1 > 00) (ws
Let Sz = ss (1 0l 1l ( (Wssor σz> 0j 0 S s m) Note that S. implies
(ws,,, 2;) s [W -,,,, 5 Wsst Wa
11211111122 = 10... w..0l22 S 42/(7v/m) c2.
14

---

Published as a conference paper at ICLR 2020
Therefore Lemma 2.4 ensures that
S s 8 (uwar
s m
(mmm
41
+
E1
2
= m
7/mm
41
+
32
16
and thus
Mr (V)(WW)- VS((W)), Wol S
1 vm
|Scl
41
1612
x7
X
(A.6)
TVm m
72 /m
4
2
where in the last step we use the condition that m 2 4096X /70.
The third term of eq. A.4) can be bounded as follows: by Lemma 2.3
(V..WW),U)) yı (V..(Wo).T) T) + 1ı (V).(W,)) - V.((W)), 0)
21 + y (fi(W)) - V.l.Wo).TT.
In addition,
y1 (V/((W)- V.A(W)). 3) V/ m
1 m
Σ
1 [
n4) > 0/
[[ ni) > 01) (o(ws)))::))
-
|Scl 2
41
61
2
72
6
m
?
m
2
16
2
where we use m 2 40962 / Therefore,
y: (V..(W.).)) U) 27 - 61
72
61
7
22 4
2
37
(A.7)
16
2
4
Putting eqs.
(A.5) to A.7
into eq.
(A.4),
we have
A7 4n
3AT
A7
4n
4
Vi (VW.W,))........ w)
21n
2
= In
5
2
4
for the À given in the statement of Theorem R(0) (W) S e/4.
2.2
Consequently, for any 0 I t < t,, it holds that
Let T = 22 /nc. The next claim is that t 2 T. To see this, note that Lemma 2.6 ensures
Ww w/ < Wo ( 21
Σ (()) (W)
S S + c nn/
Suppose 1 < T, then we have / S 2x 2x²/ve, and thus [We. WW] 2 2x2. As result, using
| < and the definition of W,
v2x > We - W
2 We - W,U) We, - Wo. T) -
-(W W - Wo. WWo... U)
We, Wo (). )
Moreover, due to eq.
A.7)
Wn - Wo, W), -n Σ
()((W))))= = Σ Σ
- E' (v.f(W=))) vi (V.:(-))
Tsti
T<t 1=1
37 4
21 Σ Q(W-)
r<h
15

---

Published as a conference paper at ICLR 2020
As result,
"1 Σ 2(W,) 1/2+112
4X
37
Furthermore, by the triangle inequality, for any
5 m
Of: yi Dwai
||
wo.0112 -Wa,--weo01,,
Σ
Σ
L (vef((W.))
05 Swee
S Σ
e' (wnf((w))]
11 2(W+)
Vm
1
4A
1 2(W,) Vm
(A.8)
mVm
which contradicts the definition of /1. Therefore 1 2
Now we ready to prove the claims of Theorem 2.2 The bound on Wap repeating the steps in eq. (.8)) The risk guarantee follows from Lemma 2.6
w2,0112 follow by
Wo W
1
Σ R(W) KT
(0)
I =c.
c
T
1/I
T
2
2
KT
B OMITTED PROOFS FROM SECTION
The proof of Theorem 3.2 based Rademacher complexity. Given sample S (2 kn)
(where = (Ii, y))) and function class H. the Rademacher complexity of H on S is defined as
Rad (H o 5) = - -B-
sup <h(2)) heA 1=1
We will use the following general result.
Lemma B.1. SShlle--Swartz & DeviD 2014 Theorem If((2) [a, b). then with prob- ability 1 - 6,
In(2/5)
sup
ELaD [m(=)]
Σ h(z)) 1=1
2Rad (H S)+ +3b a))
AEH
2n
We also need the following contraction lemma. Consider feature sample X (II.... Fn) and a function class F on X. For each 1 < i < n, let gs R - denote a K K-Lipschitz function. Let g F denote the class of functions which map 2; to 9: (xx)) for some E F.
Lemma B.2. (Shalev-Shwartz & Ben-David KRad (Fo X).
2014
Lemma 26.9) Rad (g Fo X)
To prove Theorem 3.2
we need one more Rademacher complexity bound. Given a fixed initializa- tion (Wo, a), consider the following classes:
WP = W mnd ||l, we,ul12 for any 1 m)
16

---

Published as a conference paper at ICLR 2020
and
f= / W, W WEW)
Given feature sample X, the following Lemma controls the Rademacher complexity of F, A similar version given in (Liang) 2016 Theorem 43), and the proof is similar to the proof of (Bartlett & Mendelson 2002 Theorem 18) which also pushes the supremum through and handles each hidden unit separately.
Lemma B.3. Rad (Fp X) PVm/n.
Proof of Lemma B.3
We have
E2
sup WEW ==1
Σ
<f(r;; W,
=E.
sup
Σ
a%d (!ws 2ii)
WEW, i=1
V Vm
E,
sup v Vm WEW, a= 1=1
G000 (13)
Σ E (wug ziح)) ) ((1S)
E
sup [10-- w. o0l i=1=1
s=1
Eg
sup
Σ Gaao ((w zil)
|0.-w.o
So im1
Note that for any 1 S S the mapping + (2) is I-Lipschitz, and thus Lemma B.2 gives
m
E2
sup WEW, 1=1
Σ
(1 W,
sup
Σ Ejago (wey
m
- Sp
172
Σ
c (We,
sup
m
[w, ww--w,
Sp i=1
Invoking the Rademacher complexity of linear classifiers Lemma 26.10) then gives
Shalev--S Shnlev-Shwartz & Ben-David 2014
PVm Vn
Rad E.
Σ
Eff(e;Wad)
sup WeW,
n
Now are ready to prove the main generalization result Theorem 3.2
Proof. Fix an initialization (Wo, a). and let H. = { (x. v) + - (vf(x)) f FpJ. F any h E H. and any 2, h(z)= E [O, 1], Lemma B. ensures that with probability 1 - 8 over the data sampling,
Since for
sup kEH
EAdD [[))]]
Σ h(2.))
= sup wEW,
(Q(W)- - @(W)) s 2Rad (Ho + 3// 2n
(2
Since for each < < n, the mapping + (I'(z)) is (1/4)-Lipschitz, Lemma B.2 further
ensures that Rad (H < Rad (F, o X) /4, and thus
(o(W) -(()) < PV
ln(2/8)
sup WEW,
+ 3/
(B.1)
2
2n
17

---

Published as a conference paper at ICLR 2020
On the other hand, Theorem 2.2 ensures that under the conditions of Theorem
3.2 for any fixed
dataset, with probability - 33 over the random initialization, we have
41
$(W)) - R(())) S e, and | - wo S
TVm
B.1 with = 42/l7//), with probability 1 - 48 over the random initialization and data sampling.
As a result, invoking eq.
8 (V22nn(4n/0) + In(4/c)
2A
In(2/8)
In(2/6)
@(W)) S ((W)) +
+3
Set
+ +31
7/"
2n
v²vnn
2n
Invoking P(Zy))D (uf(:; W. a)
50) $ ( finishes the proof.
C OMITTED PROOFS FROM SECTION
Proof of Lemma 4. Recall that V&(WW)ll 1, we have
W W
We
w|6 2n (vef((W.)) (V.A(Wa))) W, - w) +1² + (e(((((()))))
(C.1)
Similar to the proof of Lemma 2.6 the first order term of eq. (C.1) can be handled using the convexity of and homogeneity ReLU follows
(w..)) yi (V)((W)) W, W) 2 RW,,., - R₁ (W),
(C.2)
and the second-order term of eq. (C.1) can be bounded as follows
1/² (e' (vef((W.)) s -nl' (Bef((Wi)) = me (vif((Wa) = (Wi),
(C.3)
since 1), -l' < and -l' < Combining eqs. C.1 to CC.3 gives
(W,) < W. - l/? W W
+ 2, (W).
Telescoping gives the claim.
With Lemma
4.2 we give the following result, which is an extension of Theorem 2.2 to the SGD)
setting.
Lemma C.1. Under Assumption 3.1 given any e E (0, any 8 E 1/3), and any positive integer no. let
(m + In(4/e)
and M == 4096X2
A
7/4
76
For any m 2 M and any constant step size 7 & 1, if no 2 n = [2x²/mel. then with probability 1 36,
(WW) Sc.
KKn
Proof. We first sample data examples (æo. vo).
(Zna- Bng-1), and then feed (It, ys) to
SGD at step i. We only consider the first ng steps.
The proof is similar to the proof of Theorem 2.2
Let denote the first step before no such that > 42/(7//m. If such step does not exist, let
there exists some < s < m with W,,,, wxo 2
M1 n2.
Let W Wo XU, in exactly the same way as in Theorem 2.2 we can show that with probability
1 - 36, for any < i < n1.
W) In ( and thus R, (w) S c/4.
y4
18

---

Published as a conference paper at ICLR 2020
Now consider [2x Using Lemma 4.2 in the same way as the proof of Theorem 2.2 (replacing ((W)) with (W;), etc.), we can show that n I n1. Then invoking Lemma 4.2 again, we get
Wo W
Σ 2.())) R.((W.) KR
E Kn
(W)
6 6 S +
2
2
Next prove Lemma 4.3
We need the following martingale Bernstein bound.
Lemma C.2. (Beygelzimer et al. 2017 Theorem Let (M,.Fi)e denote a martingale with Mo O and Fo be the trivial a-algebra. Let (At)121 denote the corresponding martingale difference sequence, and let
V1
ΣB j=1
E
A
denote the sequence of conditional variance. If Ar S Raas, then for any E (0, 1), with probability least ô,
Mr S (e 2) + Rln
R
For any i 2 0, let 2; denote (xz M.). and 20, denote (2o...., 21). Note that the quantity Eisi (Q(,)) - (W,) is a martingale w.rt. the filtration (20,4-1). The martingale difference sequence is given by 2(W:) - (,WW),, which satisfies
Proof of Lemma 4.3
Q(W)) Qw,,, ((aa)DD
(uf(a; (e, E' (u.f(rs (,,)) s
(C.4)
since -1 -1 0. Moreover, we have
E (e(w)) - o.(w:)) (((00)) (((w))- Q(Wi)² 2Q(W,) O (W:) (( + IE [el(wa))
Q(w)) + (w)) ( (020,)-1))
(C.5)
E (W.) ((
E Q.(W)) (
e(W))
Invoking Lemma C.2 with eqs.
CC44
and CC.5
gives that with probability 1 - 5,
(Q(W,) 2. S (e -2 Σ
Q(W))
In
8
Consequently,
2(W)) < <4 e. 4In (1)
Q.W)))
Finally, we prove Theorem 4.1
Proof of Theorem 4.7 Suppose the condition of Lemma C.1
holds. Then we have for [2>2/ /nc]
with probability 36,
1
Σ (WWW) S
19

---

Published as a conference paper at ICLR 2020
Further invoking Lemma 4.3 gives that with probability - 45,
+ 4 In (3) 5e.
ΣΣ Q(w)) S
Σ
i<n
i<n
Since PlaanDD (v)(2; W, a) 00) x W we get
Plas)DD (us(z; W,, 50) S 10e.
1=1
For the condition of Lemma C.1 to hold, is enough to let
no = - In( In(1/5)
?7?62
which gives
[n(1/6) + +In(1/e)2
[ln(1/6) [m((1/))2
M +
and n O
78
72c
D OMITTED PROOFS FROM SECTION 5
Proof of Proposition 5.7 Define f: H. R
f(w) 2 dww(2))))wr(() dur(z) /
It holds that f is continuous, and f* has the same form. Define g R2 - IR by
g(p) == max Po: Isisn
with conjugate
(²()) 0, E
+00, O.W.
Finally, define the linear mapping A H + R" by (Aw); ys (w, 0i)
Since f. f², g and g are lower semi-continuous, and dom Adom! ff f= R", and dom f A" A'dommg g" = H. Fenchel duality may be applied in each direction (Borwein & Zhu 4.4.3), and ensures that
2005
Theorem
inf (f(w) + g(Aw)) sup --' GER"
WEH
with optimal primal-dual solutions (w, q). Moreover
inf (f(w) + 9(Aw)) weH
inf sup (f(w) g(Aw + u) + (q. u))
wER GER"
2 sup inf (f(w) + g(A + +2) + (g. u))
gERn NERN
((f(w) (A' (A'q, w)) N + (g(Aw + w) - 1-q, Aw =)))
sup inf
qER" WER,
sup (Af* - (-4))
gER"
By strong duality, the inequality holds with equality. It follows that
" = A and supp(-d) C arg max (Aw). 13i5n
20

---

Published as a conference paper at ICLR 2020
Now let us look at the dual optimization problem. is clear that
sup ( (~ g-(-)) = inf (A*r)) qERR
gEa..
In addition, we have
1 _
/
((
Σ (x)
duz(2)
Piggbays (0i(2), (z())) duw(=)
2
1
9:9;00y / (o.(2)) dpr(z)
2
1,==1
9..,,,jKK (i,j)) - ( (
2
JJ=1
and thus ('(Aa) = -2//2. Since v = A A.q, we have that |100 = n. In addition,
s(Aw) = f (A* - / (w) = -
and thus - has margin 7.. Moreover, we have
2
w(2) (V) Σ q.ya; (2, x3) > 0]:
and thus | S 1. Therefore, 0 = // / satisfies all requirements of Proposition 5.1
Proof of Proposition 5.2 Let á denote the uniform probability vector 1/n). Note that
E (w-n)(((-11,+1)))) (0))) K, (9
E
Somnif((-1,+11))
Σ 2
n Ge, Ki Ki
E
n²
i,/=1
1
1
K1 (ai, (z),, =
n
2n
Ki ( () < 1 for any c, by Markov's inequality with probability 0.9, it holds that (0 Ki ( 1 < 1/(2n)) and thus 71 S 1/v220n.
Since 0 < (q O c)
Proof of Proposition
5.3 By symmetry, we only need to consider an (z, v) where (01, 02, v) 2p.q denote (Ep, Ept1..... 2g). and similarly define xp.g. We have
(4/ 0, 1). Let
v ʃ (M(:), ((,,)) > 0] du)(=)
=y / (1 (0())) (2, > of dur(essa) dpvr(e1,2)
(D.1)
= / (0(2)22.113) ( (212, + (23.) of dprressa) ) duv(e12)
(D.2)
Σv v / (o(e)e))))) (f [1( + (23,d > of duv(esa)) [21,2 As] duw((12))
(D.3)
21

---

Published as a conference paper at ICLR 2020
where eq. (D.1) is due to the independence between 21,2 and 23,d, and in eq. D.2) use the fact that (2))1. only depends on 21,2 and 8(2)3,d all zero. Since (3(2)1,2, 0 for 21, A2 U. only need consider A1 and A3 in eq. (D.3). For simplicity, will denote 21,2 by p R?, and 12)1,22 by B(p), and 23,a by q R
For any nonzero p E A1, we have - Ag, and (6(p), 1/vd-11 Therefore
(/1 [1, + (3.)) > 0/ dyur(a)
y ((())..1.2
( (-p, 01.2) (-
+ (0(
+ (g. 23,1) > of durr(a)
/
Pi
+ (9.23,1) >
-PI
+ (g. =0 o1) duvli)
Vd
vd d
vdd1
1
P1
S (g,
P1
(D.4)
Vd-1
Vd-1
Vd vd-1
Let &p denote the density function of the standard Gaussian distribution, and for c > 0, let U(c) denote the probability that a standard Gaussian random variable lies in the interval [-c, c]:
((e) [ p(t) dt.
Since (q. 23,0) is Gaussian variable with standard deviation / (d-2)/(d-11), have
P
Vd PP1 P1 < (g.
(3,2
S
P1
= U
P1 Vid
(D.5)
Vd
Vd-1
Plugging eqs. (D44 and (..) into eq.
D.3 gives:
(o(=),x)) / (V(())))) 11 (2, x) > 0] ddv((=)
U
P1
1
lp E Aij
Vd
Vdl
(1 x(12) dp2 p(p)) dp
00
P1
U
Vd-2
2
00
U
P1
U(pi)<(pi) dpi
J
Vid
2
1
U
P1
U(p))((p)) dp1-
2
d
For t E it holds that s0t) 2 1 2Te, and thus
U(a) = =5" p(t) 2
2a
2Te
Therefore eq.
DD3) is lower bounded by
U
P1
U(p))p(p))pp dp1
2
P1
2p1
dpi
J
2
vd -
Ju
2
Vd-2
V2re
ViTe
2
pi dpi
20 1)(d 2)
Jo
60 60 (d - 1) - 2)
1
60d
22

---

Published as a conference paper at ICLR 2020
To prove Proposition 5.4 need the following technical lemma.
Lemma D.1. Given 21 NO 1) and 22 (0,0 b2) that are independent where > we have
P ([21 < 222) b"
Proof.
First note that for 23 ~ [O 1) which is independent of 21.
1
P (12l < |2] )) = (|21| b/23l) = P |2sl <
b
Still let yp denote the density of (0, 1). and let (c)) denote the probability that 23 (-c, We have
p
|2al
7 |
/
1
z2l < blai| ((=a)p((z) daa dzi
U
(0(1) d21
- bxb /
2 < b' xb
(2110(21) dz1 =
where we use the facts that U(c) 20/ v 2 and B[|=||] V2/T.
We now give the proof of Proposition 5.4 using Lemma
D.I
Proof of Proposition 5.4 By symmetry, we only need to consider the following training set:
1/1 = 1, T2 (0, 1, ,,....11). 1), 1/2 -1, T3 = (-1, 0, ........11
(1,0, 1 1). 1),
1), V/ = 1,
F4 (0. 11,1, 1,......1 1), y/4
The 1/vd - factor is omitted also because we only discuss the 0/1 loss.
For any 8, let A. denote the event that
1 (1) > 0|
[w., T2) > = 1 (w., va) > 0| = 1 (w., x.) > 0].
We will show that if < vd - 2/4, then A, is true for all 1 with probability 1/2, and Proposition 5.4 follows from the fact that the XOR data is not linearly separable.
For any and i,
(w) (w.)((x.)))
+ (wo)2(z))2
(ws)..
J=3
Since ((=))) is (1,0) or (0, 1) or (-1,0) or (0. - 1), event A, will happen as long as
d
(wa) <
Σ (ws)s v and (ww.22 <
Σ e=3
(ws)
1=3
Note that (w=)1, (wa)2 NO0 1) while Ej NN d.0.d-20 2). As a result, due Lemma D.I
d
d
P
[(w)]]
<
Σ (ws))
=P |[wua)a| <
Σ x=3
(w)))
>
Vd 2
1=3
Using a union bound, P(A.) > 1 - 2/
V/V2-2 Ifm 5 /dd 2/4, then by a union bound again,
P
U A
>1
2
m
vd 1
Vd-2 -
2
Vd-2 2
4
2
15e5m
23


Reviews:
[{"review_id": "rkgnCl8MKS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary and Decision \n\nThe authors of this paper studied the optimization and generalization properties of shallow ReLU networks. In particular, the authors were able to show a width dependence that is polylogarithmic on the number of samples, probability or failure, error tolerance, and a margin parameter. This work is unique in that the authors showed how to bound many key quantities in terms of the margin parameter, and drew a connection with the neural tangent kernel's maximum margin. Furthermore, the overall reading experience was very smooth, although I do have some minor comments later. \n\nThe main concern from me is on the implicit dependence of the margin parameter \\gamma, most notably this can lead to the width dependence to be polynomial in terms of the number of samples and the minimum separation distance. While this concern warrants a careful discussion (below), I believe the paper still offers a nice analysis of shallow networks. \n\nOverall, I would recommend accept for this paper. \n\n\nBackground \n\nThere has been a large number of works studying very wide networks, showing both optimization and generalization results. While there has been great progress, most of these existing results require the width of both deep (and shallow) networks to be very large. For example, even by being polynomial in the number of samples, the networks are already unrealizable in practice. Therefore, guarantees with much better dependence is highly desirable. \n\n\nDiscussion of Contributions\n\nAs the title may suggest, it is a bit surprising that we can show that polylog width is sufficient. Intuitively, we can imagine that the classification margin can grow exponentially more complex as the number of samples increase. I believe the nice result can be attributed to a careful analysis of key quantities such as \\| W_t - W_0 \\|_F in terms of the margin parameter from Assumption 2.1. \n\nSome nice examples of the analysis in this paper include the introduction of the weight matrix \\overline{U} and \\overline{W} as an intermediate between W_0 and W_t, and observing that the activations of the ReLU \\xi_{i,t} do not change very much during training. The tricks together led to a very tight bound on the change in weights \\| W_t - W_0 \\|_F in terms of the margin parameter \\gamma. As the authors mentioned on page 6, this tight control was used to bound the Rademacher complexity later. \n\nThe connection drawn between the margin assumption and neural tangent kernel (Proposition 5.1) is also interesting on its own. The authors intended this result to serve as a justification of the margin assumption (2.1). \n\n\nDiscussion of the Margin Parameter\n\nLet me start by saying I'm not completely certain on how to interpret this margin parameter \\gamma in Assumption 2.1. Perhaps I'm missing some obvious ideas here, but I would still like the authors respond with some more details. At the same time, I don't believe this is a sufficient criticism to reject this paper, as I believe the analysis in terms of \\gamma is still valuable. \n\nOn one hand, if we were to assume the margin condition holds for all possible data points (i.e. Assumption 3.1), then there is no concern about polynomial dependence on the number of samples, and this is certainly a reasonable assumption in some applications. \n\nOn the other hand, many of the previous analysis on wide networks were in terms of a minimum separation distance, i.e. assume there exists a \\delta > 0 such that for all i \\neq j, we have \n\t\\| x_i - x_j \\| \\geq \\delta . \nThe authors have provided a discussion in section 5, including both a worst case bound of \n\t\\gamma \\geq \\delta / (100 n^2),\nby Oymak and Soltanokotabi (2019) and an example where the margin is O( n^{-1/2} ) with high probability. \n\nUsing either bounds on \\gamma, we will have a width with polynomial dependence in terms of the number of samples and minimum separation distance. Therefore if we were to compare against previous works in the same benchmark, i.e. using a minimum separation assumption instead, then arguably this work did not achieve a width that is only polylog in terms of the number of samples. \n\nThat being said, I don't believe the authors were intentionally trying to hide sample dependence inside an assumption. The paper is presented in a very transparent way, and the authors were being honest in chapter 5 about the worst case dependence on the number of samples. \n\nTo summarize, it is unclear to me whether the paper truly achieved a width dependence that is polylog in terms of the number of samples, but the analysis in terms of \\gamma remains a valuable contribution. I welcome the authors and the other reviewers to provide additional comments on whether the title and claims of this paper is appropriate. \n\n\nMinor Comments \n\nFor the sake of improving readability, I also have some minor comments that do not contribute towards the decision. \n\n - On page 5, the first observation bullet point in section 2.2, it is written here that by triangle inequality \n     \\| \\nabla \\widehat{R}(W) \\|_F \\leq \\widehat{Q}(W) , \n    I thought you needed an absolute value on the right hand side, perhaps you should mention that \\ell is strictly decreasing. \n\n - On page 6, in the statement of Corollary 3.3, you are missing \\eta \\leq 1, and perhaps the \\tilde on \\Omega and O should be defined. \n - On the same note, while it is obvious that Theorem 3.2 implies this corollary, it is still worth writing up a proof to compute the constants. \n\n - On page 7, the notation \\Delta_n and \\odot are not defined, I had to infer definition from the proof. \n\n - On page 12, just below the second equation, it wasn't immediately clear how \\widehat{R}( \\overline{W} ) \\leq \\epsilon / 4. I believe it's worth expanding the definitions a bit, and explicitly plug in Lemma 2.5. \n\n - On page 12, in the second last equation, I'm actually not sure where this inequality comes from \n      \\| W_t - \\overline{W} \\|_F \\geq \\langle W_t - \\overline {W} , \\overline{U} \\rangle\n    Perhaps it's obvious, but I currently don't see it. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "HyeBXPOpFr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the author shows that for a two-layer ReLU network,  it only requires a network width that is poly-logarithmic in the sample size n to get good optimization and generalization error bounds, which is better than prior results. \n\nOverall, the paper is well written and easy to follow. However I still have some questions about this paper.\n\nOne of my major concerns is that there might be an important error in the proof of the main theorem. Specifically, in the proof of Theorem 2.2 (page 12), it says that due to lemma 2.5, $\\hat R^{(t)}(\\bar W)\\leq \\varepsilon$. However, Lemma 2.5 only shows that $|f(x_i,W_0,a)|$ is small, and the reason $\\hat R^{(t)}(\\bar W)$ can also be small is not explained in this paper at all. Based on Lemma 2.5, I can roughly get that $\\hat R^{(0)}(\\bar W) $ can be small, but the reason why $\\hat R^{(0)}(\\bar W) $ is small is unclear to me, especially when the network width m is only polylogarithmic in n and \\varepsilon. Without a clear explanation on this issue, the theoretical results in this paper might be flawed, and the polylog claim might not be correct.\n\nMoreover, this paper does not provide sufficient comparison with existing work. For example, Assumption 2.1 looks very similar to the assumption made in Cao & Gu (2019a). The definition of $\\hat Q(W)$ has also been introduced in Cao & Gu (2019a). However these similarities are not mentioned in the paper at all. Moreover, the result of Lemma 2.6, which is also one of the selling points of this paper, is actually very similar to Fact D.4 and Claim D.6 in the following paper:\nAllen-Zhu, Zeyuan, and Yuanzhi Li. \"What Can ResNet Learn Efficiently, Going Beyond Kernels?.\" arXiv preprint arXiv:1905.10337 (2019).\n\nFinally, the authors’ claim in the title that the width of the network is poly-logarithmic with the sample size n might be misleading. In fact, in Section 5, it has been discussed that in certain settings about the data distribution, $\\frac 1\\gamma$ is polynomial of n. However, the width is polynomial with $\\frac 1\\gamma$, which means the width is poly of n in these settings. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Bkgha_aM9r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary :\n1. Classification task with shallow Relu and logistic loss.\n2. Showing fast global convergence rate with polylog width for both training and generalization error under appropriate assumptions\n\nOverall, this paper is very exciting and surprising. At some point, I was trying to prove such results, but couldn’t get it. This paper should be accepted as an oral presentation in ICLR. If the authors can address some of the questions in the comments, I will be happy to increase the score.\n\nAdvantages:\n1. Better results for classification task with shallow Relu in terms of global convergence rate and network width\n2. Showing the essence of the power of over-parameterization that the weights don’t change much\n3. Clear logic and proof\n4. Also discuss the stochastic GD/generalization error? (I didn’t read that part)\n\n\n\nDisadvantages:\n1.Bug in proving Theorem 2.2, a larger lambda is needed (but won’t influence the polylog result). See the below for a fix.\n2.In the proving sketch, why ||W_t-W_0||_F=O(ln t)? In the proof, it looks like ||W_t-W_0||^2_F=O(t), as in the third equation on page 12. More explanation about proof sketch is needed.\n3.Typo\na.The \\odot operation in Equation 5.1 is not defined. According to later computation, this operation seems to be the hadamard product between two vectors. But this notation is not widely used and some brief introduction will be benefinitial.\nb.On page 1, “… and standard Rademacher tools but exploiting how little the….”, “but” seems to be a typo.\nc.On page 2, “also suffices via a smoothness-based generalization bound”, “suffices” should be “suffice”.\nd.Last formula in page 11 missing a “>0” in the indicator function.\n4.(optional) why using ||W_t-W_0||_F instead of ||w_r(t)-w_r(0)||_2, which used in previous work for square loss, for the analysis? Is there any benefit or restriction here? \n5.(optional) Give more insights about intermediate quantities such as \\hat R^(t), \\bar{W}, etc.\n\nComments:\n1. More arguments for polylog width in last section needed. E.g., give a specific case where the gamma in Assumption 2.1 is constant, or comparable to the smallest eigenvalue of NTK; otherwise in the worst case, gamma can be as bad as  the smallest eigenvalue of NTK over n, which ruins the polylog results. To be more specific, we can always set q to be the uniform distribution over [n], then \\|q\\odot y\\|_2 is indeed 1/\\sqrt{n}, hence \\gamma_1\\leq \\sqrt{\\lambda_{max}(K_1)/n}. If K_1 has constant spectral norm(which is the case if all the data points are orthogonal to each other), then \\gamma_1 will depend on 1/n.\n2. For the over-parameterization theory, more references are needed. https://arxiv.org/abs/1902.01028 [Allen-Zhu, Li] is about generalization bound for the over-parametrized networks, https://arxiv.org/abs/1810.12065 [Allen-Zhu, Li, Song] and https://arxiv.org/abs/1905.10337 [Allen-Zhu, Li] are about the over-parameterization bound for more than two-layer networks. https://arxiv.org/abs/1906.03593 [Song, Yang] obtains a better width bound for two-layer neural networks under the framework of https://arxiv.org/abs/1810.02054 [Du, Zhai, Poczos, Singh].\n3. Theorem 2.2 shows that the average loss converges. Does this imply after training for T steps, we obtain good weights with small logistic loss? Can you get results showing the loss is decaying, like Theorem 4.1 in https://arxiv.org/abs/1810.02054 [Du, Zhai, Poczos, Singh]?\n4. On page 8, the lower bound of \\lambda_0 is given as \\delta/n^2. Is this bound tight? Is this lower bound achievable? \n5. Under what assumptions can we prove o(log n), say poly(log log n) width?\n6. What is the role of logistic loss in the proof? In general, if we replace logistic loss with square loss, will this make it harder to train neural networks?\n\n\nThe original analysis might has some flaw/bug:\n\nIn the proof of Theorem 2.2, top of page 12, to show \\hat R^{(t)}(\\bar W)<= \\epsilon/4, the term y_i <\\nabla f_i (W_t) - \\nabla f_i (W_0) , W_0> seems to be forgotten to consider.\n\nThis could be a fix.\n\nNote that above term equals y_i/m \\sum_{r=1}^m ( 1_{[< w_{r, t}, x_i> >= 0]} - 1_{[< w_{r, 0}, x_i> >= 0]} ) < w_{r, 0}, x_i >. We can use concentration to bound <w_{r, 0}, x_i>, such that with high probability, it will be no larger than polylog(n). Correspondingly, we know this term won’t be too small. Adding this extra polylog factor into lambda, we can fix the proof.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies how much overparameterization is required to achieve zero training error via gradient descent in one hidden layer neural nets. In particular the paper studies the effect of margin in data on the required amount of overparameterization. While the paper does not improve in the worse case in the presence of margin the paper shows that sometimes even logarithmic width is sufficient. The reviewers all seem to agree that this is a nice paper but had a few mostly technical concerns. These concerns were sufficiently addressed in the response. Based on my own reading I also find the paper to be interesting, well written with clever proofs. So I recommend acceptance. I would like to make a suggestion that the authors do clarify in the abstract intro that this improvement can not be achieved in the worst case as a shallow reading of the manuscript may cause some confusion (that logarithmic width suffices in general).
Decision: Accept (Poster)