Hierarchical Refinement: Optimal Transport to Infinity and Beyond

Peter Halmos, Julian Gold, Xinhao Liu, Benjamin Raphael

International Conference on Machine Learning 2025 · Oral

Optimal Transport (OT) is a powerful mathematical framework for comparing probability distributions by finding the least-cost mapping or coupling between them. It has garnered significant attention in machine learning for its ability to model least-action principles in generative models, facilitate domain-domain translation, and enable tasks like shape registration and barycenter computation in computer vision and computational biology. However, classical OT algorithms, such as the **network simplex** and **Hungarian algorithm**, suffer from prohibitive cubic time complexity and quadratic space complexity, rendering them impractical for the massive datasets prevalent in modern AI. While methods like **Sinkhorn regularization** and **mini-batch OT** offer some scalability improvements, they often introduce approximations, batch bias, or sacrifice the global, bijective nature of the optimal map.

AI review

Hierarchical Refinement is a technically serious contribution to scalable optimal transport that earns its claims: an O(N log N) time, O(N) space algorithm for computing global, bijective Monge maps, grounded in a provable local-to-global optimality invariant derived from Meyer-Scetbon's 2021 low-rank OT formulation. The core theoretical move — showing that recursive partitioning via low-rank OT preserves global optimality through a cyclic monotonicity argument — is non-trivial and, if the proof holds as described, genuinely closes a gap the community has acknowledged for years. My…