# Exponential Convergence of Sinkhorn Under Regularization Scheduling

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jul 2022.

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

- [Accelerating Sinkhorn Algorithm with Sparse Newton Iterations](https://mlsanity.com/paper/2401.12253/) (2024)
- [Hierarchical Refinement: Optimal Transport to Infinity and Beyond](https://mlsanity.com/paper/2503.03025/) (2025)
- [A Sinkhorn-type Algorithm for Constrained Optimal Transport](https://mlsanity.com/paper/2403.05054/) (2024)
- [Bidirectional Knowledge Reconfiguration for Lightweight Point Cloud Analysis](https://mlsanity.com/paper/2310.05125/) (2023)

## Abstract (arXiv)

In 2013, Cuturi [Cut13] introduced the Sinkhorn algorithm for matrix scaling as a method to compute solutions to regularized optimal transport problems. In this paper, aiming at a better convergence rate for a high accuracy solution, we work on understanding the Sinkhorn algorithm under regularization scheduling, and thus modify it with a mechanism that adaptively doubles the regularization parameter η periodically. We prove that such modified version of Sinkhorn has an exponential convergence rate as iteration complexity depending on log(1/varepsilon) instead of varepsilon-O(1) from previous analyses [Cut13][ANWR17] in the optimal transport problems with integral supply and demand. Furthermore, with cost and capacity scaling procedures, the general optimal transport problem can be solved with a logarithmic dependence on 1/varepsilon as well.