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 \(\mu \) -Hölder continuous Hessian, when equipped with a retraction featuring a \(\nu \) -Hölder continuous differential and a \(\theta \) -inexact subproblem solver, both RTR and RAR with \(2\!+\!\alpha \) regularization (where \(\alpha =\min \{\mu ,\nu ,\theta \}\) ) locate an \((\epsilon ,\epsilon ^{\alpha /(1+\alpha )})\) -approximate second-order stationary point within at most \(O(\epsilon ^{-(2+\alpha )/(1+\alpha )})\) iterations and at most \({\widetilde{O}}(\epsilon ^{- (4+3\alpha ) /(2(1+\alpha ))})\) Hessian-vector products with high probability. These complexity results are novel and sharp, and reduce to an iteration complexity of \(O(\epsilon ^{-3 /2})\) and an operation complexity of \({\widetilde{O}}(\epsilon ^{-7 /4})\) when \(\alpha =1\) .
