Two classes of methods have been proposed for escaping from saddle points
with one using the second-order information carried by the Hessian and the
other adding the noise into the first-order information. The existing analysis
for algorithms using noise in the first-order information is quite involved and
hides the essence of added noise, which hinder further improvements of these
algorithms. In this paper, we present a novel perspective of noise-adding
technique, i.e., adding the noise into the first-order information can help
extract the negative curvature from the Hessian matrix, and provide a formal
reasoning of this perspective by analyzing a simple first-order procedure. More
importantly, the proposed procedure enables one to design purely first-order
stochastic algorithms for escaping from non-degenerate saddle points with a
much better time complexity (almost linear time in terms of the problem's
dimensionality). In particular, we develop a {\bf first-order stochastic
algorithm} based on our new technique and an existing algorithm that only
converges to a first-order stationary point to enjoy a time complexity of
{$\widetilde O(d/\epsilon^{3.5})$ for finding a nearly second-order stationary
point $\bf{x}$ such that $\|\nabla F(bf{x})\|\leq \epsilon$ and $\nabla^2
F(bf{x})\geq -\sqrt{\epsilon}I$ (in high probability), where $F(\cdot)$ denotes
the objective function and $d$ is the dimensionality of the problem. To the
best of our knowledge, this is the best theoretical result of first-order
algorithms for stochastic non-convex optimization, which is even competitive
with if not better than existing stochastic algorithms hinging on the
second-order information.

本文提供了一种新的噪声加入技术的视角，即将噪声添加到一阶信息中可以帮助从 Hessian 矩阵中提取负曲率，并通过分析一个简单的一阶过程提供了此视角的正式推理，然后提出了一种基于此技术和现有算法的一阶随机算法，实现了以几乎线性的时间复杂度（与问题的维度有关）找到接近于二阶稳定点的解的目标，从而在随机非凸优化上取得了最佳理论结果，甚至与凭借二阶信息的现有随机算法相媲美。