Riemannian Frank-Wolfe Methods

Many applications involve non-Euclidean data, such as graphs, strings or matrices. It is often beneficial to represent data in its natural space instead of computing costly, high-dimensional Euclidean embeddings. In particular, while an optimization or learning task might be hard to solve in Euclidean space, it becomes more accessible when viewed through a different, more natural geometric lense. In joint work with S. Sra (MIT), I developed efficient methods for geometric optimization on Riemannian manifolds building on a generalization of the classic Frank-Wolfe method.

In particular, we study a class of Riemannian Frank-Wolfe (RFW) methods for geodesically convex tasks. At the heart of the algorithm lies a Riemannian “linear” oracle that determines the update conditioned on geodesically convex constraints. Developing means of solving this “linear” oracle efficiently is crucial to the competitiveness of the method. While in general a nonconvex semi-definite problem, we discuss matrix-valued tasks where the solution can be computed in closed form. Furthermore, we show that RFW converges at a nonasymptotic sublinear rate. Under stronger assumptions, we can even recover linear convergence. RFW naturally extends to stochastic and finite-sum settings. Here we show that RFW converges at a sublinear rate, even if the objective is nonconvex. Our non-asymptotic convergence rates recover the best known rates of RFW’s Euclidean counterparts. Numerically, we observe performance gains on benchmark tasks in comparison with state-of-the-art Riemannian optimization methods.

Publications

  • M. Weber, S.Sra (2021): Projection-free nonconvex stochastic optimization on Riemannian manifolds. arXiv:1910.04194 IMA Numerical Analysis.[arXiv]
  • M. Weber, S.Sra (2017): Riemannian Optimization via Frank-Wolfe Methods. arXiv:1710.10770 Under review (Journal).[arXiv]
Code: GitHub