Bypassing Retraction Bottlenecks in Riemannian Optimization

24 concepts23 papers1 proposal

Many fundamental problems in machine learning require optimizing parameters that live on curved geometric surfaces rather than flat Euclidean spaces. For example, learning orthogonal transformations requires constraining a matrix $X$ to the Stiefel manifold ($X^\top X = I$). This constraint is essential for preserving stability in deep neural networks, performing principal component analysis, and learning rotations.

However, optimizing directly on these manifolds introduces a severe computational bottleneck: the retraction overhead.

The Geometry of Constraints and the Cubic Bottleneck

In standard Euclidean optimization, we update a parameter by taking a step along a gradient direction. If we do this on a curved manifold, the step immediately shoots off the surface into the ambient space. To fix this, traditional Riemannian optimization splits the update into two parts:

  1. Compute a gradient step in the flat tangent space of the current point.
  2. Apply a retraction—a geometric mapping that pulls the point back down onto the manifold surface.
Euclidean Step (Off Manifold) ───> ✘
       ▲                               │
       │                               │ Retraction (SVD, QR, Exponential)
       │                               ▼
Current Point ─────────────────────> New Point (On Manifold)

While mathematically elegant, enforcing strict feasibility at every single iteration is incredibly expensive. As noted by Raman Arora and Li Cheng 0001 et al., classical retractions often rely on matrix exponentials or full matrix inversions (such as the Cayley transform), which scale cubically ($O(n^3)$) with the matrix dimensions.

Other common retractions require Singular Value Decomposition (SVD) or QR decompositions. Meihong Wang et al. point out that these decompositions become a primary bottleneck when optimizing high-dimensional projection matrices. Similarly, Alexander Fonarev et al. and Anoop Cherian et al. observe that computing full decompositions at every iteration makes standard Riemannian optimization scale poorly for large vocabulary embeddings and high-dimensional covariance descriptors.

To scale manifold optimization to modern machine learning workloads, researchers have developed techniques to bypass or minimize this cubic retraction overhead. These approaches broadly fall into three paradigms: infeasible "landing" methods, submanifold/coordinate reductions, and projection-free trajectories.

Infeasible Optimization and the "Landing" Paradigm

If pulling the parameter back to the manifold at every step is too expensive, why not let it drift?

Infeasible optimization methods allow the algorithm's iterates to leave the manifold during training, only forcing them back asymptotically. A prominent realization of this idea is the landing algorithm proposed by Gabriel Peyré et al.. Instead of using an exact retraction like an SVD, the landing algorithm integrates a feedback loop directly into the optimization step. It introduces an algebraic penalty term that acts like a gravitational pull: when the matrix drifts away from orthogonality, the term exerts a corrective force. Crucially, this force is computed using simple matrix multiplications rather than matrix factorizations, eliminating the $O(n^3)$ bottleneck.

Simon Vary et al. extended this paradigm to the generalized Stiefel manifold ($X^\top B X = I$), demonstrating that even when the constraint matrix $B$ is stochastic or unknown, updates can "land" on the manifold in expectation using only matrix multiplications.

Allowing iterates to wander off the manifold raises questions about convergence. However, Youbang Sun et al. proved that these infeasible optimization methods still achieve local linear convergence under orthogonal constraints. This confirms that strict feasibility at every intermediate step is mathematically unnecessary. Building on this, Yilong Song et al. successfully adapted retraction-free optimization to distributed training environments, removing the need for nodes to perform expensive orthogonalization steps before communicating.

Submanifold and Coordinate-Wise Reductions

Another strategy to mitigate the $O(n^3)$ cost is to reduce the size of the matrix operation itself. If you must compute a retraction, it is far cheaper to compute it on a tiny matrix than a massive one.

In Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method, the authors introduce Riemannian Random Submanifold Descent (RSDM). Instead of updating the entire high-dimensional parameter matrix at once, RSDM restricts each optimization step to a low-dimensional random submanifold. Because the update is confined to a small subspace, the subsequent retraction step only requires decomposing a small matrix, drastically reducing wall-clock time.

Full Matrix Update:       [  X  ]  ───> Requires Full O(n³) Retraction

Submanifold Update:       [ █ ]    ───> Requires Tiny, Cheap Retraction

A related approach is to update the matrix coordinate by coordinate. Andi Han et al. developed Riemannian coordinate descent algorithms that break global manifold updates into localized, scalar- or block-level updates. By updating only a fraction of the coordinates at a time, the computational cost of mapping back to the manifold surface is distributed and minimized. To scale this further for dense matrix eigen-decompositions, Peilin Zhao et al. combined stochastic coordinate updates with data sampling, bypassing batch matrix inversions entirely.

Projection-Free Trajectories and Alternative Forces

A third paradigm avoids retractions by changing how the optimization path is constructed or how gradients are tracked.

Instead of taking discrete steps and projecting back, algorithms can navigate the constraint space along continuous curves. Seong Jae Hwang et al. designed a projection-free method for the generalized Stiefel manifold that routes updates along continuous descent curves. This allows the algorithm to handle non-smooth regularizers without ever triggering an SVD or Cholesky decomposition. For complex nested problems, Xu Shi et al. demonstrated that substituting expensive exponential mappings with simpler, first-order retractions is sufficient to maintain stability in bilevel Riemannian optimization.

Finally, in decentralized or networked settings, the communication infrastructure itself can be leveraged to maintain constraints. Jun Chen et al. developed a decentralized method called Quantized Riemannian Gradient Tracking (Q-RGT). In decentralized optimization, nodes typically drift apart and off the manifold due to communication constraints. Q-RGT turns this vice into a virtue: it repurposes low-precision quantization noise to track the global gradient and simultaneously pull local iterates back toward the compact submanifold, eliminating explicit retraction steps entirely.

Key Foundational Work

On Learning Rotations (2009) — contributed 1 concept elements to this direction.
Geometrical methods for non-negative ICA: Manifolds, Lie groups and toral subalgebras (2005) — 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_manifold_retraction_overhead_f6ec264d,
  title = {manifold retraction overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/manifold-retraction-overhead/rdr_f6ec264df52348528872e0d2213141a7},
  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_manifold_retraction_overhead_f6ec264d_v1,
  title = {manifold retraction overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/manifold-retraction-overhead/rdr_f6ec264df52348528872e0d2213141a7/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