Riemannian Adaptive Regularized Newton Methods with Hölder Continuous Hessians

Chenyu Zhang () and Rujun Jiang ()
Additional contact information
Chenyu Zhang: MIT
Rujun Jiang: Fudan University

Computational Optimization and Applications, 2025, vol. 92, issue 1, No 2, 29-79

Abstract: 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 $$\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 .

Keywords: Riemannian optimization; Adaptive regularization; Trust region; Hölder continuity; Worst-case complexity (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-025-00692-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:92:y:2025:i:1:d:10.1007_s10589-025-00692-x

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-025-00692-x

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().