Convergence Analysis of Two-layer Neural Networks with ReLU Activation
In recent years, stochastic gradient descent (SGD) based techniques has become the standard tools for training neural networks. However, formal theoretical understanding of why SGD can train neural networks in practice is largely missing. In this paper, we make progress on understanding this mystery by providing a convergence analysis for SGD on a rich subset of two-layer feedforward networks with ReLU activations. This subset is characterized by a special structure called "identity mapping". We prove that, if input follows from Gaussian distribution, with standard O(1/ √ d) initialization of the weights, SGD converges to the global minimum in polynomial number of steps. Unlike normal vanilla networks, the "identity mapping" makes our network asymmetric and thus the global minimum is unique. To complement our theory, we are also able to show experimentally that multi-layer networks with this mapping have better performance compared with normal vanilla networks. Our convergence theorem differs from traditional non-convex optimization techniques. We show that SGD converges to optimal in "two phases": In phase I, the gradient points to the wrong direction, however, a potential function g gradually decreases. Then in phase II, SGD enters a nice one point convex region and converges. We also show that the identity mapping is necessary for convergence, as it moves the initial point to a better place for optimization. Experiment verifies our claims.
This paper proves the convergence of a stochastic gradient descent algorithm from a suitable starting point to the global minimizer of a nonconvex energy representing the loss of a two-layer feedforward network with rectified linear unit activation. In particular, the algorithm is shown to converge in two phases, where phase 1 drives the iterates into a one-point convex region which subsequently leads to the actual convergence in phase 2. 
The findings, the analysis, and particularly the methodology for proving the convergence (in 2 phases) are very interesting and definitely deserve to be published. 
The entire proof is extremely long (including a flowchart of 15 Lemmas/Theorems that finally allow to show the main theorem in 25 pages of proofs), and I have to admit that I did not check this part. 
I have some questions on the paper and suggestions to further improve the manuscript:
- Figure 1 points out the different structure of the considered networks, and even the abstract already refers to the special structure of "identity mappings". However, optimizing for W (vanilla network) is equivalent to optimizing for (W+I), such that the difference seems to lie in different starting points only. If this is correct, I strongly suggest to emphasize the starting point rather than the identity mapping. In this case, please shorten the connection to ResNet. 
- There is a fundamental difference between the architecture shown in figure 1 (which is analyzed in the proofs), and the experiments in sections 5.1, 5.4, and 5.5. In particular, the ResNet trick of an identity shortcut behaves fundamentally different if the identity is used after a nonlinearity (e.g. BatchNorm in Figure 6 and ReLu in the ResNet Paper), opposed to an equivalent reformulation of the original network in Figure 1. Moreover, sections 5.1, 5.4, and 5.5 consider deep networks that have not been analyzed theoretically. Since your theoretical results deal with the 2-layer architecture shown in Figure 1, I suggest to reduce the numerical experiments that go well beyond the theoretically studied case, and instead explain the latter in more detail. It certainly contains enough material. In particular, it would be interesting to understand how close real-world data is to satisfying the assumptions of Theorem 3.1. 
- For a paper of the technical precision such as the one presented here, I think one should not talk about taking the derivative of a ReLU function without a comment. The ReLU is not differentiable whenever any component is zero - so what exactly is \nabla L(W)? In a convex setting one would consider a subgradient, but what is the right object here? A weak derivative?
- Related to the previous question, subgradient descent on a convex function already requires the step size to go to zero in order to state convergence results. Can you comment on why you can get away with constant step sizes?
- The plots in Figures 7 and 8 are difficult to read and would benefit from more detailed explanations, and labeled axes. 
- I recommend to carefully check the manuscript with respect to third person singular verbs and plural nouns. Also, some letters are accidently capitalized after a comma.