In this paper we consider a nonconvex unconstrained optimization problem
minimizing a twice differentiable objective function with H\"older continuous
Hessian. Specifically, we first propose a Newton-conjugate gradient (Newton-CG)
method for finding an approximate first-order stationary point (FOSP) of this
problem, assuming the associated the H\"older parameters are explicitly known.
Then we develop a parameter-free Newton-CG method without requiring any prior
knowledge of these parameters. To the best of our knowledge, this method is the
first parameter-free second-order method achieving the best-known iteration and
operation complexity for finding an approximate FOSP of this problem.
Furthermore, we propose a Newton-CG method for finding an approximate
second-order stationary point (SOSP) of the considered problem with high
probability and establish its iteration and operation complexity. Finally, we
present preliminary numerical results to demonstrate the superior practical
performance of our parameter-free Newton-CG method over a well-known
regularized Newton method.

本文提出了一种无需参数先验知识的 Newton-CG 方法，用于在非凸无约束最优化问题中找到近似的一阶稳定点和二阶稳定点，并证明了其迭代和操作复杂度。与一种著名的正则化 Newton 方法相比，我们的方法实现了更好的实际性能。

具有 Hölder 连续 Hessian 的非凸无约束优化的 Newton-CG 方法

Newton-CG methods for nonconvex unconstrained optimization with Hölder  continuous Hessian

Variance reduction techniques like SVRG provide simple and fast algorithms
for optimizing a convex finite-sum objective. For nonconvex objectives, these
techniques can also find a first-order stationary point (with small gradient).
However, in nonconvex optimization it is often crucial to find a second-order
stationary point (with small gradient and almost PSD hessian). In this paper,
we show that Stabilized SVRG (a simple variant of SVRG) can find an
$\epsilon$-second-order stationary point using only
$\widetilde{O}(n^{2/3}/\epsilon^2+n/\epsilon^{1.5})$ stochastic gradients. To
our best knowledge, this is the first second-order guarantee for a simple
variant of SVRG. The running time almost matches the known guarantees for
finding $\epsilon$-first-order stationary points.

该研究使用改进的 SVRG 算法创新性地找到一个非凸函数的二阶稳定点，并提出了使用稳定性 SVRG 算法的方法。

稳定 SVRG: 非凸优化的简单方差缩减

Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization

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 提供了新的见解，并可潜在地推广到广泛的随机优化算法类。

非凸随机梯度下降逃离鞍点的尖锐分析

Sharp Analysis for Nonconvex SGD Escaping from Saddle Points

This paper shows that a perturbed form of gradient descent converges to a
second-order stationary point in a number iterations which depends only
poly-logarithmically on dimension (i.e., it is almost "dimension-free"). The
convergence rate of this procedure matches the well-known convergence rate of
gradient descent to first-order stationary points, up to log factors. When all
saddle points are non-degenerate, all second-order stationary points are local
minima, and our result thus shows that perturbed gradient descent can escape
saddle points almost for free. Our results can be directly applied to many
machine learning applications, including deep learning. As a particular
concrete example of such an application, we show that our results can be used
directly to establish sharp global convergence rates for matrix factorization.
Our results rely on a novel characterization of the geometry around saddle
points, which may be of independent interest to the non-convex optimization
community.

本文研究表明惯性梯度下降法可以在较短的迭代次数内收敛于二阶稳定点，收敛速率与梯度下降到一阶稳定点的收敛速率匹配，当所有鞍点都是非退化的时，所有的二阶稳定点都是局部最小值，该结果表明惯性梯度下降法几乎可以在无成本的情况下脱离鞍点，并可直接应用于许多机器学习应用中，包括深度学习。