@inproceedings{
kassraie2024progressive,
title={Progressive Entropic Optimal Transport Solvers},
author={Parnian Kassraie and Aram-Alexandre Pooladian and Michal Klein and James Thornton and Jonathan Niles-Weed and marco cuturi},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=7WvwzuYkUq}
}
Optimal transport (OT) has profoundly impacted machine learning by providing theoretical and computational tools to realign datasets.
In this context, given two large point clouds of sizes $n$ and $m$ in $\mathbb{R}^d$, entropic OT (EOT) solvers have emerged as the most reliable tool to either solve the Kantorovich problem and output a $n\times m$ coupling matrix, or to solve the Monge problem and learn a vector-valued push-forward map. 
While the robustness of EOT couplings/maps makes them a go-to choice in practical applications, EOT solvers remain difficult to tune because of a small but influential set of hyperparameters, notably the omnipresent entropic regularization strength $\varepsilon$. Setting $\varepsilon$ can be difficult, as it simultaneously impacts various performance metrics, such as compute speed, statistical performance, generalization, and bias. In this work, we propose a new class of EOT solvers (ProgOT), that can estimate both plans and transport maps.
We take advantage of several opportunities to optimize the computation of EOT solutions by *dividing* mass displacement using a time discretization, borrowing inspiration from dynamic OT formulations, and *conquering* each of these steps using EOT with properly scheduled parameters. We provide experimental evidence demonstrating that ProgOT is a faster and more robust alternative to *standard solvers* when computing couplings at large scales, even outperforming neural network-based approaches. We also prove statistical consistency of our approach for estimating OT maps.
Progressive Entropic Optimal Transport Solvers
Parnian Kassraie Aram-Alexandre Pooladian Michal Klein James Thornton Jonathan Niles-Weed marco cuturi