Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport

Abstract

In recent years, stochastic variance reduction algorithms have attracted considerable attention for minimizing the average of a large but finite number of loss functions. This paper proposes a novel Riemannian extension of the Euclidean stochastic variance reduced gradient (R-SVRG) algorithm to a manifold search space. The key challenges of averaging, adding, and subtracting multiple gradients are addressed with retraction and vector transport. For the proposed algorithm, we present a global convergence analysis with a decaying step size as well as a local convergence rate analysis with a fixed step size under some natural assumptions. In addition, the proposed algorithm is applied to the computation problem of the Riemannian centroid on the symmetric positive definite (SPD) manifold as well as the principal component analysis and low-rank matrix completion problems on the Grassmann manifold. The results show that the proposed algorithm outperforms the standard Riemannian stochastic gradient descent algorithm in each case.

Published in SIAM Journal on Optimization. Extended and revised version of arXiv:1605.07367

References in corpus (6)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Kernel Methods on Riemannian Manifolds with Gaussian RBF Kernels
• Proximal Stochastic Dual Coordinate Ascent
• SDCA without Duality
• Riemannian stochastic quasi-Newton algorithm with variance reduction and its convergence analysis

Cited by in corpus (26)

• Cheap Orthogonal Constraints in Neural Networks: A Simple Parametrization of the Orthogonal and Unitary Group
• Riemannian conjugate gradient methods: General framework and specific algorithms with convergence analyses
• Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes
• Averaging Stochastic Gradient Descent on Riemannian Manifolds
• R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
• Riemannian adaptive stochastic gradient algorithms on matrix manifolds
• McTorch, a manifold optimization library for deep learning
• Scaling-up Distributed Processing of Data Streams for Machine Learning
• On Riemannian Optimization over Positive Definite Matrices with the Bures-Wasserstein Geometry
• Riemannian Smoothing Gradient Type Algorithms]{Riemannian Smoothing Gradient Type Algorithms for Nonsmooth Optimization Problem on Compact Riemannian Submanifold Embedded in Euclidean Space
• A Variance-Reduced Stochastic Gradient Tracking Algorithm for Decentralized Optimization with Orthogonality Constraints
• No-go Theorem for Acceleration in the Hyperbolic Plane
• Variance reduction for Riemannian non-convex optimization with batch size adaptation
• Riemannian Adaptive Optimization Algorithm and Its Application to Natural Language Processing
• Global Riemannian Acceleration in Hyperbolic and Spherical Spaces
• A Brief Introduction to Manifold Optimization
• Riemannian stochastic recursive momentum method for non-convex optimization
• On Riemannian Stochastic Approximation Schemes with Fixed Step-Size
• Riemannian Stochastic Variance-Reduced Cubic Regularized Newton Method for Submanifold Optimization
• A Riemannian Primal-dual Algorithm Based on Proximal Operator and its Application in Metric Learning
• Convergence of variational Monte Carlo simulation and scale-invariant pre-training
• A Riemannian gossip approach to subspace learning on Grassmann manifold
• On the globalization of Riemannian Newton method
• Riemannian Stochastic Hybrid Gradient Algorithm for Nonconvex Optimization
• Stochastic Augmented Lagrangian Method in Riemannian Shape Manifolds
• Some Limit Properties of Markov Chains Induced by Stochastic Recursive Algorithms