# Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms

arXiv: https://arxiv.org/abs/2405.03073 · HTML: https://mlsanity.com/paper/2405.03073/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 52 references that are in the map.
- First posted on arXiv 5 May 2024.

## Builds on (most cited first, 14 of 14)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Global rates of convergence for nonconvex optimization on manifolds](https://mlsanity.com/paper/1605.08101/) (2016)
- [Fast and accurate optimization on the orthogonal manifold without retraction](https://mlsanity.com/paper/2102.07432/) (2021)
- [Decentralized Riemannian Gradient Descent on the Stiefel Manifold](https://mlsanity.com/paper/2102.07091/) (2021)
- [When Are Nonconvex Problems Not Scary?](https://mlsanity.com/paper/1510.06096/) (2015)
- [Bayesian Optimization Meets Riemannian Manifolds in Robot Learning](https://mlsanity.com/paper/1910.04998/) (2019)
- [Block Coordinate Descent on Smooth Manifolds: Convergence Theory and Twenty-One Examples](https://mlsanity.com/paper/2305.14744/) (2023)
- [A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data](https://mlsanity.com/paper/1511.02746/) (2015)
- [Block majorization-minimization with diminishing radius for constrained nonsmooth nonconvex optimization](https://mlsanity.com/paper/2012.03503/) (2020)
- [Coordinate Descent Without Coordinates: Tangent Subspace Descent on Riemannian Manifolds](https://mlsanity.com/paper/1912.10627/) (2019)
- [Convergence and complexity of block majorization-minimization for constrained block-Riemannian optimization](https://mlsanity.com/paper/2312.10330/) (2023)
- [Nonnegative Low Rank Matrix Approximation for Nonnegative Matrices](https://mlsanity.com/paper/1912.06836/) (2019)
- [Complexity of Block Coordinate Descent with Proximal Regularization and Applications to Wasserstein CP-dictionary Learning](https://mlsanity.com/paper/2306.02420/) (2023)
- [Tangent Space Based Alternating Projections for Nonnegative Low Rank Matrix Approximation](https://mlsanity.com/paper/2009.03998/) (2020)

## Abstract (arXiv)

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.