Faster First-Order Methods for Stochastic Non-Convex Optimization on Riemannian Manifolds

Area of Science:

• Optimization Theory
• Machine Learning
• Differential Geometry

Background:

• Non-convex Riemannian optimization is crucial for structured machine learning tasks like PCA and matrix completion.
• Existing algorithms face challenges in computational efficiency and convergence guarantees.

Purpose of the Study:

• To propose an efficient Riemannian Stochastic Path Integrated Differential EstimatoR (R-SPIDER) algorithm.
• To address both finite-sum and online Riemannian non-convex minimization problems.
• To improve first-order oracle complexity compared to prior methods.

Main Methods:

• Development of a recursive semi-stochastic gradient estimator for accurate Riemannian gradient estimation.
• Adaptation for general retraction and vector transport operations.
• Analysis of convergence for finite-sum and online settings.

Main Results:

• R-SPIDER achieves improved stochastic gradient evaluations for finite-sum problems: [Formula: see text] vs. [Formula: see text].
• First non-asymptotic convergence result for online Riemannian optimization with [Formula: see text] complexity.
• A variant of R-SPIDER demonstrates linear convergence for gradient-dominated functions.

Conclusions:

• R-SPIDER offers significant computational advantages and better convergence guarantees in Riemannian non-convex optimization.
• The proposed methods outperform state-of-the-art Riemannian non-convex optimization techniques.
• This work advances the field of optimization for structured machine learning.