Faster Sinkhorn’s Algorithm with Small Treewidth

Boyu Liu, Zhao Song, Jiale Zhao, Tianyi ZhouOpenReview 2026 · Submission to ICLR 2026 · Withdrawn · OpenReview

Its authors withdrew this paper, so there is no full text to read or summarize.

Abstract

While approximating optimal transport (OT) distances such as the earth mover's distance is a fundamental problem in statistics and machine learning, it is computationally expensive. Given the cost matrix $C=AA^\top$ where $A \in \mathbb{R}^{n \times d}$, the state-of-the-art results [Dvurechensky, Gasnikov, and Kroshnin ICML 2018] cost $\widetilde{O}(\epsilon^{-2} n^2)$ time to approximate OT distance, where $n$ is the size of given two discrete distributions and $\epsilon$ is the error. In this paper, we proposed a faster Sinkhorn's Algorithm to approximate the OT distance when matrix $A$ has treewidth $\tau$, which is usually very small. Our algorithm achieves a running time of $\widetilde{O}(\epsilon^{-2} n \tau)$, improving upon the previous $\widetilde{O}(\epsilon^{-2} n^2)$ time complexity. To the best of our knowledge, our paper is the first work to improve the OT distance approximating problem running time to $\widetilde{O}(\epsilon^{-2} n \tau)$.
BibTeX
@misc{liu2026faster,
  author = {Boyu Liu and Zhao Song and Jiale Zhao and Tianyi Zhou},
  title = {{Faster Sinkhorn’s Algorithm with Small Treewidth}},
  year = {2026},
  url = {https://openreview.net/forum?id=EjzW9zHjyf},
  howpublished = {OpenReview},
  note = {Submitted to ICLR 2026},
}
Figure