Geodesically Convex Optimization on Riemannian Manifolds

25 concepts20 papers2 proposals

Convexity is the bedrock of efficient optimization. In flat Euclidean space, a function is convex if the line segment connecting any two points on its graph never dips below the function itself. This simple geometric property guarantees that any local minimum is automatically a global minimum, allowing standard gradient descent algorithms to reliably find optimal solutions.

However, many essential problems in machine learning and statistics—such as fitting Gaussian mixture models, learning distance metrics, or calculating robust covariance matrices—are highly non-convex when formulated in standard Euclidean space. Their optimization landscapes are riddled with local minima and saddle points, making global optimization notoriously difficult.

But what if this non-convexity is merely an artifact of forcing our problems into a flat space? As explored by Hongyi Zhang et al. in First-order Methods for Geodesically Convex Optimization and Suvrit Sra et al. in Geometric optimisation on positive definite matrices for elliptically contoured distributions, shifting our perspective from flat vector spaces to curved surfaces—known as Riemannian manifolds—can fundamentally reshape the optimization landscape. By redefining what it means to move in a "straight line," non-convex Euclidean problems can be transformed into beautifully convex ones.

From Straight Lines to Geodesics

To understand why this works, consider the task of finding the shortest path between two distant cities on Earth. A Euclidean straight line would tunnel directly through the planet's core. However, an inhabitant constrained to the Earth's surface must travel along a curved path—specifically, a great-circle arc. On a Riemannian manifold, these shortest paths along the curved surface are called geodesics.

Victor-Emmanuel Brunel formalizes this concept in Geodesically convex M-estimation in metric spaces: a function is geodesically convex if, for any two points in the space, the function's value along the geodesic connecting them stays below the secant line.

Crucially, geodesic convexity preserves the most vital guarantee of classical optimization: every local minimum is a global minimum. By respecting the intrinsic geometry of the parameter space, optimization algorithms can navigate complex landscapes without getting trapped. For instance, Jing Wang et al. demonstrate in A Geodesic-Based Riemannian Gradient Approach to Averaging on the Lorentz Group that algorithms operating along intrinsic geodesic paths converge significantly faster and more reliably than methods that ignore this geometry and operate in the ambient Euclidean space.

This geometric perspective applies across a wide variety of structured spaces:

The Geometry of Positive Definite Matrices

The most prominent and practical application of this paradigm is optimization over the manifold of Symmetric Positive Definite (SPD) matrices. SPD matrices are ubiquitous in machine learning, serving as covariance matrices, kernel functions, and structured parameter spaces.

In Euclidean space, the set of SPD matrices forms an open cone where operations involving matrix inverses or determinants frequently destroy convexity. However, when equipped with an appropriate Riemannian metric—such as the Affine-Invariant metric or the Bures-Wasserstein geometry studied by Andi Han et al. in On Riemannian Optimization over Positive Definite Matrices with the Bures-Wasserstein Geometry—the space becomes a curved manifold where many statistical objectives reveal their hidden geodesic convexity. As formalized by Suvrit Sra et al. in Conic Geometric Optimization on the Manifold of Positive Definite Matrices, this transformation enables the guaranteed discovery of global optima for complex statistical estimation tasks.

This geometric insight has unlocked global optimality guarantees across several domains:

  • Gaussian Mixture Models (GMMs): Parameter estimation for GMMs has long been dominated by the Expectation-Maximization (EM) algorithm, which can get trapped in poor local optima. Reshad Hosseini et al. showed in Matrix Manifold Optimization for Gaussian Mixtures that augmenting input data vectors with a constant term transforms the non-convex log-likelihood into a geodesically convex function on the SPD manifold, allowing direct gradient-based methods to reliably find global optima.
  • Robust Covariance Estimation: Computing Tyler’s M-estimator is a non-convex, non-smooth problem in Euclidean space. By proving the geodesic strong convexity of the objective function, William Cole Franks provided the first rigorous, non-asymptotic linear convergence guarantees in Rigorous Guarantees for Tyler's M-Estimator via Quantum Expansion. To make this computationally practical, Lior Danon et al. developed Frank-Wolfe-based algorithms using geodesic gradients in Frank-Wolfe-based Algorithms for Approximating Tyler's M-estimator, achieving nearly linear runtime per iteration due to superior conditioning.
  • Metric Learning and Data Averaging: In metric learning, Antoine Collas et al. demonstrated in Robust Geometric Metric Learning that formulating cost functions as geodesically convex on the Riemannian manifold ensures that local minima are global minima, providing exceptional resilience against mislabeled training data. Similarly, Florian Yger et al. leveraged this property in Geodesically-convex optimization for averaging partially observed covariance matrices to robustly average incomplete covariance matrices without falling into local traps.

This framework also extends to theoretical computer science. Zeyuan Allen-Zhu et al. utilized geodesically convex optimization over matrix spaces in Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing to design polynomial-time algorithms for the operator scaling problem, a core challenge in invariant theory and polynomial identity testing.

Bypassing the Riemannian Overhead

If geodesically convex optimization offers such powerful guarantees, why isn't it the default choice for every non-convex problem? The primary bottleneck is computational overhead. Standard Riemannian optimization algorithms require computing expensive operations—such as exponential maps, matrix logarithms, or vector transports—at every iteration to ensure that updates remain strictly on the curved manifold.

To bypass this costly overhead, recent work has uncovered a remarkable phenomenon: hidden dual structures that bridge flat and curved geometries.

In Global optimality for Euclidean CCCP under Riemannian convexity, Melanie Weber et al. revealed that certain complex objectives possess a dual nature: they are simultaneously geodesically convex on a Riemannian manifold and can be expressed as a Difference-of-Convex (DC) function in flat Euclidean space. By linearizing the concave component of the Euclidean DC structure, the authors showed that the classical Euclidean Convex-Concave Procedure (CCCP) can be applied directly. Because the underlying objective is geodesically convex, this purely Euclidean algorithm is guaranteed to converge to the global optimum, completely avoiding expensive Riemannian manifold operations.

Building on this insight, Andrew Nicholas Cheng et al. extended this framework to regularized problems in Structured Regularization on the SPD Manifold. By selecting regularizers that simultaneously satisfy geodesic convexity and a Euclidean DC structure, they enable the use of fast, standard Euclidean iterative algorithms while fully retaining the global optimality guarantees provided by the manifold's curved geometry.

Key Foundational Work

Geometric optimisation on positive definite matrices for elliptically contoured distributions (2013) — contributed 1 concept elements to this direction.
On the Quotient Representation for the Essential Manifold (2014) — contributed 1 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_geodesic_convexity_f1e885fc,
  title = {geodesic convexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/geodesic-convexity/rdr_f1e885fcc4be4c2982ea72b481a25305},
  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_f1e885fc_v1,
  title = {geodesic convexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/geodesic-convexity/rdr_f1e885fcc4be4c2982ea72b481a25305/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake