Gradient Descent Provably Optimizes Over-parameterized Neural Networks
This provides a theoretical foundation for understanding optimization in over-parameterized neural networks, addressing a key problem for machine learning researchers, though it is incremental as it focuses on shallow models.
The paper tackles the mystery of why gradient descent can achieve zero training loss in non-convex neural networks by proving that for two-layer ReLU networks with sufficient over-parameterization and non-parallel inputs, randomly initialized gradient descent converges linearly to a global optimum for quadratic loss.
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.