On the Power of Over-parametrization in Neural Networks with Quadratic Activation

By Simon Shaolei Du, Jason D. Lee. 2018

293 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks (2018, background): “Ge et al. (2015); Lee et al. (2016)) have shown that (given certain smoothness properties) it suffices for critical points to meet the following two conditions: (i) no poor local minima — every local minimum is close in its objective value to a global minimum; and (ii) strict saddle property — every”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, neutral): “…to characterize geometric landscapes of objective functions (Safran & Shamir, 2017; Zhou & Liang, 2017; Freeman & Bruna, 2016; Hardt & Ma, 2016; Nguyen & Hein, 2017; Kawaguchi, 2016; Venturi et al., 2018; Soudry & Carmon, 2016; Du & Lee, 2018; Soltanolkotabi et al., 2018; Haeﬀele & Vidal, 2015).”
Gradient Descent Finds Global Minima of Deep Neural Networks (2018, background): “…functions [Soudry and Hoffer, 2017, Safran and Shamir, 2018, 2016, Zhou and Liang, 2017, Freeman and Bruna, 2016, Hardt and Ma, 2016, Nguyen and Hein, 2017, Kawaguchi, 2016, Venturi et al., 2018, Soudry and Carmon, 2016, Du and Lee, 2018, Soltanolkotabi et al., 2018, Haeffele and Vidal, 2015].”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “Du and Lee (2018) showed that with over-parameterization, all local minima in one-hidden-layer networks with quardratic activation function are global minima.”
Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced (2018, background): “There have been many studies on the optimization landscapes of neural networks [Kawaguchi, 2016, Choromanska et al., 2015, Du and Lee, 2018, Hardt and Ma, 2016, Bartlett et al., 2018, Haeﬀele and Vidal, 2015, Freeman and Bruna, 2016, Vidal et al., 2017, Safran and Shamir, 2016, Zhou and Feng, 2017,…”
A Modern Take on the Bias-Variance Tradeoff in Neural Networks (2018, background): “A body of recent work has provided evidence that over-parameterization (in width) helps gradient descent optimize to global minima in neural networks (Du et al., 2019; Du & Lee, 2018; Soltanolkotabi et al., 2017; Livni et al., 2014; Zhang et al., 2018).”
Deep Neural Networks with Multi-Branch Architectures Are Less Non-Convex (2018, background): “Given the computational obstacles, several efforts have been devoted to designing new architectures to alleviate the above issues, including over-parametrization [17, 54, 23, 41, 2, 46] and multi-branch architectures [57, 18, 63, 33, 60].”
A Generalization Theory of Gradient Descent for Learning Over-parameterized Deep ReLU Networks (2019, background): “…2016; Hardt and Ma, 2016; Safran and Shamir, 2017; Xie et al., 2017; Nguyen and Hein, 2017; Soltanolkotabi et al., 2017; Zhou and Liang, 2017; Yun et al., 2017; Du and Lee, 2018; Venturi et al., 2018) investigated the optimization landscape of neural networks with different activation functions.”
Ellipsoidal Trust Region Methods and the Marginal Value of Hessian Information for Neural Network Training (2019, background): “For neural network training, a recent line of research proclaims the effectiveness of SGD but the results usually come at the cost of fairly strong assumptions such as heavy overparametrization and Gaussian inputs [28, 12, 50, 29, 5].”
Width Provably Matters in Optimization for Deep Linear Neural Networks (2019, background): “Many papers tried to identify the two desired geometric landscape properties of objective functions for non-linear neural networks (Freeman & Bruna, 2016; Nguyen & Hein, 2017; Venturi et al., 2018; Soudry & Carmon, 2016; Du & Lee, 2018; Soltanolkotabi et al., 2018; Haeffele & Vidal, 2017).”
Learning One-hidden-layer ReLU Networks via Gradient Descent (2018, background): “…Kawaguchi, 2016; Hardt and Ma, 2016; Soltanolkotabi et al., 2017; Soudry and Carmon, 2016; Xie et al., 2017; Nguyen and Hein, 2017; Ge et al., 2017; Safran and Shamir, 2017; Yun et al., 2017; Du and Lee, 2018) attempted to understand neural networks by characterizing their optimization landscape.”
Playing the lottery with rewards and multiple languages: lottery tickets in RL and NLP (2019, background): “This phenomenon suggests that over-parameterization in DNN training is beneficial primarily due to proper initialization rather than regularization during the training process itself [1, 2, 6, 7, 20, 21].”
Adaptive norms for deep learning with regularized Newton methods (2019, background): “For neural networks, a recent line of research proclaims the effectiveness of SGD, but the results come at the cost of strong assumptions such as heavy over-parametrization and Gaussian inputs (Du et al., 2017; Brutzkus & Globerson, 2017; Li & Yuan, 2017; Du & Lee, 2018; Allen-Zhu et al., 2018).”
An Improved Analysis of Training Over-parameterized Deep Neural Networks (2019, background): “To better understand the training of neural networks, there is a line of research (Tian, 2017; Brutzkus and Globerson, 2017; Du et al., 2017; Li and Yuan, 2017; Zhong et al., 2017; Du and Lee, 2018; Zhang et al., 2018) studying two-layer (i.”
Limitations of Lazy Training of Two-layers Neural Networks (2019, background): “Du and Lee [9] showed that the same holds as long as N ≥ d ∧ √ 2n where n is the sample size.”