# A note on overrelaxation in the Sinkhorn algorithm

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Dec 2020.

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

- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Rethinking Initialization of the Sinkhorn Algorithm](https://mlsanity.com/paper/2206.07630/) (2022)
- [On Fitting Flow Models with Large Sinkhorn Couplings](https://mlsanity.com/paper/2506.05526/) (2025)
- [Progressive Entropic Optimal Transport Solvers](https://mlsanity.com/paper/2406.05061/) (2024)
- [Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods](https://mlsanity.com/paper/2301.13006/) (2023)
- [MFMAN-YOLO: A Method for Detecting Pole-like Obstacles in Complex Environment](https://mlsanity.com/paper/2307.12548/) (2023)
- [FlashSinkhorn 2: Block-Sparse Entropic Optimal Transport](https://mlsanity.com/paper/2610.02395/) (2026)

## Abstract (arXiv)

We derive an a priori parameter range for overrelaxation of the Sinkhorn algorithm, which guarantees global convergence and a strictly faster asymptotic local convergence. Guided by the spectral analysis of the linearized problem we pursue a zero cost procedure to choose a near optimal relaxation parameter.