Year: 2021

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.

heading: 1 INTRODUCTION
text: 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, a line of research has established convergence of first-order methods such as gradient descent (GD) to global optimality, (Allen-Zhu et al., 2019; Kawaguchi & Huang, 2019; Du et al., 2019; Du & Lee, 2018; Zou & Gu, 2019; Brutzkus & Globerson, 2017; Song & Yang, 2019; Oymak & Soltanolkotabi, 2020), a phenomenon that has been confirmed in practice.
Empirically, as long as the width of a network scales linearly with the size of the training data (mild overparameterization), 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 a larger degree of overparameterization, 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 are trained with GD simultaneously, state-of-the-art results show that subquadratic (not linear) scaling is enough to converge to global optimality (Anonymous). Despite being close to the ideal linear rate of overparameterization, due to 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 mini-batch 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 a neural network, which is initialized with standard initialization schemes.
Our contributions:
• We show that under proper initialization and choice of learning rate, the iterates of SGD converge to a 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
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 on overparameterization focuses on 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 is a different setting compared to 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 are 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 or additional assumptions on the data (like separability) to guarantee convergence to a global minimum. Moreover, backpropagation on ReLU networks does not correctly calculate the gradient at all points of differentiability (Kakade & Lee, 2018; Bolte & Pauwels, 2021), which raises major technical issues. In contrast, we assume a smooth activation, similar to 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 to the results in (Anonymous), controlling the length of the trajectory is more involved in this paper, which requires a 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 overparametrization literature in Table 1.
Lazy Training. Proving fast convergence to global optimality is not a complete answer. It has been shown that despite fast convergence, it is possible that an algorithm tends towards a 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
the lazy regime. This is the reason why we omit such result from Table 1. In this work, we show global convergence and achieve subquadratic scaling under standard initialization schemes, which empirically perform well on test data.
Polylogarithmic width is enough to obtain convergence for neural networks of arbitrary depth, according to Ji & Telgarsky (2020); Chen et al. (2021). However, in those work, convergence is understood in 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 zero-approximation. This is different from the problem considered in our paper.
For a binary classification problem, Daniely (2020) showed that near linear network size is sufficient for SGD to memorize random examples under a variant of Xavier initialization, which is a different setting compared to our paper. For a 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.
A recent line of work uses mean-field analysis to approximate the target distribution of the weights in a 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∇ to represent the Jacobian of a vector-valued and gradient of a scalar-valued function. We use 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 σmin(T ) and σmax(T ) to denote the smallest and largest singular values of a linear map T . We use [n] to represent {1, · · · , n} for an integer n. We use Õ and Ω̃ to hide logarithmic factors and use . to ignore terms up to constant and logarithmic factors.

heading: 2 A GENERAL GLOBAL CONVERGENCE RESULT FOR SGD
text: In this section, we consider a general non-convex minimization problem and show that for a certain choice of learning rate and careful initialization, the iterates of SGD converge to a global minimum with high probability and exponentially fast. In Section 3, we extend our consideration to the training of a shallow neural network and find the hidden layer size, which is sufficient for SGD to converge to a global minimum i.e., its overparameterization degree. Definition 1 (Smoothness). Let βψ > 0. A function ψ : Rd1 → Rd2 is βψ-smooth, if for all u,v ∈ Rd1 , we have
σmax(∇ψ(u)−∇ψ(v)) ≤ βψ‖u− v‖. (1)
Definition 2 (PL condition (Bolte et al., 2017)). A function ψ : Rd1 → R satisfies the PL condition if there exists αψ > 0 such that, for all u ∈ Rd1 , we have
ψ(u) ≤ ‖∇ψ(u)‖ 2
2αψ . (2)
We are now ready to state our finite-sum compositional optimization problem:
min w∈Rd h(w) := f(Φ(w)) = 1m m∑ j=1 fj(Φ(w))  , Φ : Rd → Rd̃, f, fj : Rd̃ → R+ (3) where m denotes the number of training examples. Assumption 1. The functions introduced in Eq. (3) satisfy the following properties: (i) Φ is twicedifferentiable and βΦ-smooth (Definition 1), (ii) f is twice-differentiable and βf -smooth and (iii) f satisfies the PL condition with some αf > 0 (Definition 2).
We study the iterates of the stochastic gradient descent (SGD) algorithm when applied to the objective function h in Eq. (3). For i ≥ 0, let Ii denote a random minibatch at iteration i drawn uniformly at random, independent of all previous draws. Let b ∈ [m] denote the minibatch size, i.e., |Ii| = b for all i. The SGD iterates are defined by a random variable w0, referred to as the initialization, and the update rule:
wi+1 = wi − λ1 b ∑ j∈Ii ∇hj(wi), (4)
where λ > 0 is the learning rate and hj(w) := fj(Φ(w)) ∀j,w. An important feature of the SGD iterates is that 1b ∑ j∈Ii ∇hj(Φ(wi)) in Eq. (4) is an unbiased
estimator of the gradient ∇h(wi) given wi, i.e., E [
1 b ∑ j∈Ii ∇hj(Φ(wi))|wi ] = ∇h(wi). 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 ψ : Rd → R with a finite-sum structure satisfies the growth condition with minibatch size b if there exists ηψ > 0 such that, for all u ∈ Rd, we have
E [∥∥∥1 c ∑ j∈I ∇ψj(u) ∥∥∥2] ≤ ηψ‖∇ψ(u)‖2, (5) where the expectation is over the random choice of set I. Assumption 2. In Eq. (3), f satisfies the growth condition (Definition 3) for some ηf > 0.
We are now ready to state the main result of this section. Theorem 1. Let Assumptions 1 and 2 hold and let ζ > 1. Suppose that at initialization,
0 < µΦ ≤ σmin(∇Φ∗(w0)) ≤ σmax(∇Φ∗(w0)) ≤ νΦ, h(w0) = O ( αfµ 6 Φ
ζβ2Φηfν 2 Φ
) . (6)
Then, for a sufficiently small learning rate
λ . min
( µ2Φ
ηf (βΦν2Φ‖∇f(Φ(w0))‖+ βfν4Φ + βfµΦν3Φ) , µΦ ζ √ ηfνΦ(βΦ‖∇f(Φ(w0))‖+ βfνΦµΦ) ) (7)
the iterates of SGD {wi}i≥0 (4) converge to a global minimizer of h (3) with the optimal value of zero, exponentially fast and with probability at least 1− 1/ζ. The rate of convergence is given by
E[h(wi)] ≤ (1− Cλαfµ2Φ)i · h(w0) for a universal constant C. Remark 1. The second item in Eq. (6) suggests initializing close to a global minimum of the nonconvex optimization problem. This feature has precedence in the related literature, e.g., in matrix factorization (Chi et al., 2019).
The proof of Theorem 1 is deferred to Appendix B. However, in the remaining of this section we provide a 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-isometry property. Definition 4 (Near-isometry). A linear map T : Rd1 → Rd2 is (µ, ν)-near-isometry if there exist 0 < µ ≤ ν such that
µ ≤ σmin(T ) ≤ σmax(T ) ≤ ν. (8)
Let w denote the limit point when the SGD algorithm is run with some learning rate and let∇Φ∗(w) denote the adjoint operator of∇Φ(w). Convergence of SGD is ensured with high probability due to the strong growth condition (Definition 3) along with proper learning rate and initialization. We note that w is a first-order stationary point of h. Hence we have:
0 = ∇h(w) = ∇Φ∗(w)∇f(Φ(w)) (9)
Note that if ∇Φ∗(w) is nonsingular, it would follow that ∇f(Φ(w)) = 0. The PL condition (Definition 2) would then imply that Φ(w) is a 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, a careful choice of initialization will ensure that ∇Φ∗ is nonsingular for all elements within a certain distance of w0. Second, we show that under small enough learning rate, the iterates of SGD remain close to the initialization w0, with high probability regardless of the number of iterations.
The third and final step will use the non-singularity of∇Φ∗ at convergence and Eq. (9) to conclude global optimality.
This is akin to the arguments in (Anonymous), however, in our case 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 ∇Φ∗ is non-singular, with high probability.
A crucial result for the first step of our proof has already been established in by (Anonymous). It shows that a smooth function that is near-isometry at initialization will preserve such property for all points within a certain distance. Lemma 1 (Anonymous). Let Φ be βΦ-smooth and ∇Φ∗(w0) be a (µΦ, νΦ)-near-isometry. Then
for all w such that ‖w −w0‖ ≤ µΦ 2βΦ , µΦ 2 ≤ σmin(∇Φ∗(w)) ≤ σmax(∇Φ∗(w)) ≤ 3νΦ 2 (10)
The second step in the proof of Theorem 1 is to compute the expected length of the SGD trajectory which is spent inside the ball defined in Eq. (10). We find an 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 1 and 2 hold and let ζ > 1. Let the random variable I denote the first iteration of SGD (Eq. (4)) such that
wI /∈ B := ball(w0, ρΦ) := {w : ‖w −w0‖ ≤ ρΦ} (11)
or I =∞ if the trajectory does not leave B. Suppose that w0 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[`(I)] ≤ µΦ 2ζβΦ = ρΦ ζ . (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 in terms of the norm of gradients of f . With a 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 E[‖wI − wI−1‖] is bounded. Finally, under proper initialization, we obtain an upper bound on the expected length of the trajectory for the iterates inside the ball, i.e., E[ ∑I−1 i=0 ‖wi −wi−1‖]. Remark 2. A 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 to analyze.
Using the upper bound (12) on the expected length of the trajectory spent inside B = ball(w0, ρΦ), we can bound the probability that the SGD iterates leaves the ball B. Indeed, in order for the process to leave B starting from w0, it is required that the length of the trajectory spent inside B satisfies l(I) ≥ ρΦ. Hence, using bound (12) on E[`(I)] 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[`(I)] implies the convergence of the iterates. Remark 3. With a more involved analysis on the concentration properties of the random variable `(I), it may be possible to greatly improve the dependence of the initialization and step size on ζ.
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 a bound on E[`(I)]).
Although `(I) is obtained as a sum of random variables, the difficulty of obtaining better concentration bounds for `(I) 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 `(I).
In the following section, we specify our result to the special case of shallow neural networks. We will show that, in the case of quadratic loss, the strong growth condition naturally holds, with a constant depending on 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 1 with high probability.

heading: 3 GLOBAL OPTIMALITY OF NEURAL NETWORKS TRAINED WITH SGD
text: Setup. We will consider the problem of training a shallow neural network with one hidden layer, input dimension d0, d1 hidden nodes, output dimension d2, and quadratic loss. We denote the data and label matrices as X ∈ Rd0×m and Y ∈ Rd2×m, respectively. LetW ∈ Rd1×d0 and V ∈ Rd2×d1 denote the parameters of the first and second layers of the network, respectively. We collect both parameters in a variable Θ = (W,V ) ∈ Rd1×d0 × Rd2×d1 . In order to fit the supervised training of the network to the template studied in Section 2 (Eq. (3)) we define:
Φ(Θ) := V · φ(WX) ∈ Rd2×m, fj(Z) = ‖Zj − Yj‖2 ∈ R+ (13)
where Zj denotes the j-th column of a matrix Z and φ : R→ R is the activation function, which is applied entry-wise. We can now write the problem as a the finite-sum:
min θ h(Θ) = f(Φ(Θ)) = 1m‖V φ(WX)− Y ‖2 = 1m m∑ j=1 ‖V φ(WXj)− Yj‖2  (14)
We will make an assumption on the Hermite norm (Definition 5) of the activation function. Our assumptions on the activation function are summarized as Assumption 3 below. Definition 5 (Hermite norm (Olver et al., 2010)). Let φ : R→ R. The Hermite norm of φ is given by ‖φ‖H = √∑∞ i=0 c 2 i where ci denotes the i-th Hermite coefficients of φ given by:
ci = 〈φ, qi〉H = 1√ 2π
∫ φ(x)qi(x) exp ( −x 2
2
) dx
and qi : R→ R is the i-th Hermite polynomial (probabilist’s convention) for i ≥ 0. Assumption 3. φ is twice-differentiable, φ(0) = 0, supa |φ̇(a)| = φ̇max < ∞, supa |φ̈(a)| = φ̈max <∞, and ‖φ‖H <∞.
The popular ReLU does not satisfy the twice-differentiability assumption. However, smooth approximations of ReLU such as 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 et al., 2016; Gulrajani et al., 2017; Kumar et 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], ‖Xj‖ ≤ 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 0 ∼N ( 0, 1
d0
) , V 0 ∼N ( 0, 1
d1
) . Θ0 := (W 0, V 0) (15)
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 h(Θ0), near-isometry constants (µΦ, νΦ) of ∇∗Φ(Θ0) and smoothness parameter βΦ, which are required in Theorem 1. Lemma 2 (Estimation of h(Θ0), µΦ, νΦ, βΦ (Anonymous)). Let Assumptions 3 and 4 hold, and suppose that Θ0 follows the initialization distribution in Eq. (15). Let t be a positive integer such that m ' dt0 and X∗t ∈ Rd t 0×m be the matrix whose a-th column defined as vec(xa ⊗ · · · ⊗ xa) ∈ Rd t 0 .
For some constants δ1, δ2, δ3, k1, and k2 independent of d0, d1 and m, with probability at least 1− ψ̃ it holds that:
h(Θ0) ≤ δ 2 3k 2 1k 2 2σ 2 max(X)
m νΦ = max { |c0| √ (1 + δ2)d1m, ω1 √ (1 + δ2)(c21 + c 2 ∞)d1σmax(X) } µΦ = √ (1− δ1)
c2t t! d1σmin(X ∗t)
(16)
The precise expression for ψ̃ is provided in Appendix E, ci is the i-th Hermite coefficients of φ (Definition 5) and c2∞ = ∑∞ i=2 c 2 i /i!.
Moreover, the map Φ restricted to the set {(V,W ) : σmax(V ) ≤ χmax} is smooth with constant
βΦ = √ 2σmax(X) ( φ̇max + φ̈maxχmax ) . (17)
Although the mapping Φ is not globally smooth, Lemma 2 shows that it is smooth in a 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 a neighbourhood of V 0 as required in Theorem 1.
Lemma 3. Let Assumption 3 hold. Let V 0,W 0 be arbitrary matrices and µΦ be as in (16). Let
βΦ := √ 2σmax(X)(φ̇max + σmax(V 0)) + φ̈maxµΦ
2φ̇max , ρΦ := µΦ 2βΦ
(18)
The function Φ is βΦ-smooth over the set:
BρΦ(V 0,W 0) :=
{ (V,W ) : √ ‖V − V 0‖2 + ‖W −W 0‖2 ≤ ρΦ } (19)
Proof. Let
χmax := σmax(V 0) +
µΦ
2 √ 2σmax(X)φ̇max , B̃χmax := {(V,W ) : σmax(V ) ≤ χmax} (20)
Lemma 2 then implies that Φ restricted to B̃χmax is βΦ-smooth, following Eq. (17). With this choice of χmax we show that BρΦ(V
0,W 0) ⊆ B̃χmax , which implies the result. Note that βΦ ≥√ 2σmax(X)φ̇max, hence
χmax ≥ σmax(V 0) + µΦ 2βΦ = σmax(V 0) + ρΦ.
Suppose that (V,W ) ∈ BρΦ(V 0,W 0). By Eq. (19) this implies ‖V − V 0‖ ≤ ρΦ. Then,
σmax(V ) ≤ σmax(V − V 0) + σmax(V 0) ≤ ‖V − V 0‖+ σmax(V 0) ≤ ρΦ + σmax(V 0) ≤ χmax.
In our case, as f is the quadratic loss, the growth condition (Definition 3) is satisfied with ηf = mb . 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 1 and 2 hold for our shallow neural network training setting, ensuring that Theorem 1 is valid.
We are now ready to integrate Lemma 2 and Lemma 3 together with the convergence guarantees in Theorem 1 to arrive at the sufficient degree of overparameterization required for the convergence of SGD. The following theorem finally concludes that for the shallow neural network described in Section 3, for a sufficient degree of overparameterization SGD converges to a global minimum with high probability.
Theorem 2 (Shallow network with SGD). Suppose that Assumptions 3 and 4 hold, and that that (W 0, V 0) is randomly initialized as in (15). Suppose that the hidden layer width d1 satisfies
d1 = Ω̃ ( ξ(Cδ, t, φ, {ci}i≥0, ζ) σ2max(X)m
σ3min(X ∗t) √ b
) (21)
where Cδ is a set of constants, ξ is a term independent of d0,m. The SGD iterates converge to a global minimum exponentially fast with probability at least 1− ψ(φ, ξ, d0, d1, d2, X, ζ). See Appendix C for the exact expressions of ξ and ψ and the proof.
Finally, we provide an order analysis to understand how the sufficient overall overparameterization degree directly depends on the minibatch size. Intuitively, the sufficient overparameterization degree improves (is lower) as the minibatch size increases.

heading: 3.1 IMPACT OF THE MINIBATCH SIZE ON THE OVERPARAMETERIZATION DEGREE
text: For t = 1, the analysis requires m ' d0, which is not a common setting in practice. For t ≥ 2, we suppose that m ' dt0, which is the case in practice. We estimate that σmax(X) ' √ m/d0
and σmin(X∗t) ' √ m/dt0 ' 1, along the lines of (Oymak & Soltanolkotabi, 2020, Section 2.1). Substituting σmax(X) and σmin(X∗t) into (21), we have
d1 & m2√ bd0 . (22)
Therefore, the overall overparameterization degree becomes d0d1 ' Ω̃(m2/ √ b), which is sufficient for SGD to find a global minimum at a linear rate except with an arbitrary small probability. This fact will let us understand more clearly the effect minibatch size on the overparameterization degree.
If b = Ω̃(m), similar to gradient descent, a subquadratic scaling on the network width, d0d1 ' Ω̃(m 3 2 ), is sufficient. In that case, an optimal linear scaling d1 ' Õ(m) is sufficient when the number of input features is sufficiently large d0 ' Ω̃( √ m).
On the other hand, when the batch size is small b = Õ(1), we recover the standard quadratic scaling on the network width. Our analysis provides an interpolation between d0d1 ' Ω̃(m 3 2 ) and d0d1 ' Ω̃(m2) depending on b. As long as the batch size b ' Ω̃(ma) for some a > 0, we achieve a subquadratic scaling.

heading: 4 CONCLUSIONS AND FUTURE WORK
text: In this work, we prove linear convergence of stochastic gradient descent for training overparameterized two-layer neural networks with smooth activation functions, using classical initialization strategies, and where both layers are trained simultaneously. We provide a lower bound on the required over-parameterization degree for our result to hold, depending on the batch size b used to compute the stochastic gradients. More precisely, we show that using a number of parameters d0d1 = Ω(m 2/ √ b) is sufficient to obtain linear convergence with high probability, providing subquadratic over-parameterization degree as long as the batch size increases with the number of data points.
In future work, we would like to relax the smoothness condition on 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 `(I), characterizing the length of the trajectory spent in a neighborhood of the initialization. Finally, an important step would be to 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.

heading: A PROOF OF PROPOSITION 1
text: According to the definition of I , wi ∈ B for i = 0, · · · , I − 1. We first find an upper bound on the expected length of the trajectory in terms of the norm of gradients of 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 ‖wI−wI−1‖ is bounded. Finally, under proper initialization, the final bound is established.
The “length” of the trajectory traced by the SGD iterates {wi}Ii=0 is
`(I) := I−1∑ i=0 ‖wi+1 −wi‖
= λ I−1∑ i=0 ‖1 b ∑ j∈Ii ∇hj(wi)‖
. λνΦ I−1∑ i=0 ‖1 b ∑ j∈Ii ∇fj(zi)‖
(A.1)
where zi = Φ(wi) for all i.
The expected length of this segment of the trajectory is therefore bounded as
E[`(I)] . λνΦE I−1∑ i=0 ‖1 b ∑ j∈Ii ∇fj(zi)‖  ≤ λ√ηfνΦE
[ I−1∑ i=0 ‖∇f(zi)‖ ] (A.2) where the last inequality holds thanks to the growth condition and Jensen’s inequality.
We now develop a “descent inequality’ and establish a lower bound on f(zi)− E[f(zi+1)|wi]. First, consider two consecutive SGD iterates i, i+ 1 such that wi,wi+1 ∈ B. Then, we have
f(zi)− f(zi+1) ≥ 〈zi − zi+1,∇f(zi)〉 − βf 2 ‖zi+1 − zi‖2
= 〈Φ(wi)− Φ(wi+1),∇f(zi)〉 − βf 2 ‖Φ(wi+1)− Φ(wi)‖2
= 〈∇Φ(wi) { wi −wi+1 } ,∇f(zi)〉 − βf
2 ‖Φ(wi+1)− Φ(wi)‖2 − 〈Φ(wi+1)− Φ(wi)−∇Φ(wi) { wi+1 −wi } ,∇f(zi)〉
≥ 〈∇Φ(wi) { wi −wi+1 } ,∇f(zi)〉 − βf
2 ‖Φ(wi+1)− Φ(wi)‖2
− βΦ 2 ‖wi+1 −wi‖2‖∇f(zi)‖
≥ 〈∇Φ(wi) { wi −wi+1 } ,∇f(zi)〉 − 1
2 ‖wi+1 −wi‖2
( βΦ‖∇f(zi)‖+ 9βfν 2 Φ
4 ) = λ〈∇Φ(wi)
{1 b ∑ j∈Ii ∇hj(wi) } ,∇f(zi)〉 − λ 2 2 ‖1 b ∑ j∈Ii ∇hj(wi)‖2 ( βΦ‖∇f(zi)‖+ 9βfν 2 Φ 4 ) (A.3)
Hence, taking expectation over the selected batch ni at iteration i, we find that
f(zi)− E[f(zi+1)|wi]
≥ E λ〈∇Φ(wi){1 b ∑ j∈Ii ∇hj(wi)},∇f(zi)〉 − λ2 2 ‖1 b ∑ j∈Ii ∇hj(wi)‖ ( βΦ‖∇f(zi)‖+ 9βfν 2 Φ 4 ) |wi 
= λ〈∇Φ(wi){∇h(wi)},∇f(zi)〉 − λ2 2 E ‖1 b ∑ j∈Ii ∇hj(wi)‖2|wi (βΦ‖∇f(zi)‖+ 9βfν2Φ 4 ) = λ‖∇h(wi)‖2 − λ2 2 E ‖1 b ∑ j∈Ii ∇hj(wi)‖2|wi (βΦ‖∇f(zi)‖+ 9βfν2Φ 4
) ≥ ( λ‖∇h(wi)‖2 − λ 2ηfν 2 Φ
2 ‖∇f(zi)‖2
( βΦ‖∇f(zi)‖+ 9βfν 2 Φ
4 )) = λµ2Φ‖∇f(zi)‖2 ( 1− ληfν 2 ΦβΦ‖∇f(zi)‖
2µ2Φ − 9ηfβfν
4 Φ
8µ2Φ
) (chain rule and Lemma 1)
& λµ2Φ‖∇f(zi)‖2
where the final inequality holds if the learning rate is small enough such that
λ . µ2Φ
ηfβΦν2Φ maxi ‖∇f(zi)‖+ ηfβfν4Φ . (A.4)
We also note that: √ f(zi)− √ E[f(zi+1)|wi] = (f(z
i)− E[f(zi+1)|wi])√ f(zi) + √ E[f(zi+1)|wi]
& λµ2Φ‖∇f(zi)‖2√ f(zi) + √ E[f(zi+1)|wi]
≥ λµ 2 Φ‖∇f(zi)‖2 2 √ f(zi) ≥ λ √ αfµ 2 Φ‖∇f(zi)‖2√
2‖∇f(zi)‖
= λ √ αfµ 2 Φ√
2 ‖∇f(zi)‖.
(A.5)
Substituting the above back into (A.2), and using the fact that wi ∈ B ∀i = 0, . . . , I − 1, an upper bound on E[`(I)] is given by:
E[`(I)] ≤ λ√ηfνΦE [ I−1∑ i=0 ‖∇f(zi)‖ ]
. √ ηfνΦ √ αfµ2Φ E [ I−2∑ i=0 (√ f(zi)− √ E[f(zi+1)|wi] )] + λ √ ηfνΦE [ ‖∇f(zI−1)‖ ] ≤ √ ηfνΦ √ αfµ2Φ E [ I−1∑ i=0 √ f(zi)− √ f(zi+1) ] + λ √ ηfνΦE [ ‖∇f(zI−1)‖ ] (Jensen’s inequality)
= √ ηfνΦ √ αfµ2Φ
E [√ f(z0)− √ f(zI) ] + λ √ ηfνΦE [ ‖∇f(zI−1)‖ ] ≤ √ ηfνΦ √ f(z0)
√ αfµ2Φ
+ λ √ ηfνΦE [ ‖∇f(zI−1)‖ ] . (A.6)
Suppose that, in addition to the previous bound on the learning rate, we have
λ ≤ µΦ 4ζ √ ηfνΦβΦ maxi ‖∇f(zi)‖ , (A.7)
and that the initialization satisfies
f(z0) = h(w0) . αfµ
6 Φ
ζ2β2fηfν 2 Φ
. (A.8)
for some ζ > 1. Then, we obtain (12).:
E[`(I)] ≤ µΦ 2ζβΦ = ρΦ ζ .
We note that the local Lipschitz constant of f is given by
max i ‖∇f(zi)‖ ≤ ‖∇f(z0)‖+ max i ‖∇f(zi)−∇f(z0)‖
≤ ‖∇f(z0)‖+ βf max i ‖zi − z0‖
= ‖∇f(z0)‖+ βf max i ‖Φ(wi)− Φ(w0)‖
= ‖∇f(z0)‖+ 3βfνΦ 2 max i ‖wi −w0‖
≤ ‖∇f(z0)‖+ 3βfνΦ 2 · ρΦ
= ‖∇f(z0)‖+ 3βfµΦνΦ 4βΦ .
(A.9)
Substituting (A.9) into (A.4) and (A.7), an upper bound on the learning rate of SGD is given by
λ . min
( µ2Φ
ηf (βΦν2Φ‖∇f(z0)‖+ βfν4Φ + βfµΦν3Φ) , µΦ ζ √ ηfνΦ(βΦ‖∇f(z0)‖+ βfνΦµΦ)
) .
This completes the proof of Proposition 1.

heading: B PROOF THEOREM 1
text: Let ζ > 1. Using Proposition 1, under proper initialization and choice of learning rate, the expected length of SGD trajectory is bounded above by:
E[`(I)] ≤ µΦ 2ζβΦ = ρΦ ζ .
Thus, using Markov inequality on `(I), we have
Pr{`(I) ≥ ρΦ} ≤ 1
ζ .
Therefore, with probability greater than 1− 1ζ , we have `(I) < ρΦ, meaning that the SGD trajectory never leaves the ball B, i.e., I =∞. Moreover, conditioned on this event, `(I) corresponds to the length of the full trajectory. Since we have a bound on E[`(I)], 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:
E[h(wi+1)|wi] = E[h(wi+1)|wi]− h(wi) + h(wi) = E[f(zi+1)|wi]− f(zi) + h(wi) ≤ −Cλµ2Φ‖∇f(zi)‖2 + h(wi) ≤ −Cλαfµ2Φf(zi) + h(wi) = (1− Cλαfµ2Φ)h(wi),
(A.10)
where C denotes constants and zi = Φ(wi) for all i. Taking expectation of both sides of (A.10) w.r.t. n0, · · · , ni−1 completes the proof of Theorem 1.

heading: C PROOF OF THEOREM 2
text: For the case of quadratic loss functions, we have αf = βf = 2m . In the following, we first find the growth condition parameter:
Recall fj(Z) = ‖Zj − Yj‖2. Although ∇fj(Z) is a matrix is a matrix with the same size as Z, i.e.,∇f(Z) ∈ Rd2×m, fj only depends on the jth column of Z, and hence only the jth column of ∇fj(Z) will be non zero. More precisely, we have
(∇fj(Z))·j = 2
b (Zj − Yj) .
and (∇fj(Z))·k = 0 for k 6= j, where (∇fj(Z))·k denotes the kth column of∇fj(Z). We thus have that
EI,|I|=b ‖1 b ∑ j∈I ∇fj(Z)‖2  = 4 b EI,|I|=b 1 b ∑ j∈I ‖Zj − Yj‖2  = 4
b E[fj(Z)]
= 4
b f(Z).
Similarly, we have ‖∇f(Z)‖2 = 4mf(Z). Hence, the quadratic loss satisfies growth condition with ηf = m b .
Suppose there exists some constant t ≥ 1 such that m ' dt0. Using Lemma 2 and Lemma 3, we can estimate the parameters νΦ, µΦ, βΦ and establish an upper bound on h(Θ0):
h(Θ0) ≤ 1 m δ23k 2 1k 2 2σ 2 max(X)
νΦ = max { |c0| √ (1 + δ2)d1m, ω1 √ (1 + δ2)(c21 + c 2 ∞)d1σmax(X) } µΦ = √ (1− δ1)
c2t t! d1σmin(X ∗t)
βΦ = √ 2σmax(X)(φ̇max + σmax(V 0)) + φ̈maxµΦ
2φ̇max
(A.11)
where δ1, δ2, δ3, k1, and k2 are all constants and independent of d0, d1, and m; the term t is a constant such that m ' dt0, and X∗t ∈ Rd t 0×m is derived from Khatri-Rao product with its a-th column defined as vec(xa ⊗ · · · ⊗ xa) ∈ Rd t 0 , with probability at least 1 − ψ̃ where ψ̃ =
d−Cδ4d01 −d −Cδ4d2 1 −e
− (
δ1σmin(E[M 0])
4φ̇2maxσ 2 max(X)δ4 √ d0 log d1 )2 −e − (
δ2σmax(E[M 0])
4φ̇2maxσ 2 max(X)δ4 √ d0 log d1 )2 −e−Cd1−e−Cδ23 ,
δ4 = max(k1, k2), M0 = φ(X>W 0 > )φ(W 0X), C is a constant, and
ω2t1 d1 c2t t! σ2min(X
∗t) . σmin(E[M0]) ≤ σmax(E[M0]) . d1 ( mc20 + ω 2 1(c 2 1 + c 2 ∞)σ 2 max(X) ) .
We denote Cδ = {δ1, δ2, δ3, δ4}. We highlight the main condition for the linear convergence of SGD in (6):
h(Θ0) = O
( αfµ 6 Φ
ζβ2Φηfν 2 Φ
) .
The convergence happens with probability at least 1− 1ζ . Suppose |c0| is sufficiently large such that |c0| √ (1 + δ2)d1m becomes the dominating term in νΦ.1
We note that the order of σmax(X) and σmin(X∗t) play significant roles for the overparameterization order analysis. For t = 1, it requires m ' d0, which is not a common setting in practice. In the following, we focus on t ≥ 2. Substituting the parameters obtained in (A.11) into (6), a sufficient condition to satisfy (6) is given by
d1 & √ ξ(Cδ, t, φ, {ci}i≥0, ζ) ·
mσ2max(X)√ bσ3min(X ∗t) .
where
ξ(Cδ, t, φ, {ci}i≥0, ζ) =
√ ζδ23c 2 0(1 + δ2)ω 4t+4 1 δ 4 4(φ̇max + σmax(V 0))2t!3
(1− δ1)3c6t .
Since ξ(Cδ, t, φ, {ci}i≥0, ζ) is constant w.r.t. d0, d1, andm. The sufficient condition can be expressed as:
d1 = Ω̃( mσ2max(X)√ bσ3min(X ∗t) ). (A.12)
Finally, along the lines of (Oymak & Soltanolkotabi, 2020)[Section 2.1], we have σmax(X) ' √
m d0 and σmin(X∗t) ' √
m dt0 ' 1.
Replacing σmax(X) and σmin(X∗t) into (A.12), the overall overparameterization degree becomes d0d1 ' Ω̃(m2/ √ b).Finally using the union bound on the events corresponding to random initialization and random SGD iterates, the linear convergence is established with probability at least 1− ψ where
ψ = d−Cδ4d01 + d −Cδ4d2 1 + e −Cd1 + e−Cδ 2 3 +
1
ζ + e − ( δ1σmin(E[M 0]) 4φ̇2maxσ 2 max(X)δ4 √ d0 log d1 )2 + e − ( δ2σmax(E[M 0]) 4φ̇2maxσ 2 max(X)δ4 √ d0 log d1 )2 .
(A.13)

heading: D PROOF OF LEMMA 1
text: The content of this proof is originally due to (Anonymous) and provided here for the completeness of our paper.
Intuitively, if ∇Φ∗(w0) is a (µΦ, νΦ)-near-isometry, then one would expect ∇Φ∗ to remain nearisometry for all nearby points. Formally, let A, B ∈ Rm×n and let singular values of a matrix are ordered such that σi(A) ≥ σj(A) and σi(B) ≥ σj(B) for 1 ≤ i ≤ j ≤ min{m,n}. Using Weyl’s inequality and for i+ j − 1 ≤ min{m,n}, we have:
1The same scaling holds if the other term dominates.
σi+j−1(A+B) ≤ σi(A) + σj(B). (A.14)
More formally, suppose that w ∈ Rd satisfies
‖w −w0‖ ≤ µΦ 2βΦ = ρΦ. (A.15)
If∇Φ∗(w0) is (µΦ, νΦ)-isometry in the sense of Definition 4, then applying Weyl’s inequality (A.14) along with using smoothness and (A.15), we have
σmin(∇Φ∗(w)) ≥ σmin(∇Φ∗(w0))− σmax(∇Φ∗(w)−∇Φ∗(w0)) ≥ µΦ − βΦ‖w −w0‖
≥ µΦ 2 .
Using a similar argument, we establish an upper bound σmax(∇Φ∗(w)):
σmax(∇Φ∗(w)) ≤ σmax(∇Φ∗(w0)) + σmax(∇Φ∗(w)−∇Φ∗(w0)) ≤ νΦ + µΦ 2 ≤ 3νΦ 2 .

heading: E PROOF OF LEMMA 2
text: Lemma A.4 (Estimation of h(Θ0), µΦ, νΦ, βΦ (Anonymous)). Suppose that the shallow neural network satisfies Assumption 3. Then we have
h(Θ0) ≤ 1 m δ23k 2 1k 2 2σ 2 max(X)
νΦ = max { |c0| √ (1 + δ2)d1m, ω1 √ (1 + δ2)(c21 + c 2 ∞)d1σmax(X) } µΦ = √ (1− δ1)
c2t t! d1σmin(X ∗t)
βΦ = √ 2σmax(X) ( φ̇max + φ̈maxχmax ) .
(A.16)
where δ1, δ2, δ3, k1, and k2 are all constants and independent of d0, d1, andm; βΦ is the smoothness constant of the map Φ restricted to the set {(V,W ) : σmax(V ) ≤ χmax}; the term t is a constant such that m ' dt0, and X∗t ∈ Rd t 0×m is derived from Khatri-Rao product with its a-th column defined as vec(xa ⊗ · · · ⊗ xa) ∈ Rd t 0 , with probability at least 1 − ψ̃ where ψ̃ = d−Cδ4d01 −
d−Cδ4d21 − e − (
δ1σmin(E[M 0])
4φ̇2maxσ 2 max(X)δ4 √ d0 log d1 )2 − e − (
δ2σmax(E[M 0])
4φ̇2maxσ 2 max(X)δ4 √ d0 log d1 )2 − e−Cd1 − e−Cδ23 , where
δ4 = max(k1, k2), M0 = φ(X>W 0 > )φ(W 0X), C is a constant, and
ω2t1 d1 c2t t! σ2min(X
∗t) . σmin(E[M0]) ≤ σmax(E[M0]) . d1 ( mc20 + ω 2 1(c 2 1 + c 2 ∞)σ 2 max(X) ) ,
. We denote Cδ = {δ1, δ2, δ3, δ4}.
The content of this proof is originally due to (Anonymous) and provided here for the completeness of our paper.
We first obtain the expression for adjoint operator ∇Φ∗(Θ) : Rd2×m → Rd1×d0 × Rd2×d1 . Let ∆W ∈ Rd1×d0 , ∆V ∈ Rd2×d1 , and ∆ ∈ Rd2×m. We expand Φ as follow:
Φ(W + ∆W , V ) ≈ Φ(W,V ) +∇WΦ(∆W ), Φ(W,V + ∆V ) ≈ Φ(W,V ) +∇V Φ(∆V )
(A.17)
where
∇WΦ(∆W ) = V ( φ̇(WX) ∆WX ) , ∇V Φ(∆V ) = ∆V φ(WX),
stands for the Hadamard (entry-wise) product, and φ̇(WX) is the derivative of φ calculated at each entry of the matrix WX . The operator∇Φ(Θ) is given by (∆W ,∆V )→ ∇WΦ(∆W ) +∇V Φ(∆V ).
Using the cyclic property of the trace operator and trace ( (A B)C ) = trace ( (A C>)B> ) , we have
〈∆,∇WΦ(∆W )〉 = 〈( φ̇(WX) V >∆ ) X>,∆W 〉 ,
〈∆,∇V Φ(∆V )〉 = 〈 ∆V ,∆φ ( X>W> )〉 .
(A.18)
Substituting (A.18), the adjoint operator is given by ∇Φ∗(Θ) : ∆→ (( φ̇(WX) V >∆ ) X>,∆φ ( X>W> )) . (A.19)
Suppose that there exist φ̇max, φ̈max <∞ such that
sup a |φ̇(a)| ≤ φ̇max, sup a |φ̈(a)| ≤ φ̈max. (A.20)
Lemma A.5. Let A ∈ Rm×n and B ∈ Rn×k. Then, we have
σmin(A)‖B‖ ≤ ‖AB‖ ≤ σmax(A)‖B‖.
Using Lemma A.5 and triangular inequality, we note that ‖∇Φ∗(Θ,∆)‖ ≤ ∥∥∥(φ̇(WX) (V >∆))X>∥∥∥+ ∥∥∆φ(X>W>)∥∥
≤ φ̇maxσmax(X)σmax(V )‖∆‖+ σmax(φ(WX))‖∆‖. (A.21)
Similarly, we have this lower bound:
‖∇Φ∗(Θ,∆)‖ ≥ σmin(φ(WX))‖∆‖. (A.22)
Substituting Θ0 = (W0, V0) into (A.21) and (A.22), µΦ and νΦ are given by:
σmax(∇Φ∗(Θ0)) ≤ φ̇maxσmax(X)σmax(V0) + σmax(φ(W0X)) =: νΦ, σmin(∇Φ∗(Θ0)) ≥ σmin(φ(W0X)) =: µΦ.
(A.23)
Lemma A.6. Let A ∈ Rm×n and B ∈ Rn×k. Then, for p, q ≥ 1, we have
‖AB‖q ≤ ‖A‖p‖B‖q.
In the following, we find the smoothness parameter βΦ in (1). Let Θ, Θ̂ ∈ Rd1×d0 × Rd2×d1 . We note that ‖∇Φ(Θ,∆)−∇Φ(Θ̂,∆)‖ ≤ U1 + U2 where
U1 = ‖V (φ̇(W>X) (∆>WX))− V̂ (φ̇(Ŵ > X) (∆>WX))‖ U2 = ‖∆V φ(W>X)−∆V φ(Ŵ > X)‖.
(A.24)
Let us denote
σmax(V̂ ) ≤ χmax. (A.25)
An upper bound on U1 in (A.24) is given by:
U1 ≤ ‖(V − V̂ )(φ̇(W>X) (∆>WX))‖+ ‖V̂ (φ̇(W>X) (∆>WX)− V̂ φ̇(Ŵ>X) (∆>WX))‖ ≤ φ̇maxσmax(X)‖V − V̂ ‖‖∆W ‖+ σmax(X)σmax(V̂ )‖φ̇(W>X)− φ̇(Ŵ>X)‖∞‖∆W ‖ ≤ φ̇maxσmax(X)‖V − V̂ ‖‖∆W ‖+ φ̈maxσmax(X)‖X‖∞σmax(V̂ )‖W − Ŵ‖‖∆W ‖ ≤ φ̇maxσmax(X)‖V − V̂ ‖‖∆W ‖+ φ̈maxχmaxσmax(X)‖W − Ŵ‖‖∆W ‖
where the second last inequality is due to Lemma A.6.
An upper bound on U2 in (A.24) is given by:
U2 ≤ φ̇maxσmax(X)‖W − Ŵ‖‖∆V ‖.
Substituting the upper bounds on U1 and U2, an upper bound on σmax(∇Φ(Θ)−∇Φ(Θ̂)) is given by σmax(∇Φ(Θ)−∇Φ(Θ̂)) ≤ σmax(X) ( φ̇max + φ̈maxχmax ) ‖W − Ŵ‖+ σmax(X)φ̇max‖V − V̂ ‖
≤ √ 2σmax(X) ( φ̇max + φ̈maxχmax ) ‖Θ− Θ̂‖
where the last inequality holds since
‖W − Ŵ‖+ ‖V − V̂ ‖ ≤ √ 2 √ ‖W − Ŵ‖2 + ‖V − V̂ ‖2.
Finally, βΦ in (1) is given by
βΦ = √ 2σmax(X) ( φ̇max + φ̈maxχmax ) . (A.26)
E.1 ESTIMATING µΦ, νΦ
We now estimate the random quantities µΦ, νΦ in our neural network setting. They key quantities to estimate are σmin(φ(W 0X)) and σmax(φ(W 0X)). To that end, we consider Hermite decomposition of the activation function φ.
We start with the basic definition of Hermite polynomial and its properties. Let i ≥ 0 and let qi : R → R denote the i-th Hermite polynomial. Note that qi’s form an orthogonal basis for the Hilbert space of functions.:
H = { u : R→ R | ∫ u2(x) exp ( −x 2
2
) <∞ } ,
which is equipped with the inner product
〈u, v〉H = 1√ 2π
∫ u(x)v(x) exp ( −x 2
2
) dx
for u, v ∈ H. We consider probabilist’s convention of Hermite polynomial. Specifically, for i, j ≥ 0, we have
〈qi, qj〉H = { i! i = j,
0 i 6= j. (A.27)
Using the above orthogonal basis to decompose φ(W 0X), we have
φ(W 0X) = ∞∑ i=0 ci i! · qi(W 0X) (A.28)
where ci = 〈φ, qi〉H and each matrix qi(W0X) ∈ Rd1×m is formed by applying qi entry-wise to the matrix W 0X . Let us denote
M0 := φ(X>W 0 > )φ(W 0X).
In the following, we first obtain E[M̃0] = E[φ(X>W̃ 0>)φ(W̃ 0X)] with W̃ 0 ∼ N (0, 1) and then obtain a lower bound on σmin(E[M0]) and an upper bound on σmin(E[M0]) by appropriately scaling the data matrix X .
Applying Hermite decomposition (A.28) and taking expectation, we have E[M̃0] = E [ φ(X>W̃ 0 > )φ(W̃ 0X) ] =
∞∑ i,j=0 cicj i!j! E[qi(X>W̃ 0 > )qj(W̃ 0X)]
(A.29)
where the expectation is w.r.t. the random matrix W̃0. Let xa ∈ Rd0 denote the a-th column of the training data X . Each summand in (A.29) is an m×m matrix where[
E[qi(X>W̃ 0 > )qj(W̃ 0X)] ] a,b = d1∑ c=1 E [ qi(x > a W̃0,c,→)qj(W̃ > 0,c,→xb) ] , (A.30)
where W̃0,c,→ is the c-th row of W̃ 0 for a, b ∈ [m].
In summand on the RHS of (A.30), we note that there is a linear combination of W̃ 0’s elements inside of each Hermite polynomial.
We use the properties of Hermite polynomials (Olver et al., 2010)[§18.18.11]:
(a21 + · · ·+ a2r) i 2 i! q̃i (a1x1 + · · ·+ arxr
(a21 + · · ·+ a2r) 1 2
) = ∑
s1+···+sr=i
as11 · · · asrr s1! · · · sr! q̃s1(x1) · · · q̃sr (xr) (A.31)
where q̃i’s form an orthogonal basis, equipped with the inner product 〈u, v〉H̃ = 1√ π ∫ u(x)v(x) exp(−x2) dx. This basis follows the physicist’s convention of Hermite polynomial.
Since q̃i and qi are rescalings of the other, we can replace qi’s into (A.31). Note that we have ‖xa‖2 = 1 for all a ∈ [n]. Then we have
qi(x > a W̃0,c,→) = i! ∑ s1+···+sd0=i xs1a,1 · · ·x sd0 a,d0 s1! · · · sd0 ! qs1(W̃0,c,1) · · · qsd0 (W̃0,c,d0) (A.32)
where xa,k and W̃0,c,k are k-th entry of xa and W̃0,c,→ for k ∈ [d0]. Using the expansion in (A.32), we expand (A.30) as follows:
ζi,j(a, b) = i!j! ∑
s1+···+sd0=i ∑ s′1+···+s′d0=j xs1a,1 · · ·x sd0 a,d0 s1! · · · sd0 ! · x s′1 b,1 · · ·x s′d0 b,d0 s′1! · · · s′d0 ! ρs,s′(W̃0,c,→)
=
{ (i!)2 ∑ s1+···+sd0=i (xa,1xb,1) s1 ···(xa,d0xb,d0 ) sd0 s1!···sd0 ! i = j,
0 i 6= j
=
{ i! ∑ s1+···+sd0=i ( i s1,··· ,sd0 ) (xa,1xb,1)
s1 · · · (xa,d0xb,d0)sd0 i = j, 0 i 6= j
(A.33)
where ζi,j(a, b) = E [ qi(x > a W̃0,c,→)qj(W̃ > 0,c,→xb) ] ,
ρs,s′(W̃0,c,→) = E [ qs1(W̃0,c,1) · · · qsd0 (W̃0,c,d0) · qs′1(W̃0,c,1) · · · qs′d0 (W̃0,c,d0) ] ,
s = [s1, · · · , sd0 ], and s′ = [s′1, · · · , s′d0 ].
To simplify the expression in (A.33), we define X∗i ∈ Rdi0×m where the a-th column is given by
X∗ia = vec(xa ⊗ · · · ⊗ xa) ∈ Rd i 0 ,
which is also called Khatri-Rao product. For i = 0, we use the convention thatX∗0 = 11> ∈ Rm×m. We can rewrite (A.33) as follows:
ζi,j(a, b) = { i!〈X∗ia , X∗ib 〉 i = j 0 i 6= j. (A.34)
Substituting (A.34) back into (A.30), we find that[ E[qi(X>W̃ 0 > )qj(W̃ 0X)] ] a,b = d1∑ c=1 E [ qi(x > a W̃0,c,→)qj(W̃ > 0,c,→xb) ] = { d1i!〈X∗ia , X∗ib 〉 i = j 0 i 6= j.
(A.35)
Substituting (A.35) into (A.29), we have
E [ M̃0 ]
= d1 ( c2011 > + c21X >X + ∞∑ i=2 c2i i! (X∗i)>X∗i ) . (A.36)
We now establish an upper bound on σmax (∑∞ i=2 c2i i! (X ∗i)>X∗i ) :
σmax ( ∞∑ i=2 c2i i! (X∗i)>X∗i ) ≤ ∞∑ i=2 c2i i! σmax((X ∗i)>X∗i)
≤ c2∞σ2max(X)
(A.37)
where c∞ is given by
c2∞ = ∞∑ i=2 c2i i! ,
which is finite provided that ‖φ‖H is bounded.
Using (A.37), we now establish an upper bound on σmax(E[M̃0]): σmax(E[M̃0]) . d1 ( mc20 + (c 2 1 + c 2 ∞)σ 2 max(X) ) Moreover, suppose there exists some t such that σmin(X∗t) > 0. Then we have d1 c2t t! σ 2 min(X
∗t) . σmin(E[M0]). This requires to have dt0 ≥ m. Putting together the lower bound on σmin(E[M̃0]) and the upper bound on σmin(E[M̃0]), noting W 0 = ω1W̃ 0, and scaling X accordingly to take into account the coefficient ω1, we have
ω2t1 d1 c2t t! σ2min(X
∗t) . σmin(E[M0]) ≤ σmax(E[M0]) . d1 ( mc20 + ω 2 1(c 2 1 + c 2 ∞)σ 2 max(X) ) .
(A.38)
E.2 CONCENTRATION OF THE RANDOM MATRIX M0
To see how well the random matrix M0 concentrates about its expectation, note that
M0 = φ(X>W 0 > )φ(W 0X)
= d1∑ i=1 φ(X>W>0,i,→)φ(W0,i,→X)
= d1∑ i=1 Ai
(A.39)
where {Ai}d1i=1 ⊂ Rm×m are independent random matrices. Consider the event E1 that
max i∈[d1]
‖W0,i,→‖2 . k1ω1 √ d0 log d1, max
i∈[d1] ‖V0,i,↓‖2 . k2ω2
√ d2 log d1 (A.40)
where V0,i,↓ is the i-th column of V0. Note that W0,i,→ ∈ Rd0 and V0,i,↓ ∈ Rd2 are random zeromean Gaussian vectors whose entries’ variances are ω21 and ω 2 2 , respectively. Therefore, with an application of the scalar Bernstein inequality (Vershynin, 2012, Proposition 5.16), followed by the union bound, we observe that the event E1 happens except with a probability of at most
p1 := d −Ck1d0 1 + d −Ck2d2 1 , (A.41)
for a universal constant C with sufficiently large k1, k2.
Let i ∈ [d1]. Conditioned on the event E1, an upper bound on ‖φ(X>W0,i,→)‖2 is given by:
‖φ(X>W0,i,→)‖2 . φ̇maxσmax(X)k1ω1 √ d0 log d1. (A.42)
Moreover, we have
σmax(Ai) = ‖φ(X>W0,i,→)‖22 = ‖φ(X>W0,i,→)− φ(0)‖22 . φ̇2maxσ 2 max(X)k 2 1ω 2 1d0 log d1.
(A.43)
We now focus on the concentration of σmin(M0) and σmax(M0). We use a concentration property, which provides the tail bound of f̃(W ) = φ(X>W>)φ(WX) with multivariate Gaussian input W . In the following lemma, we show that f̃ is a Lipschitz function, and its Lipschitz constant explains how f̃(W ) concentrates around its mean.
Lemma A.7. Let f̃(W ) = φ(X>W>)φ(WX). Suppose W satisfies (A.40). Then f̃ is κ-Lipschitz function with constant κ = 4φ̇2maxσ 2 max(X)k1ω1 √ d0 log d1. So we have
‖f̃(W )− f̃(W ′)‖ < 4φ̇2maxσ2max(X)k1ω1 √ d0 log d1 · ‖W −W ′‖.
Proof. Note that f̃(W 0) = M0 and f̃ can be represented as
f̃(X) = d1∑ i=1 fi(Wi,→)
where fi is given by fi(Wi,→) = φ(X>W>i,→)φ(Wi,→X). We prove that each fi is κ-Lipschitz, which implies that f̃ is also κ-Lipschitz.
We note that fi’s can be expressed as a composition of three functions:
fi(v) = (g1 ◦ g2 ◦ g3)(v)
where g1, g2, and g3 are given by
g1(v) = vv >, f2(v) = φ(v), f3(v) = vX. (A.44)
It is clear that g2 is φ̇max-Lipschitz, and g3 is σmax(X)-Lipschitz from their definitions. Lipschitz constant of g1 comes from the domain bound as follows:
‖g1(v + δv)− g1(v)‖ = ‖δvv> + vδv> + δvδv>‖ ≤ 2‖δvv>‖+ ‖δvδv>‖ ≤ (2‖v‖+ ‖δv‖) · ‖δv‖.
(A.45)
A bound on (2‖v‖ + ‖δv‖) is obtained in (A.42). Then g1 is κ1-Lipschitz function with κ1 = 4φ̇maxσmax(X)k1ω1 √ d0 log d1. Therefore, all g1, g2 and g3 are Lipschitz function, so their composition fi is also Lipschitz function with constant κ = 4φ̇2maxσ 2 max(X)k1ω1 √ d0 log d1, which completes the proof.
Lemma A.8. Let z ∈ Rd denote a Gaussian random vector. Then we have Pr{‖z − E[z]‖ > t |E2} . exp(−t2) where E2 is the event that ‖z‖ is bounded.
We can focus on the tail distribution of M0 = f̃(W0). Using Lemmas A.7 and A.8, we have
Pr{‖M0 − E[M0]‖ > t |E1} . exp(−k23) (A.46)
where t = k34φ̇2maxσ 2 max(X)k1ω1 √ d0 log d1 with some constant k3.
Using (A.46), we now establish a tail bound on σmin(M0):
Pr{σmin(M0) ≤ (1− δ1)σmin(E[M0])|E1} ≤ Pr{|σmin(M0)− σmin(E[M0])| ≥ δ1σmin(E[M0])|E1} ≤ Pr{σmin(M0 − E[M0]) ≥ δ1σmin(E[M0])|E1} ≤ Pr{σmax(M0 − E[M0]) ≥ δ1σmin(E[M0])|E1} ≤ Pr{‖M0 − E[M0]‖ ≥ δ1σmin(E[M0])|E1} . p2
where
p2 = exp
( − (
δ1σmin(E[M0]) 4φ̇2maxσ 2 max(X)k1ω1 √ d0 log d1
)2) .
Similarly, we obtain
Pr{σmax(M0) ≥ (1 + δ2)σmax(E[M0])|E1} . p3 where
p3 = exp
( − (
δ2σmax(E[M0]) 4φ̇2maxσ 2 max(X)k1ω1 √ d0 log d1
)2) .
Putting these bounds together with (A.38), we have :
ωt1 √ (1− δ1)
c2t t! d1σmin(X ∗t) ≤ σmin(φ(W 0X))
σmax(φ(W 0X)) ≤ √ (1 + δ2)(ω1 √ (c21 + c 2 ∞)d1σmax(X) + |c0| √ d1m) (A.47)
except with a probability of at most p1 + p2 + p3.
With establishing the bounds on σmin(φ(W 0X)) and σmax(φ(W 0X)), we can finally estimate µΦ, νΦ as follows:
E.3 LOWER BOUND ON µΦ
A lower bound on µΦ is given by
ωt1 √ (1− δ1)
c2t t! d1σmin(X ∗t) ≤ σmin(φ(W 0X)) = µΦ, (A.48)
except with a probability of at most p1 + p2.
E.4 UPPER BOUND ON νΦ
Since νΦ = φ̇maxσmax(X)σmax(V 0) + σmax(φ(W 0X)), we obtain a bound on σmax(V 0):
Since V 0 is a Gaussian random matrix, we have
σmax(V 0) ≤ ω2(2 √ d1 + √ d2) . ω2 √ d1 (A.49)
except with a probability of at most p4 = exp(−Cd1) where C is a universal constant (Vershynin, 2012)[Corollary 5.35].
Combining (A.49) with the upper bound on σmax(φ(W 0X)), we have
νΦ = φ̇maxσmax(X)σmax(V 0) + σmax(φ(W0X)) . ω2φ̇maxσmax(X) √ d1 + ω1 √ (1 + δ2)(c21 + c 2 ∞)d1σmax(X) + c0 √ (1 + δ2)d1m
except with a probability of at most p1 + p3 + p4.
E.5 UPPER BOUND ON h(Θ0)
In this section, we bound h(Θ0). Using ‖a + b‖22 ≤ 2‖a‖22 + 2‖b‖22, we have
h(Θ0) = 1
m ‖V 0φ(W 0X)− Y ‖2 ≤ 2 m ‖V 0φ(W 0X)‖2 + 2 m ‖Y ‖2.
(A.50)
To upper bound the random norm in (A.50), we first decompose V 0φ(W 0X) into terms including W0,i,→ ∈ Rd0 and V0,i,↓ ∈ Rd2 as follows:
V 0φ(W 0X) = d1∑ i=1 Bi (A.51)
where Bi = V0,i,↓φ(W>0,i,→X) ∈ Rd2×m’s are independent random matrices for i ∈ [d1].
Conditioned on the event E1 defined in (A.40), we bound ‖Bi‖:
‖Bi‖ = ‖V0,i,↓‖2‖φ(W>0,i,→X)‖2 ≤ ‖V0,i,↓‖2 · φ̇maxσmax(X)k1ω1 √ d0 log d1
≤ ω1ω2φ̇maxσmax(X)k1k2 √ d0d2 log d1
(A.52)
for i ≤ d1. Substituting the upper bound in A.51 into A.52 and applying the Hoeffding inequality (Hoeffding, 1963), we have
Pr{‖V 0φ(W 0X)‖ & u(d0, d1, d2)|E1} = Pr{‖V 0φ(W 0X)− E[V 0φ(W 0X))|E1]‖ & u(d0, d1, d2)|E1}
≤ Pr { d1∑ i=1 ‖Bi − E[Bi]‖ & u(d0, d1, d2)|E1 } ≤ p5
where
u(d0, d1, d2) = δ3ω1ω2φ̇maxk1k2 √ d0d1d2σmax(X) log d1
and p5 = exp(−Cδ23) with δ3 ≥ 0 and a universal constant C. Therefore, under the event E1, we have
h(Θ0) ≤ 2 m ‖V 0φ(W 0X)‖2 + 2 m ‖Y ‖2
. 1
m δ23ω 2 1ω 2 2φ̇ 2 maxk 2 1k 2 2d0d1d2σ 2 max(X) log
2 d1 + 1
m ‖Y ‖2
(A.53)
except with a probability of at most p1 + p5. It is natural to assume that d2 = o(d1). We also have ‖Y ‖ ≤ 1. Suppose that
ω1ω2 . 1
φ̇max √ d0d1 log d1 . (A.54)
Substituting (A.54) into (A.53), we have
h(Θ0) ≤ 1 m δ23k 2 1k 2 2σ 2 max(X) (A.55)
where δ3, k1, and k2 are all constants and independent of d0, d1, and m.

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

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.