On Global Rates for Regularization Methods based on Secant Derivative Approximations
For optimization researchers, this work provides a theoretical foundation for using secant approximations in high-order regularization, enabling practical methods with global convergence guarantees.
This paper introduces a globally convergent framework for high-order adaptive regularization methods that use approximations of the pth-order tensor based on lower-order derivatives. It proves an iteration bound of O(max[ε₁^{-(p+1)/p}, ε₂^{-(p+1)/(p-1)}]) for reaching second-order stationary points and demonstrates the merits of secant updates for third-order approximations in numerical experiments.
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[ ε_1^{-(p+1)/p}, \, {ε_2^{-(p+1)/(p-1)}} ] \right)$ bound on the number of iterations needed to reach an $(ε_1, \, ε_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[ε_1^{-3/2}, \, \, ε_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.