Joint Mathematics Meeting

Riemannian Frank-Wolfe Methods


Many applications involve non-Euclidean data, where exploiting Riemannian geometry can deliver algorithms that are computationally superior to standard nonlinear programming approaches, resulting in an increasing interest in Riemannian methods in the machine learning community. We introduce Riemannian Frank-Wolfe (RFW) methods as a class of projection-free algorithms for constraint geodesically (non-)convex optimization. RFW is guaranteed to stay in the feasible region, circumventing the need to compute the potentially costly projections required by projected-gradient approaches in the prior literature. At the heart of RFW lies a Riemannian “linear” oracle that determines the update conditioned on geodesically convex constraints. While in general a nonconvex semi-definite problem, we discuss matrix- valued tasks where the solution can be computed in closed form. RFW extends naturally to stochastic settings, where we discuss both purely stochastic and finite-sum problems, including empirical risk minimization. We show that RFW converges at a nonasymptotic sublinear rate, recovering the best-known guarantees for its Euclidean counterpart. We discuss the computation of Riemannian centroids and Wasserstein barycenters, which are crucial subroutines in many machine learning methods.

Jan 5, 2021
Melanie Weber
Melanie Weber
Assistant Professor