2018

On the Benefit of Width for Neural Networks: Disappearance of Bad Basins

Li, Dawei, Ding, Tian, Sun, Ruoyu

Understand

Wide networks are often believed to have a nice optimization landscape, but what rigorous results can we prove? To understand the benefit of width, it is important to identify the difference between wide and narrow networks.

In this work, we prove that from narrow to wide networks, there is a phase transition from having sub-optimal basins to no sub-optimal basins.
Specifically, we prove two results: on the positive side, for any continuous activation functions, the loss surface of a class of wide networks has no sub-optimal basins, where "basin" is defined as the set-wise strict local minimum; on the negative side, for a large class of networks with width below a threshold, we construct strict local minima that are not global.
These two results together show the phase transition from narrow to wide networks.

Built on

Approximation by entire functions
Wilfred Kaplan · 1955
Earlier work this paper cites.
Neural networks and principal component analysis: Learning from examples without local minima
P. Baldi and K. Hornik · 1989
Earlier work this paper cites.
On the problem of local minima in backpropagation
Marco Gori and Alberto Tesi · 1992
Earlier work this paper cites.
On the local minima free condition of backpropagation learning
Xiao-Hu Yu and Guo-An Chen · 1995
Earlier work this paper cites.
On the computational efficiency of training neural networks
Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir · 2014
Earlier work this paper cites.
Learning polynomials with neural networks
A. Andoni, R. Panigrahy, G. Valiant, and L. Zhang · 2014
Earlier work this paper cites.
Provable methods for training neural networks with sparse connectivity
Original
H. Sedghi and A. Anandkumar · 2014
Earlier work this paper cites.
Representation benefits of deep feedforward networks
Original
Matus Telgarsky · 2015
Earlier work this paper cites.
Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding
Original
Song Han, Huizi Mao, and William J Dally · 2015
Earlier work this paper cites.
Beating the perils of non-convexity: Guaranteed training of neural networks using tensor methods
Original
M. Janzamin, H. Sedghi, and A. Anandkumar · 2015
Earlier work this paper cites.
Global optimality in tensor factorization, deep learning, and beyond
Original
B. D Haeffele and R. Vidal · 2015
Earlier work this paper cites.
The zero set of a real analytic function
Original
Boris Mityagin · 2015
Earlier work this paper cites.
Deep residual learning for image recognition
K. He, X. Zhang, S. Ren, and J. Sun · 2016
Earlier work this paper cites.
Globally optimal training of generalized polynomial neural networks with nonlinear spectral methods
A. Gautier, Q. N. Nguyen, and M. Hein · 2016
Earlier work this paper cites.
Deep learning without poor local minima
K. Kawaguchi · 2016
Earlier work this paper cites.
Topology and geometry of half-rectified network optimization
C D. Freeman and J. Bruna · 2016
Earlier work this paper cites.
Gaussian error linear units (GeLUs)
Original
Dan Hendrycks and Kevin Gimpel · 2016
Earlier work this paper cites.
The loss surface of deep and wide neural networks
Q. Nguyen and M. Hein · 2017
Earlier work this paper cites.
Globally optimal gradient descent for a convnet with gaussian inputs
Original
A. Brutzkus and A. Globerson · 2017
Earlier work this paper cites.
Learning ReLUs via gradient descent
M. Soltanolkotabi · 2017
Earlier work this paper cites.
Exponentially vanishing sub-optimal local minima in multilayer neural networks
Original
D. Soudry and E. Hoffer · 2017
Earlier work this paper cites.
Learning depth-three neural networks in polynomial time
Original
S. Goel and A. Klivans · 2017
Earlier work this paper cites.
Theoretical properties of the global optimizer of two layer neural network
Original
D. Boob and G. Lan · 2017
Earlier work this paper cites.
When is a convolutional filter easy to learn?
Original
S. S. Du, J. D. Lee, and Y. Tian · 2017
Earlier work this paper cites.
Recovery guarantees for one-hidden-layer neural networks
K. Zhong, Z. Song, P. Jain, P. L Bartlett, and I. S Dhillon · 2017
Earlier work this paper cites.
Convergence analysis of two-layer neural networks with ReLU activation
Y. Li and Y. Yuan · 2017
Earlier work this paper cites.
An analytical formula of population gradient for two-layered ReLU network and its applications in convergence and critical point analysis
Yuandong Tian · 2017
Earlier work this paper cites.
Identity matters in deep learning
M. Hardt and T. Ma · 2017
Earlier work this paper cites.
Global optimality conditions for deep neural networks
Original
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie · 2017
Earlier work this paper cites.
The loss surface and expressivity of deep convolutional neural networks
Original
Q. Nguyen and M. Hein · 2017
Earlier work this paper cites.

Similar

Exploring generalization in deep learning
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro · 2017
Cited alongside, same era.
Spectrally-normalized margin bounds for neural networks
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky · 2017
Cited alongside, same era.
Neural tangent kernel: Convergence and generalization in neural networks
Arthur Jacot, Franck Gabriel, and Clément Hongler · 2018
Cited alongside, same era.
A convergence theory for deep learning via over-parameterization
Original
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song · 2018
Cited alongside, same era.
Stochastic gradient descent optimizes over-parameterized deep ReLU networks
Original
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu · 2018
Cited alongside, same era.
Gradient descent provably optimizes over-parameterized neural networks, 2018
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh · 2018
Cited alongside, same era.
A mean field view of the landscape of two-layers neural networks
Original
Song Mei, Andrea Montanari, and Phan-Minh Nguyen · 2018
Cited alongside, same era.
Mean field analysis of neural networks
Original
Justin Sirignano and Konstantinos Spiliopoulos · 2018
Cited alongside, same era.
Neural networks as interacting particle systems: Asymptotic convexity of the loss landscape and universal scaling of the approximation error
Original
Grant M Rotskoff and Eric Vanden-Eijnden · 2018
Cited alongside, same era.
Easing non-convex optimization with neural networks
David Lopez-Paz and Levent Sagun · 2018
Cited alongside, same era.
Learning one-hidden-layer neural networks with landscape design
R. Ge, J. D Lee, and T. Ma · 2018
Cited alongside, same era.
Understanding the loss surface of neural networks for binary classification
S. Liang, R. Sun, Y. Li, and R. Srikant · 2018
Cited alongside, same era.

Then

Mean field limit of the learning dynamics of multilayer neural networks
Original
Phan-Minh Nguyen · 2019
Closest in time.
Regularization matters: Generalization and optimization of neural nets vs their induced kernel
Colin Wei, Jason Lee, Qiang Liu, and Tengyu Ma · 2019
Closest in time.
Spurious local minima exist for almost all over-parameterized neural networks
Tian Ding, Dawei Li, and Ruoyu Sun · 2019
Closest in time.
The difficulty of training sparse neural networks
Original
Utku Evci, Fabian Pedregosa, Aidan Gomez, and Erich Elsen · 2019
Closest in time.
Learning ReLU networks on linearly separable data: Algorithm, optimality, and generalization
Gang Wang, Georgios B Giannakis, and Jie Chen · 2019
Closest in time.
Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks
Original
Ziwei Ji and Matus Telgarsky · 2019
Closest in time.
How much over-parameterization is sufficient to learn deep relu networks?
Original
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu · 2019
Closest in time.
On the expressive power of deep polynomial neural networks
Original
Joe Kileel, Matthew Trager, and Joan Bruna · 2019
Closest in time.
RoBERTa: A robustly optimized BERT pretraining approach
Original
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov · 2019
Closest in time.
The generalization error of random features regression: Precise asymptotics and double descent curve
Original
Song Mei and Andrea Montanari · 2019
Closest in time.
On connected sublevel sets in deep learning
Original
Quynh Nguyen · 2019
Closest in time.
EfficientNet: Rethinking model scaling for convolutional neural networks
Original
Mingxing Tan and Quoc V Le · 2019
Closest in time.
Network slimming by slimmable networks: Towards one-shot architecture search for channel numbers
Original
Jiahui Yu and Thomas Huang · 2019
Closest in time.
The lottery ticket hypothesis: Finding sparse, trainable neural networks
Jonathan Frankle and Michael Carbin · 2019
Closest in time.
Training neural networks as learning data-adaptive kernels: Provable representation and approximation benefits
Xialiang Dou and Tengyuan Liang · 2020
Closest in time.
A generalized neural tangent kernel analysis for two-layer neural networks
Original
Zixiang Chen, Yuan Cao, Quanquan Gu, and Tong Zhang · 2020
Closest in time.
Towards a better global loss landscape of GANs
Ruoyu Sun, Tiantian Fang, and Alexander Schwing · 2020
Closest in time.
On sparsity in overparametrised shallow ReLU networks
Original
Jaume de Dios and Joan Bruna · 2020
Closest in time.
All local minima are global for two-layer ReLU neural networks: The hidden convex optimization landscape
Original
Jonathan Lacotte and Mert Pilanci · 2020
Closest in time.
Loss landscapes and optimization in over-parameterized non-linear systems and neural networks
Original
Chaoyue Liu, Libin Zhu, and Mikhail Belkin · 2020
Closest in time.
Dynamics of deep neural networks and neural tangent hierarchy
Jiaoyang Huang and Horng-Tzer Yau · 2020
Closest in time.
Toward moderate overparameterization: Global convergence guarantees for training shallow neural networks
Samet Oymak and Mahdi Soltanolkotabi · 2020
Closest in time.
Implicit neural representations with periodic activation functions, 2020
Vincent Sitzmann, Julien N. P. Martel, Alexander W. Bergman, David B. Lindell, and Gordon Wetzstein · 2020
Closest in time.
The global landscape of neural networks: An overview
Ruoyu Sun, Dawei Li, Shiyu Liang, Tian Ding, and Rayadurgam Srikant · 2020
Closest in time.
On the stability properties and the optimization landscape of training problems with squared loss for neural networks and general nonlinear conic approximation schemes
Original
Constantin Christof · 2020
Closest in time.
Modeling from features: a mean-field framework for over-parameterized deep neural networks
Cong Fang, Jason Lee, Pengkun Yang, and Tong Zhang · 2021
Closest in time.
Analytic study of families of spurious minima in two-layer ReLU neural networks
Original
Yossi Arjevani and Michael Field · 2021
Closest in time.
On the proof of global convergence of gradient descent for deep ReLU networks with linear widths
Original
Quynh Nguyen · 2021
Closest in time.
Global minima of overparameterized neural networks
Yaim Cooper · 2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…