Curvature Dependent Convergence in Riemannian Optimization

36 concepts29 papers1 proposal

In standard machine learning, we treat convexity as a superpower. If an optimization problem is convex, we know we can solve it efficiently using standard first-order methods like gradient descent. However, this guarantee almost always assumes our variables live in a flat Euclidean space.

When data naturally belongs to a curved surface—such as the space of rotations, hyperbolic spaces for hierarchical embeddings, or symmetric positive definite (SPD) matrices—we must transition to Riemannian optimization. On a smooth manifold, straight lines are replaced by geodesics (the shortest paths along the surface).

While the core algorithmic structures of gradient descent carry over to manifolds, their convergence rates do not translate cleanly. Instead, the intrinsic geometry of the space—specifically its sectional curvature—acts as a fundamental constraint, scaling factor, and sometimes an absolute barrier to optimization speed.

Sectional Curvature as a Convergence Penalty

To understand why geometry alters convergence, consider how we measure distance. In flat space, the distance between updates is straightforwardly governed by linear algebra. On a manifold, curvature distorts distance.

As established by Hongyi Zhang et al. in First-order Methods for Geodesically Convex Optimization, the convergence rates for optimization on manifolds are directly scaled by a factor dependent on the sectional curvature and the diameter of the domain. Rather than altering the foundational rate (e.g., $O(1/k)$), the geometry acts as a constant penalty on performance.

This geometric tax becomes explicit when analyzing iteration complexity. The authors of Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds demonstrated that sectional curvature serves as a core parameter in determining how many steps an algorithm requires to reach optimality. When navigating a curved landscape, the flatness or bending of the space directly dictates how much an optimization trajectory is distorted, impacting everything from escaping saddle points to reaching global minima (Criscitiello et al., 2019; Sun et al., 2019).

The Sign of Curvature: Expansion vs. Compression

The practical impact of this geometric penalty depends entirely on whether the manifold's curvature is negative or non-negative.

Negative Curvature (Hyperbolic Spaces)

In a negatively curved space (like a saddle or a hyperbolic plane), geodesics flare outward and diverge exponentially fast. This behavior introduces severe spatial uncertainty. If an algorithm makes a tiny error in estimating a gradient direction, that angular error translates into a massive spatial discrepancy as the algorithm steps along the geodesic.

Because of this rapid divergence, Christopher Criscitiello et al. proved a fundamental "no-go" theorem in Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles: global Nesterov-style acceleration is fundamentally impossible in the presence of negative curvature, even with perfect, noise-free information. The underlying geometry acts as a physical barrier, establishing a lower bound on optimization complexity that scales inherently with both the domain radius and the magnitude of the negative curvature (Criscitiello et al., 2023).

Non-Negative Curvature (Spherical and Bures-Wasserstein Spaces)

Conversely, in spaces with non-negative sectional curvature (like spheres), geodesics bow toward each other or remain tightly bounded. This geometric compression works in favor of optimization.

As shown by Andi Han et al. in On Riemannian Optimization over Positive Definite Matrices with the Bures-Wasserstein Geometry, choosing a manifold geometry with non-negative curvature allows algorithms to leverage tighter trigonometric distance bounds. These tighter bounds directly improve convergence constants, enabling stochastic and first-order methods to achieve efficiency levels that match or closely parallel standard Euclidean optimization (Zhang et al., 2016).

The Obstacle to Acceleration

In Euclidean optimization, acceleration is achieved by combining the current gradient step with a momentum step from the previous iteration. On a manifold, however, these two vectors live in different tangent spaces. To combine them, one vector must be moved to the other's tangent space via a process called parallel transport.

Because the space is curved, parallel transporting a vector over a distance distorts its direction and magnitude. David Martínez-Rubio et al. show in Accelerated Riemannian Optimization: Handling Constraints to Bound Geometric Penalties that this distance distortion creates a geometric penalty that scales with the diameter of the region explored. Over large distances, these nonlinearities accumulate, meaning acceleration guarantees often only hold within a restricted local neighborhood where the curvature has not yet overwhelmed the optimization dynamics (Zhang et al., 2018).

To stabilize accelerated trajectories, researchers have proposed two main paradigms:

  1. Curvature-Aware Friction: By analyzing acceleration through a continuous-time lens, the authors of A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization demonstrated that the friction or damping term in the optimization dynamics must be scaled according to the sectional curvature. Negatively curved manifolds require increased friction to counteract the natural divergence of geodesics and keep the trajectory from destabilizing (Duruisseaux et al., 2021).
  2. Implicit Updates: Rather than trying to correct for the geometric tax explicitly, Christophe Roux et al. developed implicit optimistic methods in Implicit Riemannian Optimism with Applications to Min-Max Problems. By utilizing implicit steps, they successfully eliminate the explicit dependence on worst-case curvature constants, allowing algorithms to match Euclidean efficiency bounds even in curved domains.

Curvature-Aware Algorithmic Design

Because curvature alters the underlying space so fundamentally, standard optimization heuristics cannot be applied blindly. They must be modified to be curvature-aware:

  • Adaptive Step Sizes: In adaptive gradient methods, step sizes must be dynamically scaled based on the sectional curvature to prevent overshooting. In highly curved environments, standard learning rates can cause algorithms to oscillate or diverge entirely (Park et al., 2026; Hino et al., 2019).
  • Gradient Estimation Variance: When exact gradients are unavailable, black-box optimization suffers heavily from curvature. As detailed by Shaocong Ma et al. in Riemannian Zeroth-Order Gradient Estimation with Structure-Preserving Metrics for Geodesically Incomplete Manifolds, zeroth-order gradient estimation error is highly sensitive to sectional curvature, with higher curvature leading to increased variance and degraded reliability.
  • Distributed Consensus: In decentralized settings where multiple agents must agree on a manifold, high curvature increases the complexity of reaching a consensus. Xiuheng Wang et al. have shown that high or irregular curvature decreases adaptation speed and necessitates smaller step sizes, forcing a strict trade-off between the speed of agreement and the intrinsic curviness of the shared space (Wang et al., 2024; Wang et al., 2025).

Key Foundational Work

Average consensus on Riemannian manifolds with bounded curvature (2011) — contributed 2 concept elements to this direction.
On The Convergence of Gradient Descent for Finding the Riemannian Center of Mass (2012) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_curvature_dependent_convergence_eca461d5,
  title = {curvature-dependent convergence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curvature-dependent-convergence/rdr_eca461d50c1f416297e8071f167e377a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_curvature_dependent_convergence_eca461d5_v1,
  title = {curvature-dependent convergence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curvature-dependent-convergence/rdr_eca461d50c1f416297e8071f167e377a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake