In this paper, we study stochastic non-convex optimization with non-convex
random functions. Recent studies on non-convex optimization revolve around
establishing second-order convergence, i.e., converging to a nearly
second-order optimal stationary points. However, existing results on stochastic
non-convex optimization are limited, especially with a high probability
second-order convergence. We propose a novel updating step (named NCG-S) by
leveraging a stochastic gradient and a noisy negative curvature of a stochastic
Hessian, where the stochastic gradient and Hessian are based on a proper
mini-batch of random functions. Building on this step, we develop two
algorithms and establish their high probability second-order convergence. To
the best of our knowledge, the proposed stochastic algorithms are the first
with a second-order convergence in {\it high probability} and a time complexity
that is {\it almost linear} in the problem's dimensionality.

本文研究带有非凸随机函数的随机非凸优化，并提出一种称为 NCG-S 的新型更新步骤，可以在高概率下实现二阶收敛，所提出的随机算法是首个具有高概率二阶收敛和几乎是线性时间复杂度的方法。