Under sufficient over-parametrization by width with fixed depth, many popular neural network architectures (including feed-forward, convolutional, and residual) with ReLU activation find a global optimum in linear time with respect to the remaining error and the trained network generalizes well [1]}, [2]}. However, the associated generalization bounds are intractable, and the amount of over-parametrization implied in these results is often unrealistically large. One can improve the asymptotic analysis [3]}, [4]}, but it still falls short of leading to any practical insight. For smooth activation functions, [5]} studied the convergence of gradient descent for various network architectures, including residual networks. They show that for any depth, if the residual layers are wide enough and the learning rate is small enough, gradient descent on the empirical mean-squared loss converges to a solution with zero training loss in linear time. The rate of convergence is proportional to the learning rate and the minimum eigenvalue of the Gram matrix. [6]} showed that in the over-parametrized regime, for a suitable initialization with the last layer initialized at zero and other weights initialized uniformly, gradient descent can find a global minimum exponentially fast with high probability.
