# HOT: An Efficient Halpern Accelerating Algorithm for Optimal Transport Problems

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Aug 2024.

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

- [PINS: Proximal Iterations with Sparse Newton and Sinkhorn for Optimal Transport](https://mlsanity.com/paper/2502.03749/) (2025)
- [A Provably Convergent and Practical Algorithm for Gromov--Wasserstein Optimal Transport](https://mlsanity.com/paper/2605.04175/) (2026)
- [GPU-Accelerated Bregman Douglas-Rachford Splitting for Discrete Optimal Transport](https://mlsanity.com/paper/2610.04715/) (2026)

## Abstract (arXiv)

This paper proposes an efficient HOT algorithm for solving the optimal transport (OT) problems with finite supports. We particularly focus on an efficient implementation of the HOT algorithm for the case where the supports are in ℝ2 with ground distances calculated by L22-norm. Specifically, we design a Halpern accelerating algorithm to solve the equivalent reduced model of the discrete OT problem. Moreover, we derive a novel procedure to solve the involved linear systems in the HOT algorithm in linear time complexity. Consequently, we can obtain an varepsilon-approximate solution to the optimal transport problem with M supports in O(M1.5/varepsilon) flops, which significantly improves the best-known computational complexity. We further propose an efficient procedure to recover an optimal transport plan for the original OT problem based on a solution to the reduced model, thereby overcoming the limitations of the reduced OT model in applications that require the transport plan. We implement the HOT algorithm in PyTorch and extensive numerical results show the superior performance of the HOT algorithm compared to existing state-of-the-art algorithms for solving the OT problems.