2016

The Power of Normalization: Faster Evasion of Saddle Points

Levy, Kfir Y.

Understand

A commonly used heuristic in non-convex optimization is Normalized Gradient Descent (NGD) - a variant of gradient descent in which only the direction of the gradient is taken into account and its magnitude ignored.

We analyze this heuristic and show that with carefully chosen parameters and noise injection, this method can provably evade saddle points.
We establish the convergence of NGD to a local minimum, and demonstrate rates which improve upon the fastest known first order algorithm due to Ge e al.
(2015).

Built on

Foundations of the parafac procedure: Models and conditions for an” explanatory” multimodal factor analysis
R. A. Harshman · 1970
Earlier work this paper cites.
Minimization methods for nonsmooth convex and quasiconvex functions
Y. E. Nesterov · 1984
Earlier work this paper cites.
Exact solution for on-line learning in multilayer neural networks
D. Saad and S. A. Solla · 1995
Earlier work this paper cites.
Policy gradient methods for reinforcement learning with function approximation
R. S. Sutton, D. A. McAllester, S. P. Singh, Y. Mansour, et al · 1999
Earlier work this paper cites.
Convergence and efficiency of subgradient methods for quasiconvex minimization
K. C. Kiwiel · 2001
Earlier work this paper cites.
Orthogonal tensor decompositions
T. G. Kolda · 2001
Earlier work this paper cites.
Learning to rank using gradient descent
C. Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton, and G. Hullender · 2005
Earlier work this paper cites.

Similar

Learning deep architectures for AI
Y. Bengio · 2009
Cited alongside, same era.
Guaranteed rank minimization via singular value projection
P. Jain, R. Meka, and I. S. Dhillon · 2010
Cited alongside, same era.
Stochastic first-and zeroth-order methods for nonconvex stochastic programming
S. Ghadimi and G. Lan · 2013
Cited alongside, same era.
Tensor decompositions for learning latent variable models
A. Anandkumar, R. Ge, D. Hsu, S. M. Kakade, and M. Telgarsky · 2014
Cited alongside, same era.
Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
Y. N. Dauphin, R. Pascanu, C. Gulcehre, K. Cho, S. Ganguli, and Y. Bengio · 2014
Cited alongside, same era.
The loss surfaces of multilayer networks
A. Choromanska, M. Henaff, M. Mathieu, G. Ben Arous, and Y. LeCun · 2015
Cited alongside, same era.
Escaping from saddle points—online stochastic gradient for tensor decomposition
R. Ge, F. Huang, C. Jin, and Y. Yuan · 2015
Cited alongside, same era.

Then

Beyond convexity: Stochastic quasi-convex optimization
E. Hazan, K. Y. Levy, and S. Shalev-Shwartz · 2015
Later among the works it cites.
Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
A. M. Saxe, J. L. McClelland, and S. Ganguli · 2015
Later among the works it cites.
Complete dictionary recovery over the sphere
J. Sun, Q. Qu, and J. Wright · 2015
Later among the works it cites.
Finding Approximate Local Minima for Nonconvex Optimization in Linear Time
Original
N. Agarwal, Z. Allen-Zhu, B. Bullins, E. Hazan, and T. Ma · 2016
Closest in time.
Variance reduction for faster non-convex optimization
Z. Allen-Zhu and E. Hazan · 2016
Closest in time.
Matrix completion has no spurious local minimum
Original
R. Ge, J. D. Lee, and T. Ma · 2016
Closest in time.
A geometric analysis of phase retrieval
Original
J. Sun, Q. Qu, and J. Wright · 2016
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…