HOW MUCH OVER-PARAMETERIZATION IS SUFFI-
Year: 2021

Abstract:
A recent line of research on deep learning focuses on the extremely overparameterized 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 ́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 ́1. Our results push the study of over-parameterized deep neural networks towards more practical settings.

heading: 1 INTRODUCTION
text: 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 a 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-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 over-parameterized deep neural networks can be characterized by a 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-Zhu et al., 2019b; Zou et 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 al. (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. ∗Equal contribution.
The typical requirement on the network width is a high degree polynomial of the training sample size n and the inverse of the target error ´1. As there still remains a huge gap between such network width requirement and the practice, many attempts have been made to improve the overparameterization 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 a mild over-parameterization is still an open problem.
In this paper, we resolve this open problem by showing that polylogarithmic network width is sufficient to learn DNNs. In particular, unlike the existing works that require the DNNs to behave very close to a linear model (up to 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 on the linear approximation error, a milder condition on the network width and tighter bounds on the convergence rate and generalization error can be proved. We summarize our contributions as 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), a set of linear functions over random features. Specifically, we prove that GD can learn deep ReLU networks with width m “ polypRq to compete with the best function in NTRF function class, where R is the radius of the NTRF function class.
• We also establish the generalization guarantees for both GD and SGD in the same setting. Specifically, we prove a diminishing statistical error for a wide range of network width m P prΩp1q,8q, while most of the previous generalization bounds in the NTK regime only works in the setting where the network widthm is much greater than the sample size n. Moreover, we establish rOp ´2q rOp ´1q 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 if a large fraction of the training data are well separated, the best function in the NTRF function class with radius R “ rOp1q can learn the training data with error up to . This together with our optimization and generalization guarantees immediately suggests that deep ReLU networks can be learned with network width m “ rΩp1q, which has a logarithmic dependence on the target error 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 a small proportion of the training data.
For the ease of comparison, we summarize our results along with the most related previous results in Table 1, in terms of data assumption, the over-parameterization 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 polylogpn, ´1q network width. Notation. For two scalars a and b, we denote a^ b “ minta, bu. For a vector x P Rd we use }x}2 to denote its Euclidean norm. For a matrix X, we use }X}2 and }X}F to denote its spectral norm and Frobenius norm respectively, and denote by Xij 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 xX,Yy “ ř
i,jXijYij .
Given a collection of matrices W “ tW1, ¨ ¨ ¨ ,WLu P bLl“1Rmlˆm 1 l and a function fpWq over bLl“1Rmlˆm 1 l , we define by∇WlfpWq the partial gradient of fpWq with respect to Wl and denote ∇WfpWq “ t∇WlfpWquLl“1. We also denote BpW, τq “ W1 : maxlPrLs }W1l ´Wl}F ď τ ( for τ ě 0. For two collection of matrices A “ tA1, ¨ ¨ ¨ ,Anu, B “ tB1, ¨ ¨ ¨ ,Bnu, we denote xA,By “
řn i“1xAi,Biy and }A}2F “ řn i“1 }Ai}2F .
Algorithm 1 Gradient descent with random initialization Input: Number of iterations T , step size η, training set S “ tpxi, yiqni“1u, initialization Wp0q for t “ 1, 2, . . . , T do
Update Wptq “Wpt´1q ´ η ¨∇WLSpWpt´1qq. end for Output: Wp0q, . . . ,WpT q.
Given two sequences txnu and tynu, we denote xn “ Opynq if |xn| ď C1|yn| for some absolute positive constant C1, xn “ Ωpynq if |xn| ě C2|yn| for some absolute positive constant C2, and xn “ Θpynq if C3|yn| ď |xn| ď C4|yn| for some absolute constants C3, C4 ą 0. We also use rOp¨q, rΩp¨q to hide logarithmic factors inOp¨q and Ωp¨q respectively. Additionally, we denote xn “ polypynq if xn “ OpyDn q for some positive constant D, and xn “ polylogpynq if xn “ polyplogpynqq.

heading: 2 PRELIMINARIES ON LEARNING NEURAL NETWORKS
text: 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.e., GD and SGD with random initialization.
Neural network function. Given an input x P Rd, the output of deep fully-connected ReLU network is defined as follows,
fWpxq “ m1{2WLσpWL´1 ¨ ¨ ¨σpW1xq ¨ ¨ ¨ q, where W1 P Rmˆd, W2, ¨ ¨ ¨ ,WL´1 P Rmˆm, WL P R1ˆm, and σpxq “ maxt0, xu 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, as long as the smallest width satisfies our overparameterization condition. We denote the collection of all weight matrices as W “ tW1, . . . ,WLu. Loss function. Given training dataset txi, yiui“1,...,n with input xi P Rd and output yi P t´1,`1u, we define the training loss function as
LSpWq “ 1
n
n ÿ i“1 LipWq,
where LipWq “ ` ` yifWpxiq ˘ “ log ` 1` expp´yifWpxiqq ˘ is defined as the cross-entropy loss.
Algorithms. We consider both GD and SGD with Gaussian random initialization. These two algorithms are displayed in Algorithms 1 and 2 respectively. Specifically, the entries in Wp0q1 , ¨ ¨ ¨ ,W p0q L´1 are generated independently from univariate Gaussian distributionNp0, 2{mq and the entries in Wp0qL are generated independently from Np0, 1{mq. For GD, we consider using the full gradient to update the model parameters. For SGD, we use a 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., 2019b; Cao and Gu, 2019).
Algorithm 2 Stochastic gradient desecent (SGD) with random initialization Input: Number of iterations n, step size η, initialization Wp0q for i “ 1, 2, . . . , n do
Draw pxi, yiq from D and compute the corresponding gradient∇WLipWpi´1qq. Update Wpiq “Wpi´1q ´ η ¨∇WLipWpi´1qq.
end for Output: Randomly choose xW uniformly from tWp0q, . . . ,Wpn´1qu.

heading: 3 MAIN THEORY
text: 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 }xi}2 “ 1, i “ 1, . . . , n.
This assumption has been widely made in many previous works (Allen-Zhu et al., 2019b;c; Du et al., 2019b;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, we give the definition of Neural Tangent Random Feature (NTRF) (Cao and Gu, 2019), which characterizes the functions learnable by over-parameterized ReLU networks.
Definition 3.2 (Neural Tangent Random Feature, (Cao and Gu, 2019)). Let Wp0q be the initialization weights, and FWp0q,Wpxq “ fWp0qpxq ` x∇fWp0qpxq,W ´Wp0qy be a function with respect to the input x. Then the NTRF function class is defined as follows
FpWp0q, Rq “ FWp0q,Wp¨q : W P BpWp0q, R ¨m´1{2q ( .
The function class FWp0q,Wpxq 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, we use the NTRF function class as a reference class to measure the difficulty of a learning problem. In what follows, we 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 1 and 2).

heading: 3.1 GRADIENT DESCENT
text: The following theorem establishes the optimization guarantee of GD for training deep ReLU networks for binary classification. Theorem 3.3. For δ,R ą 0, let NTRF “ infFPFpWp0q,Rq n´1 řn i“1 `ryiF pxiqs be the minimum training loss achievable by functions in FpWp0q, Rq. Then there exists
m˚pδ,R, Lq “ rO ` polypR,Lq ¨ log4{3pn{δq ˘ ,
such that if m ě m˚pδ,R, Lq, with probability at least 1 ´ δ over the initialization, GD with step size η “ ΘpL´1m´1q can train a neural network to achieve at most 3 NTRF training loss within T “ O `
L2R2 ´1NTRF ˘ iterations.
Theorem 3.3 shows that the deep ReLU network trained by GD can compete with the best function in the NTRF function class FpWp0q, Rq if the network width has a polynomial dependency in R and L and a logarithmic dependency in n and 1{δ. Moreover, if the NTRF function class with R “ rOp1q can learn the training data well (i.e., NTRF is less than a small target error ), a polylogarithmic (in terms of n and ´1) network width suffices to guarantee the global convergence of GD, which directly improves over-paramterization condition in the most related work (Cao and Gu, 2019). Besides, we 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)
essentially required all training data to be separable by a function in the NTRF function class with a constant margin, our result does not require such data separation assumptions, and allows the NTRF function class to misclassify a small proportion of the training data points∗.
We now characterize the generalization performance of neural networks trained by GD. We denote L0´1D pWq “ Epx,yq„Dr1tfWpxq ¨ y ă 0us as the expected 0-1 loss (i.e., expected error) of fWpxq. Theorem 3.4. Under the same assumptions as Theorem 3.3, with probability at least 1´δ, the iterate Wptq of Algorithm 1 satisfies that
L0´1D pW ptqq ď 2LSpWptqq ` rO
˜
4LL2R
c
m n ^ ˜ L3{2R? n ` L 11{3R4{3 m1{6 ¸¸ `O ˜ c logp1{δq n ¸
for all t “ 0, . . . , T .
Theorem 3.4 shows that the test error of the trained neural network can be 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 4LL2R a m{n and L3{2R{ ? n` L11{3R4{3{m1{6. Depending on the network width m, one of these two terms will be the dominating term and diminishes for large n: (1) if m “ opnq, the statistical error will be 4LL2R a
m{n, and diminishes as n increases; and (2) if m “ Ωpnq, the statistical error is L3{2R{ ? n` L11{3R4{3{m1{6, and again goes to zero as n increases. Moreover,
in this paper we have a specific focus on the setting m “ rOp1q, under which Theorem 3.4 gives a statistical error of order rOpn´1{2q. This distinguishes our result from previous generalization bounds for deep networks (Cao and Gu, 2020; 2019), which cannot be applied to the setting m “ rOp1q. We note that for two-layer ReLU networks (i.e., L “ 2) Ji and Telgarsky (2020) proves a tighter rOp1{n1{2q generalization error bound regardless of the neural networks width m, while our result (Theorem 3.4), in the two-layer case, can only give rOp1{n1{2q generalization error bound when m “ rOp1q or m “ rΩpn3q. 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-homogeneous property of the neural network, which restricted their theory in two-layer cases. An interesting research direction is to explore whether a rOp1{n1{2q generalization error bound can be also established for deep networks (regardless of the network width), which we will leave it as a future work.

heading: 3.2 STOCHASTIC GRADIENT DESCENT
text: Here we study the performance of SGD for training deep ReLU networks. The following theorem establishes a generalization error bound for the output of SGD. Theorem 3.5. For δ,R ą 0, let NTRF “ infFPFpWp0q,Rq n´1 řn i“1 `ryiF pxiqs be the minimum training loss achievable by functions in FpWp0q, Rq. Then there exists
m˚pδ,R, Lq “ rO ` polypR,Lq ¨ log4{3pn{δq ˘ ,
such that if m ě m˚pδ,R, Lq, with probability at least 1 ´ δ, SGD with step size η “ Θ ` m´1 ¨ pLR2n´1 ´1NTRF ^ L´1q ˘ achieves
ErL0´1D pxWqs ď 8L2R2 n ` 8 logp2{δq n ` 24 NTRF,
where the expectation is taken over the uniform draw of xW from tWp0q, . . . ,Wpn´1qu.
For any ą 0, Theorem 3.5 gives a rOp ´1q sample complexity for deep ReLU networks trained with SGD to achieveOp NTRF` q 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 n “ rOp ´2q to n “ rOp ´1q; and (2) the overparamterization condition is improved from m ě polyp ´1q to m “ rΩp1q. ∗A detailed discussion is given in Section 4.2.

heading: 4 DISCUSSION ON THE NTRF CLASS
text: Our theoretical results in Section 3 rely on the radius (i.e.,R) of the NTRF function classFpWp0q, Rq and the minimum training loss achievable by functions in FpWp0q, Rq, i.e., NTRF. Note that a larger R naturally implies a smaller NTRF, but also leads to worse conditions on m. In this section, for any (arbitrarily small) target error rate ą 0, we discuss various data assumptions studied in the literature under which our results can lead to Op q training/test errors, and specify the network width requirement.

heading: 4.1 DATA SEPARABILITY BY NEURAL TANGENT RANDOM FEATURE
text: In this subsection, we consider the setting where a large fraction of the training data can be linearly separated by the neural tangent random features. The assumption is stated as follows.
Assumption 4.1. There exists a collection of matrices U˚ “ tU˚1 , ¨ ¨ ¨ ,U˚Lu satisfying řL l“1 }U˚l }2F “ 1, such that for at least p1´ ρq fraction of training data we have
yix∇fWp0qpxiq,U˚y ě m1{2γ,
where γ is an absolute positive constant† and ρ P r0, 1q.
The following corollary provides an upper bound of NTRF under Assumption 4.1 for some R.
Proposition 4.2. Under Assumption 4.1, for any , δ ą 0, if R ě C “ log1{2pn{δq ` logp1{ q ‰
{γ for some absolute constant C, then with probability at least 1´ δ,
NTRF :“ inf FPFpWp0q,Rq
n´1 n ÿ
i“1 ` ` yiF pxiq ˘ ď ` ρ ¨OpRq.
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., ρ “ 0) (Ji and Telgarsky, 2020; Shamir, 2020). Our results show that for sufficiently small misclassification ratio ρ “ Op q, we have NTRF “ rOp q by choosing the radius parameter R logarithimic in n, δ´1, and ´1. Substituting this result into Theorems 3.3, 3.4 and 3.5, it can be shown that a neural network with width m “ polypL, logpn{δq, logp1{ qq ˘ suffices to guarantee good optimization and generalization performances for both GD and SGD. Consequently, we can obtain that the bounds on the test error for GD and SGD are rOpn´1{2q and rOpn´1q respectively.

heading: 4.2 DATA SEPARABILITY BY SHALLOW NEURAL TANGENT MODEL
text: 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 up¨q : Rd Ñ Rd and γ ě 0 such that }upzq}2 ď 1 for all z P Rd, and
yi
ż
Rd σ1pxz,xiyq ¨ xupzq,xiydµNpzq ě γ
for all i P rns, where µN p¨q 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) uses gradients with respect to the second layer weights instead of the first layer ones. In the following, we mainly focus on Assumption 4.3, while our result can also be generalized to cover the setting in (Cao and Gu, 2020; Frei et al., 2019).
†The factor m1{2 is introduced here since }∇Wp0qfpxiq}F is typically of order Opm 1{2q.
In order to make a fair comparison, we reduce our results for multilayer networks to the two-layer setting. In this case, the neural network function takes form
fWpxq “ m1{2W2σpW1xq. Then we provide the following proposition, which states that Assumption 4.3 implies a certain choice of R “ rOp1q such the the minimum training loss achieved by the function in the NTRF function class FpWp0q, Rq satisfies NTRF “ Op q, where is the target error. Proposition 4.4. Suppose the training data satisfies Assumption 4.3. For any , δ ą 0, let R “ C “ logpn{δq ` logp1{ q ‰
{γ for some large enough absolute constant C. If the neural network width satisfies m “ Ω ` logpn{δq{γ2 ˘
, then with probability at least 1 ´ δ, there exist FWp0q,Wpxiq P FpWp0q, Rq such that ` `
yi ¨ FWp0q,Wpxiq ˘ ď ,@i P rns.
Proposition 4.4 shows that under Assumption 4.3, there exists FWp0q,Wp¨q P FpWp0q, Rq with R “ rOp1{γq such that the cross-entropy loss of FWp0q,Wp¨q at each training data point is bounded by . This implies that NTRF ď . Moreover, by applying Theorem 3.3 with L “ 2, the condition on the neural network width becomes m “ rΩp1{γ8q‡, which matches the results proved in Ji and Telgarsky (2020). Moreover, plugging these results on m and NTRF into Theorems 3.4 and 3.5, we can conclude that the bounds on the test error for GD and SGD are rOpn´1{2q and rOpn´1q respectively.

heading: 4.3 CLASS-DEPENDENT DATA NONDEGENERATION
text: In previous subsections, we have shown that under certain data separation conditions NTRF can be sufficiently small while the corresponding NTRF function class has R of order rOp1q. 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 in Zou et al. (2019). Assumption 4.5. For all i ‰ i1 if yi ‰ yi1 , then }xi ´ xj}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 a good function that achieves training error, in the NTRF function class with a certain choice of R. Proposition 4.6. Under Assumption 4.5, if
R “ Ω ` n3{2φ´1{2 logpnδ´1 ´1q ˘ , m “ rΩ ` L22n12φ´4 ˘ ,
we have NTRF ď with probability at least 1´ δ.
Proposition 4.6 suggests that under Assumption 4.5, in order to guarantee NTRF ď , the size of NTRF function class needs to be Ωpn3{2q. 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 is impossible to be learned with small generalization error. Moreover, we would like to point out our theoretical analysis leads to a sharper over-parameterization condition than that proved in Zou et al. (2019), i.e., m “ rΩ ` n14L16φ´4`n12L16φ´4 ´1 ˘
, if the network depth satisfies L ď rOpn1{3 _ ´1{6q.

heading: 5 PROOF SKETCH OF THE MAIN THEORY
text: 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 m “ rΩpR8q (see (A.1) for more detail). §Specifically, Allen-Zhu et al. (2019b); Zou and Gu (2019) require that any two data points (rather than data points from different classes) are separated by a positive distance. Zou and Gu (2019) shows that this assumption is equivalent to those made in Du et al. (2019b;a), which require that the composite kernel matrix is strictly positive definite.

heading: 5.1 A KEY TECHNICAL LEMMA
text: Here we introduce a key technical lemma used in the proof of Theorem 3.3.
Our proof is based on the key observation that near initialization, the neural network function can be approximated by its first-order Taylor expansion. In the following, we first give the definition of the linear approximation error in a τ -neighborhood around initialization.
apppτq :“ sup i“1,...,n sup W1,WPBpWp0q,τq
ˇ ˇfW1pxiq ´ fWpxiq ´ x∇fWpxiq,W1 ´Wy ˇ ˇ.
If all the iterates of GD stay inside a neighborhood around initialization with small linear approximation error, then we may expect that the training of neural networks should be similar to the training of the corresponding linear model, where standard optimization techniques can be applied. Motivated by this, we 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.
Mpτq :“ sup i“1,...,n sup l“1,...,L sup WPBpWp0q,τq }∇WlfWpxiq}F .
By definition, we can choose W˚ P BpWp0q, Rm´1{2q such that n´1 řn i“1 ` ` yiFWp0q,W˚pxiq ˘ “ NTRF. Then we have the following lemma. Lemma 5.1. Set η “ OpL´1Mpτq´2q. Suppose that W˚ P BpWp0q, τq and Wptq P BpWp0q, τq for all 0 ď t ď t1 ´ 1. Then it holds that
1
t1
t1´1 ÿ t“0 LSpWptqq ď }Wp0q ´W˚}2F ´ }Wpt 1q ´W˚}2F ` 2t1η NTRF t1η ` 3 2 ´ 4 apppτq ˘ .
Lemma 5.1 plays a central role in our proof. In specific, if Wptq P BpWp0q, τq for all t ď t1, then Lemma 5.1 implies that the average training loss is in the same order of NTRF as long as the linear approximation error apppτq is bounded by a positive constant. This is in contrast to the proof in Cao and Gu (2019), where apppτq appears as an additive term in the upper bound of the training loss, thus requiring apppτq “ Op NTRFq to achieve the same error bound as in Lemma 5.1. Since we can show that app “ rOpm´1{6q (See Section A.1), this suggests that m “ rΩp1q is sufficient to make the average training loss in the same order of NTRF.
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-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 rely on homogeneity, and is 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-ReLU activation functions and other network architectures (e.g, Convolutional neural networks and Residual networks).

heading: 5.2 PROOF SKETCH OF THEOREM 3.3
text: 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.1.
Proof sketch of Theorem 3.3. Recall that we choose W˚ P BpWp0q, Rm´1{2q such that n´1
řn i“1 ` ` yiFWp0q,W˚pxiq ˘ “ NTRF. We set τ “ rOpL1{2m´1{2Rq, which is chosen slightly larger than m´1{2R since Lemma 5.1 requires the region BpWp0q, τq to include both W˚ and tWptqut“0,...,t1 . Then by Lemmas 4.1 and B.3 in Cao and Gu (2019) we know that apppτq “ rOpτ4{3m1{2L3q “ rOpR4{3L11{3m´1{6q. Therefore, we can set m “ rΩpR8L22q to ensure that apppτq ď 1{8.
Then we proceed to show that all iterates stay inside the region BpWp0q, τq. Since the L.H.S. of Lemma 5.1 is strictly positive and apppτq ď 1{8, we have for all t ď T ,
}Wp0q ´W˚}2F ´ }Wptq ´W˚}2F ě ´2tη NTRF,
which gives an upper bound of }Wptq ´W˚}F . Then by the choice of η, T , triangle inequality, and a simple induction argument, we see that }Wptq ´Wp0q}F ď m´1{2R ` ? 2Tη NTRF “ rOpL1{2m´1{2Rq, which verifies that Wptq P BpWp0q, τq for t “ 0, . . . , T ´ 1. The second step is to show that GD can find a neural network with at most 3 NTRF training loss within T iterations. To show this, by the bound given in Lemma 5.1 with app ď 1{8, we drop the terms }Wptq ´W˚}2F and rearrange the inequality to obtain
1
T
T´1 ÿ t“0 LSpWptqq ď 1 ηT }Wp0q ´W˚}2F ` 2 NTRF.
We 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 Wp0q, . . . ,WpT´1q achieves an empirical loss at most 3 NTRF.

heading: 6 CONCLUSION
text: 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 a network width condition that is polylogarithmic in the sample size n and the inverse of target error ´1 is sufficient to guarantee the learning of deep ReLU networks. Our results resolve an open question raised in Ji and Telgarsky (2020).

heading: ACKNOWLEDGEMENT
text: 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. DZ 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.

heading: A PROOF OF MAIN THEOREMS
text: In this section we provide the full proof of Theorems 3.3, 3.4 and 3.5.

heading: A.1 PROOF OF THEOREM 3.3
text: 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 κ such that, with probability at least 1 ´ OpnL2q expr´Ωpmτ2{3Lqs, for any τ ď κL´6rlogpmqs´3{2, it holds that
apppτq ď rO ` τ4{3L3m1{2 ˘ , Mpτq ď rOp ? mq.
Proof of Theorem 3.3. Recall that W˚ is chosen such that
1
n
n ÿ i“1 ` ` yiFWp0q,W˚pxiq ˘ “ NTRF
and W˚ P BpWp0q, Rm´1{2q. Note that to apply Lemma 5.1, we need the region BpWp0q, τq to include both W˚ and tWptqut“0,...,t1 . This motivates us to set τ “ rOpL1{2m´1{2Rq, which is slightly larger than m´1{2R. With this choice of τ , by Lemma A.1 we have apppτq “ rOpτ4{3m1{2L3q “ rOpR4{3L11{3m´1{6q. Therefore, we can set
m “ rΩpR8L22q (A.1)
to ensure that apppτq ď 1{8, where rΩp¨q hides polylogarithmic dependencies on network depth L, NTRF function class size R, and failure probability parameter δ. Then by Lemma 5.1, we have with probability at least 1´ δ, we have
}Wp0q ´W˚}2F ´ }Wpt 1q ´W˚}2F ě η
t1´1 ÿ t“0 LSpWptqq ´ 2t1η NTRF (A.2)
as long as Wp0q, . . . ,Wpt 1´1q P BpWp0q, τq. In the following proof we choose η “ ΘpL´1m´1q and T “ rLR2m´1η´1 ´1NTRFs.
We prove the theorem by two steps: 1) we show that all iterates tWp0q, ¨ ¨ ¨ ,WpT qu will stay inside the region BpWp0q, τq; and 2) we show that GD can find a neural network with at most 3 NTRF training loss within T iterations.
All iterates stay inside BpWp0q, τq. We prove this part by induction. Specifically, given t1 ď T , we assume the hypothesis Wptq P BpWp0q, τq holds for all t ă t1 and prove that Wpt1q P BpWp0q, τq. First, it is clear that Wp0q P BpWp0q, τq. Then by (A.2) and the fact that LSpWq ě 0, we have
}Wpt 1q ´W˚}2F ď }Wp0q ´W˚}2F ` 2ηt1 NTRF
Note that T “ rLR2m´1η´1 ´1NTRFs and W˚ P BpWp0q, R ¨m´1{2q, we have L ÿ
l“1 }Wpt 1q l ´W ˚ l }2F “ }Wpt 1q ´W˚}2F ď CLR2m´1,
where C ě 4 is an absolute constant. Therefore, by triangle inequality, we further have the following for all l P rLs,
}Wpt 1q l ´W p0q l }F ď }W pt1q l ´W ˚ l }F ` }W p0q l ´W ˚ l }F
ď ? CLRm´1{2 `Rm´1{2 ď 2 ? CLRm´1{2. (A.3)
Therefore, it is clear that }Wpt 1q l ´W p0q l }F ď 2
? CLRm´1{2 ď τ based on our choice of τ
previously. This completes the proof of the first part.
Convergence of gradient descent. (A.2) implies
}Wp0q ´W˚}2F ´ }WpT q ´W˚}2F ě η ˆ T´1 ÿ
t“0 LSpWptqq ´ 2T NTRF
˙
.
Dividing by ηT on the both sides, we get
1
T
T´1 ÿ t“0 LSpWptqq ď }Wp0q ´W˚}2F ηT ` 2 NTRF ď LR2m´1 ηT ` 2 NTRF ď 3 NTRF,
where the second inequality is by the fact that W˚ P BpWp0q, R ¨ m´1{2q and the last inequality is by our choices of T and η which ensure that Tη ě LR2m´1 ´1NTRF. Notice that T “ rLR2m´1η´1 ´1NTRFs “ OpL2R2 ´1 NTRFq. This completes the proof of the second part, and we are able to complete the proof.

heading: A.2 PROOF OF THEOREM 3.4
text: 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 ESpWq and population surrogate error EDpWq as follows:
ESpWq :“ ´ 1
n
n ÿ i“1 `1 “ yi ¨ fWpxiq ‰ , EDpWq :“ Epx,yq„D ´ `1 “ y ¨ fWpxq ‰( .
The following lemma gives uniform-convergence type of results for ESpWq utilizing the fact that ´`1p¨q is bounded and Lipschitz continuous.
Lemma A.3. For any rR, δ ą 0, suppose that m “ rΩpL12 rR2q ¨ rlogp1{δqs3{2. Then with probability at least 1´ δ, it holds that
|EDpWq ´ ESpWq| ď rO ˜ min # 4LL3{2 rR c m
n , L rR? n ` L
3 rR4{3
m1{6
+¸ `O ˜ c
logp1{δq n
¸
for all W P BpWp0q, rR ¨m´1{2q
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 Wp0q,Wp1q, . . . ,WpT q P BpWp0q, rRm´1{2q with rR “ Op ? LRq. Therefore by Lemma A.3, we have
|EDpWptqq ´ ESpWptqq| ď rO ˜ min # 4LL2R c m n , L3{2R? n ` L 11{3R4{3 m1{6 +¸ `O ˜ c logp1{δq n ¸
for all t “ 0, 1, . . . , T . Note that we have 1tz ă 0u ď ´2`1pzq. Therefore,
EL0´1D pW ptqq ď 2EDpWptqq
ď 2LSpWptqq ` rO ˜ min # 4LL2R c m n , L3{2R? n ` L 11{3R4{3 m1{6 +¸ `O ˜ c logp1{δq n ¸
for t “ 0, 1, . . . , T , where the last inequality is by ESpWq ď LSpWq because ´`1pzq ď `pzq for all z P R. This finishes the proof.

heading: A.3 PROOF OF THEOREM 3.5
text: 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˚ P BpWp0q, Rm´1{2q such that the loss of the corresponding NTRF model FWp0q,W˚pxq achieves NTRF. Lemma A.4. Set η “ OpL´1Mpτq´2q. Suppose that W˚ P BpWp0q, τq and Wpn1q P BpWp0q, τq for all 0 ď n1 ď n´ 1. Then it holds that
}Wp0q ´W˚}2F ´ }Wpn 1q ´W˚}2F ě
´3
2 ´ 4 apppτq
¯ η n1 ÿ
i“1 LipWpi´1qq ´ 2nη NTRF.
We introduce a surrogate loss EipWq “ ´`1ryi ¨ fWpxiqs and its population version EDpWq “ Epx,yq„Dr´`1ry ¨ fWpxqss, which have been used in (Ji and Telgarsky, 2018; Cao and Gu, 2019; Ji and Telgarsky, 2020). Our proof is based on the application of Lemma A.4 and an online-tobatch conversion argument (Cesa-Bianchi et al., 2004; Cao and Gu, 2019; Ji and Telgarsky, 2020). We introduce a surrogate loss EipWq “ ´`1ryi ¨ fWpxiqs and its population version EDpWq “ Epx,yq„Dr´`1py ¨ fWpxqqs, 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
1
n
n ÿ i“1 ` ` yiFWp0q,W˚pxiq ˘ “ NTRF
and W˚ P BpWp0q, Rm´1{2q. To apply Lemma A.4, we need the region BpWp0q, τq to include both W˚ and tWptqut“0,...,t1 . This motivates us to set τ “ rOpL1{2m´1{2Rq, which is slightly larger than m´1{2R. With this choice of τ , by Lemma A.1 we have apppτq “ rOpτ4{3m1{2L3q “ rOpR4{3L11{3m´1{6q. Therefore, we can set
m “ rΩpR8L22q
to ensure that apppτq ď 1{8, where rΩp¨q hides polylogarithmic dependencies on network depth L, NTRF function class size R, and failure probability parameter δ.
Then by Lemma A.4, we have with probability at least 1´ δ,
}Wp0q ´W˚}2F ´ }Wpn 1q ´W˚}2F ě η
n1 ÿ i“1 LipWpi´1qq ´ 2nη NTRF (A.4)
as long as Wp0q, . . . ,Wpn 1´1q P BpWp0q, τq.
We then prove Theorem 3.5 in two steps: 1) all iterates stay inside BpWp0q, τq; and 2) convergence of online SGD.
All iterates stay inside BpWp0q, τq. Similar to the proof of Theorem 3.3, we prove this part by induction. Assuming Wpiq satisfies Wpiq P BpWp0q, τq for all i ď n1 ´ 1, by (A.4), we have
}Wpn 1q ´W˚}2F ď }Wp0q ´W˚}2F ` 2nη NTRF
ď LR2 ¨m´1 ` 2nη NTRF,
where the last inequality is by W˚ P BpWp0q, Rm´1{2q. Then by triangle inequality, we further get
}Wpn 1q l ´W p0q l }F ď }W pn1q l ´W ˚ l }F ` }W˚l ´W p0q l }F
ď }Wpn 1q ´W˚}F ` }W˚l ´W p0q l }F ď Op ? LRm´1{2 `?nη NTRFq.
Then by our choices of η “ Θ ` m´1 ¨ pLR2n´1 ´1NTRF ^ L´1q ˘ , we have }Wpn1q ´Wp0q}F ď 2 ? LRm´1{2 ď τ . This completes the proof of the first part.
Convergence of online SGD. By (A.4), we have
}Wp0q ´W˚}2F ´ }Wpnq ´W˚}2F ě η ˆ n ÿ
i“1 LipWpi´1qq ´ 2n NTRF
˙
.
Dividing by ηn on the both sides and rearranging terms, we get
1
n
n ÿ i“1 LipWpi´1qq ď }Wp0q ´W˚}2F ´ }Wpnq ´W˚}2F ηn ` 2 NTRF ď L2R2 n ` 3 NTRF,
where the second inequality follows from facts that W˚ P BpWp0q, R ¨m´1{2q and η “ Θ ` m´1 ¨ pLR2n´1 ´1NTRF ^L´1q ˘
. By Lemma 4.3 in (Ji and Telgarsky, 2020) and the fact that EipWpi´1qq ď LipWpi´1qq, we have
1
n
n ÿ i“1 L0´1D pW pi´1qq ď 2 n n ÿ i“1 EDpWpi´1qq
ď 8 n
n ÿ i“1 EipWpi´1qq ` 8 logp1{δq n
ď 8L 2R2 n ` 8 logp1{δq n ` 24 NTRF.
This completes the proof of the second part.

heading: B PROOF OF RESULTS IN SECTION 4

heading: B.1 PROOF OF PROPOSITION 4.2
text: We first provide the following lemma which gives an upper bound of the neural network output at the initialization. Lemma B.1 (Lemma 4.4 in Cao and Gu (2019)). Under Assumption 3.1, if m ě C̄L logpnL{δq with some absolute constant C̄, with probability at least 1´ δ, we have
|fWp0qpxiq| ď C a logpn{δq
for some absolute constant C.
Proof of Proposition 4.2. Under Assumption 4.1, we can find a collection of matrices U˚ “ tU˚1 , ¨ ¨ ¨ ,U˚Lu with řL l“1 }U˚l }2F “ 1 such that yix∇fWp0qpxiq,U˚y ě m1{2γ for at least 1 ´ ρ fraction of the training data. By Lemma B.1, for all i P rns we have |fWp0qpxiq| ď C a
logpn{δq for some absolute constant C. Then for any positive constant λ, we have for at least 1´ ρ portion of the data,
yi ` fWp0qpxiq ` x∇fWp0q , λU˚y ˘ ě m1{2λγ ´ C a logpn{δq.
For this fraction of data, we can set
λ “ C 1 “ log1{2pn{δq ` logp1{ q ‰
m1{2γ ,
where C 1 is an absolute constant, and get
m1{2λγ ´ C a logpn{δq ě logp1{ q.
Now we let W˚ “ Wp0q ` λU˚. By the choice of R in Proposition 4.2, we have W˚ P BpWp0q, R ¨ m´1{2q. The above inequality implies that for at least 1 ´ ρ fraction of data, we have ` `
yiFWp0q,W˚pxiq ˘ ď . For the rest data, we have
yi ` fWp0qpxiq ` x∇fWp0q , λU˚y ˘ ě ´C a logpn{δq ´ λ}∇fWp0q}22 ě ´C1R
for some absolute positive constant C1, where the last inequality follows from fact that }∇fWp0q}2 “ rOpm1{2q (see Lemma A.1 for detail). Then note that we use cross-entropy loss, it follows that for this fraction of training data, we have ` `
yiFWp0q,W˚pxiq ˘ ď C2R for some constant C2. Combining the results of these two fractions of training data, we can conclude
NTRF ď n´1 n ÿ
i“1 ` ` yiFWp0q,W˚pxiq ˘ ď p1´ ρq ` ρ ¨OpRq
This completes the proof.

heading: B.2 PROOF OF PROPOSITION 4.4
text: Proof of Proposition 4.4. We are going to prove that Assumption 4.3 implies the existence of a 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 a collection of matrices W “ tW1,W2u satisfying maxt}W1 ´Wp0q1 }F , }W2 ´W p0q 2 }2u ď R ¨m´1{2 such that yi ¨ “ fWp0qpxiq ` x∇W1fWp0q ,W1 ´W p0q 1 y ` x∇W2fWp0q ,W2 ´W p0q 2 y ‰
ě logp2{ q. We first consider∇W1fWp0qpxiq, which has the form
p∇W1fWp0qpxiq ˘ j “ m1{2 ¨ wp0q2,j ¨ σ 1pxwp0q1,j ,xiyq ¨ xi.
Note that wp0q2,j and w p0q 1,j are independently generated from N p0, 1{mq and N p0, 2I{mq respectively, thus we have Pp|wp0q2,j | ě 0.47m´1{2q ě 1{2. By Hoeffeding’s inequality, we know that with probability at least 1 ´ expp´m{8q, there are at least m{4 nodes, whose union is denoted by S, satisfying |wp0q2,j | ě 0.47m´1{2. Then we only focus on the nodes in the set S. Note that W p0q 1 and W p0q 2 are independently generated. Then by Assumption 4.3 and Hoeffeding’s inequality, there exists a function up¨q : Rd Ñ Rd such that with probability at least 1´ δ1,
1
|S| ÿ jPS yi ¨ xupwp0q1,j q,xiy ¨ σ 1pxwp0q1,j ,xiyq ě γ ´
d
2 logp1{δ1q |S| .
Define vj “ upwp0q1,j q{w2,j if |w2,j | ě 0.47m´1{2 and vj “ 0 otherwise. Then we have m ÿ
j“1 yi ¨ wp0q2,j ¨ xvj ,xiy ¨ σ 1pxwp0q1,j ,xiyq “ ÿ jPS yi ¨ xupwp0q1,j q,xiy ¨ σ 1pxwp0q1,j ,xiyq
ě |S|γ ´ a 2|S| logp1{δ1q. Set δ “ 2nδ1 and apply union bound, we have with probability at least 1´ δ{2,
m ÿ j“1 yi ¨ wp0q2,j ¨ xvj ,xiy ¨ σ 1pxwp0q1,j ,xiyq ě |S|γ ´ a 2|S| logp2n{δq.
Therefore, note that with probability at least 1 ´ expp´m{8q, we have |S| ě m{4. Moreover, in Assumption 4.3, by yi P t˘1u and |σ1p¨q|, }up¨q}2, }xi}2 ď 1 for i “ 1, . . . , n, we see that γ ď 1. Then if m ě 32 logpn{δq{γ2, with probability at least 1´ δ{2´ exp ` ´ 4 logpn{δq{γ2 ˘
ě 1´ δ, m ÿ j“1 yi ¨ wp0q2,j ¨ xvj ,xiy ¨ σ 1pxwp0q1,j ,xiyq ě |S|γ{2.
Let U “ pv1,v2, ¨ ¨ ¨ ,vmqJ{ a m|S|, we have
yix∇W1fWp0qpxiq,Uy “ 1 a
|S|
m ÿ j“1 yi ¨ wp0q2,j ¨ xvj ,xiy ¨ σ 1pxwp0q1,j ,xiyq ě a |S|γ 2 ě m 1{2γ 4 ,
where the last inequality is by the fact that |S| ě m{4. Besides, note that by concentration and Gaussian tail bound, we have |fWp0qpxiq| ď C logpn{δq for some absolute constant C. Therefore, let W1 “Wp0q1 ` 4 ` logp2{ q ` C logpn{δq ˘ m´1{2U{γ and W2 “Wp0q2 , we have
yi ¨ “ fWp0qpxiq ` x∇W1fWp0q ,W1 ´W p0q 1 y ` x∇W2fWp0q ,W2 ´W p0q 2 y ‰ ě logp2{ q. (B.1)
Note that }up¨q}2 ď 1, we have }U}F ď 1{0.47 ď 2.2. Therefore, we further have }W1 ´ W p0q 1 }F ď 8.8γ´1 ` logp2{ q ` C logpn{δq ˘
¨ m´1{2. This implies that W P BpWp0q, Rq with R “ O ` log ` n{pδ q ˘ {γ ˘
. Applying the inequality `plogp2{ qq ď on (B.1) gives `pyi ¨ FWp0q,Wpxiqq ď
for all i “ 1, . . . , n. This completes the proof.

heading: B.3 PROOF OF PROPOSITION 4.6
text: Based on our theoretical analysis, the major goal is to show that there exist certain choices of R and m such that the best NTRF model in the function class FpWp0q, Rq can achieve training error. In this proof, we will prove a 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´1
řn i“1 ` ` yiFWp0q,W˚pxiq ˘ ď . In order to do so, we consider training the NTRF model via a different surrogate loss function. Specifically, we consider squared hinge loss r`pxq “ ` maxtλ´ x, 0u ˘2
, where λ denotes the target margin. In the later proof, we choose λ “ logp1{ q ` 1 such that the condition r`pxq ď 1 can guarantee that x ě logp q. 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
rLSpWq “ 1
n
n ÿ
i“1
r` ` yiFWp0q,Wpxiq ˘ .
Moreover, for simplicity, we only consider optimizing parameter in the last hidden layer (i.e., WL´1). Then the gradient flow can be formulated as
dWL´1ptq dt “ ´∇WL´1 rLSpWptqq, dWlptq dt “ 0 for any l ‰ L´ 1.
Note that the NTRF model is a linear model, thus by Definition 3.2, we have
∇WL´1 rLSpWptqq “ yir`1 ` yiFWp0q,Wptqpxiq ˘ ¨∇WL´1FWp0q,Wptqpxiq
“ yir`1 ` yiFWp0q,Wptqpxiq ˘ ¨∇ W p0q L´1 fWp0qpxiq. (B.2)
Then it is clear that∇WL´1 rLSpWptqq 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 an upper bound of the NTRF model output at the initialization.
Then we provide the following lemma which characterizes a lower bound of the Frobenius norm of the partial gradient∇WL´1 rLSpWq.
Lemma B.2 (Lemma B.5 in Zou et al. (2019)). Under Assumptions 3.1 and 4.5, if m “ rΩpn2φ´1q, then for all t ě 0, with probability at least 1´ exp ` ´Opmφ{nq ˘
, there exist a positive constant C such that
}∇WL´1 rLSpWptqq}2F ě Cmφ
n5
„ n ÿ
i“1
r`1 ` yiFWp0q,Wptqpxiq ˘
2
.
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 ∇rLSpWq can be regarded as a type of the gradient for neural network model at the initialization (i.e.,∇WL´1LSpWp0qq) is valid. Now we are ready to present the proof.
Proof of Proposition 4.6. Recall that we only consider training the last hidden weights, i.e., 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 FpWp0q, Rq around the initialization, i.e., achieving n´1
řn i“1 ` ` yiFWp0q,W˚pxiq ˘ ď . Let Wptq be the weights at time t, gradient flow implies that
drLSpWptqq dt “ ´}∇WL´1 rLSpWptqq}2F ď ´ Cmφ n5
ˆ n ÿ
i“1
r`1 ` yiFWp0q,Wptqpxiq ˘
˙2
“ 4Cmφ rLSpWptqq n3 ,
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 r`1p¨q “ ´2 b
r`p¨q. Solving the above inequality gives
rLSpWptqq ď rLSpWp0qq ¨ exp ˆ ´ 4Cmφt n3 ˙ . (B.3)
Then, set T “ O ` n3m´1φ´1 ¨ logprLSpWp0qq{ 1q ˘ and 1 “ 1{n, we have rLSpWptqq ď 1. Then it follows that r` `
yiFWp0q,Wptqpxiq ˘ ď 1, which implies that yiFWp0q,Wptqpxiq ě logp q and thus n´1
řn i“1 ` ` yiFWp0q,W˚pxiq ˘ ď . Therefore, WpT q is exactly the NTRF model we are looking for.
The next step is to characterize the distance between WpT q and Wp0q in order to characterize the quantity of R. Note that }∇WL´1 rLSpWptqq}2F ě 4CmφrLSpWptqq{n3, we have
d
b
rLSpWptqq dt “ ´ }∇WL´1 rLSpWptqq}2F
2
b rLSpWptqq ď ´}∇WL´1 rLSpWptqq}F ¨
C1{2m1{2φ1{2
n3{2 .
Taking integral on both sides and rearranging terms, we have ż T
t“0 }∇WL´1 rLSpWptqq}Fdt ď
n3{2 C1{2m1{2φ1{2 ¨ ˆ b rLSpWp0qq ´ b rLSpWptqq ˙ .
Note that the L.H.S. of the above inequality is an upper bound of }Wptq ´Wp0q}F , we have for any t ě 0,
}Wptq ´Wp0q}F ď n3{2 C1{2m1{2φ1{2 ¨ b rLSpWp0qq “ O ˆ n3{2 log ` n{pδ q ˘ m1{2φ1{2 ˙ ,
where the second inequality is by Lemma B.1 and our choice of λ “ logp1{ q ` 1. This implies that there exists a point W˚ within the class FpWp0q, Rq with
R “ O ˆ n3{2 log ` n{pδ q ˘
φ1{2
˙
such that
NTRF :“ n´1 n ÿ
i“1 ` ` yiFWp0q,W˚pxiq ˘ ď .
Then by Theorem 3.3, and, more specifically, (A.1), we can compute the minimal required neural network width as follows,
m “ rΩpR8L22q “ rΩ ˜ L22n12
φ4
¸
.
This completes the proof.

heading: C PROOF OF TECHNICAL LEMMAS
text: Here we provide the proof of Lemmas 5.1, A.3 and A.4.

heading: C.1 PROOF OF LEMMA 5.1
text: 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.e., Wpt`1q “ Wptq ´ η∇WLSpWptqq, we have the following calculation.
}Wptq ´W˚}2F ´ }Wpt`1q ´W˚}2F
“ 2η n
n ÿ i“1 xWptq ´W˚,∇WLipWptqqy loooooooooooooooooooooomoooooooooooooooooooooon
I1
´ η2 L ÿ
l“1 }∇WlLSpWptqq}2F loooooooooooooomoooooooooooooon
I2
, (C.1)
where the equation follows from the fact that LSpWptqq “ n´1 řn i“1 LipWptqq. In what follows, we first bound the term I1 on the R.H.S. of (C.1) by approximating the neural network functions with linear models. By assumption, for t “ 0, . . . , t1 ´ 1, Wptq,W˚ P BpWp0q, τq. Therefore by the definition of apppτq,
yi ¨ x∇fWptqpxiq,Wptq ´W˚y ď yi ¨ ` fWptqpxiq ´ fW˚pxiq ˘ ` apppτq (C.2)
Moreover, we also have
0 ď yi ¨ ` fW˚pxiq ´ fWp0qpxiq ´ x∇fWp0qpxiq,W˚ ´Wp0qy ˘ ` apppτq “ yi ¨ ` fW˚pxiq ´ FWp0q,W˚pxiq ˘ ` apppτq, (C.3)
where the equation follows by the definition of FWp0q,W˚pxq. Adding (C.3) to (C.2) and canceling the terms yi ¨ fW˚pxiq, we obtain that
yi ¨ x∇fWptqpxiq,Wptq ´W˚y ď yi ¨ ` fWptqpxiq ´ FWp0q,W˚pxiq ˘ ` 2 apppτq. (C.4)
We can now give a lower bound on first term on the R.H.S. of (C.1). For i “ 1, . . . , n, applying the chain rule on the loss function gradients and utilizing (C.4), we have
xWptq ´W˚,∇WLipWptqqy “ `1 ` yifWptqpxiq ˘ ¨ yi ¨ xWptq ´W˚,∇WfWptqpxiqy ě `1 `
yifWptqpxiq ˘ ¨ ` yifWptqpxiq ´ yifW˚pxiq ` 2 apppτq ˘
ě p1´ 2 apppτqq` ` yifWptqpxiq ˘ ´ ` ` yiFWp0q,W˚pxiq ˘ , (C.5)
where the first inequality is by the fact that `1 ` yifWptqpxiq ˘ ă 0, the second inequality is by convexity of `p¨q and the fact that ´`1 `
yifWptqpxiq ˘ ď ` ` yifWptqpxiq ˘ .
We now proceed to bound the term I2 on the R.H.S. of (C.1). Note that we have `1p¨q ă 0, and therefore the Frobenius norm of the gradient∇WlLSpWptqq can be upper bounded as follows,
}∇WlLSpWptqq}F “ › › ›
›
1
n
n ÿ i“1 `1 ` yifWptqpxiq ˘ ∇WlfWptqpxiq › › › › F
ď 1 n
n ÿ i“1 ´`1 ` yifWptqpxiq ˘ ¨ }∇WlfWptqpxiq}F ,
where the inequality follows by triangle inequality. We now utilize the fact that cross-entropy loss satisfies the inequalities ´`1p¨q ď `p¨q and ´`1p¨q ď 1. Therefore by definition of Mpτq, we have
L ÿ l“1 }∇WlLSpWptqq}2F ď O ` LMpτq2 ˘ ¨ ˆ 1 n n ÿ i“1 ´`1 ` yifWptqpxiq ˘ ˙2
ď O ` LMpτq2 ˘ ¨ LSpWptqq. (C.6)
Then we can plug (C.5) and (C.6) into (C.1) and obtain
}Wptq ´W˚}2F ´ }Wpt`1q ´W˚}2F
ě 2η n
n ÿ
i“1
”
p1´ 2 apppτqq` ` yifWptqpxiq ˘ ´ ` ` yiFWp0q,W˚pxiq ˘
ı
´O ` η2LMpτq2 ˘ ¨ LSpWptqq
ě „ 3
2 ´ 4 apppτq

ηLSpWptqq ´ 2η
n
n ÿ i“1 ` ` yiFWp0q,W˚pxiq ˘ ,
where the last inequality is by η “ OpL´1Mpτq´2q and merging the third term on the second line into the first term. Taking telescope sum from t “ 0 to t “ t1 ´ 1 and plugging in the definition 1 n řn i“1 ` ` yiFWp0q,W˚pxiq ˘ “ NTRF completes the proof.

heading: C.2 PROOF OF LEMMA A.3
text: Proof of Lemma A.3. We first denote W “ BpWp0q, rR ¨ m´1{2q, and define the corresponding neural network function class and surrogate loss function class as F “ tfWpxq : W P Wu and G “ t´`ry ¨ fWpxqs : W PWu respectively. By standard uniform convergence results in terms of empirical Rademacher complexity (Bartlett and Mendelson, 2002; Mohri et al., 2018; Shalev-Shwartz and Ben-David, 2014), with probability at least 1´ δ we have
sup WPW |ESpWq ´ EDpWq| “ sup WPW
ˇ
ˇ
ˇ
ˇ
ˇ ´ 1 n
n ÿ i“1 `1 “ yi ¨ fWpxiq ‰ ` Epx,yq„D`1 “ y ¨ fWpxq ‰
ˇ
ˇ
ˇ
ˇ
ˇ
ď 2pRnpGq ` C1
c
logp1{δq n ,
where C1 is an absolute constant, and
pRnpGq “ Eξi„Unifpt˘1uq
#
sup WPW
1
n
n ÿ i“1 ξi` 1“yi ¨ fWpxiq ‰
+
is the empirical Rademacher complexity of the function class G. We now provide two bounds on pRnpGq, whose combination gives the final result of Lemma A.3. First, by Corollary 5.35 in (Vershynin, 2010), with probability at least 1 ´ L ¨ expp´Ωpmqq, }Wp0ql }2 ď 3 for all l P rLs. Therefore for all W PW , we have }Wl}2 ď 4. Moreover, standard concentration inequalities on the norm of the first row of Wp0ql also implies that }Wl}2 ě 0.5 for all W PW and l P rLs. Therefore, an adaptation of the bound in (Bartlett et al., 2017)¶ gives
pRnpFq ď rO ˜
sup WPW
# m1{2? n ¨ « L ź
l“1 }Wl}2
ff ¨ « L ÿ
l“1
}WJl ´W p0qJ l } 2{3 2,1
}Wl}2{32
ff3{2+¸
ď rO ˜
sup WPW
#
4Lm1{2? n ¨ « L ÿ l“1 p ? m ¨ }WJl ´W p0qJ l }F q 2{3
ff3{2+¸
ď rO ˜ 4LL3{2 rR ¨ c m
n
¸
. (C.7)
We now derive the second bound on pRnpGq, which is inspired by the proof provided in (Cao and Gu, 2020). Since y P t`1, 1u, |`1pzq| ď 1 and `1pzq is 1-Lipschitz continuous, by standard empirical Rademacher complexity bounds (Bartlett and Mendelson, 2002; Mohri et al., 2018; Shalev-Shwartz and Ben-David, 2014), we have
pRnpGq ď pRnpFq “ Eξi„Unifpt˘1uq
«
sup WPW
1
n
n ÿ i“1 ξifWpxiq
ff
,
¶Bartlett et al. (2017) only proved the 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 ´`1p¨q function, which is bounded and 1-Lipschitz continuous. The proof in our setting is therefore exactly the same as the proof given in (Bartlett et al., 2017), and we can apply Theorem 3.3 and Lemma A.5 in (Bartlett et al., 2017) to obtain the desired bound we present here.
where pRnpFq is the empirical Rademacher complexity of the function class F . We have
pRnrFs ď Eξ
#
sup WPW
1
n
n ÿ i“1 ξi “ fWpxiq ´ FWp0q,Wpxiq ‰
+
looooooooooooooooooooooooooooomooooooooooooooooooooooooooooon
I1
`Eξ
#
sup WPW
1
n
n ÿ i“1 ξiFWp0q,Wpxiq
+
loooooooooooooooooooomoooooooooooooooooooon
I2
,
(C.8)
where FWp0q,Wpxq “ fWp0qpxq ` @ ∇WfWp0qpxq,W´Wp0q D
. For I1, by Lemma 4.1 in (Cao and Gu, 2019), with probability at least 1´ δ{2 we have
I1 ď max iPrns
ˇ ˇfWpxiq ´ FWp0q,Wpxiq ˇ ˇ ď O ` L3 rR4{3m´1{6 a logpmq ˘ ,
For I2, note that Eξ “ supWPW řn i“1 ξifWp0qpxiq ‰ “ 0. By Cauchy-Schwarz inequality we have
I2 “ 1
n
L ÿ l“1 Eξ
#
sup }ĂWl}Fď rRm´1{2 Tr
«
ĂWJl
n ÿ i“1 ξi∇WlfWp0qpxiq
ff+
ď rRm´1{2
n
L ÿ l“1 Eξ
« ›
›
›
›
›
n ÿ i“1 ξi∇WlfWp0qpxiq
›
›
›
›
›
F
ff
.
Therefore
I2 ď rRm´1{2
n
L ÿ
l“1
g f
f eEξ
« ›
›
›
›
›
n ÿ i“1 ξi∇WlfWp0qpxiq
›
›
›
›
›
2
F
ff
“ rRm´1{2
n
L ÿ
l“1
g f
f
e
n ÿ
i“1
› ›∇WlfWp0qpxiq › ›
2
F
ď O ˆ L ¨ rR? n ˙ ,
where we apply Jensen’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
pRnrFs ď rO ˆ L rR? n ` L 3 rR4{3 m1{6 ˙ .
Further combining this bound with (C.7) and recaling δ completes the proof.

heading: C.3 PROOF OF LEMMA A.4
text: Proof of Lemma A.4. Different from the proof of Lemma 5.1, online SGD only queries one data to update the model parameters in each iteration, i.e., Wi`1 “Wi ´ η∇Li`1pWpiqq. By this update rule, we have
}Wpiq ´W˚}2F ´ }Wpi`1q ´W˚}2F
“ 2ηxWpiq ´W˚,∇WLi`1pWpiqqy ´ η2 L ÿ
l“1 }∇WlLi`1pWpiqq}2F . (C.9)
With exactly the same proof as (C.5) in the proof of Lemma 5.1, we have
xWptq ´W˚,∇WLipWptqqy ě p1´ 2 apppτqq` ` yifWptqpxiq ˘ ´ ` ` yiFWp0q,W˚pxiq ˘ , (C.10)
for all i “ 0, . . . , n1 ´ 1. By the fact that ´`1p¨q ď `p¨q and ´`1p¨q ď 1, we have L ÿ
l“1 }∇WlLi`1pWpiqq}2F ď
L ÿ l“1 ` ` yi`1fWtpxi`1q ˘ ¨ }∇WlfWpiqpxi`1q}2F
ď O ` LMpτq2 ˘ ¨ Li`1pWpiqq. (C.11)
Then plugging (C.10) and (C.11) into (C.9) gives
}Wpiq ´W˚}2F ´ }Wpi`1q ´W˚}2F ě p2´ 4 apppτqqηLi`1pWpiqq ´ 2η` ` yiFWp0q,W˚pxiq ˘ ´O ` η2LMpτq2 ˘ Li`1pWpiqq
ě p3 2 ´ 4 apppτqqηLi`1pWpiqq ´ 2η` ` yiFWp0q,W˚pxiq ˘ ,
where the last inequality is by η “ OpL´1Mpτq´2q and merging the third term on the second line into the first term. Taking telescope sum over i “ 0, . . . , n1 ´ 1, we obtain
}Wp0q ´W˚}2F ´ }Wpn 1q ´W˚}2F
ě ´3
2 ´ 4 apppτq
¯ η n1 ÿ
i“1 LipWpi´1qq ´ 2η
n1 ÿ i“1 ` ` yiFWp0q,W˚pxiq ˘ .
ě ´3
2 ´ 4 apppτq
¯ η n1 ÿ
i“1 LipWpi´1qq ´ 2η
n ÿ i“1 ` ` yiFWp0q,W˚pxiq ˘ .
ě ´3
2 ´ 4 apppτq
¯ η n1 ÿ
i“1 LipWpi´1qq ´ 2nη NTRF.
This finishes the proof.

heading: D EXPERIMENTS
text: In this section, we conduct some simple experiments to validate our theory. Since our paper mainly focuses on binary classification, we use a subset of the original CIFAR10 dataset (Krizhevsky et al., 2009), which only has two classes of images. We train a 5-layer fullyconnected ReLU network on this binary classification dataset with different sample sizes (n P t100, 200, 500, 1000, 2000, 5000, 10000u), and plot the minimal neural network width that is required to achieve zero training error in Figure 1 (solid line). We also plot Opnq,Oplog3pnqq,Oplog2pnqq and Oplogpnqq in dashed line for reference. It is evident that the required network width to achieve zero training error is polylogarithmic on the sample size n, which is consistent with our theory.

Review summaries:
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.

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.