Research map / Learning theory and algorithms / Optimal transport
HOT: An Efficient Halpern Accelerating Algorithm for Optimal Transport Problems
Guojun Zhang, Z. N. Gu, Yancheng Yuan, Defeng Sun
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use HOT instead of Network Simplex | reduced OT solver · DOTmark Classic 256x256 | time (s): 2562.92 -> 12.98 | Improved |
| use HOT instead of Network Simplex | reduced OT solver · DOTmark 128x128 | speedup: 17.44x speedup | Improved |
| use HOT instead of Gurobi IPM | reduced OT solver · DOTmark 128x128 | speedup: 15.83x speedup | Improved |
| use HOT instead of convolutional Sinkhorn | OT solver · DOTmark 128x128 | speedup: 19.54x speedup | Improved |
| add Halpern acceleration (HOT vs generalized ADMM) (ablation) | ADMM on reduced OT model · DOTmark 512x512 | iterations: saves 40% of iterations; 1610 -> 900 (Classic) | Improved |
| add Halpern acceleration (HOT vs generalized ADMM) (ablation) | ADMM on reduced OT model · DOTmark Classic 512x512 | time (s): 116.92 -> 81.02 | Improved |
| use HOT instead of ADMM | reduced OT solver · DOTmark Shapes 64x64 | time (s): 3.92 -> 0.64 | Improved |
| use HOT instead of Network Simplex at small scale | reduced OT solver · DOTmark Shapes 128x128 | gap: 2.46E-09 -> 2.51E-03 | Hurt |
| increase Sinkhorn regularization lambda from 0.01% to 1% of median cost (ablation) | Convolutional Sinkhorn · DOTmark Classic 64x64 | time (s) and gap: time 16.18 -> 0.19; gap 1.69E-04 -> 3.29E-01 | Mixed |
| increase Sinkhorn regularization lambda from 0.01% to 0.1% of median cost (ablation) | Convolutional Sinkhorn · DOTmark Classic 128x128 | gap: 6.98E-04 -> 3.34E-02 | Hurt |
| replace sparse Cholesky with the explicit linear-time linear-system solution (ablation) | HOT subproblem · linear system solves over image sizes | solve time | Improved |
Closest papers by meaning
- A fast and accurate splitting method for optimal transport: analysis and implementation (ICLR 2022 · similarity 0.91)
- A Truncated Newton Method for Optimal Transport (ICLR 2025 · similarity 0.89)
- Log-Averaged Mirror Prox for Fast, Large-Scale Optimal Transport in Linear Space (NeurIPS 2026 · similarity 0.86)
- Safe and Sparse Newton Method for Entropic-Regularized Optimal Transport (NeurIPS 2024 · similarity 0.86)
- A Combinatorial Algorithm for the Semi-Discrete Optimal Transport Problem (NeurIPS 2024 · similarity 0.85)
- Progressive Entropic Optimal Transport Solvers (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
