Why does over-parameterization lead to improved initialization and convergence of deep neural networks?
Over-parameterization in Neural Network.
Over-parameterization has shown the superiority
on providing better model initialization (Arpit and
Bengio, 2019), improving model convergence (Du
et al., 2019; Allen-Zhu et al., 2019b; Gao et al.,
2022a) and generalization (Allen-Zhu et al., 2019a).
After the lottery theory hypothesis (Frankle and
Carbin, 2019) was introduced, a surge of works
pointed out that over-parameterization might be
helpful to enhance the training efficiency (Malach
et al., 2020; Pensia et al., 2020) and improve
the model performance (Chen et al., 2020; Brix
et al., 2020; Prasanna et al., 2020). Among
them, Liu et al. (2021b) employed in-time overparameterization to narrow the performance gap between sparse and dense training. Our study aimed
to use the over-parametrization strategy to better inspire the potentiality of PLMs, enhancing their fine-tuning performance.
A global convergence theory for deep ReLU implicit networks via over-parameterization
Implicit deep learning has received increasing attention recently due to the fact that it generalizes the recursive prediction rules of many commonly used neural network architectures. Its prediction rule is provided implicitly based on the solution of an equilibrium equation. Although a line of recent empirical studies has demonstrated its superior performances, the theoretical understanding of implicit neural networks is limited. In general, the equilibrium equation may not be well-posed during the training. As a result, there is no guarantee that a vanilla (stochastic) gradient descent (SGD) training nonlinear implicit neural networks can converge. This paper fills the gap by analyzing the gradient flow of Rectified Linear Unit (ReLU) activated implicit neural networks. For an $m$-width implicit neural network with ReLU activation and $n$ training samples, we show that a randomly initialized gradient descent converges to a global minimum at a linear rate for the square loss function if the implicit neural network is \textit{over-parameterized}. It is worth noting that, unlike existing works on the convergence of (S)GD on finite-layer over-parameterized neural networks, our convergence results hold for implicit neural networks, where the number of layers is \textit{infinite}.
[{"first":"Tianxiang","last":"Gao","middle":[]},{"first":"Hailiang","last":"Liu","middle":[]},{"first":"Jia","last":"Liu","middle":[]},{"first":"Hridesh","last":"Rajan","middle":[]},{"first":"Hongyang","last":"Gao","middle":[]}]
A Convergence Theory for Deep Learning via Over-Parameterization
Deep neural networks (DNNs) have demonstrated dominating performance in many fields; since AlexNet, the neural networks used in practice are going wider and deeper. On the theoretical side, a long line of works have been focusing on why we can train neural networks when there is only one hidden layer. The theory of multi-layer networks remains somewhat unsettled. In this work, we prove why simple algorithms such as stochastic gradient descent (SGD) can find $\textit{global minima}$ on the training objective of DNNs. We only make two assumptions: the inputs do not degenerate and the network is over-parameterized. The latter means the number of hidden neurons is sufficiently large: $\textit{polynomial}$ in $L$, the number of DNN layers and in $n$, the number of training samples. As concrete examples, on the training set and starting from randomly initialized weights, we show that SGD attains 100% accuracy in classification tasks, or minimizes regression loss in linear convergence speed $\varepsilon \propto e^{-\Omega(T)}$, with a number of iterations that only scales polynomial in $n$ and $L$. Our theory applies to the widely-used but non-smooth ReLU activation, and to any smooth and possibly non-convex loss functions. In terms of network architectures, our theory at least applies to fully-connected neural networks, convolutional neural networks (CNN), and residual neural networks (ResNet).
[{"first":"Zeyuan","last":"Allen-Zhu","middle":[]},{"first":"Yuanzhi","last":"Li","middle":[]},{"first":"Zhao","last":"Song","middle":[]}]
Ternary Weight Networks
We present a memory and computation efficient ternary weight networks (TWNs) - with weights constrained to +1, 0 and -1. The Euclidian distance between full (float or double) precision weights and the ternary weights along with a scaling factor is minimized in training stage. Besides, a threshold-based ternary function is optimized to get an approximated solution which can be fast and easily computed. TWNs have shown better expressive abilities than binary precision counterparts. Meanwhile, TWNs achieve up to 16$\times$ model compression rate and need fewer multiplications compared with the float32 precision counterparts. Extensive experiments on MNIST, CIFAR-10, and ImageNet datasets show that the TWNs achieve much better result than the Binary-Weight-Networks (BWNs) and the classification performance on MNIST and CIFAR-10 is very close to the full precision networks. We also verify our method on object detection task and show that TWNs significantly outperforms BWN by more than 10\% mAP on PASCAL VOC dataset. The pytorch version of source code is available at: https://github.com/Thinklab-SJTU/twns.
[{"first":"Fengfu","last":"Li","middle":[]},{"first":"Bin","last":"Liu","middle":[]},{"first":"Xiaoxing","last":"Wang","middle":[]},{"first":"Bo","last":"Zhang","middle":[]},{"first":"Junchi","last":"Yan","middle":[]}]
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
One of the mystery in the success of neural networks is randomly initialized first order methods like gradient descent can achieve zero training loss even though the objective function is non-convex and non-smooth. This paper demystifies this surprising phenomenon for two-layer fully connected ReLU activated neural networks. For an $m$ hidden node shallow neural network with ReLU activation and $n$ training data, we show as long as $m$ is large enough and the data is non-degenerate, randomly initialized gradient descent converges a globally optimal solution with a linear convergence rate for the quadratic loss function. Our analysis is based on the following observation: over-parameterization and random initialization jointly restrict every weight vector to be close to its initialization for all iterations, which allows us to exploit a strong convexity-like property to show that gradient descent converges at a global linear rate to the global optimum. We believe these insights are also useful in analyzing deep models and other first order methods.
[{"first":"Simon","last":"Du","middle":["S."]},{"first":"Xiyu","last":"Zhai","middle":[]},{"first":"Barnabas","last":"Poczos","middle":[]},{"first":"Aarti","last":"Singh","middle":[]}]
A global convergence theory for deep ReLU implicit networks via over-parameterization
1) Background and Motivation: In the last decade, implicit deep learning (El Ghaoui et al., 2019) have attracted more and more attention. Its popularity is mainly because it generalizes the recursive rules of many widely used neural network architectures. A line of recent works (Bai et al., 2019;El Ghaoui et al., 2019;Bai et al., 2020) have shown that the implicit neural network architecture is a wider class that includes most current neural network architectures as special cases, such as feed-forward neural networks, convolution neural networks, residual networks, and recurrent neural networks. Moreover, implicit deep learning is also well known for its competitive performance compared to other regular deep neural networks but using significantly fewer computational resources (Dabre & Fujita, 2019;Dehghani et al., 2018;Bai et al., 2018).
A global convergence theory for deep ReLU implicit networks via over-parameterization
Although a line of literature has been shown the superior performance of implicit neural networks experimentally, the theoretical understanding is still limited. To date, it is still unknown if a simple first-order optimization method such as (stochastic) gradient descent can converge on an implicit neural network activated by a nonlinear function. Unlike a regular deep neural network, an implicit neural network could have infinitely many layers, resulting in the possibility of divergence of the forward propagation (El Ghaoui et al., 2019;Kawaguchi, 2021). The main challenge in establishing the convergence of implicit neural network training lies in the fact that, in general, the equilibrium equation of implicit neural networks cannot be solved in closed-form. What exacerbates the problem is the well-posedness of the forward propagation. In other words, the equilibrium equation may have zero or multiple solutions. A line of recent studies have suggested a number of strategies to handle this well-posedness challenge, but they all involved reformulation or solving subproblems in each iteration. For example, El Ghaoui et al. (2019) suggested to reformulate the training as the Fenchel divergence formulation and solve the reformulated optimization problem by projected gradient descent method. However, this requires solving a projection subproblem in each iteration and convergence was only demonstrated numerically. By using an extra softmax layer, Kawaguchi (2021) established global convergence result of gradient descent for a linear implicit neural network. Unfortunately, their result cannot be extended to nonlinear activations, which are critical to the learnability of deep neural networks. This paper proposes a global convergence theory of gradient descent for implicit neural networks activated by nonlinear Rectified Linear Unit (ReLU) activation function by using overparameterization. Specifically, we show that random initialized gradient descent with fixed stepsize converges to a global minimum of a ReLU implicit neural network at a linear rate as long as the implicit neural network is overparameterized. Recently, over-parameterization has been shown to be effective in optimizing finite-depth neural networks (Zou et al., 2020;Nguyen & Mondelli, 2020;Arora et al., 2019;Oymak & Soltanolkotabi, 2020). Although the objective function in the training is nonsmooth and non-convex, it can be shown that GD or SGD converge to a global minimum linearly if the width m of each layer is a polynomial of the number of training sample n and the number of layers h, i.e., m = poly(n, h). However, these results cannot be directly applied to implicit neural networks, since implicit neural networks have infinitely many hidden layers, i.e., h → ∞, and the well-posedness problem surfaces during the training process. In fact, Chen et al. (2018); Bai et al. (2019;2020) have all observed that the time and number of iterations spent on forward propagation are gradually increased with the the training epochs. Thus, we have to ensure the unique equilibrium point always exists throughout the training given that the width m is only polynomial of n.
A global convergence theory for deep ReLU implicit networks via over-parameterization
2) Preliminaries of Implicit Deep Learning: In this work, we consider an implicit neural network with the transition at the -th layer in the following form (El Ghaoui et al., 2019;Bai et al., 2019):
A global convergence theory for deep ReLU implicit networks via over-parameterization
where φ : R d → R m is a feature mapping function that transforms an input vector x ∈ R d to a desired feature vector φ φ(x), z ∈ R m is the output of the -th layer, A ∈ R m×m is a trainable weight matrix, σ(u) = max{0, u} is the ReLU activation function, and γ ∈ (0, 1) is a fixed scalar to scale A. As will be shown later in Section 2.1, γ plays the role of ensuring the existence of the limit z * = lim →∞ z . In general, the feature mapping function φ is a nonlinear function, which extracts features from the low-dimensional input vector x. In this paper, we consider a simple nonlinear feature mapping function φ given by
A global convergence theory for deep ReLU implicit networks via over-parameterization
where W ∈ R m×d is a trainable parameter matrix. As → ∞, an implicit neural network can be considered an infinitely deep neural network. Consequently, z * is not only the limit of the sequence {z } ∞ =0 with z 0 = 0, but it is also the equilibrium point (or fixed point) of the equilibrium equation:
A global convergence theory for deep ReLU implicit networks via over-parameterization
whereγ γ/ √ m. In implicit neural networks, the predictionŷ for the input vector x is the combination of the fixed point z * and the feature vector φ, i.e.,
A global convergence theory for deep ReLU implicit networks via over-parameterization
where u, v ∈ R m are trainable weight vectors. For simplicity, we use θ vec (A, W , u, v) to group all training parameters. Given a training data set {(x i , y i )} n i=1 , we want to minimize
A global convergence theory for deep ReLU implicit networks via over-parameterization
whereŷ and y are the vectors formed by stacking all the prediction and labels.
A global convergence theory for deep ReLU implicit networks via over-parameterization
3) Main Results: Our results are based on the following observations. We first analyze the forward propagation and find that the unique equilibrium point always exists if the scaled matrixγA in Eq.
A global convergence theory for deep ReLU implicit networks via over-parameterization
(3) has an operator norm less than one. Thus, the well-posedness problem is reduced to finding a sequence of scalars {γ k } ∞ k=1 such thatγ k A(k) is appropriately scaled. To achieve this goal, we show that the operator norm A(k) is uniformly upper bounded by a constant over all iterations. Consequently, a fixed scalar γ is enough to ensure the well-posedness of Eq. (3). Our second observation is from the analysis of the gradient descent method with infinitesimal step-size (gradient flow). By applying the chain rule with the gradient flow, we derive the dynamics of predictionŷ(t) which is governed by the spectral property of a Gram matrix. In particular, if the smallest eigenvalue of the Gram matrix is lower bounded throughout the training, the gradient descent method enjoys a linear convergence rate. Along with some basic functional analysis results, it can be shown that the smallest eigenvalue of the Gram matrix at initialization is lower bounded if no two data samples are parallel. Although the Gram matrix varies in each iteration, the spectral property is preserved if the Gram matrix is close to its initialization. Thus, the convergence problem is reduced to showing the Gram matrix in latter iterations is close to its initialization. Our third observation is that we find random initialization, over-parameterization, and linear convergence jointly enforce the (operator) norms of parameters upper bounded by some constants and close to their initialization. Accordingly, we can use this property to show that the operator norm of A is upper bounded and the spectral property of the Gram matrix is preserved throughout the training. Combining all these insights together, we can conclude that the random initialized gradient descent method with a constant step-size converges to a global minimum of the implicit neural network with ReLU activation.
A global convergence theory for deep ReLU implicit networks via over-parameterization
The main contributions of this paper are summarized as follows:
A global convergence theory for deep ReLU implicit networks via over-parameterization
(i) By scaling the weight matrix A with a fixed scalar γ, we show that the unique equilibrium point z * for each x always exists during the training if the parameters are randomly initialized, even for the nonlinear ReLU activation function. (ii) We analyze the gradient flow of implicit neural networks. Despite the non-smooth and nonconvexity of the objective function, the convergence to a global minimum at a linear rate is guaranteed if the implicit neural network is over-parameterized and the data is non-degenerate. (iii) Since gradient descent is discretized version of gradient flow, we can show gradient descent with fixed stepsize converges to a global minimum of implicit neural networks at a linear rate under the same assumptions made by the gradient flow analysis, as long as the stepsize is chosen small enough.
A global convergence theory for deep ReLU implicit networks via over-parameterization
Notation: For a vector x, x is the Euclidean norm of x. For a matrix A, A is the operator norm of A. If A is a square matrix, then λ min (A) and λ max (A) denote the smallest and largest eigenvalue of A, respectively, and λ max (A) ≤ A . We denote [n] {1, 2, · · · , n}.
A global convergence theory for deep ReLU implicit networks via over-parameterization
In this section, we provide a simple condition for the equilibrium equation (3) to be well-posed in the sense that the unique equilibrium point exists. Instead of backpropagating through all the intermediate iterations of a forward pass, we derive the gradients of trainable parameters by using the implicit function theorem. In this work, we make the following assumption on parameter initialization. Assumption 1 (Random Initialization). The entries A ij and W ij are randomly initialized by the standard Gaussian distribution N (0, 1), and u i and v i are randomly initialized by the symmetric Bernoulli or Rademacher distribution. Remark 2.1. This initialization is similar to the approaches widely used in practice (Glorot & Bengio, 2010;He et al., 2015). The result obtained in this work can be easily extended to the case where the distributions for A ij , W ij , u i , and v i are replaced by sub-Gaussian random variables.
A global convergence theory for deep ReLU implicit networks via over-parameterization
In a general implicit neural network, Eq. (3) is not necessarily well-posed, since it may admit zero or multiple solutions. In this work, we show that scaling the matrix A withγ = γ/ √ m guarantees the existence and uniqueness of the equilibrium point z * with random initialization. This follows from a foundational result in random matrix theory as restated in the following lemma. Lemma 2.1 (Vershynin (2018), Theorem 4.4.5). Let A be an m × n random matrix whose entries A ij are independent, zero-mean, and sub-Gaussian random variables. Then, for any t > 0, we have
A global convergence theory for deep ReLU implicit networks via over-parameterization
Here C > 0 is a fixed constant, and K = max i,j A ij ψ2 .
A global convergence theory for deep ReLU implicit networks via over-parameterization
Under Assumption 1, Lemma 2.1 implies that, with exponentially high probability, A ≤ c √ m for some constant c > 0. By scaling A by a positive scalarγ, we show that the transition Eq. (1) is a contraction mapping. Thus, the unique equilibrium point exists with detailed proof in Appendix A.1. Lemma 2.2. If A ≤ c √ m for some c > 0, then for any γ 0 ∈ (0, 1), the scalar γ min{γ 0 , γ 0 /c} uniquely determines the existence of the equilibrium z * for every x, and z ≤ 1 1−γ0 φ for all .
A global convergence theory for deep ReLU implicit networks via over-parameterization
Lemma 2.2 indicates that equilibria always exist if we can maintain the operator norm of the scaled matrix (γ/ √ m)A less than 1 during the training. However, the operator norms of matrix A are changed by the update of the gradient descent. It is hard to use a fixed scalar γ to scale the matrix A over all iterations, unless the operator norm of A is bounded. In Section 3, we will show A ≤ 2c √ m always holds throughout the training, provided that A(0) ≤ c √ m at initialization and the width m is sufficiently large. Thus, by using the scalar γ = min{γ 0 , γ 0 /(2c)} for any γ 0 ∈ (0, 1), equilibria always exist and the equilibrium equation Eq. (3) is well-posed.
A global convergence theory for deep ReLU implicit networks via over-parameterization
For a regular network with finite layers, one needs to store all intermediate parameters and apply backpropagation to compute the gradients. In contrast, for an implicit neural network, we can derive the formula of the gradients by using the implicit function theorem. Here, the equilibrium point z * is a root of the function f given by f (z, A, W ) z − σ (γAz + φ). The essential challenge is to ensure the partial derivative ∂f /∂z at z * is always invertible throughout the training. The following lemma shows that the partial derivative ∂f /∂z at z * always exists with the scalar γ, and the gradient derived in the lemma always exists. The gradient derivations for each trainable parameters are provided in the following lemma and the proof is provided in Appendix A.2. Lemma 2.3 (Gradients of an Implicit Neural Network). Define the scalar γ min{γ 0 , γ 0 /c}. If A ≤ c √ m for some constant c > 0, then for any γ 0 ∈ (0, 1), the following results hold:
A global convergence theory for deep ReLU implicit networks via over-parameterization
(i) The partial derivatives of f with respect to z, A, and W are ∂f ∂z
A global convergence theory for deep ReLU implicit networks via over-parameterization
whereγ γ/ √ m.
A global convergence theory for deep ReLU implicit networks via over-parameterization
(ii) For any vector v, the following inequality holds
A global convergence theory for deep ReLU implicit networks via over-parameterization
which further implies ∂f /∂z is invertible at the equilibrium point z * .
A global convergence theory for deep ReLU implicit networks via over-parameterization
(iii) The gradient of the objective function L with respect to A and W are given by
A global convergence theory for deep ReLU implicit networks via over-parameterization
where z i is the equilibrium point for the training data (x i , y i ), D i diag(σ (γAz i + φ i )), and E i diag(σ (W x i )).
A global convergence theory for deep ReLU implicit networks via over-parameterization
In this section, we establish the global convergence results of the gradient descent method in implicit neural networks. In Section 3.1, we first study the dynamics of the prediction induced by the gradient flow, that is, the gradient descent with infinitesimal step-size. We show that the dynamics of the prediction is controlled by a Gram matrix whose smallest eigenvalue is strictly positive over iterations with high probability. Based on the findings in gradient flow, we will show that the random initialized gradient descent method with a constant step-size converges to a global minimum at a linear rate in Section 3.2.
A global convergence theory for deep ReLU implicit networks via over-parameterization
The gradient flow is equivalent to the gradient descent method with an infinitesimal step-size. Thus, the analysis of gradient flow can serve as a stepping stone towards understanding discrete-time gradient-based algorithms. Following previous works on gradient flow of different machine learning models (Saxe et al., 2013;Du et al., 2019;Arora et al., 2018;Kawaguchi, 2021) the gradient flow of implicit neural networks is given by the following ordinary differential equations:
A global convergence theory for deep ReLU implicit networks via over-parameterization
where L(t) represents the value of the objective function L(θ) at time t.
A global convergence theory for deep ReLU implicit networks via over-parameterization
Our results relies on the analysis of the dynamics of predictionŷ(t). In particular, Lemma 3.1 shows that the dynamics of predictionŷ(t) is governed by the spectral property of a Gram matrix H(t).
A global convergence theory for deep ReLU implicit networks via over-parameterization
and Z(s) ∈ R n×m be the matrices whose rows are the training data x i , feature vectors φ i , and equilibrium points z i at time s, respectively. With scalar γ min{γ 0 , γ 0 /c} for any γ 0 ∈ (0, 1), the dynamics of predictionŷ(t) is given by
A global convergence theory for deep ReLU implicit networks via over-parameterization
where • is the Hadamard product (i.e., element-wise product), and matrices M (t) ∈ R n×n and Q(t) ∈ R n×n are defined as follows:
A global convergence theory for deep ReLU implicit networks via over-parameterization
Note that the matrix H(t) is clearly positive semidefinite since it is the sum of three positive semidefinite matrices. If there exists a constant λ > 0 such that λ min {H(t)} ≥ λ > 0 for all t, i.e., H(t) is positive definite, then the dynamics of the loss function L(t) satisfies the following inequality L(t) ≤ exp{−λt}L(0), which immediately indicates that the objective value L(t) is consistently decreasing to zero at a geometric rate. With random initialization, we will show that H(t) is positive definite as long as the number of parameters m is sufficiently large and no two data points are parallel to each other. In particular, by using the nonlinearity of the feature map φ, we will show that the smallest eigenvalue of the Gram matrix G(t) Φ(t)Φ(t) T is strictly positive over all time t with high probability. As a result, the smallest eigenvalue of H(t) is always strictly positive.
A global convergence theory for deep ReLU implicit networks via over-parameterization
Clearly, G(t) is a time-varying matrix. We first analyze its spectral property at its initialization. When t = 0, it follows from the definition of the feature vector φ in Eq. (2) that
A global convergence theory for deep ReLU implicit networks via over-parameterization
By Assumption 1, each vector w r (0) follows the standard multivariate normal distribution, i.e., w r (0) ∼ N (0, I d ). By letting m → ∞, we obtain the covariance matrix G ∞ ∈ R n×n as follows:
A global convergence theory for deep ReLU implicit networks via over-parameterization
Here G ∞ is a Gram matrix induced by the ReLU activation function and the random initialization.
A global convergence theory for deep ReLU implicit networks via over-parameterization
The following lemma shows that the smallest eigenvalue of G ∞ is strictly positive as long as no two data points are parallel. Moreover, later in Lemmas 3.3 and 3.4, we conclude that the spectral property of G ∞ is preserved in the Gram matrices G(0) and G(t) during the training, as long as the number of parameter m is sufficiently large.
A global convergence theory for deep ReLU implicit networks via over-parameterization
Proof. The proof follows from the Hermite Expansions of the matrix G ∞ and the complete proof is provided in Appendix A.4.
A global convergence theory for deep ReLU implicit networks via over-parameterization
Assumption 2 (Training Data). Without loss of generality, we can assume that each x i is normalized to have a unit norm, i.e.,
A global convergence theory for deep ReLU implicit networks via over-parameterization
In most real-world datasets, it is extremely rare that two data samples are parallel. If this happens, by adding some random noise perturbation to the data samples, Assumption 2 can still be satisfied. Next, we show that at the initialization, the spectral property of G ∞ is preserved in G(0) if m is sufficiently large. Specifically, the following lemma shows that if m =Ω(n 2 ), then G(0) has a strictly positive smallest eigenvalue with high probability. The proof follows from the standard concentration bound for Gaussian random variables, and we relegate the proof to Appendix A.5.
A global convergence theory for deep ReLU implicit networks via over-parameterization
, then with probability of at least
A global convergence theory for deep ReLU implicit networks via over-parameterization
During training, G(t) is time-varying, but it can be shown to be close to G(0) and preserve the spectral property of G ∞ , if the matrices W (t) has a bounded operator norm and it is not far away from W (0). This result is formally stated below and its proof is provided in Appendix A.6.
A global convergence theory for deep ReLU implicit networks via over-parameterization
The next lemma shows three facts: (1) The smallest eigenvalue of G(t) is strictly positive for all t ≥ 0;
A global convergence theory for deep ReLU implicit networks via over-parameterization
(2) The objective value L(t) converges to zero at a linear convergence rate; (3) The (operator) norms of all trainable parameters are upper bounded by some constants, which further implies that unique equilibrium points in matrices Z(t) always exist. We prove this lemma by induction, which is provided in Appendix A.7.
A global convergence theory for deep ReLU implicit networks via over-parameterization
then for any t ≥ 0, the following results hold:
A global convergence theory for deep ReLU implicit networks via over-parameterization
By using simple union bounds in Lemma 2.1 and 3.5, we immediately obtain the global convergence result for the gradent flow as follows.
A global convergence theory for deep ReLU implicit networks via over-parameterization
Theorem 3.1 (Convergence Rate of Gradient Flow). Suppose that Assumptions 1 and 2 hold. If we set the number of parameter m = Ω n 2 λ 2 0 log n δ and choose 0 < γ ≤ min{ 1 2 , 1 4c }, then with probability at least 1 − δ over the initialization, we have
A global convergence theory for deep ReLU implicit networks via over-parameterization
This theorem establishes the global convergence of the gradient flow. Despite the nonconvexity of the objective function L(θ), Theorem 3.1 shows that if m is sufficiently large, then the objective value is consistently decreasing to zero at a geometric rate. In particular, Theorem 3.1 requires m =Ω(n 2 ), which is similar or even better than recent results for the neural network with finite layers ( Table 1). These results do not apply in our case since we have infinitely many layers. By taking advantage of the nonlinear feature mapping function, we establish the global convergence for the gradient flow with m independent of depth h.
A global convergence theory for deep ReLU implicit networks via over-parameterization
In this section, we show that the randomly initialized gradient descent method with a fixed stepsize converges to a global minimum at a linear rate. With similar argument used in the analysis of gradient flow, we can show the (operator) norms of the training parameters are upper bounded by some constants. It is worth noting that, unlike the analysis of gradient flow, we do not have an explicit formula for the dynamics of predictionŷ(t) in the discrete time analysis. Instead, we have to show the difference between the equilibrium points Z(k) in two consecutive iterations are bounded. Based on this, we can further bound the changes in the predictionsŷ(k) between two consecutive iterations. Another challenge is to show the objective value consistently decreases over iterations.
A global convergence theory for deep ReLU implicit networks via over-parameterization
A general strategy is to show the objective function is (semi-)smooth with respect to parameter θ, and apply the descent lemma to the objective function (Nguyen & Mondelli, 2020; Allen-Zhu et al., Zou & Gu, 2019). In this section, we take advantage of the nonlinear feature mapping function in Eq. (4). Consequently, we are able to obtain a Polyak-Łojasiewicz-like condition (Karimi et al., 2016;Nguyen, 2021), which allows us to provide a much simpler proof.
A global convergence theory for deep ReLU implicit networks via over-parameterization
The following lemma establishes the global convergence for the gradient descent method with a fixed step-size when the operator norms of A(0) and W (0) are bounded and λ min (G(0)) > 0. The proof is proved in Appendix A.8. Lemma 3.6 (Gradient Descent Convergence Rate). Suppose
A global convergence theory for deep ReLU implicit networks via over-parameterization
By using simple union bounds to combine Lemma 2.1 and 3.6, we obtain the global convergence result for the gradient descent. Theorem 3.2 (Convergence Rate of Gradient Descent). Suppose that Assumption 1 and 2 hold. If we set m = Ω n 2 λ0 log n δ , 0 < γ ≤ min{ 1 2 , 1 4c }, and choose step-size α = O λ 0 /n 2 , then with probability at least 1 − δ over the initialization, we have 
A global convergence theory for deep ReLU implicit networks via over-parameterization
In this section, we use real-world datasets MNST, FashionMNST, CIFAR10, and SVHN to evaluate our theoretical findings. We initialize the entries of parameters A, W , u, and v by standard Gaussian or symmetric Bernoulli distribution independently as suggested in Assumption 1. For each dataset, we only use classes 0 and 1, and 500 samples are randomly drawn from each class to generate the training dataset with n = 1000 samples. All data samples are converted to gray scale and resized into a 28 × 28 pixel image. We also normalize each data to have unit norm. If two parallel samples are observed, we add a random Gaussian noise perturbation to one of them. Thus, Assumption 2 is also satisfied. We run 1000 epochs of gradient descent with a fixed step-size. We test three metrics with different width m. We first test how the extent of over-parameterization affects the convergence rates. Then, we test the relation between the extent of over-parameterization and the operator norms between matrix A(k) and its initialization. Note that the "operator norm" in the plots denotes the operator norm of the scaled matrix (γ/ √ m) A(k) . Third, we test the extent of over-parameterization and the performance of the trained neural network on the unseen test data. Similar to the training dataset, We randomly select 500 samples from each class as the test dataset.
A global convergence theory for deep ReLU implicit networks via over-parameterization
From Figure 1, the figures in the first column show that as m becomes larger, we have better convergence rates. The figures in the second column show that as m becomes larger, the neural networks achieve lower test loss. The figures in the third column show that the operator norms are slightly larger for larger m but overall the operator norms are approximately equal to its initialization. The bell curve from the classical bias-variance trade-off does not appear. This opens the door to a new research direction in implicit neural networks in the analyses of generalization error and bias-variance trade-off.
A global convergence theory for deep ReLU implicit networks via over-parameterization
Implicit models has been explored explored by the deep learning community for decades. For example, Pineda (1987) and ALMEIDA (1987) (2020) showed that (stochastic) gradient descent can attain global convergence for training a finite-layer neural network when the width m is a polynomial of the sample size n and the depth h. However, their results cannot be applied directly to implicit neural networks since implicit neural networks have infinite layers and the equilibrium equation may not be well-posed. Our work establishes the well-posedness of the equilibrium equation even if the width m is only square of the sample size n.
A global convergence theory for deep ReLU implicit networks via over-parameterization
In this paper, we provided a convergence theory for implicit neural networks with ReLU activation in the over-parameterization regime. We showed that the random initialized gradient descent method with fixed step-size converges to a global minimum of the loss function at a linear rate if the width m =Ω(n 2 ). In particular, by using a fixed scalar γ ∈ (0, 1) to scale the random initialized weight matrix A, we proved that the equilibrium equation is always well-posed throughout the training. By analyzing the gradient flow, we observe that the dynamics of the prediction vector is controlled by a Gram matrix whose smallest eigenvalue is lower bounded by a strictly positive constant as long as m =Ω(n 2 ). We envision several potential future directions based on the observations made in the experiments. First, we believe that our analysis can be generalized to implicit neural networks with other scaling techniques and initialization. Here, we use a scalar γ/ √ m to ensure the existence of the equilibrium point z * with random initialization. With an appropriate normalization, the global convergence for identity initialization can be obtained. Second, we believe that the width m not only improves the convergence rates but also the generalization performance. In particular, our experimental results showed that with a larger m value, the test loss is reduced while the classical bell curve of bias-variance trade-off is not observed. Proof. Let γ 0 ∈ (0, 1). Set γ min{γ 0 , γ 0 /c}. Denoteγ = γ/ √ m. Then
A global convergence theory for deep ReLU implicit networks via over-parameterization
Applying the above argument times, we obtain
A global convergence theory for deep ReLU implicit networks via over-parameterization
where we use the fact z 0 = 0. For any positive integers p, q with p ≤ q, we have
A global convergence theory for deep ReLU implicit networks via over-parameterization
is a Cauchy sequence. Since R m is complete, the equilibrium point z * is the limit of the sequence {z } ∞ =1 , so that z exists and is unique. Moreover, let q → ∞, then we obtain z p − z * ≤ γ p 1−γ φ , so that the fixed-point iteration converges to z linearly.
A global convergence theory for deep ReLU implicit networks via over-parameterization
Let p = 0 and q = , then we obtain z ≤ 1 1−γ0 φ .
A global convergence theory for deep ReLU implicit networks via over-parameterization
Proof.
A global convergence theory for deep ReLU implicit networks via over-parameterization
(i) To simplify the notations, we denote D diag(σ (γAz + φ)), and E diag(σ (W x)). The differential of f is given by
A global convergence theory for deep ReLU implicit networks via over-parameterization
Taking vectorization on both sides yields
A global convergence theory for deep ReLU implicit networks via over-parameterization
Therefore, the partial derivative of f with respect to z, A, and φ are given by
A global convergence theory for deep ReLU implicit networks via over-parameterization
It follows from the definition of the feature vector φ in Eq.
A global convergence theory for deep ReLU implicit networks via over-parameterization
(2) that
A global convergence theory for deep ReLU implicit networks via over-parameterization
Thus, the partial derivative of φ with respect to W is given by
A global convergence theory for deep ReLU implicit networks via over-parameterization
By using the chain rule, we obtain the partial derivative of f with respect to W as follows
A global convergence theory for deep ReLU implicit networks via over-parameterization
(ii) Let v be an arbitrary vector, and u be an arbitrary unit vector. The reverse triangle inequality implies that
A global convergence theory for deep ReLU implicit networks via over-parameterization
where (a) is due to |σ (v)| ≤ 1 and A op ≤ c √ m. Therefore, taking infimum on the left-hand side over all unit vector u yields the desired result.
A global convergence theory for deep ReLU implicit networks via over-parameterization
(iii) Since f (z * , A, W ) = 0, taking implicit differentiation of f with respect to A at z * gives us
A global convergence theory for deep ReLU implicit networks via over-parameterization
The results in part (i)-(ii) imply the smallest eigenvalue of ∂f ∂z z * is strictly positive, so that it is invertible. Therefore, we have
A global convergence theory for deep ReLU implicit networks via over-parameterization
Similarly, we obtain the partial derivative of z * with respect to W as follows
A global convergence theory for deep ReLU implicit networks via over-parameterization
To further simplify the notation, we denote z to be the equilibrium point z * by omitting the superscribe, i.e., z = z * . Letŷ = u T z + v T φ be the prediction for the training data (x, y). The differential ofŷ is given by
A global convergence theory for deep ReLU implicit networks via over-parameterization
The partial derivative ofŷ with respect to u, v, z, and φ are given by
A global convergence theory for deep ReLU implicit networks via over-parameterization
Let = 1 2 (ŷ − y) 2 . Then ∂ /∂ŷ = (ŷ − y). By chain rule, we have
A global convergence theory for deep ReLU implicit networks via over-parameterization
By using (19)-(20) and chain rule, we obtain
A global convergence theory for deep ReLU implicit networks via over-parameterization
and
A global convergence theory for deep ReLU implicit networks via over-parameterization
A.3 PROOF OF LEMMA 3.1
A global convergence theory for deep ReLU implicit networks via over-parameterization
Proof. Let z i denote the i-th equilibrium point for the i-the data sample x i . By using (19), (20), (26) and (27), we obtain the dynamics of the equilibrium point z i as follows
A global convergence theory for deep ReLU implicit networks via over-parameterization
By using (18) and 27, we obtain the dynamics of the feature vector φ i
A global convergence theory for deep ReLU implicit networks via over-parameterization
By chain rule, the dynamics of the predictionŷ i is given by
A global convergence theory for deep ReLU implicit networks via over-parameterization
Define the matrices M (t) ∈ R n×n and Q(t) ∈ R n×n as follows
A global convergence theory for deep ReLU implicit networks via over-parameterization
Let X ∈ R n×d , Φ(t) ∈ R n×m , and Z(t) ∈ R n×m be the matrices whose rows are the training data x i , feature vectors φ i , and equilibrium points z i at time t, respectively. The dynamics of the prediction vectorŷ is given by
A global convergence theory for deep ReLU implicit networks via over-parameterization
A.4 PROOF OF LEMMA 3.2
A global convergence theory for deep ReLU implicit networks via over-parameterization
To make the paper self-contained, we review the necessary background about the Hermite polynomials in this section. One can find each result in this section from any standard textbooks about functional analysis such as MacCluer (2008) We consider an L 2 -space defined by L 2 (R, dP ), where dP is the Gaussian measure, that is,
A global convergence theory for deep ReLU implicit networks via over-parameterization
Thus, L 2 (R, dP ) is a collection of functions f for which
A global convergence theory for deep ReLU implicit networks via over-parameterization
Lemma A.1. The ReLU activation σ ∈ L 2 (R, dP ).
A global convergence theory for deep ReLU implicit networks via over-parameterization
Proof. Note that
A global convergence theory for deep ReLU implicit networks via over-parameterization
For any functions f, g ∈ L 2 (R, dP ), we define an inner product
A global convergence theory for deep ReLU implicit networks via over-parameterization
Furthermore, the induced norm · is given by
A global convergence theory for deep ReLU implicit networks via over-parameterization
This L 2 space has an orthonormal basis with respect to the inner product defined above, called normalized probabilist's Hermite polynomials {h n (x)} ∞ n=0 that are given by
A global convergence theory for deep ReLU implicit networks via over-parameterization
The normalized probabilist's Hermite polynomials is an orthonormal basis of L 2 (R, dP ): h m , h n = δ mn .
A global convergence theory for deep ReLU implicit networks via over-parameterization
Proof. Note that D n (e −x 2 /2 ) = e −x 2 /2 P n (x) for a polynomial with degree of n and leading term is (−1) n x n . Thus, we can consider h n (
A global convergence theory for deep ReLU implicit networks via over-parameterization
There is no boundary terms because the super exponential decay of e −x 2 /2 at infinity. Since m < n, then D n (P m ) = 0 so that h m , h n =0. If m = n, then D n (P m ) = (−1) n n!. Thus, h n , h n = 1.
A global convergence theory for deep ReLU implicit networks via over-parameterization
Remark: Since {h n } is an orthonormal basis, for every f ∈ L 2 (R, dP ), we have
A global convergence theory for deep ReLU implicit networks via over-parameterization
in the sense that
A global convergence theory for deep ReLU implicit networks via over-parameterization
Proof. Note that
A global convergence theory for deep ReLU implicit networks via over-parameterization
Lemma A.4. Consider a Hilbert space H with inner product ·, · . If f n −f → 0 and g n −g → 0, then f, g = lim n→∞ f n , g n .
A global convergence theory for deep ReLU implicit networks via over-parameterization
Observe that
A global convergence theory for deep ReLU implicit networks via over-parameterization
Let n → ∞, then the continuity of · implies the desired result.
A global convergence theory for deep ReLU implicit networks via over-parameterization
Lemma A.5. Let {h n (x)} be the normalized probabilist's Hermite polynomials. For any fixed number t, we have
A global convergence theory for deep ReLU implicit networks via over-parameterization
Proof. First, we show f (x) = e xt−t 2 /2 ∈ H L 2 (R, dP ).
A global convergence theory for deep ReLU implicit networks via over-parameterization
Proof. Given fixed numbers s and t, we define two functions f (w) = e a,w t−t 2 /2 and g(w) = e b,w s−s 2 /2 . Let x = a, w and y = b, w . Then we have
A global convergence theory for deep ReLU implicit networks via over-parameterization
Define a Hilbert space H d = L 2 (R d , dP ), where dP is the multivariate Gaussian measure, equipped with inner product f, g
A global convergence theory for deep ReLU implicit networks via over-parameterization
Note that the LHS is also given by
A global convergence theory for deep ReLU implicit networks via over-parameterization
Since s and t are arbitrary numbers, matching the coefficients yields
A global convergence theory for deep ReLU implicit networks via over-parameterization
The result in this subsection is similar to the results in (Nguyen & Mondelli, 2020, Appendix D) and (Oymak & Soltanolkotabi, 2020, Appendix H). The key difference is the assumptions made on the training data. In particular, Oymak & Soltanolkotabi (2020) assumes the training data is δ-separable, i.e., min{ x i − x j , x i + x j } ≥ δ > 0 for all i = j, and Nguyen & Mondelli (2020) assumes the data x i follows some sub-Gaussian random variable, while we assume no two data are parallel to each other, i.e., x i x j for all i = j.
A global convergence theory for deep ReLU implicit networks via over-parameterization
Lemma A.7. Given an activation function σ, if σ ∈ L 2 (R, dP ) and x i = 1 for all i ∈ [n], then
A global convergence theory for deep ReLU implicit networks via over-parameterization
where • is elementwise product.
A global convergence theory for deep ReLU implicit networks via over-parameterization
Proof. Observe
A global convergence theory for deep ReLU implicit networks via over-parameterization
Note that the tensor product of x i and x i is
A global convergence theory for deep ReLU implicit networks via over-parameterization
Here we introduce the (row-wise) Khatri-Rao product of two matrices A ∈ R k×m , B ∈ R k×n . Then
A global convergence theory for deep ReLU implicit networks via over-parameterization
where A i * indicates the i-th row of matrix A. Therefore, the i-th row of X * · · · * X X * n is x i ⊗ · · · ⊗ x i . As a result, we obtain a more compact form of (31) as follows
A global convergence theory for deep ReLU implicit networks via over-parameterization
Lemma A.8. If σ(x) is a nonlinear function and |σ(x)| ≤ |x| and , then sup{n : σ, h n > 0} = ∞.
A global convergence theory for deep ReLU implicit networks via over-parameterization
Proof. It is equivalent to show σ(x) is not a finite linear combination of polynomials. We prove by contradiction. Suppose σ(x) = a 0 + a 1 x + · · · + a n x n . Since σ(0) = 0 = a 0 , then σ(x) = a 1 x + · · · + a n x n . Observe that lim x→∞ |σ(x)| |x| = lim x→∞ |a 1 x + · · · + a n x n | |x| = lim x→∞ a 1 + · · · + a n x n−1 , =∞ which contradicts |σ(x)| |x| ≤ 1 for all x = 0.
A global convergence theory for deep ReLU implicit networks via over-parameterization
Lemma A.9. If x i x j for all i = j, then there exists k 0 > 0 such that λ min (X * k )(X * k ) T > 0 for all k ≥ k 0 . Therefore, λ min (G ∞ ) > 0.
A global convergence theory for deep ReLU implicit networks via over-parameterization
Proof. To simplify the notation, denote K = (X * k ) T ∈ R kd×n . Since x i x j and x i = 1, then let δ max{| x i , x j |} = max{|cos θ ij |} and δ ∈ (0, 1), where θ ij is the angle between x i and x j . For any unit vector v ∈ R n , we have
A global convergence theory for deep ReLU implicit networks via over-parameterization
where the last equality is because x i = 1 and v = 1. Note that
A global convergence theory for deep ReLU implicit networks via over-parameterization
≤nδ k , by Cauchy-Schwart's inequlity.
A global convergence theory for deep ReLU implicit networks via over-parameterization
By inverse triangle inequality, we have
A global convergence theory for deep ReLU implicit networks via over-parameterization
Choose k 0 ≥ log n/ log(1/δ), then λ min {(X * k )(X * k ) T } > 0 for all k ≥ k 0 .
A global convergence theory for deep ReLU implicit networks via over-parameterization
A.5 PROOF OF LEMMA 3.3
A global convergence theory for deep ReLU implicit networks via over-parameterization
Proof. Since x i = 1 and w r (0) ∼ N (0,
A global convergence theory for deep ReLU implicit networks via over-parameterization
. Let X ir σ x T i w r (0) and Z ∼ N (0, 1), then for any |λ| ≤ 1/
A global convergence theory for deep ReLU implicit networks via over-parameterization
where the first inequality is due tot |σ(x)| ≤ |x|, and the last inequality is by using the numerical
A global convergence theory for deep ReLU implicit networks via over-parameterization
, we obtain E{X 2 ir λ 2 } ≤ 2. By using Markov's inequality, we have for any t ≥ 0
A global convergence theory for deep ReLU implicit networks via over-parameterization
Therefore X ir is a sub-Gaussian random variable with sub-Gaussian norm X i ψ2 ≤ 2 (Vershynin, 2018, Proposition 2.5.2). Then X ir X jr is a sub-exponential random variable with sub-exponential norm X ir X jr ψ1 ≤ 4 (Vershynin, 2018, Lemma 2.7.7). Observe that (0)], (Vershynin, 2018, Exercise 2.7.10) implies that G ij (0) − G ∞ ij is also a zero-mean sub-exponential random variable. It follows from the Bernstein's inequality that
A global convergence theory for deep ReLU implicit networks via over-parameterization
where c > 0 is some constant, and we use the facts X 2 ≤ X F , and P{
A global convergence theory for deep ReLU implicit networks via over-parameterization
A.6 PROOF OF LEMMA 3.4
A global convergence theory for deep ReLU implicit networks via over-parameterization
Proof. By using the 1-Lipschitz continuity of σ(x), we have
A global convergence theory for deep ReLU implicit networks via over-parameterization
A.7 PROOF OF LEMMA 3.5
A global convergence theory for deep ReLU implicit networks via over-parameterization
Proof. It suffices to show the result holds for γ = min{γ 0 , γ 0 /2c}, where γ 0 = 1/2. Note that Lemma 2.1 still holds if one chooses a larger c. Thus, we choose c √ λ 0 / X . We prove by the induction. Suppose that for 0 ≤ s ≤ t, the followings hold (i) λ min (G(s)) ≥ λ0 2 ,
A global convergence theory for deep ReLU implicit networks via over-parameterization
Solving the ordinary differential equation yields
A global convergence theory for deep ReLU implicit networks via over-parameterization
By using the inductive hypothesis W (s) ≤ 2c √ m, we have
A global convergence theory for deep ReLU implicit networks via over-parameterization
It follows from Lemma 2.2 with γ 0 = 1/2 that
A global convergence theory for deep ReLU implicit networks via over-parameterization
Since v i (0) follows symmetric Bernoulli distribution, then v(0) = √ m and we obtain
A global convergence theory for deep ReLU implicit networks via over-parameterization
where the last inequality is due to m = Ω c 2 n X 2 λ 3 0 ŷ(0) − y 2 and c √ λ 0 / X .
A global convergence theory for deep ReLU implicit networks via over-parameterization
Since u i (0) follows symmetric Bernoulli distribution, then u(0) = √ m and we obtain
A global convergence theory for deep ReLU implicit networks via over-parameterization
Note that
A global convergence theory for deep ReLU implicit networks via over-parameterization
Therefore, we obtain
A global convergence theory for deep ReLU implicit networks via over-parameterization
Moreover, it follows from Lemma 3.4 that λ min {G(t)} ≥ λ0 2 . Note that ∇ v L(s)
A global convergence theory for deep ReLU implicit networks via over-parameterization
where the last inequality we use the facts β < 1. By triangle inequality, we obtain
A global convergence theory for deep ReLU implicit networks via over-parameterization
which proves the result (iii). Similarly, we can upper bound the gradient of u
A global convergence theory for deep ReLU implicit networks via over-parameterization
so that
A global convergence theory for deep ReLU implicit networks via over-parameterization
and u(k) ≤ u(k) − u(0) + u(0) ≤ 32c √ n λ 0 ŷ(0) − y .
A global convergence theory for deep ReLU implicit networks via over-parameterization
The result (ii) is also obtained.
A global convergence theory for deep ReLU implicit networks via over-parameterization
By using the inductive hypothesis, we can upper bound the gradient of W as follows
A global convergence theory for deep ReLU implicit networks via over-parameterization
where the third inequality holds is because m is large, i.e., m = Θ c 2 n X 2 λ 3 0 ŷ(0) − y 2 . To simplify the notation, we assume m = Cc 2 n X 2 λ 3 0 ŷ(0) − y 2
A global convergence theory for deep ReLU implicit networks via over-parameterization
for some large number C > 0. Moreover, we obtain W (k + 1) ≤ W (k + 1) − W (0) + W (0) ≤ 2c √ m, Therefore, it follows from Lemma 3.4 that λ min {G(k + 1)} ≥ λ0 2 . Thus, the results (i) and (iv) are established.
A global convergence theory for deep ReLU implicit networks via over-parameterization
By using similar argument, we can upper bound the gradient of A as follows Note that
A global convergence theory for deep ReLU implicit networks via over-parameterization
Since m = Cc 2 n X 2 λ 3 0 ŷ(0) − y 2 and c, C > 0 are large enough, we have
A global convergence theory for deep ReLU implicit networks via over-parameterization
Therefore, the result (v) is obtained and the equilibrium points z i (k + 1) exists for all i ∈ [n].
A global convergence theory for deep ReLU implicit networks via over-parameterization
To establish the result (vi), we need to derive the bounds between equilibrium points Z(k) and feature vectors Φ(k). We firstly bound the difference between equilibrium points z i (k + 1) and z i (k). For any ≥ 1, we have
A global convergence theory for deep ReLU implicit networks via over-parameterization
where the first term can be bounded as follows γ A(k + 1)z i (k + 1) − A(k)z i (k) ≤γ A(k + 1) − A(k) z i (k + 1) +γ A(k) z i (k + 1) − z i (k) ≤γα ∇ A L(k) (4c) +γ A(k) z i (k + 1) − z i (k) ≤ 64αcn λ 0 m ŷ(0) − y 2 β k + (1/2) z i (k + 1) − z i (k) , and the second term is bounded as follows by using (33), 35, 40, 38, hypothesis (iii), and a large constant C 0 > 0
A global convergence theory for deep ReLU implicit networks via over-parameterization
≤αC 0 c 2 n ŷ(0) − y · β k . Therefore, we have ŷ(k + 1) −ŷ(k) ≤ αC 0 c 2 n ŷ(0) − y · β k ,
A global convergence theory for deep ReLU implicit networks via over-parameterization
where the scalar 2 is absorbed in C 0 and the constant C 0 is difference from C.
A global convergence theory for deep ReLU implicit networks via over-parameterization
Let g Z(k)u(k + 1) + Φ(k)v(k + 1). Then we have ŷ(k + 1) −ŷ(k),ŷ(k) − y = ŷ(k + 1) − g,ŷ(k) − y + g −ŷ(k),ŷ(k) − y .
A global convergence theory for deep ReLU implicit networks via over-parameterization
Let us bound each term individually. By using the Cauchy-Schwartz inequality, we have ŷ(k + 1) − g,ŷ(k) − y = (Z(k + 1) − Z(k))u(k + 1),ŷ(k) − y + (Φ(k + 1) − Φ(k))v(k + 1),ŷ(k) − y ≤ ( Z(k + 1) − Z(k) u(k + 1) + Φ(k + 1) − Φ(k) v(k + 1) ) ŷ(k) − y ≤αC 0 c 2 n ŷ(0) − y · β k ŷ(k) − y , by (34), 36, 38, 39 ≤αC 0 c 2 n · β 2k ŷ(0) − y 2 .
A global convergence theory for deep ReLU implicit networks via over-parameterization
By using ∇ u L(k) = Z(k) T (ŷ(k) − y), ∇ v L(k) = Φ(k) T (ŷ(k) − y) and λ min (G(k)) ≥ λ 0 /2, we get
A global convergence theory for deep ReLU implicit networks via over-parameterization
By combining the inequalities (41), 42, 43, we obtain ŷ(k + 1) − y 2 ≤ 1 − α λ 0 − C 0 c 2 n − αC 2 0 c 4 n 2 β 2k ŷ(0) − y 2
A global convergence theory for deep ReLU implicit networks via over-parameterization
where the second inequality is by α = O λ0 n 2 . This proves the result (vi) and complete the proof.
A Convergence Theory for Deep Learning via Over-Parameterization
Neural networks have demonstrated a great success in numerous machine-learning tasks [6,25,30,33,36,46,47]. One of the empirical findings is that neural networks, trained by first-order methods from random initialization, have a remarkable ability of fitting training data [57].
A Convergence Theory for Deep Learning via Over-Parameterization
From a capacity perspective, the ability to fit training data may not be surprising: modern neural networks are always heavily over-parameterized-they have (much) more parameters than the total number of training samples. Thus, in theory, there always exists parameter choices that achieve zero training error as long as the data does not degenerate.
A Convergence Theory for Deep Learning via Over-Parameterization
Yet, from an optimization perspective, the fact that randomly initialized first-order methods can find such an optimal solution on the training data is quite non-trivial : neural networks used in practice are often equipped with the ReLU activation function, which makes the training objective not only non-convex, but even non-smooth. Even the general convergence for finding approximate first and second-order critical points of a non-convex, non-smooth function is not fully understood [12], 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 face the problem of non-smoothness or non-convexity, and can converge to even a global minimal over the training set quite easily.
A Convergence Theory for Deep Learning via Over-Parameterization
Recently, 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 [11,19,22,35,43,50,55,59,60].
A Convergence Theory for Deep Learning via Over-Parameterization
In Li and Liang [34], it was shown 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 when 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 perfect accuracy can be extended to test data as well. As a separate note, over-parameterization is suggested as the possible key to avoid bad local minima by Safran and Shamir [44] even for two-layer neural networks.
A Convergence Theory for Deep Learning via Over-Parameterization
There are also results that go beyond two-layer neural networks but with limitations. Some consider deep linear neural networks without any activation functions [7,9,26,31]. The result of Daniely [14] applies to multi-layer neural network with ReLU activation, but is about the convex training process only with respect to the last layer. Daniely worked in a parameter regime where the weight changes of all layers except the last one make negligible contribution to the final output (and they form the so-called conjugate kernel). The result of Soudry and Carmon [52] shows that under over-parameterization and under random input perturbation, there is bad local minima for multi-layer neural networks. Their work did not show any provable convergence rate.
A Convergence Theory for Deep Learning via Over-Parameterization
In this paper, we study the following fundamental question Can DNN be trained close to zero training error efficiently under mild assumptions?
A Convergence Theory for Deep Learning via Over-Parameterization
If so, can the running time depend only polynomially in the number of layers?
A Convergence Theory for Deep Learning via Over-Parameterization
Motivation. In 2012 AlexNet [33] was born with 5 convolutional layers. Since then, the common trend in the deep learning community is to build network architectures that go deeper. In 2014, Simonyan and Zisserman [49] proposed a VGG network with 19 layers. Later, Szegedy et al. [54] proposed GoogleNet with 22 layers. In practice, we cannot make the network deeper by naively stacking layers together due to the so-called vanishing / exploding gradient issues. For this reason, in 2015, He et al. [30] proposed an ingenious deep network structure called Deep Residual Network (ResNet), with the capability of handling at least 152 layers. For more overview and variants of ResNet, we refer the readers to [21].
A Convergence Theory for Deep Learning via Over-Parameterization
Compared to the practical neural networks that go much deeper, the existing theory has been mostly around two-layer (thus one-hidden-layer) networks even just for the training process alone. It is natural to ask if we can theoretically understand how the training process has worked for multi-layer neural networks.
A Convergence Theory for Deep Learning via Over-Parameterization
In this paper, we extend the over-parameterization theory to multi-layer neural networks. We show that over-parameterized neural networks can indeed be trained by regular first-order methods to global minima (e.g. zero training error), as as long as the dataset is non-degenerate. We say that the dataset is non-degenerate if the data points are distinct. This is a minimal requirement since a dataset {(x 1 , y 1 ), (x 2 , y 2 )} with the same input x 1 = x 2 and different labels y 1 = y 2 can not be trained to zero error. We denote by δ the minimum (relative) distance between two training data points, and by n the number of samples in the training dataset. Now, consider an L-layer fully-connected feedforward neural network, each layer consisting of m neurons equipped with ReLU activation. We show that,
A Convergence Theory for Deep Learning via Over-Parameterization
• As long as m ≥ poly(n, L, δ −1 ), starting from random Gaussian initialized weights, gradient descent (GD) and stochastic gradient descent (SGD) find ε-error global minimum in 2 regression using at most T = poly(n, L, δ −1 ) log 1 ε iterations. This is a linear convergence rate. • Using the same network, if the task is multi-label classification, then GD and SGD find an 100% accuracy classifier on the training set in T = poly(n, L, δ −1 ) iterations.
A Convergence Theory for Deep Learning via Over-Parameterization
• Our result also applies to other Lipschitz-smooth loss functions, and some other network architectures including convolutional neural networks (CNNs) and residual networks (ResNet).
A Convergence Theory for Deep Learning via Over-Parameterization
Remark. This paper does not cover the the generalization of over-parameterized neural networks to the test data. We refer interested readers to some practical evidence [53,56] that deeper (and wider) neural networks actually generalize better. As for theoretical results, over-parameterized neural networks provably generalize at least for two-layer networks [4,34] and three-layer networks [4]. 1 A concurrent but different result. We acknowledge a concurrent work of Du et al. [18] which has a similar abstract to this paper, 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. [18] has two main results, one for fully-connected networks and the other for residual networks (ResNet). For fully-connected networks, their provable training time is exponential in the number of layers, leading to a claim of the form "ResNet has an advantage because ResNet is polynomial-time but fully-connected network is exponential-time." As we prove in this paper, fully-connected networks do have polynomial training time, so the logic behind their claim is wrong.
A Convergence Theory for Deep Learning via Over-Parameterization
For residual networks, their training time scales polynomial in 1 λ 0 , a parameter that depends on the minimal singular value of a complicated, L-times recursively-defined kernel matrix. It is not clear whether 1 λ 0 is small in practice. From the representation of our paper, it seems their 1 λ 0 could again be exponential in the number of layers. The authors of [18] have hidden this large factor 1 λ 0 from their stated complexity in the introduction.
A Convergence Theory for Deep Learning via Over-Parameterization
Their result is different from us in many other aspects. Their result only applies to smooth activation functions and thus cannot apply to the state-of-the-art ReLU activation. Their ResNet requires the value of weight initialization to be a function polynomial in λ (which is our δ); this can heavily depend on the input data. Their result only applies to gradient descent but not to SGD. Their result only applies to 2 loss but not others.
A Convergence Theory for Deep Learning via Over-Parameterization
Li and Liang [34] originally proved their result for the cross-entropy loss. Later, the "training accuracy" (not the testing accuracy) part of [34] was extended to the 2 loss [20]. The result of [20] claims to have adopted a learning rate m times larger than [34], but that is unfair because they have re-scaled the network by a factor of √ m. 2 Linear networks without activation functions are important subjects on its own. Besides the already cited references [7,9,26,31], 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 [1, 8, 16, 17, 27-29, 39, 42, 48].
A Convergence Theory for Deep Learning via Over-Parameterization
There is sequence of work about one-hidden-layer (multiple neurons) CNN [11,19,24,41,59]. 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 [11,19,59]. The other category [24,41] have figured out a weaker assumption or even removed that patch-disjoint assumption. On input data distribution, most relied on inputs being Gaussian [11,19,41,59], and some assumed inputs to be symmetrically distributed with identity covariance and boundedness [24].
A Convergence Theory for Deep Learning via Over-Parameterization
As for ResNet, Li and Yuan [35] proved that SGD learns one-hidden-layer residual neural networks under Gaussian input assumption. The techniques in [59,60] 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 [26] deep linear residual networks have no spurious local optima.
A Convergence Theory for Deep Learning via Over-Parameterization
If no assumption is allowed, neural networks have been shown hard in several different perspectives. Thirty years ago, Blum and Rivest [10] first proved that learning the neural network is NPcomplete. Stronger hardness results have been proved over the last decade [13,15,23,32,37,38,51].
A Convergence Theory for Deep Learning via Over-Parameterization
An Over-Parameterized RNN Theory. For experts in DNN theory, one may view this present paper as a deeply-simplified version of the recurrent neural network (RNN) paper [5] by the same set of authors. 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 between the two is that in feedforward neural networks, the weight matrices are different across layers, and thus independently randomly initialized; in contrast, in 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.
A Convergence Theory for Deep Learning via Over-Parameterization
So, the over-parameterized convergence theory of DNN is much simpler than that of RNN.
A Convergence Theory for Deep Learning via Over-Parameterization
We write this DNN result as a separate paper because: (1) not all the readers can easily notice that DNN is easier to study than RNN; (2) we believe the convergence of DNN is 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 [5]).
A Convergence Theory for Deep Learning via Over-Parameterization
We also note that the techniques of this paper can be combined with [5] to show the convergence of over-parameterized deep RNN. 2 Indeed, if one replaces any function f (x) with f x √ m then the gradient decreases by a factor of √ m and the needed movement in x increases by a factor of √ m. Thus, you can equivalently increase the learning rate by a factor of m.
A Convergence Theory for Deep Learning via Over-Parameterization
We use N (µ, σ) to denote the Gaussian distribution of mean µ and variance σ; and B(m, 1 2 ) to denote the binomial distribution with m trials and 1/2 success rate. We use v to denote Euclidean norms of vectors v, and M 2 , M F to denote spectral and Frobenius norms of matrices M. For a tuple
A Convergence Theory for Deep Learning via Over-Parameterization
We use φ(x) = max{0, x} to denote the ReLU function, and extend it to vectors v ∈ R m by letting φ(v) = (φ(v 1 ), . . . , φ(v m )). We use 1 event to denote the indicator function for event.
A Convergence Theory for Deep Learning via Over-Parameterization
The training data consist of vector pairs
A Convergence Theory for Deep Learning via Over-Parameterization
where each x i ∈ R d is the feature vector and y * i is the label of the i-th training sample. We assume without loss of generality that data are normalized so that x i = 1 and its last coordinate ( 3 We make the following separable assumption on the training data (motivated by [34]):
A Convergence Theory for Deep Learning via Over-Parameterization
To present the simplest possible proof, the main body of this paper only focuses on depth-L feedforward fully-connected neural networks with an 2 -regression task. Therefore, each y * i ∈ R d is a target vector for the regression task. We explain how to extend it to more general settings in Section 3.3 and the Appendix. For notational simplicity, we assume all the hidden layers have the same number of neurons, and our results trivially generalize to each layer having different number of neurons. Specifically, we focus on the following network
A Convergence Theory for Deep Learning via Over-Parameterization
where A ∈ R m×d is the weight matrix for the input layer, W ∈ R m×m is the weight matrix for the -th hidden layer, and B ∈ R d×m is the weight matrix for the output layer. For notational convenience in the proofs, we may also use h i,−1 to denote x i and W 0 to denote A. 
A Convergence Theory for Deep Learning via Over-Parameterization
As a result, we have
A Convergence Theory for Deep Learning via Over-Parameterization
We make the following standard choices of random initialization:
A Convergence Theory for Deep Learning via Over-Parameterization
Assumption 2.4. Throughout this paper we assume m ≥ Ω (δ −1 nL log m) 30 · d · log 2 ε −1 . To present the simplest proof, we did not try hard to improve such polynomial factors. 3 Without loss of generality, one can re-scale and assume xi ≤ 1/ √ 2 for every i ∈ [n]. Again, without loss of generality, one can pad each xi by an additional coordinate to ensure xi = 1/ √ 2. Finally, without loss of generality, one can pad each xi by an additional coordinate 1 √ 2 to ensure xi = 1. This last coordinate 1 √ 2 is equivalent to introducing a (random) bias term, because A( y
A Convergence Theory for Deep Learning via Over-Parameterization
In our proofs, the specific constant 1 √ 2 does not matter.
A Convergence Theory for Deep Learning via Over-Parameterization
Our regression objective is
A Convergence Theory for Deep Learning via Over-Parameterization
We also denote by loss i def = Bh i,L − y * i the loss vector for sample i. For simplicity, we only focus on training − → W in this paper and thus leave A and B at random initialization. Our techniques can be extended to the case when A, B and − → W are jointly trained.
A Convergence Theory for Deep Learning via Over-Parameterization
Using this notation, one can calculate the gradient of F ( − → W) as follows.
A Convergence Theory for Deep Learning via Over-Parameterization
Fact 2.6. The gradient with respect to the k-th row of W ∈ R m×m is
A Convergence Theory for Deep Learning via Over-Parameterization
To present our result in the simplest possible way, we choose to mainly focus on fully-connected L-layer neural networks with the 2 regression loss. We shall extend it to more general settings (such as convolutional and residual networks and other losses) in Section 3.3. Our main results can be stated as follows:
A Convergence Theory for Deep Learning via Over-Parameterization
Theorem 1 (gradient descent). Suppose m ≥ Ω poly(n, L, δ −1 ) · d · log 2 ε −1 . Starting from random initialization, with probability at least 1 − e −Ω(log 2 m) , gradient descent with learning rate η = Θ dδ poly(n,L)·m finds a point F ( − → W) ≤ ε in T = Θ poly(n, L, δ −1 ) log 1 ε iterations. This is known as the linear convergence rate because ε 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 d is the data input dimension and our result is independent of d. log 1 ε iterations. This is a nearly-linear convergence rate because T ∝ log 1 ε log 2 log 1 ε . The reason for the additional log 2 log 1 ε factor is because we have a 1 − e −Ω(log 2 m) high confidence bound. Remark. 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 ∝ 1 poly(ε) even for convex functions. There is no contradiction here. Imaging a strongly convex function f (x) = n i=1 f i (x) that has a common minimizer x * ∈ arg min x {f i (x)} for every i ∈ [n], then SGD is known to converge in a linear convergence rate. Here, the x and y axes represent the gradient direction ∇F (Wt) and the most negatively curved direction (found by Oja's method [2,3]), and the z axis represents the objective value.
A Convergence Theory for Deep Learning via Over-Parameterization
(b) A typical training curve for SGD, where the norm of (full) gradient decreases as objective value decreases. The gradient norm does tend to zero because the cross-entropy loss is used for multi-label classification (see Section 3.3). The training accuracy already becomes 99.8%. The used dataset is CIFAR10, and used the neural network is ResNet with 32 layers. Similar landscapes can also be spotted for AlexNet, VGG, DenseNet, etc. If the readers are interested in more details, we can include more experiments in the future revision.
A Convergence Theory for Deep Learning via Over-Parameterization
The main difficulty of this paper is to prove the following two technical theorems. The first one is about the gradient bounds for points that are sufficiently close to the random initialization: 
A Convergence Theory for Deep Learning via Over-Parameterization
Most notably, the second property of Theorem 3 says that as long as the objective is large, the gradient norm is also large. (See also Figure 1(a).) This means, when we are sufficiently close to the random initialization, there is no saddle point or critical point of any order. This gives us hope to find global minima of the objective F ( − → W). Unfortunately, Theorem 3 itself is enough. Even if we follow the negative gradient direction of F ( − → W), how can we guarantee that the objective truly decreases? Classically in optimization theory, one relies on the smoothness property (e.g. Lipscthiz smoothness [40]) to derive such objectivedecrease guarantee. Unfortunately, smoothness property at least requires the objective to be twice differentiable, but ReLU activation is not.
A Convergence Theory for Deep Learning via Over-Parameterization
To deal with this issue, we prove the following "semi-smoothness" property of the objective.
A Convergence Theory for Deep Learning via Over-Parameterization
Theorem 4 (semi-smoothness). With probability at least 1 − e −Ω(m/poly(L,log m)) over the random-
A Convergence Theory for Deep Learning via Over-Parameterization
poly(L,log m) ,
A Convergence Theory for Deep Learning via Over-Parameterization
Quite different from classical smoothness, we still have a first-order term − → W 2 on the right hand side, but classical smoothness only has a second-order term − → W 2 2 . As one can see in our final proofs, as m goes larger (so when we over-parameterize), the effect of the first-order term becomes smaller and smaller comparing to the second-order term. This brings Theorem 4 closer and closer, but still not identical, to the classical Lipschitz smoothness.
A Convergence Theory for Deep Learning via Over-Parameterization
The derivation of our main Theorem 1 and 2 from technical Theorem 3 and 3 is quite straightforward, and can be found in Section 9 and 10.
A Convergence Theory for Deep Learning via Over-Parameterization
Remark. In our proofs, we show that GD and SGD can converge fast enough and thus the weights stay close to random initialization, by a seemingly small spectral norm bound 1 poly(n,L,δ −1 ) . In fact this bound is large enough to totally change the outputs and fit the training data, because weights are randomly initialized (per entry) at around 1 √ m for m being large. In practice, we acknowledge that one often goes beyond this theory-predicted spectral-norm boundary. However, quite interestingly, we still observe Theorem 3 and 4 happen in practice at least for vision tasks. In Figure 1(a), we show the typical landscape near a point − → W on the SGD training trajectory. The gradient is sufficiently large and going in its direction can indeed decrease the objective; in contrast, though the objective is non-convex, the negative curvature of its "Hessian" is not significant comparing to gradient. From Figure 1(a) we also see that the objective function is sufficiently smooth (at least in the two interested dimensions that we plot).
A Convergence Theory for Deep Learning via Over-Parameterization
Our proof to the Theorem 3 and 4 mostly consist of the following steps.
A Convergence Theory for Deep Learning via Over-Parameterization
Step 1: properties at random initialization. Let − → W = − → W (0) be at random initialization and h i, and D i, be defined with respect to − → W. We first show that forward propagation neither explode or vanish. That is, h i, ≈ 1 for all i ∈ [n] and ∈ [L]. This is basically because for a fixed y, we have Wy 2 is around 2, and if its signs are sufficiently random, then ReLU activation kills half of the norm, that is φ(Wy) ≈ 1. Then applying induction finishes the proof.
A Convergence Theory for Deep Learning via Over-Parameterization
Analyzing forward propagation is not enough. We also need spectral norm bounds on the backward matrix BD i,L W L · · · D i,a W a 2 ≤ O( m/d), and on the intermediate matrix
A Convergence Theory for Deep Learning via Over-Parameterization
. Note that if one naively bounds the spectral norm by induction, then D i,a W a 2 ≈ 2 and it will exponentially blow up! Our more careful analysis ensures that even when L layers are stacked together, there is no exponential blow up in L.
A Convergence Theory for Deep Learning via Over-Parameterization
The final lemma in this step proves that, as long as x i − x j ≥ δ, then for each layer ∈ [L] it also satisfies h i, − h j, ≥ Ω(δ). This can be proved by a careful induction. Details are in Section 4.
A Convergence Theory for Deep Learning via Over-Parameterization
Step 2: stability after adversarial perturbation. We show that for every − → W that is "close" to initialization, meaning W − W 
A Convergence Theory for Deep Learning via Over-Parameterization
is at most O(ωL 5/2 ). We emphasize here that − → W may depend on the randomness of W (0) so one cannot use union bound. We call this "forward stability", and it is one of the most technical proof of this paper.
A Convergence Theory for Deep Learning via Over-Parameterization
Another main result in this step is to show that the backward matrix BD i,L W L · · · D i,a W a does not change by more than O(ω 1/3 L 2 m/d) in spectral norm. (Recall that in the Step 1 we shown that this matrix is of spectral norm O( m/d); thus as long as ω 1/3 L 2 1, this change is somewhat negligible. Details are in Section 5.
A Convergence Theory for Deep Learning via Over-Parameterization
Step 3: gradient bound. The hard part of Theorem 3 is to show gradient lower bound. For this purpose, recall from Fact 2.6 that each term in the gradient can be written as D i, (Back i, +1 loss i )h i, −1 where the backward matrix is applied to a loss vector loss i . To show that this is large, intuitively, one wishes to show (Back i, +1 loss i ) and h i, −1 are both vectors with large Euclidean norm. However, the main difficulty is that in calculating gradient, different samples i ∈ [n] may form different gradient matrices and, when summing together, they could in principle each other and possibly even form a zero matrix. To deal with this issue, we use h i, − h j, ≥ Ω(δ) from Step 1. In other words, even if the gradient matrix with respect to one sample is fixed, that with respect to other samples still have sufficient randomness so as the final gradient matrix will not be zero. This idea comes from the prior work [34] and helps us prove Theorem 3. 4 Details in Appendix 6 and 7.
A Convergence Theory for Deep Learning via Over-Parameterization
Step 4: smoothness. In order to prove Theorem 4, one needs to argue, if we are currently at − → W and perturb it by − → W , then how much does the objective change in second and higher order terms. This is different from our stability theory in Step 2, because Step 2 is regarding having a
A Convergence Theory for Deep Learning via Over-Parameterization
This is proportional to the small perturbation W 2 so, along with other properties to prove, ensures smoothness. This explains Theorem 4 and details are in Section 8.
A Convergence Theory for Deep Learning via Over-Parameterization
Our Step 1 through Step 4 in Section 3.2 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. 5 Different loss functions. There is absolutely no need to restrict our attention only to 2 regression loss. We prove in Appendix A that, for any Lipschitz-smooth loss function f ):
A Convergence Theory for Deep Learning via Over-Parameterization
• If f is cross-entropy for multi-label classification, then we achieve 100% training accuracy in at most T = O(n 6 L 2 /δ 2 ) iterations.
A Convergence Theory for Deep Learning via Over-Parameterization
• If f is gradient dominant (a.k.a. Polyak-Lojasiewicz) but possibly non-convex, we still have linear convergence. 6
A Convergence Theory for Deep Learning via Over-Parameterization
• If f is convex, then we have convergence rate
A Convergence Theory for Deep Learning via Over-Parameterization
Convolutional neural networks (CNN). There are lots of different ways to design CNN and each of them may require somewhat different proofs. In Appendix B, we study the case when 4 This is the only technical idea that we borrowed from Li and Liang [34], which is the over-parameterization theory for 2-layer neural networks. 5 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 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. 6 Note that the loss function when combined with the neural network together f (Bhi,L) is not gradient dominant. Therefore, one cannot apply classical theory on gradient dominant functions to derive our same result. 7 Again, this cannot be derived from classical theory of finding approximate saddle points for non-convex functions, because weights − → W with small ∇f (Bhi,L) is a very different (usually much harder) task comparing to having small gradient with respect to − → W for the entire composite function f (Bhi,L).
A Convergence Theory for Deep Learning via Over-Parameterization
A, W 1 , . . . , W L−1 are convolutional while W L and B are fully connected. We assume for notational simplicity that each hidden layer has d points each with m channels. (In vision tasks, a point is a pixel). In the most general setting, these values d and m can vary across layers. Our Theorem 5 says that, as long as m is polynomially large, GD and SGD find an ε-error solution for 2 regression in T = poly(n,L,d)
A Convergence Theory for Deep Learning via Over-Parameterization
There are lots of different ways to design ResNet and each of them may require somewhat different proofs. In symbols, between two layers, one may study
A Convergence Theory for Deep Learning via Over-Parameterization
Since the main purpose here is to illustrate the generality of our techniques but not to attack each specific setting, in Appendix C, we choose to consider the simplest residual setting h = φ(h −1 + Wh −1 ) (that was also studied for instance by theoretical work [26]). With appropriately chosen random initialization, our Theorem C shows that one can also have linear convergence rate T = O n 6 L 2 δ 2 log 1 ε in the over-parameterized setting.
A Convergence Theory for Deep Learning via Over-Parameterization
Throughout this section we assume − → W, A and B are randomly generated according to Def. 2.3. The diagonal sign matrices D i, are also determined according to this random initialization.
A Convergence Theory for Deep Learning via Over-Parameterization
Remark. Lemma 4.1 is in fact trivial to prove if the allowed failure probability is instead e −Ω(mε 2 /L 2 ) (by applying concentration inequality layer by layer).
A Convergence Theory for Deep Learning via Over-Parameterization
Before proving Lemma 4.1 we note a simple mathematical fact:
A Convergence Theory for Deep Learning via Over-Parameterization
Then, • |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
A Convergence Theory for Deep Learning via Over-Parameterization
Proof of Fact 4.2. We assume each vector W i is generated by first generating a gaussian vector g ∼ N (0, 2I m ) and then setting W i = ±g where the sign is chosen with half-half probability. Now, | W i , h | = | g, h | only depends on g, and is in distribution identical to |N (0, 2 h 2 m )|. Next, after the sign is determined, the indicator 1 W i ,h+q ≥0 is 1 with half probability and 0 with another half. Therefore, |v i | satisfies the aforementioned distribution. As for v 2 , letting ω ∈ {0, 1, . . . , m} be the variable indicator how many indicators are 1, then ω ∼ B(m, 1/2) and m v 2 2 h 2 ∼ χ 2 ω .
A Convergence Theory for Deep Learning via Over-Parameterization
Proof of Lemma 4.1. We only prove Lemma 4.1 for a fixed i ∈ [n] and ∈ {0, 1, 2, . . . , L} because we can apply union bound at the end. Below, we drop the subscript i for notational convenience, and write h i, and x i as h and x respectively.
A Convergence Theory for Deep Learning via Over-Parameterization
According to Fact 4.2, fixing any h −1 = 0 and letting W be the only source of randomness, we have m 2 ∆ ∼ χ 2 ω where ω ∼ B(m, 1/2). For such reason, for each ∆ , we can write ∆ = ∆ ,ω where m 2 ∆ ,ω ∼ χ 2 ω and ω ∼ B(m, 1/2). In the analysis below, we condition on the event that ω ∈ [0.4m, 0.6m]; this happens with probability ≥ 1 − e −Ω(m) for each layer ∈ [L]. To simplify our notations, if this event does not hold, we set ∆ = 1.
A Convergence Theory for Deep Learning via Over-Parameterization
Combining everything together, along with the fact that
A Convergence Theory for Deep Learning via Over-Parameterization
Subgaussian Tail. By standard tail bound for chi-square distribution, we know that
A Convergence Theory for Deep Learning via Over-Parameterization
Since we only need to focus on ω ≥ 0.4m, this means
A Convergence Theory for Deep Learning via Over-Parameterization
On the other hand, by Chernoff-Hoeffding bound, we also have
A Convergence Theory for Deep Learning via Over-Parameterization
This implies,
A Convergence Theory for Deep Learning via Over-Parameterization
Now, let us make another simplification: define ∆ = ∆ if | log ∆ | ≤ 1 4 and ∆ = 1 otherwise. In this way, (4.2) implies that X = log ∆ is an O(m)-subgaussian random variable.
A Convergence Theory for Deep Learning via Over-Parameterization
Concentration. Using martingale concentration on subgaussian variables (see for instance [45]), we have for ε ∈ (0, 1],
A Convergence Theory for Deep Learning via Over-Parameterization
Since with probability ≥ 1 − Le −Ω(m) it satisfies ∆ = ∆ for all ∈ [L], combining this with (4.1), we have
A Convergence Theory for Deep Learning via Over-Parameterization
Proof. Again we prove the lemma for fixed i, a and b because we can take a union bound at the end. We drop the subscript i for notational convenience.
A Convergence Theory for Deep Learning via Over-Parameterization
(a) Let z a−1 be any fixed unit vector, and define z = D W · · · D a W a z a−1 . According to Fact 4.2 again, fixing any z −1 and letting W be the only source of randomness, defining ∆ def = z 2 z −1 2 , we have that m 2 ∆ is distributed according to a χ 2 ω where ω ∼ B(m, 1 2 ). Therefore, we have
A Convergence Theory for Deep Learning via Over-Parameterization
Using exactly the same proof as Lemma 4.1, we have
A Convergence Theory for Deep Learning via Over-Parameterization
taking ε-net, we know that with probability at least e −Ω(m/L) , it satisfies
A Convergence Theory for Deep Learning via Over-Parameterization
for all vectors u whose coordinates are zeros outside M . Now, for an arbitrary unit vector v ∈ R m , we can decompose it as v = u 1 + · · · + u N where N = O(L), each u j is non-zero only at O(m/L) coordinates, and the vectors u 1 , . . . , u N are non-zeros on different coordinates. We can apply (4.3) for each each such u j and triangle inequality. This gives
A Convergence Theory for Deep Learning via Over-Parameterization
(b) The proof of Lemma 4.3b is the same as Lemma 4.3a, except to take ε-net over all O m L log msparse vectors u and then applying union bound.
A Convergence Theory for Deep Learning via Over-Parameterization
(c) Similar to the proof of Lemma 4.3a, for any fixed vector v, we have that with probability at least 1 − e −Ω(m/L) (over the randomness of W b−1 , . . . , W 1 , A),
A Convergence Theory for Deep Learning via Over-Parameterization
Conditioning on this event happens, using the randomness of W b , we have for each fixed vector u ∈ R m , we have 
A Convergence Theory for Deep Learning via Over-Parameterization
Back to the case when v is an arbitrary vector, we can partition
A Convergence Theory for Deep Learning via Over-Parameterization
By applying (4.4) for N times and using triangle inequality, we have
A Convergence Theory for Deep Learning via Over-Parameterization
(d) We apply the same proof as Lemma 4.3c with minor changes to the parameters. We can show with probability at least 1 − e −Ω(m/L) (over the randomness of W b−1 , . . . , W 1 , A), for a fixed vector v ∈ R m :
A Convergence Theory for Deep Learning via Over-Parameterization
Further using the randomness of W b , we have that conditioning on the above event, fixing any u ∈ R m , with probability at least 1 − e −Ω(s log m) over the randomness of W b :
A Convergence Theory for Deep Learning via Over-Parameterization
Finally, taking ε-net over all possible vectors u, v that are s sparse, we have the desired result. 
A Convergence Theory for Deep Learning via Over-Parameterization
With probability at least ≥ 1 − e −Ω(m/L) , for all i ∈ [n], 1 ≤ a ≤ L,
A Convergence Theory for Deep Learning via Over-Parameterization
Proof. (a) The proof follows the same idea of Lemma 4.3 (but choosing b = L). Given any fixed vector u, we have with probability at least 1 − e −Ω(m/L) (over the randomness of W L , . . . , W 1 , A),
A Convergence Theory for Deep Learning via Over-Parameterization
Conditioning on this event happens, using the randomness of B (recall each entry of B follows from N (0, 1 d )), we have for each fixed vector u ∈ R m ,
A Convergence Theory for Deep Learning via Over-Parameterization
Finally, one can take ε-net over all s-sparse vectors u ∈ R m and all vectors v ∈ R d and apply union bound.
A Convergence Theory for Deep Learning via Over-Parameterization
(b) The proof is identical to Lemma 4.3c, except the fact that each entry of B follows from N (0, 1 d ) instead of N (0, 2 m ). . There exists some constant C > 1 so that, if δ ≤ 1 CL , x 1 = · · · = x n = 1 and x i − x j ≥ δ for every pair i, j ∈ [n], then with probability at least 1 − e −Ω(δ 6 m/L) , we have:
A Convergence Theory for Deep Learning via Over-Parameterization
Proof of Lemma 4.5. We first apply Lemma 4.1 to show that h i, ∈ [1 − δ 3 /10, 1 + δ 3 /10]. Next we prove Lemma 4.5 by induction.
A Convergence Theory for Deep Learning via Over-Parameterization
In the base case of = −1, since x i − x j ≥ δ by our Assumption 2.1 and without loss of generality x i = 1 and (x i ) d = 1 √ 2 , we already have
A Convergence Theory for Deep Learning via Over-Parameterization
Suppose h i, −1 and h j, −1 are fixed and satisfies (I−
A Convergence Theory for Deep Learning via Over-Parameterization
and the randomness of the two terms are independent. In particular, we can write
A Convergence Theory for Deep Learning via Over-Parameterization
where g 2 ∼ N (0, 2 m I) is independent of g 1 . Applying Claim 4.6 for each coordinate k ∈ [m] (and re-scaling by
A Convergence Theory for Deep Learning via Over-Parameterization
Applying Chernoff bound (on independent subgaussian random variables), we have with probability
A Convergence Theory for Deep Learning via Over-Parameterization
) . Since h i, and h j, are close to 1, we have
A Convergence Theory for Deep Learning via Over-Parameterization
The following mathematical fact is needed in the proof of Lemma 4.5. Its proof is by carefully integrating the PDF of Gaussian distribution.
A Convergence Theory for Deep Learning via Over-Parameterization
Claim 4.6. Given g 1 , g 2 ∼ N (0, 2), constant α ∈ R and δ ∈ [0, 1 6 ], we have E
A Convergence Theory for Deep Learning via Over-Parameterization
Proof of Claim 4.6. We first tackle two easy cases.
A Convergence Theory for Deep Learning via Over-Parameterization
Suppose a < 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
A Convergence Theory for Deep Learning via Over-Parameterization
Therefore, we have if a < 3 4 then the expectation is at least 0.03. For similar reason, if a > 5 4 we also have the expectation is at least 0.03. In the remainder of the proof, we assume α ∈ 3 4 , 5 4 . If g 1 ≥ 0, we have
A Convergence Theory for Deep Learning via Over-Parameterization
π . 8 More specifically, we can let
A Convergence Theory for Deep Learning via Over-Parameterization
Overall, we have
A Convergence Theory for Deep Learning via Over-Parameterization
It is easy to see that, as long as δ ≤ α, we always have 
A Convergence Theory for Deep Learning via Over-Parameterization
Define diagonal matrices D
A Convergence Theory for Deep Learning via Over-Parameterization
i, ∈ R m×m and D i, ∈ R m×m by letting (D  Proof of Lemma 5.2. In our proof below, we drop the subscript with respect to i for notational simplicity, and one can always take a union bound over all possible indices i at the end. Using Lemma 4.1, we can first assume that h (0) , g (0) ∈ [ 2 3 , 4 3 ] for all . This happens with probability at least 1 − e −Ω(m/L) . We also assume
A Convergence Theory for Deep Learning via Over-Parameterization
We shall inductively prove Lemma 5.2. In the base case = 0, we have g = 0 so all the statements holds. In the remainder of the proof, we assume that Lemma 5.2 holds for − 1 and we shall prove the three statements for layer . We first carefully rewrite:
A Convergence Theory for Deep Learning via Over-Parameterization
Above, inequality x uses Lemma 4.3a and D (0) a−1 + D a−1 2 = D a−1 2 ≤ 1; and inequality y has used g (0) ≤ 2 and our inductive assumption Lemma 5.2c. By triangle inequality, we have
A Convergence Theory for Deep Learning via Over-Parameterization
We next look at each term in (♥). For each a = 2, 3, . . . , , we let And therefore by triangle inequality we can write
A Convergence Theory for Deep Learning via Over-Parameterization
Together with the upper bound on − → err 1 , we have − →
A Convergence Theory for Deep Learning via Over-Parameterization
Therefore, when ω is sufficiently small, the above term is at most 4c 1 L 1.5 ω. This finishes the proof of Lemma 5.2a for layer . Finally,
A Convergence Theory for Deep Learning via Over-Parameterization
• Lemma 5.2b is due to (5.1),
A Convergence Theory for Deep Learning via Over-Parameterization
• g part of Lemma 5.2c is a simple corollary of Lemma 5.2a, and
A Convergence Theory for Deep Learning via Over-Parameterization
• h part of Lemma 5.2c is due to h = D g + D g together with the bound on g and the bound on D g from Lemma 5.2b.
A Convergence Theory for Deep Learning via Over-Parameterization
Claim 5.3. Suppose W (0) ∈ R m×m is a random matrix with entries drawn i.i.d. from N 0, 2 m , and suppose ωL 3/2 ≤ O(1). With probability at least 1 − e −Ω(mω 2/3 L) , the following holds.
A Convergence Theory for Deep Learning via Over-Parameterization
For all unit vector h (0) ∈ R m , and for all g ∈ R m that can be written as
A Convergence Theory for Deep Learning via Over-Parameterization
Corollary 5.4. In particular, if g 1 ≤ O(ωL 3/2 ) and g 2 ∞ ≤ O ω 2/3 L m 1/2 , then x 0 ≤ O(mω 2/3 L) and
A Convergence Theory for Deep Learning via Over-Parameterization
x ≤ O(ωL 3/2 ) .
A Convergence Theory for Deep Learning via Over-Parameterization
Proof of Claim 5.3. We first observe g (0) = W (0) h (0) follows from N 0, 2I m regardless of the choice of h (0) . Therefore, in the remainder of the proof, we just focus on the randomness of g (0) .
A Convergence Theory for Deep Learning via Over-Parameterization
We also observe that (D ) j,j is non-zero for some diagonal j ∈ [m] only if
A Convergence Theory for Deep Learning via Over-Parameterization
m be a parameter to be chosen later. We shall make sure that g 2 ∞ ≤ ξ/2.
A Convergence Theory for Deep Learning via Over-Parameterization
• We denote by S 1 ⊆ [m] the index sets where j satisfies |(g (0) ) j | ≤ ξ. Since we know (g (0) ) j ∼ N (0, 2/m), we have Pr[|(g (0) ) j | ≤ ξ] ≤ O (ξ √ m) for each j ∈ [m]. Using Chernoff bound for all j ∈ [m], we have with probability at least 1 − e −Ω(m 3/2 ξ) ,
A Convergence Theory for Deep Learning via Over-Parameterization
Now, for each j ∈ S 1 such that x j = 0, we must have |x j | = |(g (0) + g 1 + g 2 ) j | ≤ |(g 1 ) j | + 2ξ so we can calculate the 2 norm of x on S 1 :
A Convergence Theory for Deep Learning via Over-Parameterization
• We denote by S 2 ⊆ [m] \ S 1 the index set of all j ∈ [m] \ S 1 where x j = 0. Using (5.2), we have for each j ∈ S 2 :
A Convergence Theory for Deep Learning via Over-Parameterization
Now, for each j ∈ S 2 where x j = 0, we know that the signs of (g (0) + g 1 + g 2 ) j and (g (0) ) j are opposite. Therefore, we must have
A Convergence Theory for Deep Learning via Over-Parameterization
From above, we have
A Convergence Theory for Deep Learning via Over-Parameterization
Choosing ξ = max{2 g 2 ∞ , Θ(  
A Convergence Theory for Deep Learning via Over-Parameterization
In other words, vector y can be written as y = y 1 + y 2 where y 2 ∞ ≤ β and y 1 2 ≤ O(qβ 2 log q). Finally, we want to take ε-net over all s-sparse inputs x. This requires β 2 qm ≥ Ω(s log m), so we can choose q = Θ s log m mβ 2 = Θ(s). • for every perturbation matrices W 1 , . . . ,
A Convergence Theory for Deep Learning via Over-Parameterization
Proof. For notational simplicity we ignore subscripts in i in the proofs. In order to bound the spectral norm of W
A Convergence Theory for Deep Learning via Over-Parameterization
a , by triangle inequality, we can expend it into 2 b−a matrices and bound their spectral norms individually. Each such matrix can be written as (ignoring the subscripts) (W (0) D (0) · · · W (0) D 0/1 )D (D 0/1 W (0) D (0) · · · W (0) D 0/1 )D · · · D (D 0/1 W (0) D (0) · · · W (0) ) (5.4) Therefore, it suffices for us to bound the spectral norm of the following four types of matrices:
A Convergence Theory for Deep Learning via Over-Parameterization
• W (0) D (0) · · · W (0) D 0/1 , such matrix has spectral norm at most 2 owing to Lemma 4.3b; Together, we have
A Convergence Theory for Deep Learning via Over-Parameterization
(b) In order to bound the spectral norm of (W
A Convergence Theory for Deep Learning via Over-Parameterization
a +W a ), by triangle inequality, we can expend it into 2 b−a+1 matrices in terms of W and bound their spectral norms individually. Each such matrix can be written as (ignoring the subscripts, and denotingD = D (0) + D ) (W (0)D · · · W (0)D )W (DW (0) · · · W (0)D ) · · · W (DW (0) · · ·DW (0) ) Moreover, from Lemma 5.6a, we know the following three types of matrices • for every perturbation matrices W i,1 , . . . ,
A Convergence Theory for Deep Learning via Over-Parameterization
Proof. For notational simplicity we ignore subscripts in i in the proofs. Ignoring the subscripts for cleanness, we have
A Convergence Theory for Deep Learning via Over-Parameterization
Throughout this section we assume − → W, A and B are randomly generated according to Def. 2.3. The diagonal sign matrices D i, are also determined according to this random initialization.
A Convergence Theory for Deep Learning via Over-Parameterization
Recall we have defined Back i, def = BD i,L W L · · · D i, W ∈ R d×m . In this section, we introduce the following notion Definition 6.1. For any vector tuple v = (v 1 , . . . , v n ) ∈ (R d ) n (viewed as a fake loss vector), for each ∈ [L], we define
A Convergence Theory for Deep Learning via Over-Parameterization
Our main lemma of this section is the following. 
A Convergence Theory for Deep Learning via Over-Parameterization
For each i ∈ [n], ∈ [L], we can calculate that
A Convergence Theory for Deep Learning via Over-Parameterization
where inequality x uses Lemma 4.4b and Lemma 4.1 with high probability. Applying triangle inequality with respect to all ∈ [L], taking square on both sides, and summing up over all i ∈ [n] finish the proof.
A Convergence Theory for Deep Learning via Over-Parameterization
For analysis purpose, after h is fixed (so after fixing the randomness of A, W 1 , . . . , W L−1 ), we redefine W L h = √ 1 − θ 2 g 1 + θ g 2 where g 1 and g 2 are generated independently from N (0, 2I m ). We can do so because the two sides are equal in distribution. In other words, we can set
A Convergence Theory for Deep Learning via Over-Parameterization
then we have W L = W L + W L . In particular, the randomness of W L and W L are independent.
A Convergence Theory for Deep Learning via Over-Parameterization
In the remainder of the proof, let us choose θ def = δ 5n ≤ 1 5 . We first make two technical claims, and the proof of the first one can be found in Section 6.2.1.
A Convergence Theory for Deep Learning via Over-Parameterization
and v, we have
A Convergence Theory for Deep Learning via Over-Parameterization
Using Chernoff bound we have the desired claim.
A Convergence Theory for Deep Learning via Over-Parameterization
Combining Claim 6.4 and Claim 6.5, we can obtain a set N ⊆ [m] satisfying
A Convergence Theory for Deep Learning via Over-Parameterization
Let us fix the randomness of W L so that N is fixed. Let k be any index in N . We can write
A Convergence Theory for Deep Learning via Over-Parameterization
The only remaining source of randomness comes from W L = θ g 2 h .
A Convergence Theory for Deep Learning via Over-Parameterization
Recalling that θ = 1 5n and g 2 ∼ N (0, 2 m I), so since θ( g 2 ) k ∼ N (0, 2θ 2 m ), using numerical values of Gaussian CDF, one can verify that
A Convergence Theory for Deep Learning via Over-Parameterization
Let us denote this event of g 2 as E k . Conditioning on E k happens, recalling h i,L−1 ∈ [0.9, 1.1] from Lemma 4.1,
A Convergence Theory for Deep Learning via Over-Parameterization
• For i = i * , we have
A Convergence Theory for Deep Learning via Over-Parameterization
with probability exactly 1 2 -this is because, conditioning on event E k , the sign of (θ g 2 ) k is ±1 each with half probability.
A Convergence Theory for Deep Learning via Over-Parameterization
Recall that for every k ∈ N ,
A Convergence Theory for Deep Learning via Over-Parameterization
Now, fix the randomness of A, B, W 1 , . . . , W L−1 , W L and let g 2 be the only randomness. Conditioning on E k , we have that each term in ♣ is fixed (i.e., independent of g 2 ) because
A Convergence Theory for Deep Learning via Over-Parameterization
In contrast, conditioning on E k , the indicator 1 (W L h i * ,L−1 ) k ≥0 of the ♠ term may be 1 or 0 each with half probability. This means,
A Convergence Theory for Deep Learning via Over-Parameterization
Taking into account the fact that by definition of N ), the fact that h i,L−1 ≥ 0.9, and the fact that
A Convergence Theory for Deep Learning via Over-Parameterization
Using the independence of ( g 2 ) k with respect to different k ∈ N , we can apply Chernoff bound and derive:
A Convergence Theory for Deep Learning via Over-Parameterization
Pr
A Convergence Theory for Deep Learning via Over-Parameterization
Finally, using and |N | ≥ δ 100n m, we have
A Convergence Theory for Deep Learning via Over-Parameterization
We finish the upper bound proof of Lemma 6.3. 
A Convergence Theory for Deep Learning via Over-Parameterization
Proof of Claim 6.4. Throughout the proof we assume W L−1 , . . . , A are good enough so that Lemma 4.1 holds (for ε = 0.01) and we fix their randomness. Define 
A Convergence Theory for Deep Learning via Over-Parameterization
Next, suppose we fix the randomness of W L h. Define
A Convergence Theory for Deep Learning via Over-Parameterization
For each k ∈ N 1 and i ∈ [n] \ {i * }, we can write
A Convergence Theory for Deep Learning via Over-Parameterization
Above, the first term on the right hand side is fixed (because we have fixed the randomness of W L h); however, W L (I − h h )h i,L−1 is still fresh new random Gaussian. In symbols,
A Convergence Theory for Deep Learning via Over-Parameterization
According to Lemma 4.5, the variance here is at least 2
A Convergence Theory for Deep Learning via Over-Parameterization
. Using standard properties of Gaussian CDF (see Fact 6.6), we know |(W L h i,L−1 ) k | ≥ δ 4n √ m with probability at least 1 − 1 8n for each k ∈ [m]. By union bound, for this k ∈ [m], with probability at least 7 8 we know
A Convergence Theory for Deep Learning via Over-Parameterization
Combining the two bounds we finish the proof.
A Convergence Theory for Deep Learning via Over-Parameterization
Fact 6.6. Suppose x ∼ N (0, σ 2 ) is a Gaussian random variable. For any t ∈ (0, σ) we have
A Convergence Theory for Deep Learning via Over-Parameterization
. Similarly, if x ∼ N (µ, σ 2 ), for any t ∈ (0, σ), we have
A Convergence Theory for Deep Learning via Over-Parameterization
In this section we prove our main theorem on the gradient upper and lower bounds. 
A Convergence Theory for Deep Learning via Over-Parameterization
Remark 7.1. Our Theorem 3 only gives gradient lower bound on ∇ W L F ( − → W) F . In principle, one can derive similar lower bounds on ∇ W F ( − → W) F for all = 1, 2, . . . , L − 1. However, the proof will be significantly more involved. We choose not to derive those bounds at the expense of losing a polynomial factor in L in the final running time. For readers interested in the techniques for obtaining those bounds, we refer to them to the "randomness decomposition" part of our separate paper [5].  
A Convergence Theory for Deep Learning via Over-Parameterization
With our parameter assumption on ω, this together with Lemma 6.3 implies the same upper and lower bounds at point
A Convergence Theory for Deep Learning via Over-Parameterization
Finally, taking ε-net over all possible vectors v = (v 1 , . . . , v n ) ∈ (R d ) n , we know that the above bounds hold not only for fixed v but for all v. In particular, we can now plug in the choice of v i = loss i = Bh i,L − y * i and it implies our desired bounds on the true gradients.
A Convergence Theory for Deep Learning via Over-Parameterization
The purpose of this section is to prove Theorem 4 (objective semi-smoothness, restated). Let ω ∈ Ω( 
A Convergence Theory for Deep Learning via Over-Parameterization
We introduce the following notations before we go to proofs. 
A Convergence Theory for Deep Learning via Over-Parameterization
i, ∈ R m×m andD i, ∈ R m×m respectively by letting
A Convergence Theory for Deep Learning via Over-Parameterization
The following claim gives rise to a new recursive formula to calculate h i, −h i, .
A Convergence Theory for Deep Learning via Over-Parameterization
Proof of Theorem 4. First of all, since 1 2
A Convergence Theory for Deep Learning via Over-Parameterization
we can write
A Convergence Theory for Deep Learning via Over-Parameterization
Above, x is by the definition of F (·); y is by (8.2); z is by the definition of ∇F (·) (see Fact 2.6 for an explicit form of the gradient). We next bound the RHS of (8.3). We first note that by Lemma 5.2b, we have D i,
A Convergence Theory for Deep Learning via Over-Parameterization
i, 0 ≤ s for s = O(mω 2/3 L).
A Convergence Theory for Deep Learning via Over-Parameterization
We ignore subscripts in i for notational convenience. We first use Claim 8.2 to get
A Convergence Theory for Deep Learning via Over-Parameterization
Next we calculate that
A Convergence Theory for Deep Learning via Over-Parameterization
Finally, we also have
A Convergence Theory for Deep Learning via Over-Parameterization
where x uses Lemma 4.4b (and Lemma 5.7 for bounding the perturbation) and y uses Claim 8.2 to bound h −h 2 and our choice of ω. Putting (8.4), (8.5) and (8.6) back to (8.3), and using triangle inequality, we have the desired result.
A Convergence Theory for Deep Learning via Over-Parameterization
We first present a simple proposition about the ReLU function. Proposition 8.3. Given vectors a, b ∈ R m and D ∈ R m×m the diagonal matrix where D k,k = 1 a k ≥0 . Then, then there exists a diagonal matrix D ∈ R m×m with • |D k,k + D k,k | ≤ 1 and |D k,k | ≤ 1 for every k ∈ [m],
A Convergence Theory for Deep Learning via Over-Parameterization
• D k,k = 0 only when 1 a k ≥0 = 1 b k ≥0 , and
A Convergence Theory for Deep Learning via Over-Parameterization
Proof. We verify coordinate by coordinate for each k ∈ [m].
A Convergence Theory for Deep Learning via Over-Parameterization
Proof of Claim 8.2. We ignore the subscript in i for cleanness, and calculate that
A Convergence Theory for Deep Learning via Over-Parameterization
Above, x is by the recursive definition of h andh ; y is by Proposition 8.3 and D is defined according to Proposition 8.3; and inequality z is by recursively computing h −1 −h −1 . As for the remaining properties:
A Convergence Theory for Deep Learning via Over-Parameterization
This is because, (D ) k,k is non-zero only at the coordinates k ∈ [m] where the signs ofg and g are opposite (by Proposition 8.3). Such a coordinate k must satisfy either (D (0) ) k,k = (D ) k,k or (D (0) ) k,k = (D ) k,k , and therefore by Lemma 5.2b there are at most O(mω 2/3 L) such coordinates k.
A Convergence Theory for Deep Learning via Over-Parameterization
This is because we have
A Convergence Theory for Deep Learning via Over-Parameterization
This is because we have B(D +D )W · · ·W a+1 (D a +D a 
A Convergence Theory for Deep Learning via Over-Parameterization
Then, it satisfies
A Convergence Theory for Deep Learning via Over-Parameterization
In other words, the training loss drops to ε in a linear convergence speed.
A Convergence Theory for Deep Learning via Over-Parameterization
Proof of Theorem 1. Using Lemma 4.1 we have h i,L 2 ≤ 1.1 and then using the randomness of B, it is easy to show that Bh Let us assume for every t = 0, 1, . . . , T − 1, the following holds
A Convergence Theory for Deep Learning via Over-Parameterization
We shall prove the convergence of GD assuming (9.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 (9.1) is satisfied.
A Convergence Theory for Deep Learning via Over-Parameterization
Above, x uses Theorem 4; y uses Theorem 3 (which gives ∇ t
A Convergence Theory for Deep Learning via Over-Parameterization
× mn ); z use gradient lower bound from Theorem 3 and our choice of η. In other words, after T = Ω( dn 2 ηδm ) log n log m ε iterations we have F ( − → W (T ) ) ≤ ε.
A Convergence Theory for Deep Learning via Over-Parameterization
We need to verify for each t, − → W (t) − − → W (0) F is small so that (9.1) holds. By Theorem 3,
A Convergence Theory for Deep Learning via Over-Parameterization
where the last step follows by our choice of T .
A Convergence Theory for Deep Learning via Over-Parameterization
10 Convergence Rate of SGD Theorem 2 (stochastic gradient descent, stated). For any ε ∈ (0, 1], Suppose we start at W (0) and for each t = 0, 1, . . . , T − 1,
A Convergence Theory for Deep Learning via Over-Parameterization
(for a random subset S t ⊆ [n] of fixed cardinality b.)
A Convergence Theory for Deep Learning via Over-Parameterization
Then, it satisfies with probability at least 1 − e −Ω(log 2 m) over the randomness of S 1 , . . . , S T :
A Convergence Theory for Deep Learning via Over-Parameterization
Proof of Theorem 2. Using similar argument as the proof of Theorem 1, we have with at least
A Convergence Theory for Deep Learning via Over-Parameterization
Let us assume for every t = 0, 1, . . . , T − 1, the following holds
A Convergence Theory for Deep Learning via Over-Parameterization
We shall prove the convergence of SGD assuming (10.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 (10.1) is satisfied throughout the SGD with high probability. For each t = 0, 1, . . . , T − 1, using the same notation as Theorem 1, except that we choose
A Convergence Theory for Deep Learning via Over-Parameterization
Above, x uses Theorem 4 and E St [∇ t ] = ∇F ( − → W (t) ); y uses Theorem 3 which give
A Convergence Theory for Deep Learning via Over-Parameterization
; z use gradient lower bound from Theorem 3 and our choice of η.
A Convergence Theory for Deep Learning via Over-Parameterization
At the same time, we also have the following absolute value bound:
A Convergence Theory for Deep Learning via Over-Parameterization
Above, x uses Theorem 4 and Cauchy-Schwarz A, B ≤ A F B F , and y uses Theorem 3 which give 
A Convergence Theory for Deep Learning via Over-Parameterization
By (one-sided) martingale concentration, we have with probability at least 1 − e −Ω(log 2 m) , for every t = 1, 2, . . . , T :
A Convergence Theory for Deep Learning via Over-Parameterization
This implies two things.
A Convergence Theory for Deep Learning via Over-Parameterization
• On one hand, if T ≥ Ω L 2 n 7 bδ 2 log 2 m and T = Ω( dn 2 ηδm log n log m ε ) iterations we have
A Convergence Theory for Deep Learning via Over-Parameterization
Therefore, we have F ( − → W (T ) ) ≤ ε.
A Convergence Theory for Deep Learning via Over-Parameterization
• On the other hand, for every t = 1, 2, . . . , T , we have
A Convergence Theory for Deep Learning via Over-Parameterization
We can now verify for each t,
A Convergence Theory for Deep Learning via Over-Parameterization
F is small so that (10.1) holds. By Theorem 3,
A Convergence Theory for Deep Learning via Over-Parameterization
For simplicity, in them main body of this paper we have used the 2 regression loss. Our results generalize easily to other Lipschitz smooth (but possibly nonconvex) loss functions. Suppose we are given loss function f (z; y) that takes as input a neural-network output z ∈ R d and a label y. Then, our training objective for the i-th training sample becomes F i (W) = f (Bh i,L ; y * i ). We redefine the loss vector loss i def = ∇f (Bh i,L ; y * i ) ∈ R d (where the gradient is with respect to z). Note that if f (z; y) = 1 2 z − y 2 is the 2 loss, then this notion coincides with Section 2. We assume that f (z; y) is 1-Lipscthiz (upper) smooth with respect to z. 9 All the results in Section 4, 5 and 6 remain unchanged. Section 7 also remains unchanged, except we need to restate Theorem 3 with respect to this new notation:
A Convergence Theory for Deep Learning via Over-Parameterization
Section 8 also remains unchanged, except that we need to replace the precise definition of 2 loss in (8.2) with the semi-smoothness condition:
A Convergence Theory for Deep Learning via Over-Parameterization
and the rest of the proof remains unchanged. As for the final convergence theorem of gradient descent, we can replace (9.2) with
A Convergence Theory for Deep Learning via Over-Parameterization
This means many things:
A Convergence Theory for Deep Learning via Over-Parameterization
• If the loss is bounded (say, |f (z; y)| ≤ O(1)), then in T = O dn 2 ηδmε 2 = O n 6 L 2 δ 2 ε 2 iterations, we can find a point − → W (T ) with loss (T ) ≤ ε. (We choose m ≥ Ω (nL/δ) 30 dε −4 .)
A Convergence Theory for Deep Learning via Over-Parameterization
• If the loss is cross entropy f (z; y) = e zy d i=1 e z i for classification, then ∇f (z; y) < 1/4 implies perfect classification. 10 Thus, we have 100% training accuracy in T = O n 6 L 2 δ 2 iterations.
A Convergence Theory for Deep Learning via Over-Parameterization
• If the loss satisfies the Polyak-Lojasiewicz condition ∇f (z; y) 2 ≥ σ(f (z; y) − f (z * ; y)), then in T = Ω dn 2 ηδmσ = O n 6 L 2 δ 2 σ log 1 ε iterations, we can find a point
A Convergence Theory for Deep Learning via Over-Parameterization
(We choose m ≥ Ω (nL/δ) 30 dσ −2 log 2 ε −1 .)
A Convergence Theory for Deep Learning via Over-Parameterization
• 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 * ≤ D. Then, by convexity f (z; y) − f (z * ; y) ≤ ∇f (z; y), z − z * ≤ D ∇f (z; y) 9 That is, f (z + z ; y) ≤ f (z) + ∇f (z; y), z + 1 2 z 2 . 10 Recall ∂f (z;y) zy = py(1 − py) where pj = e z j d i=1 e z i . If py > 1/2, then z correctly predicts the target label y because py > pj for j = z.
A Convergence Theory for Deep Learning via Over-Parameterization
Putting this into (A.2), we have (here
A Convergence Theory for Deep Learning via Over-Parameterization
This implies (see for instance the classical calculation steps in [40]) that after
A Convergence Theory for Deep Learning via Over-Parameterization
There are numerous versions of convolutional neural networks (CNNs) that are used in practice.
A Convergence Theory for Deep Learning via Over-Parameterization
To demonstrate the capability of applying our techniques to such convolutional settings, in this section, we study a simple enough CNN for the 2 regression task.
A Convergence Theory for Deep Learning via Over-Parameterization
A Simple CNN Model. We assume that for the input layer (corresponding to A) and for each hidden layer = 1, 2, . . . , L − 1 (corresponding to W 1 , . . . , W L−1 ), there are d positions each consisting of m channels. (Each position can be thought as a pixel of an image in computer vision tasks.) We assume the last hidden layer = L (corresponding to W L ) and the output layer (corresponding to B) are fully connected. We assume for each j ∈ [d], there exists a set Q j ⊆ [d] of fixed cardinality q ∈ [d] so that the value at position j in any convolutional layer is completely determined by positions k ∈ Q j of the previous layer.
A Convergence Theory for Deep Learning via Over-Parameterization
Assumption B.1. We assume that (Q 1 , . . . , Q d ) give rise to a q-regular bipartite graph: each Q j has exactly q entries and each k ∈ [d] appears in exactly q different sets Q j .
A Convergence Theory for Deep Learning via Over-Parameterization
(In vision tasks, if 3×3 kernels are used then |Q j | = 9. We ignore the padding issue for simplicity.)
A Convergence Theory for Deep Learning via Over-Parameterization
The output of each convolutional layer = 0, 1, 2, . . . , L − 1 is represented by a dm-dimensional vector h = (h ,1 , . . . , h ,d ) where each h ,j ∈ R m , ∀j ∈ [d]. In the input layer and each j ∈ [d], we assume
A Convergence Theory for Deep Learning via Over-Parameterization
where x Q j ∈ R q denotes the concatenation of x k for all k ∈ Q j given input x ∈ R d , and A j ∈ R m×q is randomly initialized at N (0, 2 √ qm ) per entry. For notational simplicity, we define matrix A ∈ R dm×d so that it satisfies h 1 = φ Ax . Each row of A has q non-zero entries.
A Convergence Theory for Deep Learning via Over-Parameterization
For each layer = 1, . . . , L − 1 and each j ∈ [d], we assume
A Convergence Theory for Deep Learning via Over-Parameterization
where h −1,Q j ∈ R qm denotes the concatenation of h −1,k for all k ∈ Q j , the weights W ,j ∈ R m×(qm) and the bias the b ,j ∈ R m are randomly initialized at N (0, 2 qm ) per entry, and τ is a small parameter (say, τ = δ 2 10dL ) for bias. For notational simplicity, we define matrix W ∈ R dm×dm and vector b ∈ R dm so that it satisfies h = φ W h −1 + τ b , and define vector g
A Convergence Theory for Deep Learning via Over-Parameterization
Note that each row of W has qm non-zero entries.
A Convergence Theory for Deep Learning via Over-Parameterization
We assume the last layer W L and the output layer B are simply fully connected (say without bias). That is, each entry of W L ∈ R dm×dm is from N (0, 2 qm ), and of B ∈ R d×dm is from N (0, 1 d ). We denote by h i, the value of h when the input vector is x i , and define g i, , D i, in the same way as before.
A Convergence Theory for Deep Learning via Over-Parameterization
If one is willing to loose polynomial factors in L and d in the final complexity, then changes to each of the lemmas of this paper is very little. 11 Changes to Section 4. The first main result is Lemma 4.1: h i, is in [1 − ε, 1 + ε] with high probability. In the CNN case, for every j ∈ [d], recalling that h i, ,j = φ(W ,j h i, −1,Q j + τ b ). Applying Fact 4.2, we have that qm h i, ,j 2 2( h i, −1,Q j 2 +τ 2 ) is distributed as χ 2 ω distribution with ω ∼ B(m, 1 2 ). Due to the concentration of χ 2 distribution and the concentration of binomial distribution, h i, ,j 2 is extremely close to h i, −1,Q j 2 +τ 2 q (a careful argument of this can be found in the proof of Lemma 4.1). Summing this up over all j ∈ [d], and using Assumption B.1, we have h i, ,j 2 is concentrated at h i, −1 2 + τ 2 d q . Applying induction, we have h i, is in [1 − ε, 1 + ε] with probability at least 1 − e −Ω(mε 2 /L 2 ) , as long as τ 2 ≤ εq 10dL . 12 The changes to Lemma 4.3 and Lemma 4.4 are the same as above, but we loose some polynomial factors in L (because we are not careful in the argument above). For instance, the intermediate bound in Lemma 4.3a becomes W b D i,b−1 W b−1 · · · D i,a W a 2 ≤ O(L).
A Convergence Theory for Deep Learning via Over-Parameterization
As for the δ-separateness Lemma 4.5, we need to redefine the notion of δ-separateness between h i, and h j, : where g 2 ∼ N (0, 2 qm I) is independent of the randomness of h i, ,k once A, W 1 , . . . , W −1 are fixed. One can use this to replace (4.5) and the rest of the proof follows.
A Convergence Theory for Deep Learning via Over-Parameterization
Changes to Section 5. The first main result is Lemma 5.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 4.3a. Next, call that the proof of Lemma 5.2 relied on Claim 5.3 and Claim 5.5:
A Convergence Theory for Deep Learning via Over-Parameterization
• For Claim 5.3, we can replace the definition of x with x = D (W (0) h (0) + τ b + g ) for b ∈ N (0, 2 qm I). This time, instead of using the randomness of W (0) like in the old proof (because W (0) is no longer a full matrix), we use the randomness of τ b. The new statement becomes
A Convergence Theory for Deep Learning via Over-Parameterization
and its proof is by re-scaling x by 1 τ and then applying the old proof (with dimension m replaced with dm).
A Convergence Theory for Deep Learning via Over-Parameterization
• For Claim 5.5, it becomes y 1 ≤ O qs/m log m and y 2 ∞ ≤ 2 √ log m √ qm . 11 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. 12 We note that in all of our applications of Lemma 4.1, the minimal choice of ε is around δ 3 from the proof of δ-separateness. Therefore, choosing τ = δ 2 10dL is safe. We are aware of slightly more involved proofs that are capable of handling much larger values of τ .
A Convergence Theory for Deep Learning via Over-Parameterization
After making all of these changes, we loose at most some polynomial factors in L and d for the new statement of Lemma 5.2:
A Convergence Theory for Deep Learning via Over-Parameterization
(a) D i, 0 ≤ mω 2/3 poly(L, d) and D i, g i, ≤ ωpoly(L, d).
A Convergence Theory for Deep Learning via Over-Parameterization
(b) g i, , h i, ≤ ωpoly(L, d) √ log m.
A Convergence Theory for Deep Learning via Over-Parameterization
Finally, the statements of Lemma 5.6 and Lemma 5.7 only loose polynomial factors in L and d.
A Convergence Theory for Deep Learning via Over-Parameterization
Changes to Section 6. The norm upper bound part is trivial to modify so we only focus on the gradient norm lower bound. Since we have assumed W L to be fully connected, the gradient on W L is the same as before:
A Convergence Theory for Deep Learning via Over-Parameterization
Since we still have δ-separateness (B.1), one can verify for = L − 1,
A Convergence Theory for Deep Learning via Over-Parameterization
≥ Ω(δ 2 ) .
A Convergence Theory for Deep Learning via Over-Parameterization
Since h i, ≈ 1 and h j, ≈ 1, this gives back the old definition of δ-separateness:
A Convergence Theory for Deep Learning via Over-Parameterization
2 )h j, has norm at least Ω(δ). Therefore, the entire rest of Section 6 follows as before.
A Convergence Theory for Deep Learning via Over-Parameterization
Final Theorem. Since Section 7 and 8 rely on previous sections, they do not need to be changed (besides some polynomial factor blowup in L and d). Our final theorem becomes Theorem 5 (CNN). Let m ≥ Ω poly(n, L, d, δ −1 )·d·log 2 ε −1 . For the convolutional neural network defined in this section, with probability at least 1 − e −Ω(log 2 m) over the random initialization, GD and SGD respectively need at most T = poly(n,L,d) 
A Convergence Theory for Deep Learning via Over-Parameterization
Again as we have discussed in Section C, there are numerous versions of residual neural networks that are used in practice. To demonstrate the capability of applying our techniques to residual settings, in this section, we study a simple enough residual network for the 2 regression task (without convolutional layers).
A Convergence Theory for Deep Learning via Over-Parameterization
A Simple Residual Model. We consider an input layer h 0 = φ(Ax), L − 1 residual layers h = φ(h −1 + τ W h −1 ) for = 1, 2, . . . , L − 1, a fully-connected layer h L = φ(W L h L−1 ) and an output layer y = Bh L . We assume that h 0 , . . . , h L ∈ R m and the entries of W ∈ R m×m are from N (0, 2 m ) as before. We choose τ = Let s k = 1 if (h i, −1 − h j, −1 ) k ≥ 0 and s k = −1 otherwise. Then,
A Convergence Theory for Deep Learning via Over-Parameterization
Note that when h i, −1 and h j, −1 are fixed, the values s k (W (h i, −1 − h j, −1 )) k are independent Gaussian with mean zero. This means, with probability at least 1 − e −Ω(log 2 m) , the summation k∈M 0 s k (W (h i, −1 − h j, −1 )) k is at most O(log m) in absolute value. Putting this into the above equation, we have
A Convergence Theory for Deep Learning via Over-Parameterization
• Continuing this process for = 2, 3, . . . , L − 1, we can conclude that k∈M 0 |(h i,L−1 − h j,L−1 ) k | ≥ δ 30 √ m and therefore h i,L−1 − h j,L−1 ≥ Ω(δ 2 ). This is the same statement as before that we shall need for the downstream application of Lemma 4.5.
A Convergence Theory for Deep Learning via Over-Parameterization
Changes to Section 5. Lemma 5.2 becomes easy to prove with all the L factors disappear for the following reason. Fixing i and ignoring the subscript in i, we have for = 1, 2, . . . , L − 1:
A Convergence Theory for Deep Learning via Over-Parameterization
For some diagonal matrix D ∈ R m×m with diagonal entries in [−1, 1] (see Proposition 8.3). By simple spectral norm of matrices bound we have
A Convergence Theory for Deep Learning via Over-Parameterization
This implies h , g ≤ O(τ ω) for all ∈ [L − 1], and combining with the old proof we have h L , g L ≤ O(ω).
A Convergence Theory for Deep Learning via Over-Parameterization
As for the sparsity D 0 , because g (0) = h Next, Lemma 5.6 and Lemma 5.7 become trivial to prove (recall we have to change W (0) with I + τ W (0) for < L) and the L factor also gets improved.
A Convergence Theory for Deep Learning via Over-Parameterization
Changes to Section 6. The proofs of this section require only notational changes.
A Convergence Theory for Deep Learning via Over-Parameterization
Final Theorem. Since Section 7 and 8 rely on previous sections, they do not need to be changed (besides improving polynomial factors in L). Our final theorem becomes Theorem 6 (ResNet). Let m ≥ Ω poly(n, L, d, δ −1 ) · d · log 2 ε −1 . For the residual neural network defined in this section, with probability at least 1 − e −Ω(log 2 m) over the random initialization, GD needs at most T = O n 6 L 2 δ 2 log 1 ε iterations and SGD needs at most T = O n 7 L 2 log 2 m bδ 2 log 1 ε iterations to find a point F ( − → W) ≤ ε.
Ternary Weight Networks
Deep neural networks (DNN) have made significant improvements in lots of computer vision tasks such as object recognition [1,2,3,4] and object detection [5,6]. This motivates interests to deploy the state-of-the-art DNN models to real world applications like smart phones, wearable embedded devices or other edge computing devices. However, these models often need considerable storage and computational power [7], and can easily overburden the limited storage, battery power, and computer capabilities of the smart wearable embedded devices. As a result, it remains a challenge for the deployment.
Ternary Weight Networks
To mitigate the storage and computational problem [8,9], methods that seek to binarize weights or activations in DNN models have been proposed. BinaryConnect [10] uses a single sign function to binarize the weights. Binary Weight Networks [7] adopts the same binarization function but adds an extra scaling factor. The extensions of the previous methods †: Equal contribution. * Correspondence authors.
Ternary Weight Networks
are BinaryNet [11] and XNOR-Net [7] where both weights and activations are binary-valued. These models eliminate most of the multiplications in the forward and backward propagations, and thus own the potential of gaining significant benefits with specialized deep learning (DL) hardware by replacing many multiply-accumulate operations by simple accumulation [12]. Besides, binary weight networks achieve up to 32× model compression rate. Despite the binary techniques, some other compression methods focus on identifying models with few parameters while preserving accuracy by compressing existing state-of-the-art DNN models in a lossy way. SqueezeNet [13] is such a model that has 50× fewer parameters than AlexNet [2] but maintains AlexNet-level accuracy on ImageNet. MobileNet [14] and ShuffleNet [15] propose lightweight architectures to reduce the parameters and computation cost. Other methods propose to search efficient architectures and achieves great performance on both classification [16,17] and object detection [18]. Deep Compression [9] is another most recently proposed method that uses pruning, trained quantization and huffman coding for compressing neural networks. It reduced the storage requirement of AlexNet and VGG-16 [3] by 35× and 49×, respectively, without loss of accuracy. This paper has the following contributions:
Ternary Weight Networks
1) To our best knowledge, this was the first (at least at its debut in arxiv) ternary weight quantization scheme to reduce storage and computational cost for deep neural networks.
Ternary Weight Networks
2) We propose an approximated and universal solution with threshold-based ternary function for calculating the ternary weights of the raw neural networks.
Ternary Weight Networks
3) Experiments show the efficacy of our approach on public benchmarks for both image classification and detection.
Ternary Weight Networks
We address the limited storage and computational resources issues by introducing ternary weight networks (TWNs), which constrain the weights to be ternary-valued: +1, 0 and -1. TWNs seek to make a balance between the full precision weight networks (FPWNs) counterparts and the binary precision weight networks (BPWNs) counterparts. The detailed features are listed as follows.
Ternary Weight Networks
Expressive ability In most recent network architectures such as VGG [3], GoogLeNet [4] and ResNet [1], a most commonly used convolutional filter is of size 3×3. With binary precision, there is only 2 3×3 = 512 templates. However, a ternary filter with the same size owns 3 3×3 = 19683 templates, which gains 38× more stronger expressive abilities than the binary counterpart.
Ternary Weight Networks
Model compression In TWNs, 2-bit storage requirement is needed for a unit of weight. Thus, TWNs achieve up to 16× model compression rate compared with the float32 precision counterparts. Take VGG-19 [3] as an example, float version of the model needs ∼500M storage requirement, which can be reduced to ∼32M with ternary precision. Thus, although the compression rate of TWNs is 2× less than that of BPWNs, it is fair enough for compressing most of the existing state-ofthe-art DNN models.
Ternary Weight Networks
Computational requirement Compared with the BP-WNs, TWNs own an extra zero state. However, the zero terms need not be accumulated for any multiple operations. Thus, the multiply-accumulate operations in TWNs keep unchanged compared with binary precision counterparts. As a result, it is also hardware-friendly for training large-scale networks with specialized DL hardware.
Ternary Weight Networks
In the following parts, we will give detailed descriptions about the ternary weight networks problem and an approximated but efficient solution. After that, a simple training algorithm with error back-propagation is introduced and the run time usage is described at last.
Ternary Weight Networks
To make the ternary weight networks perform well, we seek to minimize the Euclidian distance between the full precision weights W and the ternary-valued weightsW along with a nonnegative scaling factor α [7]. The optimization problem is formulated as follows,
Ternary Weight Networks
Here n is the number of the filter. With the approximation W ≈ αW, a basic block of forward propagation in ternary weight networks is as follows,
Ternary Weight Networks
where X is the input of the block; * is a convolution or inner product operation; g is a nonlinear activation function; ⊕ indicates a convolution or an inner product operation without multiplication; Z is the output feature map of the neural network block. It can also be used as input of the next block.
Ternary Weight Networks
One way to solve the optimization Eq. 1 is to expand the cost function J(α,W) and take the derivative w.r.t. α andW i is respectively. However, this would get interdependent α * and W * i . Thus, there is no deterministic solution in this way [19]. To overcome this, we try to find an approximated optimal solution with a threshold-based ternary function,
Ternary Weight Networks
Here ∆ is an positive threshold parameter. With Eq. 3, the original problem can be transformed to
Ternary Weight Networks
i is a α independent constant. Thus, for any given ∆, the optimal α can be computed as follows,
Ternary Weight Networks
By substituting α * ∆ into Eq. 4, we get a ∆ dependent equation, which can be simplified as follows,
Ternary Weight Networks
The above euqation has no straightforward solutions. Though discrete optimization can be made to solve the problem (due to states of W i is finite), it should be very time consuming. As a viable alternative, we make a single assumption that W i are generated from uniform or normal distribution. In case of W i are uniformly distributed in [−α, α] and ∆ lies in (0, α], the approximated ∆ * is α 3 , which equals to 2 3 E(|W|). When W i is generated from normal distributions N (0, σ 2 ), the approximated ∆ * is 0.6σ which equals to 0.75E(|W|). Thus, we can use a rule of thumb that ∆ * ≈ 0.75E(|W|) ≈ 0.75 n n i=1 |W i | for simplicity.
Ternary Weight Networks
CNNs typically includes Convolution layer, Fully-Connected layer, Pooling layer (e.g.,Max-Pooling, Avg-Pooling), Batch-Normalization (BN) layer [20] and Activation layer (e.g.,ReLU, Sigmoid), in TWNs, we also follow the traditional neural network block design philosophy, the order of layers in a typical ternary block of TWNs is shown in Fig. 1.
Ternary Weight Networks
We borrow the parameter optimization strategy which successfully applied from BinaryConncet [10] and XNOR-Net [7], in our design, ternarization only happens at the forward and backward pass in convolution and fully-connected layers, but in the parameters update stage, we still keep a copy of the Algorithm 1: Train a M-layers CNN w/ ternary weights Inputs :A minibatch of inputs and targets (I, Y ), loss function L(Y ,Ŷ ) and current weight W t . Hyper-parameter :current learning rate η t .
Ternary Weight Networks
:updated weight W t+1 , updated learning rate η t+1 . ∂L ∂T = TernaryBackward( ∂L ∂Ŷ ,T ) //standard backward propagation except that gradients are computed using T instead of W t 10 W t+1 = UpdateParameters(W t , ∂L ∂T , ηt) // we use SGD in this paper 11 η t+1 = UpdateLearningrate(η t , t) //we use learning rate step decay in this paper Fig. 1. A typical Ternary block in TWNs. In the forward pass, we apply ternarization operation for the weight of convolution layer meanwhile the float32 weight will be cached for future parameter update; in the backward pass, we calculate ternary weight gradient to update the float32 weight.
Ternary Weight Networks
full-precision parameters. In addition, two effective tricks, Batch-Normalization and learning rate step decay that drops the learning rate by a factor every few epochs, are adopted. We use stochastic gradient descent (SGD) with momentum to update the the parameters when training TWNs, the detailed training strategy show in Table 1.
Ternary Weight Networks
In the forward pass, the scaling factor α could be transformed to the inputs according to Eq. 2. Thus, we only need to keep the ternary-valued weights and the scaling factors for deployment. This would results up to 16× model compression rate for deployment compared with the float32 precision counterparts.
Ternary Weight Networks
We benchmark Ternary Weight Networks (TWNs) with Binary Weight Networks (BPWNs) and Full Precision Networks (FPWNs) on both classification task (MNIST, CIFAR-10 and ImageNet) and object detection task (PASCAL VOC). For a fair comparison, we keep the following configures to be same: network architecture, regularization method (L2 weight decay), learning rate scaling procedure (multi-step) and optimization method (SGD with momentum). BPWNs use sign function to binarize the weights and FPWNs use floatvalued weights. See Table 1 for training configurations.
Ternary Weight Networks
MNIST is a collection of handwritten digits. It is a very popular dataset in the field of image processing. The LeNet-5 [21] architecture we used in MNIST experiment is "32-C5 + MP2 + 64-C5 + MP2 + 512 FC + SVM" which starts with a 5x5 convolutional block that includes a convolution layer, a BN layer and a relu layer. Then a max-pooling layer is followed with stride 2. The "FC" is a fully connect block with 512 nodes. The top layer is a SVM classifier with 10 labels. Finally, hinge loss is minimized with SGD.
Ternary Weight Networks
CIFAR-10 consists of 10 classes with 6K color images of 32x32 resolution for each class. It is divided into 50K training and 10K testing images. We define a VGG inspired architecture, denoted as VGG-7, by "2×(128-C3) + MP2 + 2×(256-C3) + MP2 + 2×(512-C3) + MP2 + 1024-FC + Softmax". Compared with the architecture in [10], we ignore the last fully connected layer. We follow the data augmentation in [1,22] for training: 4 pixels are padded on each side, and a 32×32 crop is randomly sampled from the padded image or its horizontal flip. At testing time, we only evaluate the single view of the original 32×32 image.
Ternary Weight Networks
ImageNet consists of about 1.2 million train images from 1000 categories and 50,000 validation images. ImageNet has higher resolution and greater diversity, is more close to real life than MNIST and CIFAR-10. We adopt the popular ResNet18 architecture [1] as backbone. Besides, we also benchmark another enlarged counterpart whose number of filters in each block is 1.5× of the original one which is termed as ResNet18B. In each training iteration, images are randomly cropped with 224×224 size. We do not use any resize tricks [7] or any color augmentation. Table 2 shows the classification results. On the small datasets (MNIST and CIFAR-10), TWNs achieve similar per-  formance as FPWNs, while beats BPWNs. On the large-scale ImageNet dataset, BPWNs and TWNs both get poorer performance than FPWNs. However, the accuracy gap between TWNs and FPWNs is smaller than the gap between BPWNs and TWNs. In addition, when we change the backbone from ResNet18 to ResNet18B, as the model size is larger, the performance gap between TWNs (or BPWNs) and FPWNs has been reduced. This indicates low precision networks gain more merits from larger models than the full precision counterparts. The validation accuracy curves of different approaches across all training epochs on MNIST, CIFAR-10 and Ima-geNet datasets illustrate in Fig. 2. As we can see in the figure, obviously, BPWNs converge slowly and the training loss is not stable compared with TWNs and FPWNs. However, TWNs converge almost as fast and stably as FPWNs. [23] consists of 20 classes with 11540 images and 27450 labeled objects. We adopt the popular YOLOv5 (small) [24] architecture and compare the performance of full precision, binary precision and ternary precision in Table 3.
Ternary Weight Networks
Specifically, we initialize each model by the weights trained on MS-COCO dataset [25] (provided by YOLOv5) and finetune each model by 150 epochs. We observe that TWNs significantly outperforms BPWNs by more than 10% mAP, showing the great effectiveness of our method.
Ternary Weight Networks
In this paper, we have introduced the simple, efficient, and accurate ternary weight networks for real world AI application which can reduce the memory usage about 16x and the the computation about 2x. We present the optimization problem of TWNs and give an approximated solution with a simple but effective ternary function. The proposed TWNs achieve a balance between accuracy and model compression rate as well as potentially low computational requirements of BPWNs. Empirical results on public benchmarks show the superior performance of the proposed method.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Neural networks trained by first order methods have achieved a remarkable impact on many applications, but their theoretical properties are still mysteries. One of the empirical observation is even though the optimization objective function is non-convex and non-smooth, randomly initialized first order methods like stochastic gradient descent can still find a global minimum. Surprisingly, this property is not correlated with labels. In Zhang et al. [2016], authors replaced the true labels with randomly generated labels, but still found randomly initialized first order methods can always achieve zero training loss.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
A widely believed explanation on why a neural network can fit all training labels is because the neural network is over-parameterized. For example, Wide ResNet [Zagoruyko and Komodakis] uses 100x parameters than the number of training data and thus there must exist one such neural network of this architecture that can fit all training data. However, the existence does not imply why the network found by a randomly initialized first order method can fit all the data. The objective function is neither smooth nor convex, which makes traditional analysis technique from convex optimization not useful in this setting. To our knowledge, only the convergence to a stationary point is known [Davis et al., 2018].
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
In this paper we demystify this surprising phenomenon on two-layer neural networks with rectified linear unit (ReLU) activation. Formally, we consider a neural network of the following form.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
where x ∈ R d is the input, w r ∈ R d is the weight vector of the first layer, a r ∈ R is the output weight and σ (·) is the ReLU activation function: σ (z) = z if z ≥ 0 and σ (z) = 0 if z < 0 . We focus on the empirical risk minimization problem with a quadratic loss. Given a training data set {(x i , y i )} n i=1 , we want to minimize
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
To do this, we fix the second layer and apply gradient descent (GD) on the first layer weights matrix
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
where η > 0 is the step size. Here the gradient formula for each weight vector is 1
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Though this is only a shallow fully connected neural network, the objective function is still nonsmooth and non-convex due to the use of ReLU activation function. Even for this simple function, why randomly initialized first order method can achieve zero training error is not known. In fact, many previous work have tried to answer this question or similar ones. Attempts include landscape analysis [Soudry and Carmon, 2016], partial differential equations [Mei et al.], analysis of the dynamics of the algorithm [Li and Yuan, 2017], optimal transport theory [Chizat and Bach, 2018], to name a few. These results often rely strong assumptions on the labels and input distributions, or do not imply why randomly initialized first order method can achieve zero training loss. See Section 2 for detailed comparisons between our result and previous ones.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
In this paper, we rigorously prove that as long as the data set is not degenerate and m is large enough, with properly randomly initialized a and W(0), GD achieves zero training loss at a linear convergence rate, i.e., it finds a solution W(K) with L(W(K)) ≤ ǫ in K = O(log (1/ǫ)) iterations. 2 Thus, our theoretical result not only shows the global convergence but also gives a quantitative convergence rate in terms of the desired accuracy.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
1 Note ReLU is not continuously differentiable. One can view ∂L(W) ∂wr as a convenient notation for the right hand side of (4) and this is indeed the update rule used in practice.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
2 Here we omit the polynomial dependency on n and other data dependent quantities.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Analysis Technique Overview Our proof relies on the following insights. First we directly analyze the dynamics of each individual prediction f (W, a, x i ) for i = 1, . . . , n. This is different from many previous work [Du et al., 2017b, Li andYuan, 2017] which tried to analyze the dynamics of the parameter (W ) we are optimizing. Note because the objective function is non-smooth and non-convex, analysis of the parameter space dynamics is very difficult. In contrast, we find the dynamics of prediction space is governed by the spectral property of a Gram matrix (which can vary in each iteration, c.f. (5)) and as long as this Gram matrix's least eigenvalue is lower bounded, gradient descent enjoys a linear rate. Furthermore, previous work has shown in the initialization phase this Gram matrix does has lower bounded least eigenvalue as long as the data is not degenerate [Xie et al., 2017]. Thus the problem reduces to showing the Gram matrix at later iterations is close to that in the initialization phase. Our second observation is this Gram matrix is only related to the activation patterns (I w ⊤ r x i ≥ 0 ) and we can use matrix perturbation analysis to show if most of the patterns do not change, then this Gram matrix is close to its initialization. Our third observation is we find over-parameterization, random initialization and the linear convergence jointly restrict every weight vector w r is close to its initialization. Then we can use this property to show most of the patterns do not change. Combining these insights we prove the first global quantitative convergence result of gradient descent on ReLU activated neural networks for the empirical risk minimization problem. Notably, our proof only uses linear algebra and standard probability bounds so we believe it can be easily generalized to analyze deep neural networks.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Notations We use bold-faced letters for vectors and matrices. We Let [n] = {1, 2, . . . , n}. Given a set S, we use unif {S} to denote the uniform distribution over S. Given an event E, we use I {A} to be the indicator on whether this event happens. We use N (0, I) to denote the standard Gaussian distribution. For a matrix A, we use A ij to denote its (i, j)-th entry. We use · 2 to denote the Euclidean norm of a vector, and use · F to denote the Frobenius norm of a matrix. If a matrix A is positive semi-definite, we use λ min (A) to denote its smallest eigenvalue. We use ·, · to denote the standard Euclidean inner product between two vectors. Lastly, let O(·) and Ω (·) denote standard Big-O and Big-Omega notations, only hiding absolute constants.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
In this section we survey an incomplete list of previous attempts in analyzing why first order methods can find a global minimum.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Landscape Analysis A popular way to analyze non-convex optimization problems is to identify whether the optimization landscape has some benign geometric properties. Recently, researchers found if the objective function is smooth and satisfies (1) all local minima are global and (2) for every saddle point, there exists a negative curvature, then the noise-injected (stochastic) gradient descent [Jin et al., 2017, Ge et al., 2015, Du et al., 2017a can find a global minimum in polynomial time. This algorithmic finding encouraged researchers to study whether the deep neural networks also admit these properties.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
For the objective function define in (2), some partial results were obtained. Soudry and Carmon [2016] showed if md ≥ n, then at every differentiable local minimum, the training error is zero. However, since the objective is non-smooth, it is hard to show gradient descent actually convergences to a differentiable local minimum. Xie et al. [2017] studied the same problem and related the loss to the gradient norm through the least singular value of the "extended feature matrix" D at the stationary points. However, they did not prove the convergence rate of gradient norm. Interestingly, our analysis relies on the Gram matrix which is actually DD ⊤ .
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Landscape analyses of ReLU activated neural networks for other settings have also been studied in many previous work , Safran and Shamir, 2018, 2016, Zhou and Liang, 2017, Freeman and Bruna, 2016, Hardt and Ma, 2016. These works establish favorable landscape properties such as all local minimizers are global, but do not ensure that gradient descent converges to a global minimizer of the empirical risk. For other activation functions, some previous work show the landscape does have the desired geometric properties [Du and Lee, 2018, Soltanolkotabi et al., 2018, Nguyen and Hein, 2017, Kawaguchi, 2016, Haeffele and Vidal, 2015, Andoni et al., 2014, Venturi et al., 2018. However, it is unclear how to extend their analyses in our setting.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Analysis of Algorithm Dynamics Another way to prove convergence result is to directly analyze the dynamics of first order methods. Our paper also belongs to this category. Many previous work assumed (1) the input distribution is Gaussian and (2) the label is generated according to a planted neural network. Based on these two (unrealistic) conditions, it can be shown that randomly initialized (stochastic) gradient descent can learn a ReLU [Tian, 2017, Soltanolkotabi, 2017, a single convolutional filter [Brutzkus and Globerson, 2017], a convolutional neural network with one filter and one output layer [Du et al., 2018b] and residual network with small spectral norm weight matrix [Li and Yuan, 2017]. 3 Beyond Gaussian input distribution, Du et al. [2017b] showed for learning a convolutional filter, the Gaussian input distribution assumption can be relaxed but they still require the label is generated from an underlying true filter. Comparing with these work, our paper does not try to recover the underlying true neural network. Instead, we focus on providing theoretical justification on why randomly initialized gradient descent can achieve zero training loss, which is what we can observe and verify in practice.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
The most related paper is by Li and Liang [2018] who observed that when training a two-layer full connected neural network, most of the patterns (I w ⊤ r x i ≥ 0 ) do not change over iterations, which we also use to show the stability of the Gram matrix. They used this observation to obtain the convergence rate of GD on a two-layer over-parameterized neural network for the cross-entropy loss. They need number of hidden nodes m scales with poly(1/ǫ) where ǫ is the desired accuracy. Thus unless the number of hidden nodes m → ∞, they result does not imply GD can achieve zero training loss. We improve by allowing the amount of over-parameterization to be independent of the desired accuracy and show GD can achieve zero training loss. Furthermore, our proof is much simpler and more transparent so we believe it can be easily generalized to analyze other neural network architectures.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Other Analysis Approaches Chizat and Bach [2018] used optimal transport theory to analyze continuous time gradient descent on over-parameterized models. However, their results on ReLU activated neural network is only at the formal level. Mei et al. showed the dynamics of SGD can be captured by a partial differential equation in the suitable scaling limit. They listed some specific examples on input distributions including mixture of Gaussians. However, it is still unclear whether this framework can explain why first order methods can minimize the empirical risk. Daniely [2017] built connection between 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. Again this work does not imply why first order method can achieve zero training loss.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
In this section, we present our result for gradient flow, i.e., gradient descent with infinitesimal step size. In the next section, we will modify the proof and give a quantitative bound for gradient descent with positive step size. Formally, we consider the ordinary differential equation 4 defined by :
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
a, x i ) the prediction on input x i at time t and we let u(t) = (u 1 (t), . . . , u n (t)) ∈ R n be the prediction vector at time t. Our main result in this section is the following theorem. 
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
and set the number of hidden nodes m = Ω n 6 λ 4 0 , with high probability over random initialization we have
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
We first discuss our assumptions. We assume x i 2 = 1 and |y i | ≤ C for simplicity. We can easily modify the proof by properly scaling the initialization. The key assumption is the least eigenvalue of the matrix H ∞ is strictly positive. Interestingly, various properties of this H ∞ matrix has been thoroughly studied in previous work [Xie et al., 2017, Tsuchida et al., 2017. In general, unless the data is degenerate, the smallest eigenvalue of H ∞ is strictly positive. We refer readers to Xie et al. [2017], Tsuchida et al. [2017] for a detailed characterization of this matrix.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
The number of hidden nodes m required is Ω n 6 λ 4 0 , which depends on the number of samples n and λ 0 . As will be apparent in the proof, over-parameterization, i.e., the fact m = poly(n, 1/λ 0 ), plays a crucial role in guaranteeing gradient descent to find the global minimum. We believe using a more refined analysis, this dependency can be further improved. Lastly, note the convergence rate is linear because u(t) − y 2 2 decreases to 0 exponentially fast. The specific rate also depends on λ 0 but independent of number of hidden nodes m.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Our first step is to calculate the dynamics of each prediction.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
where H(t) is an n × n matrix with (i, j)-th entry
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
With this H matrix, we can write the dynamics of prediction in a compact way:
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Note H(t) is a time-dependent symmetric matrix. We first analyze its property when t = 0. The following lemma shows if m is large then H(0) has lower bounded least eigenvalue with high probability. The proof is by standard concentration bound so we defer it to appendix. Our second step is to show H(t) is stable in terms of W. Formally, the following lemma shows if W(t) is close to the initialization W(0), H(t) is close H(0) and has a lower bounded least eigenvalue.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Lemma 3.2. Suppose for a given time t, for all r ∈ [m], w r (t) − w r (0) 2 ≤ cλ 0 n 2 R for some small positive constant c. Then we have with high probability over initialization, λ min (H(t)) > λ 0 2 . This lemma plays a crucial in our analysis so we give the proof below. Proof of Lemma 3.2 We define the event
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Note this event happens if and only if w r (0) ⊤ x 0 < R. Recall w r (0) ∼ N (0, I). By anticoncentration inequality of Gaussian, we have P (A ir ) = P z∼N (0,1) (|z| < R) ≤ 2R √ 2π . Therefore, we can bound the entry-wise deviation on H(t) in expectation:
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Summing over (i, j), we have E (n,n)
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
. Thus by Markov inequality, with high probability, we have (n,n) (i,j)=(1,1) |H ij (t) − H ij (0)| ≤ Cn 2 R where C is a large absolute constant. Next, we use matrix perturbation theory to bound the deviation from the initialization
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Lastly, we lower bound the smallest eigenvalue by plugging in R
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
The next lemma shows two facts if the least eigenvalue of H is lower bounded. First, the loss converges to 0 at a linear convergence rate. Second, w r (t) is close to the initialization for every r ∈ [m]. This lemma clearly demonstrates the power of over-parameterization.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Proof of Lemma 3.3 Recall we can write the dynamics of predictions as d dt u(t) = H(y − u(t)). We can calculate the loss function dynamics
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Thus we have d dt exp(λ 0 t) y − u(t) 2 2 ≤ 0, exp(λ 0 t) y − u(t) 2 2 is a decreasing function with respect to t. Using this fact we can bound the loss
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Therefore, u(t) → y exponentially fast. Now we bound the gradient. Recall for 0 ≤ s ≤ t,
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Integrating the gradient, we can bound the distance from the initialization
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
The next lemma shows we show if R ′ < R, the conditions in Lemma 3.2 and 3.3 hold for all t ≥ 0. The proof is by contradiction and we defer it to appendix.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Lemma 3.4. If R ′ < R, we have for all t ≥ 0, λ min (H(t)) ≥ 1 2 λ 0 , for all r ∈ [m], w r (t) − w r (0) 2 ≤ R ′ and y − u(t) 2 2 ≤ exp(−λ 0 t) y − u(0) 2 2 .
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Thus it is sufficient to show R ′ < R which is equivalent to m = Ω n 5 y−u(0) 2 2 λ 4 0 . We bound
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Thus by Markov's inequality, we have with high probability y − u(0) 2 2 = O(n). Plugging in this bound we prove the theorem.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
In this section, we show randomly initialized gradient descent with a constant positive step size converges to the global minimum at a linear rate. We first present our main theorem. 
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
and the number of hidden nodes m = Ω n 6 λ 4 0 and we set the step size η = O λ 0 n 2 then with high probability over the random initialization we have for k = 0, 1, 2, . . .
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Theorem 4.1 shows even though the objective function is non-smooth and non-convex, gradient descent with a constant positive step size still enjoys a linear convergence rate. Our assumptions on the least eigenvalue and the number of hidden nodes are exactly the same as the theorem for gradient flow. Notably, our choice of step size is independent of number of hidden nodes m in contrast to the previous work [Li and Liang, 2018].
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
We prove Theorem 4.1 by induction. Our induction hypothesis is just the following convergence rate of empirical loss.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Condition 4.1. At the k-th iteration, we have y − u(k) 2 2 ≤ (1 − ηλ 0 2 ) k y − u(0) 2 2 .
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
A directly corollary of this condition is the following bound of deviation from the initialization. The proof is similar to that of Lemma 3.3 so we defer it to appendix. 
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Now we show Condition 4.1 for every k = 0, 1, . . .. For the base case k = 0, by definition Condition 4.1 holds. Suppose for k ′ = 0, . . . , k, Condition 4.1 holds and we want to show Condition 4.1 holds for k ′ = k + 1.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Our strategy is similar to the proof of Theorem 3.1. We define the event
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
where R = cλ 0 n 2 for some small positive constant c. Different from gradient flow, for gradient descent we need a more refined analysis. We let S i = {r ∈ [m] : I{A ir } = 1} and S ⊥ i = [m] \ S i . The following Lemma bounds the sum of sizes of S ⊥ i . The proof is similar to the analysis used in Lemma 3.2. See Section A for the whole proof. Next, we calculate the difference of predictions between two consecutive iterations, analogue to du i (t) dt term in Section 3.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Here we divide the right hand side into two parts. I i 1 accounts for terms that the pattern does not change and I i 2 accounts for terms that pattern may change.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
We view I i 2 as a perturbation and bound its magnitude. Because ReLU is a 1-Lipschitz function and |a r | = 1, we have
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
To analyze I i 1 , by Corollary 4.1, we know w r (k) − w r (0) ≤ R ′ and w r (k) − w r (0) ≤ R ′ for all r ∈ [m]. Furthermore, because R ′ < R, we know I w r (k + 1) ⊤ x i ≥ 0 = I w r (k) ⊤ x i ≥ 0 . Thus we can find a more convenient expression of I i 1 for analysis )-th entry of a discrete version of Gram matrix defined in Section 3 and H ⊥ ij (k) = 1
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Let H ⊥ (k) be the n × n matrix with (i, j)-th entry being H ⊥ ij (k). Using Lemma 4.1, with high probability we obtain an upper bound of the operator norm
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Similar to the classical analysis of gradient, we also need bound the quadratic term.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
With these estimates at hand, we are ready to prove the induction hypothesis.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
The third equality we used the decomposition of u(k + 1) − u(k). The first inequality we used the Lemma 3.2, the bound on the step size, the bound on I 2 , the bound on H(k) ⊥ 2 and the bound on u(k + 1) − u(k) 2 2 . The last inequality we used the bound of the step size and the bound of R. Therefore Condition 4.1 holds for k ′ = k + 1. Now by induction, we prove Theorem 4.1.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
In this paper we show with over-parameterization, gradient descent provable converges to the global minimum of the empirical loss at a linear convergence rate. The key proof idea is to show the over-parameterization makes Gram matrix remain positive definite for all iterations, which in turn guarantees the linear convergence. Here we list some future directions.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
First, we believe the number of hidden nodes m required can be reduced. For example, previous work [Soudry and Carmon, 2016] showed m ≥ n d is enough to make all differentiable local minima global. In our setting, using advanced tools from probability and matrix perturbation theory to analyze H(t), we may able to tighten the bound.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Another direction is to prove the global convergence of gradient descent on multiple layer neural networks and convolutional neural networks. We believe our approach is still applicable because for a fixed a neural network architecture, when the number of hidden nodes is large and the initialization scheme is random Gaussian with proper scaling, the Gram matrix is also positive definite, which ensures the linear convergence of the empirical loss (at least at the begining). We believe combing our proof idea with the discovery of balancedness between layers in Du et al. [2018a] is a promising approach.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Lastly, in our paper we used the empirical loss as a potential function to measure the progress. If we use another potential function, we may able to prove the convergence rate of accelerated methods. This technique has been exploited in Wilson et al. [2016] for analyzing convex optimization. It would be interesting to bring their idea to analyze other first order methods.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Proof of Lemma 4.1. For a fixed i ∈ [n] and r ∈ [m], by anti-concentration inequality, we know P(A ir ) ≤ 2R √ 2π . Thus we can bound the size of S ⊥ i in expectation.
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Summing over i = 1, . . . , n, we have
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
Thus by Markov's inequality, we have with high probability
Gradient Descent Provably Optimizes Over-parameterized Neural Networks
for some large positive constant C > 0.