Numerical Stability in Regularized Optimal Transport

247 concepts155 papers1 proposal

Optimal Transport (OT) provides a geometrically sound framework for comparing probability distributions by computing the minimal cost of moving mass from one distribution to another. However, solving the exact, unregularized OT problem historically required solving a computationally heavy linear program that scaled poorly to large datasets.

A massive breakthrough occurred when marco cuturi introduced entropic regularization in Sinkhorn Distances: Lightspeed Computation of Optimal Transport. By adding an entropic penalty scaled by a regularization parameter $\varepsilon$, the problem transforms into a strictly convex matrix scaling task that can be solved rapidly via parallelizable Sinkhorn iterations.

Yet, as noted by Cuturi et al. in Progressive Entropic Optimal Transport Solvers, this speedup introduces a brutal trade-off. To recover the true, sharp, deterministic transport plan, practitioners must decrease $\varepsilon$ toward zero. Doing so triggers severe numerical instability, forcing a compromise between solution precision and algorithmic convergence.

Why Entropic Regularization Collapses at Low Noise

To understand why the Sinkhorn algorithm breaks down, we must examine the mathematical core of the method: the Gibbs kernel matrix, defined as:

$$K_{ij} = \exp\left(-\frac{C_{ij}}{\varepsilon}\right)$$

where $C_{ij}$ represents the cost of transporting mass from point $i$ to point $j$.

As Benamou et al. explain in Iterative Bregman Projections for Regularized Transportation Problems, when $\varepsilon$ approaches zero to increase accuracy, the negative exponent grows excessively large for any non-zero cost. Consequently, the entries of the Gibbs kernel decay exponentially, quickly dropping below machine precision. This causes arithmetic underflow, resulting in zero values in memory and algorithmic failure during iterative matrix scaling updates.

The instability becomes even more severe when computing gradients or Hessians for optimization loops (such as training generative models or optimizing trajectories). Li et al. demonstrate in Robust First and Second-Order Differentiation for Regularized Optimal Transport that the linear system governing these second-order derivatives is structurally singular. As $\varepsilon$ decreases, the system's condition number grows exponentially, causing standard matrix inversion methods to fail completely and preventing reliable optimization.

Taming Instability via Log-Domain and Dual Formulations

The most direct way to prevent arithmetic underflow is to avoid computing the exponential kernel explicitly. Instead, solvers can shift computations into the log-domain or update dual variables directly.

As highlighted by Salzo et al. in Batch Greenkhorn Algorithm for Entropic-Regularized Multimarginal Optimal Transport: Linear Rate of Convergence and Iteration Complexity, parameterizing the algorithm to update dual potentials rather than the transport plan directly prevents the numerical overflow or underflow typically associated with entropic terms. While log-domain stabilization extends the usable range of $\varepsilon$, Le et al. note in Accelerating Motion Planning via Optimal Transport that balancing computational stability with transport plan precision still requires careful manual tuning and can slow down execution.

Alternative Regularization Schemes

Rather than patching the vulnerabilities of entropic regularization, a prominent line of research replaces it entirely with alternative regularizers that do not rely on exponential functions.

Quadratic Regularization

Solomon et al. propose Quadratically Regularized Optimal Transport on Graphs, showing that quadratic penalties maintain numerical stability in low-regularization regimes where entropic methods fail. This allows practitioners to compute transport plans that are nearly identical to exact linear programming solutions. Similarly, Blondel et al. utilize squared 2-norm or group lasso penalties in Smooth and Sparse Optimal Transport to achieve sharp, sparse, and differentiable mappings without the "blurry" smoothing artifacts typical of Sinkhorn updates.

Low-Rank Factorization

Scetbon et al. introduce Low-Rank Sinkhorn Factorization, which bypasses entropic smoothing entirely by directly constraining the coupling matrix to have a low nonnegative rank. This structural constraint controls the complexity of the transport plan and maintains linear time complexity without introducing numerical instability as the approximation error approaches zero.

Operator Splitting Methods

Another powerful approach is to solve the transport problem using splitting methods borrowed from classical optimization, which decouple the constraints from the objective function.

Mai et al. introduce DROT in A fast and accurate splitting method for optimal transport: analysis and implementation, leveraging Douglas-Rachford splitting to solve the original unregularized problem directly. This ensures numerical stability on standard GPU hardware using single-precision arithmetic, avoiding the common issue where decreasing regularization parameters leads to numerical overflow or underflow.

Lindbäck et al. extend this framework in Bringing regularized optimal transport to lightspeed: a splitting method adapted for GPUs, demonstrating that operator splitting frameworks maintain robust numerical stability even when regularization parameters approach zero, allowing for high-fidelity transport plans without numerical collapse.

Living with Blur: Debiasing Stable Solutions

If a practitioner is forced to use a larger $\varepsilon$ to guarantee numerical stability and fast convergence, the resulting transport plan suffers from an over-smoothing or "blurring" bias. To counteract this without sacrificing stability, researchers have developed debiasing techniques.

In Debiased Sinkhorn barycenters, Janati et al. show that by subtracting regularized self-transport terms (Sinkhorn divergences), one can completely eliminate the blur from regularized distribution averages. This allows for the computation of sharp, mathematically grounded barycenters while operating safely within a numerically stable parameter regime.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 170 papers
  2. Version 1 · 2026-10-04 · 384 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_entropic_regularization_instability_5662e6f5,
  title = {entropic regularization instability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/entropic-regularization-instability/rdr_5662e6f5769d4c5683c0351416e19387},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_entropic_regularization_instability_5662e6f5_v2,
  title = {entropic regularization instability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/entropic-regularization-instability/rdr_5662e6f5769d4c5683c0351416e19387/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake