  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 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.
