Research map / Optimization / Nonconvex and smooth optimization
Convergence and Trade-Offs in Riemannian Gradient Descent and Riemannian Proximal Point
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes Riemannian gradient descent and inexact Riemannian proximal point in g-convex optimization, proving iterates stay in a quantified ball around the optimizer and giving non-asymptotic rates including for positive curvature and min-max problems.
Problem
Convergence of Riemannian gradient descent and proximal point is often analyzed by assuming iterates stay in a bounded set or that smoothness/strong convexity hold in unspecified regions, leaving rates unquantified and creating circular step-size dependencies, especially when positive curvature is p
Approach
Shows that RGD and RPPA iterates naturally remain in a ball around a minimizer whose radius depends on the initial distance and curvature constants, so rates can be fully quantified without a priori bounded-iterate assumptions; builds an inexact RPPA (RIPPA) implementable with first-order subroutines (composite RGD, PRGD, RGDA).
Key results
- RGD with step 1/L keeps iterates in a ball of radius O(zeta_R R) around the optimizer and gives O(zeta_R^2 L R^2/eps) rate for g-convex smooth functions (hyperbolic space: O(LR^2/eps)).
- RIPPA attains O(R^2/(eta eps)) rate for g-convex functions and keeps iterates within sqrt(2) R of the optimizer, with linear rate under strong convexity.
- Experiments on Karcher means show RIPPA is competitive and distances to the optimizer decrease monotonically in practice across tested settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use RGD with step size 1/L instead of RGD with step size 1/(Lζ₍O(R)₎) (ablation) | RGD for the Karcher mean in hyperbolic space · Karcher mean on hyperbolic space | function value | Helped |
| replace RGD with RIPPA | Karcher mean optimization · Karcher mean on symmetric positive definite matrices | function value | Helped |
| replace RGD with RIPPA | Karcher mean optimization · Karcher mean on hyperbolic space | function value | Hurt |
| change RGD step size from 1/L to 1/(Lζ₍O(R)₎) (ablation) | RGD for Karcher mean · Karcher mean on symmetric positive definite matrices | function value | No clear effect |
| use RIPPA rather than either RGD step-size variant | Karcher mean optimization across tested manifolds · Karcher mean | function value | Mixed |
| use RGD or RIPPA in the tested settings | Riemannian optimization · Karcher mean experiments | distance to optimizer | Helped |
| use step sizes that are too large | RGD and tested algorithms · Karcher mean experiments | convergence | Hurt |
| use CRGD rather than PRGD to implement RIPPA's proximal criterion (ablation) | RIPPA implementation on Hadamard manifolds · Smooth geodesically convex minimization | gradient oracle queries: Õ(1) vs. Õ(ζ_R²) | Helped |
| implement min-max RIPPA with RGDA without requiring prior knowledge of R | RIPPA-RGDA · Smooth geodesically convex-concave min-max on Hadamard manifolds | gradient oracle queries: Õ(ζ_R⁴) | Hurt |
Surprising findings
- Empirically, distance to the optimizer decreased monotonically for all tested algorithms, suggesting the theoretical iterate bounds may be loose.
- RPPA converges at rates matching the Euclidean-like analysis despite RPPA being equivalent to RGD on the Moreau envelope, which can be non-g-convex under positive curvature.
Limitations
- Some variants (e.g., RIPPA-CRGD) have implementation subproblems that may be hard to solve efficiently, and the efficient variants have worse gradient complexity or iterate bounds.
- Min-max RIPPA with RGDA requires Hadamard manifolds and has a worse dependence on zeta (power 4).
- The iterate bound for RGD with step 1/L is only for a set depending on curvature, and the best-of-all-worlds efficient method remains open.
Experimental setup
Benchmarks: Karcher mean in hyperbolic space Karcher mean on symmetric positive definite matrices
Metrics: function value gap distance to optimizer
Baselines: Riemannian gradient descent with step 1/L Riemannian extragradient RGDA projected RGD
Builds on: Riemannian gradient descent Riemannian proximal point algorithm Riemannian gradient descent-ascent
Closest papers by meaning
- Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms (ICML 2024 · similarity 0.91)
- Acceleration via silver step-size on Riemannian manifolds with applications to Wasserstein space (NeurIPS 2025 · similarity 0.89)
- An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds (NeurIPS 2025 · similarity 0.88)
- SERENA: A Unified Stochastic Recursive Variance Reduced Gradient Framework for Riemannian Non-Convex Optimization (ICML 2025 · similarity 0.88)
- Adaptive Proximal Gradient Method for Convex Optimization (NeurIPS 2024 · similarity 0.88)
- Adaptive Riemannian ADMM for Nonsmooth Optimization: Optimal Complexity without Smoothing (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.