Deep neural networks (DNNs) have demonstrated dominating performance in many fields; since AlexNet, networks used in practice are going wider and deeper. On the theoretical side, a long line of works have been focusing on why we can train neural networks when there is only one hidden layer. The theory of multi-layer networks remains unsettled. In this work, we prove simple algorithms such as stochastic gradient descent (SGD) can find global minima on the training objective of DNNs in polynomial time. We only make two assumptions: the inputs do not degenerate and the network is over-parameterized. The latter means the number of hidden neurons is sufficiently large: polynomial in L, the number of DNN layers and in n, the number of training samples. As concrete examples, starting from randomly initialized weights, we show that SGD attains 100% training accuracy in classification tasks, or minimizes regression loss in linear convergence speed ε ∝ e −Ω(T ) , with running time polynomial in n and L. Our theory applies to the widely-used but non-smooth ReLU activation, and to any smooth and possibly non-convex loss functions. In terms of network architectures, our theory at least applies to fully-connected neural networks, convolutional neural networks (CNN), and residual neural networks (ResNet).* Equal contribution . Full version and future updates are available at https://arxiv.org/abs/1811.03962.This paper is a follow up to the recurrent neural network (RNN) paper (Allen-Zhu et al., 2018b) by the same set of authors. Most of the techniques used in this paper were already discovered in the RNN paper, and this paper can be viewed as a simplification (or to some extent a special case) of the RNN setting in order to reach out to a wider audience. We compare the difference and mention our additional contribution in Section 1.2.
translated by 谷歌翻译