  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 optimal transport maps.
