2019

Sub-Optimal Local Minima Exist for Neural Networks with Almost All Non-Linear Activations

Ding, Tian, Li, Dawei, Sun, Ruoyu

Understand

Does over-parameterization eliminate sub-optimal local minima for neural networks? An affirmative answer was given by a classical result in [59] for 1-hidden-layer wide neural networks.

A few recent works have extended the setting to multi-layer neural networks, but none of them has proved every local minimum is global.
Why is this result never extended to deep networks? In this paper, we show that the task is impossible because the original result for 1-hidden-layer network in [59] can not hold.
More specifically, we prove that for any multi-layer network with generic input data and non-linear activation functions, sub-optimal local minima can exist, no matter how wide the network is (as long as the last hidden layer has at least two neurons).

Built on

Backpropagation can give rise to spurious local minima even for networks without hidden layers
Eduardo D Sontag and Héctor J Sussmann · 1989
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.
Exponentially many local minima for single neurons
Peter Auer, Mark Herbster, and Manfred K Warmuth · 1996
Earlier work this paper cites.
Optimal learning in artificial neural networks: A review of theoretical results
Monica Bianchini and Marco Gori · 1996
Earlier work this paper cites.
Qualitatively characterizing neural network optimization problems
Original
Ian J Goodfellow, Oriol Vinyals, and Andrew M Saxe · 2014
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.
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.
The zero set of a real analytic function
Original
Boris Mityagin · 2015
Earlier work this paper cites.
Global optimality of local search for low rank matrix recovery
Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro · 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.
Matrix completion has no spurious local minimum
Rong Ge, Jason D Lee, and Tengyu Ma · 2016
Earlier work this paper cites.
Deep learning without poor local minima
K. Kawaguchi · 2016
Earlier work this paper cites.
Why deep neural networks for function approximation?
Original
Shiyu Liang and Rayadurgam Srikant · 2016
Earlier work this paper cites.
Guaranteed matrix completion via non-convex factorization
Ruoyu Sun and Zhi-Quan Luo · 2016
Earlier work this paper cites.
Local minima in training of deep networks
Grzegorz Swirszcz, Wojciech Marian Czarnecki, and Razvan Pascanu · 2016
Earlier work this paper cites.
Benefits of depth in neural networks
Original
Matus Telgarsky · 2016
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.
Porcupine neural networks:(almost) all local optima are global
Original
Soheil Feizi, Hamid Javadi, Jesse Zhang, and David Tse · 2017
Earlier work this paper cites.
Global optimality in neural network training
Benjamin D Haeffele and René Vidal · 2017
Earlier work this paper cites.
The multilinear structure of relu networks
Original
Thomas Laurent and James von Brecht · 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.
Depth creates no bad local minima
Original
Haihao Lu and Kenji Kawaguchi · 2017
Earlier work this paper cites.

Similar

Convergence results for neural networks via electrodynamics
Original
Rina Panigrahy, Ali Rahimi, Sushant Sachdeva, and Qiuyi Zhang · 2017
Cited alongside, same era.
Depth-width tradeoffs in approximating natural functions with neural networks
Itay Safran and Ohad Shamir · 2017
Cited alongside, same era.
Learning relus via gradient descent
M. Soltanolkotabi · 2017
Cited alongside, same era.
Exponentially vanishing sub-optimal local minima in multilayer neural networks
Original
D. Soudry and E. Hoffer · 2017
Cited alongside, same era.
An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis
Yuandong Tian · 2017
Cited alongside, same era.
Recovery guarantees for one-hidden-layer neural networks
K. Zhong, Z. Song, P. Jain, P. L Bartlett, and I. S Dhillon · 2017
Cited alongside, same era.
Critical points of neural networks: Analytical forms and landscape properties
Original
Yi Zhou and Yingbin Liang · 2017
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.
Sgd learns over-parameterized networks that provably generalize on linearly separable data
A. Brutzkus, A. Globerson, E. Malach, and S. Shalev-Shwartz · 2018
Cited alongside, same era.
On the global convergence of gradient descent for over-parameterized models using optimal transport
Original
Lenaic Chizat and Francis Bach · 2018
Cited alongside, same era.
Essentially no barriers in neural network energy landscape
Original
Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred A Hamprecht · 2018
Cited alongside, same era.
On the power of over-parametrization in neural networks with quadratic activation
Original
S. S Du and J. D Lee · 2018
Cited alongside, same era.

Then

Adding one neuron can eliminate all bad local minima
Shiyu Liang, Ruoyu Sun, Jason D Lee, and R Srikant · 2018
Later among the works it cites.
Easing non-convex optimization with neural networks
David Lopez-Paz and Levent Sagun · 2018
Later among the works it cites.
A mean field view of the landscape of two-layers neural networks
Original
Song Mei, Andrea Montanari, and Phan-Minh Nguyen · 2018
Later among the works it cites.
On the connection between learning two-layers neural networks and tensor decomposition
Original
Marco Mondelli and Andrea Montanari · 2018
Later among the works it cites.
On the loss landscape of a class of deep neural networks with no bad local valleys
Original
Quynh Nguyen, Mahesh Chandra Mukkamala, and Matthias Hein · 2018
Later among the works it cites.
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
Later among the works it cites.
Spurious local minima are common in two-layer relu neural networks
Itay Safran and Ohad Shamir · 2018
Later among the works it cites.
Mean field analysis of neural networks
Original
Justin Sirignano and Konstantinos Spiliopoulos · 2018
Later among the works it cites.
Spurious valleys in two-layer neural network optimization landscapes
Original
Luca Venturi, Afonso Bandeira, and Joan Bruna · 2018
Later among the works it cites.
Learning relu networks on linearly separable data: Algorithm, optimality, and generalization
Original
Gang Wang, Georgios B Giannakis, and Jie Chen · 2018
Later among the works it cites.
Small nonlinearities in activation functions create bad local minima in neural networks
Original
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie · 2018
Later among the works it cites.
How much restricted isometry is needed in nonconvex matrix recovery?
Richard Zhang, Cedric Josz, Somayeh Sojoudi, and Javad Lavaei · 2018
Later among the works it cites.
Stochastic gradient descent optimizes over-parameterized deep ReLU networks
Original
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu · 2018
Later among the works it cites.
Uniform convergence may be unable to explain generalization in deep learning
Vaishnavh Nagarajan and J Zico Kolter · 2019
Closest in time.
On connected sublevel sets in deep learning
Original
Quynh Nguyen · 2019
Closest in time.
Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
Original
Samet Oymak and Mahdi Soltanolkotabi · 2019
Closest in time.
Theoretical insights into the optimization landscape of over-parameterized shallow neural networks
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee · 2019
Closest in time.
Optimization for deep learning: theory and algorithms
Original
Ruoyu Sun · 2019
Closest in time.
Depth creates no more spurious local minima
Original
Li Zhang · 2019
Closest in time.
An improved analysis of training over-parameterized deep neural networks
Original
Difan Zou and Quanquan Gu · 2019
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, 2020
Constantin Christof · 2020
Closest in time.
Piecewise linear activations substantially shape the loss surfaces of neural networks
Original
Fengxiang He, Bohan Wang, and Dacheng Tao · 2020
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…