Effect of Activation Functions on the Training of Overparametrized Neural Nets
Authors: Abhishek Panigrahi
Abhishek Shetty
Navin Goyal
Venue:  (2020)
Keywords: activation functions
deep learning theory
neural networks

Abstract: It is well-known that overparametrized neural networks trained using gradient based 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 ﬁrst 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 satisﬁes 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 sufﬁcient. 
We discuss a number of extensions and applications of these results.

Published as a conference paper at ICLR 2020
EFFECT OF ACTIVATION FUNCTIONS ON THE TRAIN- ING OF OVERPARAMETRIZED NEURAL NETS
Abhishek Panigrahi Microsoft Research India
Abhishek Shetty Comeel University
Navin Goyal
Microsoft Research India
t- a-abpani @mi crosoft.com com
a shettyêcs www.ell.o....oooooo edu
navingo@ne crosoft. com
ABSTRACT
It is well-known that overparametrized neural networks trained using gradient- based methods quickly achieve small training error with appropriate hyperparam- eter 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 eigen- value 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 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. 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 point where either the first order or second order derivative discontinuous, all eigenvalues of the associated Gram matrix are large under minimal assumptions on the data.
For smooth activations such 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 sufficient.
We discuss number of extensions and applications of these results.
INTRODUCTION
It 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 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 bounded domain be approximated arbitrarily well by finite neural network with one hidden layer. This theorem is generally stated for specific activation functions such as sigmoid ReLU. A more general form of the theorem shows this for essentially all non- polynomial activations (Leshno et al., 1993; Pinkus, 1999; Sonoda & Murata, 2017). This theorem
Work done when the author was Microsoft Research India

---

Published as a conference paper at ICLR 2020
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 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 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 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 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 anal- ysis of neural network training has seen vigorous activity of late and significant progress was made for the case of highly overparametrized networks. At 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 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. 2); 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 matrix G, either explicitly (Jacot et al., 2018; Du et al., 2019a;b) or implicitly (Allen-Zhu et al., 2019). (This matrix also occurs earlier works (Xie et al., 2017; Tsuchida et al., 201 8))) Amin (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 Amin (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 kink, i.e., those with 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 O. These results
2

---

Published as a conference paper at ICLR 2020
imply that for such activations, training will be rapid. We also provide 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 few examples: Let n be size of the dataset which is collection of points in IR, and let d' be the dimension of the span of the dataset. For quadratic activation, if d' = OVnn), then the minimum singular value is O. For tanh and swish, if d' = O(log" 0.73 n)), then the minimum eigenvalue is inverse superpolynomially small (cxp(- (cxp(-S2(m) (m 1/2d" ))). In fact, significant fraction of eigenvalues can be small. This implies that for such datasets, training using smooth activations will be slow 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 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 simplify exposition; extensions of various types including the ones that drop the above restriction are possible and discussed in Section 5.
2 PRELIMINARIES
Denote the unit sphere in R" by Sa-1 := {u IR: ||u||2 1] where /hlre//ull || := >i= uf For u, V E IR", define the standard inner product by (u, v) == Σ, u,d; Given a set S, denote by u (S) the uniform distribution over S. _N(H, denotes the univariate normal distribution with mean ş and variance o². Let Ig denote the indicator of the set S. For matrix A containing elements a.j. a, denotes its i-th column. We define some of the popular non-tradin non-traditional activation functions T+c- (Ramachandran et al., 2018) (called SiLU in Elfwing et al. (2017)); ELU(x) max (I, 0) + min (ar, 0) (e* - 1) (Clevert et al., 2016); SELU := ai max (1r, 0) + 02 min (z. 0) (e* 1). where and ag are two different constants (Klambauer et al., 2017). See Appendix B for more definitions.
here: swish(x:)
We consider 2-layer neural networks
m7
F(x:a, W)
Co
Σ a
T x)
(I)
m
where E Rd is the input and W- [Wi: Ww....., Wm. R is the hidden layer weight matrix and a E Ihm is the output layer weight vector. Activation function Φ: IR - R acts entrywise on vectors and ex I,, (2) In the case of one hidden layer nets, we set co 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 W and a have been initialized i.i.d. from the standard Gaussian distribution. This initialization and the parametrization in Equation I are from Du et al. (2019b). Together, these will be referred to as the DZPS setting. Parametrization in practice does not have co_ in Equation I; standard initializations in practice include He (He et al., vmm 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 ((x, y: } where x, E Rd and ys E R. we want to find the best fit weights W so that the quadratic loss C([ })) a, W) = = E"
F'x;;; a, W))² 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 (+++1) = w(() - v/ w ((W where ((i) denotes the weight matrix after steps of gradient descent and n > 0 is the learning rate.
(4) The output vector (1) E RD is defined by u, := F(x;; a, W(O).
3

---

Published as a conference paper at ICLR 2020
Next, we define the matrix alluded to earlier, the Gradient Gram matrix G E R associated with the neural network defined in (1), referred to as the G-matrix in the sequel:
91.5
= m ArE
Σ
aî (w x (w (x,
(2)
[m]
We will often work with the related matrix M E RRddx, whose i-th column is obtained by vectorizing F(x, 9i), i.e., M == axd' (w xx) x; for k E [m]] G is a Gram matrix: G
1 M Denote by X₂ (G) the i-th eigenvalue of G with A1 2 >2 2 ..... and similarly by (M(M)
m
the i-th singular value of M. These quantities are related by A, A₂ = of
Following Allen-Zhu et al. (2019), we make the following mild assumptions on data. Assumption 1. ||x:||2 = Vi [m]-
Assumption 2. [[, x;x; |x,|12 2 5 Vi,j E [m], j iee, the distance between the subspaces spanned by x, and Xj is at least > 0.
Assumption 1 can be easily satisfied by the following preprocessing: renormalize each x; so that ||x||| S 1/v2, add another coordinate to each x; that ||x; = 1/v2 and then add another coordinate with value 1/v2 each X;. This ensures that ||x; Xyl12 implies Assumption 2 for Kx.X,, which we later verify empirically for CIFARIO.
3 REVIEW OF RELEVANT PRIOR WORK
To motivate the importance of the G-matrix, let us first consider the continuous time gradient flow dynamics W(()) = - VWL((W()) 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 Let y E R" be the vector of outputs. It follows from an application of the chain rule that ( = (t)) (y u(t) ( Here gi.j == 1 (x,,x) E o' (wi
(!) <,w (w(")) x.). It can be shown that as oo, the matrix ( remains close to its initial value G 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 ( is given by
(t)T xz)
m
y y
Σ (e v.v (y ('))).
(3)
KE(N)
Thus, it can be seen that the eigenvalues of the G-matrix, in particular Amin (Gi control the rate of change of the output of the neural network towards the true labels. The following result plays central role in the present paper.
Theorem 3.1 (Theorem 4.1 of Du et al. (2019a)). Let be ReLU. Define matrix G as (x,. Assume X = Amia (G >> O. If we set "",,,xx,, I="
G == Ew>
m 2 2 (n and n I O (Xn 3) and initialize Wk (0,La) and ag u --,,,+1 +1}
for k E [m]. then with probability al least 1 over the random initialization, for L 2 1 we have
Ily - u0 < (1 0.5mA) |yy u
In the theorem above it can be seen that the time required to reach a desired amount of error is inversely proportional to X. Du et al. (2019b) extended the above result 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 non-singular. But the following theorem, from Du 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 - 2o but for more general non-pon polynomial Lipschitz activations was shown in Jacot et al. (2018) using techniques from Daniely et al. (2016).
Lemma 3.2 (Lemma F. in Du et al. (2019b)). o a non-polynomial analytic function and x; and Xj not parallel for distinct i, E [n), then Amin (G*)) > 0.
In these papers the number of neurons required and the rate of convergence depend on Amiu ( (Ge) (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 Amin (G²).
4

---

Published as a conference paper at ICLR 2020
Allen-Zhu al. (2019) considered L-layer networks using ReLU (see Appendix D for details their parametrization). A major step in their analysis is a lower bound on the gradient norm at each step. Theorem 3.3 (Theorem
Allen-Zhu et al. (2019)). With probability
least
(oo--9(mmpoly(m 3))) with respect to the initialization, for every W such that [W-WWi /W-Wollee //poly(n.8*)) ) we have VV (W) ll ((C(W)
We show that Amin (G) is directly related to the lower bound on the gradient in the case of ReLU. It clear the same method can be extended 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 ())) in the limit m - oo, we will focus on proving high probability bounds for eigenvalues of ())
MAIN RESULTS
4.1 ACTIVATIONS WITH A KINK
For any positive integer constant r, presence of 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 (xx) (xx)) I=<aa + (2 Zzza. where -1 < 1. Recall that C*+1 denotes the set of r + times continuously differentiable functions. We need Φ1 and Φz to satisfy the following set of conditions parametrized by and denoted J,:
Φ1, 12 E C*+1 in the domains (-o0, a) and [a, oo), respectively.
The first (r + 1) derivatives of Φi and 6b2 are upper bounded in magnitude by 1 in (-20, a] and [a, 00) respectively.
For 0 - i we have o (a) (a).
(a) - (a)) 1, i.e., the r-th derivative has jump discontinuity at
Remark. We fix the constants in Jr to 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(Vlog m), O( O(Vlogm))
J, covers activations such as ReLU, SELU and LReLU, while J2 covers activations such as ELU. Below state the bound explicitly for J2. Similar results hold for J, for 2 See Section K for details.
Theorem 4.1 (J2 activations). If the activation & satisfies J2 then we have
Amin (G 2 12 "log n) 1)
with probability at least 1 - e ((6m/n²) with respect to {w (0) (0) Jm and {ak (0) mm ym given that
m > max(1((220~1 log(n-=))) ( log d)).
The theorem above shows that the presence of a jump discontinuity in the derivative activation function (or one of its higher derivatives) leads to fast training of the neural network. For the special case 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 > 9((18-3 log' n)), then Amiu (G(O) 2 Q((8 -o5
1.5 n), with probability least -- -00mmm0 "n Ing 33)) m).
The dependence
in the above bound is inverse- polyooorpooylog opposed to unverse-polynone that seems to result from using the technique of Allen-Zhu et al. (2019). It implies that with m ②n /86) in poly(log(n/c), 1/5) steps gradient descent training achieves error less than c.
4.2 SMOOTH ACTIVATIONS
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.
5

---

Published as a conference paper at ICLR 2020
Negative results for smooth activations. The G-matrix of constant degree polynomial activations, such as quadratic activation, must have many zero eigenvalues; and of sufficienlly smooth activations, such as tanh swish, must have many small cigenvalues, 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 o' dx(x)= - ca and let d' = dim (xp.n_x.......... = (vn Then we have Xain (G (G))))
0. Furthermore, 2x= for k 2 [n/d"].
Theorem 4.4 (restatement of Theorem F.10). Let the activation function be tanh and let d' dim(span/x3 ... x, = (log"..5
0.75 r2). Then we have Amin Xmin((( (G( S exp(-9(nn)/20 )) with prob- ability at least - 1 1/n2as over the random choice of weight vectors {w (0) Lm Furthermore, the same upper bound is satisfied by 2 for k 2 [n/d"].
and {az (0) Im k Jkmi
Jkm1'
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 cigenvalue of the G-matrix for all reasonable activation functions is large:
Theorem 4.5 (informal version of Theorem E. 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 = (log 0.76 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 + oo 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 ( and with d the corresponding eigenvalue. With probability least lly-u 12 I (Ei (1 (1-1)))?( (vV (y 10))) +c, provided m 2 Q(n"x= ->miu (G( )(0))~4(") 2 and 1) S O(n Xmin ())
over the random initialization, the following holds for t 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 Amin ()) 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 :.. Xn, is P(n"), for constant y Furthermore, we assume that the data is smoothed in the following sense. We start with a preliminary dataset x'....,XX X", with the same span V. then we perturb each data point by adding i.i.d. Gaussian noise, i.c. x; = x + n; 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 1.4 respectively.
Theorem 4.7 (Informal version of Corollary L.42)). Let the activation be tanh, let the perturbation noise be of the order (R/ and d' = dim x xx,} 2 Q(n"), ), for constant y. Then we have Amin(G (G) 2 ((8(2/7)) -(3/7)) with probability at least 0.99 w.r.t the noise matrix N, {wk 1m and {a
(0) 1m Jk= provided m (118/18-4/7)
We now say a few words about our assumption that the data is smoothed. Smoothed analysis, originating from Spielman & Teng (2004), is general methodology for analyzing efficiency of algorithms (often those that work well in practice) and can be thought of as a hybrid between worst- case 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

---

Published as a conference paper at ICLR 2020
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 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. (2)19b) 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 denote this matrix by G 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 and Assumption 2. Let the depth L satisfy L = O(log 1/8). Then Xmin (G(o) n) > 1/poly(n) (n) with high probability, provided m 2 Q (poly(n,
5 EXTENSIONS
For large part of the paper confine ourselves 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 J, (Section M.5).
Generalization bounds from Arora et al. (2019c) can easily be extended to the set of functions satisfying J, using techniques from Du et al. (2019b). Similarly, techniques from Allen-Zhu et al. (2019) for higher depth generalize to funetions such as SELU, LReLU and ELU. We believe this also generalizes to J, Other loss functions such 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 the core issues about activations. We briefly discuss extension to more general classes of activations in Appendix H.
6 PROOF SKETCH
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 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 fc(w) == E &'
x;) (xxxx+ x4.
Theorem 6.1 (Informal statement of Claim K.2). Let Φ E J1. For any Ç S5-11, fc(w) has large norm with high probability for a randomly chosen standard Gaussian vector w.
Using an e-nct argument on Ç, the above result implies 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)
Ei=,S Ss d' ((w' + + +') are fixed to constant values with good probability over the choice of For the exceptional summand, say Sj d'((w' + w")T x,) )x,, the choice of w' is such that the argument (w' + +w"""xx x, 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 ll.fç (w)]l 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.
7

---

Published as a conference paper at ICLR 2020
We work with event E' involving w': in the sum defining fc(w) there is one exceptional summand S o' d'((''+ (w''ww") +w")"xx x,) x, such that the sum involving the rest of the summands-whin not fixed to constant value unlike for ReLU-doc not change much over the random choice of w". Whereas the exceptional summand varies 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 Jz. The goal again is to show that for any Ç E Sn-1, the function fc (w) has large norm with good probability for the random choice of w. To this end, we consider the Taylor approximation of g (w) == Σi= Si Ø' (w""x, around w', that is, g:(w' + w") = 9:(w") + (V weg (w')) + H(w,, w") where H is the error term. We show that V 9 (w')l is likely to be large over the random choice of w', and so (Vwgc(w) (w'))"w" w 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 |/V (w')l is large, note that Vwgc (w") = >n Zim1 Se (w"" x, x,, which allows us to use the argument above for fc(w) being large in the case of J1. This implies that gc (w) is large with good probability, which implies, with further argument, that fc(w) is large. Full proofs of these results can be found in Appendix K. As mentioned earlier, the argument can be generalized to condition J. 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 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 = M M²M/m M/m. In this case, the problem of computing the smallest eigenvalue reduces finding a non-trivial linear combination of the columns of M resulting in O. 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 O. 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 low-dimensional subspace.
Given that polynomials have singular M M-matrices, 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 's approximation. The Taylor series for tanh' around 0 has a radius of convergence T/2. Depending on the initialization and m, the argument of the function can take values outside |-x/2, π //2.. To circumvent this difficulty, consider different notion of approximation. Consider a series of Chebyshev polynomials > an TT,()) that approximates tanh' (z) in the - norm in some finite interval. The fact that tanh' can be extended analytically to the complex plane can be used 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 _ by (Chebyshev) polynomials error 0 using polynomial of degree O log(k/e)).
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 mn)). This leads the degree of polynomial 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 natural relaxation the appappooxnnottion 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 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 in the 12-norm with respect to the Gaussian measure by (Hermite) polynomiuls of degree p with error exp(-S(()) ((V))..
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
8

---

This implies that for sufficiently large L, the Gram matrix of the output of the penultimate layer, i.e. (X(1-1))Tx(I--)) where ( [x((-1) ....,xh--11 x is diagonally-dominant and has large minimum eigenvalue. The rest of the proof has some overlap with the proof for smoothed data Published as a conference paper at ICLR 2020
underlies Theorem L.2). The L La-apoooximation gives us bound 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 cigenvalues of the G-matrix are indeed small 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 I 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 essentially tight when the data is smoothed. is well-known (see Fact C.9) that the minimum singular value of a (tall) matrix Mi is lower-bounder as follows: take 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 Amia (G(O) 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 = Xi,-.. Xx.). (b) the p-th Hermite coefficient of tanh' (see Lemma 1.1 and Lemma 1.2). We use p to be approximately equal to I/y, For (a) we use the above strategy to lower bound the minimum singular value of X 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-Win 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 result of Boyd (1984) implying that the upper bound exp( (VP) 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 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 I (0. ..... L - 1), let x!" be the output of layer I on input x;- We track the behavior of the x; as I increases:
(1)
Lemma 6.5 (informal version of Lemma J.1 and Lemma J.2). As l increases, the Euclidean norm of (1) is approximately preserved. On the other hand, for every i + (xx()) shrinks. each x
xh
above. For each p 2 0, Amia (G))) can be lower bounded by a product involving (a) the minimum eigenvalue of the p-th Hadamard power of the Gram matrix of x x("-"), and (b) the p-th Hermite coefficient of tanh' (see Equation 47). For (a) we use the diagonal-dominanee of the Gram matrix. For (b) we proceed as in the case of smoothed data. The choice p = O(log n) turns out to give the best lower bound on Amin (G)
EXPERIMENTS
Synthetic data. We consider n equally spaced data points on St, randomly lifted to $9. We randomly label the data-points from 1 1). We train 2-layer neural network in the DZPS setting with mean squared loss, containing 10th neurons in the first layer with activations tanh, ReLU, swish and ELU at learning rate 10 The output layer is not trained during gradient descent. In Figure ((a) and Figure ((b) we plot the squared loss against the number of epochs trained. Results averaged over 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 I(c) and Figure I(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 1 images from CIFAR10 dataset (Krizhevsky & Hinton, 2009). We train a 2-layer network containing 10" neurons in the first layer. First, we verify Assumption 2 regarding 5-separation of data samples. We plot the I.2- disttnnss between all pairs

---

Published as a conference paper at ICLR 2020
MSE via Iteraiion no 10
MSE vis beration: na 50
Eigen value opmperison: ne 10
Eigen value comperison: n-
Sew lug Egarrsaaaa Sgmmaaatt
Squaroo anoor
Square
Sue by
Ieraaion (110)
lleraton (1)))
Eigerwolue indices
Eigenvalue indioes
(a)
(b)
(d)
ReLU
ELU
Swish
Quadratic
Tanh
Figure 1: Experiments on syntheric dataset (From left to right) (a)Rate of convergence of 2-layer network for different activations when n = 10 (b) Rate of convergence of 2-layer network for different activations when 50 (c) Eigenvalues of the G-matrix at initialization for different activations when n = 10 (d) Eigenvalues the G-matrix at initialization for different activations when n = 50
of preprocessed images (described in Section 2) in Figure 2(a). It shows that the assumptions hold for CIFARIO, with 8 at least 0.1. Figure 2(b) has the plot of the cumulative sums of eigenvalues, normalized 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 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' much difference between the spectrum of ELU and tanh. This is likely due to the fact that are in the regime of Theorem 1.4.
We observed difference in the rate of convergence while training 2-layer network, with both layers trainable, using 256 batch sized stochastic gradient descent (SGD) with cross entropy loss on the random subset of CIFARIO dataset 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 Figure 2(d) can be attributed to the eigenvalue plots in Figure 2(c) only in the first few iterations of SGD.
Marte
bigennolue Compatioon
B5sc 2irg Eigeraatte
Pai's sorted basod on 12 dizanco
Egensilus Indec (Base 2 Boak)
Dgemmnue Indions
lara (190)
(b)
(c)
(d)
ReLU
Tanh
Swish
ELU
Figure 2: Experiments on random subset of 10 images from CIFAR10 dataset: (a) L disttnnes between all pairs of preprocessed images (b) Semilog plot of sum of squares of top & singular values of data matrix (c) Figenvalue distribution of G-matrix at initialization (d) Convergence speed of layer networks using different activation functions.
8 CONCLUSION
In this paper 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 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 practice, most theoretical results in the recent literature (including the present paper) require the size of the networks be very large and the learning rate 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?
aware of. Many avenues for further investigation remain: there
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterizee neural networks, going beyond two layers. CoRR, abs/1 111..11.99999 1.00918, 2018. URL http: org/abs/ 11111111000111 04918.
Zeyuan Aluen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 242-252, Long Beach, California, USA, 09-15 Jun 2019. PMLR. URL http:/ ppwpeedinggs ngs m1 pre.sssssss..................ere / / aalaalllenllee len zhu1 1 9a html.
Joseph Anderson, Mikhail Belkin, Navin Goyal, Luis Rademacher, and James R. Voss. The more, the merrier: the blessing of dimensionality for learning large gaussian mixtures. In Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014, pp. 1135-1164, 2014. URL http://t//// http:::ppopeoeeinngggg.. proceedings
mlr press/ /tnssss/v////// 205//nndrsonnl 4. .hmml.
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gra- dient descent for deep linear neural networks. In 7th International Conference on Learn- ing Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019a. URL net forumridd SXM0g333C.....
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, Russ Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In NeurlPS, 2019b.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhi yuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. volume abs/1901.08584, 2019c.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities. Oxford Univer- sity Press, Oxford, 2013. ISBN 978-0-19-9555 19-85--9--9555255. doi: 101009//pp0f10009001993333
001.0001. URL https : / doi org/ /10 1093/ ccprof oso / 97801 9780199535255 0001.
0001. nonasymptotic theory of independence, With a foreword by Michel Ledoux.
John P Boyd. Asymptotic coefficients of hermite function series. Journal of Computational Physics, 54(3):382-4111 1984.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. SGD learns over- parameterized networks that provably generalize on linearly separable data. In 6th International Conference on Learning Representutions, ICLR 2018, Vancouver, BC, Canada, April 30 May 2018, Conference Track Proceedings, 2018. URL hwtphttpp///ccm ttttttss:/opprreeeee ew net/ forum? idd=r33wwxRR.
Anthony Carbery and James Wright. Distributional and L norm inequalities for polynomials over convex bodies IR", Math. Res. Lett. 83):2333244, 2001. ISSN 1073-2780, doi: 10.4310MRL. 2....v8.n3.al. URL https: /tw.i/ooiiii////oo//oooo wowooooorg/ai /10 4310 /310/MMLL //RL. 2001. v8 .3.
Lénaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. In S. Bengio, H. Wallach, H. Larochelle, K. Grau- man, N. Cesa- Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Sys- tems 31, pp. 3036-3046. Curran Associates, Inc., 2018. URL http: /ttp://paapp.aeee nips. ca/ ca/paper///cccccccccccccc 7567 over-paaramtterizeerr
o -es.ddeeeettteeeee------- s -
pdf.
Djork-Aréé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). In ICLR, 2016.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks:
The power of initialization and a dual view on expressivity. In Advances Neural Information Processing Systems, pp. 2253-2261. 2016.

---

Published as a conference paper at ICLR 2020
Simon S. Du and Jason D. Lee. On the power of over over-vvereae parametrization in neural networks with quadratic activation. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan. Stockholm, Sweden, July 10-15, 2018, pp. 1328-1337, 2018. URL ftstp://proeeee ngs. mm press / w80/ du 8a html.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In ICLR, 2019a.
Simon Shaolei Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima deep neural networks. ICML, 2019b.
Steffen Eger. Paul Youssef, and Iryna Gurevych. Is it time to swish? comparing deep learning activation functions across nlp tasks. In EMNLP, 2018.
Stefan Elfwing, Eiji Uchibe, and Kenji Doya. function approximation in reinforcement learning. CoRR, abs/1702.031 18, 2017. URL http: 03118.
linear units for neural network
// wwg.iii.org/bb....
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks, In Yee Whye Teh and Mike Titterington (eds.). Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pp. 249-2549 Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010. PMLR. URL http: http::://occcedddeeeeeeeo www.ggsmm.....................e. mlr..rr....... press/ /v/ /l/poolooaaaaamm htmi.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. http: //www. www.ddeepppa... inggegoooon.gooo....oo.ooooooo.. org.
Boris Hanin. Which neural net architectures give rise exploding and vanishing gradients? In S. Ben- gio, H. Wallach, H. Larocellee, K. Grauman, N. in Neural Information Processing Systems 31, pp. 582-591. Curran Associates, Inc.. 2018. URL http: /ttp:r//apppr..e nips, https/ccpppppppppppeeeeeeeeeepp which wtwp:/33---hhcc--eeeeaaaaaa neural wewt-architeetueeeeee ing.---aaaaiinnnnnnnnnnnaeeaeeee
and R. Garnett (eds.), Advances
pdf.
Boris Hanin and David Rolnick. How to start training:
The effect of initialization and architecture. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 571-581. Curran Associates, Inc.. 2018. URL http: http::://ppppssaeeem nips oc patpp//pppr/ee/e//// cttpp//pppppppppp//3/////// how-sahhoww----- how- to- wtto--statttttiiiiteeee
Soufiane Hayou, Arnaud Doucet, and Judith Rousseau. On the impact of the activation function on deep neural networks training. CoRR, abs//1922.06853 2019. URL htttp://arxiv/ abs/1902 06853.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026- 1034, 2015.
Einar Hille. Contributions the theory of Hermitian series. II. The representation problem. Trans. Amer. Math. Soc., 47:80-94 94, 1940. ISSN 0002-9947. doi: 10,2307/1990002. URL https:
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 8571- 8580. Curran Associates, Inc., 2018. URL http: / papers nips cc htee/appr//5e 8076- neural-tanger -errentt-eereel kernel convergence and generalieeieeee wiaiiriiiiiiiioiiioii in in- -eurall networks.pdr pdf.
CG Khatri and C Radhakrishna Rao. Solutions to some functional equations and their applications to characterization of probability distributions. Sankhyā: The Indian Journal of Statistics, Series A. pp. 167-180, 1968.
Joe Kileel, Matthew Trager, and Joan Bruna. On the expressive power of deep polynomial neural networks. In NeurlPS, 2019.
12

---

Published as a conference paper at ICLR 2020
Günter Klambauer, Thomas Unterthiner, Andreas Mayr, and Sepp Hochreiter. Self-norma neural networks. Advances in neural information processing systems, pp. 971-980, 2017.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Beatrice Laurent and Pascal Massart. Adaptive estimation of quadratic functional by model selection. Annals of Statistics, pp. 1302-1338, 2000.
N. N. Lebedev. Special functions and their applications. Dover Publications, Inc., New York, 1972. Revised edition, translated from the Russian and edited by Richard A. Silverman, Unabridged and corrected republication.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. arXiv preprint arXiv:1711.00165. 2017.
Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural Networks, 6(6):66 867, 1993. ISSN 0893-6080. doi: https://doii. https://do..org/IWW 10. 1016/S0893- 6080(05)80131- URL http::///// //tp:://ww... sciencedirect. com wwweecnneeaariiiie p11/50893608005555
Yuanzhi Li and Yingyu Liang. Learning overparameterizee neural networks via stochastic gradient descent on structured data. In S. Bengio, H. Wallach, H. Larochelle. K. Grauman, N. Cesa- Bianchi, and Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 8157-8166. Curran Associates, Inc., 2018. URL http: /ttt:://pppersee nips ac pappr// 8038-1earning- oewpriggggveerrrreeeeeeeeeee neurall networks -ia- stochastic- deriientdescenne on structured -tr.attredddddaa.ppppo pdf.
Cosme Louart, Zhenyu Liao, and Romain Couillet. A random matrix approach to neural networks. Ann. Appl. Probab., 2802):119--1288, 04 2018. doi: 10.1214/17-AAP1388 URL https: //doi. wrg/orrgg//.. 10. /214/17-AAP131 17-AAP1328.
J.C. Mason and D.C. Handscomb. Chebyshev Polynomials. CRC Press, 2002. ISBN 9781420036114, URL https: /books....//////.oo google..oo.oooooooooooooooo..... co htt.//ookks.ddBrrr0333t0000
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two- layer neural networks. Proceedings of the National Academy of Sciences, 115633):17665-77777 2018. ISSN 0027-8424. doi: 10.1073/pnas. 110073/pnas.10066535 1806579115. URL https: /tts:///wwrr /ww. pnas. org/ content/115/33 http:/1111/3///665555
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Workshop Track Proceedings, 2015. URL http: aariiviiiv orq/ als 1412. 6614.
Chigozie Nwankpa, Winifred Ijomah, Anthony Gachagan, and Stephen Marshall, Activation func- tions: Comparison of trends practice and research for deep learning. CoRR, 0obs/1811.03377 2018.
Ryan O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014.
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterization: global con- vergence guarantees for training shallow neural networks. arXiv preprint 1902:0192.00467. 2019.
Jeffrey Pennington and Pratik Worah. Nonlinear random matrix theory for deep learning. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gamett (eds.), Advances in Neural Information Processing Systems 30, pp. 2637-2646. Curran Associates, Inc., 2017. URL http:/ http://papers. nips. cc/ wccppppp////eee///eeeeeeeeeeeeee 5857 6857 - non linerr------er for-deep-learminng.
matrix: theory-
13

---

Published as a conference paper at ICLR 2020
Jeffrey Pennington and Pratik Worah. The spectrum of the fisher information matrix of single- hidden-layer neural network. In Bengio, H. Wallach, Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 5410-5419. Curran Associates, Inc., 2018. URL http: papers ni mips cc paper/ 7786- spect of--uuuut-------- fi wwwer-infrrmaeee commatioo--aatet ion -itaaatri-------iiiaa--- hidden- layer neural wwwwwrk..eew.................... pdf.
Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli. Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practice. In I. Guyon, U. V. Luxburg, S. Ben- gio, H. Wallach, R. Fergus. S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Infor- mation Processing Systems 30, pp. 4785-4795. Curran Associates, Inc., 2017. URL http: papprss nips cc cc/ paper / 7064 resurrecting the sigmoid- in- -deep- Learning-thrrugg-cyyneeeee dyw.ugghh-nnmmiicccmmm wttaad-ssmmttttttrreeeeeee aareecor-andd-zeee anddyyaat--ppprcceeeee ort.rpaaacaaaaaatttttttoooooooor påf.
Jeffrey Pennington, Samuel S. Schoenholz, and Surya Ganguli. The emergence of spectral universality in deep networks. In International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain, pp. 1924-1932, 2018. URL hwtp:htt//.. http://ppoocceeee httpppppoccenn..ee/ee/p
press/vesseae.. v88 htpp//nnnnnnoonn// 8a htw.oon........m......mm.m.mm
Allan Pinkus. Approximation theory of the MLP model in neural networks. Acta Numerica, 143-195, 1999. doi: 10. 10.10175006242290000999
Prajit Ramachandran, Barret Zoph, and Quoc V. Le. Searching for activation functions. In ICLR Workshop, 2018
Mark Rudelson and Roman Vershynin. Smallest singular value of a random rectangular matrix. Communications Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, (7112):707-17333 2009.
Shai Shalev-Shwarts Ohad Shamir, and Karthik Sridharan. Learning kernel-based halfspaces with the 0-1 loss. SIAM J. Comput., 40(6):1623-1646 December 2011. ISSN 0097-5397. doi: 10.1137/100806 12.. URL http::/tt/// //x:::://d/////// doi. 00.....0./.....1111100000.66..6 1011166600.01166
Sho Sonoda and Noboru Murata. Neural network with unbounded activation functions is universal approximator. Applied and Computational Harmonic Analysis, 43(2):233 268, 2017. ISSN 1063- 5203. doi: http:///iiinneeeeeeree/////////. com/
URL http: : /tww.//wwk//m enceei rect.
Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM, 51(3):385 463, 2004. doi: 10. 14519999900 990310. URL ottp::/// 911...90081191000000 991.1////990009999111..
Gábor Szegö. Orthogonal polynomials. American Mathematical Society, Providence, R.I., fourth edition, 1975. American Mathematical Society, Colloquium Publications, Vol. XXIII.
Sundaram Thangavelu. Lectures Hermite and Laguerre expansions, volume 42 of Mathematical Notes. Princeton University Press, Princeton, NJ, 1993. ISBN 0-691-00048 With preface by Robert Strichartz.
Russell Tsuchida, Farbod Roosta- Khontta-K and Marcus Gallagher. Invariance of weight distributions in rectified mips. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmmässan, Stockholm, Sweden, July 10-15, 2018, pp. 5002-5011, 2018. URL http: /ttpp/ppopcenn..eeeeeeeepee .mlr. arrss//800tsuccidee. htt.dlllll...............
Richard S Varga. Gersgorin and his circles, volume 36. Springer Science & Business Media, 2010.
Hermann Weyl. Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Dif- ferentialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung) Math. Ann. 71(4) 1912. ISSN 0025-5831. doi: 10.14444/ URL https: //doi 111.11111110001111111111
14

---

Published as a conference paper at ICLR 2020
Bo Xie, Yingyu Liang, and Le Song. Diverse neural network learns true target functions. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS
2017, 20-22 April 2017, Fort Lauderdale, FL, USA, pp. 1216-1224, 2017. URL http:// proceedi ngs. mlmm www.ppress/////e 7a html.
Bing Xu, Ruitong Huang, and Mu Li. Revise saturated activation functions. In ICLR Workshop, 2016.
15

---

Published as a conference paper at ICLR 2020
CONTENTS
Introduction
Preliminaries
3 Review of Relevant Prior Work
4
Main Results
4.1 Activations with kink
4.2 Smooth Activations
5
Extensions
Proof Sketch
7
Experiments
8 Conclusion
10
Additional Related Work
18
B Activations
18
C Preliminary facts and definitions
18
C.1 General Approach for Bounding Eigenvalue of G-Matrix
20
D Standard Parametrization and initializations
20
D.I Note on G-Matrix for Standard Initializations
Lower Bound the Trace of G-Matrix
21
F Upper Bound on Lowest Eigenvalue for tanh
22
F1
Polynomial Activation Functions
22
F.2
Approximation using the Chebyshev Polynomials.
24
F.3
L
Approximation using Hermite Polynomials..
25
E.3.1 DZPS Setting
29
F.3.2
Standard Setting
33
G Upper Bound Lowest Eigenvalue for Swish
35
H A discussion on Upper Bound of Lowest Eigenvalue for General Activation Functions
35
Lower bound on eigenvalues for tanh when the dimension the data not too small
37
Depth helps for tanh
41
16

---

Published as a conference paper at ICLR 2020
K Lower Bound on Lowest Eigenvalue for Non-Smooth Functions
49
K.1 J1: The first derivative is discontinuous at 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 point
53
................................
K.2.1 DZPS setting
53
K.2.2 J2 for Standard Setting
59
A new proof for the minimum eigenvalue for ReLU
60
M Extensions and Additional Discussion
62
M.1 Polynomial minimum eigenvalue of G-matrix at time /
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
Some basic facts about Hermite polynomials
74
17

---

Published as a conference paper at ICLR 2020
A ADDITIONAL RELATED WORK
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 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 an untrained neural network, i.e. the rate convergence of correlation among hidden layer outputs of datapoints to should be of the order poly(Z.) where L is the number of layers. They show smooth activation functions have slower rate and hence, better to use in deep neural networks. However, this set of parameterization, called "edge of chaos", proven 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.
B ACTIVATIONS
introduce some of the most popular activation functions. These activation functions are unary, i.e. of type IR + R, and act on vectors entrywise: f2,t,,f2,...)) (6(t1), (..))....) In this paper we do not study activation functions with learnable parameters such as PReLU, or activation functions such maxout which are unary. Activations functions are also referred to nonlinearities, although the case of linear activation functions has also received much attention.
ReLU(X) max (2r, 0)
LReLU(x)) := max (z, 0) + min (z, 0), where a is constant less than 1
Linear(xx) := I
tan) == 2
2-_1
sigmoid(x) := T+e =
swish(ar) := T+e-r Ramachandran et al. (2018) (called SiLU in Elfwing al. (2017))
ELU(z) := max (xr, 0) min (I,, 0) (e" 1) Clevert et al. (2016)
SELU(z) := max (z, 0) + min (z, 0) (e* - 1), where and are two different
constants Klambauer et al. (2017).
C PRELIMINARY FACTS AND DEFINITIONS
We note some well known facts about concentration of Gaussian random variables be used in the proofs.
Fact C.1. For Gaussian random variable ~ o( Vt E (0, we have
4
21
2
1
5
30
In fact, the following holds true. VI E (0, we have
Po(le- al 1] E (1
4
1 1t
5
40
where 0 < 0.
Fact C.2. For a Gaussian random variable a ~ N(u, o²). Vt E (0, we have Vt 2 0
P, f pl 5 <
2e
=
18

---

Published as a conference paper at ICLR 2020
Fact C.3 (Hoeffding's inequality, see Boucheron et al. (2013)). Let 21, 21, on be independent random variables, where Y; lies in the interval [a,, by], and let ā be the empirical mean, i.e., I Ei z4 Then,
2,2
Pr (1 [z) 2 - 2e
Fact C.4 (Multiplicative Chernoff bound, see Boucheron al. (2013)). Let 31, 22, In indepen- dent random variables taking values in {0, 1}, and let I be the empirical mean, i.e., 2-- = -i 51 Then
Pr (r < 1) E ())
S
(B(e)
(2 ( Se
for all t (0,
Fact C.5 (Maximum of Gaussians, Boucheron al. (2013)). Let 21; -1y be Gaussians
following N (0. Then,
Pr
max x4 & 1 /lylog no 21 iEln
62 2
-1
where & >> 0 is constant.
Fact C.6 (Chi square concentration bound, see lemma 1 in Laurent & Massart (2000)). For variable x that follows chi square distribution with k degrees of freedom, the following concentration bounds hold true.
P 2vkt 2t) & exp(-t), P(k - 2 kt) exp(-t).
Fact C.7 (Mini-max formulation singular values), Given a matrix M E Bmxn, assuming n S m, the singular values of M can be defined as follows.
0k (M) = min max [ Mc.SE dim (U) = k ) U
4k E [n].
Fact C.8 (adaptation of Carbery & Wright (2001); see Anderson al. (2014)). Let (Ii, ,,,,..,,aa)) be multilinear polynomial of degree d. If Var (Q) = 1, when x, ~ N 10, E [n]. Then, Vt and O, there exits C S.t.
"( (a), Fn) - 11 (c) & vdd
Fact C.9 (Rudelson & Vershynin (2009)). Given matrix E RR the following holds true for all i [m].
min dist (a,, A-:) S Omiu (A)
m KE[m]
where A-; = span (ay : i)
Fact C.10 (Gershgorin circle theorem, see e.g. Varga (2010)). Every eigenvalue of a matrix A E
Caxn, with entries Gij, lies within at least one of the discs { ((ass r=))" imp where r; Ejjtt Ois) and D(ag, rs) C C denotes a dise centered at azs and with radius
Fact C.11 (Weyl's inequalities (Weyl, 1912)), Let A and B be two hermitian matrices. Then, the following hold true Vi.j E [n].
A (A + B & A (A) A (B)
A (A B) (A) + + (B)
19

---

Published as a conference paper at ICLR 2020
Definition C.1 (Khatri Rao product and Hadamard product, Khatri & Rao (1968)). Given matrix A Rmxx and a matrix B E RPx9, the Kronecker (or tensor) product @ B defined as the mp ng matrix given by
01 B
012
O1n B
021 B
Q22
B
02n
B
A 2
=
0m1
Om
B
Omn
B
Given a matrix E Rmxx and a matrix B E Rex" the Khatri Rao product A * B is defined as the mp matrix given by
A a1 b a2 b2 a bn
Given a matrix A E R and a matrix B E R the Hadamard product A O B E R is defined as
(A B) azybey E [m], E [n].
Notation:
Given matrix X Rmxxn we denote order-r Khatri-Rao product of as X R x
which represents X X x.. X. We denote order-r Hadamard product of X as Xor Raxx, which
times
represents X X...O ② X and can be shown be equal (X*r)² X
times
C.1
GENERAL APPROACH FOR BOUNDING EIGENVALUE OF G-MATRIX
The Gram matrix G can be written as
G = 1 M"
where M Ridxnn is defined by
M Ma(k-1)41: dk,t agd (wxxx)xx
x; for [m].
Denoting by A (G) and 0 (M) as kth eigenvalue and kth singular value of G and M respectively,
we can write A (G) as 0x (M) The minimum singular value of M can be defined (through the minmax theorem) as
Omin (M) min ||M[||
<E
Hence, the general approach to show a lower bound of min (M) is to show that the following quantity
C.a =
(4)
lower-bounded for all ( E 2n-1
To show upper bound, pick a' 5n-1 and
Tmin (M) min |MC]| CE
m
(5)
D STANDARD PARAMETRIZATION AND INITIALIZATIONS 2-layer (i.e. 1-hidden layer) neural network is given by
b, W) = Σ and (w bxx)
20

---

Published as a conference paper at ICLR 2020
where I is the output layer weight vector, W R is the hidden layer weight matrix and IRthh 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(O) and a are chosen, depending on whether the number 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) _ (0. 2
f_a) and Ok (0) N (0, )
Ak E [m]]
Init(fanout): Wi
(0) .V (0, La) and d (0) N (0,
vk [m].
Note that Allen-Zhu ct al. (2019) use Init (fanout) initialization. The elements of are initialized from N (0, (8)), where small constant. We set 3 0.1 in Init (fanin) initialization and
Vm in Init (fanout) initialization.
D.1
NOTE ON G-MATRIX FOR STANDARD INITIALIZATIONS
We follow the argument in Section to get the G-matrix (G) as
(1) 9
w + b&) ø' (wf.x; x, by: X5),
where is the gradient flow rate needed to control the gradient during descent algorithm to stop gradient explosion, i.c. we need control the maximum eigenvalue of the Gram matrix.
For Init (fanin) and Init (fanout), we set 17 as and 1 respectively to get the same Gradient Gram matrix as Equation 2.
E LOWER BOUND ON THE TRACE G-MATRIX
In this section, we lower bound the trace of the gradient matrix for a general activation function as point of comparison for our results regarding the lowest eigenvalue.
Theorem E.1. Let o be activation fincttin, with Lipschitz constant and let ( be the G- matrix at initialization. Let (0-N(( (o' (wT xx)
2c for a positive constant and and for all i.
Then, (r)) 2 en with probability greater than - ((m/aa² log" m)
m11 -3.5
Remark. The constant depends 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
m
n
w (0)T 2:1) 2z))
tr(G
(()
(0)
m
j=1i=1
Using Fact C.5, (0) can be shown to be in the range (-3vlogy log m, 3 3 m) with probability
{
a
j=1
at-least 1 - m 3.5, Assuming this is true, we claim the following two statements. For any j we have (0)
(expectation is over (0)) and 0
k=1
w (a5)) :1a50) /3g
a
(0)
00
w ( zi)
(0)T
E (0)
(0))
E w
(w
xx17xx))
xx)
: 1 533
1 log m
log
2c
m
21

---

Published as a conference paper at ICLR 2020
(1-
where we use the independence of a and (0) and the variance of a² is at-least
log me
(0) taking the bound on az into account, in the intermediate steps. Also, we get from the Hoeffding bounds,
100' ((w,))) X;
T
)
2
1 c -0(mm (o(mmn//aa log""gmm
2 c
j=1
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 Ω (1).
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 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 but the radius of convergence is T/ and thus cannot be used directly if the approximation required for bigger intervals.
We consider two different notions of approximations by polynomials, depending the initialization and the regime of the parameters. is instructive to first consider polynomial activations before going to tanh. Next section is devoted polynomial activations.
F.1 POLYNOMIAL ACTIVATION FUNCTIONS
Let's begin with the linear activation function. this case, the G-matrix turns out to be the Gram matrix of the data. Since each datapoint low dimensional, we get that it is singular: Lemma F.I. (Linear activation ) If ((x)) = x and < n, then the G-matrix is singular, that
Amin (G 0.
In fact, at least (n d) eigenvalues of the G-matrix are 0.
Proof. Since & (x) = x, we have ø' (x) = and the G-matrix given by
m
G
X
m
where X = [2,, X Xn] is the matrix containing the x; as its columns. Since the x;'s are d-dimensional vectors, rank(X) < d and so. X can have most 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 o' (x) Ei cool and d' dim (Span (w) v..). Then, the G-matrix is singular, that is
Amin (G = 0,
assuming that the following condition holds,
d' +p
< n 1
(6)
p
22

---

Published as a conference paper at ICLR 2020
Proof. Referring Equation 5, it suffices find one Ç² gn-1 such that
(axd((w[x)) 0.
For any & E [m]] and E R" consider
g
1-1
Σ G xx)x,
Σ Sas Σ ct-1
W
X.
which can be written as
C--1 BE24.
Σ
Σ
Goxf
Xi
w
-
Here 24 denotes the set of non-negative integers, and the notation x is shorthand for 11 " Note that the term denoted by i d-dimensional vector, since x; E IRd. The actual number of unique equations in i depends on d', since the x; is 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 system of linear equations in variables { Counting the number of constraints for each summand and summing over all the indices gives us that the number of constraints is given by
Σ
1 t=1
P
(
+
which is equal to (d'+)) 1. Note that this can also 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 existence of least one non-zero vector Ç" satisfying the of
constraints. Since, the set of linear equations is independent of the choice of k, the claim holds true for all Thus, using a unit normalized ç" in Equation 5, we get miiu (M) 0.
Corollary F.211 Ifd' dim (span (x....x,.) O (log" 0-75 (n) x'(x) Ei-o and p S
O( then the minimum eigenvalue of the G-matrix satisfies
Amin (G!0) 0.
Proof. If d' 0 n). Condition can be simplified to get
p = (n
Applying Theorem F.2 with the above condition, 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 (xi ... x..)) ..)))) O (log m)). d'xx)
Ei oer and p S
On ) then (1 )) low-order eigenvalues of the G-matrix satisfy
A (G = Vk >
n
d
23

---

sup k. Published as a conference paper at ICLR 2020
Proof. We follow the proof of Theorem F.2. Referring Fact C.7, it suffices to find one (1 d)
dimensional subspace U such that
m
m
Gard (oe xx, O.
holds true JA E U.
For weight row vector Wa {WI, Wm its corresponding output weight ag and an arbitrary Ç E IR",, we can simplify the following quantity
Σ Garo'(wa x,)x, = Σ C ce-1
wki Lio
t=1
to get the same set of constraints on variable Ç. as in Equation 7. Making the number of constraints
less than F d' leadd the existence of the desired subspace U, whose dimension is n (1 }) satisfying the constraints. This can be restated as
(++))-
d' + I d' P 1
which can be further simplified using the fact that d' I 0 (lgg0.7
0.75 n)
to get
d'
=0 (n!/aa)
Pso
d
In the above inequality, the fact that I d'//d' I V2. Since, the set of linear equation is independent of the choice of w, the claim holds true for all w E [W1,...; Wm) } from which the result follows.
Now, if function is well approximated by low degree polynomial then we can use the idea from the above theorem to kill all but the small error term leaving us with small eigenvalue. But, for different regimes of the parameters, we need to consider different polynomial approximations.
F.2 0 APPROXIMATION USING THE CHEBYSHEV POLYNOMIALS
Let f [-k, + be function for some & > O. We would like to approximate ff with polynomials in the 0 norm. That is, we would like a polynomial 9p of degree such that
[(() - 9p(x)) S.
First, we reduce the above problem to that of approximating functions on [-1, The idea is to consider the scaled function fx) fkx). Note that fx [-1,1] - R. Let h be polynomial approximating f& i.e. supz//e(C M(x)) < e. Then, consider the function (x)) = h (æ/k). Then,
[f(z) (x()) = fx (z/k) h/z/ s Thus, consider approximation of functions [-1,1].
We are interested in approximating the derivative of tanh on (-7,7). Denote by the sigmoid function given by
(xx) e- It follows from the definition that tanh (x) = 2a (2x) - 1. The approach is to consider series in the Chebyshev polynomials Ta. That is, we consider
N
a, Ta
0=0
24

---

Published as a conference paper at ICLR 2020
The coefficients an corresponding can be computed using the orthogonality relations for the Chebyshev polynomials.
On { (
dr.
Using this, one can show the following theorem about the polynomial approximations the sigmoid function.
Theorem F.4 (Equation B.7 in Shalev-Shwartz et al. (2011)). For each k 2 0 and e E (0, 11. there is a polynomial 9r of degree p with
log
4m++2A 24
x²r
==
log (1 + . +Tk 1-T
such that
[gp(x) - o S. x
sup
The proof of the claim follows by bounding an using contour integration. From the above discussion, in order to approximate tanh in the interval (-T,T), need approximate 2x (2r.)) 1. From
Theorem F.4, we require polynomial of degree
log ( x2r
p
log (1 + .т 11)
(8)
Recall that actually need approximate the derivative of tanh. But this be achieved easily from the fact that tanh' (z) = (1 + tanh(z)) (1 - tanh(x)) and the following lemma.
Lemma F.5. Let I be interval and lel ft,9: + R for {1,2} 2 be functions such that supzer f((z) - (x)) s e for all i and [z()) S f.ror E and all Then,
sup su))f((=)f((z)) - (x))2((x)) s 3e. se1
Proof. For any we have [f((z) (x) - 91 (z)g2 (x)
s f(f( f((2)92 ( (4) (z) g1())92 (x) {1((()) (x) f(()) (z)]+ (()(()) (x) 91 (z)
{ (2) 22 (0) (x) (z)
Set (1++)e
< 2c +2
$ 3c.
F.3 L APPROXIMATION USING HERMITE POLYNOMIALS
Next we consider approximating f in the 2-norm iec would like to find polynomial hn of degree p such that
| [f(z) - (=)) dp(x)
minimized. denotes the Gaussian measure the real line. Note that this problem can be solved using the technique of orthogonal polynomials since L (R, (4) is a Hilbert space. The study of orthogonal polynomial is rich and well-developed area in mathematics (see Szegö (1975); Lebedev (1972)). Our main focus this section will be the case where f is the derivative of tanh and in later sections extend this analysis other activation functions.
25

---

Published as a conference paper at ICLR 2020
Let Hş denote the k-th normalized (physicists") Hermite polynomial given by (-1)
Hx(x) = V=2*k! 1/2
de dr
(9)
and the corresponding normalized (probabilists') Hermite polynomial is given by
d
(e) [V - 1/2 (-1)* e²2
(10)
dx
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 (z; denotes the density function of Gaussian variable with mean O and standard deviation
The series of polynomials H2 are orthonormal with respect to Gaussian measure
and the
series of polynomials Heg are orthonormal with respect to the standard Gaussian measure j (z; 1)
i.e.
1) 6m,ns
Hm (ln(z) (z) du zi V2
(11)
Hem (z) He,()) du(æ; 1) 6mmn-
(12)
The two versions of the Hermite polynomials are related by
Hm Heem (V2x)
(13)
For any function f L (p), define the Hermite expansion of the function
8
H.
From the orthogonality of the Hermite polynomials, we can compute the coefficients
= S (xx He (x) du (z; 1).
Since 2 is Hilbert space, we can use the Pythagoras theorem to bound the error of the projection onto the space of degree polynomials as
1
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. this paper, we will use probabilists' version in our proofs. Since the literature we draw comes from both conventions, we will need to talk about physicists' version also.
In the following we will be using complex numbers. For E C, the imaginary part of z is denoted by 3(2).
The following theorem provides conditions under which the Hermite coefficients decay rapidly. It says that if function extends analytically to strip around the real axis and the function decays sufficiently rapidly the real part goes infinity, the Hermite series converges uniformly over compact sets in the strip and consequently has rapidly decaying Hermite coefficients. The extension the complex plane provide the function with strong regularity conditions.
Theorem F.6. (Theorem I in Hille (1940)) Let f(z) be an analytic function. A necessary and sufficient condition in order that the Sourier-Hermin series
4, Ck =
(tt) dt
(14)
0=
26

---

Published as a conference paper at ICLR 2020
shall exist and converge to the sum f(2) in the strip S, = = ( <T)
(
<t.. is that f(2) is
holomorphic in S, and that to every B. S T, there exits a finite positive ((3) such that
[f + in) s B(8)= B( (
where I E (-00, y E (-3,3). Moreover, whenever the condition is satisfied, we have
|cxl S ((()e=(r-o)
(15)
for all positive c. Here, M denotes a function that depends only on c.
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 simple pole at every point such that e²a + = The set of solutions to this are given by 2> = (2n + 1) я. Thus, tanh is holomorphic in any region not containing these singularities. In particular, tanh is holomorphic in the strip S 2
E C: 3/(()) < / The same holds for tanh'.
Using the above theorem, we bound the size of the Hermite coefficients the derivative of tanh and thus bound the error of approximation by low degree polynomials.
Theorem F.7. Let Φ1 (z) tanh' (z/v2) -. Consider the Hermite expansion of 01 in terms of [H&)kmo k=
(1)2) Σ
(16)
Then,
leal
5 e -
Proof. As before consider the strip S, = C: C3(3(2] = < <r).
Note that Φi (z) is holomorphic in
S for < /27/2. For every B E [0, //T/2//// 4). consider = iy SBz and /2x' x and
V2 y. Also note that tanh' (=) = 1/ cosh (z). Then
|0 (=)l
1
e (2'+
cosh (x' + iny)
2² +v² 21r9
cosh (x' + iny))
2u² 2irg
cos y cosh x' + sin y sinh xr
1
- x² -
cos2 y' cosh? x' sin? yf sinh"
-= e 2ixy
cos2 y' cosh? x
--22 B²
(cos² 8) cosh? x
S 3² (sec² 3) sech?2'
4e x² 8 (sco² 3) (et +0=x)=
< 4e x² e² (sec² 3) ----21/x
40 (sco² B) e /00-v"la!
27

---

Published as a conference paper at ICLR 2020
The last inequality follows by noting that V B2 y2 SBS / v2. This satisfies the required condition with B (3) 40 e (sec² B). Hence, from Theorem F.6, we have that Equation 16 is convergent in the strip Sr, for s /2z Thus, from Equation 15, using /2n we have
lccl - Ce 2
for constant C' independent of k. Corollary F.7.1. Let Φ2(x) = tanh' (x)). Consider the Hermite expansion of d2
Φ2(x) (e)
(17)
k=
Then,
e 2x4
c 0
Proof.
Using orthonormality of He, with respect to the standard Gaussian measure, we have Pc
1 pp
(2 Hex(x)e & dx
Ōk Φ2(2) Hex(x) du(x;;
V2TT /2 2
02 (V2x) Hek (v2x) =2 dx
-30
Using Ø2
22x Φ1 (x)
defined in Theorem F.7 and Hek (v2x) H2 (I), given by
Equation 13, we have
V oi (1) & dx
Cx
Applying Theorem F.7, we get the required bound.
Corollary F.7.2. Let (2(x) tanh' (x) and let d2 be approximated by Hermite polynomials {Hex) k= of degree up to p in Equation 17, denoted by
100
hp(x) Σ c Hex()..)
Let
Ep(x) (2(2) - h)(x))
Then,
/ Ep(x) dp(x; 1) s0 -TsMP))
00
Proof.
2
Ep(x) = 62(x)) - (p(x) = Σ
He)
k=p+1
Using orthonormality of normalized Hermite polynomials with respect standard Gaussian measure, we have
du(x;)) Σ
Σ
k=p+1
k=p+1
Substituting the bounds for (ōx k=ppt from Corollary E..11 have
Σ
4vT
V2k+1
k=p+1 1
k=p+1
E 1v7 2x+1
dr
32
π
/2p + 12p+1+1)
4
required.
28

---

Published as a conference paper at ICLR 2020
For comparison, consider the Hermite expansion of the derivative of ReLU, the threshold function. It can be shown (see (Lebedev, 1972 page 75)) that
1)
T (2k: + 1)!
(x)
Σ
H2x+1(0) +
=
2VT
2 (2k + +1
km
(2k + 1)!
H2 (2) +
V 4m k=0
2 (2k + 1)
(-1)* 22k v 22k 2k
24 /2k + Vke H2x+1 +
(-1)*
(2k 1)4K H2x+1(x)
2
(-1)*
k0.75 H2)+1(x)
(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 Ex=o Cn Heg (æ), then
ReLU (e)U (z) (x)e
22T
1
ReLU ReLU'(V (V2y) Hes (V2y)e - dy
VT
1
(eL V2
(19)
VT
(-1)*
= C₁ A0.75
(20)
where we use Equation 13 and the fact that ReLU'(y) = ReLU' in Equation 19.
It can now be seen that the Hermite coefficients do not decay rapidly for this function.
F.3.1 DZPS SETTING
For this choice of initialization, defined in section 2, we need to consider two different regimes depending on the number of neurons m. When is small, we use Chebyshev approximation in the - norm, while we use the L approximation by Hermite polynomials when m is large. First consider the Chebyshev approximation.
Theorem F.8 Assuming Φ(x) = tanh(x)) and weights w ~ (,( ah ~ ~(0, Vk [m].
the minimum eigenvalue of the G-matrix is
4T + lylog nmm
Amin ((())
50 m
T/3
Vog mm
ww (0)
(0) mm) and {a k
with probability at least 1 - (mn)a.5 with respect
where p is the
largest integer that satisfies Condition 6.
Proof. In the following, for typographical reasons we will write wa instead of w and o instead (0)
(0)
of 0 Referring to Equation 5, it sufficees to find a vector Ç" 5n-1 s.t. D 4 m. is small.
For each k [m] and [n). w x is Gaussian random variable following M/ 1). Thus, there Gaussian random variables and with probability at least 3/lognmm Hence, restrict ourselves to the
2 (1 (mm])t with re-
spect to {wa] maxig(n].t[(m] wFxx
29

---

Published as a conference paper at ICLR 2020
range (-3ylog nm, 3 //log nm), when we analyze Φ(z). Now, from Equation 8 and Lemma F.5, we have that there exists polynomial (ar) of degree p that can approximate of in the interval (-3vlog nm, 3ylog nm) with the error of approximation in - norm given by
4 6yoog nm
c33
1 +
x/3
Vlg 2912
From Theorem F.2, there exists ς E gn-1 s.t.
2 x;
m
Σ
Saa
W xi
0
2
provided Condition 6 holds true. For any weight vector Wk, it's corresponding output weight a and any Ç gn-1 we have
4 a w/xx)xx
Σ C (
S
a
(ø'(w - - 9(w)x,)))
|x 11
1=1
1
(21)
S Vn
(22)
where we use triangle inequality and the Cauchy-Schwarr inequality in Inequality 21, ||, = 1,
|x:|| and that the maximum error of approximation c Inequality 22. Hence, for < = C", we have
a
C aa (aRoO(W(x)) x.
Σ
Caaro - Σ Clag((W X
+
Σ
C aag xxxx) X;
v n aaae
(23)
Thus.
2
1
m
172
Σ
m
Σ
Faxd (wFx,) x;
S
V nc S Vōmyne
where in the final step, we use chi-square concentration bounds (Fact C.6) to show that VE km is at-most v5m with probability at-least 1 e-m. Using Equation 5, amin (M) < V5m That implies, Amiin (G) Amia (M)² < 5nc?. Since, decreases with increasing p. substitute the value at maximum value of possible in order to get the desired result.
Note that since the upper bound the eigenvalue depends on m, the bound becomes increasingly worse as we increase m. This is because as we increase m, the interval (-3vlog 7um 3 rum) 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 0 norm to the L norm under the Gaussian measure. This naturally leads to approximation by Hermite polynomials as discussed in subsection F33
Theorem F.9. Assuming ((xx) tanh(()) and weights w (0)
~NO0
Ia) aa ~N(0,1) 1) Vk [m]. and (0))
-3.5 over the choice of (0) m k=1
(0) m
with probability least 1 n.l lnng the minimum eigenvalue of the G-matrix is bounded by c, i.e.
k=
Amin (G S e, where
(o(n ni log n log m
o 0n22 /pe itz wovv)))
Vm and p the largest integer that satisfies Condition 6.
max
30

---

Published as a conference paper at ICLR 2020
Proof. In the following, for typographical reasons we will write wa instead of W Referring to
(0)
Equation 5, it suffices find vector 5 S"-1 s.t. E> (fm,]] is small.
Theorem G.2 gives the enror of approximating ø' by polynomial h, consisting of Hermite polyno- mials of degree S p. in the L norm. Let Ep denote the error function of approximation, given by Ex(x) o (x) hzz).
From Theorem F.2, there exists 5* E Sn-1 s.t. for all w and ā we have
Σ (ul(wwx,)xx =0
provided p satisfies Condition 6.
We can use Fact C.5 to confine the maximum magnitude of ag to 3 m. Thus, assuming that this condition holds true, we claim the following. Using ch we get
E Bw--N(0112,.
C a0
2
72
n
ahhpp x;) x; +
Σ
uc Ep(w" xi)
X;
(24)
(25)
n
S Bw--MO11)d xi
Σ i=1
Pop ( x:)
(26)
S Bw-N(o.L
Ep (wTxx))
(27)
Ep (wTxx) (wTx:)) 2
n Eww,N((,1.)
(28)
We approximate ø' by h and use the definition of ch in Equation 24, apply Cauchy-Schware in Equation 25, || = Vi E [m).||<** 1, the linearity of expectation in Equation 26 and maximum variance of a, given the constraint on it's magnitude, upperbounded by I in Equation 27. w x1 follows a Gaussian distribution ((00 1). Hence, denoting с₁ as the error of approximation from Corollary F.7.2, get
E Bw--1011),
Σ
ao' (w" xz) Xi
< neen
where
en < O T5े VP).
Applying Hoeffding's inequality for m weight vectors Wk ~ (0. Ia) and as ~ ~N(00, 1), we get
Pr [wi)m pm (ox J
c a (olo(w(xx)))
< (n'en +1) 1
log
m
3.5
In the above inequality, we use the restriction of the maximum magnitude of az to 3y/og m and hence, Vk: Ei aaa (wf x; E (0, ll). Using / = max (nee,, n n log m
/m
31

---

Published as a conference paper at ICLR 2020
being constant and substituting the value of get the final upper bound. Thus,
m max (n(2en) ,
(
nl m log
c の0 (w x;)x;
(29)
vm
Using Equation 5 and the fact Amin (G) m mmin (M)?, we get the final bound.
The upper bound on minimum eigenvalue from Theorem F.8 can be rewritten as
Amin (G (G S O ( log (Nm)ee (am))--long plog (1-5 (og(nm))
for small constant C and p denotes the largest integer that satisfies Condition 6. Let assume that d' S O llog 0.75 n. where d' = dim (Span ..,)).)..... Then, we use the value of from Corollary F.2.1 for the next set of arguments. Substituting the value p. we get
(aam)e-ntaa -nt/dd log (I+ BollVloggin /log(mm))
Amia (G S SO
Inlog (nm)e
Assuming e (ntree) have
Amin (G <0 n²c (n'ee -a(x-iia)))) = -0(1)/2dd)
e (nnl22d))
By Theorem F.9, when
1.5 log log (n)e -n(11/20)
10 nēe "bgn
)) -P(("/add)
Amii (G (G)) max
with high probability with respect to {Wx k== and {ax 1==1 Hence, the final bounds of minimum singular value of Gram matrix case of tanh activation has been summarized below.
Theorem F.10. Let dim (span (xI...x,)) s So (og 0.75 n). Assuming Φ(z) = tanh(x) and
weights w (0) satisfies
(N) ak N(O,1) 1) Vk E [m]. the minimum eigenvalue of the G-matrix
Amin (
-2(
with probability at least m with respect to the weight vectors { w (0) m
Ja-n and (0)
Jmm
In fact, as in Theorem F.3, show that the smallest (1 1 eigenvalues of the matrix small. This is captured in the following theorem.
Corollary F.0.1. Let d' dim (span (x1... ......))) = O (log (10 n.). Assuming 6(x) = tanh(x) and weights w ~ Na az ~ 1N(0 Ak E [m]. then eigenvalues of the G-matrix satisfy
Au (G)) < -
wk
d'
(w())
[0) m
and (0) m ax
with probability at least 1 - 22. with respect the weight vectors
J Jumi
(0) and ag instead of Proof. In the following, for typographical reasons we will write wa instead of w
(0) We give proof outline. We will approximate o' by p-degree polynomial h as in Theorem F.8
a
32

---

Published as a conference paper at ICLR 2020
and Theorem E.9, where p S O (n/)d) From Theorem F.3, we get that for polynomial h, there exits a nn(1 2)) dimensional subspace U for which the following quantity
Sosh x;
=0
O, VC E U. Now, we can take an orthonormal basis (1U) = (a) ((2) ((,,,,(((-))) of and
for each ((),, we can follow the same proof structure in Theorem F.8, Theorem F.9 and Theorem F.10 to get
S Se -R((1//ar)
agd'
W xx) Xi
with probability at-least 1 1- n with respect to {wo]k=1 and {ax) Now, for bounding singular
value (MMM), ) for k 2 [ we use the following argument. We choose subset S(n-k) of size k from ((U), This subset is n k dimensional subspace U' of R². Each E U' can be written in the form
== Σ azçh))
jE[n]: ÇUEEE
with Ejelo]:co cU o3 =1. Then, for each LEL U',
m
n
m
n
m Σ
Gard' (wxxx)
Σ
Σ
a (w) xxx xi
X;
m
jEfn|: goEe
1
Σ
Σ c un (wx'xi)
aj
jE[N]: ÇUEU
Σ 5 axd (w?:x) xx: 17)
Σ
ag
jElu]: cuEeU
jE(M]: cwee
= -0(n1/2dd)
m
(30)
d'
Thus, it follows from the definition of 0k (M) from Fact C.7 that
(M)- S Vmn" =0(2/1ed)
Using A (G
m ax (M)2 get the final upper bound.
F.3.2 STANDARD SETTING
Now, consider upper bounding the eigenvalue of the G-matrix for the standard initialization. defined in Appendix D.
Theorem F11 (Init(fanout) setting). Assuming (xx) tanh(z) and weights w
N (0, in La) (0) ~ (i(,, and (()) N (0, m Vk E [m]] the minimum eigenvalue of the G-matrix
aq
4 + 6
log nm
O
los 2111 mrs
33

---

log wm log Published as a conference paper at ICLR 2020
with probability at least (mnn)as with respect to p is the largest integer that satisfies Condition
Wx
(0)
m
[0) m k=1 1 k=1
and (110)
Sa=i
where
Proof. For each [m]] and i E [n], w is Gaussian random variable following A (0. Thus, there are mm Gaussian random variables and it follows from Fact C.5 that with probability
2 at least (1 (mn)a.s with respect to {w*]
w S 3v log nm
Now, we
follow the same proof as E88 but restricted to the range (33 result.
log mm 3
log nam
to get the desired
Corollary F.11.1 (Init(fanout) setting). If = dim (Span (xI...xx)) I O 1ogo.76, n)). Assum-
ing ((x) = tanh(x) and weights w ~ N (0, La) ax ~ (V(0,1 and (0) ~ N (0, () vk E
(0)
[m]] the minimum eigenvalue of the G-matrix satisfies
Amin (G
S (B(niaad)
{
(0) m
{ato s=
(0)
with probability at least 1 - n3 with respect to the weight vectors
and
S JA=1
(0) b/
m
k=1
Proof. It follows from the same proof as Theorem F3.
Theorem F.12 (Init(fanin) setting). Assuming ((x) tanh(v: and weights w (0) N (o, La). (0)
~ (0, (h) and bg ~ ~ 0.01) wk E [m]] the minimum eigenvalue of the G-matrix is a
4T + 6
log mm
Amin (
50 n?
Ting in
(0) m
Jkzi' ax Sa and (110] }mm
[0]] (0) m
with probability at least
(mn)) 3.3 with respect
W
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
d
Corollary F.12.1 (Init(fanin) setting). df = dim (Span
< log 0.75 n). Assuming 6(z) = tanh(z) and weights w()) ~ N (o, LL). a N (0, 2) and ((0) N (0.0.01) Vk
[m]. the minimum eigenvalue of the G-matrix satisfies
Amin (G S Se-ninan
{
{wit [0) m
J {al 10) m
with probability at least 3 with respect to the weight vectors
Jmm1
and
(0)
S
34

---

Published as a conference paper at ICLR 2020
G UPPER BOUND ON LOWEST EIGENVALUE FOR SWISH
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
I
I
swish xx)
tanh
2
Hence
+ tanh }
I
4
swish' (x)
+
tanh'
2
2
Theorem G.I. swish' (1) is approximated by a degree p polynomial 9p(() within error in the interval [-k, k] in the - norm:
sup [E(-
swish' (t) (p(()] sc
where
log
4 2212
p
log (1 + -
Similarly, for the L approximation for swish, we proceed using the same technique for tanh.
Theorem G.2. Let Φ2(x)) swish' (x) and let d2 be approximated by Hermite polynomials (He of degree to p in Equation 17, denoted by
hp(x)
C Hex(xx)
k=1
Let
Ep(x) = 02(xx) - hp(2))
Then,
Ex dp(x; S O (VDE TeIve)
Using the above theorems and the techniques from the previous sections, we can upper bound the cigenvalues of the G-matrix with the swish activation flunction. We summarize this in the following theorems.
Theorem G.3. Consider the setting of Du al. (2019a). If d' dim (Span .x.... xn.) N/ Ia)vk [m], then eigenvalues
O (lgg0.7 n). Assuming d(x) = swish(x) and weights w of the G-matrix satisfy
(1))) se -((21/20))
n
A
Wk
d'
with probability at least
m23 with respect to the weight vectors
w (0)
and
(0) m a
k=1
H A DISCUSSION ON UPPER BOUND OF LOWEST EIGENVALUE FOR GENERAL ACTIVATION FUNCTIONS
In this section, we generalize the results of the previous sections upper bounding the eigenvalues of the G-matrix to more general class of activation functions. To this end we note that the only property of the tanh and swish used was that these functions aprrxxippo degree. The approximation theorems used in the previous sections can be stated under fairly general conditions the activation functions.
polynomials of low
35

---

Published as a conference paper at ICLR 2020
For the Chebyshev approximation, it can be shown that function with & derivatives with bounded norms can be approximated by Chebyshev polynomials of degree with error that decays like N 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 [-1,1 - R. be function with + 1 continuous derivatives. Let f be the Chebyshev appreximation of f to degree N. Then, have
sup -Sw =E|-1.1)
Furthermore, if f can be extended analytically to the ellipse
(w + 1-
E, 2 2E
| Sr
2
then
sup - (Sx]) 50(m))) =E|-1,11
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, can extend the upper bound on the eigenvalues on activation functions satisfying sufficient regularity conditions.
36

---

Published as a conference paper at ICLR 2020
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., X; is obtained by adding small multiple σ o= O (2/ of IID standard Gaussian noise within the subspace V of arbitrary initial samples XT, with V == Spanfx/,..... x and renormalizing I. Denoting the initial set of samples as X' {x',....< x and the noise matrix N, that has each entry coming iid from N (0, we have the data matrix X defined by {x1....X, Xn where
n. + X n.
Remark. Assuming that the initial samples x are one normoaaall w.h.p. the norm of the noisy vectors x/ + n, are in the range (1- 6) and thus, renormalization involves division by constant in the range (148' 1-z). Assuming that the initial samples x are 26 separated, w.h.p. the separation between X; can be shown be least 6, thus satisfying Assumption 2.
Assumption 4. Let d' = d' --dimensional space (otherwise we project them d' dimensional space using SVD) and d' 2.
}. For simplicity, we assume d = d' i.e. X1. X. lie in
While our result here builds upon the smoothed analysis of Anderson et al. (2014), the following lemma provides more modular approach though no new essential technical ingredient.
Lemma 111 (ef. Lemma H.1 in Oymak & Soltanolkotabi (2019)). For activation function e and a data matrix X d with unit Euclidean norm columns, the minimum eigenvalue of the Gram matrix o satisfies the following inequality
Amin (GP) 2 2 (60) Amin ((x"x) )
Vr 20
where (XTX) @(r+1), is given by (X+r) X E Ruxd" denotes the Khatri-Rat Rao product of matrix X and (,)) denotes the r-th coefficient in the probabilists' Hermite expansion of s'
Proof. Each element of G can be expressed in the following manner.
(w'xx,)0 0 (w"'x,) x Σ E (0') (xfxx) a+1
J = Eww
where we use a) unit variance of independence of à and w and b) the fact that w x; and w x; are x? x, correlated for normally distributed vector w and hence, use Lemma N.4. Thus,
x @(a+1)
Using Weyl's inequality (Fact C.11) for the sum PSD matrices { (x"x) G(a)) xc
a=1" we get
G 25 (0') (xTx) ((r+1)
Vr 20
from which, the assertion follows.
Lemma L.2. Let d' dimspan
x,).
Denote by p be an integer that satisfies
d'
n.
(31)
p
Then for any (0. with probability least K with respect to the noise matrix N,
σk
on (X*) 2 Ω
mp
37

---

Published as a conference paper at ICLR 2020
Proof. X has d' rows and columns. However, the number of distinct rows is given by ("*p=1) This follows by counting the number of distinct terms in the polynomial (Ei=) mse )" where (ux)
p
a set d' variables. Since, we assume that (+). 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 Let X'P denotes n X sized square block of X*P, that contains any random subset of size n from the set of distinct rows of X as rows, such that each row represents elements of Khatri-Ras product of the
form J 3 b 0 s bj I 1 Vj E [d"), for vector x E IRd", We can see that X, (X S o (X*)). Hence, we will focus on the minimum eigenvalue A. (P.).
Fix l E [n] and let u be the vector orthogonal to the subspace spanned by the columns of X except the 1tth column. Vector u is well-defined with probability Then the distance between x and the span of the rest of the columns, denoted dist(x;;)
*D X xx*)., 2),, is given by
(farta + enaj j=1
Σ Usga eE(n]
(32)
{ crmes of )2=1)
(33)
where 9a denotes a degree-p polynomial and is given by
9s (
tenss y=1 + cnay
dd
= II
(alks + ones) 0 o5
[d'),
b
SEld
jEld
e denotes a constant in the range (148 1-)):-8): which is the normalization factor used Assumption 3.
Hence, Equation 32 is a degree polynomial in variables Naj. 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 given by
Var (p
( ((mms))5==
26
2p
29
2
II TE (cores cness) jE(d')
1
2
where we use the fact that ||u]|| = and naj are Gaussian variables variance 4n Using a minor adjustment of Fact C.8, which takes into consideration the fact that our gaussian variables are of variance
5 and the variance of the polynomial is not 1, we have in
{p((mrt) (mas) (ma))) )
ciD
Pr P
SE
Cp
C > is constant.
Using a union bound over the choice of k. we get
1/p
Pr
f dist X S,
Vk E [m]] s Opn
P get
Using
2C
(
min (x kE(n)
X 2 v/vR.
with probability at least We use Fact C.9 in the above inequality.
Theorem 1.3. Let o(x) be constant degree p polynomial, with leading coefficient 1, and d' dim span(xi,..... x,) 2 (Pn- Then for any 10,1) we have
Amin (()) 2
ka
Ω
np
38

---

Published as a conference paper at ICLR 2020
with probability at least w.r.. the noise matrix N and (w k= provided
(0)
m Q P Apt log (n/K) 1og22++
Proof. For a degree-p polynomial with leading coefficient 1, the (p 1)-th coefficient Hermite expansion of ø' is given by Also, note that Equation 31 is satisfied by p. given that d' 2 Ω2 n for a constant Thus, using Lemma I.1, Lemma I.2 to find minimum eigenvalue of G and then applying Hoeffding's s inequality (Fact C.3) to bound the deviation of minimum eigenvalue of (0) from G get the desired bound.
Theorem 14. Let the activation function & be tanh and d' dim span Then for any (0, 1) we have
Xn} 2 82 (logn).
(tanh')
3p
Amin (G (G1O)220) 20
Rd
71
np
with probability at least w.rl. the noise matrix N and {w (0) mm ===1 provided
p n 14 log (n/x) log* m
m 2 Ω
where p denotes the smallest odd integer satisfying
and &o (tanh') denotes the p-th coefficient in the probabilists' Hermite expansion of tanh'.
Proof. p chosen such that Equation satisfied. We use Lemma I.1, Lemma 1.2 find minimum eigenvalue of a and then applying Hoeffding's 's inequality (Fact C.3) to bound the deviation of minimum eigenvalue of ( from Go we get the desired bound.
Now, we specify the behavior of the probabilists' hermite expansion coefficients cp-1 (ø') for é tanh. Let 8, the exponent of real axis convergence of tanh', be the least upper bound on y for which
tanh' (x) O (e-vlelt.
R.
for some constant // > 0 as |o||
+
xo. We have B = as tanh' (ar) e-1l 1pl for large/ar).
Hence, using Eq. 5.15 in Boyd (1984) for the coefficients & in the probabilists' Hermite expansion of tanh' we have
(2h: + 1)1/1 + ((( (c-Fraaa
2
C
as k 0c.
(34)
We remark that Boyd (1984) uses physicists' Hermite expansion. Following similar technique as in Corollary F.7.1 and Theorem F.7, we get the exact similar form of probabilists' Hermite expansion coefficients čμ (tanh').
Thus for p O(log n), we have ū = δ (e (e-o" Vlog
Corollary 1.4.1. Let ((x) be the activation functiono tanh and d' = span(xi....,,,, x,} = θ (log n). Then,
Oloo n)
Amin ((())
0
w.r.t the noise matrix N and (2 log" (2) (llx
with probability at least - 1/poly(n) - (w(() )0) )k=1-
39

---

Published as a conference paper at ICLR 2020
Corollary L442. Let the activation be tanh and d' dim span span ..,, x,) 2 52
O (n constant
log logn Then for any n. E (0, we have
logn
c' Vlogn
2p
Amin (G
Ki
n
nap
with probability at least 1 W.E.. the noise matrix N and {w (0)
Ik=1 provided
p A 4 log (N/N) log" m
Ω
where p is the smallest "odd" integer satisfying
d'
n,
and d' is constant. p can be shown to lie in the range.
2
2 Log
7
40

---

and respectively, where Published as a conference paper at ICLR 2020
J
DEPTH HELPS FOR tanh
Let the neural network under consideration be
w(1) L
Go
Σ axd k=1
((w!")² x((-1)
x:a
1=1
1i and where x( Rm
x(1) IRd for I O, is defined recursively by its components as
follows.
4/ Vm
!1] co
(( (ww
x
Ak [m], 14
kk
(0)
Wk [d].
co = E (on-No.))0())))
with ø following the following three properties.
(0))
o is a-Lipschitz. (= (0z) = 0
The weight matrices and the output weight vector are given by { (wO) 14 i=1 E Rm w E Rmxm for 2 2 and w(!) E Ixdd for 1 = 1.
Now, we define the Gram matrix ()) as follows (cf. Eq. 13 in Du al. (2019b)).
(0)
T xj (w) T x ((-1)) o' ((w!)) Σ ago' ((w)))
(2-1)
Fij
m kE[m]
with its counterpart
2 when xc, given by
( (w"x x((-111) 0 w ( x(((-1))
NW-NNo0 9zj
Lemma J.1. For small constant e > 0, if 20 max 2 Ing m log nL, (nL)
then with
probability at least - --- -S(me² 122 log? m)
nb m3.55
we have
x 00 E (1-c,1+e)
Vi e [n]. E (O....,,-11 1}
(35)
Proof. We will use induction to show that for any given with appropraite probability we have
| (1 (Acgaa)) 1-1 e, 442
AI [L].
We will apply union bound over the choice of to derive the result for all E [n]. The result holds true for = 0 by Assumption 1. Let's assume that the result holds true for = f. For a randomly picked vector w N (0, I), w' follows normal distribution with mean and standard deviation (1 c1, ez), where e, =(43302)
(t) Denote unit normalized form of x as
x; Since, there are m random Gaussian vectors in the matrix ( leading to formation of m Gaussians along the dimension of (++1) (t) we can apply Fact C.5 to confine each dimension of
x("),
((++)) (8) the range (-3v log
x
(4) 3 / m x
with probability at least
Assuming that this holds true, we can claim the following: First,
Pr W(++)
20 w/ (1-1)T x00)²
30 (wT (wTx(0)² )0)²
2 a EEEe
S
22
laxt
k=1
(36)
41

---

Published as a conference paper at ICLR 2020
(0) (0) where we Hoeffding's inequality (Fact C.3) and bound on We x; and the a-Lipschitzness of the activation put bound on (( (++1)T x; )
to be used in Hoeffding's s inequality.
Second, using Taylor expansion of Φ the deviation of 2w x( from Eg (=) can be bounded in the following manner.
Ew-)((o.)) C p(w" xxrxx x2 = Ew-N((o.) + x + = ) 2Z)() + (37)
where e' E (-2e (22 2ega This follows from the following set of equations.
6(w' x )1 = ( x1²
② (11 (1--)
s)w x + sw T xx x Ø (11 (1-8) (1--)w"' s)wTxx0 xx0) xww x(11) (wTx(0) xx((()) ds
+2 =
S ( 2e,(1 + c:a2 w² x²xx!0) x
(38)
In the inequality above we used the facts that e is a-Lipschitz and since (00) = 0 by assumption, <(=) S a/z//
This gives
Ew ol s Ew- ( xx)x())= + 2e, + +er)a2 Eu xx!x 2 2 + 2cx(1 + cz.
Ew G0 (w"x(")
Third, we use the definition of Co and the a-LLipcchizness of Φ, to bound the error due to restricting x to get
the maximum magnitude of w x to 3 m
wwwo(/))/''' S3ylogm 20 w (w'x(") x(())² E.w.No.nc (w 1²²
log
+0
m
logm
=1+0
(39)
m
This can be shown by the following equation.
E www.Wo..f/TT."") SaVlog 2 w x())
(TT F (w" x()x)
(xx)2 20==0 12
5 2TT 3ylogm
2222
22
1///2 12
2n 33/lgmm
log m
< a²
(40)
Combining Equation 36, Equation 37 and Equation 39, we get that with probability at least
-2
m
2e
log
77/2
1/2
Loww
(OT x;)3
E (1- (1-4a2czer:14 4a²c)e))
m
We the union bound for all the induction steps and examples get the final desired bounds. n
42

---

Published as a conference paper at ICLR 2020
Lemma J.2. If for a pair i,j E [n], x; then for all small e >>0 0,
(IT)T x--1)
xj
p.s. |o| S 1 ô and if Equation 35 holds,
l+e 8
1 1-c
1+c C
1- lpl
33 (e) +(1 104+2 2c) max
+
P
n1
2
n2
2
2
7/2 - e -0(m6" jo'n"oo"" w.r.t. initialization, where denotes the with probability at least 1 - m-1/2 (20 ratio E 1
Proof. From Equation 35, for a small constant c, |||//__ E (1-c1+ E [n] with high 111) for x;
probability. For a vector x set X == x/||>|| thus we will use x
(111)/ /
We
use Fact C.5 to restrict the maximum magnitude of the 2m Gaussians w x; (1-1) and w x and 3ylog m
(1-1) for
k E [m]] to 3 m
x |-1) respectively. Assuming that this condition
holds, we have
U)T (1)
1
(1Y Wk x
1 (1) 1 W/ xj (
Co m
kE/m]
1
Σ
W x x)--1) Φ
(IYT
w/ x x1111) + +
(1)2
(41)
m kEmm)
(1T x((1111) 1) @ (w xxTTxx( x(( + é cc"
Ew
W
(42)
c (0) pº +e'+ c'' e" + te"
(43)
We get Equation 41 along the lines of Equation 38: we use 1-st order Taylor expansion of (TTx (11) around w and o
wxxx--1) around wix/"-! a-Lipschitzness of o and /r||x/ x [x[-1>| and x 1) from Lemma J.1 to get
upper and lower bounds of
o ((W x (1-1) )a W 11)
o(w
xf )6l ( (1-
5)
w x 1) + swfx("-1) 11 [/ x (11 w/ ds
x x
1) 10'
+ tw 1) (w77 (1-1 w 1 dt
0' (w=
() 1) SW (1111
wF (1-1) - x 1)
1
0' (1 (1-t) t)X 111) + x 1111) ( (1-1) _
- xxXx 11 dsdt
x ")
(w 1) a² (2e(1 + E) + 2 e)²) ///x/ 1)
w (1 1)
(44)
In the inequality above we used the facts that & is a-Lipschitz and since (0) = 0 by assumption, <(z) S a|z|. This gives
m
2 ZO(WF ( ((W/
s m
1
20
)o )O( (1))
m
+a² (c(1++))+ +((+))++((++))) 1 m
Σ 2 (
w x(
m
m Σ
1
)(( + da2d 20(1 + + +
43

---

Published as a conference paper at ICLR 2020
In the last step, DC W
we Hoeffding's inequality from Bw-N(o.)) og w
bound the deviation of w 1)
W /
(1-1)
and using stan- is at-most 4. Thus,
dard gaussian moments, we can show that that Ew-N(O.)) combining everything, we get
w x;
11
w T x
E (-20ea² 22 20ca2 26)
with probability at least - (m// log m) In Equation 42, we use Hoeffding's inequality (Fact C.3), a-Lipschitzness of á and bound for the magnitude of the 2m gaussians w X; (!-1) and w x (1-1) get e" E (-T,T) where
to
pl (1 lp)) I-c 4 /x
iflel _. otherwise.
(S((m5) /a log" m))
with probability at least e
Note that, the minimum value of T is 2 The reason of using this form of will be discussed below. We use Lemma N.4 in
I-c
2 n
Equation 43, with Pro =
|
(1 1> X D| This follows P1 = | "1² and Pon =||=
from the fact that for random normal vector NO, I), w follows a normal distribution with mean 0 and variance ||x||² and the covariance of w x and w y x" y for two vectors x and y. We
have an additional error term c" (-vV log m 778
log 120
owing the condition that w x; (1-1)
must be most 3 m (proof will follow exactly along the lines of Equation 40).
Let us now focus on the quantity R (p) for the activation function coo(-), defined in Fact N.2. From the definition of Ca. it follows that cg E eg Thus, we have R(p) S R(pl) - R(1) = 1, which comes from the properties of R, given in Fact N.2. Again, we have
[a(p)] S RQpl) =
(b)
22 (0) -00=)
o
())
|pl
+
(1 1pl |pl
2 ())
-=
Thus.
x (1T x00) < [e"|++ed
+|e|+++++e"""
+|e"|| +[R(p) |||==+++(((())))
< 6Ea 2 2 + max
1+c
8
1
8
+
|p
-
l0
n²
n?
2
2
(45)
where e denotes the ratio (0)
In the equation above, we can see that the form of r = max Ee'
has been chosen so that R(p) +|e|| S (R(p)) +lel) Thus,
(I)T (1)
< + 2a) 2 (1 2c) max
(1+c 8
8
2
1
|0| + 1 - i0|2
2
n
2
n2
(46)
(9)
where we use the bound on x; from Equation 35.
Lemma J.3. Vi.j E [n], i + j. if x < 1 - 6, then x!
11-1 (1-11)
x)1
< where
8
Ω
5 56
n c)
n² c)
44

---

Published as a conference paper at ICLR 2020
and
2
log 1
- )
L max
log
1 c
2 log (n² L) log"
with probability at least 1 - Ω (1))) provided m 2 Q
where denotes
62
the ratio (o (0)
Proof. Applying Lemma J.2 with e 20 we have for each layer E [L] and i, E |r]] + j.
OT
(
(x x(-1))
x
22'n'a 'cg log (n L) log" m
holds with probability Ω2 (13)) provided m 2 f: IR - - Ris.st for p R.
Here function
82
(p),
if p
4 n
f(p)
1+c
x2
+
1-c
2
11
+
n
otherwise.
where function is defined as
f())
c
p+
1-c
c
+
8
2
2
n²
Thus,
x
(LYT (L)
xj
S ffof.... ffof..off
((0)
L times
25 and n=(1-c) Let's now focus on the function f. It can be seen that for the function f. [=(1-o)
28
are two fixed points, and starting from any positive p(0) strictly less than 1 (-[1-c] and following fixed point algorithm leads to convergence to the point --[1-]] Since, equals the function, / 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 the rate of convergence of the function f IR + R. defined for each R
25
f(p) = 1 + c 1-c 2 p+
2
Lemma J.4 shows that starting at ((0) = 5, the number of fixed point iteration steps to reach for
function / is given by T-o max [og (+) 2og (+)) Hence, from this argument, if x[ X
(0Y (0)
S
1- and - max (2 (log }) (log ))) the quantity x (L)T (1) x becomes less than c.
Lemma J.4. For E R, define the function f R by
j(p) ap + (1 a)p²
where a a constant in (0, 1). Starting at 00) 1 8. the number of fixed point iteration steps to
reach e given by + max (n (log )) (log t
Proof. The function of has fixed points and 1, but it's easy to see that starting at any point below fixed point iteration converges to 0; want to understand the speed of convergence. We will divide the fixed point iterate's 's path into two sub- -aths (a) movement from - 8 to b (b a small
constant) and (b) movement from 1 b to
45

---

Published as a conference paper at ICLR 2020
Movement from - to 1 b. We will divide the path into subpaths (1 - 2', 2
where t is an integer in (0, log ). We show that Vt S O (log : : the number of iterations
to reach from - 2 to 2' can be upper bounded by --a The number of iterations
of function f to go from (1 2,, 1 1 22)) is at most the number of iterations of the linear function ʃ R -> IR defined by
(p) (1 a0)- p.
The number of fixed point iterations of f to go from (1 2' (1-2'6) is given by
log (1 (1--011---11 which can be shown to be less than 2 2 2'6-2'-18 = 2
log 1 258
1-28-18
I-a using Taylor
(1-a)21
expansion of log function. Thus, the total number of iterations involved in the entire path is upper bounded by - log /
Movement from 1 - b to c The number of iterations of f is most that of linear function f in the domain (0, - b) defined by
f(p) = (1)(1))
-a)b)
The number of iterations of f to go from (1 - b) to is given by log which upper bounded by लांं log مبا for small enough constant b.
log r-n(i-a
Thus, summing the number of steps needed in the subpaths leads the desired quantity. Theorem J.5. If
2 c
Ω log 1) .0
log 2n log
)
I, 2
then
Amnn (G))) 2 Ω (ollogn) (d))
with probability at least 1 - Ω (1)))) provided m 2 Ω aa log (n L) log?
where čn (d))
52
denotes the th order coefficient in the probabilists' Hermite expansion of e' and denotes the ratio (o
Proof. Assuming Equation 35 with =2 2 using Lemma I.1 we get
2 Elllogn) n) (d') Amin (((x))))))))
*log x
r'
+logn
Amin (G
x (L)
+ +é'
(47)
where X
(()
denotes *r
matrix, with its th column containing x (L)
which is the unit normalized terms d' and c"
form of x (L)
X
denotes its order 7h Khatri-Rao power. There
because of two reasons (a) norm of (L) is away from (b) magnitude of w is restricted to
3 m. Following the line of proof of Equation 38, magnitude of é' can be bounded to O nnc nncfa?
Also, following the line of proof of Equation 40, magnitude of e" can be bounded to n m
log Now,
we make the following claims.
First, x x, for any i.j [n] with i * j. can be shown be most using Assumption 2.
46

---

Published as a conference paper at ICLR 2020
Second, xx - s.t. |0| S -, applying Lemma J.3 shows that (x())
x
S E, for
small constant é, provided L 2
2 I-c
max (s2 (log 3) .2 (log +) with high probability.
Third, if for any i,j E [n],
then we can see that p",, where x denotes the order-r Khatri- Rao product of vector Combining these claims, we get the following.
x
(x())
x (1)
(x/"))=
(
[x
* logg
x(()
llgg
First, The diagonal elements of the matrix
X
are equal to 1. Second,
log T
log
the non diagonal element at row and column j of the matrix
(
X
(1)
is
given by ((x!4) + log
T
(L) x
= log
whose magnitude is bounded by zlog n, Hence, if
2
max (0
(110s log _ .2
log 2n log
I 2
1 and so the absolute sum of non each non diagonal element's s absolute value becomes less than 2n
diagonal elements is at least log T
z away from the absolute value of the diagonal element, for each row of
the matrix ((x11)
(x((.)
log Using Fact C.10, we get for == log n,
Amin
((L) x x(())rTx(L)er (L)))) 2 2
(48)
Combining the value of é', value of e" and Equation 48 gives us the minimum eigenvalue of G Since,
Amin (G()) Amin (Gxx) 11-
we use Hoeffding's inequality to bound the magnitude of each element of (GD - G(0) to
Amin (Gx²) /2n and hence, get bound on Amin (G(O)
Theorem J.6. If tanh and
))
Ω log 1 5))
(og 2n log
L 2
max
1 1-
then
Amin (1))) 2e -s0 s0(toRt 1oR > 1/poly(n)
provided m 2 Ω 12 log (n L) log ), for an arbitrary
with probability at least
Ω
m
(tanh)) (tanh)
constant 0. The constant denotes the ratio
Proof. The proof follows from Theorem J.5, with the bound 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 more finer version of the theorem.
47

---

Published as a conference paper at ICLR 2020
Theorem J.7 (Thm 5.1 in Du et al. (20196)), Assume that Assumption 1 and Assumption 2 hold true, 1ys1 = ((1) vi E [n] and the mumber of neurons per layer satisfy
n² log
n
m Ω
2011) max
n
X
min (G(O)
(K))
min
Then, we follow Gradient Descent algorithm with step size
Xunin (G))
O
(L2))
with probability at least over the random initialization, the the following holds true VI. 2 1.
17 (G(U)
u p
| u w
Thus, refining the above theorem with our computed bounds for Amin (G1O) O(H),, we get the following. Theorem J.8. Φ = tanh,
Ω log ;))
llog 2n log n
2 1 c
max
and the number of neurons per layer satisfy
Ln
> Ω 20(4) max n. "
n² log
K
then, if we follow Gradient Descent algorithm with step size
n330(L)
with probability at least 1 over the random initialization, the following holds true Vt 2 1.
17
u (0)
(tanh) 2-1 25 (tanh)
The constant denotes the ratio
48

---

Published as a conference paper at ICLR 2020
K LOWER BOUND ON LOWEST EIGENVALUE FOR NON-SMOOTH FUNCTIONS
For E (-1,1) define the activation function ø by
((z) Φ1 (z)Ta<a (2 Txza-
We show that the minimum singular value of the G-matrix is at least inverse polynomially large in and 6, provided Φ1 and d2 satisfy the following properties for some positive integer r. We denote this condition by J..
1 22 E C*+1 in the domains (-oo, ai) and [a, oo), respectively.
The first (r + 1) derivatives of d1 and de upper bounded in magnitude by 1 in (-o0, a] and (a, 00) respectively.
For 0 < i < r, we have (a) 02 (a).
(a)
(a) (a) 1, ie. the r-th derivative has jump discontinuity
In the following consider J1 and Jz. The results be easily generalized to higher r but with lower bound degrading as n 22"
K.1 J1: THE FIRST DERIVATIVE IS DISCONTINUOUS AT POINT
K.1.1 DZPS SETTING
Recall that this setting defined in section 2. ReLU, SELU and LReLU satisfy the conditions for the following theorem. The data set ((x,, y:) 1.) for x; E IRd and yi E is implicitly understood in the theorem statements below.
Theorem K.1. Let the condition & be satisfied for (O, Ia) and a (O, Ak E [m]. Then, the minimum singular value of the G-matrix satisfies
1. Assume that w &
(0)
(0)
Amin (G 2
n3
with probability at least 1 (((mm/n))) with respect to { jkm and {a )mm, given that satisfies
n log 81/4
m 2
8
Proof. In the following, we will write wy instead of w following sum for an arbitrary unit vector and random standard normal vector w:
(0) and 0g instead of a Consider the
(0)
sid (wTx;) Xi.
1=1
To lower bound the lowest eigenvalue of the G-matrix, we will give lower bound on the norm of this vector. order to do this, we use the following claim whose proof is deferred to later in the section.
Claim K.2. For Ç E gn-1 let
f(w) Σ
Ø6 (w xi.
1=1
Then have
(l((w))l2
0.1
8
Pr (o..))
2
2
Ω
vn
nス
49

---

Published as a conference paper at ICLR 2020
From this claim, have
0.1
Pr (O,
Σ S Φ
w
x: x,
z
2
vn
n2
Hence,
Pr a
Σ aci of (wTxx)
X3
0.1
2
Ω
5
vn
n
owing the fact that for a standard normal variate ā, |ä| is least with probability least 0.2 using Fact C.I. Applying the Chernoff bounds, we have
Σ
Garz (wfxx)
x;
10 $8
2
2((
6m
(W Th
m
n2
To get the bound for all Ç E S This gives that
e-net argument with
Vé n²
and e-net size (1)
(wTXx,)
Ω
5
n
holds for all Ç g--1 with probability at least
2
Am
-52 mg
2 1
with respect {w 1m and {ax [o assuming that m Q { log 4))
Thus, using the fact that
Amii (G m min (M)², we get the final bound.
Corollary K.2.1. Let the activation be ReLU, then
Amin (())
2 Ω2
n3
with probability at least 1 - -R( Am satisfies
with respect to (w/
}
and (ax J given that m
(0) (
k=1
n log
2
8 11/4
We now move on to showing the main claim required the Theorem K.1. Claim K.2 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 it denote arg maxtejn Si. We split vector into two independent weight vectors, as follows
w w/ w"
w' La X X T W V 0 X
w" 0g2Xi'
(49)
where 91 and 92 are two independent Gaussian random variables following N (0, 10,1-00 82) and N (0,02) respectively and set
(-1-)2)
50

---

Published as a conference paper at ICLR 2020
Let denote the following event.
3 w X; al
8
and w x, a
vi E [m]
{i") and 18gu|
(
8
10n²
4n²
9n2
5n?
Assuming event & occurs, for = we have
W x1+ a
S 10n²
w X,+ =
0g2x Xi+
2
8
9n2
and for vi # i we have
6
6
w x;
a
>
"T x;
092xx.xx x,
4n²
5n2
Hence, conditioned on &, for + 1" we have Iw" x,20 Iw xxiza always and Iw 20 + Iw' 2a with probability 1/2.
Conditioned on & and using triangle and Schwartz inequalities we get
11 Σ Se (w"xx
E d' xx,xx112
vE(N),ia1*
Σ
l1sosill oo
('(w"xx)) |
- ø' x'(w"x;;)
iE(n].igle*
1/2
1|5xx:112
Σ
(o'(w x,) - x((w'Tx,)) xx))
(E[M),,g
rE(M),sa
1/2
Σ (ő(wWTx) x,) - o'(w"'x,,)
1/2
wT X;
TTx
(50)
iE(m),itt
8
0
5n
5nl
where we our assumption that [0"(x) I for E R {a} in Inequality 50. Conditioning
on E was used in concluding that either b'(w" x,) o' p'(w"'x, x,) Hi(w (WFFxx))) x:) H1 (w" x,) or
o' b'(wT x1) Ø x,) 22(w" x,) 66(wTT x2). In other words, of and &22 "don't mix". Since
Ilim d'(z)= limg-sa d'(z) = and (G-1 2 v
we have
Pr (|50 ob (w'x+-) x; Gi- Ø¹ (WTTxx x++
5
1
3
5n
2
To see this, note that given conditioned on E, with probability 0.5 with respect to G2. w x; is going cross the jump discontinuity and thus, ø' is going to change by at least minus the maximum movement on either side of a, which is bounded. Thus,
Pr w
Σ Goll
(''x;)
x;
x;
N
2 0.5.
We now need to show that & 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
WTTxx X;- - al s 10n
5 and T X4
a
>
4n
8
Vi
#i
2Ω
n1
8
g2
51

---

Published as a conference paper at ICLR 2020
From Claim K.3, we have
- 10n² and w x; - a 8
8
Pr w'
n x af
vi
8"
2
4
vI
n
Also, using the fact that 0g2 N (0, (2) and Fact C.I, we have
9n2 5n )
10gzl E
5x
97
2 0.08.
3
12
Independence w' and w" implies
8
Pr
2 Ω
n
Thus,
(ls(w))l2
0.1 vnl
[l((w)]2
0.1 vn
Pr w~N((0.L))
Pr w=N()
E
Pr w
[8]
8
Ω
n
Proof of K.3. By the definition of w', w x; is equal to vI - 02 g1. which is distributed according to N (0, 8²). Hence, applying concentration bounds from Fact C.I, we get that
Pr x a 10n²
(51)
40n² /1 02
We can divide w' Vi E [n] into two parts:
Component orthogonal to x, given by wT (Is X,- xx: X;
Component parallel x,- given by w/ (x,-X?) xs.
This gives
W X; w" (I--x Xi + " (xixx;;) Xi.
Conditioning on w x,-
'x,- such that Equation 51 is satisfied, we get that w xx is distributed according
w x, N w/ (xx.x(f)) x,, (1-82)
-I--xx-x3) xx-
(IL
x;
By our assumption, (I4 - -x-xx(t x: 1|22 Σ 6. Also,
0 < "T (xxxx7) x; = w" x (xFxxi)
8
+
(52)
10n²
Hence, again applying concentration bounds from Fact C. we get for fixed i + i
8
Pr [ - >
2
1
4n²
5n² 028
Taking union bound, we get that Vi E [n] and +
iz
w x; al
8
1
4
Pr w'
4n²
5n
1
0
required.
52

---

Published as a conference paper at ICLR 2020
K.1.2 J1 FOR STANDARD SETTING
The above theorems can be easily adapted 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 1. Assume, w (0) ~ N (0, ALo) 6b2) N (0, 0.01) and dg N (0, 1) Vk E [m]. Then, the minimum singular value of the G-matrix satisfies
Amin (G
n33
with probability at least 1 E -(6mm/n)) with respect to {wi (0) am that satisfies
{be a and {az ( J given Jkk
n log
m 2
8
81/4
Corollary K.3.2 (Adapting Theorem K.1 for Init (fanout) setting). Let the condition on & be satisfied for 1. Assume, W. -N (0, LTa), o ~N (0.1) and b()) ~N N (0, #h) wk E [m]. Then, the minimum singular value of the G-matrix satisfies
Amin (G:0)
2
112
with probability at least e ((6m/n)) with respect to {w that satisfies
1m
{b (0) pm
and {az mm given
lk=1
n
n2 81/2
m N
Ω
log
8
K.2 J2
THE SECOND DERIVATIVE HAS JUMP DISCONTINUITY AT A POINT
K.2.1 DZPS SETTING
Recall that this setting was defined in Section 2.
Theorem K.4. Let satisfy the condition for 2. Assume that (0) NO, Ia) and d
(0, Ak E [m]. Then, the minimum singular value of the G-matrix satisfies
83
Amin (G())
2
n²
log
(0) Jmm and {ar (0) Jm given that m with probability at least 1 =((m//??) with respect to {w satisfies
n
n2
n² log(d)
> max
Ω
log
81/3
Proof. In the following, we will use Wy instead of w and as instead of a Referring to Equation 4, it suffices show that
4.m;
Gard (WTx x3
x;
is lower bounded for all vectors Ç E 1 with high probability. Fix particular Ç E Sn-1, For each E [m]] and each i [n]. we have w x; ~ (0, 1). First, we analyze the sum for a fixed k, i.c we consider En= Ci o' (wf x;) x,. We split vector Wa as
W& WE Wk.
53

---

Published as a conference paper at ICLR 2020
where We and We are two independent Gaussian vectors in R distributed according to N (o, (1- - 02) La) and N (0, 1s) respectively. We set
8 2000 n² flg
Define the event Cw on a weight vector w as
- a
Cw =
i [n]
100m
Using Fact C.I and the fact that x, are unit vectors,
5 400nv1 82
Pr
(Cw) 2
(53)
(0.
Define the event Dw on weight vector w as
Dw
w
x
S
500n²
i [n]
Fact C.2 shows that,
-t2
Pr (0)7(0,0)1.)
[Dw] 2
1 - 2n exp
(54)
2
2
2 1
(55)
nz
2 0.5,
(56)
where we set 500.20 get Inequality 55.
We want we to satisfy condition Cw. and Wa to satisfy condition D Since, We and Wa are independent of each other, we use Equation 53 and Equation 54 to get
Pwi.wr. (Own, and Dw,) 2 0.25.
Assuming both the conditions hold, follows that IuTx.20 Iw[ 2a We will work conditioned on both the events.
Define function follows,
n f(w) = Σ
Si d'(w
1=1
Note that
Vwf(w) = Σ Si (w ( 1=1
In the sequel, we will use f' for Vwf(w) and f for f(f(w) It is easy to see that the only u/ x; a, since it is the only point of
discontinuities of the derivative of function f are when discontinuity for ø". Thus, assuming that Cw, and Dw. hold, we can apply Taylor expansion to f(wx) for a perturbation of Wa. ensuring that all the derivatives exist in the neighborhood of interest. Hence,
f(wx) = f(wx) + (Wx, (w))) + R2 (W*); where R2 denotes the second order remainder term in the Taylor expansion given by
1 /'
Rs (W+)= = 2
( (wr + twa). w dt. 1=0
Using (w)(w)) En Ci 22 (130 (z)
we have
x=(
R2 (W+) =
Σ
Ca ((W,, xx)) ((3) ((W + tWk, xi)) dt.
t=0 i=
54

---

Published as a conference paper at ICLR 2020
The magnitude of this term can be bounded follows.
((wx: x1))² (Lrn (003) (lwix + twwxx,))
R2 (wx)]
Se
(w
1
((
((wx + xw), di
Σ 2 ((We,
(57)
2
i=1
2
2
(58)
500n²
82
3,5
where Inequality 57 uses Cauchy-Schwarde inequality, Inequality 58 uses the fact that all the deriva- tives of of order up to r+ are bounded for * 0 and We satisfies condition Dwz and Wa satisfies Own. Thus we have
82
f(wL) = f(w))) + (Wk. ('(w))) +
(59)
31.5
Consider the following two cases.
Case 1: [(w+) < 2 2 /0.10.
First, condition the event that We is picked so that || (wx)ll2
0.01 and Cwv holds true. We
shall refer to this condition as Bw By Claim K.5, we get that
Pr (I)'( 0.01 and Care n
Pr [wr,]] We
2 Ω
(60)
we
(1
02)
(Wk, (WWx) is random variable following N (o, (0,0211.((vx))
Thus applying Fact C.I,
0.01
Pr
0 Bwz
Wi
Now letting event Dwn denote the complement of the event Dw. we have
0.01
Pr
Dwx.
Bwi
Wi
Pr
(WWk flik.f(Waa (wx)) 2
0.01 0
Bwi
Pr
0.01 2 n
9
Bw Dwn
Pr [Dwa]] we
Wa
n
2
n
> 1/10.
Hence, from Equation 59, get
0001
[((w))]
Pr
2 2V
and Dwa. Bire
2 0.1.
We
Thus.
1 [s(wa)) 2 2V
0.01
0.01
Pr
> Pr w.
[s(w))) 2 2V n
0 and Bwg and Dwn.
m
[[((w)))
0.01
Pr Wx
Bunl
Pr Wi
0 and Dwa. B
2
Ω
?
55

---

Published as a conference paper at ICLR 2020
Case 2: ) 2
/0100
V
We can upper-hound the magnitude of (w()) by O(vn) as follows.
[
Go W x;
S Σ G
> O((n).
Here we use the fact || = 1, o0 is bounded by constant at all x o a and||x: = 1 for i E [m]] Note that, this bound always holds true, irrespective of the value of wx- Again, using the fact that (Wx, f (wx)) is Gaussian variable following (00, (2), (f
Fact C.I shows that,
0.01 S 1
0.1
2/3
0.1 0.1
Pr Wh
0
Cwr
n
4 vn
(w))
n
Now,
1: 0.01
Pr
[
S VV
A
Dwn.
Car
We
0.01
0.01
= Pr
[(Wk. - 4 V
Cwv
Pr Wk
44V =
Cwv Dwn. Pr [Dwe]
We
1
2
60n
n²
Hence, from Equation 59, get
[s(waa))
1
0.01
!
Pr We
4 VV
o A Dwn Cwn 2 12
7
Thus,
Pr We
[s(wa)] 2 TV
1
0.01
2 Pr [s(wx) 2 VV
0.01
O and Car A Dine
0.01
> Pr
Cwn
Pr We
[F(WW)] 2
and Dan. Cara
We
Ω
Thus, combining the two cases, we have
8 (5
[((w=)]
Pr wk
2
(61)
112.51lon Tog
n?
Hence,
8
Σ
Gand (w? (xs) 2 St
2
(62)
Wi Og
n2 Vogn
owing to the fact that for a standard normal variate ā, |ä is at-least 1, with probability at-least 0.2 using Fact C.1. Applying Chernoff bound over all k [m]. get
3m
S: (w7 xxx)
2 Ω
n² log
56

---

Published as a conference paper at ICLR 2020
with probability at least eexp(-10 fm e-net argument over Ç E g"-1, with 2n Vlogn and e-net size (+) we get that
with respect twilk= and {ax [a=))=-- Applying
81.6
8'm n² log (n)
So Coo(wW (wXx;)
2 Ω
(63)
Armn
1=1
holds for all Ç g"-1 with probability at least
12n² Vlogn
00 13
(0(
md
81.5
with respect to {w and {ax am where we assume that m > 8 consider the following function,
na
log (173
Now
S(w) = Σ>
Gaard' (wffrs) xi
k=1
where ( E S"-1 Note that f(w) is d-dimensional vector. Also, the above can be written as
f(w) Qu
where [gg]]
IR
pdxx is defined by
9. = Szæz,i
and v E RR. defined by
= agd' (wp xx).
Also, since ||||| = 1 and ||x||| 1 Vi [n], we have ||Q 1. Consider the following quantity
Σj=1 Uz. This quantity denotes the dot product of a row vector of Q and v. We can apply Equation 63 to get
8
Uj
Ω
7 log n
Am
holds true with probability at-least - that, the coefficients have been normalized unit norm satisfy the condition based on which Equation 63 was derived. We can take union bound over all the rows of Q to get
with respect to {w*] m and {ax} Note
8'
Ω
n log
i=1
j=1
1=1
8
8mm m n² log
= 11 Ω
= Ω
n log
with probability at least
1
2 1
with probability at least 1 - -2 with respect to {w& m
and {ax)== assuming that m >
? log
Thus, we can use Equation 4 to show that,
83
Omiu (M) 2 Ω
(
neT TuTlogi
Using the fact that Amin (G)))
Omin (M)2 we get that Amin (M O6
gz
with logn
m
probability least 1 22 6m
n
57

---

Published as a conference paper at ICLR 2020
ELU satisfies the conditions required for Theorem K.4. We state this explicitly in the following theorem.
(0) N (N Ig) and ok Is<o (e" - 1) Ix202, have that for the G-matrix,
Corollary K.4.1. Assume w
(0)
N (0,1)) E [m]] if ((x) =
8
Amin (
2
n log
with probability at least 1 -0(
(0) W
with respect to
given that m satisfies
-==1"
n
n² log(d)
72
m max
Ω
log
9
81/3
Claim K.5. Let the variables have the same meaning as in the theorem Theorem K.4. Then,
(IF(W))B2
1 and Cw 2 92( cn
Pr
4n
for variable that depends on and 5.
Proof. Let i" denote arg maXie(n) St- We can split w as w = w w", where
w
(Id X4- x,-x;. w V1 fgix..
and
where 0 n= and g1, 92 are two independent gaussians ~ NN(,, Let & denote the following event.
w x;
and TF x; -al
Vi E [n],i it and 1092| E
10n2
4n
9n
5n2
Event & satisfies condition Cw because for i*
w x = "x, x;- + w x,- - a >
w T - al -
- X;+
90n2
and for all i it,
w x a
w x; w"r x; -a w a
"II x;
20n
Hence, we can write that
[[((W)] 4n
Pr w>.
and Ow
Pr w- --N(0,(1-6311)))
[lf((w)l2 2 and Cw E
Pr
E
4n
Pr w--V(0((1-0))))
[|'(ww)l2 E
Pr
E
w=-N(0,(1-0)1.))
1026 cn
= ②
en?
where Claim K.6 in the final step.
58

---

Published as a conference paper at ICLR 2020
Claim K.6.
Pr (-)((0,c-P.))
|I.'(w)133 2
0.01
3
2
and
0.088
Pr (8) 2 (0, c²
where & is defined and w has been split into w' and w" as in proof of Claim K.5.
Proof. This follows from the proof Claim K.2, with a slight change in distribution of w from N (0. Ia) to N (T,) and the function under consideration is changed to
((w)=
Σ Gi"" (w' (w"xx) xi)
K.2.2 J2 FOR STANDARD SETTING
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
(0) for 1. Assume, w N' (0, Laa b/ N (0. 0.01) and dg N (0, 1m) Wk: E [m]] Then, the minimum singular value of the G-matrix satisfies
6
Amin (GIO)
nodlog
-R( x
with respect to {wk (w mm
with probability at least
given that m satisfies
JK=1"
n² log
n 81/38//9 )) S2
n log(d)
))
m max
Ω
5
Corollary K.6.2 (Adapting Theorem K.4 for Init(fanout) setting). Let the condition on & be satisfied for ro 1. Assume, w N (0, IT) (0) N (o, : and a (0) N (0,1) Vk E [m]] Then, the minimum singular value of the G-matrix satisfies
Amin (.00) 22 Trmn log
with probability at least 1 - e -(6m//n) with respect to {wi 1k= that m satisfies
(0)
(be =k and {az ym given
n²
mn log n
Ω
log
8
82
59

---

Published as a conference paper at ICLR 2020
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 Equa-
tion 1. Assume that W (0) N (0.1) and a Uf-1,+1) Ak [m], Assumption and
Assumption hold true and ysl S C, for some constant C. Then, if we use gradient flow optimiza-
n2" log
tion and set the number of hidden nodes m = Amin (G
with probability at least
over the initialization we have
y/1² S e Amtn (G (G yll
Remark, The above proof can be adapted for the gradient descent algorithm with a learning rate less than O (Amin (G.), /n²). following the proof of Theorem 5.1 in Du et (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.I. If the activation is ReLU and m 5 (n48-3 log n). then with probability at least exp
m8
log
1.5
Amin
(0)
2 S2
log
Remark. Compare the previous theorem with Cor. K.2.1.
Proof.
Using Lemma I.1, we have
Amin (G 2 2 (d') Amin (x*")""")), Vr E
where denotes x n matrix, with its i-th column containing x, and X E Rd x denotes its order-r Khatri-Rao product. Note that, by Assumption 1, the columns of X*7 are unit normalized cuclidean vectors. If for any i,j E [n], x²'x, = < 1, then we can see that (xx*) T x = pp, where x" denotes the order-r Khatri-Rat product of a vector x. Also, /pl can be shown to be at most 5, using Assumption 2. Thus, for the magnitude of (x"")² x5". for any i, [m], # j. be less than 2n we must have 2 ro 20 Hence, for any ro the diagonal elements of (X*r)² X are equal and magnitude of the non diagonal elements less than 2n. Thus, applying Fact C.10, we get that
1
Amin (X
X
2
Using Equation 18, we see that for
+ log 27
&
(0') 0
((
log 2n
-1.5
Thus.
((10e
log 2n
-1.51
Amin (G 2
For computing Amin (1(0) we bound the absolute difference in each element of G and (0) by
2n. Amin (G 2c) using Hoeffding's s inequality (Fact C.3) and 1-Lipschitzness of & and then apply union bound over all the indices. The bound stated in the theorem follows from the fact that
Amin (G:0) 2 Amin (Go0)
(G -C
F
Amin (Go0) Amin (G /2.
60

---

Published as a conference paper at ICLR 2020
Using the bound of Amin (G from Theorem L.2 in Theorem L.1, get the following explicit rate of convergence for 2 layer feedforward networks.
Theorem L.3 (Thm 3.3 in Du 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 n log [n] log m with probability at least 1 - R. over the initialization we have
89
U1 yl1 Se
Vt 20 logt. log " . for an arbitrarily small constant e 0.
61

---

Published as a conference paper at ICLR 2020
M EXTENSIONS AND ADDITIONAL DISCUSSION
In this section, we discuss proof's and extensions of our theorems, using adaptations from related work.
M.1 POLYNOMIAL MINIMUM EIGENVALUE OF G-MATRIX AT TIME
The upcoming lemma shows that, if restrict the change in weight matrices, the minimum eigenvalue of G stays close the minimum eigenvalue of (
Amin (
Lemma M.1. If activaation function & is a-lipschitz and 3-smooth and w w Wr E [m], then
(G(+)
Amin (G.O)
Amin
Proof. The claim follows similar proof as the proof of lemma B.4 in Du 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 Se S [n] denote a randomly picked batch of size b. Denote (11) as Wool ((xx) Wi)sejm a, W()).. Let the activation function & used be a-lipschitz and B-smooth. The GD iterate at time t + 1 is given by,
w(++1) W(1) (1)
Amna ((0))
Let 17 S
If
Snaatt
a 3.2 log m
m 2 Ω
Amin (G(U))
then,
ly uloll² S
for t 2 () Mdmii (G.O)) ) with probability at-least m
-35 w.r.t. { k=1
(()
(0) mn
and {
{ {((0) m
Moreover,
Amin (())
w (t)
w (0)
40,3n
holds true vk [m] and 11 2 0.
Proof. The claim follows a similar proof as the proof of lemma A. in Du et (2019b), where we keep the output vector non trainable in GD update.
Remark. The above lemmas are applicable for activation functions in J, for 2. Similar lemmas can be proved for J1, along the lines of the proof of Theorem 4.1 in Du et al. (2019a).
M.2 TRAINABLE OUTPUT LAYER
Similar to the proof of Theorem 3.3 in et al. (2019b), we can show that the GD dynamics depends on sum of matrices, i.e.
du(')
dt = (G(1)
(y - (1)),
62

---

Published as a conference paper at ICLR 2020
where the definition of G stays the same and H is given by
hi
Σ rE/m
ow"""
(w),3))
m
implying H is p.s.d. For the positive results, e.g. Theorem 4.1, observe that Amin (G + H) > Amin (G), hence a bound on Amin (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 degree-p polynomial such that (' = =ixx)=Eis Geof
and let d' = dim (span {x1... kn)) = 0 ( Then we have
d ( 0, wk: [2n/dd]
Theorem M.4. Let the activation finction be tanh and let d' dim (span f31... Fn))
o 1og 0.75
0.5 n). Then we have
d + ) Eexp(-9(n < 1/poly(n), vk 2 2n/dd]
[0)] t and ( |==
with probability least 1 2/225 over the random choice of weight vectors
(0)
0kk
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 ())) i.e. n(1 - /) lower order eigenvalues are if é is degree-p polynomial and exponentially small in n 1/dd with high probability, if o is tanh.
Thus, we can use Weyl's inequality (Fact C.11) to show that n(1 = lower order eigenvalues of (()) + (0) are 0, if Φ is degree-p polynomial and exponentially small in n/d with high probability, if ø tanh.
Remark. The lemmas in subsection M.I, that proved for network with trainable output vector a, can also be proved for network with trainable output vector a. And so, polynomial lower bound on minimum eigenvalue of ()) implies polynomial lower bound on minimum eigenvalue of G under appropriate number of neurons and GD training.
M.3 MULTI CLASS OUTPUT WITH CROSS ENTROPY Loss
Let's say, have classification task, where the number of classes C' and we use the following neural network for prediction.
f A, W)
Co m
and
(
E [C]
where x E dRd is the input and W [WI...., Wm] E R is the hidden layer weight matrix and A E mR is the output layer weight matrix. We define u (x) E RRC
(x) softmax (f(x: A, A)))
where softmax on vector v E C denotes the following operation
softmax(v); Ejeloye en e"
Given a set examples {x,, ) where x; E Rdd and ys E [C] Vi E [n], we use the following cross entropy loss train the neural network.
(A, W: (x,, v.l. = Σ log (fv, (x; A, W))
63

---

Published as a conference paper at ICLR 2020
Let's denote the vector as nC' dimensional vector, whose elements defined as follows.
0,
jf y/ otherwise
Yc(+-1)+5 1
Also, let's define another vector i E RnC as follows.
Uc(i-1)+ softmax (( W)),
All the network dependent variables have 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
where G E R a gram matrix defined by its elements as follows.
1
Σ ok
(w[x)) of (w?X))
Jpr
YIB
kE[m]
where i = 1 + 1,j = 1 + 1, mod C and q' = mod C. Thus,
d y ((t) ( - - (tt) y ū(t) - -mmin (G+) -000-0000 /
dt
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 neurons, (G)) stays close to (G(0) and hence, the rate of convergence depends on the gram matrix (ā We show that the gram matrix possesses unique structure and related the gram matrix defined for single output network.
G contains C disjoint principal n blocks, denoted by (B*} where B, is defined follows:
Σ
(w oi ø' (wTxx (wεx;).
fJ
kE(m)
As can be seen, each B is structurally identical to the gram matrix defined for a single output neural network with input weight matrix W and output weight vector a, (Equation 2).
Let's denote set of C(C- - remaining disjoint non diagonal blocks of G as (B 3 where each block is defined as follows.
69.9
Σ [c([m]
O (w)x:) o' (wFX;)
Assuming that we have sufficient number of neurons, ( can be shown to be close to the matrix G using Hoeffding's inequality, where G has the following diagonal {(B ) Jq=1 and non diagonal blocks (( je- defined as follows.
(Bo)) Ew- 20 ( (w"x,) &' (w"x))
BB q Ew. aāo (wT x. (w"x,) o ( x,)
Using independence of random gaussian variables a and à and random gaussian vector w, we show that (Bo))ee are identically cally equal to the 0 matrix defined for single output layer neural networks (Equation 2). Thus, Auin (G)) = Amiu (@*)) and hence the bounds for eigenvalues of Amiu \ (Q(9)) can be derived from the bounds for eigenvalues of Amin (G (G()), defined for a single output layer neural network (Equation 2).
matrices. Also, the diagonal blocks (B>o)² are identi-
64

---

Published as a conference paper at ICLR 2020
M.4 FINE-GRAINED ANALYSIS FOR SMOOTH ACTIVATION FUNCTIONS
In this section, 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.
Φ E C
Φ is B-lipschitz and 7-smooth.
Now, we state some important theorems from Du et al. (2019b), that we will use for the future analysis. There some differences in setting and the setting of Du al. (2019b). Du et al. (2019b) work with general layer neural network. Hence, we state their theorems for L = 1. b) For simplicity of presentation, have assumed that Og 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 Vi E [n] .uus O (1) and
n K' 41 (Aain (G101)
n2
n² log 22 (Amin (G(01)
m 2 Ω
max
If we set step size as
Amin (())
17 = 0
n²
m [wx (0) }
then with probability least 1 K over
the following holds Vt Z
k=1
Amiin (G(O)
((wie)) 5
L (wr())
1
Note that al. (2019b) consider Amin (G in their arguments. However, in the overparametrized regime, with high probability with respect to {w>) Amin (Go) and Amin (G))) differ only by
constant factor, as given by lemma B.4 in Du al. (2019b). Thus, we show their theorems using Amin ((0))
Theorem M.6 (Lemma B.6 in Du et al. (2019b)). Assuming the setting in Theorem M.5, the following holds Vt E zt and vk [m].
w
(1)
w!
10)
0
71
Mmimmin (G(O))
Theorem M.7. Assuming the setting in Theorem M.5, the following holds Vt. E Z
G - G:00 50 ( n²
Vmdmin (1O0)
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 over all the elements to get bound over the
65

---

Published as a conference paper at ICLR 2020
perturbation.
(0)
[0)
Xi, x₁)
W
((()) xix & (w x,)
Σ
108T xi)
of
k x,)
10)T
m
k=1
k=1
1
(1) xx)
&3 (w ( x,) o8 (w xx 2e' W
(1)2 x,)
W
m
(0)T
6 (w/k (1) x,)
w/ (0)T xx of w
(0)T xj)
k
x:
1:
(t)T
x,
w (0) x
o'
w (t)T X3)
(t)T W
x3
0' (w
(
(0)T
x3)
0' (w
10)T Xi
< 21)(
Wk
-w/
- O
yn
mmxiin
(G
where, we use Theorem M.6 and the fact that o' is 7-smooth and is bounded by ((1) in the final step. Thus, get
-G(00
- G(O)
Σ
(0)
gij -9i5
0 50
?
Vmdmiu (G
as required.
Lemma M88 (Claim 3.4 in Du et al. (2019a)). In the setting of Theorem M.5,
| - (0))
holds with probability at least is with respect { w/ Ja=I
Now, we state the following theorem, which is a simple adaptation of theorem 4.1 in Arora et al. (2019c). Let v1, U2,..., En denote the eigenvectors of G(O), corresponding to its eigenval- ues Åι, A2 ... An-
Theorem M.9. With probability at least over the random initialization, E Zt, the following holds
u (2)
n
[1
ne321) 2t (v." (y (x-u(o)))
u(o))) =c,
y
provided
n
m 2 Ω
Ynddmuu (G())) 2
and
Amin ((
17 - 0
n2
66

---

Published as a conference paper at ICLR 2020
Proof. For each E [n]. we get
(t-1)
c
m
ak
(111)Tx x:
20 (wk
(w (1)T
x:)
m
k=1
C6
m
((w))
(w(()
0 C (wkx) )
I
@w
10T
ak
(W - "ww
x
1 (wi
xi)
(64)
m
k=1
(1)T xx) (-11 2 L (w(²) )) T
x, + (t)
(65)
dwk
m
7
8 (w/² (w/"TTxx, xi) oi ( (w x,) x) (u)) V/3 (xx:x)) + 6,x (1)
2
(t) - Uz + c (t) u
(66)
where we use Taylor expansion of é in Equation 65. e (t) denotes the error term due to truncated Taylor expansion, whose norm can be bounded by
2
|ea (t)
S
Cp
O())
" (Taw
2 C (m )
X;
(67)
2 m
3/2 2 (1)
Σ and' (w x3)
x (xx, (x-
u(() u())/
/=1
Co 2m3/22
" (0
Σ akp' (w( xx) xx) ||s-u(0)
(68)
7=1
12² con
||x Ay--u% u
0
(69)
vm\ log m
where we use the fact that [z)
S O(1VV= E R in Equation 67, use the Cauchy-Schwartz inequality in Equation 68 and use the fact that (o(()) I ((1)v2 E R, (xx, $ Vi,j E [M] and lasl $ vlog m with high probability in Equation 69. Thus, this gives
(1+1) - ( = - (()) (u() y) + c(t)
where
||<(O]| Σ ca(1)² so ( n"² mm/ log m
n
( 1 u 1/0)/²
Now, since G()) is close to ( we can write
u ((+1) (t) - (0) (n()) yy + T())
(70)
n where 7(1) - (00 - G()) (n(()) -y) + +c(t). The norm of (1)) can be bounded as follows.
(G()) G()) (u()) -y x) +||ec0|1
||t(0]|| < m
< 1
( ((
10 >| +||=(00|
n
n2g
y y y ( Vm/ logm) ) ||x u0
1 u + ( rPegno02
00
m
mmmmiu (G(0)
my²c2
00
Vmdmin (G10))
67

---

Published as a conference paper at ICLR 2020
Thus, applying Equation 70 recursively, get
t-1 Σ
u (I- ne _ (u y) +
I I
(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.
) (u -x)
| (1- n2 (u -x)
Σ
1 neghi) v.v?
1 - nc3x)) 20 (v. (u(0) -y))²
Σ
(72)
Now, the norm of the second term can be bounded as
I - 7ed (
7(t- 1-
I no G (//0 1
1 ne Ami (c1)))
myn² cg
mmmmin
(G
y
(73)
t-1-1'
ne (G(O)
myn=c
no Amin
(100)
0 ((vn/r)
minin (G
4
d'=0
neg
Amin
((())
ymn 5/2
st
1
O
/miAmmn (G:0))
In Equation 73, we use the following.
y (1
m/ Amia (G(0)
m Amin (G(0)
(0)) 3/1 s
o (
(Vn/k)
Thus, combining the two terms, we have
t-1
(G(0)
nc Amin
mpn 5/2 oz /mRidmin (G10)
8/ s
Σ 1 - neBr1 (vT (y
(0)))((())
w())) (yrru((0)
+t- 1
0
4
(74)
| 1- ne3)) (vT
2 (vT(x- (y (V--100)) +
5/2
(75)
//mm22 min (G1O))
where in Equation 74, we use the fact that
ne Amin (G(0)
4
1-
<
4
m Amin (G(o))
68

---

Published as a conference paper at ICLR 2020
Thus, for the term denoted by to be less than e, need
yn
m 2 Ω
KAmin (G(U))+
M.5 PROOF FOR SGD
The following theorem is an adaptation of Theorem 2 in Allen-Zhu al. (2019), which asserts fast convergence of SGD for ReLU. The theorem below applies to activation in J, for r 2 2; the case of J, can handled by another adaptation Theorem 2 in Allen-Zhu 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 S. [n] denote a randomly picked batch of size Let V(O) denote V wos (xxx,)) ies, ;a, w Let the activation function & be a-Lipschitz and 3-smooth. The SGD iterate at time + is given by.
w(++1) w(() (1)(()
Let 17 S O Amiia (G1O)
on If
n cx433 log m
m 2 Ω
112 122mi (G()))
then,
y u Se
n² ( (z 3 log (t) ) with probability at least e -0(n)) m -35 w.r. random
for 2
choice of So t O.
Proof. Note that
Es, (1) Wook (f(x) Ui) sel) ;a, W(0)
Using taylor expansion for each coordinate have (1+1)
(( (7(1) - (W())
=4;
4 on (WOO) - SVICO) ds
==0
(V() ((0,)(((())) do + /"' (D1o, (( w/ (wo)) (w())-501) ds
==
(t) 11()
(76)
Writing the decrease of loss at time t, we have
( (c-1)
y (t)
(u((+)) u(t))) -u())
2
y (1())
-2(y ( (t()) + ((()) [(t+1)) ((())+|(((tt))) -n(t)/?
( (4)
2(y ( 2(y - u0) + 1u - (00
(77)
(78)
69

---

Published as a conference paper at ICLR 2020
where I E IR" and its 1th coordinate is given by H.. Similarly, we define 12-
f is given as,
T = -1 ( (7(0 u,( (W(()))
T T
12
Σ
3/ (1) 24
(79)
jES
11
y/ gig
(
(80)
JES.
where we use the definition of (0) in Equation 79.
That implies,
L "b G ((t) (t)
(u ->>
11 ((0)
|1 y n
S " na
(0)
(81)
where (()) Raxx denotes diagonal matrix that has in 2th diagonal element, iff i E S, and 0 otherwise and | S |G S nL?,, since & is a-lipschitz.
Note that,
Es, (y - ( Es.
Σ
T Uu m.
(1())
Mij (u) y)
(2) (1)
(E[N] JES.
= (y -u())) T (())
y u(()
(G()) (c un00
2 Mmin
(82)
Also, we can bound 1n in the following manner.
I5(() s
2t (W(()) un
max 05*50
Since,
n//b 2
Σ KES,
u(00) a (w.x))
n 1.5 a b
y y- y
=
F
and
(u((W (W())) u/ (wi0- -5444)
0' (w:xx - 2 (w.. x2 - s 7 x:)
a
x;
1
Σ
m
(S xx x;
B
m
1
3n
V (1)
Σg a?
/m
rE/m]
< 3mn
1.5
y
u (t)
(83)
70

---

Published as a conference paper at ICLR 2020
where we use B-smoothness of the activation function & in the first step, Σx a² - 5m with high probability and raxm S
v in 3rd step.
2
That implies.
I5(1) S Bnjnn a²
y
w
a² Brj
1 y
(0)
(84)
Also,
uu( (W())) us (Wo)) (w(0)_s((1)) -sv(1)
Σ r=1
w x3 - 16 ( x; 8 sViOT xi)
or
1
m
(5 xx)
a,a
m
[ 2
S aa²
max rE/m]
rE|m)
S 2²2 ré/m]
max
(((0)
b y (1) 1)) 2
n2..5 0 S 2²²
(85)
Hence, using Equation 77, Equation 81, Equation 84 and Equation 85, we get
u (+1))
= 1 -y-u (t)
(1)
2(y 1
T/ 11 2(y - u()))/1 12 + (ct - 100 / (86)
2
L2
4.5 a² n2
a
1p ) )110 ||s u10
1 + 211
+
2,31
+
(87)
b
b
= =0 ((1+20
n2a2
||5 p
(88)
b
Taking log both the sides, we get
log (1x-n(tti) (11))
{ 50
2
n²aa²
+ log (1x (1x-uc0)) mcoll²)
11
b
By azuma-hoeffding inequality, we have
log (1x (00) 1011)) E... log (1x- -00 s Vio
n²a²
11
n
(89)
with probability at-least e- -0(22
Also,
Es. |yy u (++)
y ((() -s,2(y-u(!) ( Es,
- -s T Ess ((11) (0)
Mmmin (c(t)++ 2, 4.52
a
bス 1 2n
y (1())
(90)
f2
4.5 a² 7dmmn (G))) 2
at
|| - u
+
(G())) ) yy 00
Amii
(91)
71

---

Published as a conference paper at ICLR 2020
where we use Equation 82, Equation 84 and Equation 85 in Equation 90. Taking log both the sides, we get
log Es. l 1(3 log (1x-u()) u m001l() Mmii (G
Using Jensen's s inequality, we ger
Es, log (1x (
11) log (|x-u()) m(col() Amia (G(O)
(92)
Thus, for 2 using Equation 89 and Equation 92, we get
log ( 1/0
n²a² log (1x- 11]) 2 (ndmii (G1O0) t
s Vio
11 b
n²aa 2
y - (0) =001133)) 122)
(Vndmia Ammia (G(O:) (vi) -0 ( Ammin (G b
VAmin " (V=
< log
n n
+0
(V VAmin (G(01)
7)
2 )
AAmmn (G())) (Vi) ( - -0 -VV
n²a2
< log 110 (10))
V
(G(D) (G:0)
"
+1
b
log (|> 1y--(00// 100011 112)
(0))
aa
n7min (G: t
I
t2
Ω
b min (G:0))2
(G()) 2
< log (|x - u 10/
Jy-uu0//
a
1 Ammin
I
2
t t+1 1
ba Ami (G
8n
(93)
Hence, if > Ω
(0Am))(Gro)) log (=) we have
log (y-u(0013 < log (m)) - 2 log
12 log (e)
implying y (())
S E. Also, let To
n4 (io0y
Then, applying Equation 93 in chunks of
82 Aamin
steps To, get
(
(vn)
Σ
s 2To (Vn)
2To
+
+ +...= O((TTa)
(94)
2
which implies
8
8 w/!/
w
((+)
Σ
7
(1)
Σn "
Σ ard
(
xz Ii
iES,
an am- "//li////oo m
(1)
(95)
bym
1=
an unnnyylgg log To bym
(96)
72

---

Published as a conference paper at ICLR 2020
where in Equation 95 we the fact that maximum magnitude of a, is vlog with high probability.
Also, for G - G to be less than z Amin
(G(
we need to have (Lemma M.11)
(())
min
(
4a,3n
Thus, for both the conditions to hold true, must have
n ar log m
m 2 Ω
(97)
1 1 (G()))
Lemma M.11. If activation function & a-lipschitz and 3-smooth and w (:())
(0)
Amtia
Wr [m], then
400B
Amin
(G++
Amin (G:O)
Proof.
(0)
1
(w(()Txx) x:) & (w!'Tx)) x3) a2? (w.0iTxx) & (w.(oTx) x,)
Pij
Dij
a
max 0' (w!)Tx) oo (w.)) - o (w/ x,) 0 (x,0xx/)) x,y rE[ml
r=1
< max rE(m]
ø w ( xx)
69 (w{)Tx)) oe (w//))
+ Φ5 (w<(0)r>> x3)
o (w!)TTx)) x;) of (w!O)T x:
< max 20,3 rE(m)
w!!)) (o)
(98)
Hence,
|00 |000 -0(00 ||,
max 2T,3n w(()) w!
r
r[(m)
Since
Amin (G))) 2 Amin (G - - - (
F.'
we have
Amin (()))
2 Amin
G (0)
max 20, ((() w
rE[m]
Thus, for Amin
(G(
1
Amiu
(0)) we have
2
w(()
w..0//
Amin (G
max
5
re rm(m]
4cr.3n
73

---

Published as a conference paper at ICLR 2020
N SOME BASIC FACTS ABOUT HERMITE POLYNOMIALS
For P E [-1,]] we say that the Gaussian random variable (No, 01) is p-correlated
N (0. (b)))
U1) U1)
Fact N.1 (Proposition 11.31 in O'Donnell (2014)).
p" in
(yow))) p-correlated Hen (vo) Hem (v1)
otherwise.
where recall that He, 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 IR R by
R(p) == E ( ((vo) p-correlated
Then,
20 R(p) = 1 (0)
where &o (0) is the a-th coefficient in the probabilists' Hermite expansion of 6. The function satisfies the following two properties.
R((p) < R(p)).
R(p) is increasing in (0, 1).
In the following we let E ==
Poo
Po1
)
P01
P11
Lemma N.3.
to
21
Por Venin
if = m,
((oo.1)~<N(037)) Hen
Hem
/ooo
Vpn
otherwise.
Proof. The proof follows from the proof of Fact N.1, by using r.v. (ō), 02), defined by
00
8g
01
/Puo
/
P11
Ooi VPooP11
so that vector (01, 02) N (0, where >'
1
Vpoopli
Lemma N.4.
Vo
U1
E o
/00
/PII
Poo0P11
a=0
Proof.
Vu VP00
E
VPI1
EvnA((.
Ca (o)
vo /poo
Heg
VPn
a=0
='=0
(0)
Po1
R
P01
VPooP11
PooP11
4=0
where we use Lemma N.3 and Fact N.2 in the final step.
74


Reviews:
[{"review_id": "r1g6d9LCFS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The 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.\n\nOverall, I vote to accept the paper. The paper does a thorough theoretical study of the behavior of the eigenvalues of the matrix corresponding to NTK which is crucial to the NTK analysis. The paper successfully makes the case for non-smooth activations versus smooth activations in the lazy regime. The authors use polynomial approximations and low-dimensionality in an interesting way to show an upper bound on the min eigenvalue for activations approximable by sufficiently low-degree polynomials. The paper is well written, self-contained and well-referenced.\n\nSuggestions/Comments:\n1. Please avoid referencing theorems in the appendix that do not have informal statements in the main paper. For example \"We sketch the proofs of Theorem J.3, Theorem J.4 and Corollary J.4.1 showing that our results about the limitations of smooth activations are essentially tight when the data is smoothed.\": Theorems/Corollary are not mentioned in the main text.\n2. In real data as the authors point out, the dimension of the data is much larger than log n. In the setting of dimension being greater than log n, could you discuss how far the lower-bound from Theorem J.4.2 is from the upper bound from Theorem F.9. It would be useful to write it in similar notation.\n3. The paper, in its current form, is long and probably hard for a general audience to parse. It would be useful to organize the appendix to emphasize the main techniques and ideas.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HyeTpizhqr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The authors of the paper examine how different activation functions affect training of overparametrized neural networks. They do their analysis in a general way such that it includes most activation functions such as ReLU, swish, tanh, polynomial, etc. \n\nThe main point of their analysis is that they examine a matrix called the G-matrix which is described in equation (2), and this (positive semi-definite) G-matrix can determine the rate of convergence to zero of the training error. Namely, the minimum eigenvalue of the G-matrix is inversely proportional to the time required to reach a desired amount of error (Theorem 3.1 (Theorem 4.1 from Du et al. (2019a)). \n\nThe main results separate into two cases: (1) activation functions with a kink (i.e. if the activation function is NOT in C^{r+1}, the space of r+1 continuously differentiable functions, for some finite r) and (2) smooth activation functions.\n\nIn the first case, the authors show that the minimum eigenvalue of the G-matrix is large, i.e. bounded away from zero after a few assumptions.\n\nIn the second case, the authors show that polynomial activations have many zero eigenvalues, and sufficiently smooth activations such as tanh or swish have many small eigenvalues, if the dimension of the span of data is sufficiently small.\n\nThe author’s initial problem setup works on a one-hidden-layer neural network where only the input layer is trained, but provide some extensions in the appendix.\n\nThe authors also provide some empirical experiments: one synthetic data, and on CIFAR10. The synthetic data experiments agreed with theory, but the experiment on CIFAR10 did have some gap between theory and experiment, although the CIFAR10 with ReLU experiment agreed with theory.\n\n\nStengths: I appreciate the author’s effort in providing needed theoretical analysis on how activation affects training error for deep neural networks. The authors also provide an extensive appendix that provide seemingly full proofs of the theorems (although this reviewer did not go into detail for most of the appendix). The authors also provide experiments that confirm the theory and also provide examples highlighting the gap (which this reviewer sees as a strength).\n\n\nWeaknesses: A clear weakness of this paper is that the appendix is too long. The authors do provide a proof sketch of the main results and refer to the appendix, but I would have liked to have seen a more focused paper. Having extensions of the main results is nice, but it’s sometimes unclear what is being extended. Perhaps a list of extension would make clear what’s in the appendix.\n\n\nOther comments: (i) I’d like to an explanation to why it’s called the DZXP setting.\n(ii) On page 4, when explaining the M matrix, I think it should be grad_W F (instead of L)\n\n(iii) On page 4, I think there is more to assumption 1, after looking at Allen-Zhu et al. (2019) (https://arxiv.org/pdf/1811.03962.pdf page 4, footnote 5)\n\n(iv) the wording from page 4, “the matrix G^(t) does not evolve from its initial value G^(0)” is a bit awkward. Do you mean G^(t) does not change much from G^(0), and as to goes to infinity then G^(t) goes to G^(0)?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The article studies the role of the activation function in learning of 2 layer overparaemtrized networks, presenting results on the minimum eigenvalues of the Gram matrix that appears in this type of analysis and which controls the rate of convergence. The article makes numerous observations contributing to the development of principles for the design of activation functions and a better understanding of an active area of investigation as is convergence in overparametrized nets. The reviewers were generally positive about this article. 
Decision: Accept (Poster)