Projection-free nonconvex stochastic optimization on Riemannian manifolds

DOI10.1093/IMANUM/DRAB066MaRDI QIDQ5042891zbMATH OpenOpenAlexWikidataFDO

Authors Melanie Weber, Suvrit Sra

Publication date 26 October 2022

Published in IMA Journal of Numerical Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.04194

zbMATH Keywords

nonconvex optimizationpositive definite matricesKarcher meanRiemannian optimizationFrank-Wolfe methodsWasserstein barycenters

Mathematics Subject Classification ID

Probabilistic methods, stochastic differential equations (65C99) Numerical optimization and variational techniques (65K10)

Abstract: We study stochastic projection-free methods for constrained optimization of smooth functions on Riemannian manifolds, i.e., with additional constraints beyond the parameter domain being a manifold. Specifically, we introduce stochastic Riemannian Frank-Wolfe methods for nonconvex and geodesically convex problems. We present algorithms for both purely stochastic optimization and finite-sum problems. For the latter, we develop variance-reduced methods, including a Riemannian adaptation of the recently proposed Spider technique. For all settings, we recover convergence rates that are comparable to the best-known rates for their Euclidean counterparts. Finally, we discuss applications to two classic tasks: The computation of the Karcher mean of positive definite matrices and Wasserstein barycenters for multivariate normal distributions. For both tasks, stochastic Fw methods yield state-of-the-art empirical performance.

Recommendations

• Riemannian optimization via Frank-Wolfe methods
• Recent Advances in Stochastic Riemannian Optimization
• Riemannian Stochastic Variance Reduced Gradient Algorithm with Retraction and Vector Transport
• Riemannian stochastic fixed point optimization algorithm
• Riemannian stochastic variance-reduced cubic regularized Newton method for submanifold optimization

Cited in

(7)

• Riemannian optimization via Frank-Wolfe methods
• Recent Advances in Stochastic Riemannian Optimization
• Riemannian stochastic fixed point optimization algorithm
• Stochastic Gradient Descent on Riemannian Manifolds
• Manifold Optimization Over the Set of Doubly Stochastic Matrices: A Second-Order Geometry
• Stochastic completeness and gradient representations for Sub-Riemannian manifolds
• Riemannian gradient methods for stochastic composition problems

This page was built for publication: Projection-free nonconvex stochastic optimization on Riemannian manifolds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5042891)