Research map / Optimization / Nonconvex and smooth optimization
Riemannian coordinate descent algorithms on matrix manifolds
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 a general framework for coordinate descent (RCD and linearized RCDlin) on matrix manifolds (Stiefel, Grassmann, hyperbolic, symplectic, doubly stochastic, SPD/SPSD) using cheap Givens/hyperbolic-type coordinate updates with convergence analysis and experiments.
Problem
Riemannian optimization on matrix manifolds updates all variables each iteration and requires costly retractions; coordinate descent on manifolds is hard to design efficiently for general manifolds.
Approach
Choose tangent-space basis vectors (e.g., H_ij X, E_ij Omega X, e_i e_j^T) such that the retraction along each basis direction is cheap (Givens, hyperbolic rotation, coordinate Sinkhorn), and use a linearized variant (RCDlin) that reuses the anchored Euclidean gradient across several inner coordinate updates.
Key results
- On the PCA and Procrustes problems, RCD/RCDlin achieve better flop counts than baselines and are competitive in runtime, with RCDlin fastest on PCA due to low per-iteration cost.
- On the nearest matrix problem on the symplectic manifold (n=p=200), RCD with block updates shows clear advantage over RGD in flop counts and runtime.
- For Lorentz embeddings on WordNet mammals, RCDlin converges at a similar rate to RGD in runtime.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use RCDlin instead of RCD (ablation) | PCA on the Grassmann manifold · PCA | convergence rate | Helped |
| use cyclic rather than uniformly random basis selection (ablation) | RCD · PCA | distance to the optimal solution | Helped |
| use selection without replacement rather than uniformly random basis selection (ablation) | RCDlin · PCA | distance to the optimal solution | Helped |
| use cyclic rather than uniformly random basis selection (ablation) | RCD · Orthogonal Procrustes | optimality gap | Helped |
| use cyclic rather than uniformly random basis selection (ablation) | RCD · Orthogonal Procrustes | convergence rate | Helped |
| use block coordinate updates rather than coordinate updates (ablation) | RCD · Nearest matrix problem | flop counts | Helped |
| use block coordinate updates rather than coordinate updates (ablation) | RCD · Nearest matrix problem | runtime | Helped |
| use RCD rather than the baselines | Orthogonal deep network distillation · Orthogonal deep network distillation | flop counts | Helped |
| use RCD rather than the baselines | Orthogonal deep network distillation · Orthogonal deep network distillation | runtime | Helped |
| use RCDlin rather than RGD | SPSD optimization · Weighted least squares with sparse A | convergence rate | Helped |
| use RCDlin rather than RGD | SPD optimization · Weighted least squares with dense A | convergence rate | No clear effect |
| use time-cyclic rather than cyclic basis selection (ablation) | RCDlin · Learning Lorentz embeddings | runtime convergence rate | No clear effect |
Surprising findings
- Cyclic basis selection outperforms uniformly random selection for both TSD and RCD.
Limitations
- Convergence analysis holds only in a compact neighbourhood of a critical point under mild assumptions.
- Runtime is not uniformly better than baselines; RCD is only competitive in runtime without parallel implementation.
Experimental setup
Datasets: WordNet mammals subtree
Metrics: optimality gap flop counts runtime mean average precision mean rank
Baselines: RGD (QR, Cayley, exponential retractions) TSD PLAM PCAL PenCF ExPen Landing
Builds on: Riemannian gradient descent TSD (Stiefel coordinate subspace descent) Manopt
Closest papers by meaning
- Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method (ICML 2025 · similarity 0.89)
- Learning-Rate-Free Stochastic Optimization over Riemannian Manifolds (ICML 2024 · similarity 0.89)
- A Framework for Bilevel Optimization on Riemannian Manifolds (NeurIPS 2024 · similarity 0.87)
- Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms (ICML 2024 · similarity 0.87)
- Acceleration via silver step-size on Riemannian manifolds with applications to Wasserstein space (NeurIPS 2025 · similarity 0.87)
- Riemannian Accelerated Zeroth-order Algorithm: Improved Robustness and Lower Query Complexity (ICML 2024 · 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.