Riemannian coordinate descent algorithms on matrix manifolds

Andi Han, Pratik Jawanpuria, Bamdev Mishra

TL;DR

This paper introduces a general framework for Riemannian Coordinate Descent (RCD), allowing for computationally efficient optimization on complex matrix manifolds by updating only a few variables at a time. By identifying specific tangent space bases that enable low-cost "retractions," the authors significantly reduce the per-iteration overhead of manifold optimization, offering a linearized variant (RCDlin) that further accelerates performance when gradients are expensive to compute.

What Problem Does This Paper Address?

Many machine learning problems—from Principal Component Analysis (PCA) to training "orthogonal" neural networks—are naturally constrained. We might require a matrix to be orthogonal (columns are unit vectors and perpendicular) or symmetric positive definite (SPD). Riemannian optimization is the standard tool for this, but it has a major drawback: every update must be "retracted" back onto the manifold to maintain feasibility.

For large matrices of size $n \times n$, these retractions often involve operations like SVD or matrix exponentials, which scale as $O(n^3)$. Furthermore, standard Riemannian Gradient Descent (RGD) updates every single entry of the matrix in every step. In the Euclidean world, Coordinate Descent (CD) solves this by updating one variable at a time, making each step trivial. This paper brings that "cheap update" philosophy to the curved world of Riemannian manifolds.

Methods

The authors propose a framework to design CD algorithms for a wide variety of manifolds, including Stiefel, Grassmann, Hyperbolic, Symplectic, and SPD manifolds. Their approach relies on three key pillars:

  1. Smart Basis Selection: They identify a basis for the tangent space such that moving along a single basis vector corresponds to a very simple transformation (like a Givens rotation for orthogonal matrices).
  2. Efficient Retractions: Because only a few "coordinates" change, the retraction back to the manifold becomes much cheaper—often reducing the cost from $O(n^3)$ to $O(n)$ or even $O(1)$.
  3. RCDlin (Linearized RCD): Computing a full gradient for every tiny coordinate update is wasteful. RCDlin uses an "anchored" gradient at the start of an epoch and performs multiple coordinate updates based on that fixed gradient, drastically reducing the number of expensive gradient evaluations.

Datasets

The researchers evaluated their algorithms across several benchmark tasks:

  • Orthogonal Procrustes & PCA: Synthetic datasets used to measure FLOP counts and convergence rates.
  • Orthogonal Deep Network Distillation: A six-layer network architecture with orthonormal weights, trained to mimic a teacher network.
  • Nearest Matrix Problem: Finding the closest symplectic matrix to a random matrix.
  • Learning Lorentz Embeddings: Using the WordNet mammals subtree to learn hierarchical word embeddings in hyperbolic space.
  • Weighted Least Squares: A matrix completion task on SPD/SPSD manifolds.

Key Insights and Ideas

  • Row-wise vs. Column-wise: For the Stiefel manifold, the authors show that row-wise updates are $O(p)$, which is more efficient than previous column-wise approaches that cost $O(np)$.
  • The Power of Rotations: By using Givens rotations (for Stiefel/Grassmann) and hyperbolic rotations (for hyperbolic manifolds), the "curved" update becomes a simple 2D transformation that is extremely fast to compute.
  • Gradient Connection: They leverage a simple but powerful identity: the Riemannian coordinate derivative can be computed directly from the Euclidean gradient, bypassing the need to compute the full Riemannian gradient explicitly for every sub-step.
  • Invariance Matters: Unlike some previous manifold CD methods, this framework is invariant to basis changes, making it applicable to the Grassmann manifold (where we care about the subspace spanned by columns, not the specific columns themselves).

Key Results

The proposed RCD and RCDlin algorithms consistently outperformed standard Riemannian Gradient Descent (RGD) and other state-of-the-art baselines in terms of computational efficiency.

  • FLOP Efficiency: In the Orthogonal Procrustes problem, RCD achieved a significantly lower FLOP count to reach the same optimality gap compared to standard retractions (QR, Cayley, Exponential).
Figure 1: The Procrustes problem with varying p: (a) p = 150 and (b) p = 50. (Top row) Comparing various al- gorithms in terms of flop counts. (Bottom row) Comparing various algorithms in terms of runtime. We observe that our RCD algorithm obtains better flop counts than the baselines in flop counts and is competitive in terms of runtime.
  • Deep Learning Speedup: For orthogonal network distillation, RCD was faster in both FLOPs and actual wall-clock time, as shown in Figure 3. This is because the cost-efficient coordinate updates allow for more frequent progress than the heavy global updates of RGD.
  • Hyperbolic Embeddings: RCDlin proved competitive with RGD for learning Lorentz embeddings, showing that coordinate descent is a viable and efficient alternative for hyperbolic geometry tasks.

Limitations and Future Work

The authors note that their convergence analysis currently assumes the optimization stays within a compact neighborhood of a critical point. While this is standard for many manifold proofs, global convergence guarantees under more general conditions remain an open area.

Additionally, while the paper discusses parallelization (e.g., performing multiple independent Givens rotations simultaneously), the experimental results primarily focus on sequential implementations. Future work could explore the full potential of asynchronous or parallel Riemannian coordinate descent on high-performance hardware.

Summary updated

Abstract

Many machine learning applications are naturally formulated as optimization problems on Riemannian manifolds. The main idea behind Riemannian optimization is to maintain the feasibility of the variables while moving along a descent direction on the manifold. This results in updating all the variables at every iteration. In this work, we provide a general framework for developing computationally efficient coordinate descent (CD) algorithms on matrix manifolds that allows updating only a few variables at every iteration while adhering to the manifold constraint. In particular, we propose CD algorithms for various manifolds such as Stiefel, Grassmann, (generalized) hyperbolic, symplectic, and symmetric positive (semi)definite. While the cost per iteration of the proposed CD algorithms is low, we further develop a more efficient variant via a first-order approximation of the objective function. We analyze their convergence and complexity, and empirically illustrate their efficacy in several applications.
BibTeX
@inproceedings{han2024riemannian,
  author = {Andi Han and Pratik Jawanpuria and Bamdev Mishra},
  title = {{Riemannian coordinate descent algorithms on matrix manifolds}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=bdKaQmrM81},
}
Figure