Gradient Descent Finds Global Minima of Deep Neural Networks

Introduction

One of the mysteries in deep learning is randomly initialized first-order methods like gradient descent achieve zero training loss, even if the labels are arbitrary (Zhang et al., 2016). Over-parameterization is widely believed to be the main reason for this phenomenon as only if the neural network has a sufficiently large capacity, it is possible for this neural network to fit all the training data. For example, Lu et al. (2017) proved that except for a measure zero set, all functions cannot be approximated by ReLU networks with a width less than the input dimension. In practice, many neural network architectures are highly over-parameterized. For example, Wide Residual Networks have 100x parameters than the number of training data (Zagoruyko & Komodakis, 2016).

The second mysterious phenomenon in training deep neural networks is “deeper networks are harder to train.” To solve this problem, He et al. (2016) proposed the deep residual network (ResNet) architecture which enables randomly initialized first order method to train neural networks with an order of magnitude more layers. Theoretically, Hardt & Ma (2016) showed that residual links in linear networks prevent gradient vanishing in a large neighborhood of zero, but for neural networks with non-linear activations, the advantages of using residual connections are not well understood.

In this paper, we demystify these two mysterious phenomena. We consider the setting where there are $n$ data points, and the neural network has $H$ layers with width $m$. We focus on the least-squares loss and assume the activation function is Lipschitz and smooth. This assumption holds for many activation functions including the soft-plus and sigmoid. Our contributions are summarized below.

Our proof builds on two ideas from previous work on gradient descent for two-layer neural networks. First, we use the observation by (Li & Liang, 2018) that if the neural network is over-parameterized, every weight matrix is close to its initialization. Second, following (Du et al., 2018b), we analyze the dynamics of the predictions whose convergence is determined by the least eigenvalue of the Gram matrix induced by the neural network architecture and to lower bound the least eigenvalue, it is sufficient to bound the distance of each weight matrix from its initialization.

Different from these two works, in analyzing deep neural networks, we need to exploit more structural properties of deep neural networks and develop new techniques for analyzing both the initialization and gradient descent dynamics. In Section 4 we give an overview of our proof technique.

This paper is organized as follows. In Section 2, we discuss related works. In Section 3, we formally state the problem setup. In Section 4, we present our main analysis techniques. In Section 5, we give a warm-up result for the deep fully-connected neural network. In Section 6, we give our main result for the ResNet. In Section 7, we give our main result for the convolutional ResNet. We conclude in Section 8 and defer all proofs to the appendix.

Related Works

Recently, many works try to study the optimization problem in deep learning. Since optimizing a neural network is a non-convex problem, one approach is first to develop a general theory for a class of non-convex problems which satisfy desired geometric properties and then identify that the neural network optimization problem belongs to this class. One promising candidate class is the set of functions that satisfy: a) all local minima are global and b) there exists a negative curvature for every saddle point. For this function class, researchers have shown (perturbed) gradient descent (Jin et al., 2017; Ge et al., 2015; Lee et al., 2016; Du et al., 2017a) can find a global minimum. Many previous works thus try to study the optimization landscape of neural networks with different activation functions (Soudry & Hoffer, 2017; Safran & Shamir, 2018, 2016; Zhou & Liang, 2017; Freeman & Bruna, 2016; Hardt & Ma, 2016; Nguyen & Hein, 2017; Kawaguchi, 2016; Venturi et al., 2018; Soudry & Carmon, 2016; Du & Lee, 2018; Soltanolkotabi et al., 2018; Haeffele & Vidal, 2015). However, even for a three-layer linear network, there exists a saddle point that does not have a negative curvature (Kawaguchi, 2016), so it is unclear whether this geometry-based approach can be used to obtain the global convergence guarantee of first-order methods.

Another way to attack this problem is to study the dynamics of a specific algorithm for a specific neural network architecture. Our paper also belongs to this category. Many previous works put assumptions on the input distribution and assume the label is generated according to a planted neural network. Based on these assumptions, one can obtain global convergence of gradient descent for some shallow neural networks (Tian, 2017; Soltanolkotabi, 2017; Brutzkus & Globerson, 2017; Du et al., 2018a; Li & Yuan, 2017; Du et al., 2017b). Some local convergence results have also been proved (Zhong et al., 2017a, b; Zhang et al., 2018). In comparison, our paper does not try to recover the underlying neural network. Instead, we focus on minimizing the training loss and rigorously prove that randomly initialized gradient descent can achieve zero training loss.

The most related papers are (Li & Liang, 2018; Du et al., 2018b) who observed that when training an over-parametrized two-layer fully-connected neural network, the weights do not change a large amount, which we also use to show the stability of the Gram matrix. They used this observation to obtain the convergence rate of gradient descent on a two-layer over-parameterized neural network for the cross-entropy and least-squares loss. More recently, Allen-Zhu et al. (2018b) generalized ideas from (Li & Liang, 2018) to derive convergence rates of training recurrent neural networks.

Our work extends these previous results in several ways: a) we consider deep networks, b) we generalize to ResNet architectures, and c) we generalize to convolutional networks. To improve the width dependence $m$ on sample size $n$, we utilize a smooth activation (e.g. smooth ReLU). For example, our results specialized to depth $H=1$ improve upon (Du et al., 2018b) in the required amount of overparametrization from $m=\Omega\left(n^{6}\right)$ to $m=\Omega\left(n^{4}\right)$. See Theorem 5.1 for the precise statement.

Chizat & Bach (2018b) brought to our attention the paper of Jacot et al. (2018) which proved a similar weight stability phenomenon for deep networks, but only in the asymptotic setting of infinite-width networks and gradient flow run for a finite time. Jacot et al. (2018) do not establish the convergence of gradient flow to a global minimizer. In lieu of their results, our work can be viewed as a generalization of their result to: a) finite width, b) gradient descent as opposed to gradient flow, and c) convergence to a global minimizer.

Mei et al. (2018); Chizat & Bach (2018a); Sirignano & Spiliopoulos (2018); Rotskoff & Vanden-Eijnden (2018); Wei et al. (2018) used optimal transport theory to analyze gradient descent on over-parameterized models. However, their results are limited to two-layer neural networks and may require an exponential amount of over-parametrization.

Daniely (2017) developed the connection between deep neural networks with kernel methods and showed stochastic gradient descent can learn a function that is competitive with the best function in the conjugate kernel space of the network. Andoni et al. (2014) showed that gradient descent can learn networks that are competitive with polynomial classifiers. However, these results do not imply gradient descent can find a global minimum for the empirical loss minimization problem. Our analysis of the Gram matrices at random initialization is closely related to prior work on the analysis of infinite-width networks as Gaussian Processes (Raghu et al., 2016; Matthews et al., 2018; Lee et al., 2017; Schoenholz et al., 2016). Since we require the initialization analysis for three distinct architectures (ResNet, feed-forward, and convolutional ResNet), we re-derive many of these prior results in a unified fashion in Appendix E.

Finally, in concurrent work, Allen-Zhu et al. (2018c) also analyze gradient descent on deep neural networks. The primary difference between the two papers is that we analyze general smooth activations, and Allen-Zhu et al. (2018c) develop specific analysis for ReLU activation. The two papers also differ significantly on their data assumptions. We wish to emphasize a fair comparison is not possible due to the difference in setting and data assumptions. We view the two papers as complementary since they address different neural net architectures.

For ResNet, the primary focus of this manuscript, the required width per layer for Allen-Zhu et al. (2018c) is $m\gtrsim n^{30}H^{30}\log^{2}\frac{1}{\epsilon}$ and for this paper’s Theorem 6.1 is $m\gtrsim n^{4}H^{2}$.In all comparisons, we ignore the polynomial dependency on data-dependent parameters which only depends on the input data and the activation function. The two papers use different measures and are not directly comparable. Our paper requires a width $m$ that does not depend on the desired accuracy $\epsilon$. As a consequence, Theorem 6.1 guarantees the convergence of gradient descent to a global minimizer. The iteration complexity of Allen-Zhu et al. (2018c) is $T\gtrsim n^{6}H^{2}\log\frac{1}{\epsilon}$ and of Theorem 6.1 is $T\gtrsim n^{2}\log\frac{1}{\epsilon}$.

For fully-connected networks, Allen-Zhu et al. (2018c) requires width $m\gtrsim n^{30}H^{30}\log^{2}\frac{1}{\epsilon}$ and iteration complexity $T\gtrsim n^{6}H^{2}\log\frac{1}{\epsilon}$. Theorem 5.1 requires width $m\gtrsim n^{4}2^{O(H)}$ and iteration complexity $T\gtrsim n^{2}2^{O(H)}\log\frac{1}{\epsilon}$. The primary difference is for very deep fully-connected networks, Allen-Zhu et al. (2018c) has milder dependence on $H$, but worse dependence on $n$. Commonly used fully-connected networks such as VGG are not extremely deep ($H=16$), yet the dataset size such as ImageNet ($n\sim 10^{6}$) is very large.

In a second concurrent work, Zou et al. (2018) also analyzed the convergence of gradient descent on fully-connected networks with ReLU activation. The emphasis is on different loss functions (e.g. hinge loss), so the results are not directly comparable. Both Zou et al. (2018) and Allen-Zhu et al. (2018c) train a subset of the layers, instead of all the layers as in this work, but also analyze stochastic gradient.

Preliminaries

We Let $[n]=\{1,2,\ldots,n\}$. We use $N(\mathbf{0},\mathbf{I})$ to denote the standard Gaussian distribution. For a matrix $\mathbf{A}$, we use $\mathbf{A}_{ij}$ to denote its $(i,j)$-th entry. We will also use $\mathbf{A}_{i,:}$ to denote the $i$-th row vector of $\mathbf{A}$ and define $\mathbf{A}_{i,j:k}=(\mathbf{A}_{i,j},\mathbf{A}_{i,j+1},\cdots,\mathbf{A}_{i,k})$ as part of the vector. Similarly $\mathbf{A}_{:,i}$ is the $i$-th column vector and $\mathbf{A}_{j:k,i}$ is a part of $i$-th column vector. For a vector $\mathbf{v}$, we use $\left\|\mathbf{v}\right\|_{2}$ to denote the Euclidean norm. For a matrix $\mathbf{A}$ we use $\left\|\mathbf{A}\right\|_{F}$ to denote the Frobenius norm and $\left\|\mathbf{A}\right\|_{2}$ to denote the operator norm. If a matrix $\mathbf{A}$ is positive semi-definite, we use $\lambda_{\min}(\mathbf{A})$ to denote its smallest eigenvalue. We use $\langle\cdot,\cdot\rangle$ to denote the standard Euclidean inner product between two vectors or matrices. We let $O(\cdot)$ and $\Omega\left(\cdot\right)$ denote standard Big-O and Big-Omega notations, only hiding constants. In this paper we will use $C$ and $c$ to denote constants. The specific value can be different from line to line.

2 Activation Function

We use $\sigma\left(\cdot\right)$ to denote the activation function. In this paper we impose some technical conditions on the activation function. The guiding example is softplus: $\sigma\left(z\right)=\log(1+\exp(z))$.

These two conditions will be used to show the stability of the training process. Note for softplus both Lipschitz constant and smoothness constant are $1$. In this paper, we view all activation function related parameters as constants.

$\sigma\left(\cdot\right)$ is analytic and is not a polynomial function.

This assumption is used to guarantee the positive-definiteness of certain Gram matrices which we will define later. Softplus function satisfies this assumption by definition.

3 Problem Setup

In this paper, we focus on the empirical risk minimization problem with the quadratic loss function

where $\left\{\mathbf{x}_{i}\right\}_{i=1}^{n}$ are the training inputs, $\left\{y_{i}\right\}_{i=1}^{n}$ are the labels, $\mathbf{\theta}$ is the parameter we optimize over and $f$ is the prediction function, which in our case is a neural network. We consider the following architectures.

ResNetWe will refer to this architecture as ResNet, although this differs by the standard ResNet architecture since the skip-connections at every layer, instead of every two layers. This architecture was previously studied in (Hardt & Ma, 2016). We study this architecture for the ease of presentation and analysis. It is not hard to generalize our analysis to architectures with skip-connections are every two or more layers. : We use the same notations as the multilayer fully connected neural networks. We define the prediction recursively.

where $0<c_{res}<1$ is a small constant. Note here we use a $\frac{c_{res}}{H\sqrt{m}}$ scaling. This scaling plays an important role in guaranteeing the width per layer only needs to scale polynomially with $H$. In practice, the small scaling is enforced by a small initialization of the residual connection (Hardt & Ma, 2016; Zhang et al., 2019), which obtains state-of-the-art performance for deep residual networks. We choose to use an explicit scaling, instead of altering the initialization scheme for notational convenience.

Convolutional ResNet: Lastly, we consider the convolutional ResNet architecture. Again we define the prediction function in a recursive way.

where we let $\mathbf{x}^{(h-1)}_{:,0}=\mathbf{x}^{(h-1)}_{:,p+1}=\mathbf{0}$, i.e., zero-padding. Note this operator has the property

Note here we use the similar scaling $O(\frac{1}{H\sqrt{m}})$ as ResNet.

To learn the deep neural network, we consider the randomly initialized gradient descent algorithm to find the global minimizer of the empirical loss (1). Specifically, we use the following random initialization scheme. For every level $h\in[H]$, each entry is sampled from a standard Gaussian distribution, $\mathbf{W}_{ij}^{(h)}\sim N(0,1)$ and each entry of the output layer $\mathbf{a}$ is also sampled from $N(0,1)$. In this paper, we train all layers by gradient descent, for $k=1,2,\ldots,$ and $h\in[H]$

Technique Overview

In this section, we describe our main idea of proving the global convergence of gradient descent. Our proof technique is inspired by Du et al. (2018b) who proposed to study the dynamics of differences between labels and predictions. Here the individual prediction at the $k$-th iteration is

For this linear dynamics, using standard analysis technique for power method, one can show $\left\{\mathbf{y}-\mathbf{u}(k)\right\}_{k=0}^{\infty}$ converges to $\mathbf{0}$ where the rate is determined by the least eigenvalue of $\mathbf{H}^{\infty}$ and the step size $\eta$.

We leverage this insight to our deep neural network setting. Again we consider the sequence $\{\mathbf{y}-\mathbf{u}(k)\}_{k=0}^{\infty}$, which admits the dynamics

While following the similar high-level analysis framework proposed by Du et al. (2018b), analyzing the convergence of gradient descent for deep neural network is significantly more involved and requires new technical tools. To show $\mathbf{G}^{(H)}(k)$ is close to $\mathbf{K}^{(H)}$, we have two steps. First, we show in the initialization phase $\mathbf{G}^{(H)}(0)$ is close to $\mathbf{K}^{(H)}$. Second, we show during training $\mathbf{G}^{(H)}(k)$ is close to $\mathbf{G}^{(H)}(0)$ for $k=1,2,\ldots$. Below we give overviews of these two steps.

Unlike (Du et al., 2018b) in which they showed $\mathbf{H}(0)$ is close to $\mathbf{H}^{\infty}$ via a simple concentration inequality, showing $\mathbf{G}^{(H)}(0)$ is close to $\mathbf{K}^{(H)}$ requires more subtle calculations. First, as will be clear in the following sections, $\mathbf{K}^{(H)}$ is a recursively defined matrix. Therefore, we need to analyze how the perturbation (due to randomness of initialization and finite $m$) from lower layers propagates to the $H$-th layer. Second, this perturbation propagation involves non-linear operations due to the activation function. To quantitatively characterize this perturbation propagation dynamics, we use induction and leverage techniques from Malliavin calculus (Malliavin, 1995). We derive a general framework that allows us to analyze the initialization behavior for the fully-connected neural network, ResNet, convolutional ResNet and other potential neural network architectures in a unified way.

One important finding in our analysis is that ResNet architecture makes the “perturbation propagation” more stable. The high level intuition is the following. For fully connected neural network, suppose we have some perturbation $\left\|\mathbf{G}^{(1)}(0)-\mathbf{K}^{(1)}\right\|_{2}\leq\mathcal{E}_{1}$ in the first layer. This perturbation propagates to the $H$-th layer admits the form

Therefore, we need to have $\mathcal{E}_{1}\leq\frac{1}{2^{O(H)}}$ and this makes $m$ have exponential dependency on $H$.We not mean to imply that fully-connected networks necessarily depend exponentially on $H$, but simply to illustrate in our analysis why the exponential dependence arises. For specific activations such as ReLU and careful initialization schemes, this exponential dependence may be avoided.

On the other hand, for ResNet the perturbation propagation admits the form

Therefore we do not have the exponential explosion problem for ResNet. We refer readers to Section E for details.

Analysis of Perturbation of During Training

The next step is to show $\mathbf{G}^{(H)}(k)$ is close to $\mathbf{G}^{(H)}(0)$ for $k=0,1,\ldots$. Note $\mathbf{G}^{(H)}$ depends on weight matrices from all layers, so to establish that $\mathbf{G}^{(H)}(k)$ is close to $\mathbf{G}^{(H)}(0)$, we need to show $\mathbf{W}^{(h)}(k)-\mathbf{W}^{(h)}(0)$ is small for all $h\in[H]$ and $\mathbf{a}(k)-\mathbf{a}(0)$ is small.

In the two-layer neural network setting (Du et al., 2018b), they are able to show every weight vector of the first layer is close to its initialization, i.e., $\left\|\mathbf{W}^{(1)}(k)-\mathbf{W}^{(1)}(0)\right\|_{2,\infty}$ is small for $k=0,1,\ldots$. While establishing this condition for two-layer neural network is not hard, this condition may not hold for multi-layer neural networks. In this paper, we show instead, the averaged Frobenius norm

Similar to the analysis in the initialization, showing Equation (6) is small is highly involved because again, we need to analyze how the perturbation propagates. We develop a unified proof strategy for the fully-connected neural network, ResNet and convolutional ResNet. Our analysis in this step again sheds light on the benefit of using ResNet architecture for training. The high-level intuition is similar to Equation (5). See Section B, C, and D for details.

Warm Up: Convergence Result of GD for Deep Fully-connected Neural Networks

In this section, as a warm up, we show gradient descent with a constant positive step size converges to the global minimum at a linear rate. As we discussed in Section 4, the convergence rate depends on least eigenvalue of the Gram matrix $\mathbf{K}^{(H)}$.

The Gram matrix $\mathbf{K}^{(H)}$ is recursively defined as follows, for $(i,j)\in[n]\times[n]$, and $h=1,\ldots,H-1$

The derivation of this Gram matrix is deferred to Section E. The convergence rate and the amount of over-parameterization depends on the least eigenvalue of this Gram matrix. In Section F.1 we show as long as the input training data is not degenerate, then $\lambda_{\min}\left(\mathbf{K}^{(H)}\right)$ is strictly positive. We remark that if $H=1$, then $\mathbf{K}^{(H)}$ is the same the Gram matrix defined in (Du et al., 2018b).

Now we are ready to state our main convergence result of gradient descent for deep fully-connected neural networks.

Assume for all $i\in[n]$, $\left\|\mathbf{x}_{i}\right\|_{2}=1$, $\left|y_{i}\right|=O(1)$ and the number of hidden nodes per layer

where $\mathbf{K}^{(H)}$ is defined in Equation (7). If we set the step size

then with probability at least $1-\delta$ over the random initialization the loss, for $k=1,2,\ldots$, the loss at each iteration satisfies

Note the requirement of $m$ has three terms. The first term is used to show the Gram matrix is stable during training. The second term is used to guarantee the output in each layer is approximately normalized at the initialization phase. The third term is used to show the perturbation of Gram matrix at the initialization phase is small. See Section B for proofs.

The convergence rate depends step size $\eta$ and $\lambda_{\min}\left(\mathbf{K}^{(H)}\right)$, similar to (Du et al., 2018b). Here we require $\eta=O\left(\frac{\lambda_{\min}\left(\mathbf{K}^{(H)}\right)}{n^{2}2^{O(H)}}\right)$. When $H=1$, this requirement is the same as the one used in (Du et al., 2018b). However, for deep fully-connected neural network, we require $\eta$ to be exponentially small in terms of number of layers. The reason is similar to that we require $m$ to be exponentially large. Again, this will be improved in the next section.

Convergence Result of GD for ResNet

In this section we consider the convergence of gradient descent for training a ResNet. We will focus on how much over-parameterization is needed to ensure the global convergence of gradient descent and compare it with fully-connected neural networks. Again we first define the key Gram matrix whose least eigenvalue will determine the convergence rate.

The Gram matrix $\mathbf{K}^{(H)}$ is recursively defined as follows, for $(i,j)\in[n]\times[n]$ and $h=2,\ldots,H-1$:

Comparing $\mathbf{K}^{(H)}$ of the ResNet and the one of the fully-connect neural network, the definition of $\mathbf{K}^{(H)}$ also depends on a series of $\{\mathbf{b}^{(h)}\}_{h=1}^{H-1}$. This dependency is comes from the skip connection block in the ResNet architecture. See Section E. In Section F.2, we show as long as the input training data is not degenerate, then $\lambda_{\min}\left(\mathbf{K}^{(H)}\right)$ is strictly positive. Furthermore, $\lambda_{\min}\left(\mathbf{K}^{(H)}\right)$ does not depend inversely exponentially in $H$.

Now we are ready to state our main theorem for ResNet.

Assume for all $i\in[n]$, $\left\|\mathbf{x}_{i}\right\|_{2}=1$, $\left|y_{i}\right|=O(1)$ and the number of hidden nodes per layer

If we set the step size $\eta=O\left(\frac{\lambda_{\min}\left(\mathbf{K}^{(H)}\right)H^{2}}{n^{2}}\right)$, then with probability at least $1-\delta$ over the random initialization we have for $k=1,2,\ldots$

In sharp contrast to Theorem 5.1, this theorem is fully polynomial in the sense that both the number of neurons and the convergence rate is polynomially in $n$ and $H$. Note the amount of over-parameterization depends on $\lambda_{\min}\left(\mathbf{K}^{(H)}\right)$ which is the smallest eigenvalue of the $H$-th layer’s Gram matrix. The main reason that we do not have any exponential factor here is that the skip connection block makes the overall architecture more stable in both the initialization phase and the training phase.

Note the requirement on $m$ has $4$ terms. The first two terms are used to show the Gram matrix stable during training. The third term is used to guarantee the output in each layer is approximately normalized at the initialization phase. The fourth term is used to show bound the size of the perturbation of the Gram matrix at the initialization phase. See Section C for details.

Convergence Result of GD for Convolutional ResNet

In this section we generalize the convergence result of gradient descent for ResNet to convolutional ResNet. Again, we focus on how much over-parameterization is needed to ensure the global convergence of gradient descent. Similar to previous sections, we first define the $\mathbf{K}^{(H)}$ for this architecture.

The Gram matrix $\mathbf{K}^{(H)}$ is recursively defined as follows, for $(i,j)\in[n]\times[n]$, $(l,r)\in[p]\times[p]$ and $h=2,\ldots,H-1$,

where $\mathbf{u}$ and $\mathbf{v}$ are both random row vectors and D_{l}^{(h)}\triangleq\{s:\mathbf{x}^{(h-1)}_{:,s}\in\text{thel^{th}patch}\}.

Note here $\mathbf{K}_{ij}^{(h)}$ has dimension $p\times p$ for $h=0,\ldots,H-1$ and $\mathbf{K}_{ij,lr}$ denotes the $(l,r)$-th entry.

Now we state our main convergence theorem for the convolutional ResNet.

Assume for all $i\in[n]$, $\left\|\mathbf{x}_{i}\right\|_{F}=1$, $\left|y_{i}\right|=O(1)$ and the number of hidden nodes per layer

Conclusion

In this paper, we show that gradient descent on deep overparametrized networks can obtain zero training loss. Our proof builds on a careful analysis of the random initialization scheme and a perturbation analysis which shows that the Gram matrix is increasingly stable under overparametrization. These techniques allow us to show that every step of gradient descent decreases the loss at a geometric rate.

We list some directions for future research:

The current paper focuses on the training loss, but does not address the test loss. It would be an important problem to show that gradient descent can also find solutions of low test loss. In particular, existing work only demonstrate that gradient descent works under the same situations as kernel methods and random feature methods (Daniely, 2017; Li & Liang, 2018; Allen-Zhu et al., 2018a; Arora et al., 2019). To further investigate of generalization behavior, we believe some algorithm-dependent analyses may be useful (Hardt et al., 2016; Mou et al., 2018; Chen et al., 2018).

The width of the layers $m$ is polynomial in all the parameters for the ResNet architecture, but still very large. Realistic networks have number of parameters, not width, a large constant multiple of $n$. We consider improving the analysis to cover commonly utilized networks an important open problem.

The current analysis is for gradient descent, instead of stochastic gradient descent. We believe the analysis can be extended to stochastic gradient, while maintaining the linear convergence rate.

The convergence rate can be potentially improved if the minimum eigenvalue takes into account the contribution of all Gram matrices, but this would considerably complicate the initialization and perturbation analysis.

Acknowledgments

We thank Lijie Chen and Ruosong Wang for useful discussions. SSD acknowledges support from AFRL grant FA8750-17-2-0212 and DARPA D17AP00001. JDL acknowledges support of the ARO under MURI Award W911NF-11-1-0303. This is part of the collaboration between US DOD, UK MOD and UK Engineering and Physical Research Council (EPSRC) under the Multidisciplinary University Research Initiative. HL and LW acknowlege support from National Basic Research Program of China (973 Program) (grant no. 2015CB352502), NSFC (61573026) and BJNSF (L172037). Part of the work is done while SSD was visiting Simons Institute.

References

Appendix A Proof Sketch

Our proof is by induction. Our induction hypothesis is just the following convergence rate of empirical loss.

Note this condition implies the conclusions we want to prove. To prove Condition A.1, we consider one iteration on the loss function.

This equation shows if $2\left(\mathbf{y}-\mathbf{u}(k)\right)^{\top}\left(\mathbf{u}(k+1)-\mathbf{u}(k)\right)>\left\|\mathbf{u}(k+1)-\mathbf{u}(k)\right\|_{2}^{2}$, the loss decreases. Note both terms involves $\mathbf{u}(k+1)-\mathbf{u}(k)$, which we will carefully analyze. To simplify notations, we define

We look one coordinate of $\mathbf{u}(k+1)-\mathbf{u}(k)$.

Denote $\mathbf{I}_{1}(k)=\left(I_{1}^{1}(k),\ldots,I_{1}^{n}(k)\right)^{\top}$ and $\mathbf{I}_{2}(k)=\left(I_{2}^{1}(k),\ldots,I_{2}^{n}(k)\right)^{\top}$ and so $\mathbf{u}(k+1)-\mathbf{u}(k)=\mathbf{I}_{1}(k)+\mathbf{I}_{2}(k)$. We will show the $\mathbf{I}_{1}(k)$ term, which is proportional to $\eta$, drives the loss function to decrease and the $\mathbf{I}_{2}(k)$ term, which is a perturbation term but it is proportional to $\eta^{2}$ so it is small. We further unpack the $I_{1}^{i}(k)$ term,

According to Section 4, we will only look at $\mathbf{G}^{(H)}$ matrix which has the following form

Now we analyze $\mathbf{I}_{1}(k)$. We can write $\mathbf{I}_{1}$ in a more compact form with $\mathbf{G}(k)$.

Now recall the progress of loss function in Equation (12):

For the perturbation terms, through standard calculations, we can show both $-2\left(\mathbf{y}-\mathbf{u}(k)\right)^{\top}\mathbf{I}_{2}(k)$ and $\left\|\mathbf{u}(k+1)-\mathbf{u}(k)\right\|_{2}$ are proportional to $\eta^{2}\left\|\mathbf{y}-\mathbf{u}(k)\right\|_{2}^{2}$ so if we set $\eta$ sufficiently small, this term is smaller than $\eta\lambda_{\min}\left(\mathbf{G}^{(H)}(k)\right)\left\|\mathbf{y}-\mathbf{u}(k)\right\|_{2}^{2}$ and thus the loss function decreases with a linear rate.

Therefore, to prove the induction hypothesis, it suffices to prove $\lambda_{\min}\left(\mathbf{G}^{(H)}(k)\right)\geq\frac{\lambda_{0}}{2}$ for $k^{\prime}=0,\ldots,k$, where $\lambda_{0}$ is independent of $m$. To analyze the least eigenvalue, we first look at the initialization. Using assumptions of the population Gram matrix and concentration inequalities, we can show at the beginning $\left\|\mathbf{G}^{(H)}(0)-\mathbf{K}^{(H)}(0)\right\|_{2}\leq\frac{1}{4}\lambda_{0}$, which implies

Now for the $k$-th iteration, by matrix perturbation analysis, we know it is sufficient to show $\left\|\mathbf{G}^{(H)}(k)-\mathbf{G}^{(H)}(0)\right\|_{2}\leq\frac{1}{4}\lambda_{0}$. To do this, we use a similar approach as in (Du et al., 2018b). We show as long as $m$ is large enough, every weight matrix is close its initialization in a relative error sense. Ignoring all other parameters except $m$, $\left\|\mathbf{W}^{(h)}(k)-\mathbf{W}^{(h)}(0)\right\|_{F}\lesssim 1$, and thus the average per-neuron distance from initialization is $\frac{\left\|\mathbf{W}^{(h)}(k)-\mathbf{W}^{(h)}(0)\right\|_{F}}{\sqrt{m}}\lesssim\frac{1}{\sqrt{m}}$ which tends to zero as $m$ increases. See Lemma B.5 for precise statements with all the dependencies.

This fact in turn shows $\left\|\mathbf{G}^{(H)}(k)-\mathbf{G}^{(H)}(0)\right\|_{2}$ is small. The main difference from (Du et al., 2018b) is that we are considering deep neural networks, and when translating the small deviation, $\left\|\mathbf{W}^{(h)}(k)-\mathbf{W}^{(h)}(0)\right\|_{F}$ to $\left\|\mathbf{G}^{(H)}(k)-\mathbf{G}^{(H)}(0)\right\|_{2}$, there is an amplification factor which depends on the neural network architecture.

For deep fully connected neural networks, we show this amplification factor is exponential in $H$. On the other hand, for ResNet and convolutional ResNet we show this amplification factor is only polynomial in $H$. We further show the width $m$ required is proportional to this amplification factor.

Appendix B Proofs for Section 5

We first derive the formula of the gradient for the multilayer fully connected neural network

are the derivative matrices induced by the activation function and

is the output of the $h^{\prime}$-th layer.

Through standard calculation, we can get the expression of $\mathbf{G}^{(H)}_{i,j}$ of the following form

We first present a lemma which shows with high probability the feature of each layer is approximately normalized.

If $\sigma(\cdot)$ is $L-$Lipschitz and $m=\Omega\left(\frac{nHg_{C}(H)^{2}}{\delta}\right)$, where $C\triangleq c_{\sigma}L\left(2\left|\sigma(0)\right|\sqrt{\frac{2}{\pi}}+2L\right)$, then with probability at least $1-\delta$ over random initialization, for every $h\in[H]$ and $i\in[n]$, we have

We follow the proof sketch described in Section A. We first analyze the spectral property of $\mathbf{G}^{(H)}(0)$ at the initialization phase. The following lemma lower bounds its least eigenvalue. This lemma is a direct consequence of results in Section E.

If $m=\Omega\left(\frac{n^{2}\log(Hn/\delta)2^{O(H)}}{\lambda_{0}^{2}}\right)$, we have

Now we proceed to analyze the training process. We prove the following lemma which characterizes how the perturbation from weight matrices propagates to the input of each layer. This Lemma is used to prove the subsequent lemmas.

Suppose for every $h\in[H]$, $\left\|\mathbf{W}^{(h)}(0)\right\|_{2}\leq c_{w,0}\sqrt{m}$, $\left\|\mathbf{x}^{(h)}(0)\right\|_{2}\leq c_{x,0}$ and $\left\|\mathbf{W}^{(h)}(k)-\mathbf{W}^{(h)}(0)\right\|_{F}\leq\sqrt{m}R$ for some constant $c_{w,0},c_{x,0}>0$ and $R\leq c_{w,0}$. If $\sigma(\cdot)$ is $L-$Lipschitz, we have

where $c_{x}=2\sqrt{c_{\sigma}}Lc_{w,0}$.

Here the assumption of $\left\|\mathbf{W}^{(h)}(0)\right\|_{2}\leq c_{w,0}\sqrt{m}$ can be shown using Lemma G.2 and taking union bound over $h\in[H]$, where $c_{w,0}$ is a universal constant. Next, we show with high probability over random initialization, perturbation in weight matrices leads to small perturbation in the Gram matrix.

Suppose $\sigma(\cdot)$ is $L-$Lipschitz and $\beta-$smooth. Suppose for $h\in[H]$, $\left\|\mathbf{W}^{(h)}(0)\right\|_{2}\leq c_{w,0}\sqrt{m}$, $\left\|\mathbf{a}(0)\right\|_{2}\leq a_{2,0}\sqrt{m}$, $\left\|\mathbf{a}(0)\right\|_{4}\leq a_{4,0}m^{1/4}$ , $\frac{1}{c_{x,0}}\leq\left\|\mathbf{x}^{(h)}(0)\right\|_{2}\leq c_{x,0}$, if $\left\|\mathbf{W}^{(h)}(k)-\mathbf{W}^{(h)}(0)\right\|_{F},\left\|\mathbf{a}(k)-\mathbf{a}(0)\right\|_{2}\leq\sqrt{m}R$ where $R\leq cg_{c_{x}}(H)^{-1}\lambda_{0}n^{-1}$ and $R\leq cg_{c_{x}}(H)^{-1}$ for some small constant $c$ and $c_{x}=2\sqrt{c_{\sigma}}Lc_{w,0}$, we have

Here the assumption of $\left\|\mathbf{a}(0)\right\|_{2}\leq a_{2,0}\sqrt{m}$, $\left\|\mathbf{a}(0)\right\|_{4}\leq a_{4,0}m^{1/4}$ can be easily obtained using standard concentration inequalities, where $a_{2,0}$ and $a_{4,0}$ are both universal constants. The following lemma shows if the induction holds, we have every weight matrix close to its initialization.

If Condition A.1 holds for $k^{\prime}=1,\ldots,k$, we have for any $s=1,\ldots,k+1$

where $R^{\prime}=\frac{16c_{x,0}a_{2,0}\left(c_{x}\right)^{H}\sqrt{n}\left\|\mathbf{y}-\mathbf{u}(0)\right\|_{2}}{\lambda_{0}\sqrt{m}}\leq cg_{c_{x}}(H)^{-1}$ for some small constant $c$ with $c_{x}=\max\{2\sqrt{c_{\sigma}}Lc_{w,0},1\}$ and $Q^{\prime}(s)=4c_{x,0}a_{2,0}\left(c_{x}\right)^{H}\sqrt{n}\left\|\mathbf{y}-\mathbf{u}(s)\right\|_{2}$

Now we proceed to analyze the perturbation terms.

If Condition A.1 holds for $k^{\prime}=1,\ldots,k$, suppose $\eta\leq c\lambda_{0}\left(n^{2}H^{2}(c_{x})^{3H}g_{2c_{x}}(H)\right)^{-1}$ for some small constant $c$, we have

If Condition A.1 holds for $k^{\prime}=1,\ldots,k$, suppose $\eta\leq c\lambda_{0}\left(n^{2}H^{2}(c_{x})^{2H}g_{2c_{x}}(H)\right)^{-1}$ for some small constant $c$, then we have $\left\|\mathbf{u}(k+1)-\mathbf{u}(k)\right\|_{2}^{2}\leq\frac{1}{8}\eta\lambda_{0}\left\|\mathbf{y}-\mathbf{u}(k)\right\|_{2}^{2}$.

We now proceed with the proof of Theorem 5.1. By induction, we assume Condition A.1 for all $k^{\prime}<k$. Using Lemma B.5, this establishes

By Lemma B.4, this establishes $\lambda_{\min}(\mathbf{G}^{(H)}(k))\geq\frac{\lambda_{0}}{2}$.

With these estimates in hand, we are ready to prove the induction hypothesis of Condition A.1.

The first inequality drops the positive terms $\left(\mathbf{y}-\mathbf{u}(k)\right)^{\top}\sum_{h\in[H+1],h\neq H}\mathbf{G}^{(h)}(k)\left(\mathbf{y}-\mathbf{u}(k)\right)$. The second inequality uses the argument above that establishes $\lambda_{\min}(\mathbf{G}^{(H)}(k))\geq\frac{\lambda_{0}}{2}$. The third inequality uses Lemmas B.6 and B.7.

We will bound $\left\|\mathbf{x}_{i}^{(h)}(0)\right\|_{2}$ by induction on layers. The induction hypothesis is that with probability at least $1-(h-1)\frac{\delta}{nH}$ over $\mathbf{W}^{(1)}(0),\ldots,\mathbf{W}^{(h-1)}(0)$, for every $1\leq h^{\prime}\leq h-1$, $\frac{1}{2}\leq 1-\frac{g_{C}(h^{\prime})}{2g_{C}(H)}\leq\left\|\mathbf{x}_{i}^{(h^{\prime})}(0)\right\|_{2}\leq 1+\frac{g_{C}(h^{\prime})}{2g_{C}(H)}\leq 2$. Note that it is true for $h=1$. We calculate the expectation of $\left\|\mathbf{x}_{i}^{(h)}(0)\right\|_{2}^{2}$ over the randomness from $\mathbf{W}^{(h)}(0)$. Recall

Note that $\sigma(\cdot)$ is $L-$Lipschitz, for any $\frac{1}{2}\leq\alpha\leq 2$, we have

where $C\triangleq c_{\sigma}L\left(2\left|\sigma(0)\right|\sqrt{\frac{2}{\pi}}+2L\right)$, which implies

where $C_{2}\triangleq\sigma(0)^{4}+8\left|\sigma(0)\right|^{3}L\sqrt{2/\pi}+24\sigma(0)^{2}L^{2}+64\sigma(0)L^{3}\sqrt{2/\pi}+512L^{4}$ and the last inequality we used the formula for the first four absolute moments of Gaussian.

Applying Chebyshev’s inequality and plugging in our assumption on $m$, we have with probability $1-\frac{\delta}{nH}$ over $\mathbf{W}^{(h)}$,

Thus with probability $1-h\frac{\delta}{nH}$ over $\mathbf{W}^{(1)},\ldots,\mathbf{W}^{(h)}$,

Using union bounds over $[n]$, we prove the lemma. ∎

We prove this lemma by induction. Our induction hypothesis is

For $h=0$, since the input data is fixed, we know the induction hypothesis holds. Now suppose the induction hypothesis holds for $h^{\prime}=0,\ldots,h-1$, we consider $h^{\prime}=h$.

Because Frobenius-norm of a matrix is bigger than the operator norm, it is sufficient to bound $\left\|\mathbf{G}^{(H)}(k)-\mathbf{G}^{(H)}(0)\right\|_{F}$. For simplicity define $z_{i,r}(k)=\mathbf{w}_{r}^{(H)}(k)^{\top}\mathbf{x}_{i}^{(H-1)}(k)$, we have

For $I_{1}^{i,j}$, using Lemma B.3, we have

Using the same proof for Lemma B.3, it is easy to see

Plugging in the bound on $R$, we have the desired result.

We will prove this corollary by induction. The induction hypothesis is

First it is easy to see it holds for $s^{\prime}=0$. Now suppose it holds for $s^{\prime}=0,\ldots,s$, we consider $s^{\prime}=s+1$. We have

To bound $\left\|\mathbf{x}_{i}^{(h-1)}(s)\right\|_{2}$, we can just apply Lemma B.3 and get

To bound $\left\|\mathbf{W}^{(k)}(s)\right\|_{2}$, we use our assumption

Note that $\left\|\mathbf{J}^{(k)}(s)\right\|_{2}\leq L$. Plugging in these two bounds back, we obtain

Similar to the proof for Lemma B.5, we have

Let $\mathbf{\theta}(k,s)=\mathbf{\theta}(k)-sL^{\prime}(\mathbf{\theta}(k))$,

Since this holds for all $i\in[n]$, plugging in $\eta$ and noting that $\left\|\mathbf{y}-\mathbf{u}(0)\right\|_{2}=O(\sqrt{n})$, we have

Appendix C Proofs for Section 6

For ResNets, $\mathbf{G}^{(H)}$ has the following form:

Similar to Lemma B.1, we can show with high probability the feature of each layer is approximately normalized.

If $\sigma(\cdot)$ is $L-$Lipschitz and $m=\Omega\left(\frac{n}{\delta}\right)$, assuming $\left\|\mathbf{W}^{(h)}(0)\right\|_{2}\leq c_{w,0}\sqrt{m}$ for $h\in[2,H]$ and $c_{w,0}\approx 2$ for Gaussian initialization. We have with probability at least $1-\delta$ over random initialization, for every $h\in[H]$ and $i\in[n]$,

for some universal constant $c_{x,0}>1$ (only depends on $\sigma$).

The following lemma lower bounds $\mathbf{G}^{(H)}(0)$’s least eigenvalue. This lemma is a direct consequence of results in Section E.

If $m=\Omega\left(\frac{n^{2}\log(Hn/\delta)}{\lambda_{0}^{2}}\right)$, we have

Next, we characterize how the perturbation on the weight matrices affects the input of each layer.

Suppose $\sigma(\cdot)$ is $L$-Lipschitz and for $h\in[H]$, $\left\|\mathbf{W}^{(h)}(0)\right\|_{2}\leq c_{w,0}\sqrt{m}$, $\left\|\mathbf{x}^{(h)}(0)\right\|_{2}\leq c_{x,0}$ and $\left\|\mathbf{W}^{(h)}(k)-\mathbf{W}^{(h)}(0)\right\|_{F}\leq\sqrt{m}R$ for some constant $c_{w,0},c_{x,0}>0$ and $R\leq c_{w,0}$ . Then we have

Next, we characterize how the perturbation on the weight matrices affect $\mathbf{G}^{(H)}$.

Suppose $\sigma(\cdot)$ is differentiable, $L-$Lipschitz and $\beta-$smooth. Using the same notations in Lemma B.4, if $\left\|\mathbf{W}^{(h)}(k)-\mathbf{W}^{(h)}(0)\right\|_{F},\left\|\mathbf{a}(k)-\mathbf{a}(0)\right\|_{2}\leq\sqrt{m}R$ where $R\leq c\lambda_{0}H^{2}n^{-1}$ and $R\leq c$ for some small constant $c$, we have

We prove Theorem 6.1 by induction. Our induction hypothesis is just the following convergence rate of empirical loss.

A directly corollary of this condition is the following bound of deviation from the initialization. The proof only involves standard calculations so we defer it to appendix.

If Condition A.1 holds for $k^{\prime}=1,\ldots,k$, we have for any $s\in[k+1]$

where $R^{\prime}=\frac{16c_{res}c_{x,0}a_{2,0}Le^{2c_{res}c_{w,0}L}\sqrt{n}\left\|\mathbf{y}-\mathbf{u}(0)\right\|_{2}}{H\lambda_{0}\sqrt{m}}<c$ for some small constant $c$ and $Q^{\prime}(s)=4c_{res}c_{x,0}a_{2,0}Le^{2c_{res}c_{w,0}L}\sqrt{n}\left\|\mathbf{y}-\mathbf{u}(s)\right\|_{2}/H$.

The next lemma bounds the $\mathbf{I}_{2}$ term.

If Condition A.1 holds for $k^{\prime}=1,\ldots,k$ and $\eta\leq c\lambda_{0}H^{2}n^{-2}$ for some small constant $c$, we have

If Condition A.1 holds for $k^{\prime}=1,\ldots,k$ and $\eta\leq c\lambda_{0}H^{2}n^{-2}$ for some small constant $c$, we have $\left\|\mathbf{u}(k+1)-\mathbf{u}(k)\right\|_{2}^{2}\leq\frac{1}{8}\eta\lambda_{0}\left\|\mathbf{y}-\mathbf{u}(k)\right\|_{2}^{2}$.

Now using the same argument as in the proof for multilayer fully connected neural network, we finish our proof for ResNet.

We will bound $\left\|\mathbf{x}_{i}^{(h)}(0)\right\|_{2}$ layer by layer. For the first layer, we can calculate

where $C_{2}\triangleq\sigma(0)^{4}+4\left|\sigma(0)\right|^{3}L\sqrt{2/\pi}+6\sigma(0)^{2}L^{2}+8\left|\sigma(0)\right|L^{3}\sqrt{2/\pi}+32L^{4}$. We have with probability at least $1-\frac{\delta}{n}$,

By definition we have for $2\leq h\leq H$,

Choosing $c_{x,0}=2e^{c_{res}c_{w,0}L}$ and using union bounds over $[n]$, we prove the lemma.

We prove this lemma by induction. Our induction hypothesis is

which implies $g(1)=\sqrt{c_{\sigma}}LR$, for $2\leq h\leq H$, we have

Lastly, simple calculations show $g(h)\leq\left(\sqrt{c_{\sigma}}L+\frac{c_{x,0}}{c_{w,0}}\right)e^{2c_{res}c_{w,0}L}R$.

Similar to the proof of Lemma B.4, we can obtain

For $I_{1}^{i,j}$, using Lemma C.3, we have

where $c_{x}\triangleq\left(\sqrt{c_{\sigma}}L+\frac{c_{x,0}}{c_{w,0}}\right)e^{2c_{res}c_{w,0}L}$. To bound $I_{2}^{i,j}$, we have

Using the same proof for Lemma C.3, it is easy to see

The bound of $I_{3}^{i,j}$ is similar to that in Lemma B.4,

Plugging in the bound on $R$, we have the desired result.

We will prove this corollary by induction. The induction hypothesis is

First it is easy to see it holds for $s^{\prime}=0$. Now suppose it holds for $s^{\prime}=0,\ldots,s$, we consider $s^{\prime}=s+1$. Similar to Lemma B.5, we have

Similar to Lemma B.6, we first bound the gradient norm.

We have bounded the RHS in the proof for Lemma C.5, thus

Let $\mathbf{\theta}(k,s)=\mathbf{\theta}(k)-sL^{\prime}(\mathbf{\theta}(k))$, we have

where $c_{x}\triangleq\left(\sqrt{c_{\sigma}}L+\frac{c_{x,0}}{c_{w,0}}\right)e^{3c_{res}c_{w,0}L}$. According to Lemma G.1, we have

where we used the bound of $\eta$ and that $\left\|\mathbf{y}-\mathbf{u}(0)\right\|_{2}=O(\sqrt{n})$,. ∎

Appendix D Proofs for Section 7

For CNN, denote $\mathbf{x}_{i,l}=\phi\left(\mathbf{x}_{i,l}\right)_{:,l}$, $\mathbf{G}^{(H)}$ has the following form:

Similar to Lemma B.1, we can show with high probability the feature of each layer is approximately normalized.

If $\sigma(\cdot)$ is $L-$Lipschitz and $m=\Omega\left(\frac{p^{2}n}{c_{\sigma,\frac{1}{\sqrt{p}}}^{2}\delta}\right)$, assuming $\left\|\mathbf{W}^{(h)}(0)\right\|_{2}\leq c_{w,0}\sqrt{m}$ for $h\in[H]$, we have with probability at least $1-\delta$ over random initialization, for every $h\in[H]$ and $i\in[n]$,

The following lemma lower bounds $\mathbf{G}^{(H)}(0)$’s least eigenvalue. This lemma is a direct consequence of results in Section E.

If $m=\Omega\left(\frac{n^{2}p^{2}\log(Hn/\delta)}{\lambda_{0}^{2}}\right)$, we have

Next, we prove the following lemma which characterizes how the perturbation from weight matrices propagates to the input of each layer.

Suppose $\sigma(\cdot)$ is $L-$Lipschitz and for $h\in[H]$, $\left\|\mathbf{W}^{(h)}(0)\right\|_{2}\leq c_{w,0}\sqrt{m}$, $\left\|\mathbf{x}^{(h)}(0)\right\|_{F}\leq c_{x,0}$ and $\left\|\mathbf{W}^{(h)}(k)-\mathbf{W}^{(h)}(0)\right\|_{F}\leq\sqrt{m}R$ for some constant $c_{w,0},c_{x,0}>1$ and $R\leq c_{w,0}$ . Then we have

Next, we show with high probability over random initialization, perturbation in weight matrices leads to small perturbation in the Gram matrix.

Suppose $\sigma(\cdot)$ is differentaible, $L-$Lipschitz and $\beta-$smooth. Using the same notations in Lemma B.4, if $\left\|\mathbf{a}_{:,i}\right\|_{2}\leq a_{2,0}\sqrt{m}$ and $\left\|\mathbf{a}_{:,i}\right\|_{4}\leq a_{4,0}m^{1/4}$ for any $i\in[p]$, $\left\|\mathbf{W}^{(h)}(k)-\mathbf{W}^{(h)}(0)\right\|_{F},\left\|\mathbf{a}(k)-\mathbf{a}(0)\right\|_{F}\leq\sqrt{m}R$ where $R\leq c\lambda_{0}H^{2}\left(n\right)^{-1}poly(p)^{-1}$ for some small constant $c$, we have

If Condition A.1 holds for $k^{\prime}=1,\ldots,k$, we have for any $s\in[k+1]$

where $R^{\prime}=\frac{16c_{res}c_{x,0}L\sqrt{pq}e^{2c_{res}c_{w,0}La_{2,0}\sqrt{q}}\sqrt{n}\left\|\mathbf{y}-\mathbf{u}(0)\right\|_{2}}{H\lambda_{0}\sqrt{m}}<c$ for some small constant $c$ and

The follow lemma bounds the norm of $\mathbf{I}_{2}$.

If Condition A.1 holds for $k^{\prime}=1,\ldots,k$ and $\eta\leq c\lambda_{0}H^{2}n^{-2}poly(1/p)$ for some small constant $c$, we have

If Condition A.1 holds for $k^{\prime}=1,\ldots,k$ and $\eta\leq c\lambda_{0}H^{2}n^{-2}poly(1/p)$ for some small constant $c$, we have $\left\|\mathbf{u}(k+1)-\mathbf{u}(k)\right\|_{2}^{2}\leq\frac{1}{8}\eta\lambda_{0}\left\|\mathbf{y}-\mathbf{u}(k)\right\|_{2}^{2}$.

Now using the same argument as in the proof for multilayer fully connected neural network, we finish our proof for CNN.

We will bound $\left\|\mathbf{x}_{i}^{(h)}(0)\right\|_{F}$ layer by layer. For the first layer, we can calculate

where the inequality we use the definition of $c_{\sigma,\frac{1}{\sqrt{p}}}$ and the fact that there must exist $l^{\prime}\in[p]$ such that $\left\|\mathbf{x}_{i,l^{\prime}}\right\|_{2}^{2}\geq\frac{1}{p_{1}}\geq\frac{1}{p}$. For the variance,

where $C_{2}\triangleq\sigma(0)^{4}+4\left|\sigma(0)\right|^{3}L\sqrt{2/\pi}+6\sigma(0)^{2}L^{2}+8\left|\sigma(0)\right|L^{3}\sqrt{2/\pi}+32L^{4}$. We have with probability at least $1-\frac{\delta}{n}$,

By defination we have for $2\leq h\leq H$

Choosing $c_{x,0}=\max\{\sqrt{qL^{2}c_{\sigma}c_{w,0}^{2}},\sqrt{\frac{2c_{\sigma,\frac{1}{\sqrt{p}}}}{c_{\sigma}}}\}e^{\sqrt{q}c_{res}c_{w,0}L}$ and using union bounds over $[n]$, we prove the lemma.

We prove this lemma by induction. Our induction hypothesis is

which implies $g(1)=\sqrt{c_{\sigma}}L\sqrt{q}R$, for $2\leq h\leq H$, we have

Lastly, simple calculations show $g(h)\leq\left(\sqrt{c_{\sigma}}L\sqrt{q}+\frac{c_{x,0}}{c_{w,0}}\right)e^{2c_{w,0}L\sqrt{q}c_{res}}R$.

Similar to Lemma C.4, define $z_{i,l,r}=\left(\mathbf{w}_{r}^{(H)}\right)^{\top}\mathbf{x}_{i,l}^{(H-1)}$, we have

For $I_{1}^{i,j}$, using Lemma D.3, we have

where $c_{x}\triangleq\left(\sqrt{c_{\sigma}}L\sqrt{q}+\frac{c_{x,0}}{c_{w,0}}\right)e^{2c_{res}c_{w,0}L\sqrt{q}}$. To bound $I_{2}^{i,j}$, we have

Using the same proof for Lemma D.3, it is easy to see

Plugging in the bound on $R$, we have the desired result. ∎

We will prove this corollary by induction. The induction hypothesis is

First it is easy to see it holds for $s^{\prime}=0$. Now suppose it holds for $s^{\prime}=0,\ldots,s$, we consider $s^{\prime}=s+1$. Similar to Lemma B.5, we have

where $\left\|\cdot\right\|_{op}$ denotes the operator norm. Similarly, we have

Let $\mathbf{\theta}(k,s)=\mathbf{\theta}(k)-sL^{\prime}(\mathbf{\theta}(k))$ ,similar to the proof of Lemma B.6, we have

where we used the bound of $\eta$ and that $\left\|\mathbf{y}-\mathbf{u}(0)\right\|_{2}=O(\sqrt{n})$. ∎

Appendix E Analysis of Random Initialization

In this section we provide a self-contained framework to analyze the Gram matrix at the initialization phase. There are two main objectives. First, we provide the expression of the Gram matrix as $m\rightarrow\infty$, i.e., the population Gram matrix. Second, we quantitatively study how much over-parameterization is needed to ensure the Gram matrix generated by the random initialization. The bound will depend on number of samples $n$ and properties of the activation function. This analysis framework is fully general that it can explain fully connected neural network, ResNet, convolutional neural considered in this paper and other neural network architectures that satisfy the general setup defined below.

We begin with some notations. Suppose that we have a sequence of real vector spaces

For fully-connected neural network and ResNet, $p^{(0)}=p^{(1)}=\ldots=p^{(H)}=1$. For convolutional neural network, $p^{(h)}$ is the number of patches of the $h$-th layer.

For convolutional neural network, the dimension of $\mathcal{W}$ is the filter size.

For full-connected neural networks, we take $\mathcal{D}^{(h)}$ to be the zero mapping. For ResNet and convolutional ResNet, we take $\mathcal{D}^{(h)}$ to be the identity mapping.

Now we recursively define the output of each layer in this setup. In the following, we use $h\in[H]$ to index layers, $i\in[n]$ to index data points, $\alpha,\beta,\gamma\in[m]$ or $[d]$ to index channels (for CNN) or weight vectors (for fully connected neural networks or ResNet).

$d=1$ for fully connected neural network and ResNet and $d\geq 1$ for convolutional neural network because $d$ represents the number of input channels.

We denote $\mathbf{X}^{(h),[\alpha]}_{i}$ an $p^{(h)}$-dimensional vector which is the output at $(h-1)$-th layer. We have the following recursive formula

where $\mathbf{W}^{(h),(\alpha)}_{(\beta)}$ is $p^{(h)}\times p^{(h-1)}$ matrix generated according to the following rule

for $h=1$, $\mathbf{W}^{(h),(\alpha)}_{[\beta]}$ is defined for $1\leq\alpha\leq m$ and $1\leq\beta\leq d$; for $h>1$, $\mathbf{W}^{(h),(\alpha)}_{(\beta)}$ is defined for $1\leq\alpha\leq m$ and $1\leq\beta\leq m$;

the set of random variables $\{\mathbf{W}^{(h),(\alpha)}_{(\beta)}\}_{h,\alpha,\beta}$ are independently generated;