For solving large-scale non-convex problems, we propose inexact variants of
trust region and adaptive cubic regularization methods, which, to increase
efficiency, incorporate various approximations. In particular, in addition to
approximate sub-problem solves, both the Hessian and the gradient are suitably
approximated. Using rather mild conditions on such approximations, we show that
our proposed inexact methods achieve similar optimal worst-case iteration
complexities as the exact counterparts. Our proposed algorithms, and their
respective theoretical analysis, do not require knowledge of any unknowable
problem-related quantities, and hence are easily implementable in practice. In
the context of finite-sum problems, we then explore randomized sub-sampling
methods as ways to construct the gradient and Hessian approximations and
examine the empirical performance of our algorithms on some real datasets.

提出了非凸问题的近似解决方案；采用了三次正则化和信任域算法的不精确变体，并且可以应用于有限和问题，通过随机子采样法对梯度和 Hessian 进行适当精度逼近，实现了计算效率与最优迭代复杂度的权衡。

不精确非凸牛顿类型方法

Inexact Non-Convex Newton-Type Methods

We consider variants of trust-region and cubic regularization methods for
non-convex optimization, in which the Hessian matrix is approximated. Under
mild conditions on the inexact Hessian, and using approximate solution of the
corresponding sub-problems, we provide iteration complexity to achieve $
\epsilon $-approximate second-order optimality which have shown to be tight.
Our Hessian approximation conditions constitute a major relaxation over the
existing ones in the literature. Consequently, we are able to show that such
mild conditions allow for the construction of the approximate Hessian through
various random sampling methods. In this light, we consider the canonical
problem of finite-sum minimization, provide appropriate uniform and non-uniform
sub-sampling strategies to construct such Hessian approximations, and obtain
optimal iteration complexity for the corresponding sub-sampled trust-region and
cubic regularization methods.

本文研究了基于 Hessian 矩阵近似的非凸优化中信任域和立方正则化方法的变体。通过对不精确 Hessian 矩阵的渐进解和相应子问题的近似解，提供了迭代复杂度，以实现达到二阶最优条件的近似解，并且在现有文献中条件松弛。