Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction
This work addresses a practical bottleneck in Riemannian optimization for researchers and practitioners by making variance reduction more efficient and easier to tune, though it is incremental as it adapts existing Euclidean methods to the Riemannian setting.
The authors tackled the challenge of determining optimal inner loop lengths in Riemannian variance-reduced optimization by introducing loopless methods like R-LSVRG and R-PAGE, which use probabilistic gradient computation to simplify hyperparameter selection and achieve sharp convergence guarantees, with R-MARINA providing the best theoretical communication complexity for distributed non-convex optimization on Riemannian manifolds.
In this study, we investigate stochastic optimization on Riemannian manifolds, focusing on the crucial variance reduction mechanism used in both Euclidean and Riemannian settings. Riemannian variance-reduced methods usually involve a double-loop structure, computing a full gradient at the start of each loop. Determining the optimal inner loop length is challenging in practice, as it depends on strong convexity or smoothness constants, which are often unknown or hard to estimate. Motivated by Euclidean methods, we introduce the Riemannian Loopless SVRG (R-LSVRG) and PAGE (R-PAGE) methods. These methods replace the outer loop with probabilistic gradient computation triggered by a coin flip in each iteration, ensuring simpler proofs, efficient hyperparameter selection, and sharp convergence guarantees. Using R-PAGE as a framework for non-convex Riemannian optimization, we demonstrate its applicability to various important settings. For example, we derive Riemannian MARINA (R-MARINA) for distributed settings with communication compression, providing the best theoretical communication complexity guarantees for non-convex distributed optimization over Riemannian manifolds. Experimental results support our theoretical findings.