Efficient Riemannian Optimization via Manifold Retractions

103 concepts74 papers1 proposal

In standard machine learning, optimization takes place in flat, unconstrained Euclidean space. However, many modern problems force parameters to satisfy strict structural constraints. For example, neural network weights may be required to be orthonormal to stabilize training, data embeddings might be mapped to hyperbolic spaces to capture hierarchical structures, or optimization might occur over low-rank or doubly stochastic matrices.

Instead of treating these constraints via complex penalty functions or repeated, expensive projections, we can view the constraint set as a smooth, curved surface: a Riemannian manifold.

Optimizing directly on a manifold requires a way to move along its curved surface. The mathematically exact method to do this is the exponential map, which computes trajectories along shortest paths called geodesics. Unfortunately, computing exact geodesics is often a massive computational bottleneck, requiring expensive operations like matrix exponentials or full singular value decompositions (SVDs) at every iteration.

To scale Riemannian optimization to high-dimensional machine learning, researchers use a powerful alternative: manifold retractions. Retractions replace exact geodesic computations with first-order approximations that preserve the manifold's constraints while drastically reducing computational overhead.


The Core Mechanism: From Geodesics to Retractions

To understand why retractions work, consider the standard recipe for a single optimization step on a manifold:

  1. Compute the Gradient: Find the vanilla Euclidean gradient of the objective function in the ambient space.
  2. Project onto the Tangent Space: Project this gradient onto the tangent space—a flat vector space that perfectly touches the manifold at the current point. This gives a valid directional vector on the tangent plane.
  3. Move and Map Back: Take a step along this tangent vector. Because the tangent space is flat and the manifold is curved, this step leaves the manifold surface. We must map this flat update back down to the curved manifold.
                  [ Tangent Vector ] ---> (Leaves the manifold)
                         ^
                        / 
                       /   \  <--- Retraction (First-order snap-down)
                      /     \
  -------------------*-------V------------ Tangent Space
                    / .       .
                   /   .       . <--- Exponential Map (Exact geodesic)
                  /     .       .
  ~~~~~~~~~~~~~~~*~~~~~~~V~~~~~~~V~~~~~~~~ Manifold Surface
               Current   Exact   Approximate
               Point     Step    Step

The mathematically rigorous way to perform Step 3 is the exponential map. If you imagine the manifold as the surface of the Earth, the exponential map forces you to walk precisely along a great circle.

A retraction relaxes this requirement. Instead of calculating the exact curved path, a retraction is any smooth mapping from the tangent space back to the manifold that preserves the current position and matches the gradient's direction to first order. In our Earth analogy, a retraction means taking a straight step along the flat tangent plane and then snapping vertically down onto the globe's surface.

Because optimization is an iterative process that relies on local updates, an approximation that is accurate to the first order is completely sufficient. As long as the step size is reasonably small, the optimization trajectory under a retraction behaves almost identically to one under an exponential map, but at a fraction of the computational cost. As shown by Nicolas Boumal et al. in their widely used toolbox Manopt, a Matlab toolbox for optimization on manifolds, this first-order approximation ensures that optimization steps remain strictly within the constrained search space without sacrificing convergence behavior.


Why Retractions Preserve Convergence

A natural concern is whether substituting an approximation for the true geometry breaks the theoretical guarantees of optimization algorithms. A robust body of literature proves that it does not.

Escaping Saddle Points

In non-convex optimization, escaping saddle points is crucial to finding high-quality local minima. One might worry that the geometric distortion introduced by a retraction could trap an optimizer. However, Ya-Ping Hsieh et al. in Riemannian stochastic optimization methods avoid strict saddle points proved that stochastic Riemannian algorithms utilizing general retractions still escape strict saddle points with probability 1. Similarly, Christopher Criscitiello et al. demonstrated in Efficiently escaping saddle points on manifolds that first-order retractions provide a sufficiently smooth mapping to ensure the optimizer can navigate away from unstable critical points efficiently.

Continuous-Time Validity

The theoretical foundation of gradient descent is often analyzed using continuous-time gradient flows. Benjamin Gess et al. established in Stochastic Modified Flows for Riemannian Stochastic Gradient Descent that quantitative convergence rates derived from smooth continuous flows remain entirely valid when discretized using computationally efficient retraction maps instead of exact geodesics.

Empirical Stability

In some geometries, retractions are not just faster—they are numerically more stable. Samuele Fonio et al. explored this in Non-Euclidean Geometries for Prototype-Based Image Classification: a Reality Check, finding that for hyperspherical manifolds, first-order retractions often yield superior performance and numerical stability compared to the exact exponential map, which can suffer from compounding rounding errors.


Scaling Advanced Optimizers to Curved Spaces

By decoupling the optimization step from the expensive physics of exact geodesics, retractions allow researchers to port advanced Euclidean optimization techniques directly onto manifolds.

Adaptive and Sharpness-Aware Methods

Adaptive optimizers like Adam rely on tracking historical gradient moments across iterations. In Riemannian Adaptive Optimization Methods, Gary Bécigneul et al. showed that first-order retractions allow adaptive updates to safely navigate complex regions, such as the boundaries of the Poincaré ball in hyperbolic embeddings. This framework has been generalized with rigorous convergence analyses by the authors of Riemannian adaptive stochastic gradient algorithms on matrix manifolds and by Hideaki Iiduka et al. in A general framework of Riemannian adaptive optimization methods with a convergence analysis. Furthermore, Jihun Yun et al. successfully extended generalization-boosting techniques to manifolds in Riemannian SAM: Sharpness-Aware Minimization on Riemannian Manifolds by leveraging retractions to maintain structural constraints during the perturbation step.

Bilevel Optimization

Bilevel optimization involves solving a nested optimization problem inside another. Andi Han et al. proved in A Framework for Bilevel Optimization on Riemannian Manifolds that first-order geometric retractions are sufficient to guarantee convergence for these highly complex nested problems without sacrificing convergence rates. This was later extended to fully adaptive step-size regimes by Xu Shi et al. in An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds.


Designing Specialized Retractions for Maximum Speed

One of the greatest advantages of the retraction framework is flexibility: because any valid first-order approximation works, researchers can design custom retractions tailored to the specific algebraic structure of a given manifold.

The Stiefel Manifold and the Cayley Transform

The Stiefel manifold represents the space of orthogonal matrices (where $X^TX = I$). The exact exponential map here requires a matrix exponential, an $O(n^3)$ operation that destroys training throughput. To bypass this, Jun Li et al. developed Efficient Riemannian Optimization on the Stiefel Manifold via the Cayley Transform. They utilized an iterative approximation of the Cayley transform as a retraction, avoiding full matrix inversions and allowing orthogonality constraints to scale to massive deep learning architectures.

Doubly Stochastic Matrices

For optimization over doubly stochastic matrices (where rows and columns must sum to one), computing exact geodesics is highly prohibitive. In Manifold Optimization Over the Set of Doubly Stochastic Matrices: A Second-Order Geometry, Ahmed Douik demonstrated that retractions based on simple, iterative row-and-column normalization algorithms satisfy all necessary first-order geometric properties, yielding speedups of over 100x compared to standard solvers.

Eliminating Line Searches

In low-rank matrix completion, Zhizhong Li et al. designed a specialized retraction in A new retraction for accelerating the Riemannian three-factor low-rank matrix completion algorithm. Their retraction creates a perfect functional correspondence where the cost function values along a flat tangent line match the values along the retracted curve on the manifold. This unique property allows the optimizer to compute the exact optimal step size analytically, eliminating the need for expensive iterative line searches entirely.

Similarly, for structured natural-gradient descent, Wu Lin et al. showed in Tractable structured natural-gradient descent using local parameterizations that replacing a matrix exponential with a simple quadratic polynomial approximation preserves the required mathematical properties for natural gradient updates while significantly lowering time complexity.

Summary

Retraction-based optimization works because optimization is fundamentally a local, iterative process. By replacing global geodesic paths with first-order local approximations, retractions eliminate the heavy algebraic machinery of exponential maps. This simple shift preserves all core convergence guarantees while unlocking the ability to enforce complex geometric constraints at scale across modern machine learning.

Key Foundational Work

Descent methods for optimization on homogeneous manifolds (2008) — 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_retraction_based_optimization_685c1db1,
  title = {retraction-based optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/retraction-based-optimization/rdr_685c1db194984ef4a29f4c98b21aab29},
  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_retraction_based_optimization_685c1db1_v1,
  title = {retraction-based optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/retraction-based-optimization/rdr_685c1db194984ef4a29f4c98b21aab29/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