First-Order Methods for Riemannian Optimization

Riemannian optimization (RO) minimizes a cost function over a Riemannian manifold, exploded in popularity due to its many big data applications including metric learning, mixture model parameter estimation and covariance estimation etc. The typical manifold underlying an RO problem from data science has a dimension numbered in the thousands or millions, if not higher. Algorithms that use only the objective function’s first-order differential information, called first-order methods, are particularly attractive for these problems due to their relatively low storage and iteration costs.  This talk will start with an overview of the modern history of first-order methods in large-scale optimization on convex subsets of Euclidean space.  Our aim is to provide an understanding of these methods and their attendant benefits in the simplest setting. Next, we will generalize these algorithms to the RO setting. Naturally, these broad generalizations entail challenges of commensurate difficulty to which we will pay special emphasis. In the final part of this talk, we describe the tangent subspace descent (TSD) framework, which generalizes block coordinate descent (BCD) methods to the RO setting. The TSD framework brings forth the main benefits of BCD methods, namely simplicity and low iteration costs, to extremely large-scale RO.