A Convergence Theory for Deep Learning via Over-Parameterization

Introduction

Neural networks have demonstrated a great success in numerous machine-learning tasks . One of the empirical findings is that neural networks, trained by first-order methods from random initialization, have a remarkable ability to fit training data .

From an expressibility perspective, this may not be surprising since modern neural networks are often over-parameterized: they have much more parameters than the number of training samples. There certainly exist parameter choices with zero training error as long as data is non-degenerate.

Yet, from an optimization perspective, the fact that randomly-initialized first-order methods can find global minima on the training data is quite non-trivial : neural networks are often equipped with the ReLU activation, making the training objective not only non-convex, but even non-smooth. Even the general convergence for finding approximate critical points of a non-convex, non-smooth function is not fully-understood and appears to be a challenging question on its own. This is in direct contrast to practice, in which ReLU networks trained by stochastic gradient descent (SGD) from random initialization almost never suffer from non-smoothness or non-convexity, and can avoid local minima for a variety of network architectures (see Goodfellow et al. 2015). A theoretical justification was missing to explain this phenomenon.

There are quite a few papers trying to understand the success of neural networks from optimization perspective. Many of them focus on the case when the inputs are random Gaussian, and work only for two-layer neural networks . Li and Liang 2018 show that for a two-layer network with ReLU activation, SGD finds nearly-global optimal (say, 99% classification accuracy) solutions on the training data, as long as the network is over-parameterized , meaning that the number of neurons is polynomially large comparing to the input size. Moreover, if the data is sufficiently structured (say, coming from mixtures of separable distributions), this accuracy extends also to test data . As a separate note, over-parameterization is suggested as the possible key to avoid bad local minima by Safran and Shamir 2018 even for two-layer networks.

There are also results that go beyond two-layer networks with limitations. Some consider deep linear neural networks without any activation functions . Daniely 2017 studies multi-layer neural networks but essentially only with respect to the convex task of training the last layer. Daniely 2017 works in a parameter regime where the weight changes of all layers except the last one make negligible contribution to the final output. Soudry and Carmon 2016 show that under over-parameterization and under random input perturbation, there is bad local minima for multi-layer neural networks. Jacot et al. 2018 derive global convergence using neural tangent kernel for infinite-width neural networks.

In this paper, we study the following fundamental questions

Can DNN be trained close to zero training error efficiently under mild assumptions?

If so, can the running time depend only polynomially in the network depth and input size?

Motivation. In 2012, AlexNet was born with $5$ convolutional layers . The later VGG network uses $19$ layers , and GoogleNet uses $22$ layers . In practice, we cannot go deeper by naively stacking layers together, due to the so-called vanishing/exploding gradient problem. To deal with this issue, networks with residual links (ResNet) were proposed with the capability of handling at least $152$ layers . Compared with practical networks that go much deeper, existing theory has been mostly around two-layer (thus one-hidden-layer) neural networks, even just for the training process alone. Thus,

Can we theoretically justify how the training process has worked for multi-layer neural networks?

In this paper, we extend the over-parameterization theory to multi-layer neural networks.

We show that over-parameterized neural networks can be trained by vanilla first-order methods such as gradient descent (GD) or stochastic gradient descent (SGD) to global minima (e.g. zero training error), as long as the data is non-degenerate.

We say that the data is non-degenerate if every pairs of samples are distinct. This is a minimal requirement since a dataset with two identical data points of different labels cannot be trained to zero error. We denote by $\delta$ the minimum (relative) distance between two data points, and by $n$ the number of training samples. Now, consider an $L$-layer fully-connected feedforward neural network, each hidden layer consisting of $m$ neurons equipped with ReLU activation. We show that,

If the task is multi-label classification, then GD/SGD finds an $100\%$ accuracy classifier on the training set in $T={\mathsf{poly}}(n,L,\delta^{-1})$ iterations.

Our result also applies to other Lipschitz-smooth loss functions, and some other network architectures including convolutional neural networks (CNNs) and residual networks (ResNet).

In contrast, prior work on this task either requires $m$ and $T$ to grow in $e^{O(L)}$ (and essentially only the last layer is trained) ; or requires $m=\infty$ .

Our Contributions. We summarize our technical contributions below.

For a sufficiently large neighborhood of the random initialization, we prove that the training landscape is almost convex and semi-smooth. This somewhat explains the empirical finding by Goodfellow et al. 2015 that GD/SGD will not be trapped in local minima. (See Section 4.1.)

For a sufficiently large neighborhood of the random initialization, we derive an equivalence between neural networks and the neural tangent kernel (NTK) introduced by Jacot et al. 2018. Unlike the prior work in which they show the equivalence only for infinite-width networks (i.e., $m=\infty$), here we only need $m={\mathsf{poly}}(L)$ for such an equivalence to hold. (See Section 4.2.)

We show that equipped with ReLU activation, neural networks do not suffer from exponential gradient explosion or vanishing. This is the key reason we can avoid exponential dependency on $L$. If one is okay with $e^{O(L)}$ dependency, many proofs shall become trivial. (See Section 5.)

We derive a stability theory of neural networks against small but adversarial perturbations that may be of independent interests. Previous results on this topic either have exponential blowup in $L$ or requires the width to go to infinity . (See Section 5.)

We derive our results by training only hidden layers. This can be more meaningful than training all the layers together, in which if one is not careful with parameter choices, the training process can degenerate as if only the last layer is trained . That is a convex task and may not reflect the true power of deep learning. (Of course, as a simple corollary, our results also apply to training all the layers together.)

Finally, we emphasize that this present paper as a deeply-simplified version of the recurrent neural network (RNN) paper by the same set of authors. To some extent, DNN is a ‘‘special case’’ of RNN, A recurrent neural network executed on input sequences with time horizon $L$ is very similar to a feedforward neural network with $L$ layers. The main difference is that in a feedforward network, weight matrices are different across layers, and thus independently randomly initialized; in contrast, in an RNN, the same weight matrix is applied across the entire time horizon, so we do not have fresh new randomness for proofs that involve in induction. In other words, the over-parameterized convergence theory of DNN is much simpler than that of RNN. thus most of the technical tools were already developed in . We write this DNN result as a separate paper because: (1) not all the readers can easily derive the DNN result from ; (2) the convergence of DNN can be important on its own; (3) the proof in this paper is much simpler (30 vs 80 pages) and could reach out to a wider audience; (4) the simplicity of this paper allows us to tighten parameters in some non-trivial ways; and (5) the simplicity of this paper allows us to also study convolutional networks, residual networks, as well as different loss functions (all of them were missing from ). We also note that the techniques of this paper can be combined with to show the global convergence of training over-parameterized deep RNN. We ignore the details so as not to complicate this paper.

Towards Generalization. In practice, deeper and wider neural networks generalize better , so what can we say in theory? Although this paper does not explicitly cover generalization to test data, since a neural network in our parameter regime simulates its neural tangent kernel (NTK), it is clear that neural networks provide generalization at least as good as its NTK .

In the PAC-learning language, one may study generalization with respect to concept classes . Follow-up work shows that three-layer over-parameterized ReLU networks can efficiently (in polynomial time and sample complexity) learn the concept class of three-layer neural networks with smooth activations , and the follow-up work shows stronger results for three-layer ResNet.

It is worth pointing out that the three-layer result goes beyond the almost-convex regime and thus is not captured by its NTK; more interestingly, the three-layer ResNet result is not achievable (in a provable sense) by any kernel method including any NTK.

A concurrent but different result. We acknowledge a concurrent work that has a similar abstract but is different from us in many aspects. Since we noticed many readers cannot tell the two results apart, we compare them carefully below. Du et al. 2018a has two main results:

they show time complexity ${\mathsf{poly}}(n,2^{O(L)},1/\lambda_{\min})$ for fully-connected networks; and

they show time complexity ${\mathsf{poly}}(n,L,1/\lambda_{\min})$ for ResNets.

Here, the data-dependent parameter $\lambda_{\min}$ is the minimal eigenvalue of a complicated, $L$-times recursively-defined $n\times n$ kernel matrix. They only proved $\lambda_{\min}>0$ from $\delta>0$. It is not clear whether $\frac{1}{\lambda_{\min}}$ is small or even polynomial from their writing. What is clear is that $\lambda_{\min}$ depends both on $n$ and $L$ (and even on $2^{O(L)}$ for fully-connected networks).

Interestingly, using an argument that $\lambda_{\min}$ only depends on ${\mathsf{poly}}(L)$ for ResNet, they argued that ResNet has “exponential improvement over fully-connected networks.” According to our paper, such improvement does not hold for the ReLU activation since both complexities (for fully-connected and residual networks) can be polynomially bounded by $L$.

Finally, we acknowledge that the polynomials in our paper is quite large and might not be directly applicable to practical regime. However, most of the polynomial factors come from a worst-case analysis to handle the non-smoothness of ReLU. If instead smooth activations are considered, our bounds can be significantly improved.

2 Other Related Works

Linear networks without activation functions are important subjects on its own. Besides the already cited references , there are a number of works that study linear dynamical systems , which can be viewed as the linear version of recurrent neural networks or reinforcement learning. Recent works in this line of research include .

There is sequence of work about one-hidden-layer (multiple neurons) CNN . Whether the patches overlap or not plays a crucial role in analyzing algorithms for such CNN. One category of the results have required the patches to be disjoint . The other category have figured out a weaker assumption or even removed that patch-disjoint assumption. On input data distribution, most relied on inputs being Gaussian , and some assumed inputs to be symmetrically distributed with identity covariance and boundedness .

As for ResNet, Li and Yuan 2017 proved that SGD learns one-hidden-layer residual neural networks under Gaussian input assumption. The techniques in can also be generalized to one-hidden-layer ResNet under the Gaussian input assumption; they can show that GD starting from good initialization point (via tensor initialization) learns ResNet. Hardt and Ma 2017 deep linear residual networks have no spurious local optima.

If no assumption is allowed, neural networks have been shown hard in several different perspectives. Thirty years ago, Blum and Rivest 1993 first proved that learning the neural network is NP-complete. Stronger hardness results have been proved over the last decade .

Preliminaries

We make the following separable assumption on the training data (motivated by ):

For every pair $i,j\in[n]$, we have $\|x_{i}-x_{j}\|\geq\delta$.

Throughout this paper we assume $m\geq\Omega\big({\mathsf{poly}}(n,L,\delta^{-1})\cdot d\big)$ for some sufficiently large polynomial. To present the simplest proof, we did not try to improve such polynomial factors. We will also assume $\delta\leq O(\frac{1}{L})$ for notation simplicity.

Our Results and Techniques

This is known as the linear convergence rate because $\varepsilon$ drops exponentially fast in $T$. We have not tried to improve the polynomial factors in $m$ and $T$, and are aware of several ways to improve these factors (but at the expense of complicating the proof). We note that ${\mathfrak{d}}$ is the data input dimension and our result is independent of ${\mathfrak{d}}$.

In our version 1, for simplicity, we also put a $\log^{2}(1/\varepsilon)$ factor in the amount of over-parameterization $m$ in Theorem 1. Since some readers have raised concerns regarding this , we have removed it at the expense of changing half a line of the proof.

This is again a linear convergence rate because $T\propto\log\frac{1}{\varepsilon}$. The reason for the additional $\log^{2}m$ factor comparing to Theorem 1 is because we have a $1-e^{-\Omega(\log^{2}m)}$ high confidence bound.

For experts in optimization theory, one may immediately question the accuracy of Theorem 2, because SGD is known to converge at a slower rate $T\propto\frac{1}{{\mathsf{poly}}(\varepsilon)}$ even for convex functions. There is no contradiction here. Imaging a strongly convex function $f(x)=\sum_{i=1}^{n}f_{i}(x)$ that has a common minimizer $x^{*}\in\operatornamewithlimits{arg\,min}_{x}\{f_{i}(x)\}$ for every $i\in[n]$, then SGD is known to converge in a linear convergence rate.

Conceptual Messages and Technical Theorems

We highlight two conceptual messages that arise from the proofs of Theorem 1 and 2.

The first message is about the optimization landscape for points that are sufficiently close to the random initialization. It consists of two theorems, Theorem 3 says that the objective is “almost convex” and Theorem 4 says that the objective is “semi-smooth.”

The first property above is easy to prove, while the second property above says that as long as the objective is large, the gradient norm is also large. (See also Figure 1.) This means, when we are sufficiently close to the random initialization, there is no saddle point or critical point of any order.

Back to Theorem 1 and 2. The derivation of Theorem 1+2 from Theorem 3+4 is quite straightforward, and can be found in Section 12 and 13. At a high level, we show that GD/SGD can converge fast enough so that the weights stay close to random initialization by spectral norm bound $\frac{1}{{\mathsf{poly}}(n,L,\delta^{-1})}$. This ensures Theorem 3 and 4 both apply. This spectral norm bound seems small, but is in fact quite large: it can totally change the outputs and fit the training data, because weights are randomly initialized (per entry) at around $\frac{1}{\sqrt{m}}$ for $m$ being large.

In practice, one often goes beyond this theory-predicted spectral-norm boundary. However, quite interestingly, we still observe Theorem 3 and 4 hold in practice (see Figure 1). The gradient is sufficiently large and going in its negative direction can indeed decrease the objective.

2 Equivalence to Neural Tangent Kernel

Theorem thm:ntka and thm:ntkc says that dynamic NTK and NTK are almost equivalent up to a small multiplicative factor as long as $\omega<\frac{1}{{\mathsf{poly}}(L,\log m)}$; while Theorem thm:ntkb says that the NTK objective is almost exactly the first-order approximation of the neural network output as long as $\omega<\frac{1}{m^{3/8}{\mathsf{poly}}(L)}$.

Proof Overview

Our proof to the Theorem 3 and 4 mostly consist of the following steps.

Analyzing forward propagation is not enough. We also need spectral norm bounds on the backward matrix and on the intermediate matrix

The final lemma in this step proves that, as long as $\|x_{i}-x_{j}\|\geq\delta$, then

Again, if one is willing to sacrifice an exponential factor and prove a lower bound $\delta\cdot 2^{-\Omega(L)}$, this will be easy. What is hard is to derive such lower bound without sacrificing more than a constant factor, but under the condition of $\delta\leq\frac{1}{CL}$. Details are in Section 7.

Notable Extensions

Our Step 1 through Step 4 in Section 5 in fact give rise to a general plan for proving the training convergence of any neural network (at least with respect to the ReLU activation). Thus, it is expected that it can be generalized to many other settings. Not only we can have different number of neurons each layer, our theorems can be extended at least in the following three major directions. In principle, each such proof may require a careful rewriting of the main body of this paper. We choose to sketch only the proof difference (in the appendix) in order to keep this paper short. If there is sufficient interest from the readers, we can consider adding the full proofs in the future revision of this paper.

From random initialization, with probability at least $1-e^{-\Omega(\log^{2}m)}$, gradient descent with appropriate learning rate satisfy the following.

as long as $m\geq\widetilde{\Omega}\big({\mathsf{poly}}(n,L,\delta^{-1})\cdot d\sigma^{-2}\big)$.

If $f$ is convex, then GD finds $\varepsilon$-error minimizer in

as long as $m\geq\widetilde{\Omega}\big({\mathsf{poly}}(n,L,\delta^{-1})\cdot d\log\varepsilon^{-1}\big)$.

as long as $m\geq\widetilde{\Omega}\big({\mathsf{poly}}(n,L,\delta^{-1})\cdot d\varepsilon^{-1}\big)$.

If $f$ is cross-entropy for multi-label classification, then GD attains $100\%$ training accuracy in at most This is because attaining constant objective error $\varepsilon=1/4$ for the cross-entropy loss suffices to imply perfect training accuracy..

as long as $m\geq\widetilde{\Omega}\big({\mathsf{poly}}(n,L,\delta^{-1})\cdot d\big)$.

In Section 7, we derive network properties at random initialization.

In Section 8, we derive the stability theory against adversarial perturbation.

In Section 9, we gradient upper and lower bounds at random initialization.

Properties at Random Initialization

Lemma 7.1 is in fact trivial to prove if the allowed failure probability is instead $e^{-\Omega(m\varepsilon^{2}/L^{2})}$ (by applying concentration inequality layer by layer).

Before proving Lemma 7.1 we note a simple mathematical fact:

$|v_{i}|$ follows i.i.d. from the following distribution: with half probability $|v_{i}|=0$, and with the other half probability $|v_{i}|$ follows from folded Gaussian distributions $|\mathcal{N}(0,\frac{2\|h\|^{2}}{m})|$.

$\frac{m\|v\|^{2}}{2\|h\|^{2}}$ is in distribution identical to $\chi^{2}_{\omega}$ (chi-square distribution of order $\omega$) where $\omega$ follows from binomial distribution $\mathcal{B}(m,1/2)$.

Whenever $\omega\in[0.4m,0.6m]$, we can write

Subgaussian Tail. By standard tail bound for chi-square distribution, we know that

Since we only need to focus on $\omega\geq 0.4m$, this means

On the other hand, by Chernoff-Hoeffding bound, we also have

Concentration. Using martingale concentration on subgaussian variables (see for instance ), we have for $\varepsilon\in(0,1]$,

In other words, $\|h_{b-1}\|^{2}\in\big[1-\varepsilon,1+\varepsilon\big]$ with probability at least $1-O\big(e^{-\Omega(\varepsilon^{2}m/L)}\big)$. ∎

2 Intermediate Layers

Using exactly the same proof as Lemma 7.1, we have

with probability at least $1-e^{-\Omega(m/L)}$. As a result, if we fix a subset $M\subseteq[m]$ of cardinality $|M|\leq O(m/L)$, taking $\varepsilon$-net, we know that with probability at least $e^{-\Omega(m/L)}$, it satisfies

The proof of Lemma lem:done-4b is the same as Lemma lem:done-4a, except to take $\varepsilon$-net over all $O\big(\frac{m}{L\log m}\big)$-sparse vectors $u$ and then applying union bound.

Back to the case when $v$ is an arbitrary vector, we can partition $[m]$ into $N$ index sets $[m]=M_{1}\cup M_{2}\cup\cdots\cup M_{N}$ and write $v=v_{1}+v_{2}+\cdots+v_{N}$, where $N=O(L)$ and each $v_{j}$ is non-zero only in $M_{j}$. By applying (7.4) for $N$ times and using triangle inequality, we have

Finally, taking $\varepsilon$-net over all possible vectors $u,v$ that are $s$ sparse, we have the desired result.

3 Backward Propagation

Suppose $m\geq\Omega(nL\log(nL))$. If $s\geq\Omega\big(\frac{d}{\log m}\big)$ and $s\leq O\big(\frac{m}{L\log m}\big)$, then with probability at least $1-e^{-\Omega(s\log m)}$, for all $i\in[n]$, $a=1,2,\dots,L+1$,

With probability at least $\geq 1-e^{-\Omega(m/L)}$, for all $i\in[n],1\leq a\leq L$,

4 δ\delta-Separateness

Let $m\geq\Omega\big(\frac{L\log(nL)}{\delta^{6}}\big)$. There exists some constant $C>1$ so that, if $\delta\leq\frac{1}{CL}$, $\|x_{1}\|=\cdots=\|x_{n}\|=1$ and $\|x_{i}-x_{j}\|\geq\delta$ for every pair $i,j\in[n]$, then with probability at least $1-e^{-\Omega(\delta^{6}m/L)}$, we have:

The following mathematical fact is needed in the proof of Lemma 7.5. Its proof is by carefully integrating the PDF of Gaussian distribution.

Suppose $a<\frac{3}{4}$. If so, then with probability at least $0.3$ we have $g_{1}>1$. If this happens, then with probability at least $1/2$ we have $g_{2}<0$. If both happens, we have

Therefore, we have if $a<\frac{3}{4}$ then the expectation is at least $0.03$. For similar reason, if $a>\frac{5}{4}$ we also have the expectation is at least $0.03$. In the remainder of the proof, we assume $\alpha\in\big[\frac{3}{4},\frac{5}{4}\big]$.

It is easy to see that, as long as $\delta\leq\alpha$, we always have $\frac{(\alpha+k)\delta^{2k+1}}{(2k+1)\alpha^{2k+1}}\geq\frac{(\alpha+k+1)\delta^{2k+3}}{(2k+3)\alpha^{2k+3}}$. Therefore

Stability against Adversarial Weight Perturbations

For each term in $(\diamondsuit)$, we have

If we re-scale $x$ by $\frac{1}{\|h^{(0)}_{a-1}\|}$ (which is a constant in $[0.75,1.5]$), we can apply Claim 8.3 (with parameter choices in Corollary 8.4) on $x$ and this tells us, with probability at least $1-e^{-\Omega(m\omega^{2/3}L)}$:

using (8.1) and Claim 8.5 (with $s=O(m\omega^{2/3}L)$), we have with probability at least $1-e^{-\Omega(s\log m)}$, one can write $y=y_{1}+y_{2}$ for

And therefore by triangle inequality we can write

where $\|\overrightarrow{\mathsf{err}}_{2}\|\leq O\big(L\cdot\omega L^{3/2}\cdot L^{1/2}\omega^{1/3}\log m\big)=O\big(\omega^{4/3}L^{3}\log m\big)$ and $\|\overrightarrow{\mathsf{err}}_{3}\|_{\infty}\leq O\Big(L\cdot\omega L^{3/2}\cdot\frac{\sqrt{\log m}}{\sqrt{m}}\Big)$. Together with the upper bound on $\overrightarrow{\mathsf{err}}_{1}$, we have

Lemma lem:chap2:forwardb is due to (8.1),

In particular, if $\omega L^{3/2}\leq O(1)$, then with probability at least $1-e^{-\Omega(m\omega^{2/3}L)}$, for every $g^{\prime}=g^{\prime}_{1}+g^{\prime}_{2}$ with $\|g^{\prime}_{1}\|\leq O(\omega L^{3/2})$ and $\|g^{\prime}_{2}\|_{\infty}\leq O\big(\frac{\omega^{2/3}L}{m^{1/2}}\big)$, it satisfies

Let $\xi\leq\frac{1}{2\sqrt{m}}$ be a parameter to be chosen later. We shall make sure that $\|g^{\prime}_{2}\|_{\infty}\leq\xi/2$.

We denote by $S_{1}\subseteq[m]$ the index sets where $j$ satisfies $|(g^{(0)})_{j}|\leq\xi$. Since we know $(g^{(0)})_{j}\sim\mathcal{N}(0,2/m)$, we have $\operatornamewithlimits{\mathbf{Pr}}[|(g^{(0)})_{j}|\leq\xi]\leq O\left(\xi\sqrt{m}\right)$ for each $j\in[m]$. Using Chernoff bound for all $j\in[m]$, we have with probability at least $1-e^{-\Omega(m^{3/2}\xi)}$,

We denote by $S_{2}\subseteq[m]\setminus S_{1}$ the index set of all $j\in[m]\setminus S_{1}$ where $x_{j}\neq 0$. Using (8.2), we have for each $j\in S_{2}$:

Now, for each $j\in S_{2}$ where $x_{j}\neq 0$, we know that the signs of $(g^{(0)}+g^{\prime}_{1}+g^{\prime}_{2})_{j}$ and $(g^{(0)})_{j}$ are opposite. Therefore, we must have

From above, we have $\|x\|_{0}\leq|S_{1}|+|S_{2}|\leq O\big(\xi m^{3/2}+\frac{(\delta_{2})^{2}}{\xi^{2}}\big)$ and $\|x\|^{2}\leq O\big((\delta_{2})^{2}+\xi^{3}m^{3/2}\big)$. Choosing $\xi=\max\{2\delta_{\infty},\Theta(\frac{(\delta_{2})^{2/3}}{m^{1/2}})\}$ for the former, and choosing $\xi=2\delta_{\infty}$ for the latter, we have the desired result. ∎

As long as $\beta^{2}p^{2}m\geq\beta^{2}m\geq\Omega(\log m)$, we know that if $|y_{i}|\geq\beta p$ occurs for $q/p^{2}$ indices $i$ out of $[m]$, this cannot happen with probability more than

Finally, by applying union bound over $p=1,2,4,8,16,\dots$ we have with probability $\geq 1-e^{-\Omega(\beta^{2}qm)}\cdot\log q$,

In other words, vector $y$ can be written as $y=y_{1}+y_{2}$ where $\|y_{2}\|_{\infty}\leq\beta$ and $\|y_{1}\|^{2}\leq O(q\beta^{2}\log q)$.

Finally, we want to take $\varepsilon$-net over all $s$-sparse inputs $x$. This requires $\beta^{2}qm\geq\Omega(s\log m)$, so we can choose $q=\Theta\big(\frac{s\log m}{m\beta^{2}}\big)=\Theta(s)$. ∎

2 Intermediate Layers

Therefore, it suffices for us to bound the spectral norm of the following four types of matrices:

Moreover, from Lemma lem:chap2:intermediatea, we know the following three types of matrices

3 Backward

Gradient Bound at Random Initialization

Our main lemma of this section is the following.

2 Proof of Lemma 9.3: Lower Bound

Let $i^{*}=\operatornamewithlimits{arg\,max}_{i\in[n]}\{\|{\mathsf{v}}_{i}\|\}$. Recall

We first make two technical claims, and the proof of the first one can be found in Section 9.2.1.

Given set $N_{2}\subset[m]$ and ${\vec{{\mathsf{v}}}}$, we have

Combining Claim 9.4 and Claim 9.5, we can obtain a set $N\subseteq[m]$ satisfying

Let us denote this event of $\widehat{g}_{2}$ as $\mathfrak{E}_{k}$. Conditioning on $\mathfrak{E}_{k}$ happens, recalling $\|h_{i,L-1}\|\in[0.9,1.1]$ from Lemma 7.1,

For every $i\in[n]\setminus\{i^{*}\}$, we have

Using the independence of $(\widehat{g}_{2})_{k}$ with respect to different $k\in N$, we can apply Chernoff bound and derive:

Finally, using and $|N|\geq\frac{\delta}{100n}m$, we have

We finish the upper bound proof of Lemma 9.3. $\blacksquare$

For each $k\in N_{1}$ and $i\in[n]\setminus\{i^{*}\}$, we can write

Combining the two bounds we finish the proof. ∎

Suppose $x\sim\mathcal{N}(0,\sigma^{2})$ is a Gaussian random variable. For any $t\in(0,\sigma)$ we have

Similarly, if $x\sim\mathcal{N}(\mu,\sigma^{2})$, for any $t\in(0,\sigma)$, we have

Theorem 3: Gradient Bound at After Perturbation

In this section we prove our main theorem on the gradient upper and lower bounds.

By Lemma 7.1 and Lemma lem:chap2:forwardc, we have

Theorem 4: Objective Semi-Smoothness

We introduce the following notations before we go to proofs.

Above, ① is by the definition of $F(\cdot)$; ② is by (11.2); ③ is by the definition of $\nabla F(\cdot)$ (see Fact 2.6 for an explicit form of the gradient).

Putting (11.4), (11.5) and (11.6) back to (11.3), and using triangle inequality, we have the desired result. ∎

We first present a simple proposition about the ReLU function.

We verify coordinate by coordinate for each $k\in[m]$.

Theorem 1: Convergence Rate of GD

In other words, the training loss drops to $\varepsilon$ in a linear convergence speed.

Let us assume for every $t=0,1,\dots,T-1$, the following holds

We shall prove the convergence of GD assuming (12.1) holds, so that previous statements such as Theorem 4 and Theorem 3 can be applied. At the end of the proof, we shall verify that (12.1) is satisfied.

Most of the polynomial dependency in $n,L,\delta^{-1}$ come from the non-smoothness of the ReLU activation; if one instead studies smooth activations, their power can be significantly reduced. For instance, for smooth activation functions, one does not need the semi-smoothness Theorem 4.

We have not tried to tighten the polynomial dependency on $n,L,\delta^{-1}$. We are aware of many ways to improve the constant in the exponents at the expense of complicating the proofs. Since the main focus of this paper is to derive the first polynomial running time, we do not include such improvements.

where the last step follows by our choice of $T$. ∎

Theorem 2: Convergence Rate of SGD

Then, it satisfies with probability at least $1-e^{-\Omega(\log^{2}m)}$ over the randomness of $S_{1},\dots,S_{T}$:

The proof of Theorem 2 is the same as Theorem 1 plus the careful use of martingale concentration.

Using similar argument as the proof of Theorem 1, we have with at least $1-e^{-\Omega(\log^{2}m)}$ probability

Let us assume for every $t=0,1,\dots,T-1$, the following holds

We shall prove the convergence of SGD assuming (13.1) holds, so that previous statements such as Theorem 4 and Theorem 3 can be applied. At the end of the proof, we shall verify that (13.1) is satisfied throughout the SGD with high probability.

Most of the polynomial dependency in $n,L,\delta^{-1}$ come from the non-smoothness of the ReLU activation; if one instead studies smooth activations, their power can be significantly reduced. For instance, for smooth activation functions, one does not need the semi-smoothness Theorem 4.

We have not tried to tighten the polynomial dependency on $n,L,\delta^{-1}$. We are aware of many ways to improve the constant in the exponents at the expense of complicating the proofs. Since the main focus of this paper is to derive the first polynomial running time, we do not include such improvements.

③ use gradient lower bound from Theorem 3 and our choice of $\eta$.

At the same time, we also have the following absolute value bound:

Above, ① uses Theorem 4 and Cauchy-Schwarz $\langle A,B\rangle\leq\|A\|_{F}\|B\|_{F}$, and ② uses Theorem 3 which give

By (one-sided) martingale concentration, we have with probability at least $1-e^{-\Omega(\log^{2}m)}$, for every $t=1,2,\dots,T$:

This implies for every $t=1,2,\dots,T$, we have

Above, in ① we have used $2a\sqrt{t}-b^{2}t=-(b\sqrt{t}-a/b)^{2}+a^{2}/b^{2}$; in ② we have used our choice of $\eta$; in ③ we have used $-(a\sqrt{t}-b)^{2}\leq-\mathds{1}[t\geq 2b^{2}/a^{2}]\cdot\frac{a^{2}t}{4}$; and in ④ we have used our choice of $\eta$ again. We can read two things from the above formula:

If $T\geq\Omega\big(\frac{L^{2}n^{7}}{b\delta^{2}}\log^{2}m\log\frac{n\log m}{\varepsilon}\big)$ then we have

Letting $T_{0}=\Omega\big(\frac{L^{2}n^{7}}{b\delta^{2}}\log^{2}m\big)$, we have

Theorem 5: Equivalence to Neural Tangent Kernel

We have the following theorem whose proof is subsumed by the proofs of Theorem 3 and 4. We prove it here for completeness’ sake.

This difference matrix is precisely (10.1) (by setting $n=1$ and ${\mathsf{v}}=e_{j}$). Using the bound (10.2) we have its Frobenius norm is at most $O\left(\sqrt{m\log m/d}\cdot\omega^{1/3}L^{2}\right)$. On the other hand, one can calculate for every $k\in[m]$,

This statement can be derived from (11.3), (11.5) and (11.6). For completeness’ sake, below we provide a direct proof without invoking them. We first calculate that

Putting (14.1) and (14.2) together finishes the proof.

Appendix A Extension to Other Loss Functions

All the results in Section 7, 8 and 9 remain unchanged. Section 10 also remains unchanged, except we need to restate Theorem 3 with respect to this new notation:

and the rest of the proof remains unchanged.

As for the final convergence theorem of gradient descent, we can replace (12.2) with

If the loss is convex and its minimizer has bounded norm, meaning there exists $z^{*}$ so that $f(z^{*};y)=\min_{z}f(z;y)$ and $\|z-z^{*}\|\leq D$. Then, by convexity

If the loss is cross entropy $f(z;y)=\frac{e^{z_{y}}}{\sum_{i=1}^{d}e^{z_{i}}}$ for classification, then $\|\nabla f(z;y)\|<1/4$ implies perfect classification. Recall $\frac{\partial f(z;y)}{z_{y}}=p_{y}(1-p_{y})$ where $p_{j}=\frac{e^{z_{j}}}{\sum_{i=1}^{d}e^{z_{i}}}$. If $p_{y}>1/2$, then $z$ correctly predicts the target label $y$ because $p_{y}>p_{j}$ for $j\neq z$. Thus, we have 100% training accuracy in $T=O\big(\frac{n^{6}L^{2}}{\delta^{2}}\big)$ iterations. If suffices to choose $m\geq\widetilde{\Omega}\big({\mathsf{poly}}(n,L,\delta^{-1})\cdot d\big)$

Appendix B Extension to Convolutional Neural Networks

We assume that $(\mathcal{Q}_{1},\dots,\mathcal{Q}_{\mathfrak{d}})$ give rise to a $q$-regular bipartite graph: each $\mathcal{Q}_{j}$ has exactly $q$ entries and each $k\in[{\mathfrak{d}}]$ appears in exactly $q$ different sets $\mathcal{Q}_{j}$.

(In vision tasks, if $3\times 3$ kernels are used then $|\mathcal{Q}_{j}|=9$. We ignore the padding issue for simplicity.)

If one is willing to loose polynomial factors in $L$ and ${\mathfrak{d}}$ in the final complexity, then changes to each of the lemmas of this paper is very little. We acknowledge the existence of more careful modifications to avoid loosing too many such factors, but do not present such result for the simplicity of this paper.

Changes to Section 8. The first main result is Lemma 8.2, and we discuss necessary changes here to make it work for CNN. The first change in the proof is to replace $2c_{1}L^{1.5}$ with $2c_{1}L^{2}$ due to the above additional factor from Lemma lem:done-4a. Next, call that the proof of Lemma 8.2 relied on Claim 8.3 and Claim 8.5:

and its proof is by re-scaling $x$ by $\frac{1}{\tau}$ and then applying the old proof (with dimension $m$ replaced with ${\mathfrak{d}}m$).

For Claim 8.5, it becomes $\|y_{1}\|\leq O\big(\sqrt{qs/m}\log m\big)\hskip 10.00002pt\text{and }\hskip 10.00002pt\|y_{2}\|_{\infty}\leq\frac{2\sqrt{\log m}}{\sqrt{qm}}\kern 5.0pt.$

After making all of these changes, we loose at most some polynomial factors in $L$ and ${\mathfrak{d}}$ for the new statement of Lemma 8.2:

Finally, the statements of Lemma 8.6 and Lemma 8.7 only loose polynomial factors in $L$ and ${\mathfrak{d}}$.

Final Theorem. Since Section 10 and 11 rely on previous sections, they do not need to be changed (besides some polynomial factor blowup in $L$ and ${\mathfrak{d}}$). Our final theorem becomes

Appendix C Extension to Residual Neural Networks

for any $L-1\geq a\geq b\geq 1$ with our choice of $\tau$.

Fact 7.2 says each coordinate of $h_{0}$ follows i.i.d. from a distribution which is $0$ with half probability, and $|\mathcal{N}(0,\frac{2}{m})|$ with half probability. Therefore, with high probability, at least $m/4$ of the coordinates $k\in[m]$ will satisfy $|(h_{0})_{k}|\geq\frac{0.6}{\sqrt{m}}$. Denote this set as $M_{0}\subseteq[m]$.

In the input layer, since $\|x_{i}-x_{j}\|\geq\delta$, the same Claim 7.6 shows that, with high probability, there are at least $\frac{3}{4}m$ coordinates $k\in[m]$ with $|(h_{i,0}-h_{j,0})_{k}|\geq\frac{\delta}{10\sqrt{m}}$. At the same time, at least $\frac{3}{4}m$ coordinates $k\in[m]$ will satisfy $(h_{i,0})_{k}\geq\frac{1}{10\sqrt{m}}$ and $(h_{j,0})_{k}\geq\frac{1}{10\sqrt{m}}$. Denote $M_{0}\subseteq[m]$ as the set of coordinates $k$ satisfying both properties. We have $|M_{0}|\geq\frac{m}{2}$ and $\sum_{k\in M_{0}}|(h_{i,0}-h_{j,0})_{k}|\geq\frac{\delta}{20}\sqrt{m}$.

Changes to Section 9. The proofs of this section require only notational changes.

Final Theorem. Since Section 10 and 11 rely on previous sections, they do not need to be changed (besides improving polynomial factors in $L$). Our final theorem becomes

References