Riemannian stochastic variance reduced gradient on Grassmann manifold

Abstract

Stochastic variance reduction algorithms have recently become popular for minimizing the average of a large, but finite, number of loss functions. In this paper, we propose a novel Riemannian extension of the Euclidean stochastic variance reduced gradient algorithm (R-SVRG) to a compact manifold search space. To this end, we show the developments on the Grassmann manifold. The key challenges of averaging, addition, and subtraction of multiple gradients are addressed with notions like logarithm mapping and parallel translation of vectors on the Grassmann manifold. We present a global convergence analysis of the proposed algorithm with decay step-sizes and a local convergence rate analysis under fixed step-size with some natural assumptions. The proposed algorithm is applied on a number of problems on the Grassmann manifold like principal components analysis, low-rank matrix completion, and the Karcher mean computation. In all these cases, the proposed algorithm outperforms the standard Riemannian stochastic gradient descent algorithm.

References in corpus (6)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Kernel Methods on Riemannian Manifolds with Gaussian RBF Kernels
• Variance Reduction for Faster Non-Convex Optimization
• Proximal Stochastic Dual Coordinate Ascent
• Fast and Simple PCA via Convex Optimization
• SDCA without Duality

Cited by in corpus (8)

• Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport
• Towards Riemannian Accelerated Gradient Methods
• R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
• From Nesterov's Estimate Sequence to Riemannian Acceleration
• Vector Transport-Free SVRG with General Retraction for Riemannian Optimization: Complexity Analysis and Practical Implementation
• Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis
• A Cubic Regularized Newton's Method over Riemannian Manifolds
• Sequence Summarization Using Order-constrained Kernelized Feature Subspaces