Source-linked AI summary
On The Convergence of Gradient Descent for Finding the Riemannian Center of Mass
Bijan Afsari, Roberto Tron, René Vidal
TL;DR
The paper asks how to guarantee convergence of constant step-size gradient descent to a global Riemannian center of mass when the cost is not globally differentiable or convex. It formulates geometric convergence conditions and proves the conjectured conditions for manifolds of constant nonnegative curvature. For arbitrary curvature, it establishes weaker convergence results and studies configuration-dependent convergence speed.
Problem
The central challenge is guaranteeing convergence to the global Riemannian center of mass when the cost function is not globally differentiable or globally convex.
Method
The paper formulates convergence conditions in terms of data spread, initialization region, step size, topology, and curvature, and uses a comparison theorem to analyze the algorithm.
Results
The conjectured convergence conditions hold for manifolds of constant nonnegative curvature, while arbitrary-curvature manifolds receive weaker convergence results.
Takeaways & Limitations
Constant step-size gradient descent can be analyzed through geometric conditions that keep iterates near the global center and within a suitable data-containing region.
Takeaways & Limitations
The paper focuses on local behavior in relatively large domains and leaves global convergence behavior for further research.
Abstract
from arXiv · showhide
We study the problem of finding the global Riemannian center of mass of a set of data points on a Riemannian manifold. Specifically, we investigate the convergence of constant step-size gradient descent algorithms for solving this problem. The challenge is that often the underlying cost function is neither globally differentiable nor convex, and despite this one would like to have guaranteed convergence to the global minimizer. After some necessary preparations we state a conjecture which we argue is the best (in a sense described) convergence condition one can hope for. The conjecture specifies conditions on the spread of the data points, step-size range, and the location of the initial condition (i.e., the region of convergence) of the algorithm. These conditions depend on the topology and the curvature of the manifold and can be conveniently described in terms of the injectivity radius and the sectional curvatures of the manifold. For manifolds of constant nonnegative curvature (e.g., the sphere and the rotation group in $\mathbb{R}^{3}$) we show that the conjecture holds true (we do this by proving and using a comparison theorem which seems to be of a different nature from the standard comparison theorems in Riemannian geometry). For manifolds of arbitrary curvature we prove convergence results which are weaker than the conjectured one (but still superior over the available results). We also briefly study the effect of the configuration of the data points on the speed of convergence.
1. Introduction and Outline
The paper studies constant step-size gradient descent for computing global Riemannian centers of mass despite cost functions that may be globally nondifferentiable and nonconvex. It develops convergence conditions involving initialization, step size, data spread, topology, and curvature, and proves the conjectured conditions in a special curvature setting.
- Problem setting: Riemannian centers of mass minimize the sum of squared geodesic distances to data points and have applications in several applied fields.Applications include computer vision, shape analysis, and medical imaging.
- Problem setting: The cost function is generally neither globally differentiable nor globally convex, and it can have irrelevant local minimizers.Nondifferentiability occurs at cut points of the data points.
- Problem setting: Convergence depends on balancing sufficient cost decrease, iterates remaining near the global center, and a step size large enough for fast convergence.The initialization must be sufficiently close to the unknown global center, while the step size must be neither too large nor too small.
- Paper objectives: The paper proposes accurate convergence conditions specifying an admissible initialization ball and step-size interval for constant step-size gradient descent.The conditions are formulated using the manifold’s topology and curvature-related quantities.
- Paper objectives: For nonnegative-curvature manifolds, the relevant step size can be simply 1, while proving the broader conjecture requires keeping all iterates inside the data-containing ball.The paper identifies this invariance challenge as central to the conjecture.
- Paper objectives: The paper also examines how data configuration affects convergence speed and discusses further research on the convergence behavior.The introduction points to cases where convergence may be very fast or very slow.
2.1. Preliminaries on the Riemannian Center of Mass and the Gradient Descent Algorithm.
The preliminaries define the geometric setting, center-of-mass objectives, convexity conditions, and intrinsic gradient descent. They establish local convergence guarantees while illustrating how large steps can reach non-global centers.
- Geometric setting: A complete Riemannian manifold is equipped with sectional-curvature bounds, exponential maps, an injectivity radius, tangent-space geometry, and geodesic distance.
- Convexity: A strongly convex set contains a unique minimizing geodesic between every pair of points, and sufficiently small metric balls provide such regions.
- Center-of-mass structure: Unlike in Euclidean or Hadamard manifolds, the squared-distance cost can be nonconvex and have nonunique centers, although sufficiently concentrated data ensure a unique center.
- Gradient descent guarantees: Within a suitable strongly convex region, gradient descent decreases the Lp cost and converges to the center when iterates continuously remain inside that region.
- Gradient descent guarantees: On the circle, step sizes in (0,1] preserve the relevant ball and guarantee convergence, whereas larger steps can enter a region containing another gradient zero.
- Gradient descent guarantees: A large step can therefore converge to a local center despite reducing the cost at every iteration, motivating conditions that keep iterates inside a controlled set.
2.2. A Conjecture: The Best Convergence Condition.
The paper proposes a convergence conjecture specifying uniform conditions on data spread, initialization, and constant step size, and argues these conditions are best possible within a natural class. It proves the conjecture for constant nonnegative curvature and establishes weaker results for arbitrary curvature.
- Conjectured condition: The conjecture requires iterates to remain in a prescribed ball while the cost decreases and the iterates converge to the global center.The initial point lies in the data-containing ball, and the step size is chosen from a curvature-, radius-, and exponent-dependent interval.
- Convergence condition class: The convergence conditions are uniform over manifolds, data sets, weights, and initial conditions within the specified geometric class.The class is parameterized by sectional-curvature bounds, the data radius, the target radius, and p.
- Optimality: The conjecture is best possible in this class because the allowable data spread reaches the injectivity-radius threshold and the convergence region is largest.Larger radii cannot guarantee convergence because the global center may lie outside the ball and the gradient may have multiple zeros.
- Optimality: Its step-size interval is optimal as a uniform guarantee: it yields the smallest uniform asymptotic convergence factor and the greatest per-iteration bound reduction.This does not imply the fastest convergence for every particular data configuration.
- Proven results: The conjecture is proved for manifolds of constant nonnegative curvature, while arbitrary-curvature results trade larger allowable regions or spread against significantly smaller step sizes.The main proof difficulty is showing that iterates continuously remain inside the relevant ball; the authors describe the available arbitrary-curvature theorems as weaker.
- Comparison with prior work: Compared with prior results, Theorem 4.1 allows radius ρ ≤ 1/3 r_cx without requiring local symmetry or nonnegative curvature, while Theorem 3.6 improves further for constant nonnegative curvature.These results are stated as improvements over Le’s convergence result.
3. Convergence on Manifolds of Constant Nonnegative Curvature (An Optimal Result)
For manifolds of constant nonnegative curvature, a new triangle-secant comparison supports the conjectured convergence guarantees: constant-step gradient descent remains in a controlled region and converges to the global center of mass.
- Main convergence theorem: Theorem 3.6 proves the conjectured convergence result for complete manifolds with constant nonnegative sectional curvature.The result covers the sphere and other constant-curvature settings, with an additional convex-hull invariance statement.
- Main convergence theorem: The iterates remain in the convex hull once an iterate enters it, extending the theorem beyond convergence to include a geometric trapping property.This property follows from the manifold convex-combination results established for constant nonnegative curvature.
- Triangle-secant comparison: The comparison result appears not to follow immediately from standard Toponogov comparison theorems and is proved directly using spherical geometry.The proof relies on the axiom of plane and spherical trigonometric identities.
- Triangle-secant comparison: The key comparison theorem shows that a geodesic secant in a positively curved triangle is longer than the corresponding Euclidean secant with matching side lengths and angles.The comparison applies to triangles in S^2 or S^n and extends to manifolds of constant curvature Δ ≥ 0.
- Main convergence theorem: For p = 2, data in B(o,ρ) with ρ ≤ r_cx and x_0 ∈ B(o,ρ), any constant step-size t ∈ (0,1] yields convergence to the global center of mass.The cost decreases at every iteration unless the iterate is already the center, and iterates remain continuously inside B(o,ρ).
- Scope: The constant-curvature argument does not directly extend to variable curvature because the triangle comparison theorem is not meaningful in that setting.The paper instead conjectures that a different comparison theorem might enable analogous results for variable nonnegative curvature.
4. Convergence results for manifolds of arbitrary curvature
For manifolds of arbitrary curvature, the paper proves weaker convergence guarantees by trading either allowable data spread or step-size for control of the iterates.
- Overview: The arbitrary-curvature results are explicitly sub-optimal relative to the conjecture because they compromise data spread or restrict the step-size.Both approaches aim to keep the iterates inside a region where the desired center is the only zero of the gradient.
- Compromising step-size: Theorem 4.2 keeps iterates inside a larger ball B(o,ρ′) by restricting the step-size, while still guaranteeing monotone cost decrease and convergence.The setting assumes ρ < ρ′ ≤ r_cx and chooses the step-size below both a curvature-based bound and an exit-time bound.
- Limitations: The step-size bounds are not optimal: finer exit-time analysis cannot improve the attainable order beyond a curvature-based inverse-Hessian bound.The paper notes that the Hessian bound itself limits improvement toward the conjectured step-size.
5. On the configuration of data points and the local rate of convergence
The section relates local convergence speed to the Hessian eigenvalue ratio near the center of mass and shows that data-point configuration and spread can make convergence fast or extremely slow.
- Local rate of convergence: The local convergence rate depends on the ratio of the smallest to largest Hessian eigenvalues near the center of mass.A smaller ratio implies slower convergence.
- Fast and slow configurations: For the orthogonal antipodal configuration, the Hessian eigenvalue ratio is approximately 1, so convergence is expected to be very fast.The configuration places two antipodal pairs in perpendicular directions.
- Fast and slow configurations: For the coincident-pair configuration on the sphere, the ratio is approximately ρcotρ and can become very small as ρ approaches π.The Hessian eigenvalues differ substantially between radial and perpendicular directions.
- Numerical illustration: On the unit sphere, experiments with step-size t_k = 1 show slower convergence for the coincident-pair configuration and for larger ρ.As ρ approaches π/2, convergence for that configuration becomes extremely slow, while the orthogonal configuration is more robust.
- Configuration effects: The center of mass can become difficult to locate when the data-point convex hull is elongated, especially when its length is large.Near ρ ≈ π/2, the center of mass is close to non-uniqueness, increasing error sensitivity and worsening convergence.
6. Concluding Remarks
The paper argues for best-possible convergence conditions, proves the conjecture in constant nonnegative curvature, and obtains weaker but improved results for variable curvature.
- Contributions: The paper seeks best-possible conditions for constant step-size gradient descent to find the Riemannian center of mass.The proposed conditions concern convergence of the algorithm to the global center.
- Contributions: The conjecture is proved for manifolds of constant nonnegative curvature using a comparison theorem about the exponential map.The comparison theorem is presented as different in nature from standard Riemannian comparison theorems.
- Contributions: For manifolds of variable curvature, Theorems 4.1 and 4.2 provide weaker convergence conditions that are still better than available results.The paper notes that extending the comparison theorem could help prove the conjecture more generally.
- Numerical illustration: Figure 3 illustrates convergence behavior for two data-point configurations on the unit sphere.It uses Algorithm 1 with step-size t_k = 1.