Riemannian Adaptive Regularized Newton Methods with H"older Continuous Hessians

This paper presents strong worst-case iteration and operation complexity guarantees for Riemannian adaptive regularized Newton methods, a unified framework encompassing both Riemannian adaptive regularization (RAR) methods and Riemannian trust region (RTR) methods. We comprehensively characterize the sources of approximation in second-order manifold optimization methods: the objective function's smoothness, retraction's smoothness, and subproblem solver's inexactness. Specifically, for a function with a μ-H"older continuous Hessian, when equipped with a retraction featuring a nu-H"older continuous differential and a θ-inexact subproblem solver, both RTR and RAR with 2+α regularization (where α=minμ,nu,θ) locate an (ε,εα/(1+α))-approximate second-order stationary point within at most O(ε-(2+α)/(1+α)) iterations and at most tildeO(ε-(4+3α)/(2(1+α))) Hessian-vector products. These complexity results are novel and sharp, and reduce to an iteration complexity of O(ε-3/2) and an operation complexity of tildeO(ε-7/4) when α=1.