On the Power of Over-parametrization in Neural Networks with Quadratic Activation
This provides theoretical insights into a fundamental issue in deep learning for researchers, though it is incremental as it builds on existing work on over-parametrization.
The paper tackles the problem of understanding why over-parametrization helps in neural network training by proving that for shallow networks with quadratic activation, if the number of hidden nodes is at least sqrt(2n) where n is the sample size, local search algorithms can find globally optimal solutions for smooth convex losses, and with weight decay, the solution generalizes well under regular distributions like Gaussian.
We provide new theoretical insights on why over-parametrization is effective in learning neural networks. For a $k$ hidden node shallow network with quadratic activation and $n$ training data points, we show as long as $ k \ge \sqrt{2n}$, over-parametrization enables local search algorithms to find a \emph{globally} optimal solution for general smooth and convex loss functions. Further, despite that the number of parameters may exceed the sample size, using theory of Rademacher complexity, we show with weight decay, the solution also generalizes well if the data is sampled from a regular distribution such as Gaussian. To prove when $k\ge \sqrt{2n}$, the loss function has benign landscape properties, we adopt an idea from smoothed analysis, which may have other applications in studying loss surfaces of neural networks.