CAREER: AF: Fast Algorithms for Riemannian Optimization

Riemannian optimization, the study of minimizing a cost function over a Riemannian manifold, is surging in prominence due to its many applications in modern statistics and machine learning. A small sample of these popular applications includes metric learning, mixture model parameter estimation, covariance estimation and subspace recovery, and matrix completion. In the non-statistical realm, Riemannian optimization is becoming an important toolset for diffusion tensor imaging, a novel technology for using magnetic resonance imaging to profile the human brain, as well as for solving synchronization of rotation problems that support 3-D imaging of real-world objects. This award's overarching goal is to construct new methods for solving Riemannian optimization problems with the fastest possible computational speed. Tangible benefits of this award will include new software packages for easily solving Riemannian optimization problems, new educational materials that introduce this exciting field to undergraduate and graduate students, and funding for graduate students. Explained on a more granular level, the award aims to construct optimal rate methods, where such rates are quantified in calls to oracles that produce differential information for minimizing a cost function over a Riemannian manifold. Each of the award's constituent projects will lead to the development of algorithms whose complexity matches their analogs for optimization over a subset of a Euclidean space, such as gradient descent and Newton's method. To this end, the award focuses on two broad classes of problems: geodesically convex optimization problems and geodesically non-convex optimization problems. Naturally, geodesically convex optimization is the generalization of convex optimization to the manifold setting. Inspired by Nesterov's famous work on accelerated gradient descent, the award pays particular attention to the incorporation of Nesterov-style momentum in existing Riemannian optimization methods based on first- and second-order differential information. To benefit the real-world practice of Riemannian optimization, the award will further fund the development of deployable software packages that include the optimal rate algorithms built during this research. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.