# Robust Sublinear Convergence Rates for Iterative Bregman Projections

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 52 references that are in the map.
- First posted on arXiv 1 Feb 2026.

## Builds on (most cited first, 20 of 20)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Faster Wasserstein Distance Estimation with the Sinkhorn Divergence](https://mlsanity.com/paper/2006.08172/) (2020)
- [An Optimal Transport approach for the Schr"odinger bridge problem and convergence of Sinkhorn algorithm](https://mlsanity.com/paper/1911.06850/) (2019)
- [Scaling Algorithms for Unbalanced Transport Problems](https://mlsanity.com/paper/1607.05816/) (2016)
- [Entropic and displacement interpolation: a computational approach using the Hilbert metric](https://mlsanity.com/paper/1506.04255/) (2015)
- [Mirror Descent with Relative Smoothness in Measure Spaces, with application to Sinkhorn and EM](https://mlsanity.com/paper/2206.08873/) (2022)
- [Quantum Wasserstein Generative Adversarial Networks](https://mlsanity.com/paper/1911.00111/) (2019)
- [Maximum Flow and Minimum-Cost Flow in Almost-Linear Time](https://mlsanity.com/paper/2203.00671/) (2022)
- [A gradient descent perspective on Sinkhorn](https://mlsanity.com/paper/2002.03758/) (2020)
- [Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling](https://mlsanity.com/paper/1801.02790/) (2018)
- [Quantitative contraction rates for Sinkhorn's algorithm: beyond bounded costs and compact marginals](https://mlsanity.com/paper/2304.04451/) (2023)
- [Quantitative Uniform Stability of the Iterative Proportional Fitting Procedure](https://mlsanity.com/paper/2108.08129/) (2021)
- [Hilbert's projective metric for functions of bounded growth and exponential convergence of Sinkhorn's algorithm](https://mlsanity.com/paper/2311.04041/) (2023)
- [Sharper Exponential Convergence Rates for Sinkhorn's Algorithm in Continuous Settings](https://mlsanity.com/paper/2407.01202/) (2024)
- [Quantum Optimal Transport for Tensor Field Processing](https://mlsanity.com/paper/1612.08731/) (2016)
- [Non-asymptotic convergence bounds for Sinkhorn iterates and their gradients: a coupling approach](https://mlsanity.com/paper/2304.06549/) (2023)
- [Matrix-valued Monge-Kantorovich Optimal Mass Transport](https://mlsanity.com/paper/1304.3931/) (2013)
- [Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time](https://mlsanity.com/paper/2205.01562/) (2022)

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

- [Unfolding with a Wasserstein Loss](https://mlsanity.com/paper/2603.20903/) (2026)

## Abstract (arXiv)

Entropic regularization provides a simple way to approximate linear programs whose constraints split into two or more tractable blocks. The resulting objectives are amenable to cyclic Kullback-Leibler (KL) Bregman projections, with Sinkhorn-type algorithms for optimal transport, matrix scaling, and barycenters as canonical examples. This paper gives a general blueprint for proving O(1/k) dual convergence rate with a constant that scales only linearly in 1/γ, where γ is the entropic regularization parameter. We call such rates "robust", because this mild dependence on γ underpins favorable complexity bounds for approximating the unregularized problem via alternating KL projections. The blueprint reduces the proof to a uniform primal bound and a dual bound for a quotient norm induced by the constraint split. To make these inputs usable, we propose two helper results, which rely on the non-expansiveness of the dual iterations in this quotient dual norm. Instantiating this blueprint for graph-structured transport yields a new flow-Sinkhorn algorithm for the Wasserstein-1 distance on graphs. It achieves varepsilon-additive accuracy on the transshipment cost in O(p,diameter3/varepsilon4) arithmetic operations (up to logarithmic factors), where p is the number of edges. We also provide a machine-checked Lean formalization of the core blueprint and its graph-W1 instantiation.