Riemannian stochastic variance reduced gradient on Grassmann manifold (2016-05-24T00:00:00.000000Z)

TL;DR

This paper proposes a novel Riemannian extension of the Euclidean stochastic variance reduced gradient algorithm (R-SVRG) to a compact manifold search space and shows the developments on the 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.

Authors

Bamdev Mishra

3 papers

Hiroyuki Kasai

2 papers

Hiroyuki Sato

2 papers

TL;DR

Abstract

Authors

References30 items

Fast stochastic optimization on Riemannian manifolds

Variance Reduction for Faster Non-Convex Optimization

First-order Methods for Geodesically Convex Optimization

Fast and Simple PCA via Convex Optimization

Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity

Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives

SDCA without Duality

Kernel Methods on Riemannian Manifolds with Gaussian RBF Kernels

Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization

SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives

Low-rank tensor completion by Riemannian optimization

Riemannian Preconditioning

Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning

Semi-Stochastic Gradient Descent Methods

Accelerating Stochastic Gradient Descent using Predictive Variance Reduction

Manopt, a matlab toolbox for optimization on manifolds

R3MC: A Riemannian three-factor algorithm for low-rank matrix completion

Proximal Stochastic Dual Coordinate Ascent

A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets

Riemannian Consensus for Manifolds With Bounded Curvature

Stochastic Gradient Descent on Riemannian Manifolds

Linear Regression under Fixed-Rank Constraints: A Riemannian Approach

Online identification and tracking of subspaces from highly incomplete information

Eigentaste: A Constant Time Collaborative Filtering Algorithm

Riemannian center of mass and mollifier smoothing

Optimization algorithms on matrix manifolds

Γ and B

An Introduction to the geometry of Alexandrov spaces

Quasi-martingales

Journal of Machine Learning Research () Submitted 9/12; Published Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization

Field of Study

Journal Information

Name

Volume

Venue Information

Name

Type

URL

Alternate Names