Source-linked AI summary
Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
Hongyi Zhang, Sashank J. Reddi, Suvrit Sra
TL;DR
Finite-sum optimization on Riemannian manifolds lacked fast variance-reduced stochastic methods and non-asymptotic analysis, especially for nonconvex objectives. The paper introduces RSVRG, analyzes it across geodesic function classes while accounting for curvature, and reports first-of-kind convergence guarantees with applications including variance-reduced PCA. These results position RSVRG as a provably fast stochastic Riemannian method, although practical retractions and vector transports remain unanalyzed.
Problem
Variance-reduction methods for finite sums were limited to vector spaces, while Riemannian stochastic optimization lacked broad non-asymptotic convergence analysis.
Method
The paper introduces RSVRG, a variance-reduced Riemannian stochastic gradient method, and analyzes it for geodesically convex and nonconvex objectives with curvature-dependent factors.
Results
The paper reports global linear convergence for geodesically strongly convex functions and the first non-asymptotic convergence rates for geodesically nonconvex optimization, including batch settings.
Takeaways & Limitations
RSVRG provides a Riemannian perspective on variance-reduced PCA and is reported to outperform full-gradient and stochastic-gradient methods on finite-sum manifold problems.
Takeaways & Limitations
The analysis does not cover practical retractions and vector transports that approximate the exponential map and parallel transport.
Abstract
from arXiv · showhide
We study optimization of finite sums of geodesically smooth functions on Riemannian manifolds. Although variance reduction techniques for optimizing finite-sums have witnessed tremendous attention in the recent years, existing work is limited to vector space problems. We introduce Riemannian SVRG (RSVRG), a new variance reduced Riemannian optimization method. We analyze RSVRG for both geodesically convex and nonconvex (smooth) functions. Our analysis reveals that RSVRG inherits advantages of the usual SVRG method, but with factors depending on curvature of the manifold that influence its convergence. To our knowledge, RSVRG is the first provably fast stochastic Riemannian method. Moreover, our paper presents the first non-asymptotic complexity analysis (novel even for the batch setting) for nonconvex Riemannian optimization. Our results have several implications; for instance, they offer a Riemannian perspective on variance reduced PCA, which promises a short, transparent convergence analysis.
1 Introduction
The paper addresses the limited development of fast, non-asymptotic stochastic optimization on nonlinear Riemannian manifolds by introducing and analyzing RSVRG. It connects the method to applications including PCA and covariance-matrix centroids.
- Finite-sum optimization on Riemannian manifolds models empirical risk minimization and applications including PCA, ICA, dictionary learning, and mixture modeling.
- Projection-based methods can be expensive for manifolds such as positive definite matrices, motivating projection-free Riemannian optimization.
- RSVRG is a variance-reduced Riemannian stochastic gradient method analyzed for geodesically strongly convex, convex, nonconvex, and gradient-dominated functions.
- The analysis provides a Riemannian perspective on variance-reduced PCA and applications to leading-eigenvector computation and covariance-matrix centroids.
- The paper reports global linear rates for geodesically strongly convex functions and the first non-asymptotic rates for geodesically nonconvex optimization, with curvature-dependent effects.
- Existing Riemannian stochastic methods had asymptotic analyses without convergence rates, while vector-space variance reduction relied on properties absent from manifolds.
2 Preliminaries
The preliminaries define the manifold operations, geometric assumptions, function classes, curvature tools, and oracle model used to analyze Riemannian optimization.
- A Riemannian manifold is a smooth manifold equipped with a metric inducing inner products and norms in each tangent space.
- Geodesics are locally distance-minimizing constant-speed curves, and the exponential map sends a tangent vector to the endpoint of its corresponding geodesic.
- Parallel transport moves tangent vectors between tangent spaces along geodesics while preserving inner products and norms.
- The analysis assumes optimization over a geodesically convex set and defines geodesic convexity through geodesics that remain inside the set.
- The framework uses geodesic strong convexity, geodesic Lipschitz gradients, geodesic smoothness, and gradient domination to characterize objectives.
- A curvature-dependent trigonometric distance bound and an incremental first-order oracle support the convergence analysis and its non-asymptotic complexity measure.
3 Riemannian SVRG
RSVRG combines variance reduction with Riemannian geometry and is analyzed under convex, nonconvex, and gradient-dominated objectives. Its convergence guarantees and complexity explicitly reflect sectional curvature, while the proof handles nonlinear metrics through distance-based bounds.
- Algorithm: RSVRG uses parallel transport to combine gradients from different tangent spaces and the exponential map for manifold updates.These replace Euclidean variance reduction and update operations in the algorithm.
- Strongly geodesically convex functions: Under strong geodesic convexity, RSVRG achieves linear convergence, contrasting with the O(1/t) rate of Riemannian stochastic gradient.The analysis assumes each component is L-smooth and the objective is μ-strongly geodesically convex.
- Strongly geodesically convex functions: The proof bounds the variance-reduced gradient using squared distances to the minimizer, then derives function-gap bounds from L-g-smoothness.This route reflects the difficulty introduced by the nonlinear Riemannian metric and yields a stronger condition-number dependence.
- Geometry dependence: Curvature affects convergence through ζ: negative lower curvature gives ζ > 1, whereas nonnegative curvature gives ζ = 1 and no explicit curvature factor.The same curvature mechanism appears in the nonconvex analysis through a lower sectional-curvature bound.
- Geodesically nonconvex functions: The nonconvex analysis requires only L-geodesic smoothness for each component and measures convergence using the squared norm of the Riemannian gradient.Theorem 2 specifies parameterized step size and epoch choices depending on n and ζ.
- Gradient-dominated functions: For gradient-dominated objectives, RSVRG reaches ε-accuracy in O((n + Lτζ^1/2n^2/3) log(1/ε)) IFO calls.Strongly geodesically convex objectives obtain the corresponding complexity O((n + μ^-1Lζ^1/2n^2/3) log(1/ε)).
4 Applications
The paper applies RSVRG to leading-eigenvector computation and Riemannian centroid estimation, showing curvature- and eigengap-dependent behavior and advantages on large datasets.
- 4.1 Computing the leading eigenvector: The leading-eigenvector problem is gradient dominated on the hypersphere despite being nonconvex with nonlinear constraints in Euclidean space.
- 4.1 Computing the leading eigenvector: O(1/δ) eigengap dependence is supported as a conjectured complexity target, improving on analyses with O(1/δ2) dependence.
- 4.1 Computing the leading eigenvector: RSVRG and VR-PCA are indistinguishable in IFO complexity, while estimated epochs to double accuracy appear to depend on 1/δ.
- 4.2 Computing the Riemannian centroid: For Riemannian means of PSD matrices, RSVRG is compared with RGD and RSGD on a geodesically strongly convex problem that is nonconvex in Euclidean space.
- 4.2 Computing the Riemannian centroid: RSVRG achieves linear convergence for PSD-matrix means and is especially advantageous for large datasets.
5 Discussion
The discussion presents RSVRG as a first variance-reduced stochastic method for Riemannian optimization, with theory and experiments supporting its speed and geometric perspective. It also identifies unanalysed practical approximations as a limitation.
- The analysis covers geodesically strongly convex, convex, and nonconvex functions while explicitly showing dependence on sectional curvature.
- Experiments validate the analysis by finding RSVRG much faster than full-gradient and stochastic-gradient methods on finite-sum manifold problems.
- Leading-eigenvector optimization becomes gradient dominated on the manifold even though its ambient formulation is nonconvex with nonlinear constraints.
- The work does not analyze retraction and vector transport, which practical Riemannian algorithms use to approximate exponential and parallel transport.
A Proofs for Section 3.1
For geodesically strongly convex finite sums, the proof establishes linear convergence of RSVRG through distance-to-minimizer bounds and derives an IFO complexity guarantee.
- Under L-g-smooth component functions and µ-strong g-convexity, Theorem 1 analyzes RSVRG with parameters satisfying its stated contraction conditions.
- After S outer loops, the expected squared distance contracts geometrically as E d2(xa, x∗) ≤ α^S d2(x0, x∗).
- With η = µ/(17ζL2) and m ≥ 10ζL2/µ2, the analysis obtains a contraction sufficient for linear convergence.
- L-g-smoothness converts distance convergence into objective-gap convergence, requiring log2(Ld2(x0, x∗)/ϵ) − 1 outer loops for ϵ accuracy.
- Each outer loop uses n IFO calls for the full gradient and 2m calls per variance-reduced gradient, determining the total IFO complexity.
B Proofs for Section 3.2
The proofs establish curvature-dependent convergence bounds for RSVRG and derive oracle-complexity guarantees for nonconvex, gradient-dominated, and strongly geodesically convex objectives.
- Theorem 6: Theorem 6 bounds the expected squared Riemannian gradient of the randomly selected output using a curvature-adjusted Lyapunov analysis.The proof telescopes the per-iteration inequalities across epochs and identifies the left-hand side with E[∥∇f(xa)∥2].
- Theorem 2: Theorem 2 sets curvature-dependent step-size and epoch parameters for RSVRG under geodesic smoothness and a lower sectional-curvature bound.The parameters depend on n, L, and the curvature factor ζ through α1 and α2.
- Corollary 2: Corollary 2 gives an IFO-complexity bound for achieving an ϵ-accurate solution after choosing α1 = 2/3, with separate curvature regimes.The proof combines the number of required epochs with the cost of one epoch.
- Gradient-dominated objectives: Gradient domination yields logarithmic convergence: Corollary 4 requires O((n + Lτζ1/2n2/3) log(1/ϵ)) IFO calls.Algorithm 2 recursively applies the accuracy-improvement guarantee from Theorem 3.
- Strongly g-convex objectives: For µ-strongly g-convex objectives, Corollary 5 gives O((n + µ−1Lζ1/2n2/3) log(1/ϵ)) IFO complexity.The result uses strong geodesic convexity to establish gradient domination with parameter 1/(2µ).
C Proof for Section 4.1
For the variance-reduced PCA objective on the sphere, the analysis shows that random initialization enters a neighborhood of a global optimum with high probability and that the objective is gradient dominated there.
- Theorem 4: Theorem 4 considers a symmetric matrix with eigengap δ = λ1 − λ2 and analyzes the PCA objective on the unit sphere.The Riemannian gradient is expressed using the projection onto the tangent space and the eigenbasis of A.
- Theorem 4: With probability 1 − p, random initialization lies in a Riemannian ball around a global optimum whose radius depends on the dimension and failure probability.The ball is centered at the first eigenvector.
- Theorem 4: Within that ball, the PCA objective is min{1/2ϵ2δ, 1/δ}-gradient dominated.The proof combines separate bounds for points with large and small objective suboptimality.