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. arXiv:1705.09886v1 [cs.LG] 28 May 2017 Expressivity. Even two-layer network has great expressive power. For example, two-layer network with sigmoid activations could approximate any continuous function [19, 6, 3] . ReLU is the state-of-the-art activation function, and performs much better than sigmoid [26, 12] , but fewer and weaker results on expressivity of feedforward ReLU networks are known [25, 28, 27] . Learning. Most previous results on learning neural network are negative [35, 24, 34] , or positive but with special algorithms other than SGD [20, 39, 33, 13] , or with strong assumptions on the model [1, 2] . [31] proved that with high probability, there exists a continuous decreasing path from random initial point to the global minimum, but SGD may not follow this path. Linear network and independent activation. Some previous works simplified the model by ignoring the activation functions and considering deep linear networks [32, 21] or deep linear residual networks [16] , which can only learn linear functions. Some previous results are based on independent activation assumption that the activations of ReLU and the input are independent, which is unrealistic [4, 21] . Saddle points. It is observed that saddle point is not a big problem for neural networks [8, 15] . In general, if the objective is strict-saddle [10], SGD could escape all saddle points.
REF showed SGD can recover the true weights of a one-layer ResNet model with ReLU activation under the assumption that the spectral norm of the true weights is within a small constant of the identity mapping.
Convergence Analysis of Two-layer Neural Networks with ReLU Activation
ArXiv
ArXiv
Computer Science Mathematics