Coordinate Descent Without Coordinates: Tangent Subspace Descent on Riemannian Manifolds

David H. Gutman () and Nam Ho-Nguyen ()
Additional contact information
David H. Gutman: Department of Industrial, Manufacturing, and Systems Engineering, Texas Tech University, Lubbock, Texas 79407
Nam Ho-Nguyen: Discipline of Business Analytics, The University of Sydney, Sydney, New South Wales 2006, Australia

Mathematics of Operations Research, 2023, vol. 48, issue 1, 127-159

Abstract: We extend coordinate descent to manifold domains and provide convergence analyses for geodesically convex and nonconvex smooth objective functions. Our key insight is to draw an analogy between coordinate blocks in Euclidean space and tangent subspaces of a manifold. Hence, our method is called tangent subspace descent (TSD). The core principle behind ensuring convergence of TSD is the appropriate choice of subspace at each iteration. To this end, we propose two novel conditions, the ( C , r )-norm and C -randomized norm conditions on deterministic and randomized modes of subspace selection, respectively, that promise convergence for smooth functions and that are satisfied in practical contexts. We propose two subspace selection rules, one deterministic and another randomized, of particular practical interest on the Stiefel manifold. Our proof-of-concept numerical experiments on the sparse principal component analysis problem demonstrate TSD’s efficacy.

Keywords: Primary: 90C06; 90C30; 53B21; coordinate descent; optimization on manifolds; first-order methods (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1253 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:1:p:127-159

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().