Improved Variance Reduction Methods for Riemannian Non-Convex Optimization.

Area of Science:

• Optimization Theory
• Riemannian Geometry
• Machine Learning

Background:

• Gradient descent and stochastic gradient descent are crucial for optimization.
• Variance reduction techniques accelerate these methods on Euclidean and Riemannian spaces.
• Existing methods for non-convex Riemannian optimization have limitations.

Purpose of the Study:

• To develop a unified framework for adaptive batch size in variance reduction for non-convex Riemannian optimization.
• To improve upon existing methods like R-SVRG and R-SRG/R-SPIDER.
• To analyze the theoretical properties and complexities of these adaptive methods.

Main Methods:

• Introduced a generalized framework for batch size adaptation in Riemannian optimization.
• Incorporated retraction, vector transport, and mini-batch stochastic gradients.
• Completed theoretical analysis for R-SVRG and R-SRG under the new framework.

Main Results:

• Adaptive-batch variance reduction methods demonstrate lower gradient complexities for general non-convex and gradient-dominated functions.
• Achieved curvature-free complexity bounds for R-SVRG convergence with simplified analysis.
• Provided improved double-loop convergence results for R-SRG, matching R-SPIDER complexities.
• Established the first online complexity results for R-SVRG and R-SRG.

Conclusions:

• The proposed adaptive batch size framework offers significant theoretical improvements for Riemannian optimization.
• The framework provides a unified approach to analyze and enhance existing variance reduction methods.
• Future work can extend this framework to non-smooth, constrained, and second-order Riemannian optimizers.