Understanding How Over-Parametrization Leads to Acceleration: A case of learning a single teacher neuron

2020/10/04 by Jun-Kun Wang, Wang, Jun-Kun, Jacob Abernethy +1
Computer Science · Physics and Astronomy · #Advanced Neural Network Applications #Advanced X-ray Imaging Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Model Reduction and Neural Networks

paper · pdf · doi:10.48550/arxiv.2010.01637

openalex publication_date 2020/10/04 · openalex created_date 2020/10/08 · openalex updated_date 2026/07/28

Abstract

Over-parametrization has become a popular technique in deep learning. It is observed that by over-parametrization, a larger neural network needs a fewer training iterations than a smaller one to achieve a certain level of performance -- namely, over-parametrization leads to acceleration in optimization. However, despite that over-parametrization is widely used nowadays, little theory is available to explain the acceleration due to over-parametrization. In this paper, we propose understanding it by studying a simple problem first. Specifically, we consider the setting that there is a single teacher neuron with quadratic activation, where over-parametrization is realized by having multiple student neurons learn the data generated from the teacher neuron. We provably show that over-parametrization helps the iterate generated by gradient descent to enter the neighborhood of a global optimal solution that achieves zero testing error faster. On the other hand, we also point out an issue regarding the necessity of over-parametrization and study how the scaling of the output neurons affects the convergence time.

Citations

• Phase Retrieval with Application to Optical Imaging: A contemporary overview
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
• Efficient Learning of Generalized Linear and Single Index Models with\n Isotonic Regression
• Reliably Learning the ReLU in Polynomial Time
• The loss surface of deep and wide neural networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Decoupled Weight Decay Regularization
• Implicit Regularization in Deep Matrix Factorization
• Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals
• Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently
• Stationary Points of Shallow Neural Networks with Quadratic Activation\n Function
• Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena
• Agnostic Learning of a Single Neuron with Gradient Descent

Related

• Nearly Minimal Over-Parametrization of Shallow Neural Networks
• On the Power of Over-parametrization in Neural Networks with Quadratic Activation
• Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time
• On the Impact of Overparameterization on the Training of a Shallow Neural Network in High Dimensions
• On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization