Riemannian Adaptive Regularized Newton Methods with Hölder 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 $$\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 $$ 2 + α regularization (where $$\alpha =\min \{\mu ,\nu ,\theta \}$$ α = min { μ , ν , θ } ) locate an $$(\epsilon ,\epsilon ^{\alpha /(1+\alpha )})$$ ( ϵ , ϵ α / ( 1 + α ) ) -approximate second-order stationary point within at most $$O(\epsilon ^{-(2+\alpha )/(1+\alpha )})$$ O ( ϵ - ( 2 + α ) / ( 1 + α ) ) iterations and at most $${\widetilde{O}}(\epsilon ^{- (4+3\alpha ) /(2(1+\alpha ))})$$ O ~ ( ϵ - ( 4 + 3 α ) / ( 2 ( 1 + α ) ) ) Hessian-vector products with high probability. These complexity results are novel and sharp, and reduce to an iteration complexity of $$O(\epsilon ^{-3 /2})$$ O ( ϵ - 3 / 2 ) and an operation complexity of $${\widetilde{O}}(\epsilon ^{-7 /4})$$ O ~ ( ϵ - 7 / 4 ) when $$\alpha =1$$ α = 1 .