# A Truncated Newton Method for Optimal Transport

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 39 references that are in the map.
- First posted on arXiv 2 Apr 2025.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Improved Training of Wasserstein GANs](https://mlsanity.com/paper/1704.00028/) (2017)
- [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017)
- [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)
- [Kernel Operations on the GPU, with Autodiff, without Memory Overflows](https://mlsanity.com/paper/2004.11127/) (2020)
- [Smooth and Sparse Optimal Transport](https://mlsanity.com/paper/1710.06276/) (2017)
- [Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems](https://mlsanity.com/paper/1610.06519/) (2016)
- [On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms](https://mlsanity.com/paper/1901.06482/) (2019)
- [On the Efficiency of Entropic Regularized Algorithms for Optimal Transport](https://mlsanity.com/paper/1906.01437/) (2019)
- [On a Combination of Alternating Minimization and Nesterov's Momentum](https://mlsanity.com/paper/1906.03622/) (2019)
- [DOTmark - A Benchmark for Discrete Optimal Transport](https://mlsanity.com/paper/1610.03368/) (2016)
- [Accelerating Sinkhorn Algorithm with Sparse Newton Iterations](https://mlsanity.com/paper/2401.12253/) (2024)
- [Improved Rate of First Order Algorithms for Entropic Optimal Transport](https://mlsanity.com/paper/2301.09675/) (2023)
- [Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients](https://mlsanity.com/paper/2307.08507/) (2023)
- [Mirror Sinkhorn: Fast Online Optimization on Transport Polytopes](https://mlsanity.com/paper/2211.10420/) (2022)

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

- [FlashSinkhorn: IO-Aware Entropic Optimal Transport on GPU](https://mlsanity.com/paper/2602.03067/) (2026)
- [Fast and Large-Scale Unbalanced Optimal Transport via its Semi-Dual and Adaptive Gradient Methods](https://mlsanity.com/paper/2602.10697/) (2026)
- [DrainSinkhorn: Safe Elimination for Batched Entropic Optimal Transport](https://mlsanity.com/paper/2607.24741/) (2026)
- [Dual-guided Hierarchical Edge Localization for Large-scale Optimal Transport Across Dimensions](https://mlsanity.com/paper/2609.13010/) (2026)
- [Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory](https://mlsanity.com/paper/2609.33814/) (2026)
- [FlashSinkhorn 2: Block-Sparse Entropic Optimal Transport](https://mlsanity.com/paper/2610.02395/) (2026)

## Abstract (arXiv)

Developing a contemporary optimal transport (OT) solver requires navigating trade-offs among several critical requirements: GPU parallelization, scalability to high-dimensional problems, theoretical convergence guarantees, empirical performance in terms of precision versus runtime, and numerical stability in practice. With these challenges in mind, we introduce a specialized truncated Newton algorithm for entropic-regularized OT. In addition to proving that locally quadratic convergence is possible without assuming a Lipschitz Hessian, we provide strategies to maximally exploit the high rate of local convergence in practice. Our GPU-parallel algorithm exhibits exceptionally favorable runtime performance, achieving high precision orders of magnitude faster than many existing alternatives. This is evidenced by wall-clock time experiments on 24 problem sets (12 datasets × 2 cost functions). The scalability of the algorithm is showcased on an extremely large OT problem with n ≈ 106, solved approximately under weak entopric regularization.