Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
Authors: Atsushi Nitanda
Geoffrey Chinot
Taiji Suzuki
Venue:  (2020)
Keywords: gradient descent
neural network
over-parameterization

Abstract: Recently, several studies have proven the global convergence and generalization abilities of the gradient descent method for two-layer ReLU networks. Most studies especially focused on the regression problems with the squared loss function, except for a few, and the importance of the positivity of the neural tangent kernel has been pointed out. However, the performance of gradient descent on classification problems using the logistic loss function has not been well studied, and further investigation of this problem structure is possible. In this work, we demonstrate that the separability assumption using a neural tangent model is more reasonable than the positivity condition of the neural tangent kernel and provide a refined convergence analysis of the gradient descent for two-layer networks with smooth activations. A remarkable point of our result is that our convergence and generalization bounds have much better dependence on the network width in comparison to related studies. Consequently, our theory significantly enlarges a class of over-parameterized networks with provable generalization ability, with respect to the network width, while most studies require much higher over-parameterization.

Under review as a conference paper at ICLR 2020
GRADIENT DESCENT CAN LEARN LESS OVER- PARAMETERIZED TWO-LAYER NEURAL NETWORKS ON CLASSIFICATION PROBLEMS
Anonymous authors Paper under double-blind review
ABSTRACT
Recently, several studies have proven the global convergence and generalization abilities of the gradient descent method for two-layer ReLU networks. Most studies especially focused on the regression problems with the squared loss function, ex- cept for few, and the importance of the positivity of the neural tangent kernel has been pointed out. However, the performance of gradient descent classification problems using the logistic loss function has not been well studied, and further investigation of this problem structure is possible. In this work, we demonstrate that the separability assumption using neural tangent model is more reasonable than the positivity condition of the neural tangent kernel and provide a refined convergence analysis of the gradient descent for two-layer networks with smooth activations. A remarkable point of our result is that convergence and general- ization bounds have much better dependence on the network width in comparison related studies. Consequently, our theory provides a generalization guarantee for less over parameterized two- two-layer networks, while most studies require much higher over peer-arramtterzzatinn.
INTRODUCTION
In recent years, many studies have been devoted to explaining the great success of over-parr peee-paramttezzedd neural networks, where the number of parameters is much larger than that needed to fit given training dataset. This study also treats over over-parameete wreepparaeterized two-layer neural networks using smooth activation functions and analyzes the convergence and generalization abilities of the gradient descent method for optimizing this type of network.
For over-parann parameterized two-layer neural networks, Du et al. (2019); Arora et al. (2019); Chizat & Bach)(2018g Mei et al. (2018) showed the global convergence of the gradient descent. These studies are mainly divided into two groups depending on the scaling factor of the output of the networks to which the global convergence property has been demonstrated using different types of proofs. For the scaling factor 1/m, (m: the number of hidden units), Chizat & Bach (2188);; Mei al. (2018) showed the convergence to the global minimum over probability measures when m -> oo by utilizing the Wasserstein gradient flow perspective (Nitanda & Suzuki 2017) the gradient descent. For the scaling factor 1 1/m@ (3 < 1), Du et al. (0119 essentially demonstrated that the kernel smoothing of functional gradients by the neural tangent kernel (Jacot et al., 2018 Chizat & Bach 20185) has comparable performance with the functional gradient as m - oc by making positivity assumption on the Gram-matre matrix of this kernel, resulting the global convergence property. In addition, Arora et al.] (2019) provided a generalization bound via a fine fine-graine grained analysis of the gradient descent. These studies provide the first steps to understand the role over-parameeerizzaton of neural networks and the gradient descent on regression problems using the squared loss function.
For the classification problems with logistic loss, a few studies (Allen-Zhi et al., 2018a Cao & Gu 2219a b) investigated the convergence and generalization abilities of gradient descent under separability assumption with a suitable model instcad of the positivity of the neural tangent kernel. In this study, we further develop this line of research on binary classification problems.
Our contributions.
We provide fine-grained global convergence and generalization analyses of the gradient descent for two-layer neural networks with smooth activations under separability

---

Under review as a conference paper at ICLR 2020
Table I: Summary of hyperparameter settings and assumptions achieve expected e-classification error by gradient descent for binary classifications. The "Separability" column denotes the types of models where separability assumption is made. is the number of hidden units, n is the size of the training data, and T' is the number of iterations of gradient descent. The notations Q2 and Ô hide the logarithmic terms in the big-? and - notations. Smooth activations include sigmoid, tanh. swish activations, and several smooth approximations of ReLU. As for Allen-Zhu et al. (2018a) Cao Gu
(2019a b). we pick up results specialized to two-layer networks.
Activation
Separability
Deep
T
Allen-Zhu et al. (2018a)
RcLU
Smooth Target
yes
((-=10)
2((
Cao & Gu (2019a)
ReLU
ReL.U NN
yes
(2(--19)
Cao & Gu 2019b
ReLU
ReLU NN
yes
10(--19)
00(-))
(((-1)
((6=4)
This work
Smooth
Neural Tangent
(((=
O(c=))
assumption with a sufficient margin using neural tangent model, which is non-linear model with feature extraction through a neural tangent. We demonstrate that separability assumption is more suitable than the positivity condition of the neural tangent kernel because (i) the positive neural tangent kernel leads to weak separability and conversely, (ii) separability leads to the positivity of the neural tangent kernel only the whole space. Therefore, the separability condition is rather weak in this sense but it is enough to ensure global convergence for the classification problems. Thus, significantly better convergence and generalization analyses with respect to network width can be obtained because the positivity of the neural tangent kernel is not required. Consequently, guarantee for less over-pare sree-parameterized two-layer networks trained by gradient descent, while most existing results relying the positive neural tangent kernel essentially require quite high over- parameterization. To the best of our knowledge, there are no successful studies for our problem setting (i.e., less wee-pparameterieed two-layer neural networks with smooth activation functions for the classification problems with logistic loss) in the literature. Most studies have focused on highly over- over-param wee-parameterized neural networks with ReLU activation, and less over weerpparameterized settings have been considered difficult for showing the global convergence property of gradient descent even in the few studies using separability condition (Allen-Zhu et al.) 201 Cao & Gu 2019a by. However, we note that these studies provided global convergence and generalization analyses of the (stochastic) gradient descent for challenging settings (i.e., deep ReLU networks) by making a similar but different assumption than ours. Thus, our and these studies do not include each other because of the difference of the network structure (i.e., network depth and activation type) and assumptions.
cone spanned by labels, which is very restrictive compared to
theory provides a generalization
We here deseribe the main result informally. A neural tangent model is infinite-dine dimensional non-linear model using transformed features (Opa(((()) x=))))))))))))) where is a smooth activation and Ai is a distribution used to initialize the parameters of the input layer in two-layer neural networks. Theorem states that gradient descent find e-accurate solution in terms of the expected classification error for a wide class of over- weer-aaameterized two-layer neural networks under separability assumption using neural tangent model.
Theorem 1 (Informal). Suppose that a given data distribution is separable by a neural tangent model with a sufficient margin under Lose -onsttriin.. for any e > 0, the hyperparameters satisfy one of the following
T= (i) 3 (0, 1), = T
(m )
(ii) B = 0, m = ((E-3/2), T ))) n= ((m n = 5)(E-2).
then with high probability over the random initialization and choice of samples of size n, the gradient descent with a learning rate n achieves an expected c-classification error within T T-iterations.
Related work. A few recent studies (Allen-Zhu al. 2018a; Cao & Gu 2019a b) are closely related to our work because they also treated the logistic loss function. As stated above, problem settings in and these studies are somewhat different, but we compare our result with those
2

---

Under review as a conference paper at ICLR 2020
specialized to two-layer network to show better property of our problem setting and analyses. Separability assumptions were made on an infinite-width two-layer ReLU network in Cao & Gu (2019a b) and on smooth target function in inAllen-hhu
al. (01 For generalization analyses, result exhibits much better dependency on the network width owing to a better problem setting with a fine-grained analysis. T provides comparison of the hyperparameter settings of networks and gradient descent in related studies to achieve an expected e-classification error. As evident in Table [ for more comprehensive sizes of two-layer networks with respect the network width, our theory
ensures the same generalization ability as those of Allen-ZZh et al. (2018a); Cao & Gu (2019a b). In
fact, the network width S2(=-1) and ((2-) are sufficient in our setting.
For the stochastic gradient descent for two-layer networks, BBrutzuus et al. (2018) Li & Liang (2018)
provided generalization analyses. Brutzkus et (2018) assumed that datasets are linear separable and this restrictive assumption was relaxed mixtures of well separated data distributions in Li & Liang 2018). However, the analysis in Li & Liang (018) is also tailored to only highly over- parameterized settings. Concretely, a very large width m = Qec and the number of samples (iterations) = (T) = Ó(-112) are required to achieve an expected c-classification error in Li Liang (0018). In addition, should be noted that global convergence analyses (Allen-Zhu et al. 201 8b
Zou et al. 2018) in terms of optimization without the specification of network size will yield loose generalization bounds because the complexities neural networks cannot be specified.
Apart from the abovementioned studies, there are many other studies (Brutzkus & Globerson 2017
Zhong et al. 2017 Tian 2017 Soltanolkotabi 2017 Du et al. 2019: Zhang et al. 2018 Arora
al. 2019: Oymak & Soltanolkotabi 2019 Zhang et al. 2019 Wu et al. 2019) that focus on
regression problems but our study focuses on classification problems and demonstrates a better property of gradient descent for over- vee-ppaametteized networks by utilizing the problem structure of binary classification. Especially, we show that a separability assumption is more preferable than the positivity condition of the neural tangent kernel (Du et al.] 2019: Arora et al. 2019 Zhang et al. 2019)] Wu et al.) 2019) and show that the required network width can be significantly reduced. Concretely, the required network widths are least (n))) (Du al. 2019, Wu et al. 2019), D(n' (Arora it al. 2019), and ((n²) (Zhang et al. 2019). Thus, these widths are very large, as compared to our results because sample complexities are generally slower than or equal to n 2) In addition, proof techniques are also different for the squared loss and the logistic loss functions because the latter function lacks the strong convexity. Thus, we cannot utilize the linear convergence property for the logistic loss and parameters will diverge, which also causes the difficulty of showing better generalization ability without a fine-grained analysis.
2 PRELIMINARY
Here, we describe the problem setting for the binary logistic regression and discuss the functional gradients to provide clear theoretical view of the gradient methods for two-layer neural networks.
2.1 PROBLEM SETTING
Let X' = Rdd and be a feature space and the set of binary labels {-1, respectively. We denote by a true probability measure on X' x )' and by vn an empirical probability measure, deduced from ob- servations (I,, y independently drawn from v, i.e., dv, dx, Y' = Σn d( (X, dX)XdY where ö is the Dirac delta function. The marginal distributions of y and v, on X are denoted by x and vxX respectively. For Ç E IR and y E V, let I(C, y) be the logistic loss: log(1 + exp(-x(0 Then, the objective function to be minimized is formalized as follows:
((0) del (xx.)),,,11f666X0) 1 n
Σ (ffozz))
where Se X' IR. is two-layer neural network equipped with parameters O =0,) When consider function fo variable of the objective function, we denote L(ʃe) def
L()).
3

---

Under review as a conference paper at ICLR 2020
The two-layer neural network treated in this study is formalized as follows. For parameters θ (0,),= (0,- E IRd) and fixed constants (ar) E --
Se
m Σ (0,
where m is the number of hidden units, 3 is an order of the scaling factor, and a IR R is a smooth activation function such sigmoid, tanh, swish (Ramachandran et al. )), and other smooth approximations of ReLU. In the training procedure, the parameters + = (6, M of the input layer optimized. This setting is the same those in Du al. (2019); (Arora al. (2019); /Zhang et al. (2019) : Wu et al. (2019), except for the types of activation functions, scaling factor, and loss function.
2.2 FUNCTIONAL GRADIENT
We denote by Lz( the function space from X' to IR, equipped with the inner product (1: La(og)
(0. v) La(x))
Ex Ex (x(X)((X) Vé, V' (2(
Following the tradition in the literature of boosting and kernel methods, we call L2 (y(),) ) the function space, although this space is actually an n-dimensional space because the cardinality of the support of vx is n. The key notion to explain the behavior of the gradient descent is the functional gradient in this function space L2 (v.)). We define the functional gradient predictor f X' + E as.
vxC(f(xx des {o
36) (od(S,,))<<5G)))) (r= =x);
(otherwise).
This is simply a Fréchet differential (functional gradient) in L (2( That is, it follows that
C(F + (()) (V, Latog) + o((10ll2(003)) vf, Vá (2(x))
Therefore, the functional gradient descent using v(f( directly optimizes L in a function space L2 [2(",") ) and converges to global minimum because the objective function is convex with respect to function f. However, because C(f) contains no information regarding the unseen data, this method meaningless terms of generalization. Thus, some smoothing techniques are required to guarantee the generalization. The gradient descent method for two-layer neural networks can be recognized as a type of sernel-smoother functional gradient using the neural tangent kernel (Jacot al. 2018), and this perspective is significantly useful in showing the global convergence because characterizes the behavior of the vanilla gradient descent a function space.
BRIEF REVIEW OF FUNCTIONAL GRADIENT METHODS
Functional gradient methods have been mainly studied for gradient boosting Mason et al. I 1999
Friedman| 2001) and kernel methods (Kivinen al. 2004 Small & Yao! 2006 Ying & Zhou
2006
Raskutti et al. 2014 Wei et al. 2017) > in the machine learning community, but more recently, it has been found be useful in explaining the behavior of gradient descent for neural networks (Jacot
cet al., 2018 Chizat & Bach 20186) Du et al.) 2019 Allen-Zhe et al., (018b] Arora et al.) 2019). Our
analysis is also heavily based on the functional gradient perspective of gradient descent. Thus, briefly review the functional gradient methods.
In gradient boosting, ((f() is approximated by finding a similar function in weak learners G:
Φy E argmax (V (V,L()) +) L2(2))
dEG
and the gradient method a function space is performed using a descent direction -Øf- This approximation type of smoothing of functional gradients. In kernel methods, this smoothing procedure is realized by using the kernel smoothing technique:
T.V C(S) def Ex [XX(XXXXXXX 1 V (((()(=:)M(aa))
(3)
4

---

Under review as a conference paper at ICLR 2020
where & is kernel function. It should be noted that this kernel smoothing 3 is special case of gradient boosting 2 because of the following equation:
T& f The ((f))l
argmax (V () 1 S1
where (Mk, ()) is the reproducing kernel Hilbert space associated with a kernel k. When this kernel smoothing well approximates a functional gradient vJ(() and satisfies
(VEC(),,,V,C()) LO(N)) 2 3 V , (1
(4)
the kernel-smoothed functional gradient descent /t f 7/T' (() performs like the pure functional gradient descent, leading to the global convergence property because it tends to a stationary point in a function space, which is simply global minimum.
Recently, several studies (Jacot et al. 2018 Chizat & Bach, 2018b Du et al. 2019 Allen Zhu et al.,
2018b Arora et al. 2019) implicitly or explicitly pointed out that the gradient descent for neural networks is essentially recognized as an approximation to the kernel-smoothed functional gradient method using neural tangent kernel (NTK) (Jacot al. 2018):
KNTK (I, x') def Egcor-p (0(0) T ( 2')],
(5)
where μin is distribution to initialize the parameters of the input layer in this setting. In most proofs using NTK, the global convergence property has been demonstrated by showing the condition (4)
= def (KNTK (z,, (z,,,,)) xy)) and the similarity between the gradient descent and the kernel-smoothed functional gradient with NTK when reason why very high aver-parameterizaaion is generally required related studies.
from the positivity of the
co. This is
In this study, found that the positivity of the Gram-matrix of NTK is not required binary classification problems and a separability assumption, which is weaker condition than the positivity, enough for global convergence. Consequently, can give global convergence and generalization guarantees to a gradient method for less over-vvvernenne weer-arameterized two-layer neural networks.
GLOBAL CONVERGENCE ANALYSIS OF THE GRADIENT METHOD
The following is an update rule of gradient descent with respect to the input parameters θ = (8,)
(t-1)) 1) + O ()())
(6)
where VoL(!(t) = (0,, and >> 0 is a learning rate. We here make the assumption:
Assumption 1.
(A1) Assume that x C f X | S 1}. Let be a CC-assss function and there exist K1, K2 > 0xt. ||o' S Ki and ||o" < K2.
(A2) distribution Pa on Rd used for the initialization of 0, has sub-Gaussian tail bound:
3A, 3b > 0 such that P Poco)~pollle ||2 2 < A eeep(-btt)
(A3) Assume that the number of hidden units m 24 is an even number. Constant parameters
(ar ph and parameters (0) = [0 ym are initialized symmetrically: o, = for r {l,..., m a, -1 for r E { + L,... I....,,,,, and 0.0) 0 for r [I,..., m } where the initial m parameters ), are independently drawn from distribution pa-
(A4) Assume that there exist > O and measurable function Rdd + {w E Rd ||/l||2 S 1} such that the following inequality holds: for V(x, v) suup(v) X X
y (8 (000))2).0(00) z),0(0())) Lz(uo)
[0E 2) ((((0))]] T p.
5

---

the Gram-matrix Under review as a conference paper at ICLR 2020
Remark. Clearly, many activation functions (sigmoid, tanh, and smooth approximations of ReLU such as swish) satisfy the assumption (A1). Typical distributions, including the Gaussian distribution, satisfy (A2). The purpose of the symmetrized initialization (A3) is to bound the initial value of the loss function (()(0)) uniformly over the number of hidden units m. This initialization leads to fer (a) = O, resulting in (()(")) log(2). Assumption (A4) implies the separability of a dataset using the neural langen! model. We next discuss the validity of this assumption.
4.1 SEPARABILITY ASSUMPTION (A4) BY THE NEURAL TANGENT
The explicit feature representation: x + ( x). of NTK 5 is called the neural tangent, which is non-linear feature extraction from X' to an crinite-dimenstone space. That is, assumption (A4) ensures the separability of the transformed data (0 xx) y) through the neural tangent for (x, 3) E supp(v) with a margin p in an infinite-dimensional space by the weight: v(0()) We remark that this assumption is somewhat weaker than the positivity assumption
of NTK and is satisfied in many cases by the universal approximation ability of the neural tangent models. In addition, remark that the separability of the training dataset instead of supp(v) is enough to guarantee global convergence only for empirical risk minimization.
Theoretical comparison of kernel assumptions. In previous studies (Du et al. 2019; Arora
ct al.] 2019: Zhang et al., 2019; Wu et al., 2019) the positivity of the Gram- matrix H (KNTK (P Ty (] jjj was required to ensure the condition (4). Here, we remark that the assumption (A4) is weaker than this positivity condition in the following sense.
Proposition 1. (i) Assume Ho ł Aa and ||o' K1, then there exists measurable map v Rd + (w E IRd || S 1} such that Vi E (1.....n)
yi ( (0 TT),, o(8())
Ao
2
La(uo)
nK1
(ii) Suppose assumption (A4) holds, then EiJ=ISHH & 2 2, 11 (VE E ((o,9:))) a; 2 0}).
As seen in Proposition (i). the positivity H Z Aoln leads weak separability with a margin of O(a//)) on the training dataset. Conversely, from Proposition (i)), the separability with a margin of p leads the positivity p² of H only on cone spanned by the labels: {(o,)))) a; 2 0}. Because this cone is very restrictive, this limited positivity is much weaker than the positivity on the whole space. However, we found that this limited positivity is sufficient to ensure the global convergence of the gradient descent for binary classification problems with logistic loss. Indeed, from Proposition 3] the positivity of H000 is required only along the functional gradients: (y((fe)(z;) = 0z((fe (zt4, 3:). and these functional gradients are always contained in this limited space, unlike the squared loss function. This a reason why the positivity of NTK is not required for the binary classification problem with logistic loss. Thus, much better convergence and generalization ability can be shown for logistic loss than the previous results that relied on the positivity of 80 because the positivity of NTK on the whole space is redundant and separability condition provides a better positivity only on required small space. Concretely, from Proposition ((), can immediately check deteriorated convergence result depending the positivity of H by replacing p in Theorem 2 with O producing m = O(nAg E
1 when B = O.
Remark. For regression problem, Allen-Zhu et al. (0118/cc); Zou al. (2018); Oymak & Soltanolkotabi 2019);; Zou & Gu (2019) make a different separation where examples are away from each other: ||=- 22 2 poZuu & Gu (2019) shows that this assumption essentially same as the positivity of NTK. Thus, it also completely differs from (A4) as shown in Proposition
Universal approximation property of neural tangent models. feature vectors have a common bias term: z (z......, d s) E X (s > is sufficiently small constant for a bias term). In this case, we can easily confirm that neural tangent models include typical two-layer infinite-wi width neural networks with activation Ø': Elw(((()) (B(0)" x;) by setting v((())) = (O.... O, w( w((()))). where is real-valued function. Thus, Assumption (A.4) with certainly positive constant p is satisfied as long as a data distribution is separable by an infinite-wide two-layer network with mild weights (0) Moreover, we note that these networks have the universal
We consider the case where all

---

16KĪ Under review as a conference paper at ICLR 2020
approximation property (Hornik [991
Sonoda & Murata 2017), that there a lot of examples
such that the assumption (A4) 18 satisfied.
4.2 MAIN RESULTS
We here define the -noom of the functional gradient, which measures the convergence.
[V def
(el(fe(zz))
2n Σ y 2pe x;) + 1/.
Here, Ç is the first variable of and 10) =z) 1+exp(- fe(=)) a conditional probability on
== defined by fe. Because y[[(ff)) L, (xx) is simply gap between the labels and conditional label probabilities of the model, this norm is reasonable measure for the binary classification problems. The following is the first main result to ensure global convergence.
Theorem (Global Convergence). Suppose Assumption 7 holds. Set K = K1 + 2
For V3 E [0, 1), V8 E (0, 1) and Vm E E4 such that m Z
p² log 8, consider gradient
descent 66 with learning rate of 0 n S min {m² Then, it follows that with probability at least - 5 over the random initialization,
1m29-1 Ki+K2]
and the number of iterations
T
mp² 32n log(2)
16 16log(2)
m323-
(VLLeo))) S
K
T
p²T
We here derive a corollary, which states that an arbitrary small empirical classification error can be achievable by appropriately setting 77, m, and T as follows. From Markov's inequality,
Px,, (Y fem (X) S 0J s 2 [[Fe((()))
where we used the following relationship:
0.5 1y/ 2pe Y 1/x;)) + + (1 + exp(r))) vi S7
Thus, a convergence rate of , ((fem) )li.. leads to rate of empirical classification error.
Corollary 1. Suppose the same assumptions as in Theorem hold. ffror Ve, 8 the hyperparam- eters satisfy
B 10, S1pp T - ")) -
then with probability at least 1 - 5, gradient descent (6 with a learning rate of 1) finds parameter ( satisfying P(x.Y)<v,ll Se (X) 0] within T-iterations.
The Landau notations are applied with respect to e,p + 0. Utilizing this theorem, we can show the convergence of the loss function which leads a better result the price of slight increase of m.
Theorem 3. Suppose the same assumptions in Theorem 2 hold. Then there exists uniform constant
C > 0 such that for Va S 4kg. with probability at least 1 8,
1 C(O
sc ( a²m nf
_amm-
a
n m
Σ t=
exp
T
4
TT
p
Corollary 2. Suppose the same assumptions as in Theorem
hold. Then there exists a uniform 0, the hyperparameters satisfy
constant 0 and the following statement holds. for any
3/2 3 = 0, (p 3/3 log(1/e)), T. - log (1/e)), n O(m=l),
then with probability 1 - 8, + DT-I ((0(0) < C (s / log" (t) for 0 < VT < T.
This corollary is obtained immediately from Theorem by setting ((pc322). The convergence of classification error also derived from the corollary because L(fo) 2 ( and it also derives sharper bound the distance (T(T) (1))
7

---

Under review as a conference paper at ICLR 2020
Proposition 2. Suppose the same assumption and consider the same hyperparameter setting in Then, there exists a uniform constant C. such that with probability - 6.
Corollary 2
||0(7] 6 S CC log" (p-
Morcover, by combining Theorem and Corollary with the well-known margin bound (Koltchinskii
& Panchenko| 2002; Mohri et al. 2012, Shalev-Shwarzz & Ben-David (0144) the expected
classification error and by specifying the Rademacher complexity of the function class attained by gradient descent, can obtain the second main result for the generalization ability of gradient descent.
Theorem (Generalization Bound), Suppose Assumption 1 holds. Set K = + K K Fix vy > O. Consider the gradient descent 16 with a general hyperparameter setting in Theorem or a specific setting in Corollary 2 with E (0,1). For these cases, we set parameters C,,,. and
D Dn,mr follows:
(Former case)
1/2 Cn,m.T = p 1T m in 11/2 + .K).
Dym.T VIT
(Latter case)
Cr,m,T- = e 27 log" (1/6), DT.,.T = 6/4 lo// (p-26-1 26)
Then, there exists a uniform constant C > O and it follows that with probability at least 1 38 over a random initialization and random choice of dataset S,
l2/(2/6)
min x (O......TT T-1] P(X.Y) (X) 50] C(1 + exxp())) + 33
2n
+ -C
D nmm (1 + K1 + K2) log (n(1 K1 + (2)((mm(m18) + D r)
/
d
Moreover, when a is convex and a (0) O, we can avoid the dependence with respect to the dimension With probability at least 1 35 over a random initialization and random choice of dataset
log(2/0)
min EE EO......-1
(Y (X) 0] < CC1 exx(())))) +3/
2n
CKimt-p T (Do...++ log(Am//))
(10)
b
This theorem provides an upper-bound on an expected classification error with high probability for a network obtained by gradient descent within T-iterations. There trade-off between the optimization and complexity terms in (9). (0) with respect 1), m. and T. However, there are several choices of these hyperparameters to achieve a desired precision e of the expected classification error.
Corollary 3. Suppose the same assumptions in Theorem hold. ffr any e 0, the hyperparam- eters satisfy one of the the following
(i) E [0, 1), m 2 T 22pppppppp2)- 7= O 26 1m n Mp 2 (ii) 8 0, m 2 log(1/c)). T O log2(1/))). 7 = 0 n 52(c²))
then with probability at least 1 - ó, the gradiens descent (6) with a learning rate of finds a parameter ((t) satisfying P P(x,Y)~u faw (X) < 0) S within T Titterations.
This corollary can be immediately proven by substituting the concrete values of 3, m, T, n, and into the right hand side inequalities (9) (10) and by checking that this hyperparameter setting satisfies the conditions required in Theorem
From Corollary 3 for an arbitrary small e O, an expected e-classification error is achieved by the gradient descent within ((1/e)) ((1/e)-iteratiee
when the transformed data distribution by the
neural tangent: (0g (e!!)T ))mm is separable in the anfiiitedimmessionll space L2(p)) under the Loc -constraint with sufficient margin p. In comparison to the result in Allen-Zhu et al. (2188)); Cao & Gu (2019a]b), b). which also derived a generalization bound by making a similar separability assumption using ReL. network or smooth target function instead of the tangent model,
8

---

Under review as a conference paper at ICLR 2020
result has much better dependency on the network width and can explain the generalization ability for a less over parammeteriee two-layer network, as summarized in Table However, we note that their theories cover deeper networks and not included in theory because of the difference of the problem settings (e.g., network depth and the type of activation functions). To reduce the network width, the best choice of [0, 1) is /3 for the first setting, leading to small network width m ()) We note that an arbitrary large width is also covered by this result.
4.3 PROOF IDEA
In this section, we provide a proof idea for Theorems 3 and We introduce two important propositions that connect the gradient descent with the functional gradient descent to justify an intuitive explanation in Section 3 Proposition (i) states that the gradient descent method is certainly similar to the kernel smoothed gradient methods by the neural tangent kernel when parameter θ is sufficiently close to stationary point and the learning rate vj sufficiently small, and Proposition (ii) states that the loss landscape is almost convex with respect to the parameter when fe is sufficiently close to a stationary point in the function space. Here, We define an approximated neural tangent kernel: lig depending on the parameters O as follows:
x') defe(a) 3e
(11)
This kernel is actually an approximation to the vanilla NTK as follows:
m 2 (ig xx, - KNTK (x,,²") (m 00).
Proposition 3. Suppose assumption (A1) holds and 3 E [0. (i) We set ++ = θ v)V)(( and K K? 2K2 + K2 1f S mP, then
1²
((Se-) (C([e) (V, The v, (2(xx))
2m 2 [V
(ii) It follows that for θ (0+) |T= and @" (0)) (0r, 07 RR.), K₂
((0) + Vo (0- θ) (())) + m |
01
The next proposition states that the kernel smoothed gradients have comparable optimization ability to pure functional gradients in terms of minimizing the Lı Linom around initial parameter ())),
We define the || Inorm norm in the parameter space θ = (0, )m as ||0||2,1 def Σ 12-
Proposition 4. Suppose Assumption 7 holds. For v8 E (0, 1) and Vm E4, such that
16K? log 2n, the following statement holds with probability at least 1 8 over the random
m
initialization of (0) = (0. ym 1 -000) 11,11 S
ma then 4K2'
V ((fe). The V v(((e) Lo(uX)
16m23-T V VV
This proposition specialized to binary classification problems because the positivity of the Gram- matrix is required for regression problems to make similar statement as discussed earlier.
Combining these two propositions, we can connect the gradient descent with the functional gradient descent and show the global convergence (Theorem 2 which with the almost convexity (Proposition (ii) is also used to derive the convergence rate for the loss function (Theorem B). In addition, applying well-known result (Koltchinskii & Panchenko, (002). can derive skeleton of generalization bound (Theorem (4) composed of the margin distribution and Rademacher complexity. As for the margin distribution, the upper bound is obtained by Theorem and As for ways to bound Rademacher complexity, please see the Appendix.
5 CONCLUSION
In this paper, we have provided refined global convergence and generalization analyses the gradient descent for two-layer neural networks with smooth activations binary classification problems. The

---

Under review as a conference paper at ICLR 2020
key in analysis is the separability assumption by neural tangent model and have explained the reasonability this assumption in comparison to the positivity of NTK. Consequently. theoretical justification has been provided for less over-paramann per--paameterized neural networks. However, restricted to the deterministic gradient descent and two-layer networks; hence, its possible extensions to stochastic gradient descent and deep neural networks are also interesting. Another possible future study is to relax the positivity assumption on the Gram-matrix for regression problems by utilizing our theory and conducting further investigations of the trajectory of gradient descent, such as the shortest pass analysis (Oymak & Soltanolkotabi 2018).
theory is
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. arXiv preprint arXiv: 04918, 2018a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via parameterization. arXiv preprint / 1.03962, 2018b.
Zeyuan Allen-Zhu Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. arXiv preprint arXiv:1800. 12065, 2018c.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv:1901.08584, 2019.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normet neural networks. In Advances Neural Information Processing Systems 30, pp. 6240-6249, 2017.
margin bounds for
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In Proceedings of the 34th International Conference on Machine Leurning-Voon Volume 70, pp. 605-614, 2017.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. Sgd learns over- parameterized networks that provably generalize on linearly separable data. International Confer- ence on Learning Representations 6, 2018.
Yuan Cao and Quanquan Gu. A generalization theory of gradient descent for learning over- parameterized deep relu networks. arXiv preprint arXiv:1902.013388 2019a.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. arXiv preprint arXiv: 1905. 132 10, 2019b.
Geoffrey Chinot, Guillaume Lecué, and Matthieu Lerasle. Robust statistical learning with lipschitz and convex loss functions. Probability Theory and Related Fields, pp. 1-44, 2019.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over- wer-parameterized models using optimal transport. In Advances in Neural Information Processing Systems 31, pp. 3040-3050, 2018a
Lenaic Chizat and Francis Bach. A note on lazy training in supervised differentiable programming. arXiv preprint 1X12:1812007956 2018b.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. International Conference on Learning Representations 7, 2019.
Jerome H Friedman. Greedy function approximation: a gradient boosting machine. The Annals of Statistics, pp. 1189-1232, 2001. 2001.
Kurt Horiik Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2): 251-257, 1991.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems 31, pp. 8580-8589, 2018.
10

---

Under review as a conference paper at ICLR 2020
Jyrki Kivinen, Alexander J Smola, and Robert C Williamson. Online learning with kernels. IEEE transactions on signal processing, (2(8):2165-2117 2004.
Vladimir Koltchinskii and Dmitry Panchenko. Empirical margin distributions and bounding the generalization enror of combined classifiers. The Annals of Statistics, 30(1):1-50, 2002.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Newral Information Processing Systems 31, pp. 8157- 8166, 2018.
Llew Mason, Jonathan Baxter, Peter I. Bartlett and Marcus R Frean. Boosting algorithms as gradient descent. In Advances in Neural Information Processing Systems 12, pp. 512-518, 1999.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two- layer neural networks. Proceedings of the National Academy of Sciences, 115(33):E7665 E7671, 2018.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2012.
Atsushi Nitanda and Taiji Suzuki. Stochastic particle gradient descent for infinite ensembles. arXiv preprint arXiv:/712.055:
2017.
Samet Oymak and Mahdi Soltanolkotabi. Overparameterized nonlinear learning: Gradient descent takes the shortest path? arXiv preprint 1rXiv: 2018
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterization: global con- vergence guarantees for training shallow neural networks. arXiv preprint 1002v2190,.04674, 2019.
Prajit Ramachandran, Barret Zoph, and Quoe V. Le. Searching for activation functions. arXiv preprint arXiv:1710.0590
Garvesh Raskutti, Martin Wainwright, and Bin Yu. Early stopping and non-parametric regression: an optimal data-dependent stopping rule. Journal of Machine Learning Research, 15(1)333-336, 2014.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Steve Smale and Yuan Yao. Online learning algorithms. Foundations of computational mathematics, 6(2):145-170, 2006.
Mahdi Soltanolkotabi. Learning relus via gradient descent. In Advances in Neural Information Processing Systems 30, pp. 2007-2017, 2017.
Sho Sonoda and Noboru Murata. Neural network with unbounded activation functions is universal approximator. Applied and Computational Harmonic Analysis, 43(2):233-263. 2017.
Yuandong Tian. An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point aialysis. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 3404-3413, 2017.
Yuting Wei, Fanny Yang, and Martin Wainwright. Early stopping for kernel boosting algorithms: A general analysis with localized complexities. In Advances in Neural Information Processing Systems 30, pp. 6065-6075, 2017.
Xiaoxia Wu, Simon S Du, and Rachel Ward. Global convergence of adaptive gradient methods for an over-parameterrzee neural network. arXiv preprint arXiv: arXiv: 190.00711, 2019.
Yiming Ying and D-X Zhou. Online regularized classification algorithms. IEEE Transactions Information Theory, 22(11)477544788 2006.
Guodong Zhang, James Martens, and Roger Grosse. Fast convergence of natural gradient descent for overparameterized neural networks, arXiv preprint /905. 2019.

---

Under review as a conference paper at ICLR 2020
Xiao Zhang, Yaodong Yu, Lingxiao Wang, and Quanquan Gu. Learning one-hidden-laye layer relu networks via gradient descent. arXiv preprint
2018.
Kai Zhong. Zhao Song, Prateek Jain, Peter L Bartlett, and Inderjit S Dhillon. Recovery guarantees for one-hidden-layer neural networks. Proceedings of the 34th International Conference on Machine Learning- -ollume 70, pp. 4140 4149, 2017.
Difan Zou and Quanquan Gu. An improved analysis of training over-parameterized deep neural networks. arXiv preprint
2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint
2018
APPENDIX
A RELATIONSHIP BETWEEN KERNEL ASSUMPTIONS
Proof of Proposition 7 We here prove the statement (i). Since 0 is invertible, we set w (110)-1(y11 yn) and set
D( =
8o0 ( TT)
Then, get
y1 (000
x.),, v(0(0))
-i w
12((0))
We can bound the norm of [|o(o()))]l 2|2 as follows:
(1(00))) 112
1000 (010) xz)12//u5
#=1
(100b
x2)112)) )-
|w
5=1
Vnki /wll2
nK1
A
Thus, by resetting v((()))
) R.
conclude the statement (i).
12

---

Under review as a conference paper at ICLR 2020
We next prove the statement (ii). For & (a:9)) (a; > 0).
1 E
Ex:0 (0000((0::T O x,)E,l
k-=1
RRgio>~an
Σ ( xip)
Σ ( xx) v(B10))
Egg ~
Σ (0000 xx)) (0 |10000) wi) ))
Egtor
Σ
Oi Earro [10000(0)TT:) x.)
x:)TT((00)) [(000))
2
n
at
P² I
where we used [|(00()))l2 < 1 for the first inequality, the convexity of || 112 and Jensen's inequality for the second incquality, Assumption (A4) for the third inequality, and incquality. Thus, we finish the proof of the statement (ii).
llla S S|I- for the last
B AUXILIARY RESULTS
In this section, we introduce several existing results for proving our statements. We first describe the Hoeffding's 's inequality.
Lemma (Hoeffding's inequality). Let Z, 71, ...... Zmm be i.i.d. random variables taking values in [-a, a, for a O. Then, for any é > O, we gel
e'
Σ Zr E[Z]
> < 2exp
2a
We here define the covering number as follows.
Definition 1 (Covering Number). Let -V, metric space. A subset Ô C. V is called an e-(proper) cover of V for Vu V, there exists v' E Ú such that |/v o'll < e. Then, e-covering number N(V, e, II) V is defined as the cardinally of the smallest e-cover Vf that is,
N(V, def min{(ů] Ó is an e-cover V).
The following lemma provide a bound on the Rademacher complexity by Dudley's integral. For real-valued function class over X' and subset = (x:) Flx is defined as {(h(x))) e R" h E F} C. R.," and Fix x be equipped with - al -oom over X.
Lemma (Bartlett et al. (2017)). Let F be a class of real-valued functions taking values in [0, 1] from X and assume F. For examples VX (xx))= of size n, we gel
12
/'
R R(F < inf aso
4a +
Vog(N x
Iddc
Vn
Note that reformulate the statement in Lemma 2 from
|22coveringg to - coveriig.
13

---

Under review as a conference paper at ICLR 2020
C PROOFS OF MAIN RESULTS
In this section, we give an outline of proofs of Theorem and
Global convergence. We first introduce two important propositions which connects gradient meth- ods with functional gradient methods. The following proposition states that gradient descent methods become similar to kernel smoothed gradient methods by the neural tangent kernel when a parameter & is sufficiently close stationary point and a learning rate 1) is sufficiently small.
Proposition 5 (Restatement of Proposition 3) Suppose assumption (A1) holds and 3 E [0, (i) We set θ = = - v)eC(() and K K 2K2 + KÝK If S m2, then
((fe-) - (E((e) ((fe), The V v)((fo)) L2(1X)) )
n2 2m [V
(ūi) It follows that for θ = (0r) and O- = (0:)== (0r, 0r RR.))
K₂
((0) + VeL(e) (0" 9) S _()))
+ m
v ((fe)lll -12
The next proposition states that kernel smoothed gradients have comparable optimization ability to pure functional gradients in terms of the L1 -nom around an initial parameter ( We introduce the
|| 1|2,1 Inorm in the parameter space @ = (0,r ) as ||0||,,1 def Σ 10 12-
Proposition 6 (Restatement of Proposition 4 Suppose Assumption holds. For 48 E (0, 1) and
log 2n the following statement holds with probability least 1 Wm E Zt, such that m z x² 5
16K?
over the random initialization of ((()) = (m 1f - 11,1 $ 4K2'
mp then
(V) The Vy Le(uX)
V Vy[(f))l
25-25-
This proposition is specialized to binary classification problems because the positivity of the Gram-
matrix is needed for regression problems in order to make similar statement as discussed earlier.
We specify the possible number of iterations of gradient descent
6 such that (()) remain in the
neighborhood: {0) | - (( || S
ymg
C {0) ||0 ()))) S TK₃
||,,
mp
).
1K₃
Proposition 7. Suppose Assumption (A1) and (A3) hold. Consider gradient descent b with learning 4m 28
rate 0 17 Kt+K, and the number of iterations T Z4. Then,
1 T-1
Σ t=0
| (()
log(2).
(12)
T
T/T
Especially, we get for
S / (2). As a result, gradient descent can be performed
mp² 32nK3 log(2)
iterations within { || e I
vipp
C 10 600)
mp 48, }.
4K,
This proposition provides bound on the distance ( 0000|2 ||2. but note that this bound will be further sharpened after showing the convergence of the loss function (see Proposition 2}. From
Proposition 5 6. and 7 we notice that the gradient descent for L(O) performs like pure functional
gradient descent up to O mpp" -iterations, resulting in significant decrease of loss functions. We
next provide the proof of Theorem 2 based on this idea.
Proof of Theorem Thus, Proposition
From Proposition 7 the assumption in Proposition 6 regarding θ is satisfied. and state that for i E [O....,T-1.
np²
1 K
[(Sect)) < ((Smm)
| V )l( + 2m (e
16m23-I
14

---

Under review as a conference paper at ICLR 2020
Summing this inequality over / (0,.... ....,,, T 1} and multiplying by
4m no"
have
T V ((Se ((Sec))) S
16m25-1
8T,K T-1 p2T t=
no²T ((eero)) +
(o((0))
Applying [(0(0)) = l2g(2) and inequality
we complete the proof.
Proof of Theorem
We set 7"
((a))(()))) and @ = ( + r". Clearly, we have
|0" - avm.
(13)
As shown in Proposition we get
K2 m
(z) (
1' S a² K2m
In addition, as shown in Proposition since m 2 16K
2n log z. the inequality 21 holds with
probability least 1 - 5. Hence, we have for Vi {1, ( n),
Vife-(xx)) 2 Vefero (x) (0" -( a² K2m 1-8
y:ar m
( x;) ((( a² K2m+-8 1-8
r=1
apm 1-8
a K2m 1-8 apm--~
2
Thus, the loss at a reference point O* can be bounded follows:
[appll
((0*) < Σ log (1 + exp(- (x:)) & exp (-uifer (zi)) s exp
(14)
From Theorem Proposition (ii,, Proposition 7 and inequalities 3G, 3C2 > 0, V7 ST.
13
14p it follows that
(C((()) + (o
T t=0
K2
<<(0") +
( -0
m
S <(())) + K2
m²T
V C(C(fe) ) 1E(0....T-1)
max
|10 - -9
ma VT S <(()))
2Kg
max
(100 - + +||@(0) 1000)
200)
C2
S(())
(m2m+n11
PVrIm
apm---
C2
nf
eexp
(15)
4
p
nT
m
15

---

Under review as a conference paper at ICLR 2020
Finally, bound the average of ( Because -2a b ||a||| + -1 for real vectors a, b, we get by setting -V and b Q(t)) - -9¹,
T
T-1
(O)
-0)= 2nT
(e( (1) 112 + ||0 - 21 | -1
T t=0
T-1
"
Σ
(VL(((())
1 0-
2T 1=0
2n7
12g(2)
a²m
T
21/T'
Thus, we get that 30 > 0.
T Σ
1
a²m
apm-
a²
1
nf
exp
T
nT
n/T
p
m
We next prove Proposition 2 that gives sharper bound on ||@(T) (
Proof of Proposition 2 Let L E E, be a positive integer such that for T = - (1/e()
2- < T < 24+1 Clearly, L < log2 T. From Corollary 2 we get for lorl= E [I.
((0
((0()) 20 (c (c+22'p 2 log (1/c))
2
Therefore, there exist 2/-1 < 3s < 2 for l E (1...., L} such that
(() $ 20 (e + p-2 log (1/())
From the similar argument to the proof of Proposition Ei_ ( S /2(b + 1)m- C(O()).
get for
< b Z+,
Thus, it follows that since 81 1, (Ve(( l1 S VmK, by 19). and 2 2/-1 + +1525 1
Σ |Vec(0")) < ( 1/ Σ 1
Σ
(Ve(((()) 12 Σ \
S VmK1 +
2 log"
SvmK + loga (T) 23 + p-2 log?( (1/e)).
Hence, by setting specific values of n, T, and m in Corollary 2 we get that 3C" > O.
T-1
| - (00) 1n n
Σ
(ve
S mmmK1 + +log (T) (T ( log2
1=
S C' 3/4 log 2p (0-2)-
Generalization bound. A generalization bound can be derived by utilizing the standard analysis of the Rademacher complexity (Koltchinskii Panchenko 2002). We here introduce function class to be measured by the Rademacher complexity. Let I (v)
0) be the ramp loss:
(v) def {
(u < 0),
(0=
1 - v/4
(0 5 v S 7),
0
(v > 7).
16

---

Under review as a conference paper at ICLR 2020
Then, class of all possible ramp losses over X' y attained by the gradient descent ( up to T-iterations is defined as follows: 4yymm
def (0) ||0 ( 1|2 S Dm.T.m..
F n. def (4(ufe(x)) X + [0, 11 4 9g
Here, Dm is set to be 2nyTloo(() when considering a general hyperparameter setting in
Theorem 2 and is be sharper bound in Proposition 2 ((e%/4 log2(p (0-= when considering
a specific hyperparameter setting in that proposition.
def
For a given dataset S = (2 91) the Rademacher complexity is defined by R(F7, 7. n.m, n- --(uussspp 7,m,7 7,m,7 Ei=1 C,h(x;, Us)], where the expectation is taken over the Rademacher random variables (e))
which are i.i.d. with probabilities IPle; = 1] IPE,, = -1] = 0.5. The following
well-known result (Koltchinskii & Panchenko, 2002, Mohri et al.) 2012 -Shale-SSwaatt & Ben
David 2014) provides a bound on the expected classification error based on the empirical margin distribution and the Rademacher complexity. The empirical margin distribution for S is defined as the ratio of examples satisfying (I;; S T in S.
Lemma 3 (Koltchinskii & Panchenko 2002): Mohri et al. (012)) Shalev-Shwartz & Ben-David
(2114)). Let Vn E 24. VY 0, Vn > O, vm Et. VT E E.,, and Vo E (0,1). Then, with probability at least 8 over the random choice of S of size n, every E S.ym. satisfies
(Xe < 0] S P(xM (Vf(() S s71 + ( m,,,Tls + (2 log(2/8). (16)
To instantiate this bound, we have to provide upper bounds on the empirical margin distribution and the Rademacher complexity. We first give a bound on the Rademacher complexity.
Proposition 8. Suppose Assumption (A1) and (A2) hold. Let > 0, An > O, Vm E Z4, VT E Z,. v8 E (0, 1), and VS be examples of size n. Then, there exists a uniform constant C > 0 such that with probability at least 1 ô with respect the initialization of ()))
R(F n. S mm - - m,m, (1+K) -log log (n(1 + K1 + (2)(mmmmm/)) + D2 D)
Moreover, when a is convex and a (0) O, can avoid the dependence with respect to the dimension d. With probability at least - 8 over a random initialization of ()))
8K 8Kim?-9 (Drmm: + log(Am/0)
R(F
n.m. rs) S
7/n
Proof of Theorem We prove this theorem by instantiating inequality (6)) Let ( be sequence obtained by the gradient descent (6) Because (0(1))²-) is contained in Roym, as indicated in Proposition 7 incquality (16) holds for this sequence. As for the Rademacher complexity in (16), utilize Proposition 8 Thus, the resulting problem is to prove the convergence of the empirical margin distribution: P P(,, fe (X) & 7]. We here give its upper-bound below.
1=
0.5 1y: 2P = 1|x,)) + +1| 2 (1 exp(n)) = y:fe(æ;)) S:
Therefore, from Markov's inequality,
P( Seo (X) s PP
2 Y 2pe 2p= + + 1 exp(>))
exp(()))))
V C(fe) (()
Combining this inequality with Lemma then for Vt E fo...., T 1}.
log (2/0)
(Y (X) < 0 < (1 - -xp(())) , ((Sor) (L,, + 2 "r.m.rls) + 3//
2n
Noting that 17, m, and T satisfy the conditions in Theorem we can complete the proof by taking the average over (0, ...,. .., T 1} and applying Proposition and Theorem
17

---

Under review as a conference paper at ICLR 2020
D PROOFS FOR GLOBAL CONVERGENCE
D.1 PROOF OF PROPOSITION
S
Proof of Proposition We first show the smoothness of fe(x) with respect to θ for Vr X.
(1|=112 I 1). Noting that V fe) diag (me a, x)æx ) we get for r (T+) such that mm 11 = (r E R*).
0 (2)
o '000, x)) [T,T
m
K₂
m
Tr 11
K₂
m
This means that for = (Tr) (T, E IR).
K₂
K2
( + Vele(a)
Tr
(17)
m
m
Let us define go (T) the second-order term of Taylor's expansion of fa with respect O:
felt (x) = fe(r) + T
From the inequality (17 we have 1xx(T)] - to and [0R v)
Kallr1B m
Then, by the smoothness of Z(C, y) with respect
1/4, we get
(())+r()).))
4 (
K K
2 [VoJe(z)]]
m
By the triangle inequality, get
((fe++(=), ( Vof(()) 1)
1/2 (z)
K3 |
(101(ff(z)) (T)
|
m2 2
2Kg
K3
(=)fe(>)11
||=|12
2
m
m2
1
K?
2Kg
K 113
|
(18)
2
28--1
m
m3
where for the second inequality, we used (8,1(C,)) < 1 and for the last inequality, we used
2
K?
[Vofe(>)] Σ
(0_T x)x
22 28 / x0,T2))2 <
m2
23-11
2
We here set == -V)C The right hand side of 18 is upper bounded by
K?
2Kg m
17
K
||-112-
m
m
43-1
18

---

Under review as a conference paper at ICLR 2020
because
] =
Σ
000
2
r=1
(1)
2
2
Σ
agd (e
max jE(l.....
= ,V,((f)) (12)
(E(.....) m lo' (0, 20,221
max
< [V, (1)) m 1n2t-29k K?
$ m k?.
(19)
Therefore, we get
- (00-0-0))0000000))00000000000))) (10l)))))))))(((()))))))))))l (ve()))
K?
2K2
< m2
(
m
m
$ 1
Bm28-1 (K? + 2Kg + K2 of (
(20)
where we used 3 E (0,1) and 7 S m for the last inequality.
Noting that from the definition of kernel smoothing of functional gradients 3 we see
1
Vefe(z) VeC(()) Vefe(z))
ac((f(l)).:)Veff(c))) n
The (z))
Therefore, by taking the expectation of 20
according to the empirical distribution Vn. get
[(fe+t) (C(fe) -(ar)))((ee)
(V, TRe
2m (K} 2K, K2K3) |V
This completes the proof of the statement (i).
From the convexity of ((S, v) with respect to Ç, we have
= -0
2 216660)100-22/666000000664114641 -0) + gx gx(O" -0)) 2
-1)((((((( K₂ O* - +
3
where we used (9x - 0 <
K e m2
Thus, by taking the expectation with respect to
(X,Y) ~ Un. we get
K2 m
L())) L()) + VoL(O) (0--
Q) (0-"
[VLLee)l 011
This finishes the proof of the statement (ii).
19

---

Under review as a conference paper at ICLR 2020
D.2 PROOF OF PROPOSITION 6
def y.0g0 2.) TT)TT,(( "( We find clearly 1Zn I K₁ from By applying Hoeffding's s inequality to Z, for each {I,..., n and taking an union bound, we have
Proof of Proposition 6 Set Zr
Assumption [
2 m
_ppmm 16K?
Pe(
max (e(mn
Zr
E B0o1
[rrii]
I 2n exp
2
In other words, since 2
16k?
2n log 8, we have with probability 6,
m/2
max 1E n).
Σ Zr
g [Zra]]
S P
m7
Therefore, using Assumption (A4) and noting O (0,),= symmetrically initialized, we get with probability 1 - 5 for vi E nl.
T Σ
y: u:0 (0 x:) T0(00)) 2
(21)
772
In the following proof, assume O (8. ) satisfies this inequality. We get from the Ky-Lipschitz continuity of o' that for θ (0,) )m satisfying ||0 (00) I
mp 4K2
m noo (0, Di xi)., v(((0)
m
Vio (O( (.)),,(((((00) ((((0))
m
m
yo T (0, (0' (0, 2;4) o' -'(0 21))
m
K2l(0, 0.00) T x11
K₂
100
(0)
12.1
m
This means that there exists (w,) such that ||v, s (Vr E (I,...,m)) m)) and for vo (0,)
satisfying |0 - (0) ||,,1 <
me
TK,'
m
y 1,0 2:)
Vi (l,..,,,,
4'
Then, get the following bound: for V(xc) (as 1)),
Uaa,0b To) m
Σ a;
(8_ TT)TT uT
a:
0.
(22)
m
4 i=
i=1
20

---

Under review as a conference paper at ICLR 2020
Noting that V vx((f))(z; I+oxp(uffat..))
get
1
(V,C(Je), The V, La(U
n
i,f=1
1
((( fe(
[==(f))(z))000(( mx))
m
v [=: x;) T
2
n
m
([ Jer
n1
m 1+
m m1-23 p²
Σ (1ooffffllt)))
16n2
where we used ||u,|2 < for the first inequality, the convexity of || [ for the second inequality, and (2 for the last inequality. We can find that this inequality finishes the proof because
+ exp(Se((;)))) y -2pe 1 xx)) 1/.
D.3
PROOF OF PROPOSITION 7
The proof of Proposition 7 is based on the traditional convergence analysis of gradient descent for smooth objective functions in finite-dimensional space.
Proof of Proposition 7 We first specify the smoothness of the logistic loss function. We set Φ(v) log(1 + exp(-v)) and I(y, fe(x)) = o(yfe(z)). By the simple calculation, we get that for 7, E mL....,
Φ2 00,00, 11y, fe(x)) = 6" (vff(())) aras d' (0) x)xx m²s
[r = s) ạ Ø (yfe(())) (0) x)ax
Noting that || < and |b <
J.
that the maximum eigen-value of
(8i (dP((y.f(x))) fo(x))/00,000 )m is upper bounded by
M def
(K? + K2).
4m
21

---

Under review as a conference paper at ICLR 2020
Indeed, for (ur) such that Σ |10112 S 1, (U, R, we have
2
t Ply. fo(x))
8 (z)
m
m
00,00,
U/
m28
Σ
a,d (0, 20,20,,20
+
m
('fff(z)) Σ
a, (v, x)²
Kf
m
K₂ m
Σ
|| ll2
+ m
1rr12
4m 29
K²
K₂
(vml|(ll2)
+
4m
m
K?
K₂
4m
m
1
4m:2-1 (K} + K2).
Therefore, the loss function L(6) is M- M-Lipschitz smooth with respect to Q that is, for
M
- C(O') - [()) + (VC(O), 0' 0) + 2 ||0' 012
Plugging θ (!!)) and O' ((+11) θ V)((((()) into this inequality, we get
((0(++1) < ((((1) 17 (1 nM
2 |
1 (((0)) "/1 (
where used 1) S 1/M for the last inequality. By summing this inequality over & {0, ..., T - 13 and multiplying by n we get
1
2 (() log(2),
2
1B nIT
(23)
T
r/T
where we used L(O(0)) = log(2). Therefore, we have that from equation 23
||@(0) - ( 12 12 Sn
VeL(O!))
2
1=
S <nVT
2n/Tloo((2)
The last statement of Proposition
immediately follows from this and the following inequality.
m
|
(()
Σ
(0())
0 l12
2.1
m
Σ
1000 0 11
S mm
= / 0
(0) 1|2.
E PROOFS FOR GENERALIZATION BOUNDS
Proof of Proposition In this proof, we denote F = FY m. and Ω2 = 2g for simplicity. We
define F, def (1((.)) X 10 h F}. Then, for given dataset S (Ir, yo) notice
22

---

Under review as a conference paper at ICLR 2020
that s)) R(Filx)+ R(F-1lx), where X = (z)) Thus, it is enough provide upper bound on ((Filx) because a bound on the other complexity can be also derived in the same way.
We first give uniform high probability bound on the initialization |10; ||2 for Vr E {I....,, m.. We get from (A2), for t > 0,
|10,0) 12 2 t
[10 112 21 S m. exp(exp(bbb"
max mm
Thus, by choosing so that 6 m. exp( (bbx(-bt)), ), we confirm that with probability at least 6,
max rE (1....m) 10000 S R def
mA
log
We introduce several notations. Fix Ro > 0. We denote 0 = (0,00) E R22d 00,0' E RR) and, define for 0,
(x) def o00 2) ((8 x)
10 0'112
When 8'. we define (z(x) = 0. From the Lipschitz continuity of o, the range gy is 1-K,, Ki). Moreover, define
Ω def
{0 I 2d
|10|2 10 - R+ Dmm,T 10- 0'112 S D
2 def
(0 E 2
Ro < ||0 1/ - D D
Ω def (0 e
|10 12 < Ro).
9+ def
Ki]
E [+}
9- def
1 [-K,, Ki]
de {T
H def (fe X' + R E)
Clearly, we see
2 .2 uu+ and {97 0 E Q = G_ Ug+.
From the Lipschitz continuity of ly, we find R(Fixx) - 7 xx)
We now derive an upper bound on the Rademacher complexity. Set Cs def mà D D.m.T.
n
R(H(
E
sup
(f)(
72
BER
I
sup BER
(f((())))) (2:o
7
m
ar (o(0)..)) x.) - -0(00)) 2:))
E
sup
E m
n
BER
Cm
1>
172
0
0:00)
a10, xs) o ( x4,)
g
sup
CmmB ar
(24)
n
BEN
10, (0)
i=1
where we used the fact that feros (I:;) is constant in the expectation for the second equality. Since, for θ E Ω
10,
(0) 1l <
m 1 1
( ||2 < 1,
CarmB
CM
23

---

Under review as a conference paper at ICLR 2020
equation 24
can be upper- bouedeb by the Rademacher complexity of the convex hull. Hence,
CM E
O0, x4) - - Rz}
R(H[x) -
sup eEN
Σer
b,
1 8/'122 1|
E b, S1,,
i=1
CM
( xz) - 000 T xz))
E
sup
10, 02112
(0.,8,) -- ElT 51,,
==1 r=1
CM
o0 xz)
000 xi)
E
sup
10 0'
( i=1
Ca
sup
oEn
C'sd
E
sup
(g(0)) + sup Σ (g(xz) = C'M (# +(9+l))) (25)
9E9
gE9+
i=1
We used that for ④ E Ω (0., Moreover, the term a, disappeared by the symmetry. We used the fact that the convex hull of a hypothesis class does not increase the Rademacher complexity for the first equality.
(vr E (I....,m}) because ||0 e ll D Dmm,. T-
We next derive an upper bound on the Rademacher complexity R(G+ Ix) through the covering number (g 1 ex,e, |I ( and Lemma 2
To this end, we investigate the sensitivity of !| with respect
follows.
Let 01
(01, 01) E 52+ and B2 (02. (2) Q4 be parameters such that
10 82l12 / |10 0g 12 + 100 - 02112 I e.
This leads
10 22. 100 0/112 S e and |||0 - 8i112 110₂ 8allal s 2c.
We get from these inequalities that for || 1
||02 0% (2(00(0 x) a06 Te x)) - 110 8112(0(03 -(6
197, (z)) 9Tg (x:)
10: 11221102 0% 22
(112- 0/112
|00 (1 -o(0 o0(Tx))) x))
||0 8 102 - 8/112
10: 01112(0 (0T) a(8(Tz) x) o o00 x) aB8T x))
01 0/1121122 0/112
4D, AD Aem,
Thus, if 100 02112 S for 0,, 02 [2. then 1197, I7 al,0 S 4D 44nmmrrKKs/ R2. Since,
9+ 19o 101|2 2R 2D m.,,m 0 E RR2dd.
we get for the unit-ball B, c 2d with respect to || 112,
RG.
lx, (lx)) s CPN
B1, KR + D ) 1l lll
where Cj > 0 is a uniform constant. Hence,
Ki Ki(DD n, + D2 P ))
log 1og,N(G+ (lo0) 5 ddlog 1+
R2g
24

---

Under review as a conference paper at ICLR 2020
Applying Lemma 2 with
K1/ Vn,
obtain
Vn(RD n.m.I + D
n.m.T
R(++(x) = 0
Ki
log
+
(26)
n
Rg
We next evaluate R(G-Ix) (x) by using linear approximation. Since lo"(.) S K2, we get
ao z) a00 x) 0'(00'''000)0) z) 0)Txx( s K2 - 011..
Therefore, we get for 0 (0,6)) n__
9a (x(2) d' (0 - -0) |0 0
< K2 0 0'1 S K2Ro-
From this approximation, the Rademacher complexity can be bounded as follows.
T1
0'00 x,) 0) xi
[x)-Ix)= S Ro
+
E
sup AE
n
10 12
1=1
n Σ
S K2Ro + -E
sup
G0 (0 (OTxx:)uu xx) Ti
n
1011 I++ Dm.m. i=1 1wlls
When v 100 - 0212 + |lw1 2212 I for 110,1l2 S R Dmm,. and |20/12 I 1, we get for
| _
lo [0, x:ws x o' o'(0 x) x| s (( (0) x)) (0 x)))) x 1o (0T w2) Tl
$ [Ki + K2)c.
We set
G'_ def (00 x)w |10|| S R Dm,,, ||w|2 S 1}. Therefore, by the same argument as the case of G+, the following bound holds.
N(GG'xx,e, 11 s C&N Bi, (Ki KR)(R D Dmm,T) || l12
e
where C2 > O is a uniform constant. Hence,
log Log.Vl''lx,,,lll (1x)) 50 dlog (1 (Ki + K2) + Dom,.T)
By Lemma with Vr, we get
d log (1 +1 vn((k + K2) + D Do.m.T))
RGG 1x) < 0 K2Ro + V
(27)
Combining (25). 26 27
with Ro = v d/n, and Lipschiz continuity of Ly we obtain
m Dym..T (1 + K1 + K2) log (n(1 + K₃ + K2) + D)m,r))
R(Flx) so
Now, let us turn to the second part of Proposition 8 Let us assume that the function a is convex and Satisfies (0) 0. The main argument the convexity of activation function in the same spirit as (Chinot et al. 2019). As for the first part, with probability larger than 1 over the initialization
|0(00 1|2 < R
def
log
mA
re mm.....m
25

---

Under review as a conference paper at ICLR 2020
We only focus on the control of R(H)x).
T2
x(HIx)
-E
E
sup
(z:)
T1
eEΩ
E
sup
c (fe(x)) facos (z)))
n
eEn
m
n
E
sup BEN
G
m
ar
(o 1z) o ( x;))
E
Σ (Mr)EA
G ay
(a x;)) -00 xi))
sup 9En
m
n
E
1
Σ (6,))
E "33 (a(0(0)T x2) - x(0fxx:))
sup een
n
where A= ((i,r) E (1, ,n} x (1,-.. , : x0 - -0 xx,) 2 0}.
Let us control the first term (i.e for (i,r) E A). For any r in let Uhr IR + R defined for all E R as:
(u) = o(u 0000" x1) "0 x²)
The functions ,v,, are such that (0), O. There are convex because o is. In particular for any )
2 and u E IR, (au) 2 an/i,-(u) (u). We also have vhe
2:2) = (0 -0) -00(0 x;).
Since θ E Ω we have |0 e 2|2 < D DTm,. and for any r E [1, ... m). 10, - 0.50 0 1|2 S Dym,,
As consequence, for any (i,r) A, there exists Ber E [0, 1] such that
Dmmm.
Wi.r ((0, ((0))Tx:)) = Bir (
D Dm.m. (0, 0(00) )
110, - 0/01112
110 0 ll2
Since for any i E (I,... ,nI, Em= 100-000) 12 Ber S 1, we get
Cmmms
E sup eer (Kr))d
Σ
ar
(a x:) - ((8(0)TT..)) xx:))
m
Cm E n D Dmm.
10, 0,.0
(Dn.m - - )
Σ Gar Carm BerVerr
sup
110 - 0:00 l|
(=(0,)mm
2 -100--00000000000000000000000000 0
D mo (K.))E
1 Cm E
n
m
nt Dr Dmmm
sup @= m :0 < D. b= (b, m b. 2 $1
E
1 Cm E
sup @= 110 D T
a (0
+ (
T. D D
1m1
bm (b. D. 0. 1], E $1
26

---

Under review as a conference paper at ICLR 2020
Therefore, with probability larger than 6,
Σ
E ar m
(o x,) (
sup T ees
(i,r)E
1 Cm E
m
a, (.)) o 000 (0x)
sup
6
71. D Dnm.T
110,1125 D r: 1 b= 1m b. -.0.1) 2.01), 51
1 Cm E
(a(((( + +0) + sup Σ Go ( xx))
sup
n. D Dum,T
D 10001:100.1. i=1
10.115 i=1
K1 CM
c + +0) 24
c Iz
sup
sup
n Dymo.T
Do..0 r::l0.. 11:5
11+
K1
CM
K Kym 1/2-112-00 ( + 2R)
(D (Dym, + 2R)
Vn Dymm.
vn
Let us turn to the second term. For any (i. in A let Virr R + R defined for all u E R as:
Ger (u) ouu 0. 2;) o (0.
We have Vi.- ((o.)) TT;)) = a 00T probability larger than 6, we obtain,
0 xx)) σ (67 x.)). Using the same path as for (i,5) E A. with
B sup OER
Σ (ir)EA=
"mo (o(0(0)T:) x.,) o(ff..))))
1 Cm E
a (a((0, + 0,) 0 10 xi))
sup 10.11225 on 1R+ D mm xm1 6=1b, 1m b. "m 51
Tt. D D..m.
pm
Ki CM
(3D 21)
V D Dmm,
27


Reviews:
[{"review_id": "rylWgpohKS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors study the problem of binary logistic regression in a two-layer network with a smooth activation function.  They introduce a separability assumption on the dataset using the neural tangent model.  This separability assumption is weaker than the more Neural Tangent Kernel assumption that has been extensively studied in the regression literature.  In that case, a certain Gram-matrix must be nonnegative.  In the current work, the authors observe that the structure of the logistic loss in the binary classification problem restricts the functional gradients to lie in a particular space, meaning that nonnegative of the Gram-matrix is only needed on a subspace.  This is the underlying theoretical reason for why they can get improvement over those methods in the setting they study.  Under the separability assumption, the authors prove convergent gradient descent and generalization of the ensuring net, while assuming the two-layer networks are less overparameterized than what would have been possible under the Gram-matrix perspective.  \n\nThis paper appears to be a significant contribution to the field of convergent gradient descent algorithms because of the introduction of a weaker condition that guarantees convergence.  While the work only applies to smooth activations and to logistic loss classification problems, it can inspire additional work both in rigorous guarantees for training neural nets in regression and classification.  As a result, I recommend the paper be accepted for ICLR.\n\nMinor comments:\n\n(1) The abstract, title, and introduction emphasize the aspect of being \"less overparameterized\" than other methods.  It would be helpful to readers to have an absolute claim instead of a relative claim.\n(2) The abstract claims the separability assumption is \"more reasonable\" than the positivity condition.  This claim is overly vague and should be clarified.\n(3) There is a stray \\forall in the third line of Theorem 2.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "SygjVAKaYS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studied the generalization performance of gradient descent for training over-parameterized two-layer neural networks on classification problems. The authors proved that under a neural tangent based separability assumption, as long as the neural network width is $\\Omega(\\epsilon^{-1})$, the number of training examples is $\\tilde\\Omega(\\epsilon^{-4})$, within $O(\\epsilon^{-2})$ iterations GD can achieve expected $\\epsilon$-classification error.\n\nOverall this paper is well written and easy to follow. The theoretical results on the neural network width and iteration complexity are interesting. \n\nMy major concern is that the comparison with Allen-Zhu et al and Cao & Gu seem somewhat unfair. First, Allen-Zhu et al and Cao & Gu both studied the generalization performance of GD for training multi-layer neural networks, which is fundamentally more difficult than two-layer networks. Second, they use ReLU activation functions, which brings in the nonsmoothness along the optimization trajectory. This would also make the condition on the neural network width become worse. Therefore, when claiming the advantage of the derived guarantees, the authors should clearly clarify such differences.\n\nAnother concern is that whether the derived theoretical results can be generalized to ReLU network?\n\nWhen proving the generalization result, this paper takes advantage of margin-based generalization error bound. However, the generalization results in Cao & Gu are proved via applying standard empirical Rademacher complexity based generalization error bound. I would wonder which technique can give a tighter bound?\n\nCan you provide some examples regarding which type of data can satisfy Assumption (A.4) with constant margin $\\rho$?\n\n The authors would like to briefly discuss another data separation assumption adopted in the following papers (although this assumption is typically made for regression problem).\n\n[1] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via overparameterization. arXiv preprint arXiv:1811.03962, 2018b.\n[2] Allen-Zhu, Z., Li, Y. and Song, Z. (2018c). On the convergence rate of training recurrent neural networks. arXiv preprint arXiv:1810.12065 .\n[3] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint arXiv:1811.08888, 2018.\n[4] Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterization: global convergence guarantees for training shallow neural networks. arXiv preprint arXiv:1902.04674, 2019.\n[5] Difan Zou and Quanquan Gu. An improved analysis of training over-parameterized deep neural networks. arXiv preprint arXiv:1906.04688, 2019.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "S1lRoqAaKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the training of over-parameterized two layer neural networks with smooth activation functions. In particular, this paper establishes convergence guarantee as well as generalization error bounds under an assumption that the data can be separated by a neural tangent model. The authors also show that the network width requirement in this paper is milder than the existing results for ReLU networks.\n\nIn terms of significance, I think this paper is slightly incremental. As is discussed in the paper, results on both convergence and generalization have already been established in earlier works even for deep networks. The major contribution of this paper is probably the weaker requirement of network width, as is shown in Table 1. However, all other results in Table 1 are for ReLU networks, and it has been discussed in Oymak & Soltanolkotabi, 2019 that the over-parameterization condition for smooth activation functions are naturally weaker than that for ReLU networks. Although Oymak & Soltanolkotabi, 2019 did not study generalization, based on their discussion, the result in this paper is not surprising. Moreover, the authors should probably add comparison to Cao & Gu, 2019b in Table 1.\n\nMoreover, the results in this paper is restricted to two-layer networks with fixed second layer weights. This seems to be a much simpler setting than many existing results. The definition of neural tangent kernel in equation (5), as a result, seems to be over simplified, compared to the original definition given in Jacot et al., 2018. The improvement of requirement in network width, which is the major contribution of this paper, might not be very meaningful if it only works for shallow networks.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This article studies gradient optimization for classification problems with shallow networks with smooth activations, obtaining convergence and generalisation results under a separability assumption on the data. The results are obtained under much less stringent requirements on the width of the network than other related recent works. However, with results on convergence and generalisation having been established in other previous works, the reviewers found the contribution incremental. The responses clarified some of the distinctive challenges with the logistic loss compared with the squared loss that has been considered in other works, and provided examples for the separability assumption. Overall, the article makes important contributions in the case of classification problems. However, with many recent works addressing challenging problems in a similar direction, the bar has been set quite high. As pointed out by some of the reviewers, the contribution could gain substantially in relevance and make a more convincing case by addressing extensions to non smooth activations and deep models. 
Decision: Reject