Improved second-order evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

Abstract

The unconstrained minimization of a sufficiently smooth objective function $f(x)$ is considered, for which derivatives up to order $p$, $p\ge 2$, are assumed to be available. An adaptive regularization algorithm is proposed that uses Taylor models of the objective of order $p$ and that is guaranteed to find a first- and second-order critical point in at most $O\left(\max \left({\epsilon }_1^{-\frac{p+1}{p}},{\epsilon }_2^{-\frac{p+1}{p-1}}\right)\right)$ function and derivatives evaluations, where ${\epsilon }_1$ and ${\epsilon }_2>0$ are prescribed first- and second-order optimality tolerances. Our approach extends the method in Birgin et al. (2016) to finding second-order critical points, and establishes the novel complexity bound for second-order criticality under identical problem assumptions as for first-order, namely, that the $p$-th derivative tensor is Lipschitz continuous and that $f(x)$ is bounded from below. The evaluation-complexity bound for second-order criticality improves on all such known existing results.

Cited by in corpus (5)

• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations
• A modified adaptive cubic regularization method for large-scale unconstrained optimization problem
• Cutting plane methods can be extended into nonconvex optimization
• Convergence analysis of stochastic higher-order majorization-minimization algorithms
• A Unified Adaptive Tensor Approximation Scheme to Accelerate Composite Convex Optimization