Riemannian Adaptive Regularized Newton Methods with Hölder Continuous Hessians

Abstract

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