Subquadratic Overparameterization for Shallow Neural Networks
Authors: Chaehwan Song
Ali Ramezani-Kebrya
Thomas Pethick
Armin Eftekhari
Volkan Cevher
Venue: NeurIPS 2021 Poster (2021)
Keywords: Overparameterization
Gradient Descent
Neural Networks
Global Convergence
Initialization

Abstract: Overparameterization refers to the important phenomenon where the width of a neural network is chosen such that learning algorithms can provably attain zero loss in nonconvex training. The existing theory establishes such global convergence using various initialization strategies, training modifications, and width scalings. In particular, the state-of-the-art results require the width to scale quadratically with the number of training data under standard initialization strategies used in practice for best generalization performance. In contrast, the most recent results obtain linear scaling either with requiring initializations that lead to the "lazy-training",  or training only a single layer. In this work, we provide an analytical framework that allows us to adopt standard initialization strategies, possibly avoid lazy training, and train all layers simultaneously in basic shallow neural networks while attaining  a desirable subquadratic scaling on the network width. We achieve the desiderata via Polyak-Lojasiewicz condition, smoothness, and standard assumptions on data, and use tools from random matrix theory.

Subquadratic Overparameterization for Shallow Neural Networks
Chaehwan Song
Ali Ramezani-Kebryal
Thomas Pethick
Armin Eftekhari
Volkan Cevher!
'Laboratory for Information and Inference Systems (LIONS), EPFL Umea University
ali. ramezani@eefll.c
Abstract
Overparameterization refers to the important phenomenon where width of a neural network is chosen such that learning algorithms provably attain zero loss in nonconvex training. The existing theory establishes such global convergence using various initialization strategies, training modifications, and width scalings. In particular, the state-of-the results require the width to scale quadratically with the number of training data under standard initialization strategies used in practice for best generalization performance. In contrast, the most recent results obtain linear scaling either with requiring initializations that lead to the "lazy-training training only a single layer. In this work, we provide an analytical framework that allows adopt standard initialization strategies, possibly avoid lazy training, and train all layers simultaneously in basic shallow neural networks while attaining desirable subquadratic scaling on the network width. We achieve the desiderata via Aalyak--ojjsiewiizz condition, smoothness, and standard assumptions on data, and use tools from random matrix theory.
Introduction
Training neural network involves solving a nonconvex optimization problem, which, in theory, might trap first-order methods such gradient descent to fall in bad local minima saddle points. However, empirical evidence suggests that first-order methods with random initialization can consistently find global minimum, even with randomized labels [43]. Demystifying this observation is of central interest to deep learning.
Recently, a line of research [45, 4, 11, 29, 39, 12, 38] suggests that such an empirical success can possibly be explained by the overparameterization of neural networks, whose number of parameters exceeds the number of training data n. In particular, gradient descent converges linearly fast to global optimum in a number of problems with models that have wide hidden layers [45, 12. 39].
Despite of these remarkable results, the natural key question "How much should we overparameterize neural network?" remains open even for the toy example of two-layer neural networks. On one hand, widely accepted that, for two-layer neural networks, the number of parameters should grow linearly with (e.g., [21, 38]). On the other hand, theoretical results either require much more parameters, or they are established under restrictive settings. Specifically,
Equual contributions.
1 This work was done while Armin Eltekhari was at EPFL.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table 1: Scaling with the number of training data in the overparametierization regime.
QL=quadratic loss,
cLLvzo and Lipschitz loss, SD=separable data.
Depth
Algorithm
Setting
Activation
Scaling
Reference
2
GD on layer 1
QL
ReLU
S2(2))
Oymak and Soltanolkotabi [38]
L
GD layer L
CLL
ReLU
[(n))
Kawaguchi and Huang [21]
2
GD
SD
ReLU (2(n²)
Song and Yang [39]
2
GD
SD and QL
ReLU (2(n))
al. [12]
L
GD
SD and QL
ReLU Q(n5L*
Zou and Gu [44]
2
GD
QL
Smooth
((n2)
This paper
Kawaguchi and Huang [21] has proven the ideal (2(n) scaling for deep neural networks. However, they apply gradient descent only to the last layer, which is not the case in practical scenarios.
similar issue exists [39, 38), where the authors have shown that (t(")) parameters suffice for two-layer neural networks, but only the first layers are trained. Furthermore, even with infinite width, Oymak and Soltanolkotabi [38] cannot guarantee zero training error with probability approaching to one.
The goal of this paper is to close the gap between theory and practice, without resorting to unrealistic assumptions such as those discussed above. We sharpen the results of Oymak and Soltanolkotabi [38] by proving that, with proper random initialization of each layer, training error approaches to zero with high probability, exponentially fast in the width of the network. In addition, we show that only (m parameters suffice such that gradient descent converges to global minimum with linear rate, which improves upon the state-of-the-ard by factor of Ö(n²), We summarize the bounds on the number of parameters terms of n in Table
While our analysis on gradient descent focuses on training error, it has been observed that overparam- eterization can lead poor generalization. In particular, [7, 42, 15] have observed the phenomenon of lazy training. Chizat et al. [7] has explained lazy training as model behaves similar to its linearization around the initialization. is known that an overparameterized neural network likely to be trapped in the lazy regime since the parameters will hardly vary over the course of training with gradient descent [12, 29, 45J. The same phenomenon has been observed for infinitely wide neural networks [19]. In this paper, we provide theoretical guidance to possibly avoid lazy training through proper initialization. Experimental results confirm that lazy training might be avoided with our theoretically inspired initialization so that the issues reported in [7] do not apply.
1.1 Summary of contributions
We first focus general minimization problem assuming that the loss function satisfies Polyak- Lojasiewicz (PL. condition. We find sufficient conditions terms of initialization for the conver- gence of gradient flow and gradient descent to a global minimum.
We then focus on the special problem of training two-layer neural network with quadratic loss and smooth activation, and show that ②( parameters are sufficient for gradient descent to converge global minimum with linear rate and probability approaching one. We achieve linear scaling for the width when the number of input features is in ((vn).
We theoretically guide how to initialize the parameters of neural network the overparameterized regime of interest while possibly avoiding lazy training.
1.2 Further related work
In terms of techniques, our paper is closely related to [37, 38). Similar to our Theorem 3, Oymak and Soltanolkotabi [38, Theorem 2.1] showed that gradient descent converges with linear rate when the Jacobian of the nonlinear mapping has smooth deviations, and the number of parameters grows quadratically with n. However, Oymak and Soltanolkotabi [38] assumed that gradient descent updates only the first layer. In this paper, we consider the case where gradient descent updates both layers simultaneously, and show that it suffices to have ( parameters with linear rate of convergence.

---

ReLU is an important instance of activation functions that does not satisfy the smoothness assumption. line of research aims to relax this assumption by instead assuming the data is separable. For shallow neural networks, Du et al. [12] proved that gradient descent finds a global minimum if the width of the network scales (2(2)) assuming that no two data points are parallel. In similar setting, Song and Yang [39] established convergence to global minimum with the sufficient width of ((n"). As result, the absence of the smoothness assumption, these papers require substantially more number of parameters to guarantee convergence
global minimum.
The theoretical bounds for deep neural networks are even worse. For instance, Allen- et al. [1] required the total number of parameters of (2 122) where L. is the number of layers. Zou and Gu [44] improved the scaling to (2)) In our setting, í.e., L = 2. these bounds become vacuous in most interesting regimes. Further, [21], the authors showed that ②n)) parameters is enough to achieve global convergence under the assumption that gradient descent updates only the last layer, which essentially reduces the problem to a simple least-squares regression.
Recently, Ji and Telgarsky [20], Chen et al. [5] showed that polylogarithmic width suffices to achieve convergence for shallow and deep neural networks in an ergodic sense. We note that this is a weaker notion of convergence compared to the one we consider.
Li et al. [28] showed that gradient descent along with early stopping are robust to label noise constant fraction of labels in an overparameterized network. However, only the first layer is optimized in [28]. For possibly overparameterized and linear networks, Eftekhari [14] showed that gradient flow can successfully avoid lazy training assuming that the network has a layer with a single neuron. We note that our analysis does not require those restrictions.
Under an assumption similar to PL condition, Zou et al. [45] studied the problem of binary classifica- tion for deep network with ReLU activation, which is different problem compared to ours. In [40], the authors proved that gradient descent with overparameterization achieves erro-approiimation when the underlying function that generates the labels has low-rank approximation. Their scaling requires perfect information about the target function, which is not the case in our paper. Under a variant of Xavier initialization, Daniely [9] found near optimal scaling for binary classification problem trained by stochastic gradient descent. We note that the setting considered in our paper is more challenging than binary classification. Our results establish new state-of-the-art on the required number of parameters in a nonrestrictive setting when both layers are trained at the same time. Recently, Nguyen and Mondelli [34] obtained subquadratic scaling for deep neural network with pyramidal structure under an initialization that leads to lazy training. Our results do not have such restrictions.
field analysis was used to approximate a target distribution of parameters of a neural network by the empirical distributions [33, 32). However, these results do not provide useful bounds on the scaling in terms of n. which is our focus in this paper.
Liu et al. [31] established global convergence when the function to minimize satisfies variant of PL. condition (local PI. condition) assuming the map is Lipschitz continuous, which not the case in our paper. Liu et al. [30] characterized the constancy of the neural tangent kernel via scaling properties of the norm of the Hessian matrix of the network. In this work, we focus on obtaining a sufficient number of parameters for gradient descent to converge to global minimum with linear rate.
Notation. We use || to represent the Euclidean norm of a vector and Frobenius norm of matrix. We use V to denote the Jacobian of a vector-valued and gradient of a scalar-valued function and (4b(a) [b} to represent the directional derivative of & along b. We use @ and & to denote the Hadamard (entry-wise) product and Kronecker product, respectively. For A E pmxx and E Z4. we denote 4 E gmm x with its a-th column defined as vec(a,, @ ... @ x.) E Rmn", We use lower-case bold font to denote vectors. Sets and scalars are represented by calligraphic and standard fonts, respectively. We use [n] to denote {1...., ,n) n for an integer n. We use Ô and i to hide logarithmic factors and use S to ignore terms up to constant and logarithmic factors.
2 Problem, definitions, and assumptions
In this section, we set up a general compositional optimization problem. Then we focus on the special case of shallow neural networks in Section 5.
3

---

Let w E R. denote a parameter vector where d denotes the number of parameters. In neural network, w consists weights and biases of all layers. We consider the minimization problem
min h(w)
wER-
where h IR + R2 is the composition of loss function f Rd - R4 and nonlinear and nonconvex function 4 12 RR: h(w) f(((w))) f(z)
(2)
where = ((w).
Before providing the details, let us highlight the simple idea behind the argument (see also [37]). Let wo and w denote the initial point and limit point when the gradient descent algorithm is run with some learning rate, respectively. The precise formulation of gradient descent is provided in Section Let (w) IRd + Rd denote the adjoint operator of V (T((W). Since w a first-order stationary point of h, have
Vh(ww V (w) (V)(z)}
where 2 = (W).. Suppose that 4 (w) ) is nonsingular operator Then V 0. If is a global minimizer of f. then W a global minimizer of h. To prove global convergence, suffices show that v4" is nonsingular within neighborhood of the initialization Wo, and that points reached by gradient descent remain within this neighborhood. We will prove that both statements hold with high probability for shallow neural networks.
We first define notions that useful to state key lemma for main results:
Definition 1 (Near-isometry). A linear mapping T Rd + Rd is (#, 2/) near-isometry if there exist 0 < μ E v such that
1 S T (T) S muax (T) S V.
(3)
Definition 2 (Smoothness). Let Bg > 0. A function vb Rd - Rd is Sa-smooth, if for all u, E Rdh, we have
max (u)( - V(((v)) S u v/|-
(4)
The following lemma shows that smooth function, which is near-isometry initialization, remains wear-isomeery for all nearby points of the initialization.
Lemma 1. Suppose that & 3g -a-shooth and V4' (Wo) is (Ha. (aaavva))--aate neaar---iris..rry. Then, for all E (al pa)), we have
324
< min (Tb((w) S F [bb(ww) -
(5)
where
Pg
2
Intuitively, if (wo(w)) is
(H4, nea----nrissmetttyy then one would expect 4 to remain near-
isometry for all nearby points.
Definition 3 (PI. condition [3]). function 1/ Rdd R satisfies the PL condition if there exists ag 0 such that, for all u E Rd, we have
Vib(2))1
(u S
20p
We note that strongly convex functions satisfy minor variation of the PL condition in (7).
In analysis, we will assume that & and f satisfy the following properties: Assumption 1 (Basic assumptions for 4, f).

---

t is wifce-diffeeettablee and B smooth.
is twice-differentiabll, satisfies the PL condition with a and min f(z)
Despite f satisfies the PL condition, the nonconvex can render nonconvex, and hence difficult minimize in theory. However, we show that fast convergence of gradient descent to a global minimum can be established with appropriate initialization.
The intuition behind these assumptions is that to achieve nonsingularity of VØ", we approximate V (wo) at initialization and bound v (wo) V (w,"(;;) at iteration using the fact that w wWo-w,l will sufficiently small by the overparameterization. In the special case of shallow neural networks, we expect similar argument applies even when the activation function is ReLU. Adapting analysis for such extensions is an interesting area of future work.
Gradient flow
In this section, we consider gradient flow, which can be viewed as the limit of gradient descent for infinitesimally small learning rates. Inspired by the analysis of gradient flow, we provide an upper bound on the length of the trajectory traversed by gradient descent iterates and then find a sufficient condition in terms initialization to establish its convergence to a global minimum. We focus on gradient descent in Section 4.
Let and consider the gradient flow, which is initialized at wo Rd and traverses the curve R + Rd. given by
d7(() vh(T(()) +()) dt
where 7(0) Wo-
We now calculate the length of the curve Suppose that VΦ (wo) is (μx, ux -eea-rii-ism Using Lemma 1, in the following lemma, we control the length inside of ball (Wo, pa). See Appendix B for the proof.
Lemma 2. Les and let E(t) denote the length of the curve oy in (8), restricted to the interval [0, t). Let to E oo] be the smallest value such that (ta) & ball(wo, Po). Suppose 7h (wo) is (p), ( near-isomeery Then, for all < to. we have
( v0 (w()))
e(t) 0
Lemma implies that the objective value at initialization, lu(wo). sufficiently small, then we can localize gradient flows to region around Wo. Combining with Lemma 1, we show that the limit point of gradient flow is a global minimum. This theorem formally stated below.
Theorem (Gradient flow). Let wo Rd. Suppose that & and f satisfy Assumption I and 7 (wo) (pa, V4) near-isometry. If Wo satisfies
(aspu
h(wo) =
32 2
then the gradient flow in (8) converges to global minimum.
Proof of Theorem I. Proper initialization in (9) ensures ((t+) ) < ps. which implies that (n((t) woll = 11>(t)) -()l < Po-
(10)
Therefore, 71)) E ball(wo- Pq) for / 2 0. and the length of 7 upper bounded by Pe using Lemma 2. Hence, the gradient flow 7 converges, i.e., the limit point E Rd exists and satisfies
w woll < pa.
(11)
Combining (5) and (1I, we have
ps 2
32g
<
Omin
V4 (w) < Fmax [V*(w)
<
2
In particular, we note that V (w) is nonsingular, So we have Vf(²) = 0. Since f satisfies the PI. condition in (7), is global minimizer of f. and is global minimizer of h in (1).
D
5

---

Gradient descent
We now view gradient descent as the discretization of gradient flow, and show that similar argument as in Section holds for gradient descent.
Let 77 denote the learning rate and let i 2 0. The gradient descent update rule is given by
Wi+1 W; v/Vh(w.).
(12)
To study gradient descent, in addition the previous assumptions on and for the case of gradient flow described in Theorem 1, we also assume that is smooth, i.e., there exists B 2 0 such that, for all z, z' E 1R, we have
f(z) (1)) v.VZ)) + 5 2 2/11
Smoothness of f allows safe discretization of gradient flow without deviating too much from its trajectory. The following result is the analogue of Theorem for gradient descent; see Appendix C for the proof.
Theorem (Gradient descent). Let wo E Rd. Suppose that & and satisfy Assumption 1, f is By- smooth, and <4" (Wo) is (ua, (eee)--nar-ssmeee Suppose that gradient descent executed with sufficiently small learning rate
B Vf + 31H4 + B / 0
(13)
and Wo satisfies (9).
Then the sequence of iterates {wi] converges to a global minimum of h exponentially fast. In addition, the rate of convergence is given by
h(w,)) & (1 Cnanaaa
(14)
where C is universal constant.
To prove Theorem 2, we first compute the length of the trajectory traversed by gradient descent iterates. We then the smoothness of and follow the descent inequality to lower bound f(z:) [(z++ Finally, we compute the local Lipschitz constant of f-
Remark 1. The idea of initializing a nonconvex problem close to a global minimum has a long history in nonconvex optimization, particularly in matrix factorization; see [6] and references therein. The observation that the length of the learning trajectory is short in the overparameterization regime has precedent in [12, 37]. From algorithmic perspective, the idea of linearizing & when minimizing f o & is studied in nonlinear regression and the Gauss-Newton method [35].
In order to apply Theorem 2, the key step is to verify that h(wo) satisfies (9). In Section 5, we focus on the special case of shallow neural networks and improve the state of the art.
Shallow neural networks
In this section, consider the problem of training shallow neural networks with gradient descent. Our strategy is to cast this problem as a special case problem (1) and then apply Theorem 2 to establish global convergence. We start with the formal problem statement.
5.1 Setup, assumptions, and initialization
Consider shallow neural network with dg inputs, one hidden layer that consists of dj hidden nodes, and d2 outputs. This shallow network is specified by the map
I do + d2
(15)
x + V (WW))

---

where W E Rdixdo, V E Rdaxd and Φ R + R is an activation function, which is applied eitry-wise. Let x; R and y/ R denote the i-th training data and label, respectively, for i E [n]. By concatenating the training data and their labels, we form the matrices X E RRdxx and Y E _ddxx, Let denote θ = (W, V) E R4 xdo x ddda and Z = + = V V (WWX) E B2dax. The fitting problem can be cast (1) where
h(O) l(((0)) = IV (W - YI
(16)
We assume that the activation function Φ IR - R is twice-differentiable Despite this assumption excludes the popular ReLU, it is still possible apply our results to smooth approxi- mations of ReLU such as the softplus or Gaussian error Linear Units (GeLU) [18, 34). We note that softplus [13] or GeLU [10] often achieve similar superior performance compared to the ReLU [8, 16, 23, 22, 41].
Remark 2.
Definition 4 (Hermite norm [36]). Let : The Hermite norm of & is given by ||ol|
VD= of where os denotes the i-th Hermite coefficients of & given by:
1 2 ((x)):())
(-2
(- x²
G == (6, 9.)h
dx
and qi IR + the i-th Hermite polynomial for
In this section, we assume that o, f. and data satisfy the following properties: Assumption (Assumptions for shallow neural networks).
é is wiice-differentiable, <(0) O. supa ld(a)) Puuxx < 00, supa [(aa &maxx < 0o, and |0ll < cc. The loss function f is quadratic (16).
||x 1, ||Y|| S 1, and max (V&) O
Ómaa
fori E [n]] and k 2 0.
The assumption on & hold for GeLU, sigmoid, and tanh. The assumption (00) = 0 is to simplify the derivations and we suspect that it can be removed at the expense of more complicated expressions. The bounded Hermite norm is a mild assumption, which is used to obtain an upper bound on (max(6(W"0)) in terms of the Hermite coefficients of é. See Appendix E. for details. The assumption on the data is fairly mild and standard in the overparameterization literature as we can always normalize the data [29, 20]. Similar boundedness assumptions to the last assumption commonly used in nonconvex optimization to guarantee convergence [24]. Moreover, such a bound naturally holds by applying projection step the gradient descent update rule, which we plan to adopt as a future work.
Initialization. We first consider the initialization scheme:
Wo (0,,
Vo ~N w))
(17)
In Section 6, we study the implications of our initialization and show how to possibly avoid lazy training by varying (Wi, w2).
5.2 Main results for shallow neural networks
For shallow networks as described above, we verify in Appendix D that the key conditions in Lemma hold with high probability. Combining with Theorem guarantees. The proof in Appendix E uses standard tools from random matrix theory to control the random variables involved with initialization. We first estimate variables μ4, ua defined in Definition I and Sp in (4) for the neural network described in Section 5.1.
establish the global convergence
Lemma (Estimation of pæ, Vvg 34). Suppose that a shallow neural network, which is constructed in Section 5.1, satisfies Assumption 2. Then we have
μi = mmin (d(WxX)).
(V)) + max (oWoX), 1чΦ δmax Tmax (X) (X)o max (Vo)
(18)
3q 22 mxxxxxx (X) (Ōmaxx mmax Xmuax
where Xmax supv max (V).

---

Remark 3. The terms min I (X())))) and max (oxx))())X)) in (18) play critical role in our analysis. In [12, 39], strictly positiveness of the eigenvalues of Gram matrix is the primary tool to show the convergence. Oymak and Soltanolkotabi [38] also followed similar argument using the neural network covariance matrix. The underlying intuition seems similar Lemma 3. However, the resulting bounds are different since gradient descent updates (W, V) simultaneousyy in our problem setup, which more realistic.
By combining Lemma 3 and the results on global convergence of gradient descent in Section 4, we establish global convergence for shallow neural network.
Theorem (Shallow network with gradient descent), Consider the shallow network described in Section 5.1 that satisfies Assumption 2 and -" (")]((a) S [é(Ta)] S +=*(o(a)) for all a, 0 < T and some constants r, T22 Suppose that O is randomly initialized as in (17) with wi and w2, which satisfy
wiw2 S
(19)
ddd
and suppose that the hidden layer width d1 satisfies
d1 = (ECCEECC (citi2o) T max (X)2 V T miin (X+
(20)
where Cs is set of constants, & is term independent da, n, L a constant such that dlj, and X E BR is derived from Khatri-Rao product with its a-th column defined as vec(z, 8.. -8.)) E
Rd,, Then gradient descent converges to a global minimum exponentially fast with probability at least 1 1b(0, d, d1, d2; X). x)-See See Appendix E.6 for the exact expressions of E and s/.
Remark 4. Theorem shows that, with sufficient degree of overparumeterization. gradient descent finds a global minimum, except with an arbitrary small probubility. Note that we need two conditions for Theorem 3 to hold, both of which are related to the overarraeterriztiinn of the network. The condition (19) is for the concentration of random matrices, to make arbitrary small, and (20) is for the locality of gradient descent.
5.3 Order analysis
We first decompose the random matrix o(X T6,TW, Jo(,,)) into independent random matrices. We then apply concentration inequalities to establish an upper bound on T (&(W and lower bound on awin (iin(p(( (o((x))) through the Hermite decomposition of ((WxX and note that with high probability,
di min (X') I Gmin (6Wx)))))))) S Tmax (mxx(((oX))) & V cfddn.
We also find an upper bound on h(Ov) at initialization. Substituting Vu. plp, Bq into (9), we obtain the sufficient condition in (20). We note that E(C,, f, Φ, (c/)22) can be viewed as a constant w.r.t. do, di, and For / = 1, it requires n do. which is not a common setting in practice. For t 2 2, we suppose that n ~ dj. which is the case in practice and estimate maxx
and
do
miin (X**)
a
along the lines of [38, Section 2.1]. Substituting Tmax (X) and T (X**)
into (20), we have
n
d1 do
(21)
Therefore, the overall overparameterization degree becomes dod1 a(n=)) which is sufficient for gradient descent find a global minimum at linear rate except with an arbitrary small probability. We note that optimal linear scaling for the width dj Ö(n) is sufficient when the number of input features is sufficiently large do (VV)), which improves upon the results of [38] by factor of Ö( 3). Furthermore, unlike [38], we adopt standard initialization strategies in Theorem
3 'The last assumption holds for popular activation functions such as sigmoid, tanh, and ELU, and can be relaxed w1 = (17).
be arbitrary small.

---

6 Lazy training and experimental evaluation
Following the theoretically motivated initial- ization in Theorem 3, we set W142 = ydga This gives rise to broad family of initializa- tion schemes as one varies the ratio w2/ /w/- In- terestingly, we note that popular initialization schemes such as LeCun [26] and He initializa- tion [17] belong this family. The purpose of this section is to empirically investigate the im- pact the choice of this ratio has on generalization of shallow networks.
1.00
0.99
Accureyy
He Initialization
0.97
Training accuracy Test accuracy
0.96
0.00
0.02
0.04
0.06
0.08
To this end, we will look the generalization error of varying initializations in the more practi- cal setting of stochastic gradient descent (SGD). Specifically, we fix the product of the weight initialization Wiw2 and then proceed by varying
Figure 1: Training and test error on MNIST for different w2. Error bars indicates the 95% confidence interval computed over independent runs. The setup details are provided in Appendix G.
w2- To ensure that perfect generalization is possible, we adopt the teacher-student setup, where, for the teacher network, we train a two-layer fully connected neural network, on MNIST [25] until SGD reaches zero training error. The student networks are trained for 300 epochs to ensure convergence. The results are shown in Figure We use mean-square loss and smooth activation function (GeLU [18]) for the student network to match the problem setup closely as possible.
In Figure 1, observe that while SGD achieves zero training eπror for every Wa, suggested by Theorem applicable in the full batch setting, the generalization ability increases as the ratio w2 /wi grows. It is also interesting to observe that the popular He initialization scheme corresponds to rather balanced ratio that lies at the boundary of the well-performing region. In our experiments, we used He initialization to fix the value W,w This tendency suggests that wide family of initialization schemes could generalize well as long as the ratio w2/w> is not too small.
Comment on lazy training. It is important to address the so called lazy regime when generalization of concern. Let
M())) = h(Oa) + (Vh(O,), - Oo)
be the linearized function of h around O and let θ and Ô; denote the iterates of gradient descent at time i. The lazy training regime refers to the case where the training trajectory stays close to this linearization, i.e. [l{(O;) A(O,))l = 0 for all [7]. Such linearization occurs in infinitely wide neural networks [7], which have been shown to generalize well some settings [2, 27J. However, in case of subquadratic (finite) width, the lazy regime might lead to poor generalization. To gain insight on when we cannot avoid it with certainty, let us make a simple rewriting of our network
assuming is homogeneous:
(0)) aV (W
with Vi ~ Ao,0 and Wo ~ (O, 1) where the standard deviations are pulled out as a scaling factor a Whns = 1/vdgu This seems to fit into an example in [7, Appendix A.2] suggesting lazy training dj -> co. However, their results require an odd activation function and infinite width, while our activation function is required not to be odd (see the proof in Appendix E) and our results under subquadratic (finite) width. Instead, to study lazy training, we explicitly compute an upper bound on [lА(O,) r(,)))l in Appendix F following [7, Theorem 2.3].
It turns out that the upper bound becomes DO when W1 < w2, and it becomes zero when w1 >> w2. Our analysis suggests that shallow neural networks can avoid lazy training provided that w2/w1 + co. This analysis is corroborated by the empirical results showing that the generalization capability improves
grows in Figure 1. On the other hand, if w2/w1 + O. then lazy training is bound to happen asymptotically. For details, see Appendix Finally, we note that we have not theoretically claimed that our initialization is guaranteed to be non-lazy, since doing so would require establishing
a lower bound on [|{(O,) h(Oe))) |]. which is an interesting problem for future work. Instead, our discussion above only provides necessary condition for non-lazy training, and sufficient condition for lazy training.

---

7 Conclusions and future work
In this paper, we prove the linear convergence of first-order methods on subquadratically overpa- rameterized two-layer neural networks with smooth activation functions. Our theoretical analysis is compatible with standard initialization strategies, which can potentially avoid lazy training. We train both layers simultaneously and achieve a desirable subquadratic scaling on the width of the network. In particular, the number of input features is sufficiently large do (V))). We use tools from random matrix theory under standard assumptions on data and leverage on the assumption that the loss satisfies Lojjsk-wwsiiwizzz condition. We carefully find an explicit upper bound and lower bound on singular values of the outputs of the first layer at initialization with high probability under general initialization.
note that linear scaling for the width d1 Ö(n) is sufficient when
It is natural to ask whether activation functions such as ReLU. We plan to adapt our analysis for such extensions as a future work. While analysis provides necessary condition for avoiding lazy training, it is interesting to develop sufficient conditions in the future. In particular, developing lower bounds on [[/(O;) -h(O.)) will be a key to fully characterize lazy training.
attain similar degree of overparameterizattion with nonsmooth
Finally, theoretical work, do not anticipate any potential negative societal impacts of our paper. However, the long-term impacts of our work may depend on how machine learning algorithms used in society.
Acknowledgments and Disclosure of F Funding
The authors would like to thank Fabian Latorre, Fanghui Liu, and Paul Rolland for helpful discussions.
This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement n 725594 time-data). This project was sponsored by the Department of the Navy, Office of Naval Research (ONR) under grant number N62909-17-1-211
This work was supported by Hasler Foundation Program: Cyber Human Systems (project number 16066). Research was sponsored by the Army Research Office and was accomplished under Grant Number W911NF-1---0404
References
[1] Zeyuan Alue Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-paramettrizzaioo.. In International Conference on Machine Learning (ICML), 2019.
[2] Sanjeev Arora, Simon S. Du, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang, and Dingli Yu. Harnessing the power of infinitely wide deep nets small-data tasks. In International Conference on Learning Representations (ICLR), 2020.
[3] Jérôme Bolte, Trong Phong Nguyen, Juan Peypouquet, and Bruce W Suter. From error bounds to the complexity of first-order descent methods for convex functions. Mathematical Programming, 165:471-5000 5077 2017.
[4] Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for ConvNet with Gaussian inputs. In International Conference on Machine Learning (ICML), 2017.
[5] Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much paramertttttiinnnoonnn is suf- ficient to learn deep ReLU networks? In International Conference on Learning Representations (ICLR), 2021.
[6] Yuejie Chi, Yue M Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Transactions Signal Processing (TSP), 67:5239-5269, 2019.
[7] Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable program- ming. In Advances in neural information processing systems (NeurIPS), 2019.
10

---

[8] Djork-Amé Clevert Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep net- work learning by exponential linear units (ELUs). In International Conference on Learning Representations (ICIRR) 2016.
[9] Amit Daniely. Neural networks learning and memorization with (almost) no over- parameterization. In Advances in neural information processing systems (NeurIPS), 2020.
[10] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training deep bidirectional transformers for language understanding, arXiv preprint vrXiv:181000480055 2019.
[11] Simon S. Du and Jason D. Lee. On the power of over-parametrrizaioo in neural networks with quadratic activation. In International Conference on Machine Learning (ICML), 2018.
[12] Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference Learning Representations (ICLR), 2019.
[13] Charles Dugas, Yoshua Bengio, François Bélisle, Claude Nadeau, and René Garcia. Incor- porating second-order functional knowledge for better option pricing. In Advances in neural information processing systems (NeurIPS), 2000.
[14] Armin Eftekhari. Training linear neural networks: Non-local convergence and complexity results. In International Conference Machine Learning (ICML), 2020.
[15] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Limitations of lazy training of two-layers neural networks. In Advances in neural information processing systems (NeurIPS), 2019.
[16] Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of Wasserstein GANs, Advances in neural information processing systems (NeurIPS), 2017.
[17) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on ImageNet classification. In Conference on Computer Vision and Pattern Recognition (CVPR), 2015.
[18] Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (GELU). arXiv preprint 160iv: 14l.v11666..8415v. 084.
2020.
[19] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems (NeurIPS). 2018.
[20] Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent achieve arbitrarily small test error with shallow ReLU networks. In International Conference on Learning Representations (ICLR), 2020.
[21] Kenji Kawaguchi and Jiaoyang Huang. Gradient descent finds global minima for generalizable deep neural networks of practical sizes. In Annual Allerton Conference on Communication, Control, and Computing, 2019.
[22] Youngjin Kim, Minjung Kim, and Gunhee Kim. Memorization precedes generation: Learn- ing unsupervised GANs with memory networks. In International Conference on Learning Representations (ICLR), 2018.
[23] Abhishek Kumar, Prasanna Sattigeri, and Tom Fletcher. Semi- Sumi-supereieed learning with GANs: Manifold invariance with improved inference. In Advances in neural information processing systems (NeurIPS), 2017.
[24] Fabian Latorre, Armin Eftekhari, and Volkan Cevher. Fast and provable ADMM for learning with generative priors. Advances in neural information processing systems (NeurIPS), 2019.
[25] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied document recognition. Proceedings of the IEEE, 06:2278-2332 1998.

---

[26] Yann A. LeCun, Léon Bottou, Genevieve B. OIT, and In Neural networks: Tricks of the Trade. Springer, 2012.
Müller. Efficient BackProp.
[27] Jachoon Lee, Samuel S. Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: an empirical study. In Advances in neural information processing systems (NeurIPS), 2020.
[28] Mingchen Li, Mahdi Soltanolkotabi, and Samet Oymak. Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
[29] Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in neural information processing systems (Neur[PS), 2018.
[30] Chaoyue Liu, Libin Zhu, and Mikhail Belkin. On the linearity of large non-linear models: when and why the tangent kernel is constant. In Advances in neural information processing systems (NeurlPS), 2020.
[31] Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over- parameterized non-linear systems and neural networks. In Advances in neural information processing systems (NeurIPS), 2020.
[32] Yiping Lu, Chao Ma. Yulong Lu, Jianfeng Lu, and Lexing Ying. A mean field analysis of deep resnet and beyond: Towards provably optimization via overparameterization from depth. In International Conference Machine Learning (ICML), 2020.
[33] Song Mei, Theodor Misiakiewiez, and Andrea Montanari. Mcan-field theory of two-layers neural networks: dimension-free free bounds and kernel limit. In Conference on Learning Theory, 2019.
[34] Quynh Nguyen and Marco Mondelli. Global convergence of deep networks with one wide layer followed by pyramidal topology. Advances in neural information processing systems (NeurIPS), 2020.
[35] J. Nocedal and S. Wright. Numerical Optimization. Springer New York, 2006.
[36] Frank W. Olver, Daniel W. Lozier, Ronald F. Boisvert, and Charles W. Clark. NIST Handbook of Mathematical Functions Paperback and CD-ROM. Cambridge University Press, 2010
[37] Samet Oymak and Mahdi Soltanolkotabi. Overparameterrized nonlinear learning: Gradient descent takes the shortest path? In International Conference on Machine Learning (ICML),
2019.
[38] Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterization. global convergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 1:84-105, 2020.
[39] Zhao Song and Xin Yang. Quadratic suffices for over-parametriizatoo via matrix Chernoff bound, arXiv preprint /90.::9900033333 2019.
[40] Lili Su and Pengkun Yang. On learning over parrmmeteterie neural networks: A functional approximation perspective. In Advances in neural information processing systems (NeurIPS), 2019.
[41] Bing Xu, Naiyan Wang, Tianqi Chen, and Mu Li. Empirical evaluation of rectified activations in convolutional network. arXiv preprint arXiv: 00855000 2020.
[42] Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for under- standing neural networks. In Advances in neural information processing systems (NeurIPS), 2019.
[43] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations (ICLR), 2017.
12

---

[44] Difan Zou and Quanquan Gu. An improved analysis of training over parameterized deep neural networks. Advances in neural information processing systems (NeurIPS), 2019.
[45] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterizeed deep ReLU networks. arXiv preprini 1rXiv:1811.088888 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See Section 5.3 and Section 6.
(b) Did you describe the limitations of your work? [Yes] See Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section 7.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assump- tions and 2.
(b) Did you include complete proofs of all theoretical results? [Yes] See the supplementary document.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or as URL)? [Yes] See https://githu/. com/
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they chosen)? [Yes] See Appendix G.
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] See Section 6.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix G.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "wgpchCzIxRe", "reviewer": "Reviewer_1Kgg", "summary": "This work presents an analysis of the amount of hidden units needed for convergence of a 1 hidden layer neural network to a global minimum under gradient descent (and gradient flow).  In particular, this work establishes a bound of $\\tilde{\\Omega}(n^{\\frac{3}{2}})$ parameters for linear convergence.  Importantly, this work analyzes convergence in a 1 hidden layer network in the case where both weight matrices are trained.  The results also hold for a range of initialization schemes including the Kaiming Normal Initialization.  \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n\nPositives: \n(1) I found the work to be a novel usage of existing techniques for proving convergence in the non-convex setting via the PL inequality.  I found the analysis and the proof idea clear and easy to follow. \n\n(2) The results are novel to the best of my knowledge and the authors provide a nice comparison of how the derived scaling differs with several related works.  \n\n(3) Overall, I thought the results were clearly presented.  I especially liked that the authors included upfront a description of the proof technique that would be used throughout the work.  The theoretical results all appear to be correct to the best of my knowledge (I was able to check through Appendix C + G but unfortunately, could only skim through Appendices D-F due to time constraints).  \n\n###############################################################\n\nLimitations: \n(1) The proof technique is very reminiscent of local convergence results under the PL inequality and smoothness and it might be useful to cite the following related work: https://arxiv.org/abs/2003.00307 , https://arxiv.org/abs/2010.01092.  \n\n(2) I think the presentation can be improved slightly by introducing the motivation for analyzing gradient flow first.  Correct me if I’m mistaken, but the proof for the gradient flow case seems to mainly exist to provide intuition for the argument controlling the length of the optimization path in the gradient descent case.  It may be helpful to add text to mention something like this to motivate the gradient flow case a bit more.  \n\n(3) This comment is not as related to the main results of the paper, but more to the discussion on the lazy training regime.  I think the authors emphasize quite a bit that the lazy training regime leads to poor generalization, but this is not generally true.  In fact, the infinite width NTK can generalize well in many cases (see https://arxiv.org/abs/1910.01663, https://arxiv.org/abs/2007.15801).  I think the authors may be trying to say that the finite width linearization of a neural network seems to underperform training the same finite width network when all parameters are updated.  I feel this can be clarified a bit throughout the paper (in the introduction & Section 6).  \n\n###############################################################\n\nMinor Comments:\n\n(1) I think the function $\\psi$ should be real valued for the PL inequality correct? Right now it appears to map to $\\mathbb{R}^{d_2}$.  I also think over-parameterization is an implicit assumption for this statement of the PL inequality - this is stated later, but may be useful to say this right before the PL inequality definition.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss some limitations and societal impact appropriately in the conclusion.  \n", "review_text": "", "extra_scores": {"ethical_concerns": "None at the moment.  ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "o3pMHomV2NF", "reviewer": "Reviewer_N3qa", "summary": "In this paper, the author focus on the theoretical framework of minimizing training risk when the loss satisfy PL conditions. They prove the linear convergence in subquadratically over-parameterized shallow networks with smooth activation functions. They conduct experiments on different initialization to support the theory. The theory also provides insights toward avoiding lazy training.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and smooth to follow. The work looks original to me but I have a few concerns.\n1. On experiment perspective, to what extent the theory can even deeper network and relu activation?\n2. The experiments are not support the theorem well, no experiments provide to show how width (or overparameterization) relates to convergence and training dynamic. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, applying to ReLU is a pretty realistic direction.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "iMLQdj3hIRF", "reviewer": "Reviewer_HcjS", "summary": "The paper shows that overparameterized neural networks with $O(n^{3/2})$ neurons, where $n$ is the number of datapoints, are globally convergent at a linear rate with high probability provided that the weights are initialized from Gaussian distributions with the right variances and the activation function is twice-differentiable. The work is the first one to give a result in the regime where the number of neurons is subquadratic in $n$, and unlike previous papers, it considers the case in which both layers are trained.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The argument proposed seems novel and the results obtained are a significative improvement over what was known. The explanation is mostly clear: in particular, Section 3 is useful to get an idea of the proof in the simplified case of gradient flows.\n\nClarification to be made: In Assumption 2, Line 231, an assumption is made on $sigma_{\\max}(V_k)$. Aren’t the matrices $V_k$ the parameters of the optimization problem, i.e. not fixed? How come an assumption is made on them?\n\nSuggestions: When applying Theorem 2 to the case of shallow neural networks, it is mentioned that random matrix theory techniques are applied. Apparently, these techniques are applied in  the proof of Theorem 3, but there is little explanation in the main text about them. It would be good to provide an intuition on them, if space permits. Moreover, the reference to the Khatri-Rao product is hard to parse, given that the concept is not introduced in advance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the limitations. There is no potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "4a02H3mmTf8", "reviewer": "Reviewer_i9DR", "summary": "The focus of this paper is to improve the state-of-the-art overparameterization condition for training shallow neural networks. Besides, this paper also claims that the proposed analytical framework can be applied to the setting that uses standard initialization strategies, which possibly avoids lazy training.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Basically, the main weakness of this paper is regarding the contribution. First, the utilization of smoothness, near-isometry, and PL conditions is not new in the analysis of training overparameterized neural networks. The convergence analysis in [1, 12, 27, 41] has also explicitly or implicitly made use of these properties. Besides, the $O(n^{1/2})$ improvements are not significant and remarkable as this cannot provide us a better understanding of the true learning behavior of GD/SGD for neural network models.\n\nRegarding Table 1, the authors should also clearly state the data assumption made in [34] and this paper in the table. I think the $O(n^2)$ result in [34] is built under the assumption that the training data is Gaussian-like. Besides, [12, 40] are actually considering ReLU activation function while this paper considers smooth activation, which should also be clarified clearly in the table.\n\nThe results in Theorem 3 seem to be similar to [34], the authors may need to comment on the difference right after the theorem.\n\nIn Section 6, the authors briefly discuss the relationship between initialization to lazy training. However, there might be an issue since the lazy training happens as long as $w_1\\cdot w_2$ is large, e.g., $w_1\\cdot w_2 = O(1/\\sqrt{d_0 d_1})$, instead of the scaling of solely $w_1$ or $w_2$. Different ratio $w_2/w_1$ only determines the learning speed of the first and second layers but does not affect the fact that GD is still practicing lazy training, since $||\\Theta_t - \\Theta_0||\\rightarrow 0$. Therefore, unless considering the regime that $w_1\\cdot w_2$ is smaller (e.g, $w_1\\cdot w_2<1/d_1$), the convergence of GD will still be in the lazy training regime.\n\n===================\n\nThank you for providing such a thorough response to my questions. I agree that O(n^{1/2}) improvement is nontrivial and the study of the initialization scaling is also interesting. \n\nI mentioned [1,  27, 41] since I feel that the gradient lower bound results in their paper are similar to the PL condition. So it would be better to comment on this after the definition of PL condition or introduction in your paper.\n\nIt would be great if the authors can clarify the difference to [34] since this is the most related work. The results in [34] also have some dependency on the input dimension, it could be better to also comment on the over-parameterization condition proved in [34] when the input dimension is $\\Omega(\\sqrt{n})$.\n\nThe results on the norm between $h(\\Theta_i)$ and $\\tilde h(\\tilde \\Theta_i)$ is also interesting. It would also be better to include that lemma in the main part of this paper.\n\nOverall I would like to increase my evaluation to marginally acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper has no negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hrs"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proves $O(n^{3/2})$ overparameterization condition for training two-layer neural networks when the activation function is smooth and the loss function is square loss. The majority of the reviewers are in support of accepting this paper. Thus, I recommend acceptance. In the camera-ready, the authors should make it clear that the comparison in Table 1 is under different assumptions on the activation functions (e.g., smooth activation functions vs. ReLU). 
Decision: Accept (Poster)