Source-linked AI summary
First-order Methods for Geodesically Convex Optimization
Hongyi Zhang, Suvrit Sra
TL;DR
Geodesically convex optimization is less developed than Euclidean convex optimization, especially regarding global complexity guarantees on nonlinear spaces. This paper develops geometric tools and analyzes deterministic and stochastic first-order methods on Hadamard manifolds, deriving bounds across smoothness and strong-convexity settings while exposing curvature dependence. The resulting framework provides global iteration-complexity upper bounds for general g-convex optimization, though some curvature dependencies may be pessimistic.
Problem
Global complexity analysis for first-order algorithms in general geodesically convex optimization remains limited compared with Euclidean convex optimization.
Method
The paper develops geometric inequalities and applies them to deterministic and stochastic gradient and subgradient methods on Hadamard manifolds.
Results
The paper proves iteration-complexity upper bounds for smooth, nonsmooth, and strongly g-convex optimization, with convergence rates depending on sectional curvature.
Takeaways & Limitations
The analysis extends first-order complexity results from Euclidean settings to general g-convex optimization on Hadamard manifolds.
Takeaways & Limitations
The curvature dependence in some bounds may be pessimistic, and tighter dependence may require refined analysis because distances to the minimizer shrink.
Abstract
from arXiv · showhide
Geodesic convexity generalizes the notion of (vector space) convexity to nonlinear metric spaces. But unlike convex optimization, geodesically convex (g-convex) optimization is much less developed. In this paper we contribute to the understanding of g-convex optimization by developing iteration complexity analysis for several first-order algorithms on Hadamard manifolds. Specifically, we prove upper bounds for the global complexity of deterministic and stochastic (sub)gradient methods for optimizing smooth and nonsmooth g-convex functions, both with and without strong g-convexity. Our analysis also reveals how the manifold geometry, especially \emph{sectional curvature}, impacts convergence rates. To the best of our knowledge, our work is the first to provide global complexity analysis for first-order algorithms for general g-convex optimization.
1. Introduction
The paper develops global iteration-complexity analysis for first-order methods solving smooth and nonsmooth geodesically convex problems on Hadamard manifolds. It introduces geometric tools and studies how sectional curvature enters convergence guarantees.
- Motivation: Geodesic convexity extends convexity from vector spaces to nonlinear metric spaces, offering a setting for globally optimizable mathematical models.The paper motivates this extension by noting convexity’s role in polynomial runtimes and stable numerical methods.
- Scope: The paper analyzes deterministic and stochastic first-order methods for nonsmooth, smooth, and strongly g-convex optimization on Hadamard manifolds.The settings include both gradient and subgradient methods, with stochastic objectives represented as expectations.
- Technical challenge: Iteration-complexity analysis requires new geometric tools because non-Euclidean trigonometry and Euclidean linearization do not directly transfer.The paper identifies these geometric hurdles as obstacles to obtaining global complexity bounds.
- Novelty: The analysis extends prior Euclidean and asymptotic manifold results, providing global complexity results for general g-convex optimization without requiring line search.The paper positions these as the first such global complexity analyses to the authors’ knowledge.
- Technical contributions: The paper develops a trigonometric distance inequality for Alexandrov spaces with curvature bounded below, applicable beyond g-convex problems on Riemannian manifolds.This inequality is presented as a key contribution for analyzing optimization algorithms in curved spaces.
- Results: For g-convex optimization on Hadamard manifolds, the paper proves non-asymptotic iteration-complexity upper bounds for several existing first-order algorithms.The reported results cover multiple smoothness, convexity, and stochasticity settings summarized in Table 1.
2. Background
The paper establishes metric and Riemannian geometry concepts used to generalize optimization beyond vector spaces. It defines geodesic convexity and related function classes, while highlighting curvature and parallel transport as analysis-relevant structures.
- 2.1. Metric Geometry: Metric spaces use a distance satisfying positivity, symmetry, and the triangle inequality; geodesic spaces additionally connect every pair of points by a geodesic.Unique geodesicity means that this connecting geodesic is unique.
- 2.1. Metric Geometry: Geodesic triangles and comparison triangles in constant-curvature planes provide the geometric objects used to relate distances and angles through curvature bounds.Alexandrov spaces impose local comparison inequalities, and Toponogov’s theorem relates triangle angles and lengths to comparison triangles.
- 2.2. Riemannian Geometry: A manifold supplies tangent spaces and an exponential map that sends a tangent vector at x to the endpoint of a geodesic starting at x.The exponential map is defined through a geodesic whose initial velocity is the mapped tangent vector.
- 2.2. Riemannian Geometry: Riemannian metrics provide inner products on tangent spaces, while parallel transport moves vectors between tangent spaces and preserves inner products.Sectional curvature describes the geometry of two-dimensional subspaces, which are locally spherical, Euclidean, or hyperbolic according to its sign.
- 2.3. Function Classes on a Riemannian Manifold: The paper studies geodesic convexity together with strong convexity, Lipschitzness, and smoothness on Riemannian manifolds.Smoothness compares gradients at different points using parallel transport; the function may be nonsmooth, Lipschitz, or strongly g-convex depending on the setting.
3. Convergence Rates of First-order Methods
The paper develops global complexity analysis for deterministic and stochastic first-order methods on Hadamard manifolds, overcoming geometric obstacles absent in Euclidean spaces. The resulting rates depend on sectional curvature across nonsmooth, smooth, and strongly g-convex settings.
- Geometric hurdles: Non-asymptotic analysis is difficult because Euclidean trigonometric identities and linearization techniques do not directly extend to nonlinear spaces.The Euclidean law of cosines does not hold in nonlinear spaces, and there is no trivial analogue of a linear function for proximal-style reasoning.
- Geometric tools: A trigonometric distance bound for Alexandrov spaces with curvature bounded below provides the missing tool for analyzing manifold optimization rates.When specialized to Hadamard manifolds, the bound reduces to the analysis used in earlier Riemannian work while requiring no manifold structure in its proof.
- Curvature dependence: Setting sectional curvature κ = 0 recovers Euclidean convergence rates, whereas κ < 0 can make the algorithms converge more slowly.The upper bounds depend linearly on ζ(κ, D), though this dependence may be pessimistic for strongly convex problems because iterates approach the minimizer.
- Nonsmooth optimization: Nonsmooth g-convex methods achieve curvature-dependent rates: O(1/t) for deterministic and stochastic strongly g-convex optimization, with analogous bounds for general g-convex optimization.The results cover both deterministic and stochastic subgradient methods on Hadamard manifolds.
4. Experiments
The experiments evaluate deterministic and stochastic first-order methods on matrix Karcher mean problems using normalized positive semidefinite matrix datasets. They compare performance across dataset sizes and condition numbers.
- Problem setup: The matrix Karcher mean minimizes the sum of squared Riemannian distances over positive definite matrices.The problem is nonconvex in Euclidean space but geometrically strongly convex, motivating geodesically convex optimization.
- Algorithms: The stochastic update samples one matrix index uniformly at random from the dataset.The stepsize sequence is chosen according to the relevant theoretical constants.
- Algorithms: The comparison includes gradient descent, stochastic gradient for smooth functions, and stochastic subgradient for strongly convex functions.The algorithms use stepsizes based on smoothness, domain diameter, gradient variance, or strong convexity estimates.
- Experimental design: The datasets contain 100 × 100 normalized random PSD matrices, with N ∈ {10^2, 10^3} and condition number Q ∈ {10^2, 10^8}.Initialization uses the arithmetic mean of each dataset, and performance is measured by objective suboptimality across dataset passes.
5. Discussion
The paper establishes first-order complexity results for geodesically convex optimization on Hadamard manifolds while identifying unresolved directions for acceleration, variance reduction, and retractions. Experiments report the predicted convergence patterns for the compared methods.
- Discussion: The paper develops a trigonometric distance bound and iteration-complexity upper bounds for several first-order algorithms on Hadamard manifolds.These are presented as the paper’s two main contributions and, to the authors’ knowledge, the first such global analyses for general g-convex optimization.
- Future directions: Whether Nesterov’s accelerated gradient descent has a nonlinear-space counterpart remains unresolved because an analogous proximal projection was not found.The paper leaves open whether a different analysis is needed or such counterparts do not exist.
- Future directions: Variance-reduced stochastic methods are proposed as a direction that may achieve faster convergence than naive incremental methods on Hadamard manifolds.The paper states this as a hypothesis rather than an established result.
- Future directions: The convergence-rate effect of replacing exponential maps with cheaper retractions remains an open theoretical and practical question.The issue matters because retractions are often preferable computationally in applications.
- Experiments: Figure 2 validates linear convergence for GD, asymptotic O(1/t) convergence for SGD-sm, and O(1/t) convergence for SGD-st.The comparison varies dataset size n and condition number Q.
Appendix A. Proof of Lemma 1
The appendix proves a comparison bound for geodesic triangles in hyperbolic space by reducing the claim to a one-variable monotonicity argument. The proof then transfers the result across curvature scalings.
- Proof: The initial case c = 0 is handled directly using g(b, 0) = cosh(b) and the matching second derivative.The positive-c case is treated separately with the auxiliary-variable argument.
- Hyperbolic comparison: The scalar analysis studies h_1(u), identifies its minimum, and uses monotonicity in sin^2 A to reduce the worst case to sin^2 A = 1.The resulting bound is then converted back through the hyperbolic cosine relation.
- Hyperbolic comparison: For hyperbolic triangles of curvature −1, the argument uses the hyperbolic law of cosines and a lower bound involving c^2(x + sin^2 A).The proof reduces the target inequality to a scalar inequality in x and the angle A.
- Proof: The proof defines h_c(x) as the difference between two comparison functions and applies a monotonicity lemma to show h_c(x) ≤ 0.This establishes the desired comparison inequality for all nonnegative side-length arguments.
- Curvature scaling: The curvature-κ corollary follows by rescaling the curvature-−1 hyperbolic triangle and applying the corresponding law of cosines.The appendix explicitly treats κ < 0 in this transfer step.