Vector Transport-Free SVRG with General Retraction for Riemannian Optimization: Complexity Analysis and Practical Implementation

Abstract

In this paper, we propose a vector transport-free stochastic variance reduced gradient (SVRG) method with general retraction for empirical risk minimization over Riemannian manifold. Existing SVRG methods on manifold usually consider a specific retraction operation, and involve additional computational costs such as parallel transport or vector transport. The vector transport-free SVRG with general retraction we propose in this paper handles general retraction operations, and do not need additional computational costs mentioned above. As a result, we name our algorithm S-SVRG, where the first "S" means simple. We analyze the iteration complexity of S-SVRG for obtaining an $\epsilon$-stationary point and its local linear convergence by assuming the Łojasiewicz inequality, which naturally holds for PCA and holds with high probability for matrix completion problem. We also incorporate the Barzilai-Borwein step size and design a very practical S-SVRG-BB method. Numerical results on PCA and matrix completion problems are reported to demonstrate the efficiency of our methods.

References in corpus (9)

• Global rates of convergence for nonconvex optimization on manifolds
• Stochastic Variance Reduction for Nonconvex Optimization
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Variance Reduction for Faster Non-Convex Optimization
• Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity
• A SMART Stochastic Algorithm for Nonconvex Optimization with Applications to Robust Machine Learning
• Riemannian stochastic variance reduced gradient on Grassmann manifold
• Stochastic Variance Reduced Riemannian Eigensolver
• A conjugate gradient method for electronic structure calculations

Cited by in corpus (6)

• Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods
• A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distance
• A Variance-Reduced Stochastic Gradient Tracking Algorithm for Decentralized Optimization with Orthogonality Constraints
• Proximal Gradient Method for Nonsmooth Optimization over the Stiefel Manifold
• Two-sample Test with Kernel Projected Wasserstein Distance
• A Brief Introduction to Manifold Optimization