# Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transport

arXiv: https://arxiv.org/abs/1711.01851 · HTML: https://mlsanity.com/paper/1711.01851/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2017.

## Built on by (most cited first, 18 of 18)

- [Unbalanced Optimal Transport through Non-negative Penalized Linear Regression](https://mlsanity.com/paper/2106.04145/) (2021)
- [Trajectory Inference via Mean-field Langevin in Path Space](https://mlsanity.com/paper/2205.07146/) (2022)
- [Meta Optimal Transport](https://mlsanity.com/paper/2206.05262/) (2022)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Sinkhorn-Drifting Generative Models](https://mlsanity.com/paper/2603.12366/) (2026)
- [Rethinking Initialization of the Sinkhorn Algorithm](https://mlsanity.com/paper/2206.07630/) (2022)
- [Accelerating Sinkhorn Algorithm with Sparse Newton Iterations](https://mlsanity.com/paper/2401.12253/) (2024)
- [Progressive Entropic Optimal Transport Solvers](https://mlsanity.com/paper/2406.05061/) (2024)
- [Hilbert Curve Projection Distance for Distribution Comparison](https://mlsanity.com/paper/2205.15059/) (2022)
- [Annealed Sinkhorn for Optimal Transport: convergence, regularization path and debiasing](https://mlsanity.com/paper/2408.11620/) (2024)
- [Faster Computation of Entropic Optimal Transport via Stable Low Frequency Modes](https://mlsanity.com/paper/2506.14780/) (2025)
- [A Novel Skip Orthogonal List for Dynamic Optimal Transport Problem](https://mlsanity.com/paper/2310.18446/) (2023)
- [DrainSinkhorn: Safe Elimination for Batched Entropic Optimal Transport](https://mlsanity.com/paper/2607.24741/) (2026)
- [Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp](https://mlsanity.com/paper/2608.11760/) (2026)
- [Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory](https://mlsanity.com/paper/2609.33814/) (2026)
- [Cost-augmented Schr"odinger bridges on graphs are exactly solvable: a Feynman-Kac tilt replaces learned control](https://mlsanity.com/paper/2610.02195/) (2026)
- [FlashSinkhorn 2: Block-Sparse Entropic Optimal Transport](https://mlsanity.com/paper/2610.02395/) (2026)
- [Reinforcement Learning for Large-Scale Lifelong Multi-Agent Path Finding with Shared Spatial Fields](https://mlsanity.com/paper/2610.18186/) (2026)

## Abstract (arXiv)

This article describes a set of methods for quickly computing the solution to the regularized optimal transport problem. It generalizes and improves upon the widely-used iterative Bregman projections algorithm (or Sinkhorn--Knopp algorithm). We first propose to rely on regularized nonlinear acceleration schemes. In practice, such approaches lead to fast algorithms, but their global convergence is not ensured. Hence, we next propose a new algorithm with convergence guarantees. The idea is to overrelax the Bregman projection operators, allowing for faster convergence. We propose a simple method for establishing global convergence by ensuring the decrease of a Lyapunov function at each step. An adaptive choice of overrelaxation parameter based on the Lyapunov function is constructed. We also suggest a heuristic to choose a suitable asymptotic overrelaxation parameter, based on a local convergence analysis. Our numerical experiments show a gain in convergence speed by an order of magnitude in certain regimes.