GRADIENT DESCENT PROVABLY OPTIMIZES OVER-PARAMETERIZED NEURAL NETWORKS
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.
Additional Review
This paper did NOT handle the non-differentiability and non-linearity very well. We can see this from the following three perspectives:
1. Proof idea: the proof of this paper is noisy version of the convergence analysis of  a simple convex problem --it treats the contribution of the non-linearity and non-differentiability as bounded noise.
2. The network size is of order n^6.
3. Network size requirement is dependent on \lambda_0. 
1.Proof idea: The proof is essentially a noisy version of the convergence analysis of a linear regression problem provided in Appendix (at the end of this updated review). The only difference between linear regression and the problem in this paper is the changing patterns due to the non-linearity of ReLU. However, this paper views the changing patterns as noises compared to those unchanging patterns (e.g., S_i v.s. S_i^\perpendicular). The key trick is that if the actual trajectory radius (i.e.,the largest deviation from the initial point) R’ is much smaller than the desired trajectory radius R (given by a formula), then along the trajectory, the contribution of non-linearity is just O(n^2 R), which is small compared to the contribution of linearity, i.e., -\lambda_0 (shown in proof on page 9). 
Following the above analysis, if the experiment shows that R’ is really small compared to R, then the approach of treating non-linearity as noise is fine. However, it is not the case for the problem studied in the experiments (Sec 5, Fig 1). In figure 1, we can easily see that the maximum distance R’ is O(1), which is far larger than R = c*\lambda_0/n^2 =10^-6 when n=1k. Therefore, the proof idea used in this paper is fundamentally not able to explain the phenomenon shown in the experiment. In fact, to address this issue, authors need to consider significant contribution of non-linearity, instead of just viewing them as noises. 
2. The network size is too large. This paper requires O(n^6) neurons, that is 10^18 neurons for n=1000 samples used in the experiment. The theoretical trick to make R’< R is to note that R’ can be bounded by O(1/sqrt{m}) while R is independent of m, thus picking a sufficiently large m can make R’ very small. In a word, the reason that this paper requires so many neurons because of the inability of properly addressing non-linearity. 
3. I found the dependence of the network size on the least eigenvalue funny, although the authors claim this tool is elegant. After authors add Thm 3.1 in the revision, I realize that the dependence on \lambda_0 might come from the fact that authors do NOT handle the issue of non-differentiability. 
Let us see a simple example. Assume I have a dataset with \lambda_0 = 1. Now I am adding one more data point (x=0_d, y=1) to the dataset. After adding this sample, \lambda_0 clearly becomes 0. It seems I am just adding a constant 1 to the loss function and the gradient descent can also converge to the global min with a linear convergence rate since the constant does NOT contribution to the gradient. However, it seems the proof does NOT work. This is due to the fact that the “gradient” of the non-differentiable points are NOT well defined. Here is a simple example: h(w)=(y-ReLU(w*x))^2, where x= 0, y =1. By the definition provided in this paper (Eq.4), we can easily see that dh/dw = 1 for any w, even if h(w) = 1 for any w. This means that the constant can provide “fake” gradient information and make  the maximum distance become infinity, (R’=\inf). Therefore, the whole proof collapses. In fact, changing the gradient definition from I{z>=0} to I{z>0} does not address the issue and we can see this from this example w=g(w)=Relu(w)-Relu(-w) has a zero gradient at w=0. 
In summary, the problem considered in this paper where the size m=O(n^6), maximum distance R’= O(1/n^2) is too easy compared to most problems in practice where m=\Theta(n), R’=O(1). To address the latter problem, we need a better definition of subgradient and need to analyze the significant contribution of non-linearity and non-differentiability, instead of just viewing them as noises. 
=================================Appendix===============================
The proof basically follows from the convergence analysis of the following linear regression problem (note that u_j is fixed):
           \min_{w_1,...,w_m}\sum_{i=1}^{n}(f(x_i;w_1,...,w_m)-y_i)^2 = L(w_1,...,w_m)
where   f(x;w_1,...,w_m)=1/\sqrt{m}\sum_{j=1}^{m} a_j*(w_j^T x)*1{u_j^T x>=0}
Gradient Descent Algorithm:
-Initialization:
-For each j=1,...,m: a_j ~ U({-1,1}), u_j~N(0, I)
-Fix a_1,...,a_m, u_1,...,u_m
-Update:
-For t = 1,...,T
    w_j(t+1)  = w_j(t) - \eta* \nabla_{w_j}L(w_1,...,w_m) for j=1,..., m.
In this problem, since a_j and u_j are fixed, then model f is just a linear model w.r.t. w_j’s and the above problem is just a simple linear regression problem. Therefore, it is not difficult to prove the linear convergence rate for the gradient descent for the above problem under some mild assumptions.  Note that in this paper, u_j(t)= w_j(t) and are not fixed in iterations, i.e., patterns can change. 
=========================
First, I apologize to the authors and ACs for the late review, since this paper desearves much more time to judge the quality. 
Summary: This paper proves that the gradient descent/flow converges to the global optimum with zero training error under the settings (1) the neural network is a heavily over-parameterized ReLU network (i.e., requiting Omega(n^6) neurons); (2) the algorithm update rule “ignores” the non-differentiable point; (3) the parameters in the output layer (i.e., a_i’s) are fixed; (4) the data set has some non-degenerate properties and comes from a unit ball. The proof relies on the fact that the Gram matrix is always positive definite on the converging trajectory. 
Pros: The proof is simple and seems to be correct. The paper is paper is written clearly  and easy to follow. 
Cons:
The problem setting considered in this paper does not seem to be difficult enough. The difficulty of analyzing the landscape property of a ReLU network and proving the global convergence of the gradient descent mainly lies in the following three perspective and this paper does not try to tackle any one of them. 
First, it is very hard to characterize the landscape or the convergence trajectory at/ near the non-differentiable point and this paper fails to touch it. The parameter space is separated into several regions by the hyperplanes and the loss function is differentiable in the interior of each region and non-differentiable on the boundary. I believe the very first question authors need to answer is wether there are critical points on the boundary and why the sub-gradient descent escapes from  any of these points. However, in this paper, authors avoid this problem by defining an update rule used  in practice and this rule does not use the sub-gradient at the non-differentiable point. Thus, it is totally unclear to me wether this global convergence result comes from the fact that this update rule can generally avoid the non-differentiable  points on the boundary or the fact that the landscape is so nice such that there are no critical points on the boundary or the fact that all points on the convergence trajectory is differentiable only in this unique problem.
Second, the problem is much easier if the loss is not jointly optimized over the parameters in the first and second layer. Having parameters in one layer fixed does not seem to be a big problem at first glance, but then I realize it indeed makes the problem much easier, which can be seen in the following example. If we randomly sample the weight vector w_i from N(0, I) and only optimize  over the parameters in the second layer, then it is straightforward to show the following result.
Result: If \lambda_\min(H^\inf)>0 and m=\Omega(n\log n), then with high probability, the loss function L is strongly convex with respect to a=(a_1,…, a_m) and the loss function is zero at the global minimum.
The above result shows that if we fix the parameters in the first layer and only optimize the parameters in the second layer, it is easy to prove the global convergence with a linear convergence rate. In fact, this result does not require the samples coming from a unit ball and the network size is only slightly over-parameterized. Therefore, if we are allowed to fix the parameters in some layer, how are the result presented in this paper fundamentally different from the above result. 
Authors may say that the loss is not convex with respect to the weights in the first layer even if the second layer is fixed. However, when the second layer is fixed, the loss function is  smooth and convex in each parameter region and some recent works have shown that in this case, the loss function is a weakly global function. This means that the loss function is similar to a convex function except those plateaus and this further indicates that if the initial point is chosen in a strictly convex basin, the gradient descent is able to converge to a global min.  However, the problem becomes far more difficult if the loss is jointly optimized over  all parameters in the first and second layer. This can be easily seen since in each parameter region, the loss is no longer a convex function and this may lead to some high order saddle points such that the gradient descent cannot provably escape. Furthermore, the critical points on the boundary can be much more difficult to characterize for this joint optimization problem. 
Third, the dataset considered in this paper does not seem to be a fundamental pattern and it seems more like a technical condition required by the proof. It is easy to see that a linearly separable dataset does not necessarily satisfy the conditions that 1) the gram matrix is positive definite and that 2) samples come from the surface of a unit ball. Therefore, I do not understand the reason why we need to analyze this pattern. Clearly, in practice, the data samples is unlikely sampled from a ball surface and it is totally unclear to me why the gram matrix is necessarily positive definite. I understand that some technical assumptions are needed in a theoretical work, but I would like to see more discussions on the dataset, e.g., some necessary conditions on the dataset such that the global convergence is possible.
Last, I understand that the over-parameterization assumption is needed. In fact, I expect the network size to be of the order Omega(n*ploylog(n)). I am wondering wether Omega(n^6) is a necessary condition or wether there exists a case such that Theta(n^6) is required. 
Above all, I believe this paper is a half-baked paper with some interesting explorations. In summary, it cannot deal with non-differential points, which is considered a major difficulty for analyzing ReLU. In addition, it makes an un-justified assumption on some matrix, it requires too many neurons, and fixed 2nd layer. With so many strong assumptions, and compared to related works like [1], Mei et al., Bach and ..., its contribution is rather limited.
[1] https://arxiv.org/abs/1702.05777