Linear Convergence of SGD on Overparametrized Shallow Neural Networks
Authors: Paul Rolland
Ali Ramezani-Kebrya
ChaeHwan Song
Fabian Latorre
Volkan Cevher
Venue: ICLR 2022 Submitted (2022)

Abstract: Despite the non-convex landscape, first-order methods can be shown to reach global minima when training overparameterized neural networks, where the number of parameters far exceed the number of training data. In this work, we prove linear convergence of stochastic gradient descent when training a two-layer neural network with smooth activations. While the existing theory either requires a high degree of overparameterization or non-standard initialization and training strategies, e.g., training only a single layer, we show that a subquadratic scaling on the width is sufficient under standard initialization and training both layers simultaneously if the minibatch size is sufficiently large and it also grows with the number of training examples. Via the batch size, our results interpolate between the state-of-the-art subquadratic results for gradient descent and the quadratic results in the worst case.

Under review as a conference paper at ICLR 2022
LINEAR CONVERGENCE OF SGD ON OVERPARAMETRIZED SHALLOW NEURAL NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
Despite the non-convex landscape, first-order methods can be shown to reach global minima when training overparameterized neural networks, where the number of parameters far exceed the number of training data. In this work, we prove linear convergence of stochastic gradient descent when training two-layer neural network with smooth activations. While the existing theory either requires high degree of overparamettriiztton or non-standard initialization and training strategies, e.g., training only single layer, we show that subquadratic scaling the width is sufficient under standard initialization and training both layers simultaneously if the minibatch size is sufficiently large and also grows with the number of training examples. Via the batch size, our results interpolate between the state-of-the subquadratic results for gradient descent and the quadratic results in the worst case.
INTRODUCTION
Our understanding of the optimization landscape of supervised learning with neural networks has vastly improved in recent years. This is in part due to the observation that overparameterization is key to overcome the pitfalls of first-order methods in general non-convex problems (Soltanolkotabi et al., 2019). Under this assumption, line of research has established convergence of first-order methods such as gradient descent (GD) to global optimality. (Allen-Zhh et al., 2019; Kawaguchi & Huang, 2019; Du et al., 2019; Du & Lee, 2018; Zou & Gu, 2019; Brutzkus & Globerson, 2017: Song YYng, 2019; Oymak Soltanolkotabi, 2020), a phenomenon that has been confirmed practice.
Empirically, as long as the width of network scales linearly with the size of the training data (mild overparameterizationn, stochastic gradient descent (SGD) enjoys fast convergence to global optimality (Livni et al., 2014; Safran & Shamir, 2018; Oymak & Soltanolkotabi, 2020; Kawaguchi & Huang, 2019). Can we explain such behavior theoretically? Sadly, the available characterizations require larger degree of overparameterrizaion,, or imposes additional assumptions, which do not hold for the algorithms that are used in practice. For example, if GD is applied exclusively to the last layer, Kawaguchi & Huang (2019) show that an ideal linear scaling of the width is sufficient to guarantee convergence. Song& & Yang (2019) prove quadratic scaling when GD is applied only to the first layer.
For two-layer neural networks, when both layers trained with GD simultaneously, state-of-the-art results show that subquadratic (not linear) scaling is enough to converge to global optimality (Anony- mous). Despite being close to the ideal linear rate of overparameterizzatio,, due computational constraints, GD is rarely used in modern applications involving huge datasets. Hence, closing the gap between theory and practice requires studying scalable first-order algorithms such as SGD. Our work focuses on bini-bbtch SGD, which is one of the most common algorithms for training deep models. We study convergence of SGD when it is applied to train both layers of neural network, which initialized with standard initialization schemes.
Our contributions:
We show that under proper initialization and choice of learning rate, the iterates of SGD converge to global minimum with high probability and exponentially fast for a general non-convex problem assuming that the loss function satisfies a growth condition.
For the special case a two-layer neural network, we show that a subquadratic scaling on the width is sufficient under standard initialization and training both layers simultaneously, if the

---

Under review as a conference paper at ICLR 2022
Reference
Algorithm
Activation
Setting
Scaling
Oymak & Soltanolkotabi (2020)
SGD on layer 1
ReLU
QL
92(n²)
Song & Yang (2019)
GD on layer I
ReLU
SD
(((2²)
Kawaguchi & Huang (2019)
GD layer 2
ReLU
CLL
(2(n)
Du et al. (2019)
GD
ReLU
SD+QL
((n))
Zou & Gu (2019)
GD
ReLU
SD+QL
12(1²)
Anonymous
GD
smooth
QL
((n or (?n2))
Allen et al. (2019)
SGD
ReLU
SD+QL
l(n
This paper
SGD
smooth
QL
f(nn)) (n22)
Table 1: Required degree of Overparameterization for training shallow networks with global convergence guarantees. QL=quadratic loss, CLL=convex and Lipschitz loss, SD=separable data. The notation f ignores logarithmic factors.
minibatch size is sufficiently large and it also grows with the number of training examples. For constant batch size, we show that quadratic overparametrization is sufficient. Our results interpolate between subquadratic and quadratic scalings depending on the batch size.
Related work. The majority of the existing literature overparamettrrizaion focuses GD (Du et al., 2019; Du & Lee, 2018; Allen-Zhu et al., 2019; Zou & Gu, 2019). Allen-Zhu et al. (2019) provided theoretical bounds for deep networks trained with SGD. However, their results require an overparameterization degree that is too large, compared to what can be achieved for GD. In contrast, we study SGD and how the batch size affects the required degree of overparameterization. Chen et al. (2021) establish generalization guarantees and sufficient network width when SGD trains deep ReLU networks for binary classification, which a different setting compared our paper.
We study the case where SGD updates all the parameters of a shallow neural network. In contrast, a number of existing literature assume that only the parameters corresponding to some layers are updated throughout training (Oymak & Soltanolkotabi, 2020; Kawaguchi & Huang, 2019; Song & Yang, 2019). When SGD is applied only to the first layer, Oymak Soltanolkotabi (2020) showed that quadratic scaling is sufficient for convergence with linear rate. Despite being an interesting theoretical setup, such algorithmic choice rarely happens in practice.
There also differences regarding the choice of activation function. While ReLU can be considered as the default activation function when studying deep neural networks, its non-smoothness may be the reason why results for ReLU networks require substantially more number of parameters additional assumptions on the data (like separability) to guarantee convergence to global minimum. Moreover, backpropagation on ReLU networks does not correctly calculate the gradient all points of differentiability (Kakade & Lee, 2018; Bolte & Pauwels, 2021), which raises major technical issues. In contrast, we assume smooth activation, similar Anonymous, which avoids such issues and achieves lower overparameterization degrees.
The authors of (Anonymous) established subquadratic scaling when GD trains a shallow neural network. In this paper, we focus on SGD, which results in substantial technical challenges. Compared the results in (Anonymous), controlling the length of the trajectory is more involved this paper, which requires new analysis technique that bounds the length of the trajectory with high probability. We consider the effect of mini-batch SGD, which shows an interpolation between subquadratic and quadratic scaling. We also improve the estimates at initialization and show that more relaxed assumptions are sufficient to establish sufficient overparameterization degree.
We summarize such recent results in the overparametrizaatoo literature in Table 1.
Lazy Training, Proving fast convergence to global optimality not a complete answer. has been shown that despite fast convergence, it is possible that an algorithm tends towards solution with poor performance on test data, if the training falls in the so-called Lazy Training regime (Chizat et al., 2019). Thus, any useful algorithmic framework for learning neural networks should avoid this regime, usually through careful initialization schemes. For example, despite requiring only linear overparametrization for GD, the initialization studied by Nguyen & Mondelli (2020) leads to
2

---

Under review as a conference paper at ICLR 2022
the lazy regime. This is the reason why omit such result from Table 1. In this work, show global convergence and achieve subquadratic scaling under standard initialization schemes, which empirically perform well on test data.
Polylogarithmic width enough to obtain convergence for neural networks of arbitrary depth, according Ji & Telgarsky (2020); Chen et al. (2021). However, in those work, convergence is understood an ergodic sense. This is a weaker notion than strict convergence with high probability, which is the one we consider, and which better matches practical applications.
Given perfect knowledge about the underlying function that generates the labels and under the assumption that such target function has low-rank approximation, Su & Yang (2019) showed that GD achieves veco-approximation. This is different from the problem considered in our paper.
For binary classification problem, Daniely (2020) showed that near linear network size is sufficient for SGD to memorize random examples under variant of Xavier initialization, which is a different setting compared our paper. For deep neural network with pyramidal structure and smooth activations, Nguyen & Mondelli (2020) showed that subquadratic scaling is sufficient for global convergence of GD under a restrictive initialization scheme. In this paper, we establish global convergence for SGD under standard initialization.
recent line of work uses mean-field analysis to approximate the target distribution of the weights in neural network via their empirical distribution (Mei et al., 2019; Lu et al., 2020). Nevertheless, such results do not provide useful overparametrization degree bounds in terms of the number of samples. In contrast, our work does not require such approximations and we focus on deriving explicit sufficient overparametrization rates for global optimality of SGD.
Notation. We use to denote the Euclidean norm of a vector and Frobenius norm of a matrix. We use V to represent the Jacobian of vector-valued and gradient of a scalar-valued function. We use C and @ to represent the entry-wise Hadamard product and Kronecker product, respectively. We use lower-case bold font to denote vectors. We use calligraphic and standard fonts to represent sets and scalars, respectively. We use miin(T) and maxe (T) to denote the smallest and largest singular values of linear map T'. We use [r]] to represent {1, ... .n for an integer n. We use Ô and Si to hide logarithmic factors and use S to ignore terms up to constant and logarithmic factors.
A GENERAL GLOBAL CONVERGENCE RESULT FOR SGD
In this section, we consider general non-convex minimization problem and show that for a certain choice of learning rate and careful initialization, the iterates of SGD converge to global minimum with high probability and exponentially fast. In Section 3, we extend our consideration to the training of shallow neural network and find the hidden layer size, which is sufficient for SGD to converge to a global minimum Le., its overparameterizzaton degree.
Definition 1 (Smoothness). Let By 0.
A function và Rd - Rd2 is By-smooth, for all
u, v E gdi, have
maxx (v)(u) Vib(v)) S Bp vl|-
Definition 2 (PL condition (Bolte et al., 2017)). A function v Rd - IR satisfies the PL condition there exists ag such that, for all u E Rdh we have
Vv(u)]2
* u) <
200
We now ready state finite-sum compositional optimization problem:
min h(w) f(((w))==-)))) 1 m weRd
m7 Σ (((((w))
f.f, Rd
R. (3)
where m denotes the number of training examples.
Assumption 1. The functions introduced in Eq. (3) satisfy the following properties: (i) tb is twice- differentiable and B smooth (Definition 1). (it) f is difce-iiffrenttablee and Smooth and (ii) f
satisfies the PL condition with some og > (Definition 2).
3

---

Under review as a conference paper at ICLR 2022
We study the iterates of the stochastic gradient descent (SGD) algorithm when applied to the objective function h in Eq. (3). For 2 0, let I' denote a random minibatch at iteration i drawn uniformly at random, independent of all previous draws. Let b E [m] denote the minibatch size, i.e., [I' b for all i. The SGD iterates are defined by a random variable w referred to as the initialization, and the update rule:
w = w 1, Σ Vhy(w"),
JEI
where À > O is the learning rate and hy(w)= = : [j(((w)) Vj, w.
An important feature of the SGD iterates is that EJEr (hz(O(w")) in Eq. (4) is an unbiased estimator of the gradient Vh( w*) given w', ie., B 1 Ejez: ( w Vh(w"). Never- theless, this is not enough for SGD to converge to the first-order optimality. In addition, we will assume that f in Eq. (3) satisfies the growth condition (Schmidt & Roux, 2013; Vaswani et al., 2019; Cevher & Vu, 2019):
Definition 3 (Growth condition). A function vb Rd IR with a finite-sum sum structure satisfies the growth condition with minibatch size b if there exists Thp O such that, for all u E RR,, we have
I JEZ
IE
S T V
(5)
where the expectation over the random choice of set I. Assumption 2. In Eq. (3), f satisfies the growth condition (Definition 3) for some TT 0.
We are now ready to state the main result of this section.
Theorem 1. Let Assumptions and hold and let Ç >> 1. Suppose that initialization,
0 < H S Tmiu (ini (V4 (w")) S Tmax V "T''(w")) I vi, h(w²) = =0 (335n122
(
a
(6)
Then, for a sufficiently small learning rate
A S min
15 V/ BR1 B)povi)
(B
Bio
the iterates of SGD {w") (w')izo (4) converge a global minimizer of h (3) with the optimal value of zero, exponentially fast and with probability at least - 1/C. The rate of convergence is given by
Elh(w") s (1 - C)arf1))) t((w")
for universal constant C.
Remark 1. The second item in Eq. (6) suggests initializing close to a global minimum of the non- convex optimization problem. This feature has precedence in the related literature, e.g., in matrix factorization (Chi et al., 2019).
The proof of Theorem is deferred Appendix B. However, in the remaining of this section provide sketch of the main arguments that lead to the result. The first condition in Eq. (6) is central to our arguments, and we will refer to it as the near-isoment isometry property.
Definition 4 (Near-isometry). A linear map T Rd1 RRda is (m, meerrrisssoy if there exist < μ such that
S m (T) S 0 max (T) SV.
(8)
Let denote the limit point when the SGD algorithm is with some learning rate and let VΦ" denote the adjoint operator of V (w). Convergence of SGD is ensured with high probability due to the strong growth condition (Definition along with proper learning rate and initialization. We note that w is first-order stationary point of h. Hence we have:
Vh(w
-Φ (w)(())VW (FF())))))
4

---

Under review as a conference paper at ICLR 2022
Note that if V is nonsingular, it would follow that V)) 0. The PL condition (Definition 2) would then imply that (W)) is global minimizer of f and hence, a global minimizer of h. With this fact in mind, our proof can be summarized in three steps: first, careful choice of initialization will ensure that V is nonsingular for all elements within a certain distance of w Second, we show that under small enough learning rate, the iterates of SGD remain close to the initialization w with high probability regardless of the number of iterations.
The third and final step will use the non-singularity of V4* at convergence and Eq. (9) conclude global optimality.
This is akin to the arguments in (Anonymous), however, in our the stochasticity in the SGD updates poses a challenge for controlling the distance to initialization. We use concentration bounds on the length of the path and show that the SGD trajectory remains in the region where V is non-singular, with high probability.
crucial result for the first step of our proof has already been established in by (Anonymous). shows that smooth function that is near-isometry at initialization will preserve such property for all points within a certain distance.
Lemma 1 (Anonymous). Let &b be B4-smooth and V (wo) be (HDp (aoee.vo)-eeee -earr-sometrr Then
for all w such that [|w-- wwol S
114
Ns
S Fmin (4b (V)"(w) S mmax V4" (w) S
3// (10)
2
2
2
The second step in the proof of Theorem is to compute the expected length of the SGD trajectory which is spent inside the ball defined in Eq. (10). We find upper bound on this expected length depending on the initialization and learning rate, but independent of the number of iterations. Hence, under some proper initialization and learning rate, we can control the expected length of the trajectory for which Lemma 1 holds. In particular, we have
Proposition 1 (Expected length of trajectory). Let Assumptions and hold and let Ç > Let the random variable I denote the first iteration of SGD (Eq. (4)) such that
w' B ball(w", ppb) == [w ||w w S p4}
(11)
or I- co the trajectory does not leave B. Suppose that w satisfies Eq. (6) and SGD is executed with sufficiently small learning rate, which satisfies Eq. (7). An upper bound on the expected length of the SGD trajectory is given by
E[((T))
S
Ps 2(Bx C
(12)
We provide the sketch of the proof (see Appendix A for the complete proof). We first find an upper bound on the expected length of the trajectory terms of the norm of gradients of f. With proper learning rate, we find an upper bound on the norm of the gradient in terms of the expected decent of f in two consecutive iterates, which are inside the ball. We also ensure that the learning rate is sufficiently small such that Billw' ''' []] is bounded. Finally, under proper initialization, obtain an upper bound on the expected length of the trajectory for the iterates inside the ball, i.e.
E ||w - w--
Remark 2. similar phenomenon that shows bounded length of the trajectory has been observed in various settings mainly for gradient descent (Du et al., 2019; Oymak & Soltanolkotabi, 2019; Anonymous). In this paper, we focus on a compositional non-convex problem trained with SGD, which is more challenging analyze.
Using the upper bound (12) on the expected length of the trajectory spent inside B = ball(w", .P.). we can bound the probability that the SGD iterates leaves the ball B. Indeed, in order for the process to leave B starting from w it is required that the length of the trajectory spent inside B satisfies ((I) 2 Pg. Hence, using bound (12) on E[{(T)] together with a concentration bound (Markov inequality in our case), we can upper bound the probability of SGD iterates leaving B. Finally, under the event that the SGD iterates remain in B, an upper bound on (E(((T) implies the convergence of the iterates.
Remark 3. With a more involved analysis on the concentration properties of the random variable ((T), it may be possible greatly improve the dependence of the initialization and step size on Ç.
5

---

Under review as a conference paper at ICLR 2022
Indeed, the current analysis assumes the worst-case scenario, where the SGD iterates either remain at the initialization, or directly leave the ball B in a straight line (this scenario indeed maximizes the probability that the process leaves the ball, given bound on ([{(I))).
Although E(1) is obtained as a sum of random variables, the difficulty of obtaining better concentration bounds for E(T) comes from the high level of dependence between all the variables involved. A better analysis would thus need to better understand how the trajectories behave inside the ball B, e.g., by bounding the variance of E(I).
In the following section, we specify our result to the special case of shallow neural networks. We will show that, the case of quadratic loss, the strong growth condition naturally holds, with a constant depending the batch size. Moreover, using Gaussian initialization for the neural network parameters, we can control the initial smoothness and near-isometry parameters involved in Theorem with high probability.
GLOBAL OPTIMALITY OF NEURAL NETWORKS TRAINED WITH SGD
Setup. We will consider the problem of training a shallow neural network with one hidden layer, input dimension do. hidden nodes, output dimension d2, and quadratic loss. We denote the data and label matrices as X E 2ed and Y E Rd xm respectively.
Let W E IRd xde and V E Rdaxd, denote the parameters of the first and second layers of the network, respectively. We collect both parameters in a variable θ (W, V) E Rd xdo Rd2xd1 In order to fit the supervised training of the network to the template studied in Section 2 (Eq. (3)) we define:
(+)) = & (WX)& E RR
f, = 11 Y, 11 E I
(13)
where Zj denotes the j-th column of matrix Z and & IR R is the activation function, which is applied entry-wise. We can now write the problem as the finite-sum:
1 - Σ (V((X,) - Y/11 m
min 9
-00)=
=
-
(14)
We will make assumption the Hermite norm (Definition 5) of the activation function. Our assumptions on the activation function are summarized as Assumption 3 below.
Definition (Hermite norm (Olver et al., 2010)). Let Φ R + The Hermite norm of given by | = Vii of where 63 denotes the i-th Hermite coefficients of th given by:
C, = (é. qin
V2n (x))
1
(-² dr
x²a
and 0; : :R + R is the i-th Hermite polynomial (probabilist's convention) for 2
Assumption 3. & is twice-differenticble, ((0) = 0, supa [d(a)) = &mmax < co. sup, [o(a)l =
Ømxx <00, and | < x00.
The popular ReLU does not satisfy the twice-differentiablity assumption. However, smooth ap- proximations of ReLU such the Gaussian error Linear Units (GeLU) and softplus (Hendrycks & Gimpel, 2020; Nguyen & Mondelli, 2020) have been shown to outperform ReLU in several settings and are commonly used in practice (Clevert al., 2016; Gulrajani al., 2017; Kumar al., 2017; Kim et al., 2018; Xu et al., 2020). In addition, smoothened functions by a Gaussian kernel uniformly approximate the ReLU function (Nguyen Mondelli, 2020).
Assumption 4. For all j [m], ||X||| < 1. ||Y||| 1
Remark 4. The assumption on the data is mild and common in the overparameterization literature (Li & Liang, 2018; Ji & Telgarsky, 2020). It can be enforced by data normalization.
Initialization. The initial iterate of SGD will be chosen in the following way:
W ~N (1. % ) vo ~~ (0 dj
6a = -W0 VO)
(15)

---

Under review as a conference paper at ICLR 2022
Remark 5. The initialization in Eq. (15) matches popular initialization schemes such as LeCun (LeCun et al., 2012) and He (He et al., 2015) initializations.
We now proceed to estimate with high probability the value of 1(e"), near-isometry constants (nib, vb) of V' ((0)) and smoothness parameter So. which are required in Theorem 1.
Lemma 2 (Estimation of h(0"), uag v Bo (Anonymous)). Let Assumptions 3 and 4 hold, and suppose that @" follows the initialization distribution in Eq. (15). Let be a positive integer such that m dg and X R24h xm be the matrix whose a-th column defined as vec( 8 ..... @ xa) R6., For some constants 81, 82, dgr k1, and lig independent of do, d1 and m, with probability at least 1 v it holds that:
h3 max max (X)
1(69)
m
max leul (1 + 62)dim, wi / (1+ + c2 (20)d10 m
(16)
V (1 - 51) 2 (10min(X*)
t!
The precise expression for y is provided in Appendix E, is the i-th Hermite coefficients of Φ (Definition 5) and cx. = Ei=z L/il.
Moreover, the map & restricted to the set {(V, W) mmxx(() S Xmax is smooth with constant
BB 20 (X) (émaxx + Φmaxx Xmna
(17)
Although the mapping & is not globally smooth, Lemma 2 shows that it is smooth in region where the largest singular value of V remains bounded. In the following lemma, we show that we can indeed bound the smoothness constant of & restricted to neighbourhood of o required in Theorem 1.
Lemma 3. Let Assumption 3 hold. Let V w be arbitrary matrices and μaf be in (16). Let
Bo == 20 (X) (émax + mmax (V") +
Ømaxxf10
20 20max
Ps =
2
11.
(18)
The function & is 34 Smooth over the set:
Bo (V", Wo) = {(V,W) VIVV
II - W012 S pv -01 -IVV-
(19)
Proof. Let
Xmax = Tmax
(inxx(V) (V9)
[(V, W): Faxx (V) S Xmax (20)
2 20 max X
0max
Xmaax
Lemma then implies that & restricted to B Xmxx is 3a-smooth, following Eq. (17). With this choice of Xmax we show that Bpg (Vo, Wo) C Bxmax which implies the result. Note that 84 2 22 (X Prmax hence
Xmax 2 (max((V)) + μs = Fmax (V0) + pg.
23g
Suppose that (V, W) E B (V", W.). By Eq. (19) this implies IIV 1 S pa. Then,
mmax (V) < mmax ( V2) + Fmax (Vo (V0)
W || 101 + Jmax (Vo)
< pa + Tmax (V.)
5 Xmax.
7

---

Under review as a conference paper at ICLR 2022
In our case, f is the quadratic loss, the growth condition (Definition 3) is satisfied with π) b This is precisely the quantity that will reveal the impact of the minibatch size on the global convergence of SGD. Moreover, the quadratic loss satisfies the PL condition (Definition 2) and is smooth. All things considered, Assumptions and 2 hold for our shallow neural network training setting, ensuring that Theorem is valid.
We are now ready to integrate Lemma 2 and Lemma 3 together with the convergence guarantees in Theorem 1 to arrive the sufficient degree of overparametterizaton required for the convergence of SGD. The following theorem finally concludes that for the shallow neural network described in Section 3, for sufficient degree of overparameterization SGD converges a global minimum with high probability.
Theorem (Shallow network with SGD). Suppose that Assumptions 3 and 4 hold, and that that (W", Vo) is randomly initialized as in (15), Suppose that the hidden layer width dj satisfies
o (X) )m
d1 = (C taiti20 ()
(21)
03 min (X*)Vb)
where C. is of constants, & is term independent do, The SGD iterates converge a global minimum exponentially fast with probability at least - (0 E, do, d1, d2, X, (). See Appendix C for the exact expressions of & and u and the proof.
Finally, we provide order analysis to understand how the sufficient overall overparameteerization degree directly depends on the minibatch size. Intuitively, the sufficient overparamcterizzaton degree improves (is lower) the minibatch size increases.
3.1 IMPACT THE MINIBATCH SIZE ON THE OVERPARAMETTERIZATIOO DEGREF
For = 1, the analysis requires m = do. which is not common setting in practice. For 1 2 2, we suppose that m = dz. which is the case in practice. We estimate that m (X) = /m/do and mmin (X*))= /m/dj = 1, along the lines of (Oymak & Soltanolkotabi, 2020, Section 2.1). Substituting max (X) and miin (x)") into (21), we have
m 2
d1 Z
(22)
Vbdo
Therefore, the overall overparameterization degree becomes dod1 ~ 2-mmmmmmmm))))- /VD), which is sufficient for SGD find global minimum at linear rate except with an arbitrary small probability, This fact will let us understand more clearly the effect minibatch size on the overparameterizztion degree.
If b = (mm) similar to gradient descent, a subquadratic scaling on the network width, dod = 2(m ), is sufficient. In that case, an optimal linear scaling d, = Ó(m) is sufficient when the number of input features is sufficiently large do ~ ((ym).
On the other hand, when the batch size is small b Ö(1), we recover the standard quadratic scaling on the network width. Our analysis provides an interpolation between dgd, ~ 52(m²) and dodj ~ ?mm²)) depending on b. As long as the batch size b (((m)) for some 0, we achieve subquadratic scaling.
4 CONCLUSIONS AND FUTURE WORK
In this work, we prove linear convergence of stochastic gradient descent for training over- parameterized two-layer neural networks with smooth activation functions, using classical initial- ization strategies, and where both layers are trained simultancously. We provide lower bound on the required over averpparamtterization degree for our result to hold, depending on the batch size b used show that using number of parameters
to compute the stochastic gradients. More precisely, dudj Q(m² /vb) is sufficient to obtain linear convergence with high probability, providing sub- quadratic over-parameterization degree as long as the batch size increases with the number of data points.
8

---

Under review as a conference paper at ICLR 2022
In future work, would like to relax the smoothness condition the activation function, in order to encapsulate non-smooth activation functions such as ReLU. In addition, we would like to improve the high probability bound by analyzing more deeply the concentration properties of the random variable (()), characterizing the length of the trajectory spent in a neighborhood of the initialization. Finally, important step would be analyze the generalization properties of SGD through the lens of the proposed approach, in particular by analyzing in which case it leads to lazy training.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning (ICML), 2019.
Anonymous. Anonymous. Anonymous.
Jérôme Bolte and Edouard Pauwels. Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning. Mathematical Programming, 188(1):19-51, 2021.
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-507, 2017.
Alon Brutzkus and Amir Gloherson. Globally optimal gradient descent for a ConvNet with Gaussian inputs. In International Conference on Machine Learning (ICML), 2017.
Volkan Cevher and Bäng Công Vu. On the linear convergence of the stochastic gradient method with constant step-size. Optimization Letters, 13:1177-1187, 2019.
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much over-parameteriizaion is sufficient learn deep ReLU networks? In International Conference on Learning Representations (ICLR), 2021.
Yuejie Chi, Yue M Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Transactions on Signal Processing (TSP), 07: -269,, 2019.
Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In Advances in neural information processing systems (NeurIPS), 2019.
Djork-Aréé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learn- ing by exponential linear units (ELUs). In International Conference on Learning Representations (ICLR), 2016.
Amit Daniely. Neural networks learning and memorization with (almost) no over- peeepparamettiiztionn. In Advances neural information processing systems (NeurIPS), 2020.
Simon Du and Jason Lee. On the power of over-parametriization in neural networks with quadratic activation. In International Conference on Machine Learning (ICML), 2018.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations (ICLR), 2019.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of Wasserstein GANs. In Advances in neural information processing systems (NeurIPS), 2017.
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.
Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (GELU). arXiv preprint 2020.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of American Statistical Association, 58:13-30, 1963.

---

Under review as a conference paper at ICLR 2022
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks. In International Conference on Learning Representations (ICLR), 2020.
Sham Kakade and Jason D Lee. Provably correct automatic subdifferentiation for qualified programs. arXiv preprint 1809.0000.000 00030, 2018.
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.
Youngjin Kim, Minjung Kim, and Gunhee Kim. Memorization precedes generation: Learning unsu- pervised GANs with memory networks. In International Conference on Learning Representations (ICLR), 2018.
Abhishek Kumar, Prasanna Sattigeri, and Tom Fletcher. Semi-supervised learning with GANs: Manifold invariance with improved inference. In Advances in neural information processing systems (NeurIPS), 2017.
Yann A. LeCun, Léon Bottou, Genevieve B. Orr, and Klaus-Robert Müller. Efficient BackProp. In Neural networks: Tricks of the Trade. Springer, 2012.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in neural information processing systems (NeurIPS), 2018.
Roi Livni, Shai Shalev-She Shalev-Shwartz. Shwartz, and Ohad Shamir. On the computational efficiency of training neural networks. In Proceedings of the 27th International Conference on Neural Information Processing Systems- Volume 1, NIPS' 14, pp. 855-863, Cambridge, MA, USA, 2014, MIT Press.
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 on Machine Learning (ICML), 2020.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit. In Conference on Learning Theory, 2019.
Quynh Nguyen and Marco Mondelli. Global convergence of deep networks with wide layer followed by pyramidal topology. In Advances in neural information processing systems (NeurIPS), 2020.
Frank J. Olver, Daniel W. Lozier, Ronald F. Boisvert, and Charles W. Clark. NIST Handbook of Mathematical Functions Paperback and CD-ROM. Cambridge University Press, 2010.
Samet Oymak and Mahdi Soltanolkotabi. Overparameterized nonlinear learning: Gradient descent takes the shortest path? In International Conference on Machine Learning (ICML), 2019.
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterizzatoo:: global con- vergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 1:84-105, 2020.
Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks.
In International Conference on Machine Learning, pp. 4p.4 4443- PMLR, 2018.
Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under a strong growth condition. arXiv preprini 1 2013.
Mahdi Soltanolkotabi, Adel Javanmard, and J. Lee. Theoretical insights into the optimization landscape of over-parameterrzed shallow neural networks. IEEE Transactions on Information 65eory,65:7422 65:742-769, 2019.
Zhao Song and Xin Yang. Quadratic suffices for overepaaraenriizatoon via matrix Chernoff bound. arXiv preprint arXiv: arXiv: http:/9960..33322 2019.
Lili Su and Pengkun Yang. On learning over parameterize neural networks: A functional approxi- mation perspective. In Advances in neural information processing systems (NeurIPS), 2019.
10

---

Under review as a conference paper at ICLR 2022
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over- parameterized models and an accelerated perceptron. In International Conference on Artificial Intelligence and Statisticc (AISTATS), 2019.
Roman Vershynin. Introduction the Non-asymptotic Analysis of Random Matrices. Cambridge University Press, 2012.
Bing Xu, Naiyan Wang, Tianqi Chen, and Mu Li. Empirical evaluation of rectified activations in convolutional network. arXiv preprint arXiv: w5.. 0005000 2020.
Difan Zou and Quanquan Gu. An improved analysis of training over parameterized deep neural networks. In Advances in neural information processing systems (NeurIPS), 2019.
A PROOF OF PROPOSITION 1
According to the definition of I, w' E B i expected length of the trajectory in terms of the norm of gradients f. With a proper learning rate. we find an upper bound on the norm of the gradient in terms of the expected decent of function in two consecutive iterates. We also ensure that the learning rate is sufficiently small such that | w/-1| is bounded. Finally, under proper initialization, the final bound is established.
We first find an upper bound on the
The "length" of the trajectory traced by the SGD iterates {w²) is
((I)
Σ
| w
++ w'l
Σ
(w"))l
=
(A.1)
0=
JET
1-1 Σ
< Av/
5
(z'))
0=
jEz
where z' = ((w") for all i.
The expected length of this segment of the trajectory is therefore bounded as
B(((T)) & A
Σ
(z)(l))
1=0
jeI
(A.2)
< S
Vf(z'))
where the last inequality holds thanks to the growth condition and Jensen's 's inequality. We now develop "descent inequality' and establish lower bound on f(z') (z First, consider two consecutive SGD iterates i, é + such that w', wit1 B. Then, we have
Br 1|
f(2²) - f(x't1) 2 (z' _ Vf(z'))
||//11 212
2
B1
= =(((w)) - 2(w Vf(z'))
|| Dl
2
= (VV((W') { (w² w w(t1), vʃ(2²)) Bi (1 - =(w"))l
- ((0 - ((w') - ve(ww) {wi+l i+1 w'), vf(x)))
Bi $| (( <ww")1
2 (VD((w) (w'- - -w#t1] vf(z'))
2
11

---

Under review as a conference paper at ICLR 2022
B || || - (11
2 (VQ(w') { ( W , vf(z²))
-/1 w'll (1p (0011V((2')
+
9
4
= = 1 E [hls(w)), vf(2²)) / Σ [l)s(")]1
(8a11V((3))
93
+
4
JEZ
jeZ
(A.3)
Hence, taking expectation over the selected batch n' at iteration i, we find that
f(z')
[/w"]
9
2
E
\(V
Σ
Vhy(w (w'()) }} Vf(z'))
2
Σ
(w")l)))
(00l (B01V/(23))
+
Iwm
4
jEZ
JEZ
12 E
Thy (M)(("))/ (1") (801VV/(2211
+ 933,08
\(V4(
Vf(x')
1|
Σ
2
4
JEZ
22 E
(BaII/Ie311
93,11
\/|
11
Σ
vhyy (ly(w))))\ww)
4
JEI
22
ff('')1
(BbIV
93,u3 + 4
2
(1-
un 3 Vf(''))
3 2
>
(chain rule and Lemma 1)
2
8p3
where the final inequality holds if the learning rate is small enough such that
2 (f())) 818
(A.4)
n Bovg max,
We also note that:
(f(z') - E(f(z(t)) w')) Vf(2') + (E W wi]
ff(z') [Eff(z(t) w
X (f 1
Vs(z)) + VEL + w
(A.5)
2V5(z))
(z')
Vf(('')]
V2
Substituting the above back into (A.2), and using the fact that wi E B Vi = O,.... I - 1, an upper bound on [[[{[]) given by:
T-1
E[((T)] < X E
[z('))|
12

---

Under review as a conference paper at ICLR 2022
Vf(2) VB[S(2-1))
+ Au E|V
V EI
ff(z)) v V + +ATTyUB Vf 1|
(Jensen's inequality)
Vailu
VT
EE
Vf(z9) /5(22)
+ + [1Vf(z'
Varul
f(z²)
A [V
(A.6)
Varu3
Suppose that, in addition to the previous bound on the learning rate, we have
Ho
A S 1C Vis Bo max; Vf(z*)|
(A.7)
and that the initialization satisfies
f(z²) = h(w") S aspe
(A.8)
(2 82
for some <> 1. Then, we obtain (12).:
B[((T)) S
Hi 2ÇBp Ç
pt
We note that the local Lipschitz constant of f is given by
max [[ff(() < [V] + max Vf(z') vz(20)||
< |V/[(>>)| By max I - =011
|//(2>>]| + By max [| - ((w")l
= [V + 33,V0
(A.9)
max || - w
2
& (2V || + 33
2
33 F
|| +
484
Substituting (A.9) into (A.4) and (A.7), an upper bound on the learning rate of SGD is given by
μ4
X S min
(n(6nr2|l + 3 - ByHbrz) (VTTIs(& + 3
This completes the proof of Proposition 1.
B PROOF THEOREM 1
Let <> >>> 1. Using Proposition 1, under proper initialization and choice learning rate, the expected length of SGD trajectory is bounded above by:
E[((I)]
H4
2ÇBBpp
Thus, using Markov inequality {(I), we have
1
Pr(((T) 2 px)
$
13

---

Under review as a conference paper at ICLR 2022
Therefore, with probability greater than - we have {(T) pv. meaning that the SGD trajectory never leaves the ball B, i.e. 1 co. Moreover, conditioned on this event, {(2) corresponds the length of the full trajectory. Since we have a bound on E[E(T)), it implies that the trajectory length is finite, i.e, that the SGD iterates converge.
Finally, we show the linear convergence to the optimal limit point:
B / = E[h(w" (1/[(*+))////
//w]] /ww"
h(w") ) + h((w))
B[f(2*+1) ww] f((²)= hiww)
- -CAp Vf(z')]1 + h((w")
(A.10)
C f + hhww')
(1 Cda (
where C denotes constants and z' (w') for all Taking expectation both sides of (A.10) w.r.t. n n² completes the proof of Theorem 1.
C PROOF OF THEOREM 2
For the case of quadratic loss functions, we have By = 2. In the following, we first find the growth condition parameter:
Recall [2( = 12 - Yj Although (Z) is matrix is a matrix with the same size as Z, i... V VZ) E Rd fj only depends on the jdh column of Z, and hence only the jth column of V (Z) will be non zero. More precisely, we have
(Vf}(2)), - ( (2g
and (V)}(Z)) = for k * j. where (V)}(Z)) denotes the 1 column of (f)(Z). We thus have that
Ez,
11 Σ (2)1
4
EI,ZZ
Σ
|z 1
JET
JEZ
(1)
b
f(2).
Similarly, we have [f(]] =ff((), Hence, the quadratic loss satisfies growth condition with 7y
Suppose there exists some constant 2 1 such that m
Using Lemma 2 and Lemma 3, we can estimate the parameters v4, pa, Bo and establish an upper bound on h()%):
h(09)= < m
R2o max (X)
14 max (1 82)dim, wi wiy(L 52) + mm
(A.11)
μq V (1) 2
+ o m (v0)) + Smaxxfu
B4
2
where 61, 82. 83, and he are all constants and independent of do, d1, and m: the term is a constant such that m = di and X E x is derived from Khatri-Rao product with its a-th column defined as vea(ar. 60 va) E RRdd, with probability least & where y
14

---

Under review as a conference paper at ICLR 2022
-( Smimi (E)
-(
d Cógdo -di C8 - 44 thar (X064 logdi -
40 Thae (X164 /dg logdi
- Cod -e CB.
54 max(ki, 122, Mo =00=0(20 == )<((Wo X), C' is a constant, and
di of min (X*1) min (B[ max (B & di (mc wf(c (22]+22)00 2 (X))
wI'
We denote C3 {81, 62, 83. }
We highlight the main condition for the linear convergence of SGD in (6):
a
h(0") O
(33
The convergence happens with probability at least 1
Suppose |cul sufficiently large such that |colv(1 62 d1 becomes the dominating term in Vq.
We note that the order of (max(X) and ( play significant roles for the overparameterization order analysis. For 1, requires following, we focus on 2 2.
do. which is not a common setting in practice. In the
Substituting the parameters obtained (A.11) into (6), sufficient condition satisfy (6) is given by mo? max (X)
d1 2 E((Co, (c1)2o.
Vbo min (X+1)
where
E(Co, &, (ci)20, = 583c2(1 + 82) 4444
11 (0max + Fmax mmax (V
11-5,
Since E(Cs, t, o, {cil2oo () is constant w.r.t. do, d1, and m. The sufficient condition can be expressed as:
d1 Ω mo? max (X) ). Vbo min (X+t))
(A.12)
Finally, along the lines of (Oymak & Soltanolkotabi, 2020)[Section 2.1]. we have Tmax (X) V and mmiu (X*t)
1.
Replacing maxx X)) and mmin (X*t) into (A.12), the overall overparamettrizztion degree becomes dgd1 St(2² /tt)///)..allllll.. Finally using the union bound on the events corresponding to random initializa- tion and random SGD iterates, the linear convergence is established with probability at least e where
1/ di Chado d, Chad2 +e C + C66 +
(A.13)
( 469 4i 1)
-
(eemax(E[>1"
maax amaa (2)66 / do
+
403
mans thas (80 lox
D PROOF OF LEMMA
The content of this proof originally due to (Anonymous) and provided here for the completeness of our paper.
Intuitively, if VV""(W" isometry for all nearby points. Formally, let A, B E Rmxn and let singular values of matrix are ordered such that (A) 2 (A) and o, 2 o, (B) for Sisj j S min(m, n). Using Weyl's inequality and for +
(nos ve -ear-isesssy then one would expect V to remain near-
min(m, n). we have:
The same scaling holds if the other dominates.
15

---

Under review as a conference paper at ICLR 2022
o+j- S (,(A) + (B).
5
(A.14)
More formally, suppose that w E Rd satisfies
||
w/ll S
144
pa.
(A.15)
2
If V ( is (Li p4) -isomeeryy in the sense of Definition 4, then applying Weyl's inequality (A.14)
along with using smoothness and (A.15), we have
V (Φ"(ww) 2 min
V (w")) max (w) (w"(w)))
Fin
2 Ps
Be l|
w
Using similar argument, establish upper bound maxx (VD"(w)
3/4
O max <4 (w)) S max (V4 (w) max (WD((w) (bb((w)) S ug 2
E PROOF OF LEMMA 2
Lemma A.4 (Estimation of h(@"), uaa vg, B4 (Anonymous)), Suppose that the shallow neural network satisfies Assumption Then we have
1 A(09)= - _ R
max
wIy(1 d2)dim, WI (10) 1/ max (1
d2) + + (dam))
(A.16)
n14 V(1 (1-)) (1 (1dmmii((**)
B4 = -20 max) (X) (dmax + xmaxxXaax)
where 81, 82. 83, k1, and 2oz are all constants and independent of da, di, and m. Bg the smoothness constant of the map & restricted to the set {(V, W): mm)x(V) S Xmax}; the term is constant such that m z dl and X Re is derived from Khatri- Raa product with its a-th column defined as voc(Ea
xa) Rdb with probability at least
where J dj Co
S DD
di Cbada -e 682 oinn (X 184 LoRdi -
40/2
Iunn (X 184 / logdi
e -dd e CG3, where
54 max(ki, 12), Mo 6(X wo )o X), C constant, and
2 wi'd di o oxin S min (E[M max (B[M)) S di (me + wflch + o jo (X))
We denote Cs- (ô1, 82, 83, 8
The content this proof originally due to (Anonymous) and provided here for the completeness of our paper.
We first obtain the expression for adjoint operator (+) Rdaxm - Rdi xdo x Rd2xd1 Let
Aw Rdixdd xdo Ay E Rd2xd, and A Rd We expand & as follow:
((W + Aw. V) (WW Vw
(A.17)
Φ(W, V + AA) ((W, + vy4(Av)
where
vw = (((IX)))Amx) vrΦ(Av) = AvO(WX),
16

---

Under review as a conference paper at ICLR 2022
stands for the Hadamard (entry-wise) product, and (WWX) ) is the derivative of é calculated at each entry of the matrix WX. The operator (+) is given by (Aw, Av) - Vw 4 + ((Ay)
Using the eyclic property of the trace operator and trace ((A O B)C) trace ((A 2 CT B we have
( Vw ((TAA)))(((((Wx)))))) (((WW))VVT)) X", .",AW)
(A.18)
(A, vy Ao
Substituting (A. 18), the adjoint operator is given by
V (+) - (((()))vVAA) X (
(A.19)
Suppose that there exist @max: Xmax < xi such that sup [ó(a) < δmaxi
sup [ō(a)) S Qmax.
(A.20)
Lemma A.5. Let A E _m and B E B Then, have
minn (A) S ||AB]] I mmax (M)x((A)]22) (A)
Using Lemma A.5 and triangular incquality, we note that
(V, A)l < (x(Wx)) O T + |
(A.21)
< @max max (X) max (V] All + m (6(WX))
Similarly, we have this lower bound:
|V A)II miin (XWX)))
(A.22)
Substituting O, = (Wo, Vo) into (A.21) and (A.22), μtf and vi are given by:
m < (On)) < Φinxx (X)omax(Vo) + maxx (WWW)) =: 10, Miin (V' (On)) 2 amin (6) (W()))) =: Mao.
(A.23)
Lemma A.6. Let gm and E B Then, for p. 2 we have
|AB||,
||||
In the following, we find the smoothness parameter 3g in (1). Let O, Rdixdo Rdxxd, We note that (2) - v A)l s U1 + U2 where
U1 = ( T x) o (ATx)) V((( T O)o (ATx))II
(A.24)
U2 = |Av X) - Avo(W X)|I
Let us denote
Fmax VV) S Xmax
(A.25)
An upper bound on U1 in (A.24) is given by:
U. < I(V ( X) @ (A X))II + (V( X) (T - Vă(NT X) & (XxIII
< Xmaxx (X)IIV V VIllAw|l + Fmax Xxx (x)x (X))max(VV))) X) - G( 11)
< Amaxo (X)IIV V|]lAw Tmax (X X)|XX max (V)lIW WIllAww
I Fmax (X]VV - V']lAww] + Xmax
Xmax Xmax maax (X)IW - WIllAw1l
where the second last inequality is due to Lemma A.6.
17

---

Under review as a conference paper at ICLR 2022
An upper bound on U2 in (A.24) is given by:
U2 S @maxxmax (X)I Willlar11
Substituting the upper bounds U1 and U2 upper bound max (VD(O)- v is given by
Fmax (+) vE(()) - maxx (X) (Ōmas + Ōmax I1 - W1l + F (X) ( 1m maxxllVV VII
S 20 (X) (ōmuxx + xmaxx 110 ô1
where the last inequality holds since
I W + VV VIl V2WI W1 + V1 - VII
Finally, Bo in (1) given by
BB V 20 20xxxxXXX (òmax + xmaxx
(A.26)
E. ESTIMATING Jlb., V/
We now estimate the random quantities μıg, Vg in our neural network setting. They key quantities to estimate are min (6(W'XX) and Tmax (max(x((OXX)))) To that end, consider Hermite decomposition of the activation function é.
We start with the basic definition of Hermite polynomial and its properties. Let i 0 and let R + I denote the i-th Hermite polynomial. Note that gi 's form an orthogonal basis for the Hilbert space of functions.:
H lu:R-B / ((((t)eep) ( which is equipped with the inner product
(-2 000 }
x² (
2m / u(x))(x)) exp
x²
(u, v)H
dx
for u, u E H. consider probabilist's convention of Hermite polynomial. Specifically, for i,j 2 we have
i! i=
(ge, g3)H H 0 i j.
(A.27)
Using the above orthogonal basis decompose @(W0X X), we have
x( = Σ i! 9: (W"))
(A.28)
1=0
where c; (6.4)) and each matrix (W, E Rd xm is formed by applying qi entry-wise to the
matrix W X. Let us denote
M = 6(X Wo xx
In the following, we first obtain E E[M E W jo W X) with w ~ (0 1) and then obtain a lower bound on mmin (E] and an upper bound on aiin (E[M)) by appropriately scaling the data matrix X.
Applying Hermite decompasition (A.28) and taking expectation, we have
| = 6(x W )o(('))))
x]]
(A.29)
(X
1000 )a, (Wxx))
ilj!
18

---

Under review as a conference paper at ICLR 2022
where the expectation is w.r.t. the random matrix Wo- Let X, E Rd denote the a-th column of the training data X. Each summand in (A.29) is an m x m matrix where
di
El
(oo(xxWo')> woT )9, (9)(W
B
(x
W Wa (o)c
(A.30)
a.6
where - is the e-th row of W for a, E [m]]
In summand the RHS of (A.30), note that there linear combination of W elements inside of each Hermite polynomial.
We the properties of Hermite polynomials (Olver al., 2010)1188188111-
(a} + ......... + a..² d.
[1111 + ... + C.Trr
Σ
Ven (x1) ... .. (1.
(A.31)
(a + ... 22)
where hss form an orthogonal basis, equipped with the inner product (u, t) f [((x))(()) ex) dz. This basis follows the physicist's convention of Hermite polynomial.
Since & and are rescalings of the other, we can replace q's into (A.31). Note that we have |xa = for all a E [m]. Then we have
a: (x. Wo,c,-) i!
E
o.
Yes (Wo.c.1) ... qoan (Wo,e.do)
(A.32)
8.g
where k and Wo,c. are k-th entry of x, and Wo,,, for [do]. Using the expansion in (A.32), we expand (A.30) follows:
(,)(a, = =il!!
Σ
a,1
0,
h.
Pe.s (Wo,,,))
$1
d
5/
s''
81 tottttau Sulo
mi of +
(il)2
Σ Espt.n $s1t
(Ire 1o, ) 1..111 do To.dn )
(A.33)
0
i #
i i= i! Σ 2ss = (er .edd (ara, 100,, )02 to )000
0
8 8 j
where (i b)= = E (x] Wo,e, )as (W (WTCe-xa))
Pa.s' Pa.s (Wo..,..
9s (Woee1) ... goso (Wo,c.o)) 9s, (Wo...) .. 4sho Sdol, and s' = = S'dnl
-.4,, (Wocdo))
S = [$1, ==[s1,
To simplify the expression (A.33), we define X E Rddjxmm xm where the a-th column is given by X
vec(xa x.)
124
which is also called Khatri-Ran product. For O. we use the convention that x 11 T E g
We can rewrite (A.33) as follows:
(a) = [il(X X
i=j i i j.
(A.34)
Substituting (A.34) back into (A.30), we find that
di
[xxx(X TWO )og (W. (W]x
Σ
E
gi((x, T W Wo.c,-)a;(Hk (o,,,
a.b
(A.35)
di X i=j
0
i i j.
19

---

Under review as a conference paper at ICLR 2022
Substituting (A.35) into (A.29), we have
2 Σ
E
Mo = d1
+
(A.36)
i!
1=2
We now establish an upper bound on mmax
Eis i!
(X x
Σ d!
(X+i)
xai
1=2 z! max ( (Xx1) T Xa1)
max
(A.37)
0 max (X)
where Coo is given by
2
which is finite provided that ||l|| is bounded.
Using (A.37), we establish upper bound o muax ( (E(M)))) max (T (B([)))) d1 (meğ (eî jo (X))
Moreover, suppose there exists some such that min (X*) > O. Then we have dj _ min (x*1) x miin (E[M)) This requires to have db 2 m. Putting together the lower bound on miin (E (M))
and the upper bound on miin (E[A)")), noting W = wi W and scaling X accordingly to take into account the coefficient w1, we have
2t & wi di min ( (X* S mmin (B max (B(a) S di (meğ + wf(c + ) (X))
(A.38)
E.2 CONCENTRATION OF THE RANDOM MATRIX M
To how well the random matrix 2 concentrates about its expectation, note that
M o(X T WOT xx
Σ 6(x W. Wo
(A.39)
Σ A
where (4.) C mm are independent random matrices.
Consider the event E that
max [o, S kiwi / do log d1, sE|dh
max Vo.i..llz S k2w2 / du log (E[d;]
(A.40)
where Voss. is the i-th column of Vy. Note that Wo...++ E R and Vo,i.1 E Rd are random zero- mean Gaussian vectors whose entries' variances are w/ and wy respectively. Therefore, with an application of the scalar Bernstein inequality (Vershynin, 2012, Proposition 5.))), followed by the union bound, we observe that the event E, happens except with a probability of at most
Pr := dj Chido + di Ckada
(A.41)
for universal constant with sufficiently large k K2.
20

---

Under review as a conference paper at ICLR 2022
Let i [d1]. Conditioned the event ε upper bound | Wo, 122 is given by:
1Ø 1 Wo,i,+)ll S dmaxx o max (X))X) v do log d1.
(A.42)
Moreover, have
O Omax (A:) 11 -o,,
|| (o,x--ooo,))))) (0)1
(A.43)
S Xmax Fmax (X) log d1.
We now focus on the concentration of min (A1 and (. We concentration property, which provides the tail bound of f(W) o(X² (XTWW W (6WW) with multivariate Gaussian input W. In the following lemma, we show that is Lipschitz function, and its Lipschitz constant explains how f(W) concentrates around its mean.
Lemma A.7. Let f(W) - o(X W X) Suppose W satisfies (A.40). Then f is k-Lipschitz function with constant = 4 max o (X)kiw do log dr. So we have
If(W)- - f(W')ll < 40 o m (1) v do log d1 IIW W/ll
Proof. Note that f(W") M and can be represented as
f(x) = Σ ((W.--)
t=1
where is given by (((W,-) o(X o( JoW We prove that each is x-Lipschitz
which implies that ff is also x-Lipschitz.
We note that f. 's can be expressed as composition of three functions:
fi(v) (gi 92 gv)
where 91, 92. and Os are given by
91 (v = vv f2(v) o(v), fa(v)= vx.
(A.44)
It is clear that 92 is dmax- Lipschitz, and ya is Tmax (X) - from their definitions. Lipschitz constant gi comes from the domain bound as follows:
lv + 5v) - -0 (v) = 1ạvvv + vōv T + 588v TI
< 2l(8vv TI || 1óvvvv
(A.45)
< (2/|v|l [|ōv|]) ||ōv
bound on (2||v|] + [[ōv[)) is obtained in (A.42). Then 9I is -i-Lipsciitz function with K1 = 4 (X)k1a dd log d1. Therefore, all 91, 92 and gs are Lipschitz function, so their composition fa is also Lipschitz function with constant x 402 which completes the proof.
o o
do log di.
Lemma A.8. Let E Rdd denote a Gaussian random vector. Then we have PrílIz Elz]] t {12)) S exp(-t?) where Eg is the event that [z|]| is bounded.
We can focus on the tail distribution of Mo f(Wo). Using Lemmas A.7 and A.8, we have Pr R[M > | exp(-h3))
(A.46)
where 1g4 2 max (X) vdn log di with constant kz
21

---

Under review as a conference paper at ICLR 2022
Using (A.46), we now establish tail bound min (M²):
Pr(omin(MM) - (1 di) (B[M))))&
s Pr (A1 m (LE[M 2 min (LE &1
Pr mmin (MO B[M"D] 2 810min [E[M
Pr(omax (M - -B(M 2 8 (E]M)
Pr[ - E[M 2 51amin (E[MM)
P2
where
(-(aiz 402 of
81 min (E[M)))
P2 exp
max max (X) Kkw wl yo log di
Similarly, obtain
Prromax (M 2 (1 + 62)0 max (E(M")) E ps
where
P3 exp (-( 402 max
820 max [E] I)
o max (X X)kw do log dj
Putting these bounds together with (A.38), we have
wiv (1 81)
- t!
2 di (X*) min (x(((((00
(A.47)
mmax Fmax(o(W") X)) S v 62) (w) v (cf + Od + |col sollvinn dim)
except with a probability of at most pt + P2 + pz.
With establishing the bounds on Gmin mmin (W and mma (omx)) we can finally estimate
pqg, Vg follows:
E.3 LOWER BOUND ON μro
A lower bound on pa is given by
c wf (1 81) d10min(X (min(o(W" pbb,
(A.48)
!!
except with probability of at most pr + P2.
E.4 UPPER BOUND vg
Since PΦ = Ommasermas maxx X x) maxx (VO) a (d(Wo)) we obtain bound on T (V)):
Since O is a Gaussian random matrix, we have
T ( (V") < w2(2 + V d2) S w2Vdi
(A.49)
except with a probability of at most p1 = (c)( where C' is a universal constant (Vershynin, [CrollCoryl 5.35).
Combining (A.49) with the upper bound on maxx Tmaxx(@WW)) (x(WX))) we have
V4 émaxo max Xa (V + Tmax (o(WoXX)
S urdmaxxmax (X) / + w1 / (1 +2) +
+ cov (1+ 82)2dmm
except with probability of at most P1 + Pa + P4-
22

---

Under review as a conference paper at ICLR 2022
E.5
UPPER BOUND ON h(@")
In this section, we bound h()"). Using laa blß S 2||a| + 2//b| we have
h(e)))
- 1 x) Y1?
m
(A.50)
2
2 m |
[V" x)]2
To upper bound the random norm (A.50), we first decompose 0 () into terms including
-o E gd and Vo,i E R2 follows:
V V
Σ
(A.51)
where B, = (W E Raxx'ss 's are independent random matrices for i E [d1].
Conditioned on the event E defined in (A.40), we bound [B]]:
|B||| [Vo.ullallo@WW
< |Vo,i 0max (X) wi / do logdi
(A.52)
S WiWzomax0man (X) (X) dodz log
for S d1.
Substituting the upper bound in A.51 into A.52 and applying the Hoeffding inequality (Hoeffding, 1963), have
Pr(II" u(do, di, {2)
d(W X) (W)))() 2 u(do, d1, d2)(E:)
Pr
[B, - B[B]] こ u(do d1 d2)1E
Ps
where
u(do, d1, d2) = w2nnakk k v dads max mxx log di
and ps exp(-C63) with 2 0 and universal constant C.
Therefore, under the event ε,, we have
2 v I 2(
2 x X)I |2al
h(09)= -
m
(A.53)
$ - Foufusd max 12 dyo max (X) log" d1 + _ =1111
except with probability of at most Pı + Ps. It is natural to assume that d2 = o( We also have ||X||| S
Suppose that
w142 S
(A.54)
mmax ddgd log d1
Substituting (A.54) into (A.53), we have
h()0) < - 83 max (X)
(A.55)
m
where 63, hi, and k2 are all constants and independent of do, di, and m.
23


Reviews:
[{"review_id": "zOn9fEadHd_", "reviewer": "Reviewer_Vg9p", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "While the results of this paper look correct and rigorous, I have a major concern about the significance and novelty of the paper.\n\nFirst of all, the $O( m^2 / \\sqrt{b} )$ condition on overparameterization in fact requires additional assumptions on the data (or data distribution) that is not covered by Assumptions 1-4 in this paper. This result relies on an estimated order of $\\sigma_{\\mathrm{min}} (X^{*t}) $ that is derived by assuming X is uniform. This is a very strong data distribution assumption. With this additional assumption, it is not fair to compare the condition $\\sigma_{\\mathrm{min}} (X^{*t}) $ with the other works in Table 1. For example, in order to compare the result with existing works considering the separable data assumption, the authors should derive additional guarantees of $\\sigma_{\\mathrm{min}} (X^{*t}) $ based on this separable data assumption, as is done in Oymak & Soltanolkotabi (2020). \n\nMoreover, the discussion on Ji & Telgarsky (2020), Chen et al. (2021), and Daniely (2020) is too vague and not convincing. It still seems that these works have already proved better conditions of overparameterization than this paper. Since these works also highlight the improvement of overparameterization conditions, the authors should consider adding them to Table 1 and discuss the differences between this work and existing works in detail.\n\nAt last, as given in Table 1 in this paper, the result in this paper is only better than Oymak & Soltanolkotabi (2020) in the sense that (i) this paper considers the training of parameters on both layers, while Oymak & Soltanolkotabi (2020) only considers the training of the first layer (however, in literature, it is widely believed that the difficulty of the analysis lies mainly on the training of the first layer parameters); (ii) this paper gives results for different mini-batch sizes. However, this paper also has a disadvantage compared to Oymak & Soltanolkotabi (2020), as this paper requires a smooth activation function, while Oymak & Soltanolkotabi (2020) works for ReLU activation. Therefore, the result of this paper can be quite incremental compared to Oymak & Soltanolkotabi (2020). \n\n\nTypos:\n\n1. The sample size is denoted as n in Table 1. However, in the latter part of the paper, the notation of sample size is m.\n\n2. The notation $\\nabla h_j(w^i)$ Equation (4) is not consistent with that in the discussion below it $\\nabla h_j(\\Phi(w^i))$\n\n\n", "summary_of_the_paper": "This paper focuses on improving the condition of overparameterization for stochastic gradient descent on overparameterized shallow neural networks. The authors first present a general global convergence result for SGD on a finite-sum compositional optimization problem, and then apply this general result to two-layer neural networks with smooth activation functions to obtain a sufficient condition of overparameterization of order $O(m^2 / \\sqrt{b})$, where $m$ is the sample size and $b$ is the mini-batch size. ", "summary_of_the_review": "My major concern about this paper is its significance and novelty. Based on this concern, I would like to recommend rejection.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "s9Or4jNyZ2M", "reviewer": "Reviewer_t48E", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "-Strengths:\n\n1. This paper provided a better width requirement bound for linear convergence in two-layer neural network training by generalizing techniques from previous results and taking batch size into consideration. Specifically, compared to (Oymak & Soltanolkotabi, 2020), this paper enables the training for both layers instead of a single layer. Besides, compared to (Anonymous), this paper enables training using mini-batch SGD instead of GD.\n\n2. This paper is generally well-organized and easy to follow. It also provided detailed proof sketches with a few remarks, making the proof easy to understand.\n\n3. The related works appear to be adequately cited and compared in detail.\n\n-Concerns:\n\n1. The novelty of this paper might be somewhat limited, and this is my major concern of this paper. I will explain in detail in the following paragraphs.\n\n1.1 The learning dynamics of neural networks in this paper are still in the lazy regime, and the proof ideas are of similar styles as previous papers in this area. Specifically, as shown in Lemma 1, the authors require that the weights do not move far (i.e., larger than a constant) from the initialization to ensure the local smoothness and bound the eigenvalues of the Jacobian. The bound on minimum eigenvalue of the Jacobian ensures linear convergence, which results in bounded weight change and then induces bounds on eigenvalues of the Jacobian. Therefore, the learning dynamics in this paper still require a lot of things (including weights, Jacobian matrices, etc.) to remain close to initialization, which should be considered as lazy regime. This is different from the neural network training in practice since empirically the weights of neural networks usually move far from initialization.\n\n1.2 The novelty of the techniques used in this paper seems a bit limited. The bounds for local smoothness $\\beta_\\Phi$, eigenvalues of $\\Phi^*(w_0)$, initial function value, and preservation of \"near-isometry\" during training all come from (Anonymous). Furthermore, the idea of bounding the probability that the weights leave the local neighborhood of the initialization exists in Theorem 3.1 of (Oymak & Soltanolkotabi, 2019) and Theorem 2.6 of (Oymak & Soltanolkotabi, 2020). This paper provided a new way of bounding the expected length of SGD trajectory (Proposition 1), enabled training for the second-layer weights, and generalized SGD to mini-batch SGD by introducing the batch size $b$ (Theorem 2) to interpolate between (Anonymous) and (Oymak & Soltanolkotabi, 2020). The techniques used in these steps seem specific to the particular setting in this paper and might not generalize. Thus, the technical novelty of this paper might be a bit limited.\n\n2. The results in this paper only apply to smooth activation functions with bounded Hermite norm, which is a bit strong, and the width requirement also depends on the smoothness factor and Hermite norm. Most previous works hold for ReLU activations, as also shown in Table 1.\n\n-Minor Comments:\n\n1. The statement of Theorem 1 might need to be further clarified about the randomness. When stating Theorem 1, the authors said \"with probability at least $1-\\zeta$\", and the result still has the expectation notation. It would be better if the authors could clarify what randomness goes into the \"$1-\\zeta$\" part and what randomness is the expectation taken over. One possible way might be to define the event that SGD travels outside the neighborhood of the initialization and state Theorem 1 in a similar way as Theorem 2.6 in (Oymak & Soltanolkotabi, 2020).\n\n-Typos: \n\n1. Definition 3, \"$\\frac1c$\" -> \"\"$\\frac1b$\"\"\n2. $\\rho_\\Phi$ is used in Proposition 1 but not formally defined until Lemma 3, so it is better to move the definition earlier.\n3. \"$\\simeq$\" is used in Lemma 2 and Section 3.1 but is not formally defined.\n\n---------------------Update--------------------------\n\nThank the authors for their responses. I have read all other reviews and the authors' responses to all the reviewers, and I have decided to keep my score unchanged. The authors' responses address some of my concerns, e.g., their main results do not directly require the weights during training remain close enough to the initialization. However, my major concern (the novelty of the proof techniques, which is also shared by the other reviewers) still remains because most of the results/methods used in this paper already exist in the literature. Therefore, I would like to keep my score and tend to recommend rejection.", "summary_of_the_paper": "This paper proved that a two-layer neural network with smooth activation and proper initialization can converge linearly to a global minima of training loss using mini-batch SGD when the width is larger than $\\Omega(m^2/\\sqrt{b})$ where $m$ is the number of training data and $b$ is batch size. As the batch size increases, this provides an interpolation between the quadratic result for SGD and the sub-quadratic result for full-batch GD. To prove this result, the authors first provide a general convergence result for SGD on a particular class of functions and then apply this framework to 2-layer neural networks to derive the width requirement.", "summary_of_the_review": "I tend to vote for rejecting this paper. Despite generalizing the linear convergence result to mini-batch SGD and improving the width requirement to sub-quadratic, my major concern about this paper is its limited novelty, as explained in the \"Concerns\" section above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QiKVdKnz31", "reviewer": "Reviewer_2P9T", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Pros:\n1. This paper relaxed the over-parameterization requirement in two-layer neural networks for the SGD algorithm, which is certainly an important direction.\n2. The proof involves bounding the distance to initialization for SGD iterates, which is much more challenging than for GD. I think the techniques here can be useful in future studies in SGD convergence. \n\nCons:\n1. I am concerned about the novelty of the proof. It seems to me that the proof is very similar to the NTK analysis in the sense that it argues the Jacobian matrix is full-rank during the training because the SGD iterates stay close to the initialization. I wonder if there is any conceptual difference between this proof and the NTK argument. \n2. In section 3.1, the authors assumed that $m\\geq d_0^2$ and claimed it's the case in practice. I think in practice the number of training samples $(m)$ is much smaller than the square of input dimension $(d_0^2).$ For example, in CIFAR the input dimension is $32\\times 32\\times 3=3072$ and there are only $50000$ training samples; in ImageNet the input dimension is $256\\times 256\\times 3=196608$ and there are only 1M samples. \n3. One of the messages of this paper is that a smaller batch size requires a wider neural network. Is there any empirical experiment that can support this claim? Otherwise, this might just be an artifact of the analysis.", "summary_of_the_paper": "1. This paper proves that SGD converges to a global minimum in certain non-convex problems assuming the loss function satisfies a growth condition. The proof relies on assuming that the initial Jacobian matrix is non-singular and shows that it stays non-singular since SGD iterates remain close to the initialization. \n2. The paper then applies the above analysis to a two-layer neural network and proves that a subquadratic scaling on the width is sufficient for global convergence assuming the minibatch size grows with the number of training samples. For constant batch size, it requires quadratic over-parameterization. Furthermore, an interpolation between subquadratic and quadratic scaling is given depending on the batch size. ", "summary_of_the_review": "The main result of this paper is proving the subquadratic width scaling for SGD convergence in two-layer neural networks assuming the batch size grows with the number of training samples. I understand that the analysis requires new techniques to bound the distance of SGD iterates to its initialization, but I think the proof is conceptually the same as NTK analysis and am concerned about its novelty. Therefore, I think this paper is marginally below the acceptance threshold. I will be willing to raise my score if my concerns are addressed. \n\n------------------\n\nThanks for the response. After reading the response and other reviews, I decided to keep my original score. My major concern is still the novelty of the proof. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "NnZ1qPVjwoU", "reviewer": "Reviewer_SWMd", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The results presented in this paper are already known in the literature. Please check the two highly related papers: Liu et al (2021), Liu et al (2020).\n\n>Specifically, assuming PL condition on the loss function, convergence of SGD is already obtained in Liu et al (2021), with an exponential learning rate. This covers Theorem 1 of this submission. \n\n>The concepts of near-isometry (definition 4) and length of trajectory (proposition 1) are also similarly established in Liu et al (2021). Near-isometry corresponds to the so-called uniform conditioning of NTK (neural tangent kernel), and proposition 1 corresponds to the “existence of solution” in a neighborhood ball.\n\n>PL conditions are shown on neural networks in Liu et al (2021). I noticed that Liu et al (2021) includes deep neural networks, as well as shallow ones. But this submission only considers shallow networks, with more assumptions (assumption 3 & 4).\n\nThe proof of the growth condition of the shallow network is incorrect. In section 2, the theory assumes growth condition on stochastic gradients, i.e., derivative of loss w.r.t. the model *parameters*. However, when proving a shallow network satisfies growth conditions in the proof of theorem 2, the paper analyzes a different object:  derivative of loss w.r.t. the model *output*.\n\nThe notations of the paper are not consistent and ambiguous, which makes it hard to read. For example, in Eq.(13) and the sentence after, matrix Z is discussed, but Z is never defined before.\n\n\nReferences:\n\nLiu, et al. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks, 2021.\n\nLiu, et al. On the linearity of large non-linear models: when and why the tangent kernel is constant. NeurIPS, 2020.\n\n================ Edited after author feedback ================\n\nThanks for the authors for the feedback.\n\nThe paper seems properly cited the anonymous paper. So, I removed the dual submission concern flag in the ethic review part.\n\nAs for the high similarities with prior works, I never \"acknowledged that there are *significant* differences between\" the current submission and  prior works, e.g., [Liu et al., 2020]. The concepts and main logic are highly similar to prior works I mentioned above. \n\nI have read the other reviews and agree that this paper lacks novelty, and that main concepts and methods are already known in prior works. So, I would like to keep my score unchanged.\n\n\n\n", "summary_of_the_paper": "This paper first analyzes the convergence of SGD under assumptions of PL condition on loss function and growth condition on stochastic gradients. Then, it considers a two-layer neural network with some special setting, and claims that this network with quadratic loss satisfies both PL condition and growth condition, and hence SGD converges.", "summary_of_the_review": "1. Known results\n2. incorrect proof\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper shows SGD enjoys linear convergence for shallow neural networks under certain assumptions. However, reviewers reach the consensus that this paper lacks technical novelty. The meta reviewer agrees and thus decides to reject the paper.
Decision: Reject