GEORCE: A Fast New Control Algorithm for Computing Geodesics

Frederik Möbius Rygaard, Søren HaubergarXiv 2025 · DOI · arXiv

TL;DR

GEORCE is a new algorithm that reformulates the search for geodesics (shortest paths) on curved surfaces as an optimal control problem. It combines the global stability of gradient descent with the lightning-fast local convergence of Newton’s method—all without requiring expensive second-order derivatives—making it significantly faster and more accurate than standard optimizers for high-dimensional manifolds.

What Problem Does This Paper Address?

In fields ranging from robotics and medical imaging to generative AI, we often need to find the "straightest" path between two points on a non-Euclidean surface, known as a geodesic. Mathematically, this is a Boundary Value Problem (BVP) that is notoriously difficult to solve.

Existing methods generally fall into two camps:

  1. Shooting methods: These try to "aim" an initial velocity to hit a target point, but they are numerically brittle and often fail to converge.
  2. Energy minimization: These use standard solvers like ADAM or BFGS to minimize a path's energy functional. However, these solvers often scale poorly with the manifold's dimension, converge slowly, or get stuck in local minima.

The authors identify a clear gap: we lack a solver that is simultaneously robust, fast in high dimensions, and easy to implement without calculating complex second-order derivatives (Hessians).

Methods

The authors introduce GEORCE (GEodesic Optimization RalgoRithm using Control tEchniques). The core innovation is re-framing the discrete energy functional of a path as a discrete-time optimal control problem.

Key technical highlights include:

  • Decomposition: By applying Pontryagin’s Maximum Principle, the authors decompose the global path optimization into a sequence of strictly convex subproblems.
  • The "Iterative Trick": In each iteration, the algorithm fixes the metric tensor and its derivatives based on the current path estimate. This transforms a complex non-linear system into a system of linear equations that can be solved explicitly and efficiently.
  • Convergence Properties: The paper proves that GEORCE achieves global convergence (it will find a local minimum from almost any starting point) and quadratic local convergence (it speeds up dramatically as it nears the solution), similar to Newton's method but using only first-order information.
  • Finsler Extension: Unlike many solvers restricted to Riemannian geometry, GEORCE naturally extends to Finsler manifolds, where distances might not be symmetric (e.g., traveling through a "wind field" where going from A to B is harder than B to A).

Datasets

The authors evaluated GEORCE across an extensive range of benchmarks:

  • Mathematical Manifolds: $n$-spheres, $n$-ellipsoids, tori, hyperbolic spaces, and "egg-tray" surfaces.
  • Information Geometry: Manifolds of probability distributions (Gaussian, Fréchet, Cauchy, and Pareto) equipped with the Fisher-Rao metric.
  • Generative Models: Latent spaces of Variational Autoencoders (VAEs) trained on the MNIST (handwritten digits), SVHN (street view house numbers), and CelebA (celebrity faces) datasets.

Key Insights and Ideas

  • Control Theory as an Optimizer: The "aha moment" is realizing that the velocity vectors along a geodesic act exactly like "controls" in a dynamical system. This allows the use of powerful tools from control theory to solve geometry problems.
  • Hessian-like Speed without the Hessian: GEORCE manages to mimic the behavior of a sparse Newton method. By exploiting the specific structure of the geodesic equations, it achieves quadratic convergence using only the gradient of the metric.
  • Robustness to Complexity: While standard solvers like BFGS struggle as the number of grid points ($T$) or dimensions ($d$) increases, GEORCE’s complexity scales linearly with $T$ and cubically with $d$, making it highly efficient for complex models.

Key Results

  • Speedup: On a 1000-dimensional sphere ($S^{1000}$), GEORCE converged in roughly 15 minutes on a CPU, whereas BFGS failed to finish within 24 hours.
  • Accuracy: GEORCE consistently found paths with lower Riemannian length compared to ADAM and BFGS, particularly on "unruly" surfaces like the egg-tray manifold or VAE latent spaces.
  • Generative Modeling: When interpolating between faces in the CelebA VAE, GEORCE produced smoother transitions and reached the solution in significantly fewer iterations than baseline optimizers.
  • Finsler Performance: The algorithm successfully computed geodesics for "microswimmers" subject to external force fields, demonstrating its versatility beyond standard Riemannian geometry.

Limitations and Future Work

  • Matrix Inversions: The algorithm requires inverting the metric matrix at every grid point in every iteration. While $O(d^3)$ is better than many alternatives, it could still be a bottleneck for extremely high-dimensional charts (e.g., $d > 10,000$).
  • Local Chart Constraint: The current derivation assumes the entire geodesic lies within a single coordinate chart. While the authors suggest this can be mitigated by switching charts mid-calculation, they haven't implemented a multi-chart version yet.
  • Future Directions: The authors suggest investigating adaptive step-size schemes and more efficient ways to approximate the inverse metric to further boost performance in high-dimensional settings.

Summary updated

Abstract

Computing geodesics for Riemannian manifolds is a difficult task that often relies on numerical approximations. However, these approximations tend to be either numerically unstable, have slow convergence, or scale poorly with manifold dimension and number of grid points. We introduce a new algorithm called GEORCE that computes geodesics in a local chart via a transformation into a discrete control problem. We show that GEORCE has global convergence and quadratic local convergence. In addition, we show that it extends to Finsler manifolds. For both Finslerian and Riemannian manifolds, we thoroughly benchmark GEORCE against several alternative optimization algorithms and show empirically that it has a much faster and more accurate performance for a variety of manifolds, including key manifolds from information theory and manifolds that are learned using generative models.
BibTeX
@misc{rygaard2025georce,
  author = {Frederik Möbius Rygaard and Søren Hauberg},
  title = {{GEORCE: A Fast New Control Algorithm for Computing Geodesics}},
  year = {2025},
  eprint = {2505.05961},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.05961},
  howpublished = {arXiv},
}
Figure