On Global Rates for Regularization Methods based on Secant Derivative Approximations

Abstract

An inexact and globally convergent framework for high-order adaptive regularization methods is presented, in which approximations may be used for the $p$th-order tensor, based on lower-order derivatives. Between each recalculation of the $p$th-order derivative approximation, a high-order secant equation can be used to update the $p$th-order tensor as proposed in (Karl Welzel and Raphael A Hauser, Approximating higher-order derivative tensors using secant updates, SIAM J.Optim, 34(1), 2024) or the approximation can be kept constant in a lazy manner. When refreshing the $p$th-order tensor approximation after $m$ steps, an exact evaluation of the tensor or a finite difference approximation can be used with an explicit discretization stepsize. For all the newly adaptive regularization variants, we prove an $\mathcal{O}\left(\max [\hat{I}{\mu }_1^{-(p+1)/p},\hat{I}{\mu }_2^{-(p+1)/(p-1)}]\right)$ bound on the number of iterations needed to reach an $(\hat{I}{\mu }_1,\hat{I}{\mu }_2)$ second-order stationary points. Discussions on the number of oracle calls for each introduced variant are also provided. When $p=2$, we obtain a second-order method that uses quasi-Newton approximations with an $\mathcal{O}\left(\max [\hat{I}{\mu }_1^{-3/2},\hat{I}{\mu }_2^{-3}]\right)$ iteration bound to achieve approximate second-order stationarity. Numerical illustrations for the case $p=3$ are provided in both the deterministic and noisy settings showcasing the merits of secant updates for approximating third-order information, as well as the robustness of our proposed method even in noisy cases.