HOT: An Efficient Halpern Accelerating Algorithm for Optimal Transport Problems

Guojun Zhang, Z. N. Gu, Yancheng Yuan, Defeng SunIEEE TPAMI 2024

TL;DR

This paper introduces HOT, a novel algorithm that significantly speeds up the computation of Optimal Transport (OT) distances, a crucial tool in various machine learning applications. HOT achieves this by reformulating the problem and employing a clever linear-time solver for its subproblems, leading to a substantial improvement in computational complexity and practical performance, especially for large datasets.

What Problem Does This Paper Address?

The Kantorovich-Wasserstein (KW) distance is a powerful metric for comparing probability distributions, finding applications in image processing, computer graphics, and more. However, computing this distance involves solving a large-scale Optimal Transport (OT) problem, which is computationally expensive and memory-intensive. Traditional methods like simplex or interior-point methods struggle with scalability, and even popular alternatives like the Sinkhorn algorithm face numerical challenges with small regularization parameters. While some methods reduce the problem's size, they often lose the ability to recover the actual transport plan, which is essential for many applications. This paper tackles these limitations by proposing an efficient and scalable algorithm that not only computes the KW distance faster but also recovers the transport plan.

Methods

The core of the paper is the HOT (Halpern Accelerating) algorithm. It addresses the OT problem by:

  • Reformulating the OT problem: The authors leverage a known "reduced model" of the OT problem, which has fewer variables than the original formulation. This reduced model is still an LP problem but is more amenable to efficient solvers.
  • Halpern Acceleration: HOT employs a Halpern accelerating method, a type of first-order optimization technique known for its convergence properties. This is applied to solve the dual of the reduced OT problem.
  • Linear-Time Subproblem Solver: A key innovation is a novel procedure to solve the linear systems that arise within the Halpern iteration. This procedure exploits the specific structure of the problem and achieves linear time complexity, a significant improvement over standard methods like Cholesky decomposition.
  • Transport Plan Recovery: The paper also introduces an efficient algorithm to reconstruct the optimal transport plan from the solution of the reduced model. This overcomes a major limitation of previous reduced-model approaches.

Datasets

The paper uses the DOTmark dataset for evaluation. This dataset is a collection of benchmark instances for optimal transport, categorized into:

  • Classic Images
  • Shapes
  • Gaussian Distributions

The experiments involve resizing images from these categories to various resolutions (64x64, 128x128, 256x256, and 512x512) and randomly selecting pairs to compute KW distances.

Key Insights and Ideas

  • The power of the reduced model: By reformulating the OT problem into a smaller, equivalent problem, the authors unlock significant computational gains.
  • Linear-time solvers are crucial: The bottleneck in many OT algorithms is solving linear systems. The paper's linear-time solver for these specific systems is a major breakthrough.
  • Halpern acceleration pays off: Combining Halpern acceleration with an efficient subproblem solver leads to superior convergence and practical speedups.
  • Recovering the transport plan is feasible: The ability to reconstruct the transport plan from the reduced model solution makes the approach applicable to a wider range of tasks where the plan itself is needed.

Key Results

  • Computational Complexity: HOT achieves an ε-approximate solution with M supports in O(M¹·⁵/ε) flops, which is stated to be the best-known complexity.
  • Speedup: For images sized 128x128, HOT achieved a 17.44x speedup over Network Simplex, 15.83x speedup over Gurobi, and 19.54x speedup over convolutional Sinkhorn.
  • Memory Efficiency: HOT demonstrates significant memory advantages, avoiding the O(M²) memory requirement of Sinkhorn-type methods by not needing to store the full transport cost matrix.
  • Transport Plan Recovery: The paper provides an efficient algorithm for recovering the transport plan, which is crucial for applications like color transfer.
  • Numerical Performance: Extensive experiments on the DOTmark dataset show HOT's superior performance in terms of both speed and memory usage compared to state-of-the-art methods.

Limitations and Future Work

  • Generalization to Rd: The paper primarily focuses on the case where supports are in R², with L₁-norm distances. Future work aims to design efficient implementations for discrete supports in the more general Rᵈ space.
  • Wasserstein Barycenter Problem: The authors suggest extending their work to solve the Wasserstein barycenter problem with discrete supports.
  • Hardware Considerations: While GPU acceleration is supported, further optimization for specific hardware architectures might be explored.

Summary updated

Abstract

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 $\mathbb{R}^2$ with ground distances calculated by $L_2^2$-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(M^{1.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.
BibTeX
@article{zhang2024hot,
  author = {Guojun Zhang and Z. N. Gu and Yancheng Yuan and Defeng Sun},
  title = {{HOT: An Efficient Halpern Accelerating Algorithm for Optimal Transport Problems}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2024},
}
Figure