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

2020/07/03 by Andi Han, Han, Andi, Junbin Gao +1
Computer Science · Engineering · #FOS: Computer and information sciences #FOS: Mathematics #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2007.01494

openalex publication_date 2020/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• A Riemannian symmetric rank-one trust-region method
• Gradient-based learning applied to document recognition
• Computing the Karcher mean of symmetric positive definite matrices
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp\n Minima
• Coupling Adaptive Batch Sizes with Learning Rates
• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Don't Decay the Learning Rate, Increase the Batch Size
• Riemannian adaptive stochastic gradient algorithms on matrix manifolds
• Riemannian stochastic quasi-Newton algorithm with variance reduction and its convergence analysis
• History-Gradient Aided Batch Size Adaptation for Variance Reduced\n Algorithms
• Riemannian Adaptive Optimization Algorithm and Its Application to Natural Language Processing

Related

• Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction
• Stochastic Variance Reduction for Nonconvex Optimization
• Riemannian Stochastic Hybrid Gradient Algorithm for Nonconvex Optimization
• k-SVRG: Variance Reduction for Large Scale Optimization
• Variance Reduction for Faster Non-Convex Optimization