2023/09/08 by Chenyu Zhang, Zhang, Chenyu, Rujun Jiang +1
Computer Science · Engineering · Mathematics · #65K05 #68Q25 #90C26 #90C30 #90C60 #Advanced Optimization Algorithms Research #Applied mathematics #Artificial intelligence #Combinatorics #Computer science #FOS: Mathematics #Function (biology) #Hessian matrix #Mathematical analysis #Mathematical optimization #Mathematics #Optimization and Control (math.OC) #Regularization (linguistics) #Riemannian manifold #Smoothness #Solver #Sparse and Compressive Sensing Techniques #Stationary point #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2309.04052
openalex publication_date 2023/09/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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ölder continuous Hessian, when equipped with a retraction featuring a ν-Hölder continuous differential and a θ-inexact subproblem solver, both RTR and RAR with 2+α regularization (where α=min\μ,ν,θ\) locate an (ε,εα/(1+α))-approximate second-order stationary point within at most O(ε-(2+α)/(1+α)) iterations and at most O(ε-(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 O(ε-7/4) when α=1.