In this paper, we give a sharp analysis for Stochastic Gradient Descent (SGD)
and prove that SGD is able to efficiently escape from saddle points and find an
$(\epsilon, O(\epsilon^{0.5}))$-approximate second-order stationary point in
$\tilde{O}(\epsilon^{-3.5})$ stochastic gradient computations for generic
nonconvex optimization problems, when the objective function satisfies
gradient-Lipschitz, Hessian-Lipschitz, and dispersive noise assumptions. This
result subverts the classical belief that SGD requires at least
$O(\epsilon^{-4})$ stochastic gradient computations for obtaining an
$(\epsilon,O(\epsilon^{0.5}))$-approximate second-order stationary point. Such
SGD rate matches, up to a polylogarithmic factor of problem-dependent
parameters, the rate of most accelerated nonconvex stochastic optimization
algorithms that adopt additional techniques, such as Nesterov's momentum
acceleration, negative curvature search, as well as quadratic and cubic
regularization tricks. Our novel analysis gives new insights into nonconvex SGD
and can be potentially generalized to a broad class of stochastic optimization
algorithms.

本文将通过对随机梯度下降进行深入分析，证明当目标函数满足梯度 Lipschitz、Hessian-Lipschitz 和发散噪声假设时，SGD 能够在 O（ε^ -3.5）次随机梯度计算中逃离鞍点并找到（ε，O（ε^ 0.5））- 近似二阶稳定点，从而推翻了 SGD 至少需要 O（ε^ - 4）的经典信念。此类 SGD 速率与大多数采用其他技术的加速非凸随机优化算法的速率相匹配，如 Nesterov 的动量加速，负曲率搜索，以及二次和三次正则化技巧。本文的新型分析为非凸 SGD 提供了新的见解，并可潜在地推广到广泛的随机优化算法类。