Escaping From Saddle Points - Online Stochastic Gradient for Tensor Decomposition

By Rong Ge, Furong Huang, Chi Jin, Yang Yuan. 2015

1,144 citations recorded by the source corpus.

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. To the best of our knowledge this is the first work that gives global convergence guarantees for stochastic gradient descent on non-convex functions with exponentially many local minima and saddle points. Our analysis can be applied to orthogonal tensor decomposition, which is widely used in learning a rich class of latent variable models. We propose a new optimization formulation for the tensor decomposition problem that has strict saddle property. As a result we get the first online algorithm for orthogonal tensor decomposition with global convergence guarantee.

Subfields: Artificial Intelligence, Computational Mathematics, Computational Mechanics, Optimization & Training, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

  1. Yoshua Bengio
  2. Tengyu Ma
  3. Ruslan Salakhutdinov
  4. Michael I. Jordan
  5. Jason D. Lee
  6. Percy Liang
  7. Sergey Levine
  8. Quoc V. Le

In Computational Mathematics

  1. Jason D. Lee
  2. Yuanzhi Li
  3. Anima Anandkumar
  4. Kfir Yehuda Levy
  5. Rong Ge
  6. Sham M. Kakade
  7. Simon Shaolei Du
  8. Michael I. Jordan

In Computational Mechanics

  1. Zeyuan Allen-Zhu
  2. Peter Richtárik
  3. Jason D. Lee
  4. Michael I. Jordan
  5. Francis R. Bach
  6. Nati Srebro
  7. Jakub Konecný
  8. Tengyu Ma

In Optimization & Training

  1. Jason D. Lee
  2. Zeyuan Allen-Zhu
  3. Peter Richtárik
  4. Tengyu Ma
  5. Yuanzhi Li
  6. Ohad Shamir
  7. Jakub Konecný
  8. Francis R. Bach

In Mathematical Optimization

  1. Zeyuan Allen-Zhu
  2. Prateek Jain
  3. Jason D. Lee
  4. Peter Richtárik
  5. Michael I. Jordan
  6. Sham M. Kakade
  7. Francis R. Bach
  8. Yuanzhi Li

Citations in the corpus