Variance reduction for Riemannian non-convex optimization with batch size adaptation

Abstract

Variance reduction techniques are popular in accelerating gradient descent and stochastic gradient descent for optimization problems defined on both Euclidean space and Riemannian manifold. In this paper, we further improve on existing variance reduction methods for non-convex Riemannian optimization, including R-SVRG and R-SRG/R-SPIDER with batch size adaptation. We show that this strategy can achieve lower total complexities for optimizing both general non-convex and gradient dominated functions under both finite-sum and online settings. As a result, we also provide simpler convergence analysis for R-SVRG and improve complexity bounds for R-SRG under finite-sum setting. Specifically, we prove that R-SRG achieves the same near-optimal complexity as R-SPIDER without requiring a small step size. Empirical experiments on a variety of tasks demonstrate effectiveness of proposed adaptive batch size scheme.

References in corpus (18)

• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Don't Decay the Learning Rate, Increase the Batch Size
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• Global rates of convergence for nonconvex optimization on manifolds
• Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
• Stop Wasting My Gradients: Practical SVRG
• Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport
• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• Averaging Stochastic Gradient Descent on Riemannian Manifolds
• Towards Riemannian Accelerated Gradient Methods
• R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
• Coupling Adaptive Batch Sizes with Learning Rates
• Riemannian adaptive stochastic gradient algorithms on matrix manifolds
• From Nesterov's Estimate Sequence to Riemannian Acceleration
• History-Gradient Aided Batch Size Adaptation for Variance Reduced Algorithms
• Momentum Improves Optimization on Riemannian Manifolds
• Riemannian Adaptive Optimization Algorithm and Its Application to Natural Language Processing
• Improving the convergence of SGD through adaptive batch sizes

Cited by in corpus (3)

• On Riemannian Optimization over Positive Definite Matrices with the Bures-Wasserstein Geometry
• Riemannian stochastic recursive momentum method for non-convex optimization
• On Riemannian Stochastic Approximation Schemes with Fixed Step-Size