Coordinate Descent Without Coordinates
Date:
Locations:
- INFORMS Annual Meeting 2022, Indianapolis, IN
- INFORMS Annual Meeting 2021, Anaheim, CA
- WOMBAT 2021, Virtual
We consider an extension of the coordinate descent algorithm to manifold domains, and provide convergence analyses for geodesically convex and non- convex 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 gap ensuring and C-randomized norm conditions on deterministic and randomized modes of subspace selection respectively. These ensure convergence for smooth functions, and are satisfied in practical contexts. We propose randomized and deterministic subspace selection rules of particular practical interest for the Stiefel manifold