Riemannian coordinate descent algorithms on matrix manifolds
This work addresses computational efficiency for machine learning practitioners dealing with optimization on matrix manifolds, representing an incremental improvement over existing methods.
The authors tackled the problem of high computational cost in Riemannian optimization by developing a coordinate descent framework that updates only a few variables per iteration while maintaining manifold constraints, resulting in low-cost algorithms with proven convergence and empirical efficacy.
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.