R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
arXiv:1811.04194
Abstract
We study smooth stochastic optimization problems on Riemannian manifolds. Via adapting the recently proposed SPIDER algorithm \citep{fang2018spider} (a variance reduced stochastic method) to Riemannian manifold, we can achieve faster rate than known algorithms in both the finite sum and stochastic settings. Unlike previous works, by \emph{not} resorting to bounding iterate distances, our analysis yields curvature independent convergence rates for both the nonconvex and strongly convex cases.
arXiv admin note: text overlap with arXiv:1605.07147
References in corpus (13)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- 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
- Multivariate Generalized Gaussian Distribution: Convexity and Graphical Models
- SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient
- Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport
- Averaging Stochastic Gradient Descent on Riemannian Manifolds
- First-order Methods for Geodesically Convex Optimization
- SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms
- Towards Riemannian Accelerated Gradient Methods
- Linear Convergence of Variance-Reduced Stochastic Gradient without Strong Convexity
- Riemannian stochastic variance reduced gradient on Grassmann manifold
Cited by in corpus (13)
- SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms
- From Nesterov's Estimate Sequence to Riemannian Acceleration
- Riemannian Stochastic Proximal Gradient Methods for Nonsmooth Optimization over the Stiefel Manifold
- Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature
- Variance reduction for Riemannian non-convex optimization with batch size adaptation
- Global Riemannian Acceleration in Hyperbolic and Spherical Spaces
- On the Convergence of SARAH and Beyond
- Convergence Analysis of Riemannian Stochastic Approximation Schemes
- Solving Optimization Problems over the Stiefel Manifold by Smooth Exact Penalty Function
- Riemannian stochastic recursive momentum method for non-convex optimization
- Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimization
- Accelerated Algorithms for Convex and Non-Convex Optimization on Manifolds
- Non-local Optimization: Imposing Structure on Optimization Problems by Relaxation