How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
Authors: Zixiang Chen
Yuan Cao
Difan Zou
Quanquan Gu
Venue: ICLR 2021 Poster (2021)
Keywords: deep ReLU networks
neural tangent kernel
(stochastic) gradient descent
generalization error
classification

Abstract: A recent line of research on deep learning focuses on the extremely over-parameterized setting, and shows that when the network width is larger than a high degree polynomial of the training sample size $n$ and the inverse of the target error $\epsilon^{-1}$, deep neural networks learned by (stochastic) gradient descent enjoy nice optimization and generalization guarantees. Very recently, it is shown that under certain margin assumptions on the training data, a polylogarithmic width condition suffices for two-layer ReLU networks to converge and generalize (Ji and Telgarsky, 2020). However, whether deep neural networks can be learned with such a mild over-parameterization is still an open question. In this work, we answer this question affirmatively and establish sharper learning guarantees for deep ReLU networks trained by (stochastic) gradient descent. In specific, under certain assumptions made in previous work, our optimization and generalization guarantees hold with network width polylogarithmic in $n$ and $\epsilon^{-1}$. Our results push the study of over-parameterized deep neural networks towards more practical settings.

Published as a conference paper at ICLR 2021
How MUCH OVER-PARAMETERIIZATOO Is SUFFI- CIENT TO LEARN DEEP RELU NETWORKS?
Zixiang Chen Yuan Cao'; Difan Zou Quanquan Gu
DDepartment of Computer Science, University of California, Los Angles (chenzx19 9, yuancao, knowzou, qgu (cs. www.ucllle...ooo..o edu
ABSTRACT
A recent line of research on deep learning focuses on the extremely over- parameterized setting, and shows that when the network width is larger than high degree polynomial of the training sample size n and the inverse of the target error e-1, deep neural networks learned by (stochastic) gradient descent enjoy nice optimization and generalization guarantees. Very recently, it is shown that under certain margin assumptions on the training data, a polylogarithmic width condition suffices for two-layer ReLU networks to converge and generalize (Ji and Telgarsky, 2020). However, whether deep neural networks can be learned with such a mild over-parameeterizatoon still open question. In this work, we answer this question affirmatively and establish sharper learning guarantees for deep ReLU networks trained by (stochastic) gradient descent. specific, under certain assumptions made in previous work, our optimization and generalization guarantees hold with network width polylogarithmic in n and - Our results push the study of over-parameterized deep neural networks towards more practical settings.
INTRODUCTION
Deep neural networks have become one of the most important and prevalent machine learning models due to their remarkable power in many real-world applications. However, the success of deep learning has not been well-explained in theory. It remains mysterious why standard optimization algorithms tend to find globally optimal solution, despite the highly non-convex landscape of the training loss function. Moreover, despite the extremely large amount of parameters, deep neural networks rarely over-fit, and can often generalize well to unseen data and achieve good test accuracy. Understanding these mysterious phenomena on the optimization and generalization of deep neural networks is one of the most fundamental problems in deep learning theory.
Recent breakthroughs have shed light on the optimization and generalization of deep neural networks (DNNs) under the over-pan parameterized setting, where the hidden layer width is extremely large (much larger than the number of training examples). It has been shown that with the standard random initialization, the training of peeettaramttri deep neural networks can be characterized by kernel function called neural tangent kernel (NTK) (Jacot et al., 2018; Arora et al., 2019b). In the neural tangent kernel regime (or lazy training regime (Chizat et al., 2019)), the neural network function behaves similarly as its first-order Taylor expansion at initialization (Jacot et al., 2018; Lee et al., 2019; Arora et al., 2019b; Cao and Gu, 2019), which enables feasible optimization and generalization analysis. In terms of optimization, a line of work (Du et al., 2019b; Allen-Zhr et al., 2019b; Zou al., 2019; Zou and Gu, 2019) proved that for sufficiently wide neural networks, (stochastic) gradient descent (GD/SGD) can successfully find a global optimum of the training loss function. For generalization. Allen-Zhu et (2019a): Arora et al. (2019a); Cao and Gu (2019) established generalization bounds of neural networks trained with (stochastic) gradient descent, and showed that the neural networks can learn target functions in certain reproducing kernel Hilbert space (RKHS) or the corresponding random feature function class.
Although existing results in the neural tangent kernel regime have provided important insights into the learning of deep neural networks, they require the neural network to be extremely wide.
Equul contribution.

---

Published as a conference paper at ICLR 2021
The typical requirement the network width is high degree polynomial of the training sample size n and the inverse of the target eтrоr e='. As there still remains a huge gap between such network width requirement and the practice, many attempts have been made to improve the over- parameterization condition under various conditions on the training data and model initialization (Oymak and Soltanolkotabi, 2019; Zou and Gu, 2019; Kawaguchi and Huang. 2019; Bai and Lee, 2019). For two-layer ReLU networks, a recent work (Ji and Telgarsky, 2020) showed that when the training data are well separated, polylogarithmic width is sufficient to guarantee good optimization and generalization performances. However, their results cannot be extended to deep ReLU networks since their proof technique largely relies on the fact that the network model is 1-homogeneous, which cannot be satisfied by DNNs. Therefore, whether deep neural networks can be learned with such mild vverpaarameterizationn is still an open problem.
In this paper, we resolve this open problem by showing that polylogarithnic network width is sufficient to learn DNNs. In particular, unlike the existing works that require the DNNs to behave very close to linear model (up some small approximation error), we show that a constant linear approximation error is sufficient to establish nice optimization and generalization guarantees for DNNs. Thanks to the relaxed requirement the linear approximation eтror, milder condition on the network width and tighter bounds on the convergence rate and generalization error can be proved. We summarize our contributions follows:
We establish the global convergence guarantee of GD for training deep ReLU networks based on the so-called NTRF function class (Cao and Gu, 2019), set of linear functions over random features. Specifically, we prove that GD can learn deep ReLU networks with width m poly(F) to compete with the best function in NTRF function class, where the radius of the NTRF function class.
We also establish the generalization guarantees for both GD and SGD in the same setting. Specifi- cally, we prove a diminishing statistical error for a wide range of network width m E ($(1), oo). while most of the previous generalization bounds in the NTK regime only works in the setting where the network width in is much greater than the sample size n. Moreover, we establish Ö( O(--)) Ö(-11) sample complexities for GD and SGD respectively, which are tighter than existing bounds for learning deep ReLU networks (Cao and Gu, 2019), and match the best results when reduced to the two-layer cases (Arora et al., 2019b; Ji and Telgarsky, 2020).
We further generalize our theoretical analysis to the scenarios with different data separability assumptions in the literature. We show a large fraction of the training data are well separated, the best function in the NTRF function class with radius R - Õ(1) can learn the training data with error up This together with our optimization and generalization guarantees immediately suggests that deep ReLU networks can be learned with network width m (i(1), which has a logarithmic dependence on the target error e and sample size n. Compared with existing results (Cao and Gu, 2020; Ji and Telgarsky, 2020) which require all training data points to be separated in the NTK regime, our result is stronger since it allows the NTRF function class to misclassify small proportion of the training data.
For the ease of comparison, summarize our results along with the most related previous results in Table I, in terms of data assumption, the over- paeepaarttttiiziaoonnn condition and sample complexity. It can be seen that under data separation assumption (See Sections 4.1, 4.2), our result improves existing results for learning deep neural networks by only requiring a polylog (n,, -1) network width.
Notation. For two scalars and b, we denote a to denote its Euclidean norm. For a matrix X, we use |X|| and | [ to denote its spectral norm and Frobenius norm respectively, and denote by X., the entry of X at the i-th row and j-th column. Given two matrices X and Y with the same dimension, we denote (X, Y) Σ,g X.x Y iz.
min(a, b). For a vector E Rd use |x|
Given a collection of matrices W- IW,.... Wr) E , D+__, xm/ and a function f(W) over 0f_ mh xmi, we define by ww (W) the partial gradient of f(W) with respect to W. and denote Vw Vw (W) = [W)) We also denote B W -) = { [W' maxieee] || - Wi] & r} (Ap.... A,). B = (B,...., ,B,), we denote
for T > 0. For two collection of matrices A
A, B) Σi_ A, B,) and 1 Σ
A P-
2

---

Published as a conference paper at ICLR 2021
Table 1: Comparison of neural network learning results in terms of over par-pammrmteezaoionn condition and sample complexity. Here is the target error rate, n is the sample size, is the network depth.
Assumptions
Algorithm
Over-para, Condition
Sample Complexity
Network
Zou et al. (2019)
Duta nondegeneration
GD
""""" +c-1))
Deep
This paper
Data nondegeneration
GD
(1)
Deep
Cao and Gu (2020)
Data separation
Ö " OLL)
Deep
Telgarkky (2020)
Data separation
polylog(n;e
Ö(r 2)
Shallow
This paper
Data separation
polylog(n; (, [oloy((
O(e O(L)
Deep
Cao and Gu (2019)
sepuration
(2(e"11) (oly(L)
O(e ppul((L)
Deep
Telgansky (2020)
sepuration
polylog(c
O(c-1)
Shallow
This paper
Data separation
SGD
polylog(e Poly(L)
O -ployyL)
polly())
Deep
Algorithm 1 Gradient descent with random initialization
Input: Number of iterations T, step size 7,, training set ((x,,)() fort= 1,2, T do
Mo) initialization W
Update ((t) = w(t - VwLs(W((-1)
end for Output: W W(T)
Given two sequences { and [ya). we denote T.p = O(ya) if [ | & Cilyna for some absolute positive constant C1, In (y(n)) if |z,|| > C2lgnl for some absolute positive constant C2. and In = (yy.) if Ca/unl < |xxl & Calynal for some absolute constants C3, C4 > O. We also use Ö-), ((-) to hide logarithmic factors in (-)) and (2(-) respectively. Additionally, we denote In = poly(yn) if TT = Oly for some positive constant D, and In polylog(y,) if x,, poly(log(y.)).
PRELIMINARIES ON LEARNING NEURAL NETWORKS
In this section, we introduce the problem setting in this paper, including definitions of the neural network and loss functions, and the training algorithms, i.c., GD and SGD with random initialization.
Neural network function. Given input x Rd, the output of deep fully-connected ReLU network is defined as follows,
fw(x) = m m ///l//Wro 1o Wo L-11 ... ..........WW.................... o.. ...,,
where W1 E R W....., WL-1 E R WL E R xm and o oxx) max x) is the ReLU activation function. Here, without loss of generality, we assume the width of each layer is equal to m. Yet our theoretical results can be easily generalized to the setting with unequal width layers, long as the smallest width satisfies our overparameterizztion condition. We denote the collection of all weight matrices as W ( W
Loss function. Given training dataset (xi, 31 w-i.. with input x; E Rd and output E (-1,+13,
we define the training loss function as
(s( = 1 Σ L(W),,
where (.W) (x.)f(xx)) log (1 exp(=xf/(xx))) is defined as the cross-entropy loss.
Algorithms. We consider both GD and SGD with Gaussian random initialization. These two algo-
rithms are displayed in Algorithms and 2 respectively. Specifically, the entries in ( ..., w(O) L-1
generated independently from univariate Gaussian distribution N (0, 2/m) and the entries in W L are generated independently from N (0, 1/m). For GD, we consider using the full gradient to update the model parameters. For SGD, we use new training data point in each iteration.
Note that our initialization method in Algorithms 1, 2 is the same as the widely used He initialization (He et al., 2015). Our neural network parameterization is also consistent with the parameterization used in prior work on NTK (Jacot et al., 2018; Allen-Zhu et al., 2019b; Du et al., 2019a: Arora et al., 2019h 9b; Cao and Gu, 2019).
3

---

Published as a conference paper at ICLR 2021
Algorithm 2 Stochastic gradient desecent (SGD) with random initialization
Input: Number of iterations step size initialization W
for i = ..2,...,* do
Draw (x,, 3/6) from DD and compute the corresponding gradient Vw (W(i-)).
Update W w 1 VwL((W(--))
end for
Output: Randomly choose W uniformly from (W W(n-1).
MAIN THEORY
In this section, we present the optimization and generalization guarantees of GD and SGD for learning deep ReLU networks. We first make the following assumption on the training data points. Assumption 3.1. All training data points satisfy ||x;|22 1, ,,
This assumption has been widely made in many previous works (Allen-Zhu et al., 2019b;e; Du et al., ab;a;; Zou et al., 2019) in order to simplify the theoretical analysis. This assumption can be relaxed to be upper bounded and lower bounded by some constant.
In the following, give the definition of Neural Tangent Random Feature (NTRF) (Cao and Gu, 2019), which characterizes the functions learnable by weerpparaettrrzzed ReLU networks.
Definition 3.2 (Neural Tangent Random Feature, (Cao and Gu, 2019)). Let ( be the initialization weights, and Fwio w (x) fwie (x) + (W (x), W W(0)) be function with respect to the input x. Then the NTRF function class is defined as follows
F(W(O) R) = (Fwo, W E ((W()), R m m//2))
The function class Fwio, w (x) consists of linear models over random features defined based on the network gradients at the initialization. Therefore it captures the key "almost linear" property of wide neural networks in the NTK regime (Lee et al., 2019; Cao and Gu, 2019). In this paper, use the NTRF function class as a reference class to measure the difficulty of a learning problem. In what follows, deliver our main theoretical results regarding the optimization and generalization guarantees of learning deep ReLU networks. We study both GD and SGD with random initialization (presented in Algorithms and 2).
3.1 GRADIENT DESCENT
The following theorem establishes the optimization guarantee of GD for training deep ReLU networks for binary classification.
Theorem 3.3. For 8, R > 0, let CNTRE = inf FeF(Woo) RR) n En_ [xx,) be the minimum training loss achievable by functions F(W(0), R). Then there exists
m (6, L) Ö (Poly( L) log (nn
such that if m > m= R, L), with probability at least 1 over the initialization, GD with step size (L m can train neural network to achieve at most 3ENTRF training loss within T OL22R22 ( iterations.
Theorem 3.3 shows that the deep ReLU network trained by GD can compete with the best function in the NTRF function class F(W(0) R) if the network width has polynomial dependency in R and L
and logarithmic dependency in n and 1/6. Moreover, if the NTRF function class with Ō(1) can learn the training data well (i.c., ENTRE is less than small target error e), polylogarithmic (in
terms and - network width suffices to guarantee the global convergence of GD, which directly
improves over- peee-paratteizziionn condition in the most related work (Cao and Gu, 2019). Besides, remark here that this assumption on the NTRF function class can be easily satisfied when the training data admits certain separability conditions, which we discuss in detail in Section 4.
Compared with the results in (Ji and Telgarsky, 2020) which give similar network width requirements for two-layer networks, our result works for deep networks. Moreover, while Ji and Telgarsky (2020)
4

---

Published as a conference paper at ICLR 2021
essentially required all training data be separable by function in the NTRF function class with constant margin, our result does not require such data separation assumptions, and allows the NTRF function class to misclassify small proportion of the training data points".
We now characterize the generalization performance of neural networks trained by GD. We denote (W) (xxx,))>[111 (/w (x) y < 0]] the expected 0-1 loss (i.e., expected error) of fw fw(x). Theorem 3.4. Under the same assumptions as Theorem 3.3, with probability at least 1 - ó, the iterate
W(1) Algorithm satisfies that
1 R//// Vn
) + + log(1/0)
I (W()) & 222s(W(0)) δ 4 14
m
A
+
m//6
for all 1 0, O...., T.
Theorem 3.4 shows that the test error of the trained neural network can bounded by its training error plus statistical error terms. Note that the statistical error terms is in the form of a minimum between two terms 4 L L mfn and 3 R/v ni + 1 22//3/ R4/3////66 /m2/6 Depending on the network width m, one of these two terms will be the dominating term and diminishes for large n: (1) m o(n), the statistical error will be 4 T,2 RV mm/n, and diminishes as n increases; and (2) if m = (n)). the statistical error is 3 R/ n + 1 ////////////////////// 184/3/mm /m/// and again goes to zero increases. Moreover, in this paper have specific focus on the setting statistical error of order (O 1/3). This distinguishes our result from previous generalization bounds for deep networks (Cao and Gu, 2020; 2019), which cannot be applied to the setting m = Ö(1).
( under which Theorem 3.4 gives
We note that for two-layer ReLU networks (i.e., L 2) Ji and Telgarsky (2020) proves tighter ((1/n!/2) generalization enror bound regardless of the neural networks width m. while our result (Theorem 3.4), in the two-layer case, can only give O(1/n2/22 generalization error bound when m = (1) m = ((n2)). However, different from our proof technique that basically uses the (approximated) linearity of the neural network function, their proof technique largely relies on the 1 t-homogeneous property of the neural network, which restricted their theory in two-layer cases. An interesting research direction is to explore whether ((1/n²/2) generalization error bound can be also established for deep networks (regardless of the network width), which we will leave as a future work.
3.2 STOCHASTIC GRADIENT DESCENT
Here we study the performance of SGD for training deep ReLUU networks. The following theorem establishes generalization error bound for the output of SGD.
Theorem 3.5. For 6, R > 0, let ENTRE = FeF(2 RR) n --' " ((nF(xx)) be the minimum training loss achievable by functions F(W("), RR. Then there exists
m (8, R. L) δ (poly((R, L) (n//))
such that if m 3 m² R, L), with probability at least 1 - 8, SGD with step size rj = (mm-1. - NTRR 1)) achieves
RL2R²
8log(2/0)
E ELLO
+ 24ENTRF
where the expectation taken over the uniform draw of W from (W ...., (3-
For any > 0, Theorem 3.5 gives a Õ sample complexity for deep ReLU networks trained with SGD to achieve O(ENTRF <) test error. Our result extends the result for two-layer networks proved in (Ji and Telgarsky, 2020) to multi-layer networks. Theorem 3.5 also provides sharper results compared with Allen-Zhu et al. (2019a); Cao and Gu (2019) in two aspects: (1) the sample complexity is improved from
Ō(E 2) to n Ō and (2) the overparamterization condition is improved from m > poly(c-1) to m Ā(1)
A detailed discussion is given in Section 4.2.
5

---

Published as a conference paper at ICLR 2021
4 DISCUSSION ON THE NTRF CLASS
Our theoretical results in Section 3 rely on the radius (i.e., R) of the NTRF function class F(W(o), R) and the minimum training loss achievable by functions in F( F(W((), Rt), i.e. SNIRF- Note that larger R naturally implies a smaller ENTRE, but also leads to worse conditions on m. In this section, for any (arbitrarily small) target eπrоr rate > 0. we discuss various data assumptions studied in the literature under which our results can lead to ((e) training/test errors, and specify the network width requirement.
4.1 DATA SEPARABILITY BY NEURAL TANGENT RANDOM FEATURE
In this subsection, we consider the setting where large fraction of the training data can be linearly separated by the neural tangent random features. The assumption stated as follows.
Assumption 4.1. There exists a collection of matrices U {Ui..... U.} satisfying
Σ | 1, such that for at least (1 p) fraction of training data we have
y V wwi (x,): U*> > m2227,
where 7 is an absolute positive constant and e [0, 1).
The following corollary provides an upper bound of eNTRF under Assumption 4.1 for some R.
Proposition 4.2. Under Assumption 4.1, for any e, 8 > R C[log* (n/6) log(L/e)) for some absolute constant C, then with probability at least 1 5,
CTTR
inf
n
Σ
FEF(WO) RR)
Proposition 4.2 covers the setting where the NTRF function class is allowed to misclassify training data, while most of existing work typically assumes that all training data can be perfectly separated with constant margin (i.e., P 0) (Ji and Telgarsky, 2020; Shamir, 2020). Our results show that for sufficiently small misclassification ratio p (c)), we have CNTRF Ō(c) by choosing the radius parameter R logarithimic in 8-1, and E Substituting this result into Theorems 3.3, 3.4 and 3.5, it can be shown that neural network with width m = poly L, log(n) (n/())),, log(1/)))) suffices to guarantee good optimization and generalization performances for both GD and SGD. Consequently, we can obtain that the bounds the test error for GD and SGD are Ö(n (n-1/2) and Ö(n-)) respectively.
4.2 DATA SEPARABILITY BY SHALLOW NEURAL TANGENT MODEL
In this subsection, we study the data separation assumption made in Ji and Telgarsky (2020) and show that our results cover this particular setting. We first restate the assumption as follows.
Assumption 4.3. There exists u(-) Rdd Rd and y > 0 such that |[(())]22 < 1 for all z R4, and
Yi
d(( (u(z). x, duN > Rdd
for all i [n], where (-(()) denotes the standard normal distribution.
Assumption 4.3 is related to the linear separability of the gradients of the first layer parameters at random initialization, where the randomness is replaced with an integral by taking the infinite width limit. Note that similar assumptions have also been studied in (Cao and Gu, 2020; Nitanda and Suzuki, 2019; Frei et al., 2019). The assumption made in (Cao and Gu, 2020: Frei et al., 2019) gradients with respect to the second layer weights instead the first layer ones. In the following, we mainly focus Assumption 4.3, while result can also be generalized cover the setting in (Cao and Gu, 2020; Frei et al., 2019).
The factor is introduced here since || wit) (f [xx)] is typically of order 0(m" 122)

---

Published as a conference paper at ICLR 2021
In order to make fair comparison, reduce results for multilayer networks to the two-layer setting. In this case, the neural network function takes form
[x( = W20//2aoW
Then we provide the following proposition, which states that Assumption 4.3 implies a certain choice
of R = (1) such the the minimum training loss achieved by the function in the NTRF function class F(W(O), Rt) satisfies eNTRF = O(e), where is the target error.
Proposition 4.4. Suppose the training data satisfies Assumption 4.3. For any c, 0, let R C (o) + log (1 for some large enough absolute constant C. If the neural network width satisfies m 2 log(n) ///0//)) then with probability at least 1 - 6, there exist Fwo,, "wo,,w(x) (x:) F(W(O), R) such that Ey: Fwo, w (x:)) & e, Vi [n].
Proposition 4.4 shows that under Assumption 4.3, there exists F Wio w() E F(W((), R) with R = ((17)) such that the cross-entropy loss of Fwoo w(.) at each training data point is bounded by This implies that ENTRF & e. Moreover, by applying Theorem 3.3 with L = 2, the condition on the neural network width becomes
(1//5)/,, which matches the results proved in Ji and Telgarsky (2020). Moreover, plugging these results on m and eNTRF into Theorems 3.4 and 3.5, we can conclude that the bounds on the test error for GD and SGD are Ó( 1/2) and Önn")) respectively.
4.3 CLASS-DEPENDENT DATA NONDEGENERATION
In previous subsections, have shown that under certain data separation conditions CNTRE can be sufficiently small while the corresponding NTRF function class has R of order Ö(1) Thus neural networks with polylogarithmic width enjoy nice optimization and generalization guarantees. In this part, we consider the following much milder data separability assumption made Zou al. (2019).
Assumption 4.5. For all i * i' if * ye, then x; x 2 á for some absolute constant Φ.
In contrast to the conventional data nondegeneration assumption (i.e., no duplicate data points) made in Allen-Zhu et al. (2019b); Du et al. (2019b;a); Zou and Gu (2019)², Assumption 4.5 only requires that the data points from different classes are nondegenerate, thus we call it class-dependent data nondegeneration.
We have the following proposition which shows that Assumption 4.5 also implies the existence of good function that achieves training error, in the NTRF function class with certain choice of R. Proposition 4.6. Under Assumption 4.5, if
R = 2/2 1-:0//6-1// 1/2 (e((n6-'e-1) have ENTRF & with probability at least 8.
m = n2
Proposition 4.6 suggests that under Assumption 4.5, in order to guarantee CXTRF & c, the size of NTRF function class needs to be ((n23/2). Plugging this into Theorems 3.4 and 3.5 leads to vacuous bounds on the test error. This makes sense since Assumption 4.5 basically covers the "random label" setting, which impossible to be learned with small generalization error. Moreover, we would like point out theoretical analysis leads to sharper peee-aarametrizatioon condition than that proved in Zou et al. (2019), i.e., m & 03 ve-1/6) -116).
-- - ). the network depth satisfies
5 PROOF SKETCH OF THE MAIN THEORY
In this section, we introduce a key technical lemma in Section 5.1, based on which we provide a proof sketch of Theorems 3.3. The full proof of all our results can be found in the appendix.
We have shown in the proof of Theorem 3.3 that .²(Ht² ) (see (A.1) for more detail). 'Specifically, Allen Zlunn-Zhu et al. (2019b); Zou and Gu (2019) require that any two data points (rather than data points from different classes) are separated by positive distance. Zou and Gu (2019) shows that this assumption equivalent to those made in Du et al. (2019h;a), which require that the composite kernel matrix is strictly positive definite.
7

---

Published as a conference paper at ICLR 2021
5.1 A KEY TECHNICAL LEMMA
Here we introduce a key technical lemma used in the proof of Theorem 3.3.
Our proof is based the key observation that near initialization, the neural network function be approximated by its first-order Taylor expansion. In the following, we first give the definition of the linear approximation error in 7-neighborhood around initialization.
Fapp (T)
sup
sup
[w (x;)) - (V/w W PP--W -
1- 1=1,- 1 WeB(W
all the iterates of GD stay inside a neighborhood around initialization with small linear approxima- tion error, then we may expect that the training of neural networks should be similar the training of the corresponding linear model, where standard optimization techniques can be applied. Motivated by this, also give the following definition on the gradient upper bound of neural networks around initialization, which is related to the Lipschitz constant of the optimization objective function.
((T
== sup
sup
sup
(w,))l
L= I.,,,,,, WEB(W(O).))
By definition, we can choose W E B(W Rm 1/2) such that n En_ ey: .w+ ((J:Fwro..xxxx))) =
eNTRF. Then we have the following lemma.
Lemma 5.1. Set 17 ((L
Suppose that W E B (( r) and W( B B(W()),))
for all 0 & 1 E
Then it holds that
W - W
W
W - W + 21' NENTET
Σ Ls(( (w()))
('n(( 4eapp(T))
Lemma 5.1 plays a central role in our proof. In specific, if W(O E B(W("), . for all & & l', then Lemma 5.1 implies that the average training loss is in the same order of CNTRF as long as the linear approximation error (Tpp(T) (T) is bounded by a positive constant. This is in contrast to the proof in Cao and Gu (2019), where (T) (T) appears as an additive term in the upper bound of the training loss, thus requiring (pp (T) = (TNTR)) to achieve the same error bound as in Lemma 5.1. Since we can show that Capp O - 1/6) (See Section A.1), this suggests that = 22(1 is sufficient to make the average training loss in the same order of CNTRE-
Compared with the recent results for two-layer networks by Ji and Telgarsky (2020), Lemma 5.1 is proved with different techniques. In specific, the proof by Ji and Telgarsky (2020) relies on the 1 t-homogeneous property of the ReLU activation function, which limits their analysis to two-layer networks with fixed second layer weights. In comparison, our proof does not not rely on homogeneity, and purely based on the linear approximation property of neural networks and some specific properties of the loss function. Therefore, our proof technique can handle deep networks, and is potentially applicable to non Ron- activation functions and other network architectures (e.g. Convolutional neural networks and Residual networks).
5.2 PROOF SKETCH OF THEOREM 3.3
Here we provide a proof sketch of Theorem 3.3. The proof consists of two steps: (i) showing that all T iterates stay close to initialization, and (ii) bounding the empirical loss achieved by gradient descent. Both of these steps are proved based on Lemma 5.
Proof sketch of Theorem 3.3. Recall that we choose W E B(W()), Rm- such that n - (y Fwoo Bol,.ww((e (x:)) = <NTRE. We set r = m1122 which is chosen slightly larger than 1/2 R. since Lemma 5.1 requires the region (()(()), r) to include both W and (W00) Then by Lemmas 4.1 and B.3 in Cao and Gu (2019) we know that capp(T) = 0(14411118mm11 Therefore, we can set m 5(( 1,22) to ensure that
Eapp(1) (T) < 1/8.
Then we proceed show that all iterates stay inside the region B (0) .). Since the L.H.S. of Lemma 5.1 is strictly positive and capp (Tp(T)) & 1/8, we have for all / & T.
( way
|W()) W
20
8

---

Published as a conference paper at ICLR 2021
which gives upper bound of W W Then by the choice of 77, T, triangle inequality, and simple induction argument, we that [W(t) W F & 1/2 /2T O(L'/mm-1/ 1/2 R), which verifies that W( ((W for
-
The second step is to show that GD can find a neural network with at most 3ENTRE training loss within iterations. To show this, by the bound given Lemma 5.1 with Eapp & 1/8, we drop the terms [|W() 3 and rearrange the inequality to obtain
Ls
1 [((0)) T/T
w 1 2ENTRF.
1=
see that T is large enough to ensure that the first term in the bound above is smaller than éNTRF- This implies that the best iterate among W ,..., W(T-1) achieves an empirical loss most 3ENTRE.
6 CONCLUSION
In this paper, we established the global convergence and generalization error bounds of GD and SGD for training deep ReLU networks for the binary classification problem. We show that network width condition that is polylogarithmic in the sample size n and the inverse of target error e is sufficient to guarantee the learning of deep ReLU networks. Our results resolve an open question raised in Ji and Telgarsky (2020).
ACKNOWLEDGEMENT
We would like to thank the anonymous reviewers for their helpful comments. ZC, YC and QG are partially supported by the National Science Foundation CAREER Award 1906169, IIS-2008981 and Salesforce Deep Learning Research Award. D7. is supported by the Bloomberg Data Science Ph.D. Fellowship. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
REFERENCES
ALLEN-ZHU, Z., LI, Y. and LIANG, Y. (2019a). Learning and generalization overparameterizee neural networks, going beyond two layers. In Advances in Neural Information Processing Systems.
ALLEN-ZHU, Z., LI, Y. and SoNG, Z. (2019h). A convergence theory for deep learning via over-parametteiizatio.. In International Conference on Machine Learning.
ALLEN-ZHU, Z., L1, Y. and SoNG, Z. (2019c). On the convergence rate of training recurrent neural networks. In Advances in Neural Information Processing Systems.
ARORA, S., DU, S., HU, W., Z. and WANG, R. (2019a). Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning.
ARORA, S., DU, S. S., HC, W., LI, 7.,, SALAKHUTDINOV, R. and WANG, R. (2019b). On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems.
BAI, Y. and LEE, J. D. (2019). Beyond linearization: On quadratic and higher-order approximation of wide neural networks. In International Conference on Learning Representations.
BARTLETT, P. L., FOSTER, D. and TELGARSKY, M. (2017). Spectrally-normalized margin bounds for neural networks. In Advances in Neural Information Processing Systems.
BARTLETT, P. L. and MENDELSON, S. (2002). Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research 463-482.
CAO, Y. and Gu, Q. (2019). Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems.

---

Published as a conference paper at ICLR 2021
CAO, Y. and GU, Q. (2020). Generalization error bounds of gradient descent for learning parameterized deep relu networks. In the Thirty- Sairty-Fourth AAAI Conference on Artificial Intelligence.
CESA-BIANC BIANBII N., CONCONI, A. and GENTILE, C. (2004). On the generalization ability on-line learning algorithms. IEEE Transactions Information Theory 50 2050-2057.
CHIZAT, L.., OYALLON, F. and BACH, F. (2019). On lazy training in differentiable programming. In Advances in Neural Information Processing Systems.
DU, LEE, J., LI, H., WANG, L. and Zhai, (2019a). Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning.
DU, S. S., ZHAI, X., Poczos, B. and SINGH, A. (2019b), Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations.
FREI, S., CAO, Y. and GU, Q- (2019). Algorithm-dependent generalization bounds for overparame- terized deep residual networks. In Advances in Neural Information Processing Systems.
HE, K., ZHANG, X., REN, S. and SUN, J. (2015). Delving deep into rectifiers: Surpassing human- level performance imagenet classification. In Proceedings of the IEEE international conference on computer vision.
JACOT, A., GABRIEL, F, and HONGLER, C. (2018). Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems.
JI, Z. and TELGARSKY, M. (2018). Risk and parameter convergence of logistic regression. arXiv preprint arXiv:1803.07334
J1, Z. and TELGARSKY, M. (2020). Polylogarithmic width suffices for gradient descent achieve arbitrarily small test error with shallow relu networks. In International Conference on Learning Representations.
KAWAGUCHI, K. and HUANG, (2019). Gradient descent finds global minima for generalizable deep neural networks of practical sizes. In 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE.
KRIZHEVSKY, A. ET AL. (2009). Learning multiple layers of features from tiny images.
LEE, J., XIAO, L., SCHOENIIOLZ, S. S., BAIRI, Y., SOII-DICKSTEI, and PENNINGTON, J. (2019). Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in Neural Information Processing Systems.
MOHRI, M., ROSTAMIZADEH, A. and TALWALKAR, A. (2018). Foundations of machine learning. MIT press.
NITANDA, A. and SUZUKI, T. (2019). Refined generalization analysis of gradient descent for ower-parameterized two-layer neural networks with smooth activations classification problems. arXiv preprint arXiv: /005.099000090
OYMAK, and SOLTANOLKOTABI, M. (2019). Towards moderate overparameterization:: global convergence guarantees for training shallow neural networks. arXiv preprint arXiv:1902.0400
SHALEV-SHARTZ. S. and SEN-DAVID, S. (2014). Understanding machine learning: From theory to algorithms. Cambridge university press.
SHAMIR, O. (2020). arXiv:2007.00028
Gradient methods never overfit on separable data.
arXiv preprint
VERSHYNIN, R. (2010). Introduction to the non-asymptotic analysis of random matrices. arXiv preprint 1011::001.
Zou, D., CAO, Y., ZHOU, D. and GU, Q. (2019). Gradient descent optimizes over-parameterrized deep ReLU networks. Machine Learning
Zou, D. and GU, Q. (2019). An improved analysis of training over over- aver-parameterized deep neural networks. In Advances in Neural Information Processing Systems.
10

---

Published as a conference paper at ICLR 2021
A PROOF OF MAIN THEOREMS
In this section we provide the full proof of Theorems 3.3, 3.4 and 3.5.
A.1 PROOF OF THEOREM 3.3
We first provide the following lemma which is useful in the subsequent proof.
Lemma A.1 (Lemmas 4.1 and B.3 in Cao and Gu (2019)), There exists an absolute constant x such that, with probability at least (nI2²) exp[- L)], for any r KL- (ao."([og(m))) (m) holds that
Capp (T) (
M(T) Ölvm)
Proof of Theorem 3.3. Recall that W* is chosen such that
1
(uuF = CNIRFF
and W E B(W(()) RRm Rm3-/ Note that to apply Lemma 5.1, we need the region ((W r) to in-
clude both W* and "W("))=...... This motivates set m( 1/2 which is slightly
larger than m m/2 R. With this choice of т, by Lemma A. we have <app(7) ( 1/2 1,) Ö(R4/3 L m ). Therefore, we can set
= 1,22
(A.1)
to ensure that (Tp)(T) & 1/8, where (?(-) hides polylogarithmic dependencies on network depth L, NTRF function class size R. and failure probability parameter 8. Then by Lemma 5.1, we have with probability least 1 5, we have
I W /W()'
w
Σ
Ls(W(1)
22' PENTTR
(A.2)
as long as (0))) W ((W(") .)). In the following proof we choose 17 1mm__mm²1
and 7' L EIRFI
We prove the theorem by steps: 1) show that all iterates ( ,-... W(T) will stay inside the region ((W(0), r); and 2) we show that GD can find a neural network with at most 3ENTRE training loss within 7 iterations.
All iterates stay inside B B(W(0), .)). We prove this part by induction. Specifically, given & T, we assume the hypothesis ( E B (0), (0) (T) holds for all < t' and prove that w(() e B (((()), T).
First, it is clear that ((0) E B (0), T). Then by (A.2) and the fact that Ls(W) > 0, we have
(
[W W + 2nt'' CNTRF
Note that T [LR2 m 1n NIRF and W* ((W(") R m 1/2), we have
Σ w (()) W 1 & mI
where C ' is absolute constant. Therefore, by triangle inequality, we further have the following for all e [L].
w w (w(?) Wi + | WilF
V VCLm 1/2 + Pmm 1/22
2v CLRRm-M -1/2
(A.3)
Therefore, it is clear that w previously. This completes the proof of the first part.
w (0) |r & 2CLLRm 1/2 & 7 based on our choice of T
11

---

Published as a conference paper at ICLR 2021
Convergence of gradient descent. (A.2) implies
--1
| (0) W W W
Σ
Ls( (s(()) 27 2TENRRE
Dividing by 7/ on the both sides, we get
T-1 Σ Ls(W))) & (W w
LR m1
2ENTRE
+ 2ENTRE & 3ENTRE.
T
nf
1/
where the second inequality by the fact that W E B(W(O), R m 1/2) and the last in- equality is by our choices of T and y which ensure that T' > LR-m-''eTi ENTRF Notice that [LR2m-ly " = O R2 (TRF). This completes the proof of the second part, and are able to complete the proof.
A.2 PROOF OF THEOREM 3.4
Following Cao and Gu (2020), we first introduce the definition of surrogate loss of the network, which is defined by the derivative of the loss function.
Definition A.2. We define the empirical surrogate error Es( W) and population surrogate error ED (W) as follows:
T1 n Σ
(w(
[w fw(wx)] ED(W) Exx.)= - [ fw(x)]}
The following lemma gives uniform--onvergence type of results for &s(W) utilizing the fact that (-) is bounded and Lipschitz continuous.
Lemma A.3. For any R. 5 > O, suppose that (2 at least 1 - 8, it holds that
[log(1/5))3r
Then with probability
(ED(W) Es( W) & θ min
1,/1
R
m
LR
+
L
T2/3
)) 0 +VV log (/5)
Vn
m/
for all We ((W()), R. m 1/2)
We are now ready to prove Theorem 3.4, which combines the trajectory distance analysis in the proof of Theorem 3.3 with Lemma A.3.
Proof of Theorem 3.4. With exactly the same proof as Theorem 3.3, by (A.3) and induction we have W()), W(1) W()) e B(W("), Rm Rm2) with R O(VLR) Therefore by Lemma A.3, we have
(ED(W()) Es(( (w(() o min 44
3 Vni
1
}) O log((/0))
n
m 1/6
11
for all i 0, T. Note that we have 1/2 < 0) & 22' Therefore,
EL--1(((1) & 28 (w(())
$ 2T. (T(((W())) δ min 4 R
m
1
L (1/324:0 m/6
)) 001
log( 1/8)
Vn
n
for 0, 1......, where the last inequality is by Es( W) & Ls( W) because -6((2) $ ((2) for all R. This finishes the proof.
12

---

Published as a conference paper at ICLR 2021
A.3 PROOF OF THEOREM 3.5
In this section we provide the full proof of Theorem 3.5. We first give the following result, which is the counterpart of Lemma 5.1 for SGD. Again we pick W E B(W(") Rm 1/2) such that the loss of the corresponding NTRF model Fwo, .w= (x) achieves CNTRF.
Lemma A.4. Set (LL Suppose that W E B(W T) and W(4)) B(W for all 0 n' < n 1. Then holds that
n L (W(i-)) 2TTENTRE-
3 W (0) 1 - |w(n') W 2 ( (T)
We introduce surrogate loss (W) - fw fw,)) and its population version Ep ()) ((m.g)-p[-e") [w(]]]], which have been used (Ji and Telgarsky, 2018; Cao and Gu, 2019; Ji and Telgarsky, 2020). Our proof is based on the application of Lemma A.4 and online-to- batch conversion argument (Cesa-Bianch) et al., 2004; Cao and Gu, 2019; Ji and Telgarsky. 2020). We introduce surrogate loss (W) [ fw (ax) ]] and its population version &p (DW E(e.))) (w(x)), which have been used in (Ji and Telgarsky, 2018; Cao and Gu, 2019; Nitanda and Suzuki, 2019; Ji and Telgarsky, 2020).
Proof of Theorem 3.5. Recall that W* is chosen such that
= ENTRF
and W* E B( ((W(O), Rm 1/2) To apply Lemma A.4, we need the region B (0) 7) to include
(0) both W and [W())..-....... J.-0.....' This motivates to set O 12/22 Rt. which is slightly larger than m 1/2 R. With this choice of т, by Lemma A.1 we have Capp (T) Ö( m/2 Ö(R4/3 11/3 m m-1).. Therefore, we can set
m = π (Q[RLL 22
to ensure that (T) & 1/8, where 2(-) hides polylogarithmic dependencies network depth L, NTRF function class size R, and failure probability parameter 8.
Then by Lemma A.4, have with probability at least 1 8,
W w+ - |/wnn) - w+ 21 2 ((((i-))) 2TTTENTRE
(A.4)
as long as ( W(a-11) E B(W(0),
We then prove Theorem 3.5 in two steps: 1) all iterates stay inside B(W(0), T): and 2) convergence of online SGD.
All iterates stay inside B3 (()))),) r). Similar to the proof of Theorem 3.3, we prove this part by induction. Assuming ( satisfies W(() e B(W(") -) for all i < n' - 1,, by (A.4), we have
[w W* < W (0) W* 2- 21TEENTRE
LR
21MENNTEF
where the last inequality is by W B B(W()) Rm 1.2). Then by triangle inequality, further get
[w("') (n') w/ & W (n') W F + W
w ||
(1') W' F IW
W 00)
OVLLRm 1/2 + VnTIENTRF)
Then by our choices of = 0mm -I
NTRF A )-))), we have w(() - TTRmm 1/2 & This completes the proof of the first part.
13

---

Published as a conference paper at ICLR 2021
Convergence of online SGD. By (A.4), we have
|W w |W(") w
Σ
(w((i1)))
22ENTRF
Dividing by ynn the both sides and rearranging terms, get
L(((-1)) w W IW(n)
W*
L²
2ENTRE $ n
3ENTRE;
17m
where the second inequality follows from facts that W* E B(W R m m- and O(m L L-) By Lemma 4.3 in (Ji and Telgarsky, 2020) and the fact that E (W((1))) L (), we have
1
L 0-1 (W
2
Σ Ep
(w(li)))
D
8 n
((((-))) + 8log(1/6)
Σ
n
[-1
n
SL2 R²
8 8log(1/6) 24ENTRF
n
n
This completes the proof of the second part.
B PROOF RESULTS IN SECTION 4
B.1 PROOF OF PROPOSITION 4.2
We first provide the following lemma which gives an upper bound of the neural network output at the initialization.
Lemma B.1 (Lemmaa 4.4 in Cao and Gu (2019)). Under Assumption 3.1, if m t CLllo((n//)) with some absolute constant C, with probability at least 6, we have
Ifwro: & Coloo((n/8)
for some absolute constant C.
Proof of Proposition 4.2. Under Assumption 4.1, we can find a collection of matrices U* [U+. U with Σ/= | = such that yk f (x;), U*> > m 1/2 for at least 1 fraction of the training data. By Lemma B. for all i E [m] we have If (x,) < C. /log(n/o) for
some absolute constant C. Then for any positive constant X, we have for least portion the data,
yA (Jwros (xx) + (V/wo,, \U*)) 2 1/2 Colog(n/8).
For this fraction of data, we can set
Ioolog log (n//0) + log(l/e))
where C" is absolute constant, and get
1/2 by
> log(1/e).
Now we let W = W( + XU" By the choice of R in Proposition 4.2, we have W* B(W B(W(O), R m-1122) The above inequality implies that for at least fraction of data, we have (ynlFwoo w* (x:)) For the rest data, we have
yz (f + (Vfwo, AU*) CVlog(n/0) Awwo 1 >
14

---

Published as a conference paper at ICLR 2021
for some absolute positive constant C1, where the last inequality follows from fact that Vf Omm!/2) (see Lemma A.I I for detail). Then note that we use cross-entropp loss, follows that for this fraction of training data, we have {yy Fwo.,, (ww.)./=(X)) (x())) & C2R for some constant C2. Combining the results of these two fractions of training data, we can conclude
ENTRF E n
Σ (1oF < (1 - p)e p. P-(H)
This completes the proof.
B.2 PROOF OF PROPOSITION 4.4
Proof of Proposition 4.4. We are going to prove that Assumption 4.3 implies the existence of good function in the NTRF function class.
By Definition 3.2 and the definition of cross-entropy loss, our goal is to prove that there exists
collection of matrices W- (W1, 1, Wa) satisfying max| W w F. W2- w (0) (2) < R m 1/2 such that
y/ [/wro] + (Ww,/wo) Wi w (Vwz/wo, W2 w > log(2/e).
We first consider Jwro (x:), which has the form
(Vw,/wol (x:)) m 1/2
(0) 22.
(0) o ((w w.. x:)) X;.
Note that (0)
W2.3 and wi. are independently generated from (0, 1 1/m) and ((0, 21/m) respectively, thus we have P(
(0) > 0.47m-1/22 1/2. By Hoeffeding's inequality, we know that with probability at least 1 exp(-m/8), there are least m/4 nodes, whose union is denoted by S, (0) > 0.47m 1/2, Then we only focus on the nodes in the set S. Note that w and _ are independently generated. Then by Assumption 4.3 and Hoeffeding's 's incquality, there exists a function u(-): : Rd pd such that with probability at least 1 8',
satisfying |
(1/8)
yi (u (u(w (0) x.) d'((w') (0)
x.))
S
S
JES
Define v, = u(w(..)) ///))///, /w2,, if W2y > 0.47m - 1/2 and V, 0 otherwise. Then we have
> 3i
2 (0)
(v), o' d'( (( x1))
(0)
> ys (.(w.)))) xx) o d'((w 1 xx)
jES
>
|Sh v 2|S (og()))))
Set 8 = 2nód and apply union bound, we have with probability at least 1-66 8/2.
m Σ y 2 (v), o' ('(w (x)l,,))) xx)) > |sh 2/8) log (21/0))
(0)
Therefore, note that with probability at least - exp(-m/8) we have |S| i m/4. /4. Moreover, in Assumption 4.3, by {+1} and (o(()), [T]()]]2, ||x:|| & 1 for i = -,.... n. we see that 7 & 1. Then if m 32 log(n/8) /)/77² with probability at least - 8/2 exp ( 4 log(n/0)/73 > - 5.
U 22 (v, x,) d'(( x)) > |Sh/2 Σ
1=1
Let U (V1, vm) 1/v S. have
m
(0) 2j (v,, 0 d( (() V
124
y: VW, U)
y/ w
15

---

Published as a conference paper at ICLR 2021
where the last inequality is by the fact that |S| > m/4. Besides, note that by concentration and Gaussian tail bound, we have wf (x,) & (n/)g(n/)) for some absolute constant C. Therefore,
let W1 w 4 (1og(2/c) + Clog(n/6)) - and W₂ w/ have
V4 [f (x.) + fw.., W w + (Vw:Jwo, We ! > e log(2/e). (B.1) Note that |a(-)1l2 $ 1, we have | & 1/0.47 2.2. Therefore, we further have [W1 w |F < 8.8y 8 (2/((2/)) + Cllo((n/6)) -m This implies that W e B(W(O), R) with R = O(log log (n/(de)) /7) Applying the inequality ((1og(//e)) & on (B.1) gives
fyy Fw (x,)) E
for all I,..., This completes the proof.
B.3 PROOF OF PROPOSITION 4.6
Based on our theoretical analysis, the major goal to show that there exist certain choices of R and m such that the best NTRF model in the function class F(W(O) 1 R) can achieve training error. In this proof, will prove stronger results by showing that given the quantities of R and m specificed in Proposition 4.6, there exists a NTRF model with parameter W that satisfies n Σ {y: woo, (x())))
In order to do so, we consider training the NTRF model via different surrogate loss function. Specifically, we consider squared hinge loss {(x) [max(AA À z, 03)² where À denotes the target margin. In the later proof, we choose À = (1/ee + such that the condition {(xr) & 1 can guarantee that x > log(e). Moreover, we consider using gradient flow, i.e., gradient descent with infinitesimal step size, to train the NTRF model. Therefore, in the remaining part of the proof, we consider optimizing the NTRF parameter W with the loss function
Ls(W) Σ
E Eyr w(x)))
Moreover, for simplicity, only consider optimizing parameter in the last hidden layer (i.e., W. WL-1). Then the gradient flow can be formulated as
dW (t) = Vw.., Lw.. dt
dW,(t) = 0 for any l # L 1.
dt
Note that the NTRF model is linear model, thus by Definition 3.2, have Ww., y
( (yx Fwoo, (()()))) Vw ((oo),))((())))
yi Fyro (y.Fwwo..coo(x.) V V fwor (x:).
(B.2)
Then it is clear that V (W()) has fixed direction throughout the optimization.
In order to prove the convergence of gradient flow and characterize the quantity of R, We first provide the following lemma which gives upper bound of the NTRF model output at the initialization.
Then we provide the following lemma which characterizes a lower bound the Frobenius norm of the partial gradient V Vwz-, (s()..
Lemma B.2 (Lemma B.5 in Zou al. (2019)). Under Assumptions 3.1 and 4.5, if m Q(n2 then for all / > O, with probability at least 1 exp O(monn)) there exist a positive constant C such that
Vw..,Ls
CmΦ n
Σ E' (y. ,wo
We slightly modified the original version of this lemma since we use different models (we consider NTRF model while Zou et al. (2019) considers neural network model). However, by (B.2), it is clear that the gradient VLs(W) can be regarded as type of the gradient for neural network model the initialization (i.e., V Vwa-, - T.s( (W(0))) is valid. Now are ready to present the proof.
16

---

Published as a conference paper at ICLR 2021
Proof of Proposition 4.6. Recall that only consider training the last hidden weights, i... W WL-1. via gradient flow with squared hinge loss, and our goal is to prove that gradient flow is able to find a NTRF model within the function class F(W("), R) around the initialization, i.c, achieving -x=1 Fyi (x)))) Let ((t) be the weights at time t, gradient flow implies that
(F(((W())))))))))))))))()))))()) dt = VV., =
Cmm n2
~ (ve
(ommLLs(W()))) n
&
where the first equality is due to the fact that we only train the last hidden layer, the first inequality is by Lemma B.2 and the second equality follows from the fact that (()) - above inequality gives
-2 (()).
Solving the
[s((())) < Ls(((()) exp (- 4Cmpt
(B.3)
n²
Then, set T' = On''m'n''''' log(Ls (W(())/e)) Lew..looo(S(((OO00 it follows that Elv: Fly: w(n) (x:)) & 1, which implies that yı w.oo (())) > log(e) and thus Therefore, W(T) is exactly the NTRF model
and é' 1/n, we have Ls (W (t)) < é.. Then
n= E BeceFroo,+*xx/ for.
looking
The next step is to characterize the distance between W(T) and W(O) in order to characterize the quantity of R. Note that /V,,,, Ls(())) (CmoLs(W((t)) we have
dy Ls((W de
Vw Ls (W())) VwV LLs(W(()) F. 2 (W()))
1222//
1//
Taking integral on both sides and rearranging terms, have
3/3/2
(VIs(W(O) LL(((())))))))
J VwL (W)))ll 1/22m12612
Note that the L.H.S. of the above inequality is upper bound of [W(t) -(0)) r. have for any t > 0,
n 3/2
3/2 log (n/(6e))
4/222 V (Ls(W(o)) o(
(( (()] &
11/201/2
where the second inequality is by Lemma B.I and our choice log(1/c) + 1. This implics that there exists point * within the class F( ((W("), Rt) with
n 3/2 log (n/(6c))
R = O
1/2
such that
12 Σ El (woFFwoo,. Sc
CNTRF
Then by Theorem 3.3, and, more specifically, (A.1), we can compute the minimal required neural network width follows,
n2
m = 5(
Φf
This completes the proof.
C PROOF OF TECHNICAL LEMMAS
Here provide the proof of Lemmas 5.1, A.3 and A.4.
17

---

Published as a conference paper at ICLR 2021
C.1
PROOF OF LEMMA 5.1
The detailed proof of Lemma 5.1 is given as follows.
Proof of Lemma 5.1. Based on the update rule of gradient descent, i... W = W(0)
7/V Ls (W()), we have the following calculation.
|W
W - | 3
20
W - W (w n
Σ V Ww, Los (s((0))
(C.1)
12
where the equation follows from the fact that Ls( ( - T (W))). what follows, we first bound the term J on the R.H.S. of (C.1) by approximating the neural network functions with linear models. By assumption, for t = O,....t t' - 1, w w e B(W(0), r). Therefore by the definition of Capp(T) (T).
(Vifww (x;), W(t) - W*> & Vi (fwro( fw=((x)) + Eapp(T)
(C.2)
Moreover, we also have
yi (fw* (xx) - (x(o(())) (Vfwro (xx), -*- w(0))) (Tp
Yi (fw* (x;) F we (x:)) Cupp(T):
(C.3)
where the equation follows by the definition of Fwio; w (x). Adding (C.3) to (C.2) and canceling the terms y fw= (x:), we obtain that
yi V wwo (x),, (( W*> & ye (fwro - Fwo. ww (x:)) + (T)
(C.4)
We can now give a lower bound on first term on the R.H.S. of (C.1). For 1,..., n, applying the chain rule on the loss function gradients and utilizing (C.4), we have
(w - W* Vw e' (yifwio (xx) Vs <W(o - Wa, (woo
(yies (xi) (yalwoo (x:) - wifwe (x:) 2eap (T)) F w (x:)), (C.5)
(1 (T (B)
where the first inequality is by the fact that l' (yifwoe) < O, the second inequality is by convexity of E(-) and the fact that- - (I)Sooxx))) & (VIJwie (x:).
We now proceed to bound the term l2 on the R.H.S. of (C.1). Note that we have E'(.) < 0, and therefore the Frobenius norm of the gradient (w.Ls(W(t)) can be upper bounded as follows,
|Vw.Ls
e' (x)
F
(()xfwoox:)) (ww,fwoo(x))lr
where the inequality follows by triangle inequality. We now utilize the fact that cross-entropy loss satisfies the inequalities - -e(() & E(-) and e((()) & 1. Therefore by definition of (T), we have
(1 - E' ((rfrroo)))))))
2
V.. Ww.Ls(Wir Ww < ((L(())))
& {(L(()))) Ls( (W))..
(C.6)
Then we can plug (C.5) and (C.6) into (C.1) and obtain
[W(
w+1
[(+1)
W*
18

---

Published as a conference paper at ICLR 2021
20
(1 2eapp ( (T)) - Poyeo (oo,,, -O(P -Ls(W(t)
3
(p)p nT. (W())
24
n2 Σ (yx:Froo,,xxx
W
where the last inequality is by 1 O and merging the third term on the second line into the first term. Taking telescope sum from to t = t' and plugging in the definition u--1 Fyiooo w*(x)) ENTRF completes the proof.
C.2 PROOF OF LEMMA A.3
Proof of Lemma A.3. We first denote W = B(W(") R m 1/2),, and define the corresponding neural network function class and surrogate loss function class as F (fw(x) W W) and {-ffy- fw(]]] W e W) respectively.
By standard uniform convergence results in terms of empirical Rademacher complexity (Bartlett and Mendelson, 2002; Mohri et al., 2018; Chalev-Shwart, and Ben-David, 2014), with probability at least 1 8 we have
e' [(v fw(xx)] + E(x.)) sw(x)]
sup WEW
[Es(W) - ED(W)) sup weW
log
29, + C
where 11 an absolute constant, and
Rr (9) Eg, -Uii((((()
sup WeW 71
Σ siElls fw(a)]
the empirical Rademacher complexity of the function class G. We now provide two bounds on (9), whose combination gives the final result of Lemma A.3. First, by Corollary 5.35 in (Vershynin, 2010), with probability at least 1 - L exp(-I(m)), |w < 3 for all I E [L]. Therefore for all W W, we have W & 4. Moreover, standard concentration inequalities on the norm of the first row of w(()) also implies that [[W]22 > 0.5 for all W W and / [4]. Therefore, gives
an adaptation of the bound in (Bartlett al., 2017)*
1/2
WT
O)
2/3
3/2
(F)
sup WeW
l12
2,1
Vn
W
1
2/3
m Vn
L Σ (Vm-
3/2
sup WeW
IW
w O)T 1
4 1,
3/2
(C.7)
m
We now derive the second bound on R. (9), which is inspired by the proof provided in (Cao and Gu, 2020). Since y [+1.1), (+)) < 1 and (((2) is 1-Lipschitz continuous, by standard empirical Rademacher complexity bounds (Bartlett and Mendelson, 2002; Mohri al., 2018; Shalev-Swwart and Ben-David, 2014), we have
1 a
(9) (F) -
sup Σ (.f((z))) WeW n
Bartlett et (2017) only proved Rademacher complexity bound for the composition of the ramp loss and the neural network function. In our setting essentially the ramp loss is replaced with the --((-) function, which is bounded and I-Lipschitz continuous. The proof in our setting is therefore exactly the same as the proof given in (Bartlett al., 2017), and we apply Theorem 3.3 and I Lemma A.5 in (Bartlett et al., 2017) obtain the desired bound present here.
19

---

Published as a conference paper at ICLR 2021
where (F) is the empirical Rademacher complexity of the function class F. We have
1 n
1 - Σ F Co) ww
[F| & Be
sup WEW
Σ TI
((f((x;) - (wo.,,(())) + EE
sup WeW
(C.8)
where Fw.., w wx) fwo (x) w fwoo (x), W -W For I1, by Lemma 4.1 in (Cao and Gu, 2019), with probability least 6/2 we have
1 $ max [w(w),)) Fw Fw:o), & 0 7 1/6 Vlo((m))
ic(n]
For I2, note that Eg| supwew Ei= fifwro
0. By Cauchy-Schwarzz inequality we have
12 =
Eg
sup
Tr
& V W. Fwrooo
[
1/2
Rm
1/2
Eg
Σ E V w fw:o
1=1
Therefore
Nmm 1/2
L
12 $
Ee
E V (wioo
1/2 Rm
L
n
(wo)
L. R
O
where we apply Jensen's 's inequality to obtain the first inequality, and the last inequality follows by Lemma B.3 in (Cao and Gu, 2019). Combining the bounds of I1 and I2 gives
LR
12
RM
&
m
Further combining this bound with (C.7) and recaling å completes the proof.
C.3 PROOF OF LEMMA A.4
Proof of Lemma A.4. Different from the proof of Lemma 5.1, online SGD only queries data to update the model parameters in each iteration, i.c., W W (W(().. By this update rule, we have
( W* 1 [W++)) W
L Vw, Li+1 (
27 ( W L (Wi))
n²
(C.9)
With exactly the same proof (C.5) in the proof of Lemma 5.1, we have
(w W Vw Tw((()()) (1 2eapp (1)p(T)))
(x:)) (yrlfwo, we (x)), (C.10)
for all 0, O,...,'' n' - 1. By the fact that -l(()) & E(.) and -E()) & 1, we have
Vw, Lin (W & Σ
20

---

Published as a conference paper at ICLR 2021
< {L((())) (W()..
(C.11)
Then plugging (C.10) and (C.11) into (C.9) gives
|W
W+ | W*
(2 Leapp ( (W()) - 2nd (y Fwi, (x()) -
3
2n ( y1 Fwror (w.. wxx)))
where the last inequality is by 1 OLL O (M) 3) and merging the third term on the second line into the first term. Taking telescope sum over O,...,n' 1. obtain
Ww w Wwn')
w
3
ceapp(7) (T))
Σ
Lg (w(()))) 2n
Σ el w (x:))
2
1-1
i-1
2¹'
3
4Capp (T)
Σ
L; (w((i-)))
2n Σ F(yiFwio, (xx))
2
1-1
3
n
W
Kkppp (7)
Σ
L; (w((i)))) - 2nTENTTRE
2
This finishes the proof.
D EXPERIMENTS
In this section, we conduct some simple experiments validate our theory. Since our pa- per mainly focuses on binary classification, we use subset of the original CIFARIO dataset (Krizhevsky et al., 2009), which only has two classes of images. We train 5-layer fully- connected ReLU network on this binary classification dataset with different sample sizes (n {100, 200, 500, 1000, 2000, 5000, 10000)), and plot the minimal neural network width that is required to achieve zero training error Figure (solid line). We also plot O(n), (log" (n)), Ologg (n)) and (n))( in dashed line for reference. It is evident that the required network width achieve zero training error is polylogarithmic on the sample size n, which is consistent with our theory.
50
50
O(n)
O(n)
Minimum Width
dinimum DNN Width
Ollog (n))
Ollog
35
35
30
30
Ollog
Ollog
25
25
20
20
15
(llog(n)
15:
Ollog(n))
10
10
5
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
Sample (n)
Sample Size (n)
(a) "cat" vs. "dog"
(b) "cat" vs. "ship"
Figure 1: Minimum network width that is required to achieve zero training error with respect to the training sample size (blue solid line). The hidden constants in all O(.) notations adjusted to ensure their plots (dashed lines) start from the same point.
21


Reviews:
[{"review_id": "ybGEC5t5ys2", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "The paper analyses the generalization properties of deep neural networks for classification tasks. The authors focus on the Neural Tangent Random Features (NTRF) class of functions to investigate these generalization properties.\nIn particular, the authors study the convergence of gradient descent (and its stochastic version). They establish that the training loss decreases until a certain level of the order of the best they can expect in the NTRF class. Then, the authors establish interesting generalization results with respect to the 0-1 loss. \nThis problem has been tackled recently in many papers. However, to establish similar results as those proved in this paper, the previous papers required a number of neurons per hidden layer to be polynomial with respect to the number of samples n. The authors shows here that a logarithmic (to a certain power) is actually sufficient when working with the NRTF class. Such results have been obtained recently in Ji and Telgarski (2020) but only for shallow network. In this paper, the results are generalized for deep neural networks. \n\nThe paper is clearly written and the comparison with the literature is complete and well-organized. The authors have worked hard to present, in a concise way and clearly their results. I appreciate it. The paper is fluid and nice to read. \n\nHere are some remarks that might improve the presentation of the paper:\n\n- It would be nice to recall the function $\\sigma$ in Section 2\n\n- In my opinion the remark: \n\" Moreover, while Ji and Telgarsky (2020)\nessentially required all training data to be separable by a function in the NTRF function class with a\nconstant margin, our result does not require such data separation assumptions, and allows the NTRF\nfunction class to misclassify a small proportion of the training data points\",\nis a big advantage of your analysis. Probably, you should spotlight it more clearly.\n\n- Page 12 in the proof of Theorem 3.4. In the last inequality of the page, could you add that it holds because $-\\ell'(x) \\geq \\ell(x)$ for all $x \\in \\mathbb R^d$. \n\n- Proposition 4.2: you use two notations for the proportion of data not satisfying the margin assumption. You should replace all the $\\sigma$ by $\\rho$. \n\n- Page 18: \"where the equation follows from the fact that\" --> $W^{0}$ should be $W^{t}$\n\n- Before Equation (C.7). Could you add parenthesis around the product with  respect to $l$. Otherwise it is not very clear. \n\n- Could you explain a bit more Assumption 4.1. Is it a strong assumption ? Do you have any insight wether it is verified in practice ? \n\n\nTo summarize, I enjoyed to review this paper. The results are clear and interesting. The paper deserves to be accepted for publication.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "x0rMFWIIMkj", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "- Overview\n\nThis paper greatly relaxed the rate of over-parametrization for deep neural networks.\nPreviously, shallow networks required fewer parameters (polylog(eps)), while deep networks required a large number of parameters (\\Omega (eps^{-14})).\nThis paper shows that faster rates can be achieved in deep networks.\nThe key result is the analysis around the initial values using the Taylor approximation, which is independent of the shallowness of the layers.\nThis result allows the paper to achieve rates similar to existing shallow neural networks.\n\n- Comment.\n\nThe results are impactful, showing that global convergence can be said to be possible with over-parametrization, even in deep neural networks with smaller number of nodes.\nThe paper is carefully written and the differences from existing research and the place of novelty are easy to see.\n\nMy question is what difference does this make to the smooth activation function case?\nLemma 5.1 doesn't seem to make much use of the ReLU property, is the result similar to the smooth case in this case?\n\nAnother question relates to optimality.\nIs it possible to give an additional analysis of the theoretical limitations of the rates obtained here to see if they can be further improved?\n\nThe other one, which is not that important, is the value of 4^L that appears in Theorem 3.4.\nThis value will be a major obstacle to thinking about deep neural nets, but I wonder if it can be explained.", "extra_scores": {}, "extra_text": {}}, {"review_id": "2tM2Kvbvs4H", "reviewer": "AnonReviewer3", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper extends an existing proof for the sufficiency of polylogarithmic width for sharp learning guarantees of ReLU networks trained by (stochastic) gradient descent from shallow networks to deep networks. The theoretical analysis links the convergence of GD and SGD to the width of the network. The paper shows that polylogarithmic width is enough to give reasonable guarantees also for deep neural networks. It furthermore provides a generalisation bound in terms of network width.\n\nThe paper states a clearly formulated contribution and provides rigorous proofs for the claims stated. The analysis highly relies on the radius R of the NTRF function class and the authors provide a discussion showing the connection of the requirements on data separability to the values that R can take. The main lemma behind the proof and the sketch of the proof is also presented and explained.\n\nThe paper lacks a discussion of the applicability of the theory (e.g., how limiting are the assumptions of  the equal width layers, normalization by square root of m and the input norms being bounded by 1?), including a discussion on how the results could be generalized would be required. Also, since the paper extends a result on shallow networks to deep networks it should be discussed how depth affects the results. The generalization guarantees provided in this paper are vacuous without strict assumptions on data separability, as the authors state. However, it remains unclear whether the guarantee is non-vacuous for separable data. Could the authors argue whether the bound is non-vacuous for separable data?\n\nBut overall the contribution deems to be interesting still, so I suggest to accept the paper. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "2_xEAqlEuUc", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies optimization and generalization properties of deep relu networks trained with (stochastic) gradient descent on the logistic loss in the neural tangent kernel (NTK) regime. By using a new analysis that makes the \"linearized\" approximation as well as the L2 norm of the model in the approximate \"random feature\" kernel more explicit, the authors obtain results where the width only depends poly-logarithmically on the number of samples and 1/epsilon, for a test 0-1 loss of epsilon. This improves on previous analysis for deep networks, although it is similar to the two-layer result of Ji & Telgarsky.\n\nI find the analysis interesting, more intuitive and practically relevant than previous studies, thanks to assumptions on the norm of the linearized model and the explicit bound on the approximation from linearization. The obtained guarantees are somewhat incremental are they are in large part similar to Ji & Telgarsky for the two-layer case, and remain in the NTK regime which only provides a limited picture of deep learning performance, but the extension to multiple layers and potentially other activations may be useful for the community, thus I remain on the accept side.\n\ncomments/questions:\n- how do the dependencies of m and n on R or gamma compare to Ji & Telgarsky? more discussions on this comparisons at the end of sections 3.1 and 3.2 would be welcome\n- the gap in sample complexity between GD and SGD is somewhat surprising (both the 1/eps^2 and the exponential dependency on L), is this just an artefact of the GD analysis in the generalization bound?\n- in section 2, is the factor m^1/2 in the definition of f_W standard? how does this parameterization compare to previous works? (it seems like it may compensate the m^{-1/2} from the initialization of the first layer, which is often not present in other works, but this should be further discussed)\n- in prop 4.4, it would be interesting to compare the obtained results to a simple linear model in the class NTRF, to see the cost of ensuring good linear approximation: does linear approximation require a larger m than what is needed just for good approximation of the infinite width kernel?\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the convergence rate and generalization of deep ReLU networks trained with gradient descent and SGD in the NTK regime. Although the analysis technique is not really novel and heavily relies on past results, the paper is easy to follow and does provide some nice improvements compared to prior work (e.g. it require less overparametrization, and the NTRF function class is allowed to misclassify a fraction of the training data). Some of the results are very incremental, e.g. the generalization bound for GD seems to simply combine existing bounds on the Rademacher complexity from Bartlett et al. 2017 and from Cao et al. 2019. Nevertheless, the paper does have the potential to yield further improvements in the field and I therefore recommend acceptance as a poster.
Decision: Accept (Poster)