Geodesic Convexity for Global Optimization on Riemannian Manifolds

This direction is split into other directions: geodesic convexity. Its last version stays readable and citable here.

Version 1 of 156 papers93 conceptsfrozen 2026-10-04

In the standard toolkit of optimization, convexity is the "gold standard." If a function is convex, we are guaranteed that any local minimum is a global minimum, allowing simple gradient-based algorithms to find optimal solutions reliably. However, this guarantee traditionally relies on "Flatland"—the assumption that our variables live in a Euclidean vector space where "straight lines" are linear interpolations.

Many modern problems in machine learning and statistics do not fit this mold. Data often lives on curved surfaces: the space of rotations, the manifold of positive-definite matrices, or hyperbolic spaces representing hierarchies. In these domains, functions that appear hopelessly non-convex in Euclidean coordinates often reveal a hidden, tractable structure called geodesic convexity.

Redefining the Straight Line

The core intuition behind this research direction is that convexity is not an intrinsic property of a function alone, but a relationship between a function and the geometry of the space it inhabits. As Nisheeth K Vishnoi explains in Geodesic Convex Optimization: Differentiation on Manifolds, Geodesics, and Convexity, we can generalize convexity by replacing linear segments with geodesics—the shortest paths on a Riemannian manifold.

A function is geodesically convex if, for any two points on the manifold, the function's value along the geodesic connecting them stays below the average of the values at the endpoints. This shift allows us to solve problems that are "Euclidean non-convex" by simply changing our perspective on what "straight" means. Patrick M. Wensing argues in Contraction Analysis of Geodesically Convex Optimization that by mapping a non-convex landscape to a curved manifold with a suitable metric, we can extend standard optimization guarantees to previously intractable problems.

The Manifold of Positive Definite Matrices

The most successful application of this idea is on the manifold of Symmetric Positive Definite (SPD) matrices. Many statistical tasks, such as estimating covariance or calculating the mean of multiple matrices, are non-convex in flat space but perfectly well-behaved in the "log-determinant" or "affine-invariant" geometries of the SPD cone.

Suvrit Sra and Reshad Hosseini have demonstrated this across several domains:

This geometric insight extends to robust statistics as well. William Cole Franks proved in Rigorous Guarantees for Tyler's M-Estimator via Quantum Expansion that establishing geodesic strong convexity on the SPD manifold allows for linear convergence rates in robust estimation.

Transforming Landscapes via Geometry

Sometimes, a problem is not naturally geodesically convex, but can be made so through clever reparameterization. A striking example is found in hyperbolic space, which is ideal for embedding hierarchical data like social networks or taxonomies.

Standard hyperbolic classifiers often struggle with non-convexity. However, Xiran Fan, Chun-Hao Yang, and Baba C. Vemuri introduced HoroSVM in Horospherical Decision Boundaries for Large Margin Classification in Hyperbolic Space. By using horospheres (surfaces of constant Busemann function value) as decision boundaries instead of geodesics, they transform the classification task into a geodesically convex problem. This ensures that Riemannian gradient descent converges to a global optimum, bypassing the local minima that plague traditional hyperbolic models.

Automated Discovery and Disciplined Programming

As the field matures, the focus is shifting from manual proofs of convexity to automated verification. Identifying geodesic convexity is notoriously difficult because it depends on the interaction between the function and the metric tensor.

To address this, Melanie Weber and colleagues introduced Disciplined Geodesically Convex Programming (DGCP) in Disciplined Geodesically Convex Programming. Much like Disciplined Convex Programming (DCP) revolutionized Euclidean optimization (via tools like CVX), DGCP provides a formal grammar and a library to certify "hidden" convexity in non-convex problems. This allows researchers to verify global optimality for complex expressions on manifolds like the SPD cone without needing to derive the curvature properties from scratch.

Why It Works: The Local-to-Global Principle

The power of this approach lies in the Local-to-Global Principle. As explored by Juan-Pablo Ortega and Petre Birtea in Metric convexity in the symplectic category, if a space has the right metric properties (like being a complete length space), local convexity-like behavior along geodesics ensures global weak convexity.

By choosing a metric that "straightens" the function's contours, we are essentially warping the space so that the gradient always points toward the global minimum. This is why Melanie Weber and Suvrit Sra found in Global optimality for Euclidean CCCP under Riemannian convexity that even standard Euclidean algorithms like the Convex-Concave Procedure (CCCP) can achieve global optimality if the underlying problem is geodesically convex. The geometry provides the "hidden" structure that prevents the algorithm from getting stuck in what would otherwise be a local trap.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_geodesic_convexity_for_global_optimizati_7d55a9e3,
  title = {Geodesic Convexity for Global Optimization on Riemannian Manifolds},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/geodesic-convexity-for-global-optimization-on-riemannian-manifolds/rdr_7d55a9e37fea46ebb2ec23a11abbb617},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_geodesic_convexity_for_global_optimizati_7d55a9e3_v1,
  title = {Geodesic Convexity for Global Optimization on Riemannian Manifolds},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/geodesic-convexity-for-global-optimization-on-riemannian-manifolds/rdr_7d55a9e37fea46ebb2ec23a11abbb617/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}