Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911871361089536 |
|---|---|
| author | Li, Yuchen Balzano, Laura Needell, Deanna Lyu, Hanbaek |
| author_facet | Li, Yuchen Balzano, Laura Needell, Deanna Lyu, Hanbaek |
| contents | We analyze inexact Riemannian gradient descent (RGD) where Riemannian gradients and retractions are inexactly (and cheaply) computed. Our focus is on understanding when inexact RGD converges and what is the complexity in the general nonconvex and constrained setting. We answer these questions in a general framework of tangential Block Majorization-Minimization (tBMM). We establish that tBMM converges to an $ε$-stationary point within $O(ε^{-2})$ iterations. Under a mild assumption, the results still hold when the subproblem is solved inexactly in each iteration provided the total optimality gap is bounded. Our general analysis applies to a wide range of classical algorithms with Riemannian constraints including inexact RGD and proximal gradient method on Stiefel manifolds. We numerically validate that tBMM shows improved performance over existing methods when applied to various problems, including nonnegative tensor decomposition with Riemannian constraints, regularized nonnegative matrix factorization, and low-rank matrix recovery problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_03073 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms Li, Yuchen Balzano, Laura Needell, Deanna Lyu, Hanbaek Optimization and Control Machine Learning We analyze inexact Riemannian gradient descent (RGD) where Riemannian gradients and retractions are inexactly (and cheaply) computed. Our focus is on understanding when inexact RGD converges and what is the complexity in the general nonconvex and constrained setting. We answer these questions in a general framework of tangential Block Majorization-Minimization (tBMM). We establish that tBMM converges to an $ε$-stationary point within $O(ε^{-2})$ iterations. Under a mild assumption, the results still hold when the subproblem is solved inexactly in each iteration provided the total optimality gap is bounded. Our general analysis applies to a wide range of classical algorithms with Riemannian constraints including inexact RGD and proximal gradient method on Stiefel manifolds. We numerically validate that tBMM shows improved performance over existing methods when applied to various problems, including nonnegative tensor decomposition with Riemannian constraints, regularized nonnegative matrix factorization, and low-rank matrix recovery problems. |
| title | Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2405.03073 |