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

We analyze stochastic gradient descent for optimizing non-convex functions.\nIn many cases for non-convex functions the goal is to find a reasonable local\nminimum, and the main concern is that gradient updates are trapped in saddle\npoints. In this paper we identify strict saddle property for non-convex problem\nthat allows for efficient optimization. Using this property we show that\nstochastic gradient descent converges to a local minimum in a polynomial number\nof iterations. To the best of our knowledge this is the first work that gives\nglobal convergence guarantees for stochastic gradient descent on non-convex\nfunctions with exponentially many local minima and saddle points. Our analysis\ncan be…