Efficient Adaptive Regularized Tensor Methods

High-order tensor methods employing local Taylor approximations have attracted considerable attention for convex and nonconvex optimisation. The pth-order adaptive regularisation (ARp) approach builds a local model comprising a pth-order Taylor expansion and a (p+1)th-order regularisation term, delivering optimal worst-case global and local convergence rates. However, for p≥2, subproblem minimisation can yield multiple local minima, and while a global minimiser is recommended for p=2, effectively identifying a suitable local minimum for p≥3 remains elusive.
This work extends interpolation-based updating strategies, originally proposed for p=2, to cases where p≥3, allowing the regularisation parameter to adapt in response to interpolation models. Additionally, it introduces a new prerejection mechanism to discard unfavourable subproblem minimisers before function evaluations, thus reducing computational costs for p≥3.
Numerical experiments, particularly on Chebyshev-Rosenbrock problems with p=3, indicate that the proper use of different minimisers can significantly improve practical performance, offering a promising direction for designing more efficient high-order methods.