One of the mysteries 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 no two inputs are parallel, randomly initialized gradient descent converges to a globally optimal solution at a linear convergence rate for the quadratic loss function.

 Our analysis relies 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. 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 BID37 , authors replaced the true labels with randomly generated labels, but still found randomly initialized first order methods can always achieve zero training loss.A widely believed explanation on why a neural network can fit all training labels is that the neural network is over-parameterized. For example, Wide ResNet (Zagoruyko and Komodakis) uses 100x parameters than the number of training data. 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 BID5 .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. DISPLAYFORM0 a r σ w r x (1) 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 DISPLAYFORM1 Our main focus of this paper is to analyze the following procedure. We fix the second layer and apply gradient descent (GD) to optimize the first layer DISPLAYFORM2 where η > 0 is the step size. Here the gradient formula for each weight vector is 2 ∂L(W, a) DISPLAYFORM3 (f (W, a, x i ) − y i )a r x i I w r x i ≥ 0 .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. 3 Even for this simple function, why randomly initialized first order method can achieve zero training error is not known. Many previous works have tried to answer this question or similar ones. Attempts include landscape analysis BID28 , partial differential equations (Mei et al.) , analysis of the dynamics of the algorithm BID20 , optimal transport theory BID3 , to name a few. These results often make 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.In this paper, we rigorously prove that as long as no two inputs are parallel and m is large enough, with randomly initialized a and W(0), gradient descent achieves zero training loss at a linear convergence rate, i.e., it finds a solution DISPLAYFORM4 Thus, our theoretical result not only shows the global convergence but also gives a quantitative convergence rate in terms of the desired accuracy.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 BID8 BID20 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. Equation (6)) and as long as this Gram matrix's least eigenvalue is lower bounded, gradient descent enjoys a linear rate. It is easy to show as long as no two inputs are parallel , in the initialization phase, this Gram matrix has a lower bounded least eigenvalue. (c.f. Theorem 3.1). 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 to be 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.Notations 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. 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.First, we believe our approach can be generalized to deep neural networks. We elaborate the main idea here for gradient flow. Consider a deep neural network of the form DISPLAYFORM0 where x ∈ R d is the input, W (1) ∈ R m×d is the first layer, W (h) ∈ R m×m for h = 2, . . . , H are the middle layers and a ∈ R m is the output layer. Recall u i is the i-th prediction. If we use the quadratic loss, we can compute DISPLAYFORM1 Similar to Equation (5), we can calculate DISPLAYFORM2 where DISPLAYFORM3 . Therefore, similar to Equation FORMULA12 , we can write du(t) dt =
We prove gradient descent achieves zero training loss with a linear rate on over-parameterized neural networks. This work considers optimizing a two-layer over-parameterized ReLU network with the squared loss and given a data set with arbituary labels. This paper studies one hidden layer neural networks with square loss, where they show that in over-parameterized setting, random initialization and gradient descent gets to zero loss.