Riemannian optimization via Frank-Wolfe methods

Journal article

We study projection-free methods for constrained Riemannian optimization. In particular, we propose a Riemannian Frank-Wolfe (RFW) method that handles constraints directly, in contrast to prior methods that rely on (potentially costly) projections. We analyze non-asymptotic convergence rates of RFW to an optimum for geodesically convex problems, and to a critical point for nonconvex objectives. We also present a practical setting under which RFW can attain a linear convergence rate. As a concrete example, we specialize RFW to the manifold of positive definite matrices and apply it to two tasks: (i) computing the matrix geometric mean (Riemannian centroid); and (ii) computing the Bures-Wasserstein barycenter. Both tasks involve geodesically convex interval constraints, for which we show that the Riemannian “linear” oracle required by RFW admits a closed form solution; this result may be of independent interest. We complement our theoretical results with an empirical comparison of RFW against state-of-the-art Riemannian optimization methods, and observe that RFW performs competitively on the task of computing Riemannian centroids.

Authors: Weber, M; Sra, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer
• Journal: Mathematical Programming
• Volume: 199
• Pages: 525-556
• Publication date: 2022-07-14
• Acceptance date: 2022-05-10
• DOI: 10.1007/s10107-022-01840-5
• EISSN: 1436-4646
• ISSN: 0025-5610
• Language: English
• Keywords: FFR