Escaping From Saddle Points – Online Stochastic Gradient for Tensor Decomposition
Rong Ge Microsoft Research New England, Furong Huang University of California Irvine, Department of Electrical Engineering and Computer Science, Chi Jin University of California Berkeley, Department of Electrical Engineering and Computer Science, Yang Yuan Cornell University, Computer Science Department,
Abstract
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.
中文速览
非凸优化中，随机梯度下降（stochastic gradient descent, SGD）最大的拦路虎不是局部极小值，而是鞍点——梯度为零却不是极小值的"平坦"位置，算法一旦陷入就难以脱身。这篇论文提出了一个叫做"严格鞍点"（strict saddle）的函数性质：每个鞍点的Hessian矩阵都至少有一个负特征值，意味着鞍点在某个方向上是"下坡"的；利用这一性质，作者证明了带噪声的SGD能靠随机扰动自然逃离鞍点，并在多项式步数内收敛到局部极小值，这是首个针对同时拥有指数多个局部极小值和鞍点的非凸函数给出全局收敛保证的理论结果。作者将该框架应用于正交张量分解（orthogonal tensor decomposition）问题，设计了一个满足严格鞍点性质的新目标函数，进而得到首个具有全局收敛保证的在线张量分解算法，对隐变量模型的可扩展学习具有重要意义。
原文 arXiv:1503.02101;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1503.02101v1