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

arXiv:2405.03073v1 Announce Type: cross
Abstract: 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 $\epsilon$-stationary point within $O(\epsilon^{-2})$ iterations. Under a mild assumption, the results still hold when the subproblem is …

abstract algorithms analyze arxiv complexity convergence focus general gradient math.oc optimization questions stat.ml type understanding