Towards moderate overparameterization: global convergence guarantees for training shallow neural networks

Introduction

Modern neural networks typically have more parameters than the number of data points used to train them. This property allows neural nets to fit to any labels even those that are randomly generated . Despite many empirical evidence of this capability the conditions under which this occurs is far from clear. In particular, due to this overparameterization, it is natural to expect the training loss to have numerous global optima that perfectly interpolate the training data. However, given the highly nonconvex nature of the training landscape it is far less clear why (stochastic) gradient descent can converge to such a globally optimal model without getting stock in subpar local optima or stationary points. Furthermore, what is the exact amount and kind of overpametrization that enables such global convergence? Yet another challenge is that due to overparameterization, the training loss may have infinitely many global minima and it is critical to understand the properties of the solutions found by first-order optimization schemes such as (stochastic) gradient descent starting from different initializations.

Recently there has been interesting progress aimed at demystifying the global convergence of gradient descent for overparameterized networks. However, most existing results focus on either quadratric activations or apply to very specialized forms of overparameterization involving unrealistically wide neural networks where the number of hidden nodes are polynomially large in the size of the dataset. In contrast to this theoretical literature popular neural networks require much more modest amounts of overparameterization and do not typically involve extremely wide architectures. In particular (stochastic) gradient descent starting from a random initialization seems to find globally optimal network parameters that perfectly interpolate the training data as soon as the number of parameters exceed the size of the training data by a constant factor. See Section 4 for some numerical experiments corroborating this claim. Also in such overparameterized regimes gradient descent seems to converge much faster than existing results suggest.

In this paper we take a step towards closing the significant gap between the theory and practice of overparameterized neural network training. We show that for training neural networks with one hidden layer, (stochastic) gradient descent starting from a random initialization finds globally optimal weights that perfectly fit any labels as soon as the number of parameters in the model exceed the square of the size of the training data by numerical constants only depending on the input training data. This result holds for networks with differentiable activations. We also develop results of a similar flavor, albeit with slightly worse levels of overparameterization, for neural networks involving Rectified Linear Units (ReLU) activations. Our results also show that gradient descent converges at a much faster rate than existing gurantees. Our theory is based on combining recent results on overparameterized nonlinear learning with more intricate tools from random matrix theory and bounds on the spectrum of Hadamard matrices. While in this paper we have focused on shallow neural networks with a quadratic loss, the mathematical techniques we develop are quite general and may apply more broadly. For instance, our techniques may help improve the existing guarantees for overparameterized deep networks () or allow guarantees for other loss functions. We leave a detailed study of these cases to future work.

2 Model

We can now rewrite our input-output model in the more succinct form

Here, we have used the convention that when $\phi$ is applied to a vector it corresponds to applying $\phi$ to each entry of that vector.

3 Notations

Main results

To optimize this loss we run (stochastic) gradient descent starting from a random initialization $\bm{W}_{0}$. We wish to understand: (1) when such iterative updates lead to a globally optimal solution that perfectly interpolates the training data, (2) what are the properties of the solutions these algorithms converge to, and (3) what is the required amount of overparameterization necessary for such events to occur. We begin by stating results for training via gradient descent for smooth activations in Section 2.1 followed by ReLU activations in Section 2.2. Finally, we discuss results for training via Stochastic Gradient Descent (SGD) in Section 2.3.

In our first result we consider a one-hidden layer neural network with smooth activations and study the behavior of gradient descent in an over-parameterized regime where the number of parameters is sufficiently large.

and $c$ is a fixed numerical constant, then with probability at least $1-\frac{1}{n}-e^{-\delta^{2}\frac{n}{2\left\|{\bm{X}}\right\|^{2}}}$ all GD iterates obey

Furthermore, the total gradient path obeys

We would like to note that we have chosen to state our results based on easy to calculate quantities such as $\sigma_{\min}^{2}\left({\bm{X}}*{\bm{X}}\right)$ and $\mu_{\phi}$. As it becomes clear in the proofs a more general result holds where the theorem above and its conclusions can be stated with $\mu_{\phi}\sigma_{\min}\left(\bm{X}*\bm{X}\right)$ replaced with a quantity that only depends on the expected minimum singular value of the Jacobian of the neural network mapping at the random initialization (See Theorem 6.2 in the proofs for details). Using this more general result combined with well known calculations involving Hermite polynomials one can develop other interpretable results. For instant we can show that $\sigma_{\min}({\bm{X}}*{\bm{X}})$ can be replaced with higher order Khatrio-Rao products (i.e. $\sigma_{\min}({\bm{X}}^{*r})$).

Before we start discussing the conclusions of this theorem let us briefly discuss the scaling of various quantities. When $n\gtrsim d$, in many cases we expect $\left\|{\bm{X}}\right\|$ to grow with $\sqrt{n/d}$ and $\sigma_{\min}({\bm{X}}*{\bm{X}})$ to be roughly a constant so that $\kappa({\bm{X}})$ is typically a constant (see Corollary 2.2 below for a precise statement). Thus based on (2.2) the typical scaling required in our results is $kd\gtrsim n^{2}$. That is, the conclusions of Theorem 2.1 holds with high probability as soon as the square of the number of parameters of the model exceed the number of training data by a fixed numerical constant. To the extent of our knowledge this result is the first of its kind only requiring the number of parameters to be sufficiently large w.r.t. the training data rather than the number of hidden units w.r.t. the size of the training data. That said, as we demonstrate in Section 4 neural networks seem to work with even more modest amounts of overparameterization and when the number of parameters exceed the size of the training data by a numerical constant i.e. $kd\gtrsim n$. We hope to close this remaining gap in future work. We also note that based on this typical scaling the convergence rate is on the order of $\left(1-c\frac{d}{n}\right)$.

We briefly pause to also discuss the case where one assumes $n\lesssim d$ (although this is not a typical regime of operation in neural networks). In this case both $\left\|{\bm{X}}\right\|$ and $\sigma_{\min}({\bm{X}}*{\bm{X}})$ are of the order of one and thus $\kappa$ scales as $\sqrt{d/n}$. Thus, the overparmeterization requirement (2.2) reduces to $k\gtrsim n$. Thus, in this regime we can perfectly fit any labels as soon as the number of hidden units exceeds the size of the training data. We also note that in this regime the convergence rate is a fixed numerical constant independent of any of the dimensions.

Before we start discussing the conclusions of this theorem let us state a simple corollary that clearly illustrates the scaling discussed above for randomly generated input data. The proof of this simple corollary is deferred to Appendix E.

with probability at least $1-\frac{2}{n}-e^{-\frac{d}{4}}-ne^{-\gamma_{1}\sqrt{n}}-(2n+1)e^{-\gamma_{2}d}$ all GD iterates obey

Here, $\gamma_{1},\gamma_{2},c,C,c_{1},c_{2}$, and $c_{3}$ are fixed numerical constants.

We would like to note that while for simplicity this corollary is stated for data points that are uniform on the unit sphere, as it becomes clear in the proof, this result continues to hold for a variety of other genericInformally, we call a set of points generic as long as no subset of them belong to an algebraic manifold. data models with the same scaling. The corollary above clarifies that the typical scaling required in our results is indeed $kd\gtrsim n^{2}$. That is, the conclusions of Theorem 2.1 holds with high probability as soon as the square of the number of parameters of the model exceed the number of training data by a fixed numerical constant.

The theorem and corollary above show that under $kd\gtrsim n^{2}$ overparameterization Gradient Descent (GD) iterates have a few interesting properties properties:

Gradient descent iterates remain close to the initialization: The second interesting aspect of our result is that we guarantee the GD iterates never leave a neighborhood of radius of the order of $\sqrt{n}$ around the initial point. That is the GD iterates remain rather close to the initialization.Note that $\left\|\bm{W}_{0}\right\|_{F}\approx\sqrt{kd}>>\sqrt{n}$ so that this radius is indeed small. Furthermore, (2.5) shows that for all iterates the weighted sum of the distance to the initialization and the misfit error remains bounded so that as the loss decreases the distance to the initialization only moderately increases.

Gradient descent follows a short path: Another interesting aspect of the above results is that the total length of the path taken by gradient descent remains bounded and is of the order of $\sqrt{n}$.

2 Training ReLU networks via gradient descent

The results in the previous section focused on smooth activations and therefore does not apply to non-differentiable activations and in particular the widely popular ReLU activations. In the next theorem we show that a similar result continues to hold when ReLU activations are used.

and $\gamma$ and $c$ fixed numerical constants, then with probability at least $1-\frac{1}{n}-e^{-\delta^{2}\frac{n}{\left\|{\bm{X}}\right\|^{2}}}-ne^{-n}$ all GD iterates obey

Also similar to Corollary 2.2 we can state the following simple corollary to better understand the requirement in typical instances.

with probability at least $1-\frac{2}{n}-e^{-{d}}-ne^{-\gamma_{1}\sqrt{n}}-(2n+1)e^{-\gamma_{2}d}$ all GD iterates obey

Here, $\gamma_{1},\gamma_{2},c,C,c_{1},c_{2}$, and $c_{3}$ are fixed numerical constants.

The theorem and corollary above show that all the nice properties of GD with smooth activations continue to hold for ReLU activations. The only difference is that the required overparameterization is now of the form $\sqrt{kd}\geq C\frac{n^{2}}{d}$ which is suboptimal compared to the smooth case by a factor of $n/d$.

Our discussion so far focused on results based on the minimum singular value of the second order Khatrio-Rao product ${\bm{X}}*{\bm{X}}$ or higher order products ${\bm{X}}^{*r}$. The reason we require these minimum singular values to be positive is to ensure diversity in the data set. Indeed, if two data points are the same but have different output labels there is no way of achieving zero training error. However, assuming these minimum singular values are positive is not the only way to ensure diversity and our results apply more generally (see Theorem 6.3 in the proofs). Another related and intuitive criteria for ensuring diversity is assuming the input samples are sufficiently separated as defined below.

We now state a result based on this minimum separation assumption. This result is a corollary of our meta theorem (Theorem 6.3) discussed in the proofs.

Then with probability at least $1-\frac{2}{n}-e^{-\nu^{2}\frac{n}{\left\|{\bm{X}}\right\|^{2}}}$ all GD iterates obey

We would like to note that related works consider slight variations of this assumption for training ReLU networks to give overparameterized learning guarantees where the number of hidden nodes grow polynomially in $n$. Our results seem to have much better dependencies on $n$ compared to these works. Furthermore, we do not require the number of hidden nodes to scale with the desired training accuracy ($\mathcal{L}(\bm{W})\leq\epsilon$) as required by .

3 Training using SGD

The most widely used algorithm for training neural networks is Stochastic Gradient Descent (SGD) and its variants. A natural implementation of SGD is to sample a data point at random and use that data point for the gradient updates. Specifically, let $\{\gamma_{\tau}\}_{\tau=0}^{\infty}$ be an i.i.d. sequence of integers chosen uniformly from $\{1,2,\ldots,n\}$, the SGD iterates take the form

Here, $G(\bm{\theta}_{\tau};\gamma_{\tau})$ is the gradient on the $\gamma_{\tau}$th training sample. We are interested in understanding the trajectory of SGD for neural network training e.g. the required overparameterization and the associated rate of convergence. We state our result for smooth activations. An analogous result also holds for ReLU activations but we omit the statement to avoid repetition.

Furthermore, on this event the SGD iterates never leave the local neighborhood $\left\|\bm{W}_{\tau}-\bm{W}_{0}\right\|_{F}\leq c\nu\sqrt{n}$ with $c$ a fixed numerical constant.

This result shows that SGD converges to a global optima that is close to the initialization. Furthermore, SGD always remains in close proximity to the initialization with high probability. To assess the rate of convergence, let us assume generic data and $n\geq d$, so that we have $\|{\bm{X}}\|\sim\sqrt{n/d}$ and $\sigma_{\min}({\bm{X}}*{\bm{X}})$ scales as a constant. Then, the result above shows that to achieve a relative accuracy of $\varepsilon$ the number of SGD iterates required is of the order of $\tau\gtrsim\frac{n^{2}}{d}\log(\frac{1}{\varepsilon})$. This is essentially on par with our earlier result on gradient descent by noting that $n$ SGD iterations require similar computational effort to one full gradient with both approaches requiring $\frac{n}{d}\log(1/\epsilon)$ passes through the data.

The need for overparameterization beyond width

which is a simple least-squares problem with a globally optimal solution given by

This simple observation shows that the simple least-squares optimization over the output weights achieves zero training as soon as $\bm{\Phi}$ has full column rank. Thus, in such a setting a simple kernel regression using the random features $\phi(\bm{W}\bm{x}_{1}),\phi(\bm{W}\bm{x}_{2}),\ldots,\phi(\bm{W}\bm{x}_{n})$ suffices to perfectly interpolate the data. In this section we wish to understand the amount and kind of overparameterization where such a simple strategy suffices. We thus need to understand the conditions under which the matrix $\phi\left({\bm{X}}\bm{W}^{T}\right)$ has full row rank. To make things quantitative we need the following definition.

We define the output feature covariance matrix as

With this definition in place we are now ready to state the main result of this section.

Then, the matrix $\bm{\Phi}:=\phi\left({\bm{X}}\bm{W}^{T}\right)$ has full row rank with the minimum eigenvalue obeying

Thus, the global optima of (3.1) achieves zero training error as long as $\widetilde{\lambda}({\bm{X}})\geq\frac{6B}{n^{100}}$.

We note that one can develop interpretable lower bounds for $\widetilde{\lambda}$ (see Appendix H). For instance, in Appendix H we show that

As we discussed in the previous sections for generic or random data $\sigma_{\min}^{2}\left({\bm{X}}*{\bm{X}}\right)$ often scales like a constant. In turn, based on the above inequality $\widetilde{\lambda}({\bm{X}})$ also scales like a constant. Thus, the above theorem shows that as long as the neural network is wide enough in the sense that $k\gtrsim n$, with high probability on can achieve perfect interpolation and the global optima by simply fitting the last layer with the input-to-hidden weights set randomly. Of course the optimization problem over $\bm{W}$ is significantly more challenging to analyze (the setting in this paper and other publications ). However, this simple baseline result suggests that there is no fundamental barrier to understanding perfect interpolation for $k\gtrsim n$ wide networks. In particular, as discussed earlier the result above can be thought of as kernel learning with random features. Indeed, in this settings one can also show the solutions found by (stochastic) gradient descent converges to the least-norm solution and does indeed generalize. Furthermore, neural networks are often trained with the number of hidden nodes of the at each intermediate layer significantly smaller than the data size. Thus to truly understand the behavior of neural network training and demystify their success beyond kernel learning it is crucially important to focus on moderately overparameterized networks where the number of data points is only moderately larger than the number of parameters used for training. We hope the discussion above can help focus future theoretical investigations to this moderately overparameterized regime.

Numerical experiments

Figure 2(a) plots the success probability where $n=100$ and $k$ and $d$ are varied between to $25$. The solid white line represents the $n=kd$. There is a visible phase transition from failure to success as $k$ and $d$ grows. Perhaps more surprisingly, the success region is tightly surrounded by the $n=kd$ curve indicating that neural nets can overfit as soon as the problem is slightly overparameterized. Figure 2(b) repeats the same experiment with a larger dataset ($n=200$). Phase transitions are more visible in higher dimensions due to concentration of measure phenomena. Indeed, $n=kd$ curve matches the success region even tighter indicating that $kd>(1+\varepsilon)n$ amount of overparametrization may suffice for fitting random data.

A related set of experiments are based on assigning random labels in classification problems . These experiments shuffle the labels of real datasets (e.g. CIFAR10) and demonstrate that standard deep architectures can still fit them (even if the training takes a bit longer). While these experiments provide very interesting and useful insights the do not address the fundamental tradeoffs surrounding problem parameters such as $n,k,$ and $d$. Finally, we emphasize that the dataset in our experiment is randomly generated. It is possible that worst case datasets exhibit different phase transitions. For instance, if two identical inputs receive different outputs a significantly higher amounts of overparameterization may be required.

Prior art

Optimization of neural networks is a challenging problem and it has been the topic of many recent works . A large body of work focuses on understanding the optimization landscape of the simple nonlinearities or neural networks when the labels are created according to a planted model. These works establish local convergence guarantees and use techniques such as tensor methods to initialize the network in the proper local neighborhood. Ideally, one would not need specialized initialization if loss surface has no spurious local minima. However, a few publications demonstrate that the loss surface of nonlinear networks do indeed contains spurious local minima even when the input data are random and the labels are created according to a planted model.

Over-parameterization seems to provide a way to bypass the challenging optimization landscape by relaxing the problem. Several works study the benefits of overparameterization for training neural networks and related optimization problems. Very recent works show that overparameterized neural networks can fit the data with random initialization if the number of hidden nodes are polynomially large in the size of the dataset. While these results are based on assuming the networks are sufficiently wide with respect to the size of the data set we only require the total number of parameters to be sufficiently large. Since our conclusions and assumptions are more closely related to we focus precise comparisons to these two publications. In particular, for smooth activations we show that neural networks can fit the data as soon as $kd\gtrsim n^{2}$ where as requires $k\gtrsim n^{4}$. Thus, in terms of the hidden units our results are sharper by a factor on the order of $n^{2}d$.Our results are also sharper in terms of dependence on the quantity $\lambda$ defined in the proofs. In more detail, we require $kd\gtrsim\frac{n^{2}}{\lambda^{2}}$ where as requires $k\gtrsim\frac{n^{4}}{\lambda^{4}}$. Focusing on ReLU networks we require $k\gtrsim\frac{n^{4}}{d^{3}}$ compared to $k\gtrsim n^{6}$ assumed in so that our results are sharper by a factor $n^{2}d^{3}$. Our convergence rate for gradient descent also seems to be faster by a factor on the order of $n$ compared to these results. In addition our results extend to SGD. We would like to note however that our results focus on one-hidden layer networks where as some of the publications above such as apply to deep architectures. That said, our results and proof strategy can be extended to deeper architectures and we hope to study such networks in our future work. Finally, these recent papers as well as our work is inherently based on connecting neural networks to kernel methods. We would like to note that the relationship between kernel methods and deep learning has been emphasized by a few interesting publications .

We would also like to note that a few interesting recent papers relate the empirical distribution of the network parameters to Wasserstein gradient flows using ideas from mean field analysis. However, this literature is focused on asymptotic characterizations rather than finite-size networks.

An equally important question to understanding the convergence behavior of optimization algorithms for overparameterized models is understanding their generalization capabilities. This is the subject of a few interesting recent papers . While this work do not directly address generalization, techniques developed here (e.g. characterizing how far is global minima) may help demystify the generalization capabilities of overparametrized networks trained via first order methods. Rigorous understanding of the relationship between optimization and generalization is an interesting and important subject for future research.

Proofs

Alternatively this can be rewritten in the form

An alternative characterization of the Jacobian is

The latter can also be rewritten in the more compact form

2 Meta-theorems

In this section we will state two meta-theorems and discuss how the two main theorems stated in the main text follow from these results. Our results require defining the notion of a covariance matrix associated to a neural network.

We also define the eigenvalue $\lambda({\bm{X}})$ based on $\bm{\Sigma}({\bm{X}})$ as

As mentioned earlier we prove a more general version of Theorem 2.1 which we now state. The proof is deferred to Section 6.2.

and $c$ a fixed numerical constant, then with probability at least $1-\frac{1}{n}-e^{-\delta^{2}\frac{n}{2\left\|{\bm{X}}\right\|^{2}}}$ all GD iterates obey

Furthermore, the total gradient path obeys

Next we state our meta-theorem for ReLU activations. The proof is deferred to Section 6.2.

holds with $C$ a fixed numerical constant, then with probability at least $1-\frac{2}{n}-e^{-\delta^{2}\frac{n}{\left\|{\bm{X}}\right\|^{2}}}$ all GD iterates obey

Our main theorems in Section 2 can be obtained by substituting the appropriate value of $\lambda({\bm{X}})$ into the two meta theorems above.

3 Reduction to quadratic activations and proofs for Theorems 2.1 and 2.3

Theorems 2.1 and 2.3 are corollaries of the meta-Theorems 6.2 and 6.3. To see this connection we will focus on lower bounding the the quantity $\lambda({\bm{X}})$ which is not very interpretable and also not easily computable based on data. In the next lemma we provide a lower bound on $\lambda({\bm{X}})$ based on the minimum eigenvalue of the Khatri-Rao product of ${\bm{X}}$ with itself. This key lemma relates the neural network covariance (from Definition 6.1) for any activation $\phi$ to the case of where the activation is a quadratic of the form $\phi(z)=\frac{1}{2}z^{2}$. We defer the proof of this lemma to Appendix B. We also note that this lemma is a special case of a more general result containing higher order interactions between the data points. Please see Appendix H for more details.

Then, the neural network covariance matrix and eigenvalue obey

To see the relationship with the quadratic activation note that for this activation

Thus the right-hand side of (6.4) is $\mu_{\phi}^{2}$ multiplied by the covariance matrix of a neural network with a quadratic activation $\phi(z)=\frac{1}{2}z^{2}$.

With this lemma in place we can now prove Theorem 2.1 as simple corollaries of Theorem 6.2 by noting that $\lambda({\bm{X}})\geq\mu_{\phi}^{2}\sigma_{\min}^{2}\left({\bm{X}}*{\bm{X}}\right)$ per (6.5) from Lemma 6.4. Similarly, to prove Theorem 2.3 from Theorem 6.3 we again use the fact that $\lambda({\bm{X}})\geq\mu_{\phi}^{2}\sigma_{\min}^{2}({\bm{X}}*{\bm{X}})$ where for the ReLU activation $\mu_{\phi}^{2}=\frac{1}{2\pi}$.

4 Lower and upper bounds on the eigenvalues of the Jacobian

In this section we will state a few key lemmas that provide lower and upper bounds on the eigenvalues of Jacobian matrices. The results in this section apply to any one-hidden neural network with activations that have bounded generalized derivative. In particular, our results here do not require the activation to be differentiable or smooth and thus apply to both the softplus ($\phi(z)=\log\left(e^{z}+1\right)$) and ReLU ($\phi(z)=\max\left(0,z\right)$) activations.

We begin this section by stating a key lemma regarding the spectrum of the Hadamard product of matrices due to Schur which plays a crucial role in both the upper and lower bounds on the eigenvalues of the Jacobian discussed in this section as well as our results on the perturbation of eigenvalues of the Jacobian discussed in the next section.

The next lemma focuses on upper bounding the spectral norm of the Jacobian. The proof is deferred to Appendix A.1.

Next we focus on lower bounding the minimum eigenvalue of the Jacobian matrix at initialization. The proof is deferred to Appendix A.2.

5 Jacobian perturbation

In this section we discuss results regarding the perturbation of the Jacobian matrix.

Our first result focuses on smooth activations. In particular, we show the Lipschitz property of the Jacobian with smooth activations. The proof is deferred to Appendix C.1.

Our second result focuses on perturbation of the Jacobian from the random initialization with ReLU activations. This requires an intricate perturbation bound stated below and proven in Appendix C.2.

with probability at least $1-ne^{-\frac{m_{0}^{2}}{6n}}$ the Jacobian matrix $\mathcal{J}$ associated with the neural network obeys

6 Proofs for meta-theorem with smooth activations (Proof of Theorem 6.2)

To prove this theorem we will utilize a result from stated below.

Consider a nonlinear least-squares optimization problem of the form

Furthermore, the total gradient path is bounded. That is,

It is more convenient to work with a simpler variation of this theorem that only requires assumption (6.7) to hold at the initialization point. We state this corollary below and defer its proof to Appendix D.

Consider the setting and assumptions of Theorem 6.10 where

holds only at the initialization point $\bm{\theta}_{0}$ in lieu of the left-hand side of (6.7). Furthermore, assume

holds. Then, the conclusions of Theorem 6.10 continue to hold.

To be able to use this corollary it thus suffices to prove the conditions (6.8), $\left\|\mathcal{J}(\bm{\theta})\right\|\leq\beta$, (6.12), and (6.13) hold for proper choices of $\alpha,\beta,$ and $L$. First, by Lemma 6.8 and our choice of $\bm{v}$ we can use

Second, by Lemma 6.6 and our choice of $\bm{v}$ we can use

Here, (a) follows from the fact that $n\geq\log n$ for $n\geq 1$ and (b) from (6.16). Thus by our choice of $\bm{v}$ we have

All that remains is to prove the theorem using Corollary (6.11) is to check that (6.13) holds. To this aim we upper bound the initial misfit in the next lemma. The proof is deferred to Section 6.6.1.

holds with probability at least $1-e^{-\delta^{2}\frac{n}{2\left\|{\bm{X}}\right\|^{2}}}$.

To do this we will use Lemma 6.12 to conclude that

holds with probability at least $1-e^{-\delta^{2}\frac{n}{2\left\|{\bm{X}}\right\|^{2}}}$. Thus, as long as

all the assumptions of Corollary 6.11 hold and so do its conclusions, completing the proof of Theorem 6.2.

holds with probability at least $1-e^{-\delta^{2}\frac{n}{2\left\|{\bm{X}}\right\|^{2}}}$. Thus,

holds with probability at least $1-e^{-\delta^{2}\frac{n}{2\left\|{\bm{X}}\right\|^{2}}}$ concluding the proof.

7 Proofs for meta-theorem with ReLU activations (Proof of Theorem 6.3)

To prove Theorem 6.3 we start by stating a general overparameterized fitting of non-smooth functions. This can be thought of a counter part to Theorem 6.10 for non-smooth mappings. We note that we do not require the mapping $f$ to be differentiable rather here the Jacobian is defined based on a generalized derivative. Consider a nonlinear least-squares optimization problem of the form

Under these assumptions we can state the following theorem. We defer the proof of this Theorem to Appendix G.

Then, using a learning rate $\eta\leq\frac{1}{3\beta^{2}}$, all gradient iterations obey

We shall apply this theorem to the case where the parameter is $\bm{W}$, the nonlinear mapping is given by $f(\bm{W})=\bm{v}^{T}\phi\left(\bm{W}{\bm{X}}^{T}\right)$ with $\phi=ReLU$, and the norm $\|\cdot\|$ is the spectral norm of a matrix.

Completing the proof of Theorem 6.3. With this result in place we are now ready to complete the proof of Theorem 6.3. As in the smooth case (6.3) guarantees the condition of Lemma 6.7 (i.e. $k\geq 20\log n\frac{\|{\bm{X}}\|^{2}}{\lambda({\bm{X}})}$) holds. Thus, using Lemma 6.7 with probability at least $1-1/n$, Assumption 2 holds with

Furthermore, Lemma 6.6 allows us to conclude that Assumption 3 holds with

To be able to apply Theorem 6.13, all that remains is to prove Assumption 4 holds. To this aim note that using Lemma 6.12 with $B=1$ and $\delta\leftarrow 2\delta$, to conclude that the initial misfit obeys

with probability at least $1-e^{-\delta^{2}\frac{n}{\|{\bm{X}}\|^{2}}}$. Therefore, with high probability

Thus, when (6.3) holds using the perturbation Lemma 6.9 with $m_{0}=\sqrt{\frac{k}{{200}}}\frac{\sqrt{\lambda({\bm{X}})}}{\left\|{\bm{X}}\right\|}$, with probability at least $1-ne^{-\frac{k}{1200}\frac{\lambda({\bm{X}})}{\left\|{\bm{X}}\right\|^{2}}}-e^{-\delta^{2}\frac{n}{\|{\bm{X}}\|^{2}}}$, for all $\bm{W}$ obeying

This guarantees Assumption 4 also holds concluding the proof of Theorem 6.3 via Theorem 6.13.

8 Proofs for training the output layer (Proof of Theorem 3.2)

Here $T_{n}$ a function of $n$ whose value shall be determined later in the proofs. To continue we need the matrix Chernoff result stated below.

Next we shall connect the the expected value of the truncated matrix $\widetilde{\bm{A}}(\bm{w})$ to one that is not truncated defined as $\bm{A}(\bm{w})=\phi({\bm{X}}\bm{w})\phi({\bm{X}}\bm{w})^{T}$. To do this note that

Thus by Lipschitz concentration of Gaussian functions for a random vector $\bm{w}\sim\mathcal{N}(\bm{0},\bm{I}_{d})$ we have

holds with probability at least $1-e^{-\frac{t^{2}}{2B^{2}\left\|\bm{X}\right\|^{2}}}$. Thus using $t=\Delta B\sqrt{n}$ we conclude that

holds with probability at least $1-e^{-\frac{\Delta^{2}}{2}\frac{n}{\left\|\bm{X}\right\|^{2}}}$. Thus using $\Delta=c\sqrt{\log n}$ and $T_{n}=CB\sqrt{n\log n}$ we can conclude that

Combining this with (6.22) with $\delta=1/2$ we conclude that

holds with probability at least $1-ne^{-\gamma\frac{k\widetilde{\lambda}({\bm{X}})}{T_{n}^{2}}}$. The latter probability is larger than $1-\frac{1}{n^{100}}$ as long as

Acknowledgements

M. Soltanolkotabi would like to thank the Modest Yachts #mathshop slack channel for fruitful discussions. In particular, Laurant Lessard, Ali Rahimi, and Ben Recht who pointed out via plots that applying softplus to a Gaussian input leads to essentially a uniform distribution. M. Soltanolkotabi would like to thank Zixuan Zhang for help with the simulations of Figure 2. M. Soltanolkotabi is supported by the Packard Fellowship in Science and Engineering, an NSF-CAREER under award #1846369, the Air Force Office of Scientific Research Young Investigator Program (AFOSR-YIP) under award #FA9550-18-1-0078, an NSF-CIF award #1813877, and a Google faculty research award.

References

Appendix A Proofs for bounding the eigenvalues of the Jacobian

To bound the spectral norm note that as stated earlier

A.2 Proofs for minimum eigenvalue of the Jacobian at initialization (Proof of Lemma 6.7)

To relate the minimum eigenvalue of the expectation to that of $\mathcal{J}(\bm{W}_{0})\mathcal{J}(\bm{W}_{0})^{T}$ we utilize the matrix Chernoff identity stated below.

Thus using (A.2) in the above with $\delta=\frac{1}{2}$ we have

holds with probability at leat $1-\frac{1}{n}$.

Appendix B Reduction to quadratic activations (Proof of Lemma 6.4)

First we note that (6.5) simply follows from (6.4) by noting that

Thus we focus on proving (6.4). We begin the proof by noting two simple identities. First, using multivariate Stein identity we have

Combining the latter with (B.3) we arrive at

Hence, setting $\eta=\widetilde{\mu}_{\phi}$ and $\gamma=\mu_{\phi}$ we conclude that

completing the proof of (6.4) and the lemma.

Appendix C Proofs for Jacobian perturbation

To prove this lemma first note that using the form (6.1) we have

Now using the fact that $(\bm{A}*\bm{B})(\bm{A}*\bm{B})^{T}=\left(\bm{A}\bm{A}^{T}\right)\odot\left(\bm{B}\bm{B}^{T}\right)$ we conclude that

To continue further we use Lemma 6.5 combined with (C.1) to conclude that

C.2 Jacobian perturbation results for ReLU networks (Proof of Lemma 6.9)

To prove Lemma 6.9 we first relate the perturbation of the Jacobian to perturbation of the activation pattern $\phi^{\prime}({\bm{X}}\bm{W}^{T})$ as follows.

Proof Similar to the smooth case in the previous section, the Jacobian difference is given by

The lemma above implies that, we simply need to control $\phi^{\prime}(\bm{W}\bm{x}_{i})$ around a neighborhood of $\bm{W}_{0}$. To continue note that since $\phi^{\prime}$ is the step function, we shall focus on the number of sign flips between the matrices $\bm{W}{\bm{X}}^{T}$ and $\bm{W}_{0}{\bm{X}}^{T}$. Let $\|\bm{v}\|_{m-}$ denote the $m$th smallest entry of $\bm{v}$ after sorting its entries in terms of absolute value. We first state a intermediate lemma.

Proof We will prove this result by contradiction. Suppose there is an $\bm{x}_{i}$ such that $\phi^{\prime}(\bm{W}\bm{x}_{i})$ and $\phi^{\prime}(\bm{W}_{0}\bm{x}_{i})$ have (at least) $2m$ different entries. Let $\{(a_{r},b_{r})\}_{r=1}^{2m}$ be (a subset of) entries of $\bm{W}\bm{x}_{i},\bm{W}_{0}\bm{x}_{i}$ at these differing locations respectively and suppose $a_{r}$’s are sorted decreasingly in absolute value. By definition $\left|a_{r}\right|\geq\left|\bm{W}_{0}\bm{x}_{i}\right|_{m-}$ for $r\leq m$. Consequently, using $\text{sign}(a_{r})\neq\text{sign}(b_{r})$,

This implies $\left\|\bm{W}-\bm{W}_{0}\right\|\geq\sqrt{{m}}\left|\bm{W}_{0}\bm{x}_{i}\right|_{m-}$ contradicting the assumption of the lemma and thus concluding the proof.

Now note that by setting $m=m_{0}^{2}$ in Lemma C.2 as long as

Thus to complete the proof of Lemma 6.9 all that remains is to prove (C.2). To this aim, we state the following lemma proven later in this section.

holds for all $i=1,2,\ldots,n$. Hence, with same probability, all $\left\|\bm{W}-\bm{W}_{0}\right\|\leq\frac{m_{0}^{3}}{2k}$ obeys (C.2) concluding the proof of Lemma 6.9.

The complementary event implies that at most $m$ entries are less than $\frac{m}{2k}$. This together with the union bound completes the proof.

Appendix D Proof of Corollary 6.11

First note that (6.13) can be rewritten in the form

Thus using the Lipschitzness of the Jacobian from (6.8) for all $\bm{\theta}\in\mathcal{B}\left(\bm{\theta}_{0},R\right)$ we have

Combining the latter with the triangular inequality we conclude that

so that (6.7) holds under the assumptions of the corollary. Therefore, all of the assumptions of Theorem 6.10 continue to hold and thus so do its conclusions.

Appendix E Proof of Corollary 2.2

holds with probability at least $1-e^{-\gamma_{2}d}$. Furthermore, based on a simple modification of [2, Corollary 6.5]

holds with probability at least $1-ne^{-\gamma_{1}\sqrt{n}}-\frac{1}{n}-2ne^{-\gamma_{2}d}$ where $c,\gamma_{1},$ and $\gamma_{2}$ are fixed numerical constants.

Appendix F Proof of Theorem 2.6

The proof of this result follows from [10, Theorem 3.1] similar to how Theorem 2.1 follows from Theorem 6.10 from the same paper. The only new parameter we have to calculate is the maximum Euclidean norm of the rows of the Jacobian matrix. For neural networks this takes the form

Appendix G Proofs for nonsmooth optimization (Proof of Theorem 6.13)

To prove this theorem we begin by stating a few preliminary results and definitions.

Proof Under Assumptions 2 and 4, applying Lemma G.1 with ${\bm{A}}={\cal{J}}(\bm{x})$, ${{\bm{B}}}={\cal{J}}(\bm{y},\bm{x})$, ${\bm{C}}={\cal{J}}(\bm{\theta}_{0})$, and $\varepsilon=\alpha/3$, we conclude that

Suppose Assumptions 2 and 4 hold. Consider two consequent iterative updates $\bm{\theta}_{\tau}$ and $\bm{\theta}_{\tau+1}$ which by definition obey

with $\eta\leq\frac{1}{3\beta^{2}}$. Also, denote the corresponding residuals by $\bm{r}_{\tau+1}:=f(\bm{\theta}_{\tau+1})-\bm{y}$ and $\bm{r}_{\tau}:=f(\bm{\theta}_{\tau})-\bm{y}$. Finally, assume $\bm{\theta}_{\tau},\bm{\theta}_{\tau+1}$ satisfy $\|\bm{\theta}_{\tau+1}-\bm{\theta}_{0}\|,\|\bm{\theta}_{\tau}-\bm{\theta}_{0}\|\leq R$. Then

Proof For this proof we use the short-hand ${\cal{J}}_{\tau+1,\tau}:=\mathcal{J}(\bm{\theta}_{\tau},\bm{\theta}_{\tau})$ and $\mathcal{J}_{\tau}:=\mathcal{J}(\bm{\theta}_{\tau})$. We expand the residual at $\bm{\theta}_{\tau+1}$ using Lemma G.3 as follows

Using the fact that $\eta\leq\frac{1}{3\beta^{2}}$, we conclude that

With these lemmas in place we are now ready to complete the proof of Theorem 6.13. To this aim suppose the conclusions hold until iteration $\tau>0$. We shall show the result for iteration $\tau+1$. We first prove that iterates still stays inside the region $\|\bm{\theta}-\bm{\theta}_{0}\|\leq R$. To this aim first note that by the induction hypothesis we know that

Combining this with the gradient update rule, $\eta\leq 1/\beta^{2}$ and $\|{\cal{J}}\|\leq\beta$ yields

Now that we have shown $\|\bm{\theta}_{\tau+1}-\bm{\theta}_{0}\|\leq R$, we can apply Lemma G.4 to conclude that

Next, we complement this by using Lemma G.3 to control the increase in the distance of the iterates to the initial point. This allows us to conclude that

Adding the latter two identities, we obtain

Appendix H Lower bounds on the minimum eigenvalue of covariance matrices

In this section we discuss lower bounds on the minimum eigenvalue of the neural network and output feature covariance matrices which involve higher order Khatri-Rao products. This results involve the Hermite expansion of the activation and its derivatives. For any $\phi$ with bounded Gaussian meaure i.e. $\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{+\infty}\phi^{2}(g)e^{-\frac{g^{2}}{2}}dg<\infty$ the Hermite coefficients $\{\mu_{r}(\phi)\}_{r=0}^{+\infty}$ associated to $\phi$ are defined as

where $h_{r}(g)$ is the normalized probabilists’ Hermite polynomial defined by

Using these expansions we prove the following simple lemma. The first one is a generalization of the reduction to quadratic activation Lemma (Lemma 6.4). We note that Lemma 6.4 is a special case as $\widetilde{\mu}_{\phi}=\mu_{0}(\phi)$ and $\mu_{\phi}=\mu_{1}(\phi)$.

Proof To prove this result note that by the properties of Hermite expansions we have

Using the latter combined with the fact that the Hadamard product of two PSD matrices are PSD we arrive at (H.1). The latter also implies (H.2).

Similarly, it is also easy to prove the following result about the output feature covariance.

Proof To prove this result note that by the properties of Hermite expansions we have

concluding the proof of (H.3). This in turn also implies (H.4).

Appendix I Proofs for datasets with δ𝛿\delta-separation (Proof of Theorem 2.5)

Then, the covariance of the vector ${\mathcal{I}}({\bm{X}}\bm{w})$ obeys

For $0\leq\gamma\leq 1/2$, Gaussian small ball guarantees

Next, we argue that ${\bm{z}}_{i}=\left<{\bar{{\bm{Q}}}\bar{{\bm{g}}}},\bm{x}_{i}\right>$ is small for all $i\neq 1$. For a fixed $i\geq 2$, observe that

Hence $1-(\bm{x}_{1}^{T}\bm{x}_{i})^{2}\geq\delta^{2}/2$. From Gaussian small ball and variance bound on ${\bm{z}}_{i}$, we have

Union bounding, we find that, with probability $1-\frac{2n\gamma}{\sqrt{\pi}\delta}$, we have that, $|{\bm{z}}_{i}|>\gamma$ for all $i\geq 2$. Since $\bar{{\bm{g}}}$ is independent of $g_{1}$, setting $\gamma=\frac{\delta}{2\sqrt{2}n}$ (which is at most $1/2$ since $\delta\leq\sqrt{2}$),

On the event $E$, we have that ${\mathcal{I}}(\bm{x}_{i}^{T}\bm{x}_{1}g_{1}+\bm{x}_{i}^{T}\bar{{\bm{Q}}}\bar{{\bm{g}}})={\mathcal{I}}(\bm{x}_{i}^{T}\bar{{\bm{Q}}}\bar{{\bm{g}}})$ since $|g_{1}|\leq\gamma\leq|\bm{x}_{i}^{T}\bar{{\bm{Q}}}\bar{{\bm{g}}}|$. Hence, on $E$,

where $\text{rest}(\bar{{\bm{g}}})=\sum_{i=2}^{n}(a_{i}\times{\mathcal{I}}(\bm{x}_{i}^{T}\bar{{\bm{Q}}}\bar{{\bm{g}}}))$. Furthermore, conditioned on $E$, $g_{1},\bar{{\bm{g}}}$ are independent as ${\bm{z}}_{i}$’s are function of $\bar{{\bm{g}}}$ alone hence, $E$ can be split into two equally likely events that are symmetric with respect to $g_{1}$ i.e. $g_{1}\geq 0$ and $g_{1}<0$. Consequently,

Now, using $\max(|a|,|b|)\geq|a-b|/2$, we find

Proof For proof, we wish to apply the Meta-Theorem 6.3 with proper value of $\lambda({\bm{X}})$. Under Assumption 1, using Corollary I.2, we have that

Substituting this $\lambda({\bm{X}})$ value results in the advertised result $k\geq{\cal{O}}((1+\nu)^{2}n^{9}\|{\bm{X}}\|^{6}/\delta^{4})$ and the associated learning rate.