2017

Exponentially vanishing sub-optimal local minima in multilayer neural networks

Soudry, Daniel, Hoffer, Elad

Understand

Background: Statistical mechanics results (Dauphin et al.

(2014); Choromanska et al.
(2015)) suggest that local minima with high error are exponentially rare in high dimensions.
However, to prove low error guarantees for Multilayer Neural Networks (MNNs), previous works so far required either a heavily modified MNN model or training method, strong assumptions on the labels (e.g., "near" linear separability), or an unrealistic hidden layer with $\Omega\left(N\right)$ units.

Built on

Geometry of Neural Network Loss Surfaces via Random Matrix Theory
Jeffrey Pennington and Yasaman Bahri · 1938
Earlier work this paper cites.
The One Sided Problem for Gaussian Noise
D Slepian · 1962
Earlier work this paper cites.
Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition
T M Cover · 1965
Earlier work this paper cites.
Learning machines
Nils J. Nilsson · 1965
Earlier work this paper cites.
Lower bounds on the maximum cross correlation of signals
L. Welch · 1974
Earlier work this paper cites.
On the capabilities of multilayer perceptrons
Eric B. Baum · 1988
Earlier work this paper cites.
Linear Learning: Landscapes and Algorithms
Pierre Baldi · 1989
Earlier work this paper cites.
Approximation by superpositions of a sigmoidal function
G Cybenko · 1989
Earlier work this paper cites.
Nonconvergence to unstable points in urn models and stochastic approximations
R Pemantle · 1990
Earlier work this paper cites.
Approximation capabilities of multilayer feedforward networks
K Hornik · 1991
Earlier work this paper cites.
On the problem of local minima in backpropagation
Marco Gori and Alberto Tesi · 1992
Earlier work this paper cites.
Can Backpropagation Error Surface Not Have Local Minima
Xiao Hu Yu · 1992
Earlier work this paper cites.
Online learning and stochastic approximations
L Bottou · 1998
Earlier work this paper cites.
Local minima and plateaus in hierarchical structures of multilayer perceptrons
K. Fukumizu and S. Amari · 2000
Earlier work this paper cites.
Training a single sigmoidal neuron is hard
Jirí Síma · 2002
Earlier work this paper cites.
Extreme learning machine: Theory and applications
Guang-Bin Huang, Qin-Yu Zhu, and Chee-Kheong Siew · 2005
Earlier work this paper cites.
Saddlepoint Approximations with Applications
Ronald W. Butler · 2007
Earlier work this paper cites.
Identifiability of parameters in latent structure models with many observed variables
Elizabeth S. Allman, Catherine Matias, and John A. Rhodes · 2009
Earlier work this paper cites.
Sparse and redundant representations: from theory to applications in signal and image processing
Michael Elad · 2010
Earlier work this paper cites.
Non-asymptotic Theory of Random Matrices: Extreme Singular Values
Mark Rudelson and Roman Vershynin · 2010
Earlier work this paper cites.

Similar

Rectifier Nonlinearities Improve Neural Network Acoustic Models
Andrew L. Maas, Awni Y. Hannun, and Andrew Y. Ng · 2013
Cited alongside, same era.
Learning Polynomials with Neural Networks
A Andoni, R Panigrahy, G Valiant, and L Zhang · 2014
Cited alongside, same era.
Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
YN Dauphin, Razvan Pascanu, and Caglar Gulcehre · 2014
Cited alongside, same era.
One weird trick for parallelizing convolutional neural networks
Original
Alex Krizhevsky · 2014
Cited alongside, same era.
On the Computational Efficiency of Training Neural Networks
Roi Livni, S Shalev-Shwartz, and Ohad Shamir · 2014
Cited alongside, same era.
Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
A M Saxe, J L. McClelland, and S Ganguli · 2014
Cited alongside, same era.
Influences of preconditioning on the mutual coherence and the restricted isometry property of Gaussian/Bernoulli measurement matrices
Yingtong Chen and Jigen Peng · 2015
Cited alongside, same era.
The Loss Surfaces of Multilayer Networks
Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Y LeCun · 2015
Cited alongside, same era.
Qualitatively characterizing neural network optimization problems
Ian J. Goodfellow, Oriol Vinyals, and Andrew M. Saxe · 2015
Cited alongside, same era.
Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun · 2015
Cited alongside, same era.
Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
Original
M Janzamin, H Sedghi, and A Anandkumar · 2015
Cited alongside, same era.
Adam: a Method for Stochastic Optimization
Diederik P Kingma and Jimmy Lei Ba · 2015
Cited alongside, same era.

Then

On the Quality of the Initial Basin in Overspecified Neural Networks
Itay Safran and Ohad Shamir · 2016
Later among the works it cites.
Distribution Specific Hardness of Learning Neural Networks
Original
Ohad Shamir · 2016
Later among the works it cites.
Designing and Training Feedforward Neural Networks: A Smooth Optimisation Perspective
Hao Shen · 2016
Later among the works it cites.
Robust Large Margin Deep Neural Networks, 2016
Jure Sokolic, Raja Giryes, Guillermo Sapiro, and Miguel R. D. Rodrigues · 2016
Later among the works it cites.
No bad local minima: Data independent training error guarantees for multilayer neural networks
Original
D. Soudry and Y Carmon · 2016
Later among the works it cites.
Local minima in training of deep networks
Original
Grzegorz Swirszcz, Wojciech Marian Czarnecki, and Razvan Pascanu · 2016
Later among the works it cites.
Diversity Leads to Generalization in Neural Networks
Bo Xie, Yingyu Liang, and Le Song · 2016
Later among the works it cites.
Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
Alon Brutzkus and Amir Globerson · 2017
Closest in time.
When is a Convolutional Filter Easy To Learn?
Simon S. Du, Jason D. Lee, and Yuandong Tian · 2017
Closest in time.
Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
Gintare Karolina Dziugaite and Daniel M. Roy · 2017
Closest in time.
Identity Matters in Deep Learning
Moritz Hardt and Tengyu Ma · 2017
Closest in time.
Convergence Analysis of Two-layer Neural Networks with ReLU Activation
Yuanzhi Li and Yang Yuan · 2017
Closest in time.
Depth Creates No Bad Local Minima
Haihao Lu and Kenji Kawaguchi · 2017
Closest in time.
The loss surface of deep and wide neural networks
Quynh Nguyen and Matthias Hein · 2017
Closest in time.
Weight Sharing is Crucial to Succesful Optimization
Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah · 2017
Closest in time.
Theoretical insights into the optimization landscape of over-parameterized shallow neural networks
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D. Lee · 2017
Closest in time.
Symmetry-Breaking Convergence Analysis of Certain Two-layered Neural Networks with ReLU nonlinearity
Yuandong Tian · 2017
Closest in time.
Recovery Guarantees for One-hidden-layer Neural Networks
Kai Zhong, Ut-Austin Zhao Song, Prateek Jain, Peter L. Bartlett, and Inderjit S. Dhillon · 2017
Closest in time.
The Landscape of Deep Learning Algorithms
Pan Zhou and Jiashi Feng · 2017
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…