Research map / Optimization / Nonconvex and smooth optimization
Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes tangential Block Majorization-Minimization (tBMM), a general framework for multi-block nonconvex, nonsmooth Riemannian optimization with constraints and inexact subproblem solves, proving O(epsilon^-2) iteration complexity to epsilon-stationarity.
Problem
Convergence and iteration complexity of first-order Riemannian optimization (inexact Riemannian gradient descent, proximal gradient on Stiefel manifolds, block methods) under constraints, nonsmooth terms, and inexact subproblem solutions.
Approach
Lift each block's majorizer to the tangent space via retraction (pullback), minimize the tangential surrogate over a lifted constraint set, and retract back; summable optimality gaps of inexact subproblem solves preserve O(eps^-2) complexity.
Key results
- tBMM converges to an epsilon-stationary point within O(epsilon^-2) iterations under summable optimality gaps for inexact subproblem solves.
- Inexact RGD and nonsmooth proximal gradient on Stiefel manifolds inherit the O(epsilon^-2) complexity as special cases.
- Numerically, tBMM achieves lower relative error than block PGD on nonnegative tensor decomposition and NMF, and outperforms NIHT on low-rank matrix recovery.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use tBMM with prox-linear surrogates instead of block PGD | Riemannian tensor decomposition · Nonnegative tensor decomposition with Riemannian constraints | relative reconstruction error | Helped |
| Use tBMM with prox-linear surrogates instead of block PGD | Regularized nonnegative matrix factorization · Regularized nonnegative matrix factorization with Riemannian constraints | relative error | Helped |
| Use tBMM instead of NIHT | Low-rank matrix recovery · Low-rank matrix recovery at \rho=0.5 and 0.75 | relative reconstruction error | Helped |
| Use tBMM instead of NIHT across matrix dimensions | Low-rank matrix recovery · Different matrix dimensions | robustness | Helped |
| Allow inexact subproblem solutions when the optimality gaps are summable | tBMM · General nonconvex constrained Riemannian optimization | iteration complexity: O(\varepsilon^{-2}) | Helped |
| Use summable gradient noise, with \Delta_n = c/(n+1)^2 | Inexact tBMM and inexact RGD · Low-rank matrix recovery | convergence speed | Helped |
Limitations
- Requires summable optimality gaps for inexact subproblems, a mild but nontrivial assumption.
- Assumes retraction bound and convexity of lifted constraint set, which may not hold generally.
Experimental setup
Datasets: synthetic tensors synthetic matrices for low-rank matrix recovery
Benchmarks: nonnegative tensor decomposition with l1 regularization regularized nonnegative matrix factorization low-rank matrix recovery
Metrics: relative reconstruction error
Baselines: block projected gradient descent NIHT
Builds on: block majorization-minimization Riemannian gradient descent restricted Lipschitz-type gradients
Closest papers by meaning
- Convergence and Trade-Offs in Riemannian Gradient Descent and Riemannian Proximal Point (ICML 2024 · similarity 0.91)
- Acceleration via silver step-size on Riemannian manifolds with applications to Wasserstein space (NeurIPS 2025 · similarity 0.88)
- SERENA: A Unified Stochastic Recursive Variance Reduced Gradient Framework for Riemannian Non-Convex Optimization (ICML 2025 · similarity 0.88)
- Adaptive Riemannian ADMM for Nonsmooth Optimization: Optimal Complexity without Smoothing (NeurIPS 2025 · similarity 0.88)
- Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds (NeurIPS 2025 · similarity 0.87)
- Preconditioned Riemannian Gradient Descent Algorithm for Low-Multilinear-Rank Tensor Completion (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.