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

Abstract

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.

arXiv commentAccepted by ICML 2018

Cited by in corpus (54)

• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Gradient Descent Finds Global Minima of Deep Neural Networks
• How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks
• One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers
• A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks
• Gradient Descent Maximizes the Margin of Homogeneous Neural Networks
• Playing the lottery with rewards and multiple languages: lottery tickets in RL and NLP
• A Modern Take on the Bias-Variance Tradeoff in Neural Networks
• Depth with Nonlinearity Creates No Bad Local Minima in ResNets
• Convergence of Adversarial Training in Overparametrized Neural Networks
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don't
• Spurious Valleys in Two-layer Neural Network Optimization Landscapes
• Elimination of All Bad Local Minima in Deep Learning
• Understanding Self-supervised Learning with Dual Deep Networks
• Exponential convergence rates for Batch Normalization: The power of length-direction decoupling in non-convex optimization
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• On the Power and Limitations of Random Features for Understanding Neural Networks
• Optimization and Generalization of Shallow Neural Networks with Quadratic Activation Functions
• Knowledge distillation via adaptive instance normalization
• Effect of Activation Functions on the Training of Overparametrized Neural Nets
• Understanding Generalization in Deep Learning via Tensor Methods
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics
• Convex Geometry and Duality of Over-parameterized Neural Networks
• Deep Neural Networks with Multi-Branch Architectures Are Less Non-Convex
• Stationary Points of Shallow Neural Networks with Quadratic Activation Function
• Policy Search with Rare Significant Events: Choosing the Right Partner to Cooperate with
• Universal Approximation with Quadratic Deep Networks
• Improved Learning of One-hidden-layer Convolutional Neural Networks with Overlaps
• On Expressivity and Trainability of Quadratic Networks
• Avoiding Spurious Local Minima in Deep Quadratic Networks
• A Dynamical View on Optimization Algorithms of Overparameterized Neural Networks
• Towards an Understanding of Residual Networks Using Neural Tangent Hierarchy (NTH)
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
• Architecture Selection via the Trade-off Between Accuracy and Robustness
• Understanding Global Loss Landscape of One-hidden-layer ReLU Networks, Part 1: Theory
• Sub-Optimal Local Minima Exist for Neural Networks with Almost All Non-Linear Activations
• On the Global Convergence of Gradient Descent for multi-layer ResNets in the mean-field regime
• Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time
• Implicit regularization and solution uniqueness in over-parameterized matrix sensing
• On the Provable Generalization of Recurrent Neural Networks
• Robust Generalization of Quadratic Neural Networks via Function Identification
• Neural Networks with Complex-Valued Weights Have No Spurious Local Minima
• SGD Through the Lens of Kolmogorov Complexity
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results
• Adaptive norms for deep learning with regularized Newton methods
• PDE constraints on smooth hierarchical functions computed by neural networks
• The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural Networks: an Exact Characterization of the Optimal Solutions
• MARS: Masked Automatic Ranks Selection in Tensor Decompositions
• Understanding How Over-Parametrization Leads to Acceleration: A case of learning a single teacher neuron
• Benefits of over-parameterization with EM
• Second-Order Convergence of Asynchronous Parallel Stochastic Gradient Descent: When Is the Linear Speedup Achieved?