ING OF OVERPARAMETRIZED NEURAL NETS
Year: 2020

Abstract:
It is well-known that overparametrized neural networks trained using gradientbased methods quickly achieve small training error with appropriate hyperparameter settings. Recent papers have proved this statement theoretically for highly overparametrized networks under reasonable assumptions. These results either assume that the activation function is ReLU or they depend on the minimum eigenvalue of a certain Gram matrix. In the latter case, existing works only prove that this minimum eigenvalue is non-zero and do not provide quantitative bounds which require that this eigenvalue be large. Empirically, a number of alternative activation functions have been proposed which tend to perform better than ReLU at least in some settings but no clear understanding has emerged. This state of affairs underscores the importance of theoretically understanding the impact of activation functions on training. In the present paper, we provide theoretical results about the effect of activation function on the training of highly overparametrized 2-layer neural networks. A crucial property that governs the performance of an activation is whether or not it is smooth: • For non-smooth activations such as ReLU,SELU,ELU, which are not smooth because there is a point where either the first order or second order derivative is discontinuous, all eigenvalues of the associated Gram matrix are large under minimal assumptions on the data. • For smooth activations such as tanh, swish, polynomial, which have derivatives of all orders at all points, the situation is more complex: if the subspace spanned by the data has small dimension then the minimum eigenvalue of the Gram matrix can be small leading to slow training. But if the dimension is large and the data satisfies another mild condition, then the eigenvalues are large. If we allow deep networks, then the small data dimension is not a limitation provided that the depth is sufficient. We discuss a number of extensions and applications of these results.

text: • For non-smooth activations such as ReLU,SELU,ELU, which are not smooth because there is a point where either the first order or second order derivative is discontinuous, all eigenvalues of the associated Gram matrix are large under minimal assumptions on the data.
• For smooth activations such as tanh, swish, polynomial, which have derivatives of all orders at all points, the situation is more complex: if the subspace spanned by the data has small dimension then the minimum eigenvalue of the Gram matrix can be small leading to slow training. But if the dimension is large and the data satisfies another mild condition, then the eigenvalues are large. If we allow deep networks, then the small data dimension is not a limitation provided that the depth is sufficient.
We discuss a number of extensions and applications of these results.

heading: 1 INTRODUCTION
text: It is now well-known that overparametrized feedforward neural networks trained using gradient-based algorithms with appropriate hyperparameter choices reliably achieve near-zero training error, e.g., Neyshabur et al. (2015). Importantly, overparametrization also often helps with generalization; but our central concern here is the training error which is an important component in understanding generalization. We study the effect of the choice of activation function (we often just say activation) on the training of overparametrized neural networks. By overparametrized setting we roughly mean that the number of parameters or weights in the networks is much larger than the number of data samples.
The well-known universal approximation theorem for feedforward neural networks states that any continuous function on a bounded domain can be approximated arbitrarily well by a finite neural network with one hidden layer. This theorem is generally stated for specific activation functions such as sigmoid or ReLU. A more general form of the theorem shows this for essentially all nonpolynomial activations (Leshno et al., 1993; Pinkus, 1999; Sonoda & Murata, 2017). This theorem
∗Work done when the author was at Microsoft Research India.
concerns only the expressive power and does not address how the training and generalization of neural networks are affected by the choice of activation, nor does it provide quantitative information about the size of the network needed for the task.
Traditionally, sigmoid and tanh had been the popular activations but a number of other activations have also been considered including linear and polynomial activations (Arora et al., 2019a; Du & Lee, 2018; Kileel et al., 2019). One of the many innovations in the resurgence of neural networks in the last decade or so has been the realization that ReLU activation generally performs better than the traditional choices in terms of training and generalization. ReLU is now the de facto standard for activation functions for neural networks but many other activations are also used which may be advantageous depending on the situation (e.g. (Goodfellow et al., 2016, Chapter 6)). In practice, most activation functions often achieve reasonable performance. To quote Goodfellow et al. (2016): In general, a wide variety of differentiable functions perform perfectly well. Many unpublished activation functions perform just as well as the popular ones. Concretely, Ramachandran et al. (2018) provides a list of ten non-standard functions which all perform close to the state of the art at some tasks. This hints at the possibility of a universality phenomenon for training neural networks similar to the one for expressive power mentioned above.
Search for activation functions. A number of recent papers have proposed new activations—such as ELU, SELU, penalized tanh, SiLU/swish—based on either theoretical considerations or automated search using reinforcement learning and other methods; e.g. Clevert et al. (2016); Klambauer et al. (2017); Xu et al. (2016); Elfwing et al. (2017); Ramachandran et al. (2018). For definitions, see Section 2 and Appendix B. These activation functions have been found to be superior to ReLU in many settings. See e.g. Eger et al. (2018); Nwankpa et al. (2018) for overview and evaluation. We quote once more from Goodfellow et al. (2016): The design of hidden units is an extremely active area of research and does not yet have many definitive guiding theoretical principles.
Theoretical analysis of training of highly overparametrized neural networks. Theoretical analysis of neural network training has seen vigorous activity of late and significant progress was made for the case of highly overparametrized networks. At a high level, the main insight in these works is that when the network is large, small changes in weights can already allow the network to fit the data. And yet, since the weights change very little, the training dynamics approximately behaves as in kernel methods and hence can be analyzed (e.g. Jacot et al. (2018); Li & Liang (2018); Du et al. (2019a); Allen-Zhu et al. (2019); Du et al. (2019b); Allen-Zhu et al. (2018); Arora et al. (2019c); Oymak & Soltanolkotabi (2019)). There are also many other approaches for theoretical analysis, e.g. Brutzkus et al. (2018); Mei et al. (2018); Chizat & Bach (2018). Because of the large number of papers on this topic, we have chosen to list only the most closely related ones.
Analyses in many of these papers involve a matrix G, either explicitly (Jacot et al., 2018; Du et al., 2019a;b) or implicitly (Allen-Zhu et al., 2019). (This matrix also occurs in earlier works (Xie et al., 2017; Tsuchida et al., 2018).) λmin(G), the minimum eigenvalue of G, is an important parameter that directly controls the rate of convergence of gradient descent training: the higher the minimum eigenvalue the faster the convergence. Jacot et al. (2018); Du et al. (2019b) show that λmin(G) > 0 for certain activations assuming that no two data points are parallel. Unfortunately, these results do not provide any quantitative information. The result of Allen-Zhu et al. (2019), where the matrix G does not occur explicitly, can be interpreted as showing that the minimum eigenvalue is large under the reasonable assumption that the data is δ-separated, meaning roughly that no two data points are very close, and the activation used is ReLU. This quantitative lower bound on the minimum eigenvalue implies fast convergence of training. So far, ReLU was the only activation for which such a proof was known.
Our results in brief. A general result one could hope for is that based on general characteristics of the activations, such as smoothness, convexity etc., one can determine whether the smallest eigenvalue of G is small or large. We prove results of this type. A crucial distinction turns out to be whether the activation is (a) not smooth (informally, has a “kink”) or (b) is smooth (i.e. derivatives of all orders exist over R). The two classes of functions above seem to cover all “reasonable” activations; in particular, to our knowledge, all functions used in practice seem to fall in one of the two classes above. • Activations with a kink, i.e., those with a a jump discontinuity in the derivative of some constant
order, have all eigenvalues large under minimal assumptions on the data. E.g., the first derivatives of ReLU and SELU, the second derivative of ELU have jump discontinuities at 0. These results
imply that for such activations, training will be rapid. We also provide a new proof for ReLU with the best known lower bound on the minimum eigenvalue.
• For smooth activations such as polynomials, tanh and swish the situation is more complex: the minimum eigenvalue can be small depending on the dimension of the span of the dataset. We give a few examples: Let n be size of the dataset which is a collection of points in Rd, and let d′ be the dimension of the span of the dataset. For quadratic activation, if d′ = O( √ n), then the minimum
singular value is 0. For tanh and swish, if d′ = O(log0.75 n), then the minimum eigenvalue is inverse superpolynomially small (exp(−Ω(n1/2d′))). In fact, a significant fraction of eigenvalues can be small. This implies that for such datasets, training using smooth activations will be slow if the dimension of the dataset is small. A trade off is possible: assuming stronger bounds on the dimension of the span gives stronger bounds on the eigenvalues. We also show that these results are tight in a precise sense. We further show that the above limitation of smooth activations disappears if one allows sufficiently deep networks.
Unless otherwise stated, we work with one hidden layer neural nets where only the input layer is trained. This choice is made to simplify exposition; extensions of various types including the ones that drop the above restriction are possible and discussed in Section 5.

heading: 2 PRELIMINARIES
text: Denote the unit sphere in Rn by Sn−1 := { u ∈ Rn :‖u‖2 = 1 } where‖u‖2 :=‖u‖22 := ∑n i=1 u 2 i .
For u, v ∈ Rn, define the standard inner product by 〈u, v〉 := ∑ i uivi. Given a set S, denote by U (S) the uniform distribution over S. N (µ, σ2) denotes the univariate normal distribution with mean µ and variance σ2. Let IS denote the indicator of the set S. For a matrix A containing elements aij , ai denotes its i-th column. We define some of the popular non-traditional activation functions here: swish(x) := x1+e−x (Ramachandran et al., 2018) (called SiLU in Elfwing et al. (2017)); ELU(x) := max (x, 0) + min (x, 0) (ex − 1) (Clevert et al., 2016); SELU(x) := α1 max (x, 0) + α2 min (x, 0) (e
x − 1), where α1 and α2 are two different constants (Klambauer et al., 2017). See Appendix B for more definitions.
We consider 2-layer neural networks
F (x;a,W) := cφ√ m m∑ k=1 akφ ( wTk x ) , (1)
where x ∈ Rd is the input and W = [w1, . . . ,wm] ∈ Rm×d is the hidden layer weight matrix and a ∈ Rm is the output layer weight vector. Activation function φ : R → R acts entrywise on vectors and c2φ := Ez∈N (0,1)φ(z)2. In the case of one hidden layer nets, we set cφ = 1 to simplify expressions; this is without loss of generality. For deeper networks we do not do this as this assumption would result in loss of generality. Elements of W and a have been initialized i.i.d. from the standard Gaussian distribution. This initialization and the parametrization in Equation 1 are from Du et al. (2019b). Together, these will be referred to as the DZPS setting. Parametrization in practice does not have cφ√
m in Equation 1; standard initializations in practice include He (He et al.,
2015) and Glorot initializations (Glorot & Bengio, 2010) and variants. In the DZPS setting, the argument of the activation can be larger compared to the standard initializations, making the analysis harder. Our theorems apply to the DZPS setting as well as to standard initializations and for the latter easily follow as corollaries to the analysis in the DZPS setting. We defer this discussion to the appendix. Unless otherwise stated, we work in the DZPS setting with one hidden layer neural nets with initialization as above with only the input layer trained.
Given labeled input data {(xi, yi)}ni=1, where xi ∈ Rd and yi ∈ R, we want to find the best fit weights W so that the quadratic loss L({(xi, yi)}ni=1;a,W) := 12 ∑n i=1(yi − F (xi;a,W))2 is minimized. We train the neural network by fixing the output weight vector a at random initialization and training the hidden layer weight matrix W (output layer being trained can be easily handled as in Du et al. (2019a;b); See Appendix M for details). In this paper, we focus on the gradient descent algorithm for this purpose. The gradient descent update rule for W is given by W(t+1) := W(t)− η∇WL(W(t)), where W(t) denotes the weight matrix after t steps of gradient descent and η > 0 is the learning rate. The output vector u(t) ∈ Rn is defined by u(t)i := F (xi;a,W(t)).
Next, we define the matrix alluded to earlier, the Gradient Gram matrix G ∈ Rn×n associated with the neural network defined in (1), referred to as the G-matrix in the sequel:
gi,j := 1
m ∑ k∈[m] a2k φ ′(wTk xi)φ ′(wTk xj)〈xi,xj〉. (2)
We will often work with the related matrix M ∈ Rmd×n, whose i-th column is obtained by vectorizing ∇WF(xi, yi), i.e., Md(k−1)+1:dk,i := akφ′ ( wTk xi ) xi for k ∈ [m]. G is a Gram matrix: G =
1 mM TM. Denote by λi(G) the i-th eigenvalue of G with λ1 ≥ λ2 ≥ . . ., and similarly by σi(M) the i-th singular value of M. These quantities are related by λi(G) = 1mσ 2 i (M).
Following Allen-Zhu et al. (2019), we make the following mild assumptions on data. Assumption 1. ‖xi‖2 = 1 ∀i ∈ [n]. Assumption 2. ‖(In − xixTi )xj‖2 ≥ δ ∀i, j ∈ [n], i 6= j i.e., the distance between the subspaces spanned by xi and xj is at least δ > 0.
Assumption 1 can be easily satisfied by the following preprocessing: renormalize each xi so that ‖xi‖ ≤ 1/ √ 2, add another coordinate to each xi so that ‖xi‖ = 1/ √ 2 and then add another
coordinate with value 1/ √
2 to each xi. This ensures that ‖xi − xj‖2 ≥ δ implies Assumption 2 for xi,xj , which we later verify empirically for CIFAR10.

heading: 3 REVIEW OF RELEVANT PRIOR WORK
text: To motivate the importance of the G-matrix, let us first consider the continuous time gradient flow dynamics Ẇ(t) = −∇WL(W(t)), where L(W) denotes the loss function (in the notation we suppressed dependence on data and the weights of the output layer) and Ẇ denotes the derivative with respect to t. Let y ∈ Rn be the vector of outputs. It follows from an application of the chain rule that u̇(t) = G(t)(y − u(t)). Here g(t)i,j := 1m 〈 xi,xj 〉∑m k=1 φ ′(w (t)T k xj)φ ′(w (t)T k xi). It can be shown that as m→∞, the matrix G(t) remains close to its initial value G(0) which is exactly the G-matrix (see e.g. Jacot et al. (2018); Arora et al. (2019b) for closely related results). This leads us to the approximate solution, which upon diagonalizing the PSD matrix G(0) is given by
y − u(t) = ∑ i∈[n] (e−λitviv T i )(y − u(0)). (3)
Thus, it can be seen that the eigenvalues of the G-matrix, in particular λmin(G(0)), control the rate of change of the output of the neural network towards the true labels. The following result plays a central role in the present paper. Theorem 3.1 (Theorem 4.1 of Du et al. (2019a)). Let φ be ReLU. Define matrix G∞ as G∞ := Ew∼N (0,Id) IwTxi≥0,wTxj≥0 〈 xi,xj 〉 . Assume λ = λmin (G∞) > 0. If we set
m ≥ Ω ( n6λ−4κ−3 ) and η ≤ O ( λn−3 ) and initialize wk ∼ N (0, Id) and ak ∼ U {−1,+1} for k ∈ [m], then with probability at least 1− κ over the random initialization, for t ≥ 1 we have ‖y − u(t)‖22 ≤ (1− 0.5ηλ) t ‖y − u(0)‖22.
In the theorem above it can be seen that the time required to reach a desired amount of error is inversely proportional to λ. Du et al. (2019b) extended the above result to general real-analytic functions. While the definition of the G-matrix shows that it is positive semidefinite, it is not immediately clear that the matrix is non-singular. But the following theorem, from Du et al. (2019b) says that the matrix is indeed non-singular under very weak assumptions on the data and activation function. A similar result for the limit m→∞ but for more general non-polynomial Lipschitz activations was shown in Jacot et al. (2018) using techniques from Daniely et al. (2016). Lemma 3.2 (Lemma F.1 in Du et al. (2019b)). If φ is a non-polynomial analytic function and xi and xj are not parallel for distinct i, j ∈ [n], then λmin (G∞) > 0.
In these papers the number of neurons required and the rate of convergence depend on λmin(G∞) (e.g. Theorem 3.1 above) and thus it is necessary for the matrix to have large minimum singular value for their analysis to give useful quantitative bounds. Unfortunately, these papers do not provide quantitative lower bound for λmin (G∞).
Allen-Zhu et al. (2019) considered L-layer networks using ReLU (see Appendix D for details on their parametrization). A major step in their analysis is a lower bound on the gradient norm at each step.
Theorem 3.3 (Theorem 3 in Allen-Zhu et al. (2019)). With probability at least 1 − exp(−Ω(m/poly(n, 1δ ))) with respect to the initialization, for every W such that ‖W−W
(0)‖F ≤ 1/poly(n,δ−1), we have ‖∇WL (W) ‖2F ≥ Ω(L(W)mδd−1n−2).
We show that λmin (G) is directly related to the lower bound on the gradient in the case of ReLU. It is not clear if the same method can be extended to other activation functions.
With this in mind, we aim to characterize the minimum eigenvalue of Gram matrix G∞. Since, G∞ is the same matrix as G(0) in the limit m→∞, we will focus on proving high probability bounds for eigenvalues of G(0).

heading: 4 MAIN RESULTS

heading: 4.1 ACTIVATIONS WITH A KINK
text: For any positive integer constant r, presence of a jump discontinuity in the r-th derivative of the activation leads to a large lower bound on the minimum eigenvalue. The activation function has the form φ(x) = φ1(x) Ix<α + φ2(x) Ix≥α, where −1 ≤ α ≤ 1. Recall that Cr+1 denotes the set of r + 1 times continuously differentiable functions. We need φ1 and φ2 to satisfy the following set of conditions parametrized by r and denoted Jr:
• φ1, φ2 ∈ Cr+1 in the domains (−∞, α] and [α,∞), respectively. • The first (r + 1) derivatives of φ1 and φ2 are upper bounded in magnitude by 1 in (−∞, α]
and [α,∞) respectively.
• For 0 ≤ i < r, we have φ(i)1 (α) = φ (i) 2 (α).
• |φ(r)1 (α)− φ (r) 2 (α)| = 1, i.e., the r-th derivative has a jump discontinuity at α.
Remark. We fix the constants in Jr to 1 for simplicity. We could easily parameterize these constants and make explicit the dependence of our bounds on these parameters. The requirement on the boundedness of derivatives is also not essential and can be relaxed as “all the action happens” in the interval [−O( √ logm), O( √ logm)].
J1 covers activations such as ReLU, SELU and LReLU, while J2 covers activations such as ELU. Below we state the bound explicitly for J2. Similar results hold for Jr for r ≥ 1. See Section K for details.
Theorem 4.1 (J2 activations). : If the activation φ satisfies J2 then we have
λmin(G (0)) ≥ Ω(δ3n−7(log n)−1),
with probability at least 1 − e−Ω(δm/n2) with respect to {w(0)k }mk=1 and {a (0) k }mk=1, given that m > max(Ω(n3δ−1 log(nδ−1)),Ω(n2δ−1 log d)).
The theorem above shows that the presence of a jump discontinuity in the derivative of activation function (or one of its higher derivatives) leads to fast training of the neural network. For the special case of ReLU we give a new proof. To our knowledge, lower bound on the minimum eigenvalue of the G-matrix below is the best known. The proof technique uses Hermite polynomials and is motivated by our results for smooth activations in the next section. See Section L for details.
Theorem 4.2. If the activation is ReLU and m ≥ Ω̃(n4δ−3 log4 n), then λmin(G(0)) ≥ Ω((δ1.5 log−1.5 n), with probability at least 1− e−Ω̃(mδ3n−2 log−3 n).
The dependence on n in the above bound is inverse-polylogarithmic as opposed to inverse-polynomial that seems to result from using the technique of Allen-Zhu et al. (2019). It implies that with m = Ω̃(n6/δ6) in poly(log(n/ ), 1/δ) steps gradient descent training achieves error less than .

heading: 4.2 SMOOTH ACTIVATIONS
text: In contrast to activations with a kink, the situation is more complex for smooth activations and we can divide the results into positive and negative.
Negative results for smooth activations. The G-matrix of constant degree polynomial activations, such as quadratic activation, must have many zero eigenvalues; and of sufficiently smooth activations, such as tanh or swish, must have many small eigenvalues, if the dimension of the span of data is sufficiently small:
Theorem 4.3 (restatement of Theorem F.2). Let the activation be a degree-p polynomial such that φ′(x) = ∑p−1 l=0 c`x
` and let d′ = dim(span{x1 . . .xn}) = O(n1/p). Then we have λmin(G(0)) = 0. Furthermore, λk = 0, for k ≥ dn/d′e. Theorem 4.4 (restatement of Theorem F.10). Let the activation function be tanh and let d′ = dim(span{x1 . . .xn}) = O(log0.75 n). Then we have λmin(G(0)) ≤ exp(−Ω(n1/2d ′ )), with probability at least 1 − 1/n3.5 over the random choice of weight vectors {w(0)k }mk=1 and {a (0) k }mk=1. Furthermore, the same upper bound is satisfied by λk, for k ≥ dn/d′e.
See Appendix F for proofs. Note that the bounds above do not make any assumption on the data other than the dimension of its span. The proof technique generalizes to give similar results for general classes of smooth activation such as swish (Section 6 and Appendix H). In contrast to the above result, the average eigenvalue of the G-matrix for all reasonable activation functions is large:
Theorem 4.5 (informal version of Theorem E.1). Let φ be a non-constant activation function, with Lipschitz constant α and let G be its G-matrix. Then, tr(G) = Ω(n) with high probability.
The previous two theorems together imply that the G-matrix is poorly conditioned when d = O(log0.75 n) and the activation function is smooth, e.g., tanh. The effect on training of G-matrix being poorly conditioned can be easily seen in Equation 3 for the m→∞ case with gradient flow discussed earlier. For the finite m setting, we show that the technique of Arora et al. (2019c) can be extended to the setting of smooth functions (see Appendix M.4) to prove the following.
Theorem 4.6. Denote by vi the eigenvectors of G(0) and with λi the corresponding eigenvalue. With probability at least 1 − κ over the random initialization, the following holds for t ≥ 0, ‖y−u(t)‖2 ≤ ( ∑n i=1(1−ηλi)2t(vTi (y−u(0)))2)1/2+ , providedm ≥ Ω(n5κ−1λmin(G(0))−4 −2) and η ≤ O(n−2λmin(G(0))).
This result can be interpreted to mean that in the small perturbative regime of Du et al. (2019a); Arora et al. (2019c), smooth functions like tanh do not train fast. The learning rate in the above result is small as λmin(G(0)) is small. Analyzing the training for higher learning rates remains open.
Positive results for smooth activations. We show that in a certain sense the results of Theorem 4.3 and Theorem 4.4 are tight. Let us illustrate this for Theorem 4.4. Suppose that the activation function is tanh and that the dimension of the span V of the data x1, . . . ,xn is Ω(nγ), for a constant γ. Furthermore, we assume that the data is smoothed in the following sense. We start with a preliminary dataset x′1, . . . ,x ′ n with the same span V , then we perturb each data point by adding i.i.d. Gaussian noise, i.e. xi = x′i + ni, and normalize to have unit Euclidean norm (see Assumption 3 for a precise statement). This Gaussian noise is obtained by taking the standard Gaussian variable on V multiplied by a small factor. Thus the new data points have span V . For such datasets we show the following theorem. For more general theorems for polynomial activations and tanh, see Theorem I.3 and Theorem I.4 respectively.
Theorem 4.7 (Informal version of Corollary I.4.2). Let the activation be tanh, let the perturbation noise be of the order (δ/ √ n) and d′ = dim span{x1, . . . ,xn} ≥ Ω(nγ), for a constant γ. Then we have λmin(G(0)) ' Ω(δ(2/γ)n−(3/γ)) with probability at least 0.99 w.r.t. the noise matrix N, {w(0)k }mk=1 and {a (0) k }mk=1, provided m ' Ω̃(n6/γδ−4/γ).
We now say a few words about our assumption that the data is smoothed. Smoothed analysis, originating from Spielman & Teng (2004), is a general methodology for analyzing efficiency of algorithms (often those that work well in practice) and can be thought of as a hybrid between worstcase and average-case analysis. Since in nature, problem instances are often subject to numerical and observational noise, one can model them by the process of smoothing. Smoothed analysis involves analyzing the performance of the algorithm on smoothed instances, which can be substantially better than the worst-case instances. Smoothed analysis has also been used in learning theory and our proof is inspired by Anderson et al. (2014) addressing a different problem, namely rank-1 decomposition
of tensors. In the present case, smoothness of the data rules out situations where the data has span d′ in a non-robust sense: most of the data points lie in small dimensional subspace and the dimension of the span is high because of a few points. Some such condition seems essential.
In another direction, we show that if the network is sufficiently deep for tanh, only the separability assumption on the data suffices. For deep networks, Du et al. (2019b) generalized the notion of G-matrix to be the G-matrix for the penultimate layer (see Section J). This matrix and its eigenvalues play similar role in the dynamics of training as for the one-hidden layer case discussed before; we continue to denote this matrix by G(0). This result can be generalized to other smooth activations. Theorem 4.8 (informal version of Theorem J.6). Let the activation be tanh and let the data satisfy Assumption 1 and Assumption 2. Let the depth L satisfy L = Θ(log 1/δ). Then λmin(G(0)) ≥ e−Ω( √ logn) 1/poly(n) with high probability, provided m ≥ Ω ( poly(n, 1/δ) ) .

heading: 5 EXTENSIONS
text: For a large part of the paper we confine ourselves to the case of one hidden layer where only the input layer is trained. This is in order to focus on the core technical issues of the spectrum of the G-matrix. Indeed, our results can be extended along several axes, often by combining our results for the G-matrix with existing techniques from the literature. We now briefly discuss some of these extensions. Some of these are worked out in the appendix for completeness.
We can easily generalize to the case when the output layer is also trained (Section M.2). Also, we have focused on training with gradient descent, but training with stochastic gradient descent can also be analyzed for activations in Jr (Section M.5).
Generalization bounds from Arora et al. (2019c) can easily be extended to the set of functions satisfying Jr using techniques from Du et al. (2019b). Similarly, techniques from Allen-Zhu et al. (2019) for higher depth generalize to functions such as SELU, LReLU and ELU. We believe this also generalizes to Jr. Other loss functions such as cross-entropy can be handled as well as activations with more than one kink. The case of multi-class classification can also be handled (Sec. M.3). We do not pursue these directions in this paper choosing to focus on the core issues about activations. We briefly discuss extension to more general classes of activations in Appendix H.

heading: 6 PROOF SKETCH
text: In this section, we provide a high level sketch of the proofs of our results. Activations with a kink. We first sketch the proof of Theorem K.1, which shows that the minimum eigenvalue of the G-matrix is large for activations satisfying J1. As an illustrative example, consider ReLU. Its derivative, the step function, is discontinuous at 0. In their convergence proof for ReLU networks, Allen-Zhu et al. (2019) prove that the norm of the gradient for a W is large if the loss at W is large. We observe that their technique also shows a lower bound on the lowest singular value of the M-matrix by considering the norm of all possible linear combinations of the columns. For ζ ∈ Sn−1, define the linear combination fζ(w) := ∑n i=1 ζi φ ′(wTxi)xi. Theorem 6.1 (Informal statement of Claim K.2). Let φ ∈ J1. For any ζ ∈ Sn−1, fζ(w) has large norm with high probability for a randomly chosen standard Gaussian vector w.
Using an -net argument on ζ, the above result implies a lower bound on the minimum singular value of M. Allen-Zhu et al. (2019) write w as two independent Gaussian vectors w′ and w′′, with large and small variances respectively. They isolate an event E involving w′. This event happens if all but one of the summands in fζ(w) = ∑n i=1 ζi φ
′((w′ + w′′)Txi)xi are fixed to constant values with good probability over the choice of w′′. For the exceptional summand, say ζj φ
′((w′ + w′′)Txj)xj , the choice of w′ is such that the argument (w′ + w′′)Txj can be on either side of the jump discontinuity with large probability over the random choice of w′′. The random choice of w′′ now shows that the whole sum is not concentrated and so with significant probability has large norm. They show that E has substantial probability over the choice of w′, which implies that with significant probability ‖fζ(w)‖ is large. The property of all but one of the summands being fixed relies crucially on the fact that the derivative of ReLU is constant on both sides of the origin.
When generalizing this proof to activations in J1 we run into the difficulty that the derivative need not be a constant function on the two sides of the jump discontinuity. We are able to resolve this difficulty with additional technical ideas, in particular, using the assumption that |φ′(·)| is bounded.
We work with event E′ involving w′: in the sum defining fζ(w) there is one exceptional summand ζj φ
′((w′ + w′′)Txj)xj such that the sum involving the rest of the summands—while not fixed to a constant value unlike for ReLU—does not change much over the random choice of w′′. Whereas the exceptional summand varies a lot with the random choice of w′′ because the argument moves around the jump discontinuity. We show that E′ has significant probability, which proves the theorem.
Now, we look at the proof of Theorem 4.1 which handles activations in J2. The goal again is to show that for any ζ ∈ Sn−1, the function fζ(w) has large norm with good probability for the random choice of w. To this end, we consider the Taylor approximation of gζ(w) := ∑n i=1 ζi φ
′(wTxi) around w′, that is, gζ(w′ + w′′) = gζ(w′) + (∇wgζ(w′))Tw′′ + H(w′,w′′) where H is the error term. We show that ∥∥∇wgζ(w′)∥∥ is likely to be large over the random choice of w′, and so (∇wgζ(w′))Tw′′ is likely to be not concentrated on any single value if the error term H(w′,w′′) is sufficiently small, which we show. To prove that ‖∇wgζ(w′)‖ is large, note that∇wgζ(w′) = ∑n i=1 ζi φ
′′(wTxi)xi, which allows us to use the argument above for fζ(w) being large in the case of J1. This implies that gζ(w) is large with good probability, which implies, with further argument, that fζ(w) is large. Full proofs of these results can be found in Appendix K. As mentioned earlier, the argument can be generalized to condition Jr for any constant r; we omit the details.
Smooth activations. First we look at the proof sketch for Theorem 4.4. To understand the behavior of smooth activations under gradient descent, we first look at the behavior of a natural subclass of smooth functions: polynomials. The proof actually works with the M -matrix introduced earlier whose spectrum is closely related to that of G = MTM/m. In this case, the problem of computing the smallest eigenvalue reduces to finding a non-trivial linear combination of the columns of M resulting in 0. We show that if d′, the dimension of the span of the data, is sufficiently small, then this can be done implying that the smallest eigenvalue is 0. By a simple extension of the argument, we can show that in fact the G-matrix has low rank. This gives Theorem 6.2 (Informal version of Theorem F.2). The G-matrix for polynomial activation functions has low rank if the data spans a low-dimensional subspace.
Given that polynomials have singular M -matrices, a natural idea is to approximate the smooth function tanh′ by a suitable family of polynomials, and then use the above theorem to “kill” the polynomial part using an appropriate linear combination and get an upper bound on the eigenvalue comparable to the error in the approximation. An immediate choice is Taylor’s approximation. The Taylor series for tanh′ around 0 has a radius of convergence π/2. Depending on the initialization and m, the argument of the function can take values outside [−π/2, π/2]. To circumvent this difficulty, we consider a different notion of approximation. Consider a series of Chebyshev polynomials∑ anTn(x) that approximates tanh′(x) in the L∞ norm in some finite interval. The fact that tanh′ can be extended analytically to the complex plane can be used to show that the coefficients of the above series decay rapidly. The approximation is captured by the following theorem. Theorem 6.3 (Informal version of Theorem F.4). tanh′ is approximable on the interval [−k, k] in the L∞-norm by (Chebyshev) polynomials to error > 0 using a polynomial of degree O(k log(k/ )).
When applying the lemma above, the degree required for approximation increases with the number of neurons m. This is because the interval [−k, k], in which the approximation is required to hold, grows with m (the maximum of mn Gaussians grows as O( √ logmn)). This leads the degree of polynomial to become too large to be “killed” as m becomes larger. Thus, for large m, this fails to give the required bound. To remedy this, we relax the approximation requirement. Since we are working with Gaussian initialization of weights a natural relaxation is the L2-approximation under the Gaussian measure. This leads us to consider the Hermite expansion (see also Daniely et al. (2016)) of tanh′. The p-th coefficient in Hermite expansion is an integral involving the p-th Hermite polynomial. For large p, these polynomials are highly oscillatory which makes evaluation of the coefficients difficult. Fortunately, a theorem of Hille (1940) comes to rescue. Again, the fact that tanh′ can be analytically extended to a certain region of the complex plane can be used to bound the decay of the Hermite coefficients, which in turn bounds the error in polynomial approximation: Theorem 6.4 (Informal version of Theorem G.2). tanh′ is approximable on R in the L2-norm with respect to the Gaussian measure by (Hermite) polynomials of degree p with error exp(−Ω(√p)).
In contrast, the p-th Hermite coefficients of the step function (also called threshold or sgn) which is the derivative of ReLU (whose G-matrix has large minimum eigenvalue), decays as p−0.75 (this fact
underlies Theorem L.2). The L2-approximation gives us a bound on the expected loss. To argue about high probability bounds, we need to resort to concentration of measure arguments. This requires the number of neurons m to be large. Thus, these two notions of approximation complement each other.
Now, using these theorems for the small and large m regimes, we can show that the eigenvalues of the G-matrix are indeed small as stated in Theorem 4.4. These results can be easily extended to swish. In fact, the above theorems hold for general functions satisfying certain regularity conditions such as having an analytic continuation onto a strip of complex plane that contains the domain of interest, e.g. an interval of R or all of R (Appendix F).
For smoothed data not restricted to small dimension, tanh works well. We sketch the proof of Theorem 4.7 showing that our results about the limitations of smooth activations are essentially tight when the data is smoothed. It is well-known (see Fact C.9) that the minimum singular value of a (tall) matrix M is lower-bounded as follows: take a column of M and consider its distance from the span of the rest of the columns. The minimum of this quantity over all columns gives a lower bound on the minimum singular value (up to polynomial factors in the dimensions of M). The problem of lower bounding λmin(G(0)) then reduces to the problem of lower bounding a product involving (a) the minimum singular value of X∗p, the p-th Khatri–Rao power of the data matrix X = [x1, . . . ,xn], (b) the p-th Hermite coefficient of tanh′ (see Lemma I.1 and Lemma I.2). We use p to be approximately equal to 1/γ. For (a) we use the above strategy to lower bound the minimum singular value of X∗p. It turns out that for any given column, its distance from the span of the rest of the columns can be written as a polynomial in the noise variables. We can then use the anticoncentration inequality of Carbery–Wright (see Fact C.8) to show that this distance is unlikely to be small, and then use the union bound to show that this is unlikely to be small for every column. For (b), we invoke a result of Boyd (1984) implying that the upper bound exp(−Ω (√ p ) ) on the p-th Hermite coefficient of tanh′ used in Theorem 6.4 above is essentially tight. The choice of p that gives the best lower bound depends on the activation function.
Depth helps for tanh. We now sketch the proof of Theorem 4.8 (for a formal statement, see Theorem J.6). For each i ∈ [n] and l ∈ {0, ..., L − 1}, let x(l)i be the output of layer l on input xi. We track the behavior of the x(l)i as l increases:
Lemma 6.5 (informal version of Lemma J.1 and Lemma J.2). As l increases, the Euclidean norm of each x(l)i is approximately preserved. On the other hand, for every i 6= j, |(x (l) i ) Tx (l) j | shrinks.
This implies that for sufficiently large L, the Gram matrix of the output of the penultimate layer, i.e. (X(L−1))TX(L−1), where X(L−1) = [x(L−1)1 , . . . ,x (L−1) n ] is diagonally-dominant and has large minimum eigenvalue. The rest of the proof has some overlap with the proof for smoothed data above. For each p ≥ 0, λmin(G(0)) can be lower bounded by a product involving (a) the minimum eigenvalue of the p-th Hadamard power of the Gram matrix of x(L−1)i , and (b) the p-th Hermite coefficient of tanh′ (see Equation 47). For (a) we use the diagonal-dominance of the Gram matrix. For (b) we proceed as in the case of smoothed data. The choice p = Θ(log n) turns out to give the best lower bound on λmin(G(0)).

heading: 7 EXPERIMENTS
text: Synthetic data. We consider n equally spaced data points on S1, randomly lifted to S9. We randomly label the data-points from U {−1, 1}. We train a 2-layer neural network in the DZPS setting with mean squared loss, containing 106 neurons in the first layer with activations tanh, ReLU, swish and ELU at learning rate 10−3. The output layer is not trained during gradient descent. In Figure 1(a) and Figure 1(b) we plot the squared loss against the number of epochs trained. Results are averaged over 5 different runs. We observed that the eigenvalues and the eigenvectors stayed essentially constant throughout training, indicating overparametrized regime. ReLU converges to zero training error much faster than other activation functions, ELU is faster than tanh and swish. In Figure 1(c) and Figure 1(d) we plot the eigenvalues at initialization. Eigenvalues of ReLU and ELU are larger compared to those of tanh and swish. This is consistent with the theory. Real data. We consider a random subset of 104 images from CIFAR10 dataset (Krizhevsky & Hinton, 2009). We train a 2-layer network containing 105 neurons in the first layer. First, we verify Assumption 2 regarding δ-separation of data samples. We plot the L2-distances between all pairs
of preprocessed images (described in Section 2) in Figure 2(a). It shows that the assumptions hold for CIFAR10, with δ at least 0.1. Figure 2(b) has the plot of the cumulative sums of eigenvalues, normalized to the range [0, 1], of the data covariance matrix. This figure shows that the intrinsic dimension of data is much larger than O (log n), where n denotes the number of samples. Eigenvalues of the G-matrix for different activations at initialization are plotted in Figure 2(c). This shows that ReLU has higher eigenvalues compared to other activations. However there isn’t much difference between the spectrum of ELU and tanh. This is likely due to the fact that we are in the regime of Theorem I.4.
We observed a difference in the rate of convergence while training a 2-layer network, with both layers trainable, using 256 batch sized stochastic gradient descent (SGD) with cross entropy loss on the random subset of CIFAR10 dataset at l.r. 10−3 (Figure 2(d)). Here we are not in the overparametrized regime as the eigenvalues and eigenvectors change considerably during training. Therefore, observations in Figure 2(d) can be attributed to the eigenvalue plots in Figure 2(c) only in the first few iterations of SGD.

heading: 8 CONCLUSION
text: In this paper we characterized the effect of activation function on the training of neural networks in the overparametrized regime. Our results hold for very general classes of activations and cover all the activations in use that we are aware of. Many avenues for further investigation remain: there are gaps between theory and practice because of the differences in the sizes, learning rates, optimization procedures and architectures used in practice and those analyzed in theory: compared to practice, most theoretical results in the recent literature (including the present paper) require the size of the networks to be very large and the learning rate to be very small. Bridging this gap is an exciting challenge. Fine-grained distinction between the performance of activations is also of interest. For example, Figure 2(d) shows that ReLU converges much faster compared to the other activations. But the roles can be reversed based on the architecture and the dataset etc., e.g., Ramachandran et al. (2018). In a given situation, what makes one activation more suitable than another?

heading: CONTENTS

heading: 1 Introduction 1

heading: 2 Preliminaries 3

heading: 3 Review of Relevant Prior Work 4

heading: 4 Main Results 5
text: 4.1 Activations with a kink . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.2 Smooth Activations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

heading: 5 Extensions 7

heading: 6 Proof Sketch 7

heading: 7 Experiments 9

heading: 8 Conclusion 10

heading: A Additional Related Work 18

heading: B Activations 18

heading: C Preliminary facts and definitions 18
text: C.1 General Approach for Bounding Eigenvalue of G-Matrix . . . . . . . . . . . . . . 20

heading: D Standard Parametrization and initializations 20
text: D.1 Note on G-Matrix for Standard Initializations . . . . . . . . . . . . . . . . . . . . 21
E Lower Bound on the Trace of G-Matrix 21
F Upper Bound on Lowest Eigenvalue for tanh 22
F.1 Polynomial Activation Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
F.2 L∞ Approximation using the Chebyshev Polynomials . . . . . . . . . . . . . . . . 24
F.3 L2 Approximation using Hermite Polynomials . . . . . . . . . . . . . . . . . . . . 25
F.3.1 DZPS Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
F.3.2 Standard Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

heading: G Upper Bound on Lowest Eigenvalue for Swish 35

heading: H A discussion on Upper Bound of Lowest Eigenvalue for General Activation Functions 35
text: I Lower bound on eigenvalues for tanh when the dimension of the data is not too small 37
J Depth helps for tanh 41

heading: K Lower Bound on Lowest Eigenvalue for Non-Smooth Functions 49
text: K.1 J1: The first derivative is discontinuous at a point . . . . . . . . . . . . . . . . . . 49
K.1.1 DZPS Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
K.1.2 J1 for Standard Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
K.2 J2 : The second derivative has jump discontinuity at a point . . . . . . . . . . . . 53
K.2.1 DZPS setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
K.2.2 J2 for Standard Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
L A new proof for the minimum eigenvalue for ReLU 60

heading: M Extensions and Additional Discussion 62
text: M.1 Polynomial minimum eigenvalue of G-matrix at time t . . . . . . . . . . . . . . . 62
M.2 Trainable output layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
M.3 Multi Class Output with Cross Entropy Loss . . . . . . . . . . . . . . . . . . . . . 63
M.4 Fine-grained analysis for smooth activation functions . . . . . . . . . . . . . . . . 65
M.5 Proof for SGD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
N Some basic facts about Hermite polynomials 74

heading: A ADDITIONAL RELATED WORK
text: The literature is extensive; we only mention some of the related work Pennington et al. (2017); Louart et al. (2018); Hanin (2018); Hanin & Rolnick (2018); Pennington & Worah (2017; 2018); Pennington et al. (2018). Of these, perhaps the closest to our work is Louart et al. (2018): they keep the random weights in the input layer fixed and only train the output layer. The main result is determination of the spectrum of a matrix associated with the input layer with the activation function being Lipschitz. This matrix is different from one considered here. Also the scaling used is different: both the dimension of the data, number of samples, and the number of neurons grow at the same rate to infinity. The effect of the activation function on the training via the spectrum is considered but no results are provided for popular activations. Hayou et al. (2019) aim to find the best possible initialization of weights, that lead to better propagation of information in an untrained neural network, i.e. the rate of convergence of correlation among hidden layer outputs of datapoints to 1 should be of the order 1poly(L) , where L is the number of layers. They show smooth activation functions have a slower rate and hence, are better to use in deep neural networks. However, this set of parameterizations, called “edge of chaos”, were proven to be essential for training by Lee et al. (2017) under the framework of equivalence of infinite width deep neural networks to Gaussian processes over the weight parameters. The extent to which the approximation of stochastic gradient descent by Bayesian inference holds is still an open problem.

heading: B ACTIVATIONS
text: We introduce some of the most popular activation functions. These activation functions are unary, i.e. of type φ : R→ R, and act on vectors entrywise: φ((t1, t2, ...)) := (φ(t1), φ(t2), ...). In this paper we do not study activation functions with learnable parameters such as PReLU, or activation functions such as maxout which are not unary. Activations functions are also referred to as nonlinearities, although the case of linear activation functions has also received much attention.
• ReLU(X) := max (x, 0) • LReLU(x) := max (x, 0) + αmin (x, 0), where α is a constant less than 1 • Linear(x) := x
• tanh(x) := e 2x−1 e2x+1
• sigmoid(x) := 11+e−x • swish(x) := x1+e−x Ramachandran et al. (2018) (called SiLU in Elfwing et al. (2017)) • ELU(x) := max (x, 0) + min (x, 0) (ex − 1) Clevert et al. (2016) • SELU(x) := α1 max (x, 0) + α2 min (x, 0) (ex − 1), where α1 and α2 are two different
constants Klambauer et al. (2017).

heading: C PRELIMINARY FACTS AND DEFINITIONS
text: We note some well known facts about concentration of Gaussian random variables to be used in the proofs. Fact C.1. For a Gaussian random variable v ∼ N (0, σ2), ∀t ∈ (0, σ), we have
Pv{|v| ≥ t} ∈ (
1− 4 5 t σ , 1− 2 3 t σ
) .
In fact, the following holds true. ∀t ∈ (0, σ/2), we have Pv{|v − a| ≥ t} ∈ (
1− 4 5 t σ , 1− 1 4 t σ
) .
where 0 ≤ a ≤ σ. Fact C.2. For a Gaussian random variable v ∼ N (µ, σ2), ∀t ∈ (0, σ), we have ∀t ≥ 0
Pv { |v − µ| ≤ t } ≤ 1− 2e− t2 2σ2 .
Fact C.3 (Hoeffding’s inequality, see Boucheron et al. (2013)). Let x1, x2, .., xn be n independent random variables, where xi lies in the interval [ai, bi], and let x̄ be the empirical mean, i.e., x̄ =∑n
i=1 xi n . Then,
Pr (∣∣x̄− E (x̄)∣∣ ≥ t) ≤ 2e− 2n2t2∑ni=1(ai−bi)2 .
Fact C.4 (Multiplicative Chernoff bound, see Boucheron et al. (2013)). Let x1, x2, .., xn be independent random variables taking values in {0, 1}, and let x̄ be the empirical mean, i.e., x̄ = ∑n i=1 xi n . Then
Pr ( x̄ < (1− t)E (x̄) ) ≤ e− t2E(x̄) 2 ,
Pr ( x̄ > (1 + t)E (x̄) ) ≤ e− t2E(x̄) 2+t
for all t ∈ (0, 1). Fact C.5 (Maximum of Gaussians, see Boucheron et al. (2013)). Let x1, x2, ..., xn be n Gaussians following N ( 0, σ2 ) . Then,
Pr { max i∈[n] |xi| ≤ k √ log nσ } ≥ 1− 2
n k2 2 −1 .
where k > 0 is a constant.
Fact C.6 (Chi square concentration bound, see lemma 1 in Laurent & Massart (2000)). For a variable x that follows chi square distribution with k degrees of freedom, the following concentration bounds hold true.
P (x− k ≥ 2 √ kt+ 2t) ≤ exp(−t),
P (k − x ≥ 2 √ kt) ≤ exp(−t).
Fact C.7 (Mini-max formulation of singular values). Given a matrix M ∈ Rm×n, assuming n ≤ m, the singular values of M can be defined as follows.
σk (M) = min U maxζ { Mζ ∣∣∣∣ζ ∈ U, ζ 6= 0 }∣∣∣∣ dim (U) = k  ∀k ∈ [n]. Fact C.8 (adaptation of Carbery & Wright (2001); see Anderson et al. (2014)). Let Q (x1, . . . , xn) be a multilinear polynomial of degree d. If Var (Q) = 1, when xi ∼ N (0, 1)∀i ∈ [n]. Then, ∀t ∈ R and > 0, there exits C > 0 s.t.
Pr(x1,...,xn)∼N (0,In) (∣∣Q (x1, . . . , xn)− t∣∣ ≤ ) ≤ Cd 1/d. Fact C.9 (Rudelson & Vershynin (2009)). Given a matrix A ∈ Rn×m, the following holds true for all i ∈ [m].
1√ m min i∈[m] dist (ai,A−i) ≤ σmin(A)
where A−i = span ( aj : j 6= i ) Fact C.10 (Gershgorin circle theorem, see e.g. Varga (2010)). Every eigenvalue of a matrix A ∈ Cn×n, with entries aij , lies within at least one of the discs { D(aii, ri) }n i=1 , where ri = ∑ j:j 6=i
∣∣aij∣∣ and D(aii, ri) ⊂ C denotes a disc centered at aii and with radius ri. Fact C.11 (Weyl’s inequalities (Weyl, 1912)). Let A and B be two hermitian matrices. Then, the following hold true ∀i, j ∈ [n].
λi+j−1 (A + B) ≤ λi (A) + λj (B)
λi+j−n (A + B) ≥ λi (A) + λj (B)
Definition C.1 (Khatri Rao product and Hadamard product, see Khatri & Rao (1968)). Given a matrix A ∈ Rm×n and a matrix B ∈ Rp×q, the Kronecker (or tensor) product A⊗B is defined as the mp× nq matrix given by
A⊗B =  a11B a12B · · · a1nB a21B a22B · · · a2nB ... ... . . . ...
am1B am2B · · · amnB  . Given a matrix A ∈ Rm×n and a matrix B ∈ Rp×n, the Khatri Rao product A ∗B is defined as the mp× n matrix given by
A ∗B = [ a1 ⊗ b1 a2 ⊗ b2 · · ·an ⊗ bn ] .
Given a matrix A ∈ Rm×n and a matrix B ∈ Rm×n, the Hadamard product A B ∈ Rm×n is defined as
(A ∗B)ij = aijbij , ∀i ∈ [m], j ∈ [n].
Notation: Given a matrix X ∈ Rm×n, we denote order-r Khatri-Rao product of X as X∗r ∈ Rmr×n, which represents X ∗X . . . ∗X︸ ︷︷ ︸
r times
. We denote order-r Hadamard product of X as X r ∈ Rn×n, which
represents X X . . . X︸ ︷︷ ︸ r times and can be shown to be equal to (X∗r)T X∗r.
C.1 GENERAL APPROACH FOR BOUNDING EIGENVALUE OF G-MATRIX
The Gram matrix G can be written as
G = 1
m MTM.
where M ∈ Rmd×n is defined by Md(k−1)+1: dk,i = akφ ′ ( wTk xi ) xi for k ∈ [m].
Denoting by λk(G) and σk(M) as kth eigenvalue and kth singular value of G and M respectively, we can write λk (G) as 1mσk (M)
2. The minimum singular value of M can be defined (through the minmax theorem) as
σmin (M) = min ζ∈Sn−1
‖Mζ‖ .
Hence, the general approach to show a lower bound of σmin (M) is to show that the following quantity ∥∥∥∥∥∥ n∑ i=1 ζimi ∥∥∥∥∥∥ = m∑ k=1 √√√√√ ∥∥∥∥∥∥ n∑ i=1 akζiφ′(wTk xi)xi ∥∥∥∥∥∥ 2 (4)
is lower-bounded for all ζ ∈ Sn−1. To show an upper bound, we pick a ζ ′ ∈ Sn−1 and use
σmin (M) = min ζ∈Sn−1
‖Mζ‖ ≤ ∥∥∥∥∥∥ n∑ i=1 ζ ′imi ∥∥∥∥∥∥ . (5)

heading: D STANDARD PARAMETRIZATION AND INITIALIZATIONS
text: A 2-layer (i.e. 1-hidden layer) neural network is given by
F (x;a,b,W) = m∑ k=1 akφ ( wTk x+ bk ) ,
where a ∈ Rm is the output layer weight vector, W ∈ Rd×m is the hidden layer weight matrix and b ∈ Rm denotes the hidden layer bias vector. This parametrization differs slightly from the choice made in Equation 1. By standard initialization techniques He et al. (2015) and Glorot & Bengio (2010), there are two ways in which the initial values of the weights W(0) and a(0) are chosen, depending on whether the number of neurons in the previous layer is taken into account (fanin) or the number of neurons in the current layer is taken into account (fanout).
• Init(fanin) : w(0)k ∼ N ( 0, 1dId ) and a(0)k ∼ N ( 0, 1m ) ∀k ∈ [m],
• Init(fanout): w(0)k ∼ N ( 0, 1mId ) and a(0)k ∼ N (0, 1) ∀k ∈ [m].
Note that Allen-Zhu et al. (2019) use Init (fanout) initialization. The elements of b are initialized from N ( 0, β2 ) , where β is a small constant. We set β = 0.1 in Init (fanin) initialization and
β = 1√ m in Init (fanout) initialization.
D.1 NOTE ON G-MATRIX FOR STANDARD INITIALIZATIONS
We follow the argument in Section 3 to get the G-matrix (G) as
g (t) ij = η m∑ k=1 a2kφ ′ ( wTk xi + bk ) φ′ ( wTk xj + bk ) 〈 xi,xj 〉 ,
where η is the gradient flow rate needed to control the gradient during descent algorithm to stop gradient explosion, i.e. we need to control the maximum eigenvalue of the Gram matrix.
For Init (fanin) and Init (fanout), we set η as 1 and 1m respectively to get the same Gradient Gram matrix as in Equation 2.
E LOWER BOUND ON THE TRACE OF G-MATRIX
In this section, we lower bound the trace of the gradient matrix for a general activation function as a point of comparison for our results regarding the lowest eigenvalue. Theorem E.1. Let φ be an activation function, with Lipschitz constant α and let G(0) be the Gmatrix at initialization. Let Ew∼N (0,I) ( φ′ ( wTxi )2) = 2c for a positive constant c and for all i.
Then, tr(G(0)) ≥ cn with probability greater than 1− e−Ω(m/α 2 log2 m) −m−3.5.
Remark. The constant c depends on the choice of the activation function and is bounded away from 0 for most activation functions such as ReLU or tanh.
Proof. The trace of the G-matrix is given by
tr(G(0)) = 1
m m∑ j=1 n∑ i=1 ( a (0) j φ ′ ( w (0)T j xi ))2 .
Using Fact C.5, { a
(0) j }m j=1 can be shown to be in the range ( −3 √ logm, 3 √ logm ) with probability
at-least 1−m−3.5. Assuming this is true, we claim the following two statements. For any j we have (expectation is over W(0) and { a
(0) k }m k=1 )
E w
(0) j ,a (0) j : |a(0)j |≤3 √ logm n∑ i=1 ( a (0) j φ ′ ( w (0)T j xi ))2 =
n∑ i=1 E a (0) j : |a(0)j |≤3 √ logm ( a (0) j )2 E w (0) j ( φ′ ( w (0)T j xi ))2 ≥
n∑ i=1 2c
( 1− √ logm
m ) ≥ cn.
where we use the independence of a(0)j and w (0) j and the variance of a (0) j is at-least
( 1− √ logm m ) ,
taking the bound on a(0)j into account, in the intermediate steps.
Also, we get from the Hoeffding bounds,
Pr  1 m m∑ j=1 n∑ i=1 ( a (0) j φ ′ (( w (0) j )T xi ))2 ≥ 1 2 cn  ≤ 1− e−Ω(mn2/α4 log2 m) as required.
This shows that the trace is large with high probability. From it follows that average of eigenvalue is Ω (1). It also follows that maximum eigenvalue is Ω (1).
F UPPER BOUND ON LOWEST EIGENVALUE FOR tanh
For activation functions represented by polynomials of low degree, we show that the G-matrix is singular. In fact, the rank of this matrix is small if the degree of the polynomial is small. To upper bound the lowest eigenvalue of the G-matrix for the tanh activation function, we proceed by approximating tanh′ with polynomials of low degree. It turns out that tanh′ can be well-approximated by polynomials in senses to be described below. This allows us to use the result about polynomial activation functions to show that the minimum singular value of the G-matrix of tanh is small. The approximation of tanh′ by polynomials turns out to be non-trivial. It does have Taylor expansion centered at 0 but the radius of convergence is π/2 and thus cannot be used directly if the approximation is required for bigger intervals.
We consider two different notions of approximations by polynomials, depending on the initialization and the regime of the parameters. It is instructive to first consider polynomial activations before going to tanh. Next section is devoted to polynomial activations.

heading: F.1 POLYNOMIAL ACTIVATION FUNCTIONS
text: Let’s begin with the linear activation function. In this case, the G-matrix turns out to be the Gram matrix of the data. Since each datapoint is low dimensional, we get that it is singular: Lemma F.1. (Linear activation function) If φ(x) = x and d < n, then the G-matrix is singular, that is
λmin
( G(0) ) = 0.
In fact, at least (n− d) eigenvalues of the G-matrix are 0.
Proof. Since φ (x) = x, we have φ′ (x) = 1 and the G-matrix is given by
G = 1
m  m∑ j=1 a2j XTX where X = [x1,x2, ...,xn] is the matrix containing the xi’s as its columns. Since the xi’s are d-dimensional vectors, rank(X) ≤ d and so, X can have at most d non-zero singular values, which leads to at most d non-zero eigenvalues for G.
We next show that activation functions represented by low degree polynomial must have singular Gradient Gram matrices: Theorem F.2. Let φ′(x) = ∑p `=0 c`x ` and d′ = dim ( Span {x1 . . . xn} ) . Then, the G-matrix is singular, that is λmin ( G(0) ) = 0, assuming that the following condition holds,( d′ + p
p
) < n+ 1. (6)
Proof. Referring to Equation 5, it suffices to find one ζ ′ ∈ Sn−1 such that∥∥∥∥∥∥ n∑ i=1 ζ ′imi ∥∥∥∥∥∥ 2 = √√√√√ m∑ k=1 ∥∥∥∥∥∥ n∑ i=1 ζ ′iakφ ′(wTk xi)xi ∥∥∥∥∥∥ 2 2 = 0.
For any k ∈ [m] and ζ ∈ Rn consider n∑ i=1 ζiakφ ′(wTk xi)xi = n∑ i=1 ζiak p∑ `=1 c`−1 ( wTk xi )`−1 xi
which can be written as
ak p∑ l=1 c`−1 ∑
β∈Zd+,‖β‖1=`−1
( n∑ i=1
ζix β i xi︸ ︷︷ ︸
†
) wβk (7)
Here Z+ denotes the set of non-negative integers, and the notation xβ is shorthand for ∏d j=1 x βj j . Note that the term denoted by † is a d-dimensional vector, since xi ∈ Rd. The actual number of unique equations in † depends on d′, since the xi’s can have only upto d′ order unique moments. Hence, if we want to make the above zero, it suffices to make the term denoted by † zero for each of the summands. This is a system of linear equations in variables {ζi}ni=1. Counting the number of constraints for each summand and summing over all the indices gives us that the number of constraints is given by
p∑ `=1 ( d′ + `− 1 ` ) which is equal to ( d′+p p ) − 1. Note that this can also be seen by counting the number of non-trivial monomials of degree at most p in d′ variables. Hence, making the number of constraints less then number of variables, leads to existence of at least one non-zero vector ζ ′′ satisfying the set of constraints. Since, the set of linear equations is independent of the choice of k, the claim holds true for all k. Thus, using a unit normalized ζ ′′ in Equation 5, we get σmin (M) = 0. Corollary F.2.1. If d′ = dim ( span {x1 . . .xn} ) ≤ O ( log0.75 n ) , φ′(x) = ∑p `=0 c`x ` and p ≤ O(n 1d′ ) then the minimum eigenvalue of the G-matrix satisfies
λmin
( G(0) ) = 0.
Proof. If d′ = O ( log0.75 n ) , Condition 6 can be simplified to get
p = O(n 1d′ )
Applying Theorem F.2 with the above condition, we get the desired solution.
By slightly modifying the proof of the above theorem, we can actually show not only that the matrix is singular, but also that the kernel must be high dimensional.
Theorem F.3. If d′ = dim ( span {x1 . . .xn} ) ≤ O ( log0.75 n ) , φ′(x) = ∑p `=0 c`x ` and p ≤
O(n 1d′ ), then ( 1− 1d′ ) n low-order eigenvalues of the G-matrix satisfy
λk
( G(0) ) = 0, ∀k ≥ ⌈ n
d′
⌉ .
Proof. We follow the proof of Theorem F.2. Referring to Fact C.7, it suffices to find one n ( 1− 1d′ ) dimensional subspace U such that∥∥∥∥∥∥ n∑ i=1 ζimi ∥∥∥∥∥∥ 2 = √√√√√ m∑ k=1 ∥∥∥∥∥∥ n∑ i=1 ζiakφ′(wTk xi)xi ∥∥∥∥∥∥ 2 2 = 0.
holds true ∀ζ ∈ U. For a weight row vector wk ∈ {w1, ... ,wm}, its corresponding output weight ak and an arbitrary ζ ∈ Rn, we can simplify the following quantity
n∑ i=1 ζiakφ ′(wTk xi)xi = n∑ i=1 akζi p∑ `=1 c`−1  d∑ j=1 wk,j xi,j `−1 xi to get the same set of constraints on variable ζ, as in Equation 7. Making the number of constraints less than ⌈ n d′ ⌉ leads to the existence of the desired subspace U, whose dimension is n ( 1− 1d′ ) , satisfying the constraints. This can be restated as( d′ + p
p
) − 1 ≤ n
d′ which can be further simplified using the fact that d′ ≤ O ( log0.75 n ) to get
p ≤ O ( n d′ ) 1 d′  = O (n1/d′) . In the above inequality, we use the fact that 1 ≤ d′1/d′ ≤ √ 2. Since, the set of linear equation is independent of the choice of w, the claim holds true for all w ∈ {w1, ...,wm}, from which the result follows.
Now, if a function is well approximated by a low degree polynomial then we can use the idea from the above theorem to kill all but the small error term leaving us with a small eigenvalue. But, for different regimes of the parameters, we need to consider different polynomial approximations.

heading: F.2 L∞ APPROXIMATION USING THE CHEBYSHEV POLYNOMIALS
text: Let f : [−k, k]→ R be a function for some k > 0. We would like to approximate f with polynomials in the L∞ norm. That is, we would like a polynomial gp of degree p such that
sup x∈[−k,k] ∣∣f(x)− gp(x)∣∣ ≤ . First, we reduce the above problem to that of approximating functions on [−1, 1]. The idea is to consider the scaled function fk(x) = f(kx). Note that fk : [−1, 1] → R. Let h be a polynomial approximating fk i.e. supx
∣∣fk(x)− h(x)∣∣ ≤ . Then, consider the function gp(x) = h (x/k). Then,∣∣f(x)− gp(x)∣∣ = ∣∣∣fk (x/k)− h(x/k)∣∣∣ ≤ . Thus, we can consider approximation of functions on [−1, 1].
We are interested in approximating the derivative of tanh on (−τ, τ). Denote by σ the sigmoid function given by
σ(x) = 1
1 + e−x .
It follows from the definition that tanh (x) = 2σ (2x)− 1. The approach is to consider a series in the Chebyshev polynomials Tn. That is, we consider
N∑ i=0 anTn
The coefficients an corresponding to σ can be computed using the orthogonality relations for the Chebyshev polynomials.
an = 2
π ∫ 1 −1 σ(x)Tn(x)√ 1− x2 dx.
Using this, one can show the following theorem about the polynomial approximations of the sigmoid function.
Theorem F.4 (Equation B.7 in Shalev-Shwartz et al. (2011)). For each k ≥ 0 and ∈ (0, 1], there is a polynomial gp of degree p with
p =  log ( 4π+2k π2 ) log (1 + πk−1)  such that
sup x∈[−1,1] ∣∣gp(x)− σ(kx)∣∣ ≤ . The proof of the claim follows by bounding an using contour integration. From the above discussion, in order to approximate tanh in the interval (−τ, τ), we need to approximate 2σ (2τx)− 1. From Theorem F.4, we require a polynomial of degree
p =
⌈ log (
4π+2τ π2 ) log (1 + πτ−1) ⌉ . (8)
Recall that we actually need to approximate the derivative of tanh. But this can be achieved easily from the fact that tanh′(x) = ( 1 + tanh(x) ) ( 1− tanh(x) ) and the following lemma.
Lemma F.5. Let I be an interval and let fi, gi : I → R for i ∈ {1, 2} be functions such that supx∈I ∣∣fi(x)− gi(x)∣∣ ≤ for all i and∣∣fi(x)∣∣ ≤ 1 for x ∈ I and all i. Then, sup x∈I
∣∣f1(x)f2(x)− g1(x)g2(x)∣∣ ≤ 3 . Proof. For any x ∈ I we have∣∣f1(x)f2 (x)− g1(x)g2 (x)∣∣ ≤ ∣∣f1(x)f2 (x)− f1(x)g2 (x) + f1(x)g2 (x)− g1(x)g2 (x)∣∣
≤ ∣∣f1(x)f2 (x)− f1(x)g2 (x)∣∣+∣∣f1(x)g2 (x)− g1(x)g2 (x)∣∣ ≤ ∣∣f1 (x)∣∣∣∣f2 (x)− g2 (x)∣∣+∣∣g2 (x)∣∣∣∣f1 (x)− g1 (x)∣∣ ≤ + (1 + ) ≤ 2 + 2
≤ 3 .

heading: F.3 L2 APPROXIMATION USING HERMITE POLYNOMIALS
text: Next we consider approximating f in the 2-norm i.e. we would like to find a polynomial hp of degree p such that ∫ ∞
−∞ ∣∣f(x)− hp(x)∣∣2 dµ(x) is minimized. µ denotes the Gaussian measure on the real line. Note that this problem can be solved using the technique of orthogonal polynomials since L2 (R, µ) is a Hilbert space. The study of orthogonal polynomial is a rich and well-developed area in mathematics (see Szegő (1975); Lebedev (1972)). Our main focus in this section will be the case where f is the derivative of tanh and in later sections we extend this analysis to other activation functions.
Let Hk denote the k-th normalized (physicists’) Hermite polynomial given by Hk(x) = [√ π2kk! ]−1/2 (−1)k ex 2 dk
dxk e−x
2
, (9)
and the corresponding normalized (probabilists’) Hermite polynomial is given by
Hek(x) = [√ πk! ]−1/2 (−1)k ex 2/2 d k
dxk e−x 2/2. (10)
The Hermite polynomials are usually written without the normalization. The normalization terms ensure that the polynomials form orthonormal systems with respect to their measures. Recall that µ (x;σ) denotes the density function of a Gaussian variable with mean 0 and standard deviation σ. The series of polynomials Hk are orthonormal with respect to Gaussian measure µ ( x; 1√
2
) and the
series of polynomials Hek are orthonormal with respect to the standard Gaussian measure µ (x; 1) i.e. ∫ ∞
−∞ Hm(x)Hn(x) dµ
( x;
1√ 2 ) = δm,n, (11)∫ ∞
−∞ Hem(x)Hen(x) dµ(x; 1) = δm,n. (12)
The two versions of the Hermite polynomials are related by
Hm(x) = Hem
(√ 2x ) . (13)
For any function f ∈ L2 (µ), we can define the Hermite expansion of the function as
f = ∞∑ i=0 fiHei.
From the orthogonality of the Hermite polynomials, we can compute the coefficients as
fi = ∫ f (x)Hei (x) dµ (x; 1) .
Since L2 is a Hilbert space, we can use the Pythagoras theorem to bound the error of the projection onto the space of degree k polynomials as
∞∑ i=k+1 |fi|2.
This leads us to consider the Hermite coefficients of the functions we would like to study.
We defined the Hermite expansion in terms of probabilists’ Hermite polynomials. For physicists’ version we can define an expansion similarly. In this paper, we will use probabilists’ version in our proofs. Since the literature we draw on comes from both conventions, we will need to talk about physicists’ version also.
In the following we will be using complex numbers. For z ∈ C, the imaginary part of z is denoted by =(z). The following theorem provides conditions under which the Hermite coefficients decay rapidly. It says that if a function extends analytically to a strip around the real axis and the function decays sufficiently rapidly as the real part goes to infinity, the Hermite series converges uniformly over compact sets in the strip and consequently has rapidly decaying Hermite coefficients. The extension to the complex plane provide the function with strong regularity conditions. Theorem F.6. (Theorem 1 in Hille (1940)) Let f(z) be an analytic function. A necessary and sufficient condition in order that the Fourier-Hermite series
∞∑ k=0 ckHk(z)e − z22 , ck = ∫ ∞ −∞ f(t)Hk(t)e − t22 dt (14)
shall exist and converge to the sum f(z) in the strip Sτ = { z ∈ C : ∣∣= (z)∣∣ < τ}, is that f(z) is holomorphic in Sτ and that to every β, 0 ≤ β < τ , there exits a finite positive B(β) such that∣∣f(x+ iy)∣∣ ≤ B(β)e−|x|(β2−y2)1/2 where x ∈ (−∞,∞), y ∈ (−β, β). Moreover, whenever the condition is satisfied, we have
|ck| ≤M( )e−(τ− ) √ 2k+1 (15)
for all positive . Here, M denotes a function that depends only on .
The function tanh can be naturally extended to the complex plane using its definition in terms of the exponential function. From this definition, it follows that tanh has a simple pole at every point such that e2z + 1 = 0. The set of solutions to this are given by 2z = (2n+ 1)π. Thus, tanh is holomorphic in any region not containing these singularities. In particular, tanh is holomorphic in the strip Sπ/2 = { z ∈ C :
∣∣=(z)∣∣ < π/2}. The same holds for tanh′. Using the above theorem, we bound the size of the Hermite coefficients of the derivative of tanh and thus bound the error of approximation by low degree polynomials.
Theorem F.7. Let φ1(z) = tanh′ ( z/ √ 2 ) e− z2 2 . Consider the Hermite expansion of φ1 in terms of {Hk}∞k=0, as
φ1(z) = ∞∑ k=0 ckHk(z)e − z22 . (16)
Then,
|ck| ≤ O ( e− π √ k 4 ) .
Proof. As before consider the strip Sτ = { z ∈ C : ∣∣=(z)∣∣ < τ}. Note that φ1(z) is holomorphic in Sτ for τ < √ 2π/2. For every β ∈ [0, √ 2π/4], consider z = x + iy ∈ Sβ and set √ 2x′ = x and√
2y′ = y. Also note that tanh′(z) = 1/ cosh2(z). Then
∣∣φ1(z)∣∣ = ∣∣∣∣∣ 1cosh2 (x′ + iy′) ∣∣∣∣∣ ∣∣∣∣e−(x′+iy′)2 ∣∣∣∣
= ∣∣∣∣ 1cosh (x′ + iy′) ∣∣∣∣2∣∣∣e−x2+y2−2ixy∣∣∣
= ∣∣∣∣ 1cos y′ coshx′ + i sin y′ sinhx′ ∣∣∣∣2∣∣∣e−x2+y2−2ixy∣∣∣
= 1
cos2 y′ cosh2 x′ + sin2 y′ sinh2 x′ ∣∣∣e−x2+y2−2ixy∣∣∣ ≤ e−x 2 ey 2∣∣e2ixy∣∣
cos2 y′ cosh2 x′
≤ e −x2eβ 2
(cos2 β) cosh2 x′
≤ e−x 2 eβ 2 (sec2 β) sech2x′
≤ 4e−x 2 eβ 2 (sec2 β) ( ex ′ + e−x ′ )−2
≤ 4e−x 2 eβ 2 (sec2 β) e− √ 2|x|
≤ 40 eβ 2 (sec2 β) e− √ β2−y2|x|.
The last inequality follows by noting that √ β2 − y2 ≤ β ≤ √ 2π/4 ≤ √ 2. This satisfies the required condition with B (β) = 40 eβ 2
(sec2 β). Hence, from Theorem F.6, we have that Equation 16 is convergent in the strip Sτ , for τ ≤ √ 2π 4 . Thus, from Equation 15, using = √ 2π 8 we have
|ck| ≤ Ce− π 4 √ 2
√ 2k+1
for some constant C independent of k.
Corollary F.7.1. Let φ2(x) = tanh′(x). Consider the Hermite expansion of φ2:
φ2(x) = ∞∑ k=0 c̄kHek(x). (17)
Then,
|c̄k| ≤ O ( e− π √ k 4 ) .
Proof. Using orthonormality of Hek with respect to the standard Gaussian measure, we have
c̄k = ∫ ∞ −∞ φ2(x)Hek(x) dµ(x; 1) = 1√ 2π ∫ ∞ −∞ φ2(x)Hek(x)e − x22 dx
= √
2 1√ 2π ∫ ∞ −∞ φ2 (√ 2x ) Hek (√ 2x ) e−x 2 dx
Using φ2 (√ 2x ) = φ1 (x) e x2 2 , defined in Theorem F.7 and Hek (√ 2x )
= Hk (x), as given by Equation 13, we have
c̄k = 1√ π ∫ ∞ −∞ φ1 (x)Hk (x) e − x22 dx
Applying Theorem F.7, we get the required bound.
Corollary F.7.2. Let φ2(x) = tanh′(x) and let φ2 be approximated by Hermite polynomials {Hek}∞k=0 of degree up to p in Equation 17, denoted by
hp(x) := p∑ k=1 c̄kHek(x).
Let Ep(x) := φ2(x)− hp(x).
Then, ∫ ∞ −∞ Ep(x) 2 dµ(x; 1) ≤ O (√ pe − π 4 √ 2 √ p ) .
Proof.
Ep(x) = φ2(x)− hp(x) = ∞∑
k=p+1
c̄kHek(x).
Using orthonormality of normalized Hermite polynomials with respect standard Gaussian measure, we have ∫ ∞
−∞ Ep(x)
2 dµ(x; 1) = ∞∑ k=p+1 ∫ ∞ −∞ c̄2kHek(x)Hek(x) dx = ∞∑ k=p+1 c̄2k.
Substituting the bounds for {c̄k}∞k=p+1 from Corollary F.7.1, we have ∞∑
k=p+1
c̄2k ≤ ∞∑
k=p+1
e − π 4 √ 2
√ 2k+1
≤ ∫ ∞ p e − π 4 √ 2 √ 2x+1 dx
= 32
π2
( π
4 √ 2
√ 2p+ 1 + 1 ) e − π 4 √ 2 √ 2p+1 ,
as required.
For comparison, consider the Hermite expansion of the derivative of ReLU, the threshold function. It can be shown (see (Lebedev, 1972, page 75)) that
ReLU′(x) = 1
2 √ π ∞∑ k=0
(−1)k √√ π22k+1(2k + 1)!
22k (2k + 1) k! H2k+1(x) +
1
2
= 1
4 √
4π ∞∑ k=0
(−1)k √ (2k + 1)!
2k (2k + 1) k! H2k+1(x) +
1
2
≈ ∞∑ k=0
(−1)k √ 22kk2k √ 2ke−2k
2k √ (2k + 1)kk √ ke−k H2k+1(x) + 1 2
≈ ∞∑ k=0 (−1)k√ (2k + 1) 4 √ k H2k+1(x) + 1 2
≈ ∞∑ k=0 (−1)k k0.75 H2k+1(x) + 1 2 . (18)
We can also expand the threshold function, in terms of probabilist’s Hermite polynomials in the following manner. If the expansion of threshold function is written as ∑∞ k=0 c̄kHek (x), then
c̄k = 1√ 2π ∫ ∞ −∞ ReLU′(x)Hek(x)e − x22 dx
= 1√ π ∫ ∞ −∞ ReLU′( √ 2y)Hek( √ 2y)e−y 2 dy
= 1√ π ∫ ∞ −∞ ReLU′(y)Hk(y)e −y2dy (19)
= ck ≈ (−1)k
k0.75 (20)
where we use Equation 13 and the fact that ReLU′(y) = ReLU′( √ 2y) in Equation 19.
It can now be seen that the Hermite coefficients do not decay rapidly for this function.

heading: F.3.1 DZPS SETTING
text: For this choice of initialization, defined in section 2, we need to consider two different regimes depending on the number of neurons m. When m is small, we use Chebyshev approximation in the L∞ norm, while we use the L2 approximation by Hermite polynomials when m is large. First consider the Chebyshev approximation.
Theorem F.8. Assuming φ(x) = tanh(x) and weights w(0)k ∼ N (0, Id), a (0) k ∼ N (0, 1) ∀k ∈ [m], the minimum eigenvalue of the G-matrix is
λmin
( G(0) ) ≤ O n 4π + 6√log nm(
1 + π/3√ lognm
)p  2 
with probability at least 1 − 2 (mn)3.5
with respect to { w
(0) k }m k=1 and { a (0) k }m k=1
, where p is the largest integer that satisfies Condition 6.
Proof. In the following, for typographical reasons we will write wk instead of w (0) k and ak instead of a(0)k . Referring to Equation 5, it suffices to find a vector ζ g ∈ Sn−1 s.t. ∥∥∑n i=1 ζ g imi ∥∥ is small. For each k ∈ [m] and i ∈ [n], wTk xi is a Gaussian random variable following N (0, 1). Thus, there are mn Gaussian random variables and with probability at least ( 1− 2
(mn)3.5
) with re-
spect to {wk}mk=1, maxi∈[n],k∈[m] ∣∣wTk xi∣∣ ≤ 3√log nm. Hence, we restrict ourselves to the
range ( −3 √ log nm, 3 √ log nm ) , when we analyze φ(x). Now, from Equation 8 and Lemma F.5, we have that there exists a polynomial g (x) of degree p that can approximate φ′ in the interval( −3 √ log nm, 3 √ log nm ) with the error of approximation in L∞ norm given by
≤ 3 4π + 6√log nm( 1 + π/3√
lognm
)p  .
From Theorem F.2, there exists ζg ∈ Sn−1 s.t.
m∑ k=1 ∥∥∥∥∥∥ n∑ i=1 ζgi ak g ( wTk xi ) xi ∥∥∥∥∥∥ 2
2
= 0
provided Condition 6 holds true. For any weight vector wk, it’s corresponding output weight ak and any ζ ∈ Sn−1, we have∥∥∥∥∥∥ n∑ i=1 ζi akφ ′(wTk xi)xi − n∑ i=1 ζi akg(w T k xi)xi ∥∥∥∥∥∥ 2 ≤ √√√√a2k n∑ i=1 ζ2i ( φ′(wTk xi)− g(wTk xi) )2√√√√ n∑ i=1 ‖xi‖2
(21)
≤ √ n |ak| (22)
where we use triangle inequality and the Cauchy-Schwartz inequality in Inequality 21, ‖ζ‖ = 1, ‖xi‖ = 1 and that the maximum error of approximation is in Inequality 22. Hence, for ζ = ζg , we have∥∥∥∥∥∥ n∑ i=1 ζgi akφ ′(wTk xi)xi ∥∥∥∥∥∥ 2 ≤ ∥∥∥∥∥∥ n∑ i=1 ζgi akφ ′(wTk xi)xi − n∑ i=1 ζgi akg(w T k xi)xi ∥∥∥∥∥∥ 2 + ∥∥∥∥∥∥ n∑ i=1 ζgi akg(w T k xi)xi ∥∥∥∥∥∥ 2
≤ √ n|ak| (23)
Thus, ∥∥∥∥∥∥ n∑ i=1 ζgimi ∥∥∥∥∥∥ = √√√√√ m∑ k=1 ∥∥∥∥∥∥ n∑ i=1 ζgi akφ ′ ( wTk xi ) xi ∥∥∥∥∥∥ 2 ≤ √√√√ m∑ k=1 a2k √ n ≤ √ 5m √ n
where in the final step, we use chi-square concentration bounds (Fact C.6) to show that √∑m
k=1 a 2 k
is at-most √ 5m with probability at-least 1− e−m. Using Equation 5, σmin (M) ≤ √ 5m √ n . That implies, λmin(G) = 1mλmin (M) 2 ≤ 5n 2. Since, decreases with increasing p, we substitute the value of at maximum value of p possible in order to get the desired result.
Note that since the upper bound on the eigenvalue depends on m, the bound becomes increasingly worse as we increase m. This is because as we increase m, the interval ( −3 √ log nm, 3 √ log nm )
in which we need the polynomial approximation to hold increases in length and thus the degree needed to approximate grows with m. To remedy this, we relax the approximation guarantee required from the L∞ norm to the L2 norm under the Gaussian measure. This naturally leads to approximation by Hermite polynomials as discussed in subsection F.3.
Theorem F.9. Assuming φ(x) = tanh(x) and weights w(0)k ∼ N (0, Id) , a (0) k ∼ N (0, 1) ∀k ∈ [m], with probability at least 1− e−Ω ( mc2 n2 logm ) −m−3.5 over the choice of { w
(0) k }m k=1 and { a (0) k }m k=1
the minimum eigenvalue of the G-matrix is bounded by c, i.e.
λmin(G (0)) ≤ c, where
c = max ( O ( n log n logm√
m
) ,O ( n2 √ pe − π 4 √ 2 √ p ))
and p is the largest integer that satisfies Condition 6.
Proof. In the following, for typographical reasons we will write wk instead of w (0) k . Referring to Equation 5, it suffices to find a vector ζh ∈ Sn−1 s.t. ∥∥∑n
i=1 ζ h i mi ∥∥ is small. Theorem G.2 gives the error of approximating φ′ by a polynomial h, consisting of Hermite polynomials of degree ≤ p, in the L2 norm. Let Ep denote the error function of approximation, given by Ep(x) = φ ′(x)− h(x).
From Theorem F.2, there exists ζh ∈ Sn−1 s.t. for all w and ã we have n∑ i=1 ζhi ãh(w Txi)xi = 0,
provided p satisfies Condition 6. We can use Fact C.5 to confine the maximum magnitude of ak to 3 √
logm. Thus, assuming that this condition holds true, we claim the following. Using ζh, we get
Ew∼N (0,Id),ã∼N (0,1) ∥∥∥∥∥∥ n∑ i=1 ζhi ãφ ′(wTxi)xi ∥∥∥∥∥∥ 2
= Ew∼N (0,Id),ã∼N (0,1) ∥∥∥∥∥∥ n∑ i=1 ζhi ãhp(w Txi)xi + n∑ i=1 ãζhi Ep(w Txi)xi ∥∥∥∥∥∥ 2
(24)
= Ew∼N (0,Id),ã∼N (0,1) ∥∥∥∥∥∥ n∑ i=1 ζhi ãEp(w Txi)xi ∥∥∥∥∥∥ 2
(25)
≤ Ew∼N (0,Id),ã∼N (0,1)ã 2 ∥∥∥∥∥∥ n∑ i=1 ζhi xi ∥∥∥∥∥∥ 2 n∑ i=1 ( Ep ( wTxi ))2 (26) ≤ n
n∑ i=1 { Ew∼N (0,Id) ( Ep ( wTxi ))2} (27)
= n2 Ew∼N (0,Id) ( Ep ( wTx1 ))2 . (28)
We approximate φ′ by h and use the definition of ζh in Equation 24, apply Cauchy-Schwartz in Equation 25, ‖xi‖ = 1 ∀i ∈ [n], ∥∥ζh∥∥ = 1, the linearity of expectation in Equation 26 and maximum variance of ã, given the constraint on it’s magnitude, as upperbounded by 1 in Equation 27. wTx1 follows a Gaussian distribution N (0, 1). Hence, denoting h as the error of approximation from Corollary F.7.2, we get
Ew∼N (0,Id),ã∼N (0,1) ∥∥∥∥∥∥ n∑ i=1 ζhi ãφ ′(wTxi)xi ∥∥∥∥∥∥ 2 ≤ n2 h
where h ≤ O( √ pe − π 4 √ 2 √ p ).
Applying Hoeffding’s inequality for m weight vectors wk ∼ N (0, Id) and ak ∼ N (0, 1), we get
Pr {wk}mk=1,{ak} m k=1  1m m∑ k=1 ∥∥∥∥∥∥ n∑ i=1 ζhi akφ ′(wTk xi)xi ∥∥∥∥∥∥ 2 ≤ ( n2 h + t ) ≥ 1− e− 2mt 2 9n2 log2 m −m−3.5.
In the above inequality, we use the restriction of the maximum magnitude of ak to 3 √
logm and hence, ∀k, ∥∥∥∑ni=1 ζhi akφ′ (wTk xi)xi∥∥∥ ∈ (0, 3√n√logm). Using t = max(n2 h, n logn logm√m ), c
being a constant and substituting the value of , we get the final upper bound. Thus,
m∑ k=1 ∥∥∥∥∥∥ n∑ i=1 ζhi φ ′(wTk xi)xi ∥∥∥∥∥∥ 2
2
≤ mmax ( O ( n2 h ) ,O ( n log n logm√
m
)) (29)
Using Equation 5 and the fact λmin(G) = 1mσmin(M) 2, we get the final bound.
The upper bound on minimum eigenvalue from Theorem F.8 can be rewritten as
λmin(G (0)) ≤ O ( n log (nm)e −p log ( 1+π3 √ log(nm) )) for a small constant C and p denotes the largest integer that satisfies Condition 6. Let us assume that d′ ≤ O ( log0.75 n ) , where d′ = dim ( Span {x1 . . .xn} ) . Then, we use the value of p from
Corollary F.2.1 for the next set of arguments. Substituting the value of p, we get
λmin(G (0)) ≤ O ( n log (nm)e −n1/d ′ log ( 1+π3 √ log(nm) )) Assuming m < eO ( n1/d ′) , we have
λmin(G (0)) ≤ O ( n2e −Ω ( n1/2d ′)) = e −Ω ( n1/2d ′) .
By Theorem F.9, when m > eΩ ( n1/2d ′) ,
λmin(G (0)) ≤ max ( n1.5 log (n)e −Ω ( n1/2d ′) ,O ( n2e − π 4 √ 2 n1/2d ′ )) = e −Ω ( n1/2d ′)
with high probability with respect to {wk}mk=1 and {ak} m k=1. Hence, the final bounds of minimum singular value of Gram matrix in case of tanh activation has been summarized below.
Theorem F.10. Let d′ = dim ( span {x1 . . .xn} ) ≤ O ( log0.75 n ) . Assuming φ(x) = tanh(x) and
weights w(0)k ∼ N (0, Id) , a (0) k ∼ N (0, 1) ∀k ∈ [m], the minimum eigenvalue of the G-matrix satisfies
λmin
( G(0) ) ≤ e−Ω(n 1/2d′ )
with probability at least 1− 1n3.5 with respect to the weight vectors { w (0) k }m k=1 and { a (0) k }m k=1 .
In fact, as in Theorem F.3, we can show that the smallest ( 1− 1d′ ) n eigenvalues of the matrix are small. This is captured in the following theorem.
Corollary F.10.1. Let d′ = dim ( span {x1 . . .xn} ) = O ( log0.75 n ) . Assuming φ(x) = tanh(x)
and weights w(0)k ∼ N (0, Id) , a (0) k ∼ N (0, 1) ∀k ∈ [m], then eigenvalues of the G-matrix satisfy
λk
( G(0) ) ≤ e−Ω ( n1/2d ′) ∀k ≥ ⌈ n
d′ ⌉ with probability at least 1− 1n2.5 with respect to the weight vectors { w (0) k }m k=1 and { a (0) k }m k=1 .
Proof. In the following, for typographical reasons we will write wk instead of w (0) k and ak instead of a (0) k . We give a proof outline. We will approximate φ ′ by a p-degree polynomial h as in Theorem F.8
and Theorem F.9, where p ≤ O ( n1/d ′ ) . From Theorem F.3, we get that for polynomial h, there
exits a n(1− 1d′ ) dimensional subspace U for which the following quantity√√√√√ m∑ k=1 ∥∥∥∥∥∥ n∑ i=1 ζiakh ( wTk xi ) xi ∥∥∥∥∥∥ 2 = 0
is 0, ∀ζ ∈ U. Now, we can take an orthonormal basis ζ(U) = [ ζ(1), ζ(2), ..., ζ ( n(1− 1d′ ) )] of U and
for each ζ(j), we can follow the same proof structure in Theorem F.8, Theorem F.9 and Theorem F.10 to get
1
m m∑ k=1 ∥∥∥∥∥∥ n∑ i=1 ζ (j) i akφ ′ ( wTk xi ) xi ∥∥∥∥∥∥ 2 ≤ e−Ω ( n1/2d ′)
with probability at-least 1− 1n2.5 with respect to {wk} m k=1 and {ak} m k=1. Now, for bounding singular value σk(M), for k ≥ ⌈ n d′ ⌉ , we use the following argument. We choose a subset S(n−k) of size n− k from ζ(U). This subset is a n− k dimensional subspace U′ of Rn. Each ζ ∈ U′ can be written in the form
ζ = ∑
j∈[n] : ζ(j)∈U′ αjζ
(j)
with ∑ j∈[n] : ζ(j)∈U′ α 2 j = 1. Then, for each ζ ∈ U′,
1
m m∑ k=1 ∥∥∥∥∥∥ n∑ i=1 ζiakφ ′ ( wTk xi ) xi ∥∥∥∥∥∥ 2 = 1 m m∑ k=1 ∥∥∥∥∥∥∥ n∑ i=1 ∑ j∈[n] : ζ(j)∈U′ αjζ (j) i akφ ′ ( wTk xi ) xi ∥∥∥∥∥∥∥ 2
= 1
m m∑ k=1 ∥∥∥∥∥∥∥ ∑ j∈[n] : ζ(j)∈U′ αj  n∑ i=1 ζ (j) i akφ ′ ( wTk xi ) xi  ∥∥∥∥∥∥∥ 2
≤ 1 m m∑ k=1  ∑ j∈[n] : ζ(j)∈U′ α2j   ∑ j∈[n] : ζ(j)∈U′ ∥∥∥∥∥∥  n∑ i=1 ζ (j) i akφ ′ ( wTk xi ) xi ∥∥∥∥∥∥ 2 
≤ ( n ( 1− 1
d′
)) e −Ω ( n1/2d ′) = e −Ω ( n1/2d ′) (30)
Thus, it follows from the definition of σk (M) from Fact C.7 that σk (M) ≤ √ me −Ω ( n1/4d ′)
Using λk ( G(0) ) = 1mσk (M) 2, we get the final upper bound.

heading: F.3.2 STANDARD SETTING
text: Now, we consider upper bounding the eigenvalue of the G-matrix for the standard initialization, defined in Appendix D. Theorem F.11 (Init(fanout) setting). Assuming φ(x) = tanh(x) and weights w(0)k ∼ N ( 0, 1mId ) , a (0) k ∼ N (0, 1) and b (0) k ∼ N ( 0, 1m ) ∀k ∈ [m], the minimum eigenvalue of the G-matrix is
O n  4π + 6 √ lognm m(
1 + π/3√ lognm m
)p  2 
with probability at least 1− 2 (mn)3.5
with respect to { w
(0) k }m k=1 , { a (0) k }m k=1 and { b (0) k }m k=1
, where p is the largest integer that satisfies Condition 6.
Proof. For each k ∈ [m] and i ∈ [n], wTk xi is a Gaussian random variable following N ( 0, 1m ) . Thus, there are mn Gaussian random variables and it follows from Fact C.5 that with probability
at least (
1− 2 (mn)3.5 ) with respect to {wk}mk=1, maxi∈[n],k∈[m] ∣∣wTk xi∣∣ ≤ 3√ lognmm . Now, we follow the same proof as F.8 but restricted to the range ( −3 √
lognm m , 3 √ lognm m ) to get the desired
result. Corollary F.11.1 (Init(fanout) setting). If d′ = dim ( Span {x1 . . .xn} ) ≤ O ( log0.75 n ) . Assum-
ing φ(x) = tanh(x) and weights w(0)k ∼ N ( 0, 1mId ) , a (0) k ∼ N (0, 1) and b (0) k ∼ N ( 0, 1m ) ∀k ∈ [m], the minimum eigenvalue of the G-matrix satisfies
λmin
( G(0) ) ≤ e−Ω(n 1/2d′ )
with probability at least 1 − 1n3 with respect to the weight vectors { w (0) k }m k=1 , { a (0) k }m k=1
and{ b (0) k }m k=1 .
Proof. It follows from the same proof as Theorem F.3. Theorem F.12 (Init(fanin) setting). Assuming φ(x) = tanh(x) and weights w(0)k ∼ N ( 0, 1dId ) , a (0) k ∼ N ( 0, 1m ) and b(0)k ∼ N (0, 0.01) ∀k ∈ [m], the minimum eigenvalue of the G-matrix is
λmin
( G(0) ) ≤ O n2  4π + 6 √ lognm d(
1 + π/3√ lognm d
)p  2 
with probability at least 1− 2 (mn)3.5
with respect to { w
(0) k }m k=1 , { a (0) k }m k=1 and { b (0) k }m k=1
, where p is the largest integer that satisfies Condition 6.
Proof. The proof follows from the proofs of Theorem F.8 and Theorem F.9, with the region of approximation reduced to ( −3 √
lognm d , 3 √ lognm d ) .
Corollary F.12.1 (Init(fanin) setting). If d′ = dim ( Span {x1 . . .xn} ) ≤ O ( log0.75 n ) . Assuming
φ(x) = tanh(x) and weights w(0)k ∼ N ( 0, 1dId ) , a(0)k ∼ N ( 0, 1m ) and b(0)k ∼ N (0, 0.01) ∀k ∈ [m], the minimum eigenvalue of the G-matrix satisfies
λmin
( G(0) ) ≤ e−Ω( √ dn1/2d ′ )
with probability at least 1 − 1n3 with respect to the weight vectors { w (0) k }m k=1 , { a (0) k }m k=1
and{ b (0) k }m k=1 .

heading: G UPPER BOUND ON LOWEST EIGENVALUE FOR SWISH
text: In this section, we show upper bounds on the eigenvalues for the G-matrix for the Swish activation function using techniques largely similar to the techniques uses for the tanh activation function. This is not too surprising since they satisfy the following functional identity
swish(x) = x
2
[ tanh ( x
2
) + 1 ] .
Hence
swish′ (x) = 1
2
[ 1 + x
2 tanh′
( x
2
) + tanh ( x
2
)] .
Theorem G.1. swish′(t) is approximated by a degree p polynomial gp(t) within error in the interval [−k, k] in the L∞ norm:
sup t∈[−k,k] ∣∣swish′(t)− gp(t)∣∣ ≤ where
p =  log ( 4πk+2k2 π2 ) log (1 + πk−1)  . Similarly, for the L2 approximation for swish, we proceed using the same technique as for tanh.
Theorem G.2. Let φ2(x) = swish′(x) and let φ2 be approximated by Hermite polynomials {Hek}∞k=0 of degree up to p in Equation 17, denoted by
hp(x) = p∑ k=1 c̄kHek(x).
Let Ep(x) = φ2(x)− hp(x). Then, ∫ ∞ −∞ Ep(x) 2 dµ(x; 1) ≤ O (√ pe − π 4 √ 2 √ p ) .
Using the above theorems and the techniques from the previous sections, we can upper bound the eigenvalues of the G-matrix with the swish activation f0unction. We summarize this in the following theorems.
Theorem G.3. Consider the setting of Du et al. (2019a). If d′ = dim ( Span {x1 . . .xn} ) ≤
O ( log0.75 n )
. Assuming φ(x) = swish(x) and weights w(0)k ∼ N (0, Id)∀k ∈ [m], then eigenvalues of the G-matrix satisfy
λk
( G(0) ) ≤ e−Ω ( n1/2d ′) ∀k ≥ ⌈ n
d′ ⌉ with probability at least 1− 1n2.5 with respect to the weight vectors { w (0) k }m k=1 and { a (0) k }m k=1 .

heading: H A DISCUSSION ON UPPER BOUND OF LOWEST EIGENVALUE FOR GENERAL ACTIVATION FUNCTIONS
text: In this section, we generalize the results of the previous sections upper bounding the eigenvalues of theG-matrix to a more general class of activation functions. To this end we note that the only property of the tanh and swish we used was that these functions are well-approximated by polynomials of low degree. The approximation theorems used in the previous sections can be stated under fairly general conditions on the activation functions.
For the Chebyshev approximation, it can be shown that a function with k derivatives with bounded norms can be approximated by Chebyshev polynomials of degree N with error that decays like N−k. This shows that for smooth functions the error decays faster than any inverse polynomial. Under the assumption of analyticity, this can be further improved to get exponential decay of error. We summarize this in the following theorem. Theorem H.1 (see Section 5.7 in Mason & Handscomb (2002)). Let f : [−1, 1]→ R be a function with k+ 1 continuous derivatives. Let SNf be the Chebyshev approximation of f to degree N . Then, we have
sup x∈[−1,1] ∣∣f(x)− (SNf) (x)∣∣ ≤ O (N−k) . Furthermore, if f can be extended analytically to the ellipse
Er =
{ z ∈ C : z = (w + w −1)
2 |w| ≤ r
} ,
then sup
x∈[−1,1] ∣∣f(x)− (SNf) (x)∣∣ ≤ O (r−N) . Similarly, for Hermite approximation one can state the decay of the Hermite coefficients in terms of the regularity of the derivatives, expressed in terms of inclusion of the function in certain Sobolev spaces. Also, Theorem F.6 indicates that extending the function on to the complex plane gives better convergence properties. See Thangavelu (1993) for further details.
With these general approximation theorems and techniques from the previous sections, we can extend the upper bound on the eigenvalues on activation functions satisfying sufficient regularity conditions.
I LOWER BOUND ON EIGENVALUES FOR tanh WHEN THE DIMENSION OF THE DATA IS NOT TOO SMALL
For the following proof, we assume the data generation process as follows. Assumption 3. The data is mildly generic as in smoothed analysis: e.g., xi is obtained by adding
small multiple ( σ = O ( δ
2 √ n
)) of IID standard Gaussian noise within the subspace V′ of arbitrary
initial samples x′i, with V ′ := Span{x′1, . . . ,x′n} and renormalizing to 1. Denoting the initial set of samples as X′ = { x′1, . . .x ′ n } and the noise matrix N, that has each entry coming iid from
N ( 0, σ2 ) , we have the data matrix X defined by {x1, . . .xn}, where
xi = ni + x ′ i∥∥ni + x′i∥∥
Remark. Assuming that the initial samples x′i are one-normalized, w.h.p. the norm of the noisy vectors x′i + ni are in the range (1− δ, 1 + δ) and thus, renormalization involves division by a constant in the range ( 11+δ , 1 1−δ ). Assuming that the initial samples x ′ i are 2δ separated, w.h.p. the separation between xi can be shown to be at least δ, thus satisfying Assumption 2. Assumption 4. Let d′ = span{x1, . . . ,xn}. For simplicity, we assume d = d′ i.e. x1, ...,xn lie in d′-dimensional space (otherwise we project them to d′ dimensional space using SVD) and d′ ≥ 2.
While our result here builds upon the smoothed analysis of Anderson et al. (2014), the following lemma provides a more modular approach though no new essential technical ingredient. Lemma I.1 (cf. Lemma H.1 in Oymak & Soltanolkotabi (2019)). For an activation function φ and a data matrix X ∈ Rd×n with unit Euclidean norm columns, the minimum eigenvalue of the Gram matrix G∞, satisfies the following inequality
λmin (G ∞) ≥ c̄2r ( φ′ ) λmin (( XTX ) (r+1)) , ∀r ≥ 0
where ( XTX ) (r+1) is given by (X∗r)T X∗r, X∗r ∈ Rn×dr denotes the Khatri-Rao product of matrix X and c̄r(φ′) denotes the r-th coefficient in the probabilists’ Hermite expansion of φ′.
Proof. Each element of G∞ can be expressed in the following manner.
g∞ij = Ew∼N (0,1),ã∼N (0,1)ã 2φ′ ( wTxi ) φ′ ( wTxj ) xTi xj = ∞∑ a=0 c̄2a ( φ′ ) ( xTi xj )a+1 where we use a) unit variance of ã and independence of ã and w and b) the fact that wTxi and wTxj are xTi xj correlated for a normally distributed vector w and hence, use Lemma N.4. Thus,
G∞ = ∞∑ a=0 c̄2a ( φ′ ) ( XTX ) (a+1)
Using Weyl’s inequality (Fact C.11) for the sum of PSD matrices {( XTX ) (a)}∞
a=1 , we get
G∞ c̄2r ( φ′ ) ( XTX ) (r+1) ,∀r ≥ 0
from which, the assertion follows.
Lemma I.2. Let d′ = dim span{x1, . . . ,xn}. Denote by p be an integer that satisfies( d′
p
) ≥ n. (31)
Then for any κ ∈ (0, 1), with probability at least 1− κ with respect to the noise matrix N,
σn (X ∗p) ≥ Ω ( 1√ n ( σκ np )p) .
Proof. X∗p has d′p rows and n columns. However, the number of distinct rows is given by ( d′+p−1
p
) .
This follows by counting the number of distinct terms in the polynomial (∑d′
k=1 vk )p , where {vk}d ′ k=1
is a set of d′ variables. Since, we assume that ( d′
p
) , which is lesser than this quantity, is greater than
n, the number of distinct rows is greater than the number of columns for the matrix X∗p. Let X̂∗p denotes a n× n sized square block of X∗p, that contains any random subset of size n from the set of distinct rows of X∗p as rows, such that each row represents elements of Khatri-Rao product of the form ∏ j∈[d′] x bj j , 0 ≤ bj ≤ 1 ∀j ∈ [d′], for a vector x ∈ Rd ′ . We can see that λn(X̂∗p) ≤ σn(X∗p). Hence, we will focus on the minimum eigenvalue λn(X̂∗p).
Fix k ∈ [n] and let u be the vector orthogonal to the subspace spanned by the columns of X̂∗p, except the kth column. Vector u is well-defined with probability 1. Then the distance between x̂∗pk and the span of the rest of the columns, denoted dist(x̂∗pk , X̂ ∗p −k), is given by
uT x̂∗pk = ∑ s∈[n] usgs ({ cx′kj + cnkj }d′ j=1 ) (32)
=: P ({ cnkj }d′ j=1 ) , (33)
where gs denotes a degree-p polynomial and is given by
gs ({ cx′kj + cnkj }d′ j=1 ) = ∏ j∈[d′] ( cx′kj + cnkj )bsj , 0 ≤ bsj ≤ 1 ∀j ∈ [d′], ∑ j∈[d′] bsj = p.
c denotes a constant in the range ( 11+δ , 1 1−δ ), which is the normalization factor used in Assumption 3.
Hence, Equation 32 is a degree p polynomial in variables nkj . We will apply the anticoncentration inequality of Carbery-Wright to show that the distance between any column and the span of the rest of the columns is large with high probability. The variance of the polynomial is given by
Var ( P ({ nkj }d′ j=1 )) ≥ ∑ s∈[n] |us|2 ∏ j∈[d′] E ( cx′kj + cnkj )2bsj ≥ ( σ 1 + δ )2p ≥ ( σ 2 )2p where we use the fact that‖u‖ = 1 and nkj are Gaussian variables of variance δ 2
4n . Using a minor adjustment of Fact C.8, which takes into consideration the fact that our gaussian variables are of variance δ 2
4n and the variance of the polynomial is not 1, we have
Pr  ∣∣∣∣∣P ({ nkj }d′ j=1 )∣∣∣∣∣ ≤  ≤ Cp 1/pσ
2
, C > 0 is a constant.
Using a union bound over the choice of k, we get Pr {
dist(x̂∗pk , X̂ ∗p −k) ≤ , ∀k ∈ [n]
} ≤ Cpn 1/p
σ 2 Using = (
σκ 2Cpn
)p , we get
σn
( X̂∗p ) =
1√ n min k∈[n] dist(x̂∗pk , X̂ ∗p −k) ≥ / √ n.
with probability at least 1− κ. We use Fact C.9 in the above inequality.
Theorem I.3. Let φ(x) be a constant degree p polynomial, with leading coefficient 1, and d′ = dim span{x1, . . . ,xn} ≥ Ω(n1/p). Then for any κ ∈ (0, 1) we have
λmin
( G(0) ) ≥ Ω
( 1
n
( κσ
np
)2p)
with probability at least 1− κ w.r.t. the noise matrix N and {w(0)k }mk=1, provided
m ≥ Ω
( p4pn4p+4 log ( n/κ ) log2p+3m
σ4pκ4p
) .
Proof. For a degree-p polynomial with leading coefficient 1, the (p− 1)-th coefficient in Hermite expansion of φ′ is given by 1. Also, note that Equation 31 is satisfied by p, given that d′ ≥ Ω ( n 1 p ) for a constant p. Thus, using Lemma I.1, Lemma I.2 to find minimum eigenvalue of G∞ and then applying Hoeffding’s inequality (Fact C.3) to bound the deviation of minimum eigenvalue of G(0) from G∞, we get the desired bound.
Theorem I.4. Let the activation function φ be tanh and d′ = dim span{x1, ...,xn} ≥ Ω (log n). Then for any κ ∈ (0, 1) we have
λmin
( G(0) ) ≥ Ω ( c̄2p−1 ( tanh′ ) n ( κσ np )2p)
with probability at least 1− κ w.r.t. the noise matrix N and {w(0)k }mk=1, provided
m ≥ Ω
( p4pn4p+4 log ( n/κ ) log2m
σ4pκ4p
) ,
where p denotes the smallest odd integer satisfying( d′
p
) ≥ n,
and c̄p ( tanh′ ) denotes the p-th coefficient in the probabilists’ Hermite expansion of tanh′.
Proof. p is chosen such that Equation 31 is satisfied. We use Lemma I.1, Lemma I.2 to find minimum eigenvalue of G∞ and then applying Hoeffding’s inequality (Fact C.3) to bound the deviation of minimum eigenvalue of G(0) from G∞, we get the desired bound. Now, we specify the behavior of the probabilists’ hermite expansion coefficients cp−1 ( φ′ )
for φ = tanh. Let β, the exponent of real axis convergence of tanh′, be the least upper bound on γ for which
tanh′(x) = O ( e−ν|x| γ ) , x ∈ R,
for some constant ν > 0 as|x| → ∞. We have β = 1, as tanh′(x) ∼ e−4|x| for large|x|. Hence, using Eq. 5.15 in Boyd (1984) for the coefficients c̄k in the probabilists’ Hermite expansion of tanh′ we have
c̄k = 2
(2k + 1) 1/4
Θ ( e− π 4 (2k+1) 1 2 ) , as k →∞. (34)
We remark that Boyd (1984) uses physicists’ Hermite expansion. Following similar technique as in Corollary F.7.1 and Theorem F.7, we can get the exact similar form of probabilists’ Hermite expansion coefficients c̄k ( tanh′ ) .
Thus for p = O(log n), we have c̄p = Ω̃ ( e−c ′√logn ) .
Corollary I.4.1. Let φ(x) be the activation function tanh and d′ = span{x1, ...,xn} = Θ (log n). Then,
λmin
( G(0) ) ≥ ( σ
n )O(logn) with probability at least 1 − 1/poly(n) − e−Ω ( m log2 m ( σn ) O(logn) )
w.r.t. the noise matrix N and {w(0)k }mk=1.
Corollary I.4.2. Let the activation be tanh and d′ = dim span{x1, ...,xn} = Θ (nγ), for a constant γ ≥ Ω ( log logn
logn
) . Then for any κ ∈ (0, 1) we have
λmin
( G(0) ) ≥ Ω
( e−c ′√logn
n
( κσ
np
)2p)
with probability at least 1− κ w.r.t. the noise matrix N and {w(0)k }mk=1, provided
m ≥ Ω
( p4pn4p+4 log ( n/κ ) log2m
σ4pκ4p
) ,
where p is the smallest ”odd” integer satisfying( d′
p
) ≥ n,
and c′ is a constant. p can be shown to lie in the range,
1 γ ≤ p ≤ 2
γ − 2logn .
J DEPTH HELPS FOR tanh
Let the neural network under consideration be
F ( x;a, { W(l) }L l=1 ) = cφ√ m m∑ k=1 akφ (( w (L) k )T x(L−1) ) where x(l) ∈ Rm ∀l ≥ 1 and x(l) ∈ Rd for l = 0, is defined recursively by its components as follows.
x (l) k = cφ√ m φ
(( w
(l) k
)T x(l−1) ) ∀k ∈ [m],∀l ≥ 1
x (0) k = xk ∀k ∈ [d].
cφ = ( Ez∼N (0,1)φ(z)2 )− 12 , with φ following the following three properties.
• φ(0) = 0. • φ is α-Lipschitz. • Ez∼N (0,1) φ(z) = 0
The weight matrices and the output weight vector are given by { W(l) }L i=1 and a respectively, where a ∈ Rm, W(l) ∈ Rm×m for l ≥ 2 and W(l) ∈ Rm×d for l = 1. Now, we define the Gram matrix G(0) as follows (cf. Eq. 13 in Du et al. (2019b)).
g (0) ij =
1
m ∑ k∈[m] a2kφ ′ (( w (L) k )T x (L−1) i ) φ′ (( w (L) k )T x (L−1) j ) with its counterpart G∞, when m→∞, given by
g∞ij = Ew∼N (0,I),a∼N (0,1)a2φ′ ( wTx (L−1) i ) φ′ ( wTx (L−1) j ) Lemma J.1. For a small constant > 0, if m ≥ Ω ( max ( 2L log2 m 2 log nL, (nL) 2/7 )) , then with
probability at least 1− e−Ω(m 2/2L log2 m) − nLm3.5 we have∥∥∥x(l)i ∥∥∥ ∈ (1− , 1 + ) ∀i ∈ [n], l ∈ {0, . . . , L− 1} . (35)
Proof. We will use induction on l to show that for any given i with appropraite probability we have∥∥∥x(l)i ∥∥∥ ∈ (1− (4c2φα2)l−L , 1 + (4c2φα2)l−L ) ∀l ∈ [L]. We will apply union bound over the choice of i to derive the result for all i ∈ [n]. The result holds true for l = 0 by Assumption 1. Let’s assume that the result holds true for l = t. For a randomly picked vector w ∼ N (0, I), wTx(t)i follows a normal distribution with mean 0 and standard deviation∥∥∥x(t)i ∥∥∥ ∈ (1− t, 1 + t), where t = (4c2φα2)t−L . Denote unit normalized form of x(t)i as x
(t) i . Since, there are m random Gaussian vectors in the matrix W (t+1), leading to formation of m Gaussians along the dimension of W(t+1)Tx(t)i , we can apply Fact C.5 to confine each dimension of
W(t+1)Tx (t) i to the range
( −3 √ logm ∥∥∥x(t)i ∥∥∥ , 3√logm∥∥∥x(t)i ∥∥∥) with probability at least 1− 1m3.5 .
Assuming that this holds true, we can claim the following: First,
Pr W(t+1)  ∣∣∣∣∣∣ 1m m∑ k=1 c2φφ ( w (t+1)T k x (t) i )2 − Ew∼N (0,I)c2φφ ( wTx (t) i )2∣∣∣∣∣∣ ≥ α2c2φ t  ≤ 2e−Ω( m 2tlog2 m)
(36)
where we use Hoeffding’s inequality (Fact C.3) and bound on w(t)Tk x (t) i and the α-Lipschitzness of the activation φ to put a bound on ∣∣∣φ(w(t+1)Tk x(t)i )∣∣∣ to be used in Hoeffding’s inequality.
Second, using Taylor expansion of φ, the deviation of Ew∼N (0,I)c2φφ(w Tx (t) i ) 2 from Ez∼N (0,1) c2φφ(z)2 can be bounded in the following manner.
Ew∼N (0,I) c2φ φ(wTx (t) i ) 2 = Ew∼N (0,I) c2φ φ ( wTx (t) i )2 + ′ = Ez∼N (0,1) c2φ φ(z)2 + ′ (37)
where ′ ∈ ( −2c2φα2 t, 2c2φα2 t ) . This follows from the following set of equations.
φ(wTx (t) i )
2 = φ ( wTx
(t) i )2 + 2
∫ 1 s=0 φ ( (1− s)wTx(t)i + sw Tx (t) i ) φ′ ( (1− s)wTx(t)i + sw Tx (t) i )( wTx (t) i −w Tx (t) i ) ds
≤ φ ( wTx
(t) i )2 + 2 t(1 + t)α 2 ( wTx (t) i )2 . (38)
In the inequality above we used the facts that φ is α-Lipschitz, and since φ(0) = 0 by assumption, φ(z) ≤ α|z|. This gives
Ew∼N (0,I) c2φ φ(wTx (t) i ) 2 ≤ Ew∼N (0,I) c2φ φ ( wTx (t) i )2 + 2 t(1 + t)α 2c2φ Ew∼N (0,I) ( wTx (t) i )2 ≤ Ew∼N (0,I) c2φφ ( wTx (t) i )2 + 2 t(1 + t)α 2c2φ.
Third, we use the definition of cφ and the α-Lipschitzness of φ, to bound the error due to restricting the maximum magnitude of wTx(t)i to 3 √ logm ∥∥∥x(t)i ∥∥∥, to get
E w∼N (0,I): ∣∣∣wTx(t)i ∣∣∣≤3√logm c2φφ ( wTx (t) i )2 = Ew∼N (0,I)c 2 φφ ( wTx (t) i )2 +O
(√ logm
m
)
= 1 +O
(√ logm
m
) (39)
This can be shown by the following equation.∣∣∣∣Ew∼N (0,I):∣∣∣wTx(t)i ∣∣∣≤3√logmc2φ φ(wTx(t)i )2 − Ew∼N (0,I)c2φ φ(wTx(t)i )2 ∣∣∣∣ ≤ 2 1√2π ∫ ∞ 3 √ logm φ(x)2e−x 2/2dx
≤ α22 1√ 2π ∫ ∞ 3 √ logm x2e−x 2/2dx
≤ α2 √ logm
m (40)
Combining Equation 36, Equation 37 and Equation 39, we get that with probability at least 1 − 2e −Ω ( m 2t log2 m ) −m−7/2,
∥∥∥x(t+1)i ∥∥∥ =  1 m m∑ k=1 c2φφ(w (t)T k xi) 2 1/2 ∈ (1− 4α2c2φ t, 1 + 4α2c2φ t) . We use the union bound for all the induction steps and examples to get the final desired bounds.
Lemma J.2. If for a pair i, j ∈ [n], x(l−1)Ti x (l−1) j = ρ s.t. |ρ| ≤ 1 − δ and if Equation 35 holds, then for all small > 0,∣∣∣x(l)Ti x(l)j ∣∣∣ ≤ 3 (1 + 2 ) α2c2φ+(1 + 2 ) max ( 1 + c
2
( δ
n2
) +
1− c 2
( δ
n2
)2 , 1 + c
2 |ρ|+ 1− c 2 |ρ|2 )
with probability at least 1−m−7/2 − e−Ω(mδ 2/α4n4 log2 m) w.r.t. initialization, where c denotes the ratio c̄ 2 1(φ)∑∞
a=1 c̄ 2 a(φ)
.
Proof. From Equation 35, for a small constant , ∥∥∥x(l−1)i ∥∥∥ ∈ (1− , 1 + ) ,∀i ∈ [n] with high
probability. For a vector x set x := x/‖x‖; thus we will use x(l−1)i for x (l−1) i / ∥∥∥x(l−1)i ∥∥∥. We use Fact C.5 to restrict the maximum magnitude of the 2m Gaussians wTk x (l−1) i and w T k x (l−1) j for k ∈ [m] to 3 √ logm ∥∥∥x(l−1)i ∥∥∥ and 3√logm∥∥∥x(l−1)j ∥∥∥ respectively. Assuming that this condition holds, we have
x (l)T i x (l) j = c 2 φ
1
m ∑ k∈[m] φ ( w (l)T k x (l−1) i ) φ ( w (l)T k x (l−1) j ) = c2φ 1
m ∑ k∈[m] φ ( w (l)T k x (l−1) i ) φ ( w (l)T k x (l−1) j ) + ′ (41)
= c2φEw∼N (0,I)φ ( w (l)T k x (l−1) i ) φ ( w (l)T k x (l−1) j ) + ′ + ′′ (42)
= c2φ ∞∑ a=0 c̄2a (φ) ρ a + ′ + ′′ + ′′′. (43)
We get Equation 41 along the lines of Equation 38: we use 1-st order Taylor expansion of φ ( wTk x (l−1) i ) around wTk x (l−1) i and φ ( wTk x (l−1) j ) around wTk x (l−1) j , α-Lipschitzness of φ and
upper and lower bounds of ∥∥∥x(l−1)i ∥∥∥ and∥∥∥x(l−1)j ∥∥∥ from Lemma J.1 to get
φ(wTk x (l−1) i )φ(w T k x (l−1) j ) = φ ( wTk x (l−1) i ) φ(wTk x (l−1) j )
+ ∫ 1 s=0 φ(wTk x (l−1) j )φ ′ ( (1− s)wTk x (l−1) i + sw T k x (l−1) i )( wTk x (l−1) i −w T k x (l−1) i ) ds
+ ∫ 1 t=0 φ(wTk x (l−1) i )φ ′ ( (1− t)wTk x (l−1) j + tw T k x (l−1) j )( wTk x (l−1) j −w T k x (l−1) j ) dt
+ ∫ 1 s=0 ∫ 1 t=0 φ′ ( (1− s)wTk x (l−1) i + sw T k x (l−1) i )( wTk x (l−1) i −w T k x (l−1) i ) φ′ (
(1− t)wTk x (l−1) j + tw T k x (l−1) j )( wTk x (l−1) j −w T k x (l−1) j ) dsdt
≤ φ ( wTk x (l−1) i ) φ ( wTk x (l−1) j ) + α2 ( 2 (1 + ) + 2(1 + )2 )∣∣∣wTk x(l−1)i ∣∣∣∣∣∣wTk x(l−1)j ∣∣∣ . (44) In the inequality above we used the facts that φ is α-Lipschitz, and since φ(0) = 0 by assumption, φ(z) ≤ α|z|. This gives
1
m m∑ k=1 c2φφ(w T k x (l−1) i )φ(w T k x (l−1) j ) ≤ 1 m m∑ k=1 c2φφ(w T k x (l−1) i )φ(w T k x (l−1) i )
+ α2 ( 2 (1 + ) + 2(1 + )2 ) 1 m m∑ k=1 c2φ ∣∣∣wTk x(l−1)i ∣∣∣∣∣∣wTk x(l−1)j ∣∣∣ ≤ 1 m m∑ k=1 c2φφ(w T k x (l−1) i )φ(w T k x (l−1) i ) + 4α 2c2φ ( 2 (1 + ) + 2(1 + )2 ) .
In the last step, we use Hoeffding’s inequality to bound the deviation of 1 m ∑m k=1 c 2 φ ∣∣∣wTk x(l−1)i ∣∣∣∣∣∣wTk x(l−1)j ∣∣∣ from Ew∼N (0,I) c2φ∣∣∣wTx(l−1)i ∣∣∣∣∣∣wTx(l−1)j ∣∣∣ and using standard gaussian moments, we can show that that Ew∼N (0,I)
∣∣∣wTx(l−1)i ∣∣∣∣∣∣wTx(l−1)j ∣∣∣ is at-most 4. Thus, combining everything,we get
′ ∈ ( −20 α2c2φ, 20 α2c2φ ) with probability at least 1−e−Ω(m/ log
2 m). In Equation 42, we use Hoeffding’s inequality (Fact C.3), α-Lipschitzness of φ and bound for the magnitude of the 2m gaussians wTk x (l−1) i and w T k x (l−1) j to get ′′ ∈ (−τ, τ) where
τ =  1−c 2 |ρ| ( 1−|ρ| ) , if |ρ| ≥ δn2 .
1−c 2 δ n2 ( 1− δn2 ) , otherwise.
with probability at least 1 − e− ( Ω(mδ2/α4n4 log2 m) )
. Note that, the minimum value of τ is 1−c
2 δ n2 ( 1− δn2 ) . The reason of using this form of τ will be discussed below. We use Lemma N.4 in
Equation 43, with ρ00 = ∥∥∥x(l−1)i ∥∥∥2 , ρ11 =∥∥∥x(l−1)j ∥∥∥2 and ρ01 = ρ∥∥∥x(l−1)i ∥∥∥∥∥∥x(l−1)j ∥∥∥. This follows
from the fact that for a random normal vector w ∼ N (0, I), wTx follows a normal distribution with mean 0 and variance‖x‖2 and the covariance of wTx and wTy is xTy for two vectors x and y. We
have an additional error term ′′′ ∈ ( − √
logm m , √ logm m ) owing to the condition that ∣∣∣wT x̄(l−1)i ∣∣∣ must be at most 3 √ logm (proof will follow exactly along the lines of Equation 40).
Let us now focus on the quantity R (ρ) for the activation function cφφ(.), defined in Fact N.2. From the definition of cφ, it follows that c2φ = 1∑∞ a=1 c̄ 2 a(φ)
. Thus, we have ∣∣R(ρ)∣∣ ≤ R(|ρ|) ≤ R(1) = 1,
which comes from the properties of R, as given in Fact N.2. Again, we have ∣∣R(ρ)∣∣ ≤ R(|ρ|) ≤ c2φ ∞∑
a=1
c̄2a (φ)|ρ| 2 + c2φc 2 1 (φ)
( |ρ| −|ρ|2 ) = ( |ρ|+ c̄ 2 1 (φ)∑∞
a=1 c̄ 2 a(φ)
( 1−|ρ| )) |ρ|
Thus,∣∣∣x(l)Ti x(l)j ∣∣∣ ≤ ∣∣ ′′∣∣+∣∣ ′∣∣+∣∣ ′′′∣∣+∣∣R(ρ)∣∣ ≤ 6 α2c2φ + max ( 1 + c
2
( δ
n2
) +
1− c 2
( δ
n2
)2 , 1 + c
2 |ρ|+ 1− c 2 |ρ|2 )
(45)
where c denotes the ratio c̄ 2 1(φ)∑∞
a=1 c̄ 2 a(φ)
. In the equation above, we can see that the form of τ = max ∣∣ ′∣∣
has been chosen so that R(|ρ|) + ∣∣ ′∣∣ ≤ 12 (R(|ρ|) +|ρ|) Thus,∣∣∣x(l)Ti x(l)j ∣∣∣ ≤ 6 (1 + 2 ) α2c2φ + (1 + 2 ) max ( 1 + c
2
( δ
n2
) +
1− c 2
( δ
n2
)2 , 1 + c
2 |ρ|+ 1− c 2 |ρ|2 )
(46) where we use the bound on ∥∥∥x(l)i ∥∥∥ from Equation 35.
Lemma J.3. ∀i, j ∈ [n], i 6= j, if xTi xj ≤ 1− δ, then x (L−1)T i x (L−1) j ≤ , where
Ω
( δ
n2(1− c)
) ≤ ≤ 1− Ω ( δ
n2(1− c)
) ,
and
L ≥ 2 1− c max
( Ω ( log 1
δ
) ,Ω ( log 1 )) ,
with probability at least 1−Ω (
1 m3
) , provided m ≥ Ω ( 2Ln2α4c4φ log (n 2L) log2 m
δ2
) , , where c denotes
the ratio c̄ 2 1(φ)∑∞
a=1 c̄ 2 a(φ)
.
Proof. Applying Lemma J.2 with = δ 20n2α2c2φ , we have for each layer l ∈ [L] and i, j ∈ [n]; i 6= j,∣∣∣x(l)Ti x(l)j ∣∣∣ ≤ f (∣∣∣x(l−1)Ti x(l−1)j ∣∣∣) holds with probability 1 − Ω ( 1 m3 ) , provided m ≥ Ω ( 2Ln4α4c4φ log (n 2L) log2 m δ2 ) . Here function
f : R→ R is s.t. for ρ ∈ R,
f(ρ) = f̂ (ρ) , if|ρ| ≥ δ n2 .
1+c 2 ( δ n2 ) + 1−c2 ( δ n2 )2 + δn2 , otherwise.
where function f̂ is defined as
f̂ (ρ) = 1 + c
2 ρ+ 1− c 2 ρ2 + δ n2
Thus, ∣∣∣x(L)Ti x(L)j ∣∣∣ ≤ f ◦ f . . . ◦ f︸ ︷︷ ︸ L times (∣∣∣x(0)Ti x(0)j ∣∣∣) Let’s now focus on the function f . It can be seen that for the function f̂ , 2δn2(1−c) and 1− 2δ n2(1−c) are two fixed points, and starting from any positive ρ(0) strictly less than 1− 2δn2(1−c) and following fixed point algorithm leads to convergence to the point 2δn2(1−c) . Since, f̂ equals the function f till the convergence point, the rate of convergence of fixed point algorithm for the function f is well approximated by the rate of convergence for the function f̂ . Also, the rate of convergence of f̂ is equal to the rate of convergence of the function f̃ : R→ R defined for each ρ ∈ R as
f̃(ρ) = 1 + c
2 ρ+ 1− c 2 ρ2.
Lemma J.4 shows that starting at ρ(0) = 1− δ, the number of fixed point iteration steps to reach for function f̃ is given by 21−c max ( Ω log ( 1 δ ) ,Ω log ( 1 )) . Hence, from this argument, if ∣∣∣x(0)Ti x(0)j ∣∣∣ ≤ 1− δ and L ≥ 21−c max ( Ω ( log 1δ ) ,Ω ( log 1 )) , the quantity
∣∣∣x(L)Ti x(L)j ∣∣∣ becomes less than . Lemma J.4. For ρ ∈ R, define the function f̃ : R→ R by
f̃(ρ) = aρ+ (1− a)ρ2
where a is a constant in (0, 12 ). Starting at ρ (0) = 1− δ, the number of fixed point iteration steps to reach is given by 11−a max ( Ω ( log 1δ ) ,Ω ( log 1 )) .
Proof. The function f̃ has fixed points 0 and 1, but it’s easy to see that starting at any point below 1, fixed point iteration converges to 0; we want to understand the speed of convergence. We will divide the fixed point iterate’s path into two sub-paths (a) movement from 1− δ to 1− b (b is a small constant) and (b) movement from 1− b to .
• Movement from 1−δ to 1− b :. We will divide the path into subpaths (1−2tδ, 1−2t−1δ), where t is an integer in (0, log bδ ). We show that ∀t ≤ O ( log bδ ) , the number of iterations
to reach from 1− 2t−1δ to 1− 2tδ can be upper bounded by 11−a . The number of iterations of function f̃ to go from (1−2t−1δ, 1−2tδ) is at most the number of iterations of the linear function f̂ : R→ R defined by
f̂ (ρ) = ( 1− (1− a)2t−1δ ) ρ.
The number of fixed point iterations of f̂ to go from ( 1− 2t−1δ ) to ( 1− 2tδ ) is given by
log 1−2 t−1δ
1−2tδ log(1−(1−a)2t−1δ) , which can be shown to be less than 2 2 tδ−2t−1δ (1−a)2t−1δ = 2 1−a using Taylor expansion of log function. Thus, the total number of iterations involved in the entire path is upper bounded by 21−a log b δ .
• Movement from 1− b to : The number of iterations of f̃ is t most that of a linear function f̂ in the domain (0, 1− b) defined by
f̂(ρ) = ( 1− (1− a)b ) ρ.
The number of iterations of f̂ to go from (1− b) to is given by log 1−b
log 1 1−b(1−a)
, which upper
bounded by 1b(1−a) log 1−b , for small enough constant b.
Thus, summing the number of steps needed in the two subpaths leads to the desired quantity.

heading: Theorem J.5. If
text: L ≥ 2 1− c max
( Ω ( log 1
δ
) ,Ω ( log 2n
log n
)) ,
then
λmin
( G(0) ) ≥ Ω ( c̄2Θ(logn) ( φ′ )) −O ( δ
n ) with probability at least 1 − Ω ( 1 m3 ) , provided m ≥ Ω ( 2Ln4α4c4φ log (n 2L) log2 m δ2 ) , where c̄k ( φ′ )
denotes the kth order coefficient in the probabilists’ Hermite expansion of φ′ and c denotes the ratio c̄21(φ)∑∞ a=1 c̄ 2 a(φ) .
Proof. Assuming Equation 35 with = δ n2c2φα 2 , using Lemma I.1 we get
λmin (G ∞) ≥ c̄2Θ(logn) ( φ′ ) λmin ((X(L))∗ logn)T (X(L))∗ logn + ′ + ′′ (47)
where X (L) denotes a m×n matrix, with its ith column containing x(L)i , which is the unit normalized form of x(L)i , ( X (L) )∗r denotes its order rth Khatri–Rao power. There are two error terms ′ and ′′
because of two reasons (a) norm of x(L)i is away from 1 (b) magnitude of w Tx (l) i is restricted to 3 √ logm. Following the line of proof of Equation 38, magnitude of ′ can be bounded toO ( nc2φα 2 ) .
Also, following the line of proof of Equation 40, magnitude of ′′ can be bounded to n √
logm m . Now,
we make the following claims.
First, xTi xj , for any i, j ∈ [n] with i 6= j, can be shown to be at most to 1− δ, using Assumption 2.
Second, if xTi xj = ρ s.t. |ρ| ≤ 1 − δ, applying Lemma J.3 shows that ∣∣∣∣(x(L)i )T x(L)j ∣∣∣∣ ≤ ̃, for a
small constant ̃, provided L ≥ 21−c max ( Ω ( log 1δ ) ,Ω ( log 1̃ )) , with high probability. Third, if for any i, j ∈ [n], ( x
(L) i
)T x
(L) j = ρ
′ < 1, then we can see that ((
x (L) i
)∗r)T ( x
(L) j
)∗r =
ρ′r, where x∗r denotes the order-r Khatri–Rao product of a vector x.
Combining these claims, we get the following.
First, The diagonal elements of the matrix (( X (L) )∗ logn)T ( X (L) )∗ logn are equal to 1. Second,
the non diagonal element at row i and column j of the matrix (( X (L) )∗ logn)T ( X (L) )∗ logn is given by ((
x (L) i
)∗ logn)T ( x
(L) i
)∗ logn , whose magnitude is bounded by ̃logn. Hence, if
L ≥ 2 1− c max
( Ω ( log 1
δ
) ,Ω ( log 2n
log n
)) ,
each non diagonal element’s absolute value becomes less than 12n and so the absolute sum of non diagonal elements is at least 12 away from the absolute value of the diagonal element, for each row of
the matrix (( X(L) )∗ logn)T ( X(L) )∗ logn . Using Fact C.10, we get for r = log n,
λmin
( X(L)∗rTX(L)∗r ) ≥ 1
2 (48)
Combining the value of ′, value of ′′ and Equation 48 gives us the minimum eigenvalue of G∞. Since,
λmin
( G(0) ) ≥ λmin (G∞)− ∥∥∥∥(G∞ −G(0))∥∥∥∥ F ,
we use Hoeffding’s inequality to bound the magnitude of each element of ( G∞ −G(0) ) to
λmin (G ∞) /2n and hence, get a bound on λmin ( G(0) ) .
Theorem J.6. If φ = tanh and
L ≥ 2 1− c max
( Ω ( log 1
δ
) , ( log 2n
log n
)) ,
then
λmin
( G(0) ) ≥ e −Ω ( log 1 2 n ) 1/poly(n)
with probability at least 1 − Ω (
1 m3
) , provided m ≥ Ω ( 2Ln4 log (n2L) log2 m
δ2
) , for an arbitrary
constant > 0. The constant c denotes the ratio c̄ 2 1(tanh)∑∞
a=1 c̄ 2 a(tanh)
.
Proof. The proof follows from Theorem J.5, with the bound on Hermite coefficients for tanh′ from Eqn. (34).
We re-state the rate of convergence theorem from Du et al. (2019b) and use our bounds on minimum eigenvalue of the gram matrix to give a more finer version of the theorem.
Theorem J.7 (Thm 5.1 in Du et al. (2019b)). Assume that Assumption 1 and Assumption 2 hold true,|yi| = O(1) ∀i ∈ [n] and the number of neurons per layer satisfy
m ≥ Ω 2O(L) max  n 4 λ4min ( G(0) ) , n κ , n2 log ( Ln κ ) λ2min ( G(0) )   .
Then, if we follow a Gradient Descent algorithm with step size
η = O λmin ( G(0) ) n22O(L)  , with probability at least 1− κ over the random initialization, the following holds true ∀t ≥ 1.
∥∥∥y − u(t)∥∥∥2 ≤ 1− ηλmin ( G(0) ) 2  t∥∥∥y − u(0)∥∥∥2 .
Thus, refining the above theorem with our computed bounds for λmin ( G(0) ) > O( 1n ), we get the following. Theorem J.8. If φ = tanh,
L ≥ 2 1− c max
( Ω ( log 1
δ
) , ( log 2n
log n
)) ,
and the number of neurons per layer satisfy
m ≥ Ω 2O(L) max{n8, n κ , n4 log ( Ln κ )} , then, if we follow a Gradient Descent algorithm with step size
η ≤ O (
1
n32O(L)
) ,
with probability at least 1− κ over the random initialization, the following holds true ∀t ≥ 1.∥∥∥y − u(t)∥∥∥2 ≤ (1− η 2n )t∥∥∥y − u(0)∥∥∥2 . The constant c denotes the ratio c̄ 2 1(tanh)∑∞
a=1 c̄ 2 a(tanh)
.

heading: K LOWER BOUND ON LOWEST EIGENVALUE FOR NON-SMOOTH FUNCTIONS
text: For α ∈ (−1, 1) define the activation function φ by
φ(x) = φ1(x)Ix<α + φ2(x)Ix≥α.
We show that the minimum singular value of the G-matrix is at least inverse polynomially large in n and δ, provided φ1 and φ2 satisfy the following properties for some positive integer r. We denote this condition by Jr.
• φ1, φ2 ∈ Cr+1 in the domains (−∞, α] and [α,∞), respectively. • The first (r + 1) derivatives of φ1 and φ2 are upper bounded in magnitude by 1 in (−∞, α]
and [α,∞) respectively.
• For 0 ≤ i < r, we have φ(i)1 (α) = φ (i) 2 (α). • ∣∣∣φ(r)1 (α)− φ(r)2 (α)∣∣∣ = 1, i.e. the r-th derivative has a jump discontinuity at α.
In the following we consider J1 and J2. The results can be easily generalized to higher r but with lower bound degrading as n−2 r .
K.1 J1: THE FIRST DERIVATIVE IS DISCONTINUOUS AT A POINT

heading: K.1.1 DZPS SETTING
text: Recall that this setting was defined in section 2. ReLU, SELU and LReLU satisfy the conditions for the following theorem. The data set {(xi, yi)}ni=1, for xi ∈ Rd and yi ∈ R is implicitly understood in the theorem statements below.
Theorem K.1. Let the condition on φ be satisfied for r = 1. Assume that w(0)k ∼ N (0, Id) and a(0)k ∼ N (0, 1) ∀k ∈ [m]. Then, the minimum singular value of the G-matrix satisfies
λmin
( G(0) ) ≥ Ω ( δ
n3
) ,
with probability at least 1 − e−Ω(δm/n 2) with respect to {w(0)k }mk=1 and {a (0) k }mk=1, given that m satisfies
m ≥ Ω
( n3
δ log
n
δ1/4
) .
Proof. In the following, we will write wk instead of w (0) k and ak instead of a (0) k . Consider the following sum for an arbitrary unit vector ζ and a random standard normal vector w: n∑ i=1 ζi φ ′ ( wTxi ) xi.
To lower bound the lowest eigenvalue of the G-matrix, we will give a lower bound on the norm of this vector. In order to do this, we use the following claim whose proof is deferred to later in the section.
Claim K.2. For ζ ∈ Sn−1, let
f(w) = n∑ i=1 ζi φ ′ ( wTxi ) xi.
Then we have
Pr w∼N (0,Id)
(∥∥f(w)∥∥ 2 ≥ 0.1√
n
) ≥ Ω ( δ
n2
) .
From this claim, we have
Pr w∼N (0,Id)  ∥∥∥∥∥∥ n∑ i=1 ζi φ ′ ( wTxi ) xi ∥∥∥∥∥∥ 2 ≥ 0.1√ n  ≥ Ω( δ n2 ) .
Hence,
Pr w∼N (0,Id),ã∼N (0,1)  ∥∥∥∥∥∥ n∑ i=1 ãζi φ ′ ( wTxi ) xi ∥∥∥∥∥∥ 2 ≥ 0.1√ n  ≥ Ω( δ n2 ) .
owing to the fact that for a standard normal variate ã, |ã| is at least 1 with probability at least 0.2 using Fact C.1. Applying the Chernoff bounds, we have
Pr {Wk}mk=1,{ak} m k=1  1 m m∑ k=1 ∥∥∥∥∥∥ n∑ i=1 ζiakφ ′ ( wTk xi ) xi ∥∥∥∥∥∥ 2
2
≥ 10 −3δ
n3  ≥ 1− e−Ω( δmn2 ). To get the bound for all ζ ∈ Sn−1, we use an -net argument with = Θ (√ δ
n2
) and -net size ( 1 )n .
This gives that
1
m m∑ k=1 ∥∥∥∥∥∥ n∑ i=1 ζiφ ′ ( wTk xi ) xi ∥∥∥∥∥∥ 2
2
≥ Ω ( δ
n3 ) holds for all ζ ∈ Sn−1 with probability at least
1− ( n2√ δ )n e −Ω ( δm cn2 ) ≥ 1− e−Ω ( δm n2 )
with respect to {wk}mk=1 and {ak} m k=1, assuming that m ≥ Ω
( n3
δ log n4 δ
) . Thus, using the fact that
λmin
( G(0) ) = 1mσmin (M) 2, we get the final bound.
Corollary K.2.1. Let the activation be ReLU, then
λmin
( G(0) ) ≥ Ω ( δ
n3 ) with probability at least 1 − e−Ω ( δm n2 ) with respect to { w
(0) k }m k=1 and { a (0) k }m k=1
, given that m satisfies
m ≥ Ω
( n3
δ log
n
δ1/4
) .
We now move on to showing the main claim required in the Theorem K.1. Claim K.2 is an adaptation of (Allen-Zhu et al., 2019, Claim 6.4) with a slightly different choice of parameters and exposition.
Proof of Claim K.2 . Let i∗ denote arg maxi∈[n] ζi. We split vector w into two independent weight vectors, as follows
w = w′ + w′′, w′ = ( Id − xi∗xTi∗ ) w − √ 1− θ2g1xi∗ ,
w′′ = θg2xi∗ , (49)
where g1 and g2 are two independent Gaussian random variables following N ( 0, 1− θ2 ) and
N ( 0, θ2 ) respectively and we set θ = δn2 .
Let E denote the following event.
E = {∣∣∣w′Txi∗ − α∣∣∣ < δ 10n2 and ∣∣∣w′Txi − α∣∣∣ > δ 4n2 ∀i ∈ [n] \ {i∗} and |θg2| ∈ ( δ 9n2 , δ 5n2 )} .
Assuming event E occurs, for i = i∗ we have∣∣∣w′Txi∗ − α∣∣∣ ≤ δ 10n2 , ∣∣∣w′′Txi∗ ∣∣∣ = ∣∣∣θg2xTi∗xi∗ ∣∣∣ ≥ δ9n2 , and for ∀i 6= i∗ we have∣∣∣w′Txi − α∣∣∣ > δ 4n2 , ∣∣∣w′′Txi∣∣∣ = ∣∣∣θg2xTi∗xi∣∣∣ ≤ δ5n2 . Hence, conditioned on E , for i 6= i∗ we have IwTxi≥α = Iw′Txi≥α always and IwTxi∗≥α 6= Iw′Txi∗≥α with probability 1/2. Conditioned on E and using triangle and Cauchy–Schwartz inequalities we get
‖ ∑
i∈[n],i6=i∗ ζi φ ′(wTxi)xi − ∑ [n],i6=i∗ ζi φ ′(w′Txi)xi‖2
≤ ∑
i∈[n],i6=i∗ ‖ζixi‖2 ∣∣∣φ′(wTxi)− φ′(w′Txi)∣∣∣ ≤
 ∑ i∈[n],i6=i∗ ‖ζixi‖22 1/2 ∑ i∈[n],i6=i∗ (φ′(wTxi)− φ′(w′Txi))2 1/2
=  ∑ i∈[n],i6=i∗ (φ′(wTxi)− φ′(w′Txi))2 1/2
≤  ∑ i∈[n],i6=i∗ ∣∣∣wTxi −w′Txi∣∣∣2 1/2 (50)
≤ O (√ n ) δ
5n2 = O
( δ
5n1.5
) ,
where we use our assumption that ∣∣φ′′(x)∣∣ ≤ 1 for x ∈ R \ {α} in Inequality 50. Conditioning on E was used in concluding that either φ′(wTxi) − φ′(w′Txi) = φ′1(wTxi) − φ′1(w′Txi) or φ′(wTxi)− φ′(w′Txi) = φ′2(wTxi)− φ′2(w′Txi). In other words, φ′1 and φ′2 “don’t mix”. Since∣∣limz→α− φ′(z)− limz→α+ φ′(z)∣∣ = 1 and|ζi∗ | ≥ 1√n , we have
Pr g2 (∥∥∥∥ζi∗ φ′ (wTxi∗)xi∗ − ζi∗ φ′ (w′Txi∗)xi∗∥∥∥∥ 2 ≥ 1√ n ( 1− δ 5n2 ) ∣∣∣∣ E ) = 1 2 .
To see this, note that given conditioned on E , with probability 0.5 with respect to g2, wTxi is going to cross the jump discontinuity at α and thus, φ′ is going to change by at least 1, minus the maximum movement on either side of α, which is bounded. Thus,
Pr w  ∥∥∥∥∥∥ n∑ i=1 ζiφ ′ ( wTxi ) xi ∥∥∥∥∥∥ 2 ≥ 0.1√ n ∣∣∣∣∣ E  ≥ 0.5.
We now need to show that E occurs with high probability. To do this, we state the following claim that we prove later.
Claim K.3. Let all the variables be as in Claim K.3. Then,
Pr w′ (∣∣∣w′Txi∗ − α∣∣∣ ≤ δ 10n2 and ∣∣∣w′Txi − α∣∣∣ ≥ δ 4n2 ∀i 6= i∗ ) ≥ Ω ( δ n2 √ 1− θ2 ) .
From Claim K.3, we have
Pr w′ (∣∣∣w′Txi∗ − α∣∣∣ ≤ δ 10n2 and ∣∣∣w′Txi − α∣∣∣ ≥ δ 4n2 ∀i 6= i∗ ) ≥ Ω ( δ√ 1− θ2n2 ) .
Also, using the fact that θg2 ∼ N ( 0, θ2 ) and Fact C.1, we have
Pr g2
( |θg2| ∈ ( δ
9n2 , δ 5n2
)) ≥ δ 5n2
δ n2
− 2 3
δ 9n2
δ n2
≥ 0.08.
Independence of w′ and w′′ implies
Pr w
[E ] ≥ Ω ( δ
n2
) .
Thus,
Pr w∼N (0,Id)
(∥∥f(w)∥∥ 2 ≥ 0.1√
n
) ≥ Pr
w∼N (0,Id)
(∥∥f (w)∥∥ 2 ≥ 0.1√
n
∣∣∣∣E )
Pr w∼N (0,Id)
[E ]
≥ Ω ( δ
n2
) .
Proof of K.3. By the definition of w′, w′Txi∗ is equal to √
1− θ2g1, which is distributed according to N ( 0, 1− θ2 ) . Hence, applying concentration bounds from Fact C.1, we get that
Pr w′ (∣∣∣w′Txi∗ − α∣∣∣ ≤ δ 10n2 ) ≥ δ 40n2 √ 1− θ2 . (51)
We can divide w′ ∀i ∈ [n] into two parts:
• Component orthogonal to xi∗ given by w′T ( Id − xi∗xTi∗ ) xi
• Component parallel to xi∗ given by w′T ( xi∗x T i∗ ) xi.
This gives us w′Txi = w ′T ( Id − xi∗xTi∗ ) xi︸ ︷︷ ︸ +w′T ( xi∗x T i∗ ) xi.
Conditioning on w′Txi∗ such that Equation 51 is satisfied, we get that w′Txi is distributed according to
w′Txi ∼ N ( w′T ( xi∗x T i∗ ) xi, ( 1− θ2 )∥∥∥∥(Id − xi∗xTi∗)xi∥∥∥∥2
2
) .
By our assumption, ∥∥∥(Id − xi∗xTi∗)xi∥∥∥
2 ≥ δ. Also,
0 ≤ ∣∣∣∣w′T (xi∗xTi∗)xi∣∣∣∣ = ∣∣∣∣w′Txi∗ (xTi∗xi)∣∣∣∣ ≤ ∣∣∣∣α+ δ10n2 ∣∣∣∣ ≤ 1 (52) Hence, again applying concentration bounds from Fact C.1, we get for a fixed i 6= i∗
Pr w′ (∣∣∣w′Txi − α∣∣∣ ≥ δ 4n2 ) ≥ 1− δ 5n2 √ 1− θ2δ .
Taking a union bound, we get that ∀i ∈ [n] and i 6= i∗
Pr w′ (∣∣∣w′Txi − α∣∣∣ ≥ δ 4n2 ) ≥ 1− 1 5n √ 1− θ2 ≥ 4 5 ,
as required.

heading: K.1.2 J1 FOR STANDARD SETTING
text: The above theorems can be easily adapted to the standard settings, defined in Appendix D. We capture this with the following corollaries. Corollary K.3.1 (Adapting Theorem K.1 for Init (fanin) setting). Let the condition on φ be satisfied for r = 1. Assume, w(0)k ∼ N ( 0, 1dId ) , b (0) k ∼ N (0, 0.01) and a (0) k ∼ N ( 0, 1m ) ∀k ∈ [m]. Then, the minimum singular value of the G-matrix satisfies
λmin
( G(0) ) ≥ Ω ( δ
n3
) ,
with probability at least 1− e−Ω(δm/n 2) with respect to {w(0)k }mk=1, {b (0) k }mk=1 and {a (0) k }mk=1, given that m satisfies
m ≥ Ω
( n3
δ log
n
δ1/4
) .
Corollary K.3.2 (Adapting Theorem K.1 for Init (fanout) setting). Let the condition on φ be satisfied for r = 1. Assume, w(0)k ∼ N ( 0, 1mId ) , a (0) k ∼ N (0, 1) and b (0) k ∼ N ( 0, 1m ) ∀k ∈ [m]. Then, the minimum singular value of the G-matrix satisfies
λmin
( G(0) ) ≥ Ω ( δ
n2
) ,
with probability at least 1− e−Ω(δm/n) with respect to {w(0)k }mk=1, {b (0) k }mk=1 and {a (0) k }mk=1, given that m satisfies
m ≥ Ω
( n2
δ log
n
δ1/2
) .

heading: K.2 J2 : THE SECOND DERIVATIVE HAS JUMP DISCONTINUITY AT A POINT

heading: K.2.1 DZPS SETTING
text: Recall that this setting was defined in Section 2.
Theorem K.4. Let φ satisfy the condition for r = 2. Assume that w(0)k ∼ N (0, Id) and a (0) k ∼ N (0, 1) ∀k ∈ [m]. Then, the minimum singular value of the G-matrix satisfies
λmin
( G(0) ) ≥ Ω
( δ3
n7 log n
) ,
with probability at least 1 − e−Ω(δm/n 2) with respect to {w(0)k }mk=1 and {a (0) k }mk=1, given that m satisfies
m > max Ω(n3 δ log ( n δ1/3 )) ,Ω ( n2 log(d) δ ) . Proof. In the following, we will use wk instead of w (0) k and ak instead of a (0) k . Referring to Equation 4, it suffices to show that∥∥∥∥∥∥ n∑ i=1 ζimi ∥∥∥∥∥∥ 2
2
= m∑ k=1 ∥∥∥∥∥∥ n∑ i=1 ζiakφ ′ ( wTk xi ) xi ∥∥∥∥∥∥ 2
2
.
is lower bounded for all vectors ζ ∈ Sn−1 with high probability. Fix a particular ζ ∈ Sn−1. For each k ∈ [m] and each i ∈ [n], we have wTk xi ∼ N (0, 1). First, we analyze the sum for a fixed k, i.e. we consider ∑n i=1 ζi φ ′ (wTk xi)xi. We split vector wk as wk = ŵk + w̄k,
where ŵk and w̄k are two independent Gaussian vectors in Rd distributed according to N ( 0, ( 1− θ2 ) Id ) and N ( 0, θ2Id ) respectively. We set
θ = δ
2000n2 √ log n .
Define the event Cw on a weight vector w as
Cw = {∣∣∣wTxi − α∣∣∣ ≥ δ 100n2 : i ∈ [n] } .
Using Fact C.1 and the fact that xi are unit vectors,
Pr w∼N (0,(1−θ2)Id)
[Cw] ≥ 1− δ
400n √ 1− θ2 . (53)
Define the event Dw on a weight vector w as
Dw = {∣∣∣wTxi∣∣∣ ≤ δ 500n2 : i ∈ [n] } .
Fact C.2 shows that,
Pr w∼N (0,θ2Id)
[Dw] ≥ 1− 2n exp(−t2 2 ) (54) ≥ 1− 2
n7 (55)
≥ 0.5, (56)
where we set t = δ500n2θ to get Inequality 55.
We want ŵk to satisfy condition Cŵk and w̄k to satisfy condition Dw̄k . Since, ŵk and w̄k are independent of each other, we use Equation 53 and Equation 54 to get
Pw̄k,ŵk ( Cŵk and Dw̄k ) ≥ 0.25.
Assuming both the conditions hold, it follows that IŵTk xi≥α = IwTk xi≥α. We will work conditioned on both the events.
Define a function f as follows,
f(w) = n∑ i=1 ζi φ ′(wTxi).
Note that
∇wf(w) = n∑ i=1 ζi φ ′′(wTxi)xi.
In the sequel, we will use f ′ for ∇wf(w) and f ′′ for ∇2wf(w). It is easy to see that the only discontinuities of the derivative of function f are when wTxi = α, since it is the only point of discontinuity for φ′′. Thus, assuming that Cŵk and Dw̄k hold, we can apply Taylor expansion to f(ŵk) for a perturbation of w̄k, ensuring that all the derivatives exist in the neighborhood of interest. Hence, f(wk) = f(ŵk) + 〈w̄k, f ′(ŵk)〉+R2 (wk) , where R2 denotes the second order remainder term in the Taylor expansion given by
R2 (wk) = 1
2 ∫ 1 t=0 〈 f ′′ (ŵk + tw̄k) , w̄ ⊗2 k 〉 dt.
Using∇2wf(w) = ∑n i=1 ζi x ⊗2 i φ (3) (z) ∣∣∣∣ z=〈w,xi〉 , we have
R2 (wk) = 1
2 ∫ 1 t=0 n∑ i=1 ζi ( 〈w̄k,xi〉 )2 φ(3) ( 〈ŵk + tw̄k,xi〉 ) dt.
The magnitude of this term can be bounded as follows.
∣∣R2 (wk)∣∣ = 1 2 n∑ i=1 ζi ( 〈w̄k,xi〉 )2(∫ 1 t=0 φ(3) ( 〈ŵk + tw̄k,xi〉 ) dt )
≤ 1 2 √√√√ n∑ i=1 (∫ 1 t=0 φ(3) ( 〈ŵk + tw̄k,xi〉 ) dt )2√√√√ n∑ i=1 ζ2i ( 〈w̄k,xi〉 )4 (57)
≤ 1 2 √ n
( δ
500n2
)2 (58)
≤ O
( δ2
n3.5
) ,
where Inequality 57 uses Cauchy-Schwartz inequality, Inequality 58 uses the fact that all the derivatives of φ of order up to r+ 1 are bounded for x 6= 0 and w̄k satisfies condition Dw̄k and ŵk satisfies Cŵk . Thus we have
f(wk) = f(ŵk) + 〈w̄k, f ′(ŵk)〉+O
( δ2
n3.5
) . (59)
Consider the following two cases. Case 1: ∣∣f(ŵk)∣∣ < 12√ 0.01n θ.
First, we condition on the event that ŵk is picked so that ∥∥f ′ (ŵk)∥∥22 ≥ 0.01n and Cŵk holds true. We shall refer to this condition as Bŵk . By Claim K.5, we get that
Pr ŵk
[ Bŵk ] = Pr
ŵk (∥∥f ′(ŵk)∥∥22 ≥ 0.01n and Cŵk ) ≥ Ω ( δ (1− θ2)n2 ) . (60)
〈w̄k, f ′(ŵk)〉 is a random variable following N ( 0, θ2 ∥∥f ′(ŵk)∥∥22). Thus applying Fact C.1,
Pr w̄k (∣∣〈w̄k, f ′(ŵk)〉∣∣ ≥√0.01 n θ ∣∣∣∣ Bŵk ) ≥ 1 5 .
Now letting event D̄w̄k denote the complement of the event Dw̄k we have
Pr w̄k (∣∣∣〈w̄k, f ′(Ŵk)〉∣∣∣ ≥√0.01 n θ ∧ DW̄k ∣∣∣∣BŴk )
= Pr w̄k (∣∣〈w̄k, f ′(ŵk)〉∣∣ ≥√0.01 n θ ∣∣∣∣ Bŵk ) − Pr w̄k (∣∣〈w̄k, f ′(ŵk)〉∣∣ ≥√0.01 n θ ∣∣∣∣ Bŵk , D̄w̄k ) Pr w̄k [ D̄w̄k
] ≥ 1
5 − 2 n7
≥ 1/10.
Hence, from Equation 59, we get
Pr w̄k (∣∣f(wk)∣∣ ≥ 1 2 √ 0.01 n θ and Dw̄k ∣∣∣∣Bŵk ) ≥ 0.1.
Thus,
Pr wk (∣∣f(wk)∣∣ ≥ 1 2 √ 0.01 n θ ) ≥ Pr wk (∣∣f(wk)∣∣ ≥ 1 2 √ 0.01 n θ and Bŵk and Dw̄k )
≥ Pr ŵk
[ Bŵk ] Pr w̄k (∣∣f(wk)∣∣ ≥ 1 2 √ 0.01 n θ and Dw̄k ∣∣∣∣Bŵk )
≥ Ω ( δ
n2
)
Case 2: ∣∣f(ŵk)∣∣ ≥ 12√ 0.01n θ. We can upper-bound the magnitude of f ′(ŵk) by O( √ n) as follows.
∥∥f ′(ŵk)∥∥ = ∥∥∥∥∥∥ n∑ i=1 ζiφ ′′(ŵTk xi)xi ∥∥∥∥∥∥ ≤ √√√√ n∑ i=1 ζ2i φ ′′(ŵTk xi) 2 √√√√ n∑ i=1 ‖xi‖2 ≤ O( √ n).
Here we use the fact that‖ζ‖ = 1, φ′′ is bounded by a constant at all x 6= α and‖xi‖ = 1 for i ∈ [n]. Note that, this bound always holds true, irrespective of the value of ŵk. Again, using the fact that 〈w̄k, f ′(ŵk)〉 is a Gaussian variable following N (0, θ2 ∥∥f ′(ŵk)∥∥2), Fact C.1 shows that, Pr w̄k (∣∣〈w̄k, f ′(ŵk)〉∣∣ ≤ 1 4 √ 0.01 n θ ∣∣∣∣ Cŵk ) ≥ 0.1 4 2/3 √ n ∥∥f ′(ŵk)∥∥ ≥ 0.14 2/3n .
Now,
Pr w̄k (∣∣〈w̄k, f ′(ŵk)〉∣∣ ≤ 1 4 √ 0.01 n θ ∧ Dw̄k ∣∣∣∣ Cŵk )
= Pr w̄k (∣∣〈w̄k, f ′(ŵk)〉∣∣ ≤ 1 4 √ 0.01 n θ ∣∣∣∣ Cŵk ) − Pr w̄k (∣∣〈w̄k, f ′(ŵk)〉∣∣ ≤ 1 4 √ 0.01 n θ ∣∣∣∣ Cŵk , D̄w̄k ) Pr w̄k [ D̄w̄k
] ≥ 1
60n − 2 n7
≥ Ω ( 1
n
) .
Hence, from Equation 59, we get
Pr w̄k (∣∣f(wk)∣∣ ≥ 1 4 √ 0.01 n θ ∧ Dw̄k ∣∣∣∣Cŵk ) ≥ Ω ( 1 n ) .
Thus,
Pr wk (∣∣f(wk)∣∣ ≥ 1 4 √ 0.01 n θ ) ≥ Pr wk (∣∣f(wk)∣∣ ≥ 1 4 √ 0.01 n θ and Cŵk ∧ Dw̄k )
≥ Pr ŵk
[ Cŵk ] Pr w̄k (∣∣f(wk)∣∣ ≥ 1 4 √ 0.01 n θ and Dw̄k ∣∣∣∣Cŵk )
≥ Ω ( 1
n
) .
Thus, combining the two cases, we have
Pr wk (∣∣f(wk)∣∣ ≥ Ω( δ n2.5 √ log n )) ≥ Ω ( δ n2 ) . (61)
Hence,
Pr wk,ak  ∣∣∣∣∣∣ n∑ i=1 ζiakφ ′(wTk xi) ∣∣∣∣∣∣ ≥ Ω (
δ
n2.5 √ log n ) ≥ Ω( δ n2 ) . (62)
owing to the fact that for a standard normal variate ã, |ã| is at-least 1, with probability at-least 0.2 using Fact C.1. Applying a Chernoff bound over all k ∈ [m], we get
m∑ k=1  n∑ i=1 ζiφ ′ ( wTk xi )2 ≥ Ω( δ3m n7 log n )
with probability at least 1 − exp(−Ω( δmn2 )) with respect to {wk} m k=1 and {ak}mk=1.. Applying an
-net argument over ζ ∈ Sn−1, with = δ 1.5
2n4 √ logn and -net size
( 1 )n , we get that
m∑ k=1  n∑ i=1 ζiφ ′(wTk xi) 2 ≥ Ω( δ3m n7 log (n) ) (63)
holds for all ζ ∈ Sn−1 with probability at least
1−
( 2n4 √ log n
δ1.5
)n e −Ω ( mδ n2 ) ≥ 1− e−Ω ( mδ n2 )
with respect to {wk}mk=1 and {ak}mk=1., where we assume that m > Ω ( n3 δ log ( n δ1/3 )) . Now
consider the following function,
f(w) = m∑ k=1 n∑ i=1 ζiakφ ′ ( wTk xi ) xi
where ζ ∈ Sn−1. Note that f(w) is a d-dimensional vector. Also, the above can be written as f(w) = Qv
where Q = [qij ] ∈ Rd×n is defined by qi,j = ζjxj,i
and v ∈ Rn, defined by vi = akφ ′(wTk xi). Also, since ‖ζ‖ = 1 and ‖xi‖ = 1 ∀i ∈ [n], we have ‖Q‖F = 1. Consider the following quantity∑n j=1 qi,jvj . This quantity denotes the dot product of a row vector of Q and v. We can apply
Equation 63 to get ∣∣∣∣∣∣ n∑ j=1 qi,j ‖qi‖ vj ∣∣∣∣∣∣ 2 ≥ Ω ( δ3m n7 log n )
holds true with probability at-least 1 − e−Ω ( δm n2 ) with respect to {wk}mk=1 and {ak} m k=1. Note that, the coefficients have been normalized to unit norm to satisfy the condition based on which Equation 63 was derived. We can take a union bound over all the rows of Q to get
∥∥f(w)∥∥2 = d∑ i=1 ∣∣∣∣∣∣ n∑ j=1 qi,jvj ∣∣∣∣∣∣ 2 ≥ d∑ i=1 ‖qi‖2 Ω ( δ3m n7 log n )
=‖Q‖2F Ω
( δ3m
n7 log n
) = Ω ( δ3m
n7 log n ) with probability at least
1− de−Ω ( δm n2 ) ≥ 1− e−Ω ( δm n2 ) with probability at least 1− e−Ω ( δm n2 ) with respect to {wk}mk=1 and {ak} m k=1, assuming that m ≥
Ω ( n2 log d
δ
) . Thus, we can use Equation 4 to show that,
σmin (M) ≥ Ω √ δ3m n7 log n  . Using the fact that λmin ( G(0) ) = 1mσmin (M) 2, we get that λmin ( M(0) ) ≥ Ω( δ 3 n7 logn ) with
probability at least 1− e−Ω ( δm n2 ) .
ELU satisfies the conditions required for Theorem K.4. We state this explicitly in the following theorem.
Corollary K.4.1. Assume w(0)k ∼ N (0, Id) and a (0) k ∼ N (0, 1)∀k ∈ [m], if φ(x) = Ix<0 (ex − 1) + Ix≥0x, we have that for the G-matrix,
λmin
( G(0) ) ≥ Ω
( δ3
n7 log n
)
with probability at least 1− e−Ω ( δm n2 ) with respect to { w
(0) k }m k=1 , given that m satisfies
m > max Ω(n3 δ log ( n δ1/3 )) ,Ω ( n2 log(d) δ ) . Claim K.5. Let the variables have the same meaning as in the theorem Theorem K.4. Then,
Pr w∼N (0,c2Id)
( ‖f ′(w)‖22 ≥ 1
4n and Cw
) ≥ Ω( δ
cn2 )
for a variable c that depends on n and δ.
Proof. Let i∗ denote arg maxi∈[n] ζi. We can split w as w = w ′ + w′′, where
w′ = (Id − xi∗xTi∗)w + √ 1− θ2g1xi∗
and w′′ = θg2xi∗
where θ = δn2 and g1, g2 are two independent gaussians ∼ N (0, c 2). Let E denote the following event.
E = {∣∣∣w′Txi∗ − α∣∣∣ < δ 10n2 and ∣∣∣w′Txi − α∣∣∣ > δ 4n2 ∀i ∈ [n], i 6= i∗ and |θg2| ∈ ( δ 9n2 , δ 5n2 )} Event E satisfies condition Cw because for i∗,∣∣∣wTx∗i − α∣∣∣ = ∣∣∣w′Txi∗ + w′′Txi∗ − α∣∣∣ > ∣∣∣∣∣∣∣w′Txi∗ − α∣∣∣−∣∣∣w′′Txi∗ ∣∣∣∣∣∣∣ > δ90n2 and for all i 6= i∗,∣∣∣wTxi − α∣∣∣ = ∣∣∣w′Txi + w′′Txi − α∣∣∣ > ∣∣∣∣∣∣∣w′Txi − α∣∣∣−∣∣∣w′′Txi∣∣∣∣∣∣∣ > δ20n2 Hence, we can write that
Pr w∼N (0,c2Id)
( ‖f ′(w)‖22 ≥ 1
4n and Cw
)
≥ Pr w∼N (0,(1−θ2)Id)
( ‖f ′(w)‖22 ≥ 1
4n and Cw ∣∣∣∣∣E ) Pr w∼N (0,(1−θ2)Id) E
= Pr w∼N (0,(1−θ2)Id)
( ‖f ′(w)‖22 ≥ 1
4n ∣∣∣∣∣E ) Pr w∼N (0,(1−θ2)Id) E
≥ 1 2 0.2δ cn2 = Ω( δ cn2 ),
where we use Claim K.6 in the final step.
Claim K.6.
Pr w∼N (0,c2Id) ‖f ′(w)‖22 ≥ 0.01n ∣∣∣∣∣E  ≥ 1 2
and Pr
w∼N (0,c2Id) (E) ≥ 0.08δ c2n2
where E is defined and w has been split into w′ and w′′ as in proof of Claim K.5.
Proof. This follows from the proof of Claim K.2, with a slight change in distribution of w from N (0, Id) to N ( 0, c2Id ) and the function under consideration is changed to
f ′(w) = n∑ i=1 ζiφ ′′ ( wTxi ) xi.

heading: K.2.2 J2 FOR STANDARD SETTING
text: As before, we state the main theorem for standard initializations, defined in Appendix D, as corollaries. Corollary K.6.1 (Adapting Theorem K.4 for Init(fanin) setting). Let the condition on φ be satisfied for r = 1. Assume, w(0)k ∼ N ( 0, 1dId ) , b (0) k ∼ N (0, 0.01) and a (0) k ∼ N ( 0, 1m ) ∀k ∈ [m]. Then, the minimum singular value of the G-matrix satisfies
λmin
( G(0) ) ≥ Ω
( δ3
n7d log n
)
with probability at least 1− e−Ω ( δm n2 ) with respect to { w
(0) k }m k=1 , given that m satisfies
m > max Ω(n3 δ log ( n δ1/3d1/9 )) ,Ω ( n2 log(d) δ ) . Corollary K.6.2 (Adapting Theorem K.4 for Init(fanout) setting). Let the condition on φ be satisfied for r = 1. Assume, w(0)k ∼ N ( 0, 1mId ) , b (0) k ∼ N ( 0, 1m ) and a(0)k ∼ N (0, 1) ∀k ∈ [m]. Then, the minimum singular value of the G-matrix satisfies
λmin
( G(0) ) ≥ Ω
( δ2
mn4 log n
) ,
with probability at least 1− e−Ω(δm/n) with respect to {w(0)k }mk=1, {b (0) k }mk=1 and {a (0) k }mk=1, given that m satisfies
m ≥ Ω
( n2
δ log
mn5 log n
δ2
) .
L A NEW PROOF FOR THE MINIMUM EIGENVALUE FOR ReLU
Theorem L.1 (Thm 3.3 in Du et al. (2019a)). Consider the 2-layer feed forward network in Equation 1. Assume that w(0)k ∼ N (0, 1) and a (0) k ∼ U{−1,+1} ∀k ∈ [m], Assumption 1 and Assumption 2 hold true and|yi| ≤ C, for some constant C. Then, if we use gradient flow optimiza-
tion and set the number of hidden nodes m = Ω (
n6 log mκ λmin(G∞) 4κ3
) , with probability at least 1 − κ
over the initialization we have
‖ut − y‖2 ≤ e−λmin(G ∞)t‖u0 − y‖
Remark. The above proof can be adapted for the gradient descent algorithm with a learning rate less than O ( λmin (G ∞) /n2 ) , following the proof of Theorem 5.1 in Du et al. (2019b) and theorem 4.1 in Du et al. (2019a) without substantial changes in the bounds.
Theorem L.2. Assume that we are in the setting of Theorem L.1. If the activation is ReLU and m ≥ Ω ( n4δ−3 log4 n ) , then with probability at least 1− exp ( −Ω ( mδ3
n2 log3 n
))
λmin
( G(0) ) ≥ Ω
(( δ
log n
)1.5) .
Remark. Compare the previous theorem with Cor. K.2.1.
Proof. Using Lemma I.1, we have
λmin (G ∞) ≥ c̄2r ( φ′ ) λmin ( (X∗r) T X∗r ) , ∀r ∈ Z+
where X denotes a d× n matrix, with its i-th column containing xi and X∗r ∈ Rd r×n denotes its order-r Khatri-Rao product. Note that, by Assumption 1, the columns of X∗r are unit normalized euclidean vectors. If for any i, j ∈ [n], xTi xj = ρ < 1, then we can see that ( x∗ri )T x∗rj = ρ r, where x∗r denotes the order-r Khatri–Rao product of a vector x. Also,|ρ| can be shown to be at most 1− δ, using Assumption 2. Thus, for the magnitude of ( x∗ri )T
x∗rj , for any i, j ∈ [n], i 6= j, to be less than 1
2n , we must have r ≥ r0 = log 2n δ . Hence, for any r ≥ r0 the diagonal elements of (X ∗r) T X∗r are equal to 1 and magnitude of the non diagonal elements are less than 12n . Thus, applying Fact C.10, we get that
λmin
( (X∗r) T X∗r ) ≥ 1
2 . Using Equation 18, we see that for r = Θ (
log 2n δ
) ,
c̄2r ( φ′ ) = Θ
(( log 2n
δ
)−1.5) .
Thus,
λmin (G ∞) ≥ Ω
(( log 2n
δ
)−1.5) .
For computing λmin ( G(0) ) , we bound the absolute difference in each element of G∞ and G(0) by
1 2nλmin (G ∞) using Hoeffding’s inequality (Fact C.3) and 1-Lipschitzness of φ and then apply a union bound over all the indices. The bound stated in the theorem follows from the fact that
λmin
( G(0) ) ≥ λmin (G∞)− ∥∥∥∥(G∞ −G(0))∥∥∥∥ F
≥ λmin (G∞)− λmin (G∞) /2.
Using the bound of λmin (G∞) from Theorem L.2 in Theorem L.1, we get the following explicit rate of convergence for 2 layer feedforward networks. Theorem L.3 (Thm 3.3 in Du et al. (2019a)). Assume that the assumptions in Du et al. (2019a) hold true. Then, if we use gradient flow optimization and set the number of hidden nodes m =
Ω
( n6 log6(n) log mκ
δ6κ3
) , with probability at least 1− κ over the initialization we have
‖ut − y‖2 ≤ ∀t ≥ Ω (
log1.5 n δ1.5 log n
) , for an arbitrarily small constant > 0.

heading: M EXTENSIONS AND ADDITIONAL DISCUSSION
text: In this section, we discuss proofs and extensions of our theorems, using adaptations from related work.
M.1 POLYNOMIAL MINIMUM EIGENVALUE OF G-MATRIX AT TIME t
The upcoming lemma shows that, if we restrict the change in weight matrices, the minimum eigenvalue of G(t) stays close to the minimum eigenvalue of G(0).
Lemma M.1. If activation function φ is α-lipschitz and β-smooth and ∥∥∥w(t)r −w(0)r ∥∥∥ ≤ λmin(G(0))4αβn , ∀r ∈ [m], then
λmin
( G(t) ) ≥ 1
2 λmin
( G(0) ) Proof. The claim follows a similar proof as the proof of lemma B.4 in Du et al. (2019b) and has been repeated in Lemma M.11.
The restriction is ensured by the large number of neurons we can choose for our neural network, as we mention in the next lemma.
Lemma M.2. Let St ⊆ [n] denote a randomly picked batch of size b. Denote ∇(t) as ∇W(t)L ({ (xi, yi) } i∈[n] ;a,W (t) )
. Let the activation function φ used be α-lipschitz and β-smooth.

heading: The GD iterate at time t+ 1 is given by,
text: W(t+1) = W(t) − η∇(t)
Let η ≤ O
( λmin ( G(0)
) βn4α4 ) . If
m ≥ Ω n4α4β2 logm λmin ( G(0) )4 
then, ∥∥∥y − u(t)∥∥∥2 ≤ for t ≥ Ω ( log(n )
ηλmin(G(0))
) , with probability at-least 1 −m−3.5 w.r.t. { w
(0) k }m k=1 and { a (0) k }m k=1 .
Moreover, ∥∥∥w(t)k −w(0)k ∥∥∥ ≤ λmin ( G(0) ) 4αβn
holds true ∀k ∈ [m] and ∀t ≥ 0.
Proof. The claim follows a similar proof as the proof of lemma A.1 in Du et al. (2019b), where we keep the output vector a non trainable in GD update.
Remark. The above lemmas are applicable for activation functions in Jr for r ≥ 2. Similar lemmas can be proved for J1, along the lines of the proof of Theorem 4.1 in Du et al. (2019a).

heading: M.2 TRAINABLE OUTPUT LAYER
text: Similar to the proof of Theorem 3.3 in Du et al. (2019b), we can show that the GD dynamics depends on sum of two matrices, i.e.
du(t)
dt = (G(t) + H(t))(y − u(t)),
where the definition of G stays the same and H is given by
hij = 1
m ∑ r∈[m] σ(wTr xi)σ(w T r xj),
implying H is p.s.d. For the positive results, e.g. Theorem 4.1, observe that λmin(G + H) ≥ λmin(G), hence a bound on λmin (G) suffices in this case. For the negative results, Theorem 4.3 and Theorem 4.4 can be restated as follows. Theorem M.3. Let the activation function φ be a degree-p polynomial such that φ′(x) = ∑p−1 l=0 c`x `
and let d′ = dim ( span {x1 . . . xn} ) = O ( n 1 p ) . Then we have
λk
( G(0) + H(0) ) = 0, ∀k ≥ ⌈ 2n/d′ ⌉ Theorem M.4. Let the activation function be tanh and let d′ = dim ( span {x1 . . . xn} ) =
O ( log0.75 n ) . Then we have
λk
( G(0) + H(0) ) ≤ exp(−Ω(n1/2d ′ )) 1/poly(n), ∀k ≥ ⌈ 2n/d′ ⌉ with probability at least 1 − 1/n3.5 over the random choice of weight vectors { w
(0) k }m k=1
and{ a
(0) k }m k=1 .
Proof. (Proof sketch for Theorem M.3 and Theorem M.4) Following the proof of Theorem 4.3 and Theorem 4.4 gives us similar lower bounds for H(0) i.e. n(1 − 1d′ ) lower order eigenvalues are 0, if φ is a degree-p polynomial and exponentially small in n1/d ′ with high probability, if φ is tanh. Thus, we can use Weyl’s inequality (Fact C.11) to show that n(1 − 2d′ ) lower order eigenvalues of G(0) + H(0) are 0, if φ is a degree-p polynomial and exponentially small in n1/d ′ with high probability, if φ is tanh.
Remark. The lemmas in subsection M.1, that were proved for a network with non trainable output vector a, can also be proved for a network with trainable output vector a. And so, a polynomial lower bound on minimum eigenvalue of G(0) implies polynomial lower bound on minimum eigenvalue of G(t), under appropriate number of neurons and GD training.

heading: M.3 MULTI CLASS OUTPUT WITH CROSS ENTROPY LOSS
text: Let’s say, we have a classification task, where the number of classes is C and we use the following neural network for prediction.
fq(x;A,W) := cφ√ m m∑ k=1 ak,qφ ( wTk x ) , ∀q ∈ [C]
where x ∈ Rd is the input and W = [w1, . . . ,wm] ∈ Rm×d is the hidden layer weight matrix and A ∈ Rm×C is the output layer weight matrix. We define u (x) ∈ RC as
u (x) = softmax ( f(x;A,W) ) where softmax on a vector v ∈ RC denotes the following operation
softmax(v)i = evi∑
j∈[C] e vj .
Given a set of examples {xi, yi}ni=1, where xi ∈ Rd and yi ∈ [C] ∀i ∈ [n], we use the following cross entropy loss to train the neural network.
L ( A,W; {xi, yi}ni=1 ) = − n∑ i=1 log ( fyi(x;A,W) )
Let’s denote the vector ỹ as an nC dimensional vector, whose elements are defined as follows.
ỹC(i−1)+j = { 0, if j 6= yi 1, otherwise
Also, let’s define another vector ũ ∈ RnC as follows. ũC(i−1)+j = softmax ( f(xi;A,W) ) j
All the network dependent variables have a superscript t, depending on the time step at which they are calculated.
Using chain rule and derivative of cross entropy loss w.r.t. output of softmax layer, we can show the following differential equation for gradient flow.
dũ dt = G̃(t) (ỹ − ũ)
where G̃ ∈ RnC×nC is a gram matrix defined by its elements as follows.
g̃pr = 1
m ∑ k∈[m] ak,qak,q′φ ′ ( wTk xi ) φ′ ( wTk xj ) ,
where i = b pC c+ 1, j = b r C c+ 1, q = p mod C and q ′ = r mod C. Thus, d ∥∥∥ỹ − ũ(t)∥∥∥2
dt = −
( ỹ − ũ(t) )T G̃(t) ( ỹ − ũ(t) ) ≤ −λmin ( G̃(t) )∥∥∥ỹ − ũ(t)∥∥∥2 Again following the argument discussed in section 3, if there hasn’t been much movement in the weights of the network due to large number of neurons, ( G̃(t) ) stays close to ( G̃(0) ) and hence, the
rate of convergence depends on the gram matrix ( G̃(0) ) . We show that the gram matrix possesses a
unique structure and is related to the gram matrix defined for a single output network.
G̃ contains C disjoint principal n× n blocks, denoted by {Bq}Cq=1, where Bq is defined as follows:
bqij = 1
m ∑ k∈[m] a2k,qφ ′ ( wTk xi ) φ′ ( wTk xj ) .
As can be seen, each Bq is structurally identical to the gram matrix defined for a single output neural network with input weight matrix W and output weight vector aq (Equation 2).
Let’s denote the set of C(C−1) remaining disjoint non diagonal blocks of G̃ as {Bq,q′}q,q′∈[C],q 6=q′ , where each block is defined as follows.
bq,q ′ ij = 1
m ∑ k∈[m] ak,qak,q′φ ′ ( wTk xi ) φ′ ( wTk xj ) .
Assuming that we have sufficient number of neurons, G̃(0) can be shown to be close to the matrix G̃∞ using Hoeffding’s inequality, where G̃∞ has the following diagonal {(B∞)q}Cq=1 and non diagonal blocks {(B∞)q,q ′ }Cq=1 defined as follows.
(B∞) q ij = Ew∼N (0,I),ã∼N (0,1) ã 2φ′ ( wTxi ) φ′ ( wTxj ) ,
(B∞) q,q′ ij = Ew∼N (0,I),a,ã∼N (0,1) aãφ ′ ( wTxi ) φ′ ( wTxj ) .
Using independence of random gaussian variables a and ã and random gaussian vector w, we can show that (B∞)q,q ′ are identically zero matrices. Also, the diagonal blocks (B∞)q are identically equal to the G∞ matrix defined for single output layer neural networks (Equation 2). Thus, λmin(G̃ ∞) = λmin(G̃ ∞) and hence the bounds for eigenvalues of λmin(G̃(0)) can be derived from the bounds for eigenvalues of λmin(G(0)), defined for a single output layer neural network (Equation 2).

heading: M.4 FINE-GRAINED ANALYSIS FOR SMOOTH ACTIVATION FUNCTIONS
text: In this section, we show the behavior of the loss function under gradient descent, in the low learning rate setting considered by Du et al. (2019a), Du et al. (2019b) and Arora et al. (2019c). We consider the neural network given by Equation 1.
We assume that the activation function φ satisfies the following properties.
• φ ∈ C3,
• φ is β-lipschitz and γ-smooth.
Now, we state some important theorems from Du et al. (2019b), that we will use for the future analysis. There are some differences in our setting and the setting of Du et al. (2019b). a) Du et al. (2019b) work with a general L layer neural network. Hence, we state their theorems for L = 1. b) For simplicity of presentation, we have assumed that ak has been kept fixed during gradient descent, which can be easily removed as in subsection M.2 and Du et al. (2019a).
Theorem M.5 (Lemma B.4 in Du et al. (2019b)). Assume that ∀i ∈ [n] ,|yi| = O (1) and
m ≥ Ω max  n4( λmin ( G(0) ))4 , nκ , n2 log nκ( λmin ( G(0) ))2   ,
If we set step size as
η = O λmin ( G(0) ) n2  then with probability at least 1− κ over { w
(0) k }m k=1 , the following holds ∀t ∈ Z+.
L ( W(t) ) ≤ 1− ηλmin ( G(0) ) 2  t L ( W(0) )
Note that Du et al. (2019b) consider λmin (G∞) in their arguments. However, in the overparametrized regime, with high probability with respect to {wk}mk=1, λmin (G∞) and λmin ( G(0) ) differ only by a constant factor, as given by lemma B.4 in Du et al. (2019b). Thus, we show their theorems using λmin ( G(0) ) .
Theorem M.6 (Lemma B.6 in Du et al. (2019b)). Assuming the setting in Theorem M.5, the following holds ∀t ∈ Z+ and ∀k ∈ [m].
∥∥∥w(t)k −w(0)k ∥∥∥ ≤ O (
n √ mλmin ( G(0) )) . Theorem M.7. Assuming the setting in Theorem M.5, the following holds ∀t ∈ Z+.∥∥∥G(t) −G(0)∥∥∥
2 ≤ O
( n2
√ mλmin ( G(0) )) . Proof. We follow the proof of lemma B.5 of Du et al. (2019b). We will bound the change in each element of the G-matrix and then, take a sum over all the elements to get a bound over the
perturbation. ∣∣∣g(t)ij − g(0)ij ∣∣∣ = ∣∣∣∣∣∣∣ 〈 xi,xj 〉 m  m∑ k=1 φ′ ( w (t)T k xi ) φ′ ( w (t)T k xj ) − m∑ k=1 φ′ ( w (0)T k xi ) φ′ ( w (0)T k xj ) ∣∣∣∣∣∣∣
≤ 1 m m∑ k=1 ∣∣∣∣φ′ (w(t)Tk xi)φ′ (w(t)Tk xj)− φ′ (w(0)Tk xi)φ′ (w(t)Tk xj)∣∣∣∣ + 1
m m∑ k=1 ∣∣∣∣φ′ (w(0)Tk xi)φ′ (w(t)Tk xj)− φ′ (w(0)Tk xi)φ′ (w(0)Tk xj)∣∣∣∣ = 1
m m∑ k=1 ∣∣∣∣φ′ (w(t)Tk xi)− φ′ (w(0)Tk xi)∣∣∣∣ ∣∣∣∣φ′ (w(t)Tk xj)∣∣∣∣ + 1
m m∑ k=1 ∣∣∣∣φ′ (w(t)Tk xj)− φ′ (w(0)Tk xj)∣∣∣∣ ∣∣∣∣φ′ (w(0)Tk xi)∣∣∣∣ ≤ 2γO(1) ∥∥∥w(0)k −w(t)k ∥∥∥ ≤ O (
γn √ mλmin ( G(0)
))
where, we use Theorem M.6 and the fact that φ′ is γ-smooth and is bounded by O(1) in the final step. Thus, we get
∥∥∥G(t) −G(0)∥∥∥ F ≤ √√√√ ∑ i,j∈[n] ( g (t) ij − g (0) ij )2 ≤ O ( γn2 √ mλmin ( G(0) ))
as required.
Lemma M.8 (Claim 3.4 in Du et al. (2019a)). In the setting of Theorem M.5,∥∥∥y − u(0)∥∥∥ ≤ O(√n κ ) holds with probability at least 1− κ with respect to { w
(0) k }m k=1 .
Now, we state the following theorem, which is a simple adaptation of theorem 4.1 in Arora et al. (2019c). Let v1, v2, ..., vn denote the eigenvectors of G(0), corresponding to its eigenvalues λ1, λ2, ..., λn.
Theorem M.9. With probability at least 1−κ over the random initialization, ∀t ∈ Z+, the following holds ∥∥∥y − u(t)∥∥∥ = √√√√ n∑ i=1 ( 1− ηc2φλi )2t ( vTi ( y − u(0) ))2 ± ,
provided
m ≥ Ω  n5 γκλmin ( G(0) )4 2  and
η ≤ O λmin ( G(0) ) c2φn 2 
Proof. For each i ∈ [n], we get
u (t+1) i − u (t) i = cφ√ m m∑ k=1 ak { φ ( w (t+1)T k xi ) − φ ( w (t)T k xi )}
= cφ√ m m∑ k=1 ak φ (( w (t) k − η ∂ ∂wk L ( w (t) k ))T xi ) − φ ( w (t)T k xi ) (64) =
cφ√ m m∑ k=1 akφ ′ ( w (t)T k xi )( −η ∂ ∂wk L ( w (t) k ))T xi + i (t) (65)
= − ηc2φ m m∑ k=1 a2k n∑ j=1 ( φ′ ( w (t)T k xi ) φ′ ( w (t)T k xj ))( u (t) j − yj ) 〈 xi,xj 〉 + i (t)
= −ηc2φ n∑ j=1 G (t) ij ( u (t) j − yj ) + i (t) (66)
where we use Taylor expansion of φ in Equation 65. i (t) denotes the error term due to truncated Taylor expansion, whose norm can be bounded by∣∣ i (t)∣∣ ≤ cφ
2 √ m m∑ k=1 O(1)
(( η ∂ ∂wk L ( w (t) k ))T xi )2 (67)
= cφ
2m3/2 η2O(1) m∑ k=1  n∑ j=1 akφ ′ ( w (t)T k xi ) 〈 xi,xj 〉 ( y − u(t) ) j 2
≤ cφ 2m3/2 η2O(1) m∑ k=1  n∑ j=1 akφ ′ ( w (t)T k xi )2 〈 xi,xj 〉2∥∥∥y − u(t)∥∥∥2 (68) ≤ O ( η2cφn√ m/ logm
)∥∥∥y − u(t)∥∥∥2 (69) where we use the fact that
∣∣φ′′(z)∣∣ ≤ O(1)∀z ∈ R in Equation 67, use the Cauchy-Schwartz inequality in Equation 68 and use the fact that
∣∣φ′(z)∣∣ ≤ O(1)∀z ∈ R, 〈xi,xj〉 ≤ 1 ∀i, j ∈ [n] and|ak| ≤ √ logm with high probability in Equation 69. Thus, this gives
u(t+1) − u(t) = −ηc2φG(t) ( u(t) − y ) + (t)
where ∥∥ (t)∥∥ = √√√√ n∑
i=1
i(t) 2 ≤ O
( η2cφn
3/2√ m/ logm )∥∥∥y − u(t)∥∥∥2 . Now, since G(t) is close to G(0), we can write
u(t+1) − u(t) = −ηc2φG(0) ( u(t) − y ) + τ(t) (70)
where τ(t) = −ηc2φ ( G(t) −G(0) )( u(t) − y ) + (t). The norm of τ(t) can be bounded as follows.∥∥τ(t)∥∥ ≤ ηc2φ∥∥∥∥(G(t) −G(0))(u(t) − y)∥∥∥∥+∥∥ (t)∥∥
≤ ηc2φ ∥∥∥G(t) −G(0)∥∥∥∥∥∥u(t) − y∥∥∥+∥∥ (t)∥∥
≤ O ( ηγ
n2c2φ√ mλmin ( G(0) ))∥∥∥y − u(t)∥∥∥+O( η2cφn3/2√ m/ logm )∥∥∥y − u(t)∥∥∥2 ≤ O ( ηγn2c2φ√
mλmin ( G(0)
))∥∥∥y − u(t)∥∥∥ .
Thus, applying Equation 70 recursively, we get
u(t) − y = ( I− ηc2φG(0) )t (u(0) − y) + t−1∑ t′=0 ( I− ηc2φG(0) )t′ τ(t− 1− t′). (71)
We bound the norm of each term in the above equation. The norm of the first term can be given as follows. ∥∥∥∥−(I− ηc2φG(0))t (u(0) − y)∥∥∥∥ = ∥∥∥∥∥∥  n∑ i=1 ( 1− ηc2φλi )t viv T i (u(0) − y) ∥∥∥∥∥∥
= √√√√ n∑ i=1 ( 1− ηc2φλi )2t ( vTi ( u(0) − y ))2 . (72)
Now, the norm of the second term can be bounded as ‖ t−1∑ t′=0 ( I− ηc2φG(0) )t′ τ(t− 1− t′)‖2
≤ t−1∑ t′=0 ∥∥∥I− ηc2φG(0)∥∥∥t 2 ∥∥τ(t− 1− t′)∥∥ 2
≤ t−1∑ t′=0 ( 1− ηc2φλmin ( G(0) ))t′ O ( ηγn2c2φ√ mλmin ( G(0) ))∥∥∥u(t−1−t′) − y∥∥∥ 2
(73)
≤ t−1∑ t′=0 ( 1− ηc2φλmin ( G(0) ))t′ O ( ηγn2c2φ√ mλmin ( G(0) )) 1− ηc2φλmin ( G(0) ) 4  t−1−t′ O (√ n/κ )
≤ t 1− ηc2φλmin ( G(0) ) 4  t−1 O ( γηn5/2c2φ√ mκλmin ( G(0) )) . In Equation 73, we use the following. ∥∥∥u(s) − y∥∥∥ 2 = 1− ηc2φλmin ( G(0) ) 4  s∥∥∥u(0) − y∥∥∥ ≤ 1− ηc2φλmin ( G(0) ) 4  s O (√ n/κ )
Thus, combining the two terms, we have
∥∥∥u(t) − y∥∥∥ ≤ √√√√ n∑
i=1
( 1− ηc2φλi )2t ( vTi ( y − u(0) ))2 ± t 1− ηc2φλmin ( G(0) ) 4  t−1 O ( γηn5/2c2φ√ mκλmin ( G(0) ))
(74)
≤ √√√√ n∑ i=1 ( 1− ηc2φλi )2t ( vTi ( y − u(0) ))2 ±O ( γn5/2 √ κmλ2min ( G(0) ))︸ ︷︷ ︸ ♠
(75)
where in Equation 74, we use the fact that
t 1− ηc2φλmin ( G(0) ) 4  t−1 ≤ 4 ηc2φλmin ( G(0) ) .
Thus, for the term denoted by ♠ to be less than , we need
m ≥ Ω  γn5 κλmin ( G(0) )4 2 

heading: M.5 PROOF FOR SGD
text: The following theorem is an adaptation of Theorem 2 in Allen-Zhu et al. (2019), which asserts fast convergence of SGD for ReLU. The theorem below applies to activation in Jr for r ≥ 2; the case of J1 can be handled by another adaptation of Theorem 2 in Allen-Zhu et al. (2019) which we do not discuss. Du et al. (2019b) analyzed gradient descent for this setting and mentioned the analysis of SGD as a future work. Theorem M.10. Let St ⊆ [n] denote a randomly picked batch of size b. Let ∇(t) denote n b∇W(t)L ({ (xi, yi) } i∈St ;a,W(t) )
. Let the activation function φ be α-Lipschitz and β-smooth.

heading: The SGD iterate at time t+ 1 is given by,
text: W(t+1) = W(t) − η∇(t) Let η ≤ O ( λmin ( G(0) ) b2
βn6α4
) . If
m ≥ Ω  n6α4β2 logm b2λmin ( G(0) )4 
then, ∥∥∥y − u(t)∥∥∥2 ≤ for t ≥ Ω ( n6α4
b2λmin(G(0)) 2 β log
( n )) , with probability at least 1− e−Ω(n 2) −m−3.5 w.r.t. random
choice of St for t ≥ 0.
Proof. Note that ESt∇(t) = ∇W(t)L ({ (xi, yi) } i∈[n] ;a,W (t) )
Using taylor expansion for each coordinate i, we have
u (t+1) i − u (t) i
=ui
( W(t) − η∇(t) ) − ui(W(t))
=− ∫ η s=0 〈 ∇(t), u′i ( W(t) − s∇(t) )〉 ds
=− ∫ η s=0 〈 ∇(t), u′i(W(t)) 〉 ds+ ∫ η s=0 〈 ∇(t), u′i(W(t))− u′i ( W(t) − s∇(t) )〉 ds
,Ii1(t) + I i 2(t) (76)
Writing the decrease of loss at time t, we have∥∥∥y − u(t+1)∥∥∥2 2 = ∥∥∥y − u(t) − (u(t+1) − u(t))∥∥∥2 2
= ∥∥∥y − u(t)∥∥∥2
2 − 2(y − u(t))>(u(t+1) − u(t)) + ∥∥∥u(t+1) − u(t)∥∥∥2 2
= ∥∥∥y − u(t)∥∥∥2
2 − 2(y − u(t))>I1 − 2(y − u(t))>I2 + ∥∥∥u(t+1) − u(t)∥∥∥2 2
(77)
(78)
where I1 ∈ Rn and its ith coordinate is given by Ii1. Similarly, we define I2. Ii1 is given as,
Ii1 = −η 〈 ∇(t), u′i(W(t)) 〉 = −ηn
b ∑ j∈St ( u (t) j − yj )〈 u′j(W (t)), u′i(W (t)) 〉
(79)
, −ηn b ∑ j∈St ( u (t) j − yj ) g (t) ij (80)
where we use the definition of ∇(t) in Equation 79. That implies,
‖I1‖ = η n
b ∥∥∥∥G(t)D(t) (u(t) − y)∥∥∥∥ ≤ ηn
b ∥∥∥G(t)∥∥∥ 2 ∥∥∥y − u(t)∥∥∥ ≤ ηn
b nα2 ∥∥∥y − u(t)∥∥∥ (81) where D(t) ∈ Rn×n denotes a diagonal matrix that has 1 in ith diagonal element, iff i ∈ St and 0 otherwise and‖G‖2 ≤‖G‖F ≤ nL2, since φ is α-lipschitz. Note that,
ESt(y − u(t))>I1 = ESt ∑ i∈[n] ∑ j∈St η n b ( u (t) i − yi ) g (t) ij ( u (t) j − yj ) = η ( y − u(t) )> G(t) ( y − u(t)
) ≥ ηλmin ( G(t)
)∥∥∥y − u(t)∥∥∥2 (82) Also, we can bound I2 in the following manner.∣∣∣Ii2(t)∣∣∣ ≤ η∥∥∥∇(t)∥∥∥
F max 0≤s≤η ∥∥∥∥u′i(W(t))− ui′(W(t) − s∇(t))∥∥∥∥ F
Since,
∥∥∥∇(t)∥∥∥2 F = ( n/b√ m )2 m∑ r=1 ∥∥∥∥∥∥ ∑ i∈St ( yi − u(t)i ) arφ ′ ( wTr xi ) xi ∥∥∥∥∥∥ 2 ≤ ( n1.5 α b ∥∥∥y − u(t)∥∥∥)2
and∥∥∥∥u′i(W(t))− u′i (W(t) − s∇(t))∥∥∥∥ F = 1√ m √√√√ m∑ r=1 ∥∥∥∥∥ar ( φ′ ( wTr xi ) − φ′ ( wTr xi − s∇ (t)T r xi )) xi ∥∥∥∥∥ 2
2
≤ 1√ m √√√√ m∑ r=1 ∥∥∥∥arβ (s∇(t)Tr xi)xi∥∥∥∥2 2
≤ 1√ m βη √√√√max r∈[m] ∥∥∥∇(t)r ∥∥∥2 2 m∑ r=1 a2r
≤ βηn1.5α b
∥∥∥y − u(t)∥∥∥ (83)
where we use β-smoothness of the activation function φ in the first step, ∑ r a 2 r ≤ 5m with high
probability and maxr∈[m] ∥∥∥∇(t)r ∥∥∥2 2 ≤ ∥∥∥∇(t)r ∥∥∥2 F in 3rd step. That implies, ∣∣∣Ii2(t)∣∣∣ ≤ βη2n3α2b2 ∥∥∥y − u(t)∥∥∥2 ≤ βη2n4α2b2 ∥∥∥y − u(t)∥∥∥ (84) Also,∣∣∣∣ui(W(t))− ui (W(t) − s∇(t))∣∣∣∣2 = 1m ∣∣∣∣∣∣ m∑ r=1 ar ( φ ( wTr xi ) − φ ( wTr xi − s∇(t)Tr xi ))∣∣∣∣∣∣ 2
≤ 1 m  m∑ r=1 ∣∣∣∣arα(s∇(t)Tr xi)∣∣∣∣ 2
≤ α2η2  1 m ∑ r∈[m] a2r  max r∈[m] ∥∥∥∇(t)r ∥∥∥2 2
≤ α2η2 max r∈[m] ∥∥∥∇(t)r ∥∥∥2 2
≤ α2η2 ( n1.5 α
b ∥∥∥y − u(t)∥∥∥)2 (85) Hence, using Equation 77, Equation 81, Equation 84 and Equation 85, we get∥∥∥y − u(t+1)∥∥∥2 2 = ∥∥∥y − u(t)∥∥∥2 2 − 2(y − u(t))>I1 − 2(y − u(t))>I2 + ∥∥∥u(t+1) − u(t)∥∥∥2 2 (86)
= ( 1 + 2η n2L2
b + 2βη2n4.5
α2 b2 + α4 b2 η2n4 )∥∥∥y − u(t)∥∥∥2 (87) = O (1 + 2ηn2α2 b )∥∥∥y − u(t)∥∥∥2  (88)
Taking log both the sides, we get
log (∥∥∥y − u(t+1)∥∥∥2 2 ) ≤ O ( η n2α2 b ) + log (∥∥∥y − u(t)∥∥∥2) By azuma-hoeffding inequality, we have
log (∥∥∥y − u(t)∥∥∥2 2 ) − ESt−1 log (∥∥∥y − u(t)∥∥∥2 2 ) ≤ √ tO ( η n2α2 b ) n (89)
with probability at-least 1− e−Ω(n 2).
Also,
ESt ∥∥∥y − u(t+1)∥∥∥2 2 = ∥∥∥y − u(t)∥∥∥2 2 − ESt2(y − u(t))>I1 − ESt2(y − u(t))>I2 + ESt ∥∥∥u(t+1) − u(t)∥∥∥2 2
≤ ( 1− ηλmin ( G(t) ) + 2βη2n4.5 α2
b2 + α4 b2 η2n4 )∥∥∥y − u(t)∥∥∥2 (90) ≤ ( 1− 1
2 ηλmin
( G(0) ) + 2βη2n4.5 α2
b2 + α4 b2 η2n4 )∥∥∥y − u(t)∥∥∥2 ≤ (
1− 1 4 ηλmin
( G(0) ))∥∥∥y − u(t)∥∥∥2 (91)
where we use Equation 82, Equation 84 and Equation 85 in Equation 90.
Taking log both the sides, we get
log ( ESt ∥∥∥y − u(t+1)∥∥∥2 2 ) ≤ log (∥∥∥y − u(t)∥∥∥2)− 1 4 ηλmin ( G(0) ) Using Jensen’s inequality, we get
ESt log (∥∥∥y − u(t+1)∥∥∥2 2 ) ≤ log (∥∥∥y − u(t)∥∥∥2)− 1 4 ηλmin ( G(0) ) (92)
Thus, for t ≥ 0, using Equation 89 and Equation 92, we get
log (∥∥∥y − u(t)∥∥∥2 2 ) ≤ √ tO ( η n2α2 b ) n+ log (∥∥∥y − u(0)∥∥∥2 2 ) − Ω ( 1 4 ηλmin ( G(0) )) t
≤ log (∥∥∥y − u(0)∥∥∥2
2
) − √ηλmin (G(0))Ω(√t)−O(√ η λmin ( G(0) ) n3α2 b )2
+O
(√ η
λmin ( G(0) ) n3α2 b
)2
≤ log (∥∥∥y − u(0)∥∥∥2
2
) − √ηλmin (G(0))Ω(√t)−O(√ η λmin ( G(0) ) n3α2 b )2 + 1 ≤ log (∥∥∥y − u(0)∥∥∥2 2 ) − I t ≥ n6α4 b2λmin ( G(0) )2 Ω(ηλmin (G(0))) t+ 1 ≤ log (∥∥∥y − u(0)∥∥∥2
2
) − I t ≥ n6α4 b2λmin ( G(0) )2  b2λmin ( G(0) )2 βn6α4 t+ 1
(93) Hence, if t ≥ Ω ( n6α4
b2λmin(G(0)) 2 β log
( n )) , we have
log (∥∥∥y − u(t)∥∥∥2 2 ) ≤ log ( O (n) ) − Ω ( log ( n )) ≤ log ( )
implying ∥∥∥y − u(t)∥∥∥2
2 ≤ . Also, let T0 = n
6α4
b2λmin(G(0)) 2 . Then, applying Equation 93 in chunks of
steps T0, we get ∞∑ t=0 ∥∥∥y − u(t)∥∥∥ ≤ 2T0O (√n)+ 2T0O (√n) 2 + O (√ n ) 4 + ... = O (√ nT0 ) (94)
which implies
∞∑ t=0 ∥∥∥w(t+1)r −w(t)r ∥∥∥ = ∞∑ t=0 η ∥∥∥∇(t)r ∥∥∥ = ∞∑ t=0 η ∥∥∥∥∥∥ ∑ i∈St arφ ′ ( wTr xi ) xi ∥∥∥∥∥∥ ≤ αn 1.5η √ logm
b √ m
∞∑ t=0 ∥∥∥y − u(t)∥∥∥ (95) = αn2η √ logm
b √ m
T0 (96)
where in Equation 95 we use the fact that maximum magnitude of ar is √ logm with high probability.
Also, for ∥∥∥G(t) −G(0)∥∥∥ to be less than 12λmin (G(0)), we need to have (Lemma M.11)
∥∥∥w(t)r −w(0)r ∥∥∥ ≤ λmin ( G(0) ) 4αβn
Thus, for both the conditions to hold true, we must have
m ≥ Ω  n6α4β2 logm b2λmin ( G(0) )4  (97)
Lemma M.11. If activation function φ is α-lipschitz and β-smooth and ∥∥∥w(t)r −w(0)r ∥∥∥ ≤
λmin ( G(0) ) 4αβn , ∀r ∈ [m], then
λmin
( G(t) ) ≥ 1
2 λmin
( G(0) )

heading: Proof.
text: ∣∣∣g(t)ij − g(0)ij ∣∣∣ = 1m ∣∣∣∣∣∣ m∑ r=1 a2rφ ′ ( w(t)Tr xi ) φ′ ( w(t)Tr xj ) − a2rφ′ ( w(0)Tr xi ) φ′ ( w(0)Tr xj )∣∣∣∣∣∣ ≤ 1 m  m∑ r=1 a2r  max r∈[m]
∣∣∣∣φ′ (w(t)Tr xi)φ′ (w(t)Tr xj)− φ′ (w(0)Tr xi)φ′ (w(0)Tr xj)∣∣∣∣ ≤ max r∈[m] ∣∣∣∣∣φ′ (w(t)Tr xi) ( φ′ ( w(t)Tr xj ) − φ′ ( w(0)Tr xj
))∣∣∣∣∣ + ∣∣∣∣∣φ′ (w(0)Tr xj) ( φ′ ( w(t)Tr xi ) − φ′ ( w(0)Tr xi
))∣∣∣∣∣ ≤ max r∈[m] 2αβ ∥∥∥w(t)r −w(0)r ∥∥∥ . (98)
Hence, ∥∥∥G(t) −G(0)∥∥∥ F ≤ max r∈[m] 2Lβn ∥∥∥w(t)r −w(0)r ∥∥∥
Since λmin ( G(t) ) ≥ λmin ( G(0) ) − ∥∥∥G(t) −G(0)∥∥∥
F ,
we have λmin ( G(t) ) ≥ λmin ( G(0) ) − max r∈[m] 2αβn ∥∥∥w(t)r −w(0)r ∥∥∥ .
Thus, for λmin ( G(t) ) ≥ 12λmin ( G(0) ) , we have
max r∈[m] ∥∥∥w(t)r −w(0)r ∥∥∥ ≤ 14αβnλmin (G(0)) .

heading: N SOME BASIC FACTS ABOUT HERMITE POLYNOMIALS
text: For ρ ∈ [−1, 1] we say that the Gaussian random variable (v0, v1) is ρ-correlated if
(v0, v1) ∼ N ( 0, ( 1 ρ ρ 1 )) .
Fact N.1 (Proposition 11.31 in O’Donnell (2014)).
E(v0,v1) ρ-correlatedHen (v0)Hem (v1) = { ρn if n = m, 0 otherwise.
where recall that Hen denotes the degree-n probabilists’ Hermite polynomial given by (10).
The following fact follows immediately from the previous one. Fact N.2. For an activation function, define function R : R→ R by
R(ρ) := E(v0,v1)∼ ρ-correlated φ(v0)φ(v1). Then,
R(ρ) = ∞∑ a=0 c̄2a (φ) ρ a,
where c̄a (φ) is the a-th coefficient in the probabilists’ Hermite expansion of φ. The function satisfies the following two properties.
• ∣∣R(ρ)∣∣ ≤ R(|ρ|), • R(ρ) is increasing in (0, 1).
In the following we let Σ := ( ρ00 ρ01 ρ01 ρ11 ) .

heading: Lemma N.3.
text: E(v0,v1)∼N (0,Σ)Hen ( v0√ ρ00 ) Hem ( v1√ ρ11 ) =  ( ρ01√ ρ11ρ11 )n if n = m, 0 otherwise.
Proof. The proof follows from the proof of Fact N.1, by using the r.v. (ṽ1, ṽ2), defined by
ṽ0 = v0√ ρ00 ṽ1 = v1√ ρ11
so that vector (ṽ1, ṽ2) ∼ N ( 0,Σ′ ) where Σ′ :=  1 ( ρ01√ ρ00ρ11 )( ρ01√ ρ00ρ11 ) 1 .

heading: Lemma N.4.
text: Ev∼N (0,Σ) φ ( v0√ ρ00 ) φ ( v1√ ρ11 ) = ∞∑ a=0 c̄2a(φ) ( ρ01√ ρ00ρ11 )a .

heading: Proof.
text: Ev∼N (0,Σ)φ ( v0√ ρ00 ) φ ( v1√ ρ11 )
= Ev∼N (0,Σ) ∞∑ a=0 ∞∑ a′=0 c̄a(φ)c̄a′(φ)Hea ( v0√ ρ00 ) Hea′ ( v1√ ρ11 )
= ∞∑ a=0 c̄2a(φ) ( ρ01√ ρ00ρ11 )a = R ( ρ01√ ρ00ρ11 ) where we use Lemma N.3 and Fact N.2 in the final step.

Review summaries:
The paper aims to characterize for different activation functions the minimum eigenvalue of a certain gram matrix that is crucial to the convergence rate for training over-parameterized neural networks in the lazy regime (small learning rate). On this front, the paper shows that for non-smooth activations the minimum eigenvalue is large under separation assumptions on the data improving on prior work. However, for smooth activations the authors show that the minimum eigenvalue can be exponentially small (or even 0 in case of polynomials) if the data has low-dimensional structure or the network is sufficiently deep. The authors experimentally validate the observations on synthetic data.