2015

Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition

Ge, Rong, Huang, Furong, Jin, Chi et al.

Understand

We analyze stochastic gradient descent for optimizing non-convex functions.

In many cases for non-convex functions the goal is to find a reasonable local minimum, and the main concern is that gradient updates are trapped in saddle points.
In this paper we identify strict saddle property for non-convex problem that allows for efficient optimization.
Using this property we show that stochastic gradient descent converges to a local minimum in a polynomial number of iterations.

Built on

Pseudo-convex functions
Mangasarian, O. L. (1965) · 1965
Earlier work this paper cites.
Weighted sums of certain dependent random variables
Azuma, K. (1967) · 1967
Earlier work this paper cites.
Foundations of the PARAFAC procedure: Models and conditions for an “explanatory” multi-modal factor analysis
Harshman, R. A. (1970) · 1970
Earlier work this paper cites.
How easy is local search?
Johnson, D. S., Papadimitriou, C. H., and Yannakakis, M. (1988) · 1988
Earlier work this paper cites.
Learning representations by back-propagating errors
Rumelhart, D. E., Hinton, G. E., and Williams, R. J. (1988) · 1988
Earlier work this paper cites.
Source separation using higher order moments
Cardoso, J.-F. (1989) · 1989
Earlier work this paper cites.
On-line learning in soft committee machines
Saad, D. and Solla, S. A. (1995) · 1995
Earlier work this paper cites.
Sparse coding with an overcomplete basis set: A strategy employed by V1?
Olshausen, B. A. and Field, D. J. (1997) · 1997
Earlier work this paper cites.
Natural gradient descent for on-line learning
Rattray, M., Saad, D., and Amari, S.-i. (1998) · 1998
Earlier work this paper cites.
Invexity and the kuhn–tucker theorem
Hanson, M. A. (1999) · 1999
Earlier work this paper cites.
Fast ICA for noisy data using gaussian moments
Hyvarinen, A. (1999) · 1999
Earlier work this paper cites.

Similar

Numerical optimization
Wright, S. J. and Nocedal, J. (1999) · 1999
Cited alongside, same era.
Convergence and efficiency of subgradient methods for quasiconvex minimization
Kiwiel, K. C. (2001) · 2001
Cited alongside, same era.
Orthogonal tensor decompositions
Kolda, T. G. (2001) · 2001
Cited alongside, same era.
Tensor decompositions
Comon, P. (2002) · 2002
Cited alongside, same era.
On-line learning theory of soft committee machines with correlated hidden units–steepest gradient descent and natural gradient descent–
Inoue, M., Park, H., and Okada, M. (2003) · 2003
Cited alongside, same era.
Independent component analysis
Hyvärinen, A., Karhunen, J., and Oja, E. (2004) · 2004
Cited alongside, same era.
Learning deep architectures for AI
Bengio, Y. (2009) · 2009
Cited alongside, same era.
Tensor decompositions, alternating least squares and other tales
Comon, P., Luciani, X., and De Almeida, A. L. (2009) · 2009
Cited alongside, same era.
Stochastic convex optimization
Shalev-Shwartz, S., Shamir, O., Sridharan, K., and Srebro, N. (2009) · 2009
Cited alongside, same era.
Fast global convergence rates of gradient methods for high-dimensional statistical recovery
Agarwal, A., Negahban, S., and Wainwright, M. J. (2010) · 2010
Cited alongside, same era.

Then

Provable ICA with unknown gaussian noise, with implications for gaussian mixtures and autoencoders
Arora, S., Ge, R., Moitra, A., and Sachdeva, S. (2012) · 2012
Later among the works it cites.
Making gradient descent optimal for strongly convex stochastic optimization
Rakhlin, A., Shamir, O., and Sridharan, K. (2012) · 2012
Later among the works it cites.
Learning linear transformations
Frieze, A., Jerrum, M., and Kannan, R. (1996) · 2013
Later among the works it cites.
Fast detection of overlapping communities via online tensor methods
Original
Huang, F., Niranjan, U., Hakeem, M. U., and Anandkumar, A. (2013) · 2013
Later among the works it cites.
Low-rank matrix completion using alternating minimization
Jain, P., Netrapalli, P., and Sanghavi, S. (2013) · 2013
Later among the works it cites.
Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
Original
Saxe, A. M., McClelland, J. L., and Ganguli, S. (2013) · 2013
Later among the works it cites.
Contrastive learning using spectral methods
Zou, J. Y., Hsu, D., Parkes, D. C., and Adams, R. P. (2013) · 2013
Later among the works it cites.
Tensor decompositions for learning latent variable models
Anandkumar, A., Ge, R., Hsu, D., Kakade, S. M., and Telgarsky, M. (2014) · 2014
Later among the works it cites.
The loss surface of multilayer networks
Original
Choromanska, A., Henaff, M., Mathieu, M., Arous, G. B., and LeCun, Y. (2014) · 2014
Later among the works it cites.
Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
Dauphin, Y. N., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., and Bengio, Y. (2014) · 2014
Later among the works it cites.

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…