Riemannian Adaptive Regularized Newton Methods with Hölder Continuous Hessians
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918017794834432 |
|---|---|
| author | Zhang, Chenyu Jiang, Rujun |
| author_facet | Zhang, Chenyu Jiang, Rujun |
| contents | 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 $\tilde{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 $\tilde{O}(ε^{-7/4})$ when $α=1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_04052 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Riemannian Adaptive Regularized Newton Methods with Hölder Continuous Hessians Zhang, Chenyu Jiang, Rujun Optimization and Control 90C30, 65K05, 90C26, 90C60, 68Q25 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 $\tilde{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 $\tilde{O}(ε^{-7/4})$ when $α=1$. |
| title | Riemannian Adaptive Regularized Newton Methods with Hölder Continuous Hessians |
| topic | Optimization and Control 90C30, 65K05, 90C26, 90C60, 68Q25 |
| url | https://arxiv.org/abs/2309.04052 |