Learning Costs for Structured Monge Displacements
Michal Klein Aram-Alexandre Pooladian Pierre Ablin Eugène Ndiaye Jonathan Niles-Weed Marco Cuturi
Optimal transport theory has provided machine learning with several tools to
infer a push-forward map between densities from samples. While this theory has
recently seen tremendous methodological developments in machine learning, its
practical implementation remains notoriously difficult, because it is plagued
by both computational and statistical challenges. Because of such difficulties,
existing approaches rarely depart from the default choice of estimating such
maps with the simple squared-Euclidean distance as the ground cost,
$c(x,y)=\|x-y\|^2_2$. We follow a different path in this work, with the
motivation of \emph{learning} a suitable cost structure to encourage maps to
transport points along engineered features. We extend the recently proposed
Monge-Bregman-Occam pipeline~\citep{cuturi2023monge}, that rests on an
alternative cost formulation that is also cost-invariant $c(x,y)=h(x-y)$, but
which adopts a more general form as $h=\tfrac12 \ell_2^2+\tau$, where $\tau$ is
an appropriately chosen regularizer. We first propose a method that builds upon
proximal gradient descent to generate ground truth transports for such
structured costs, using the notion of $h$-transforms and $h$-concave
potentials. We show more generally that such a method can be extended to
compute $h$-transforms for entropic potentials. We study a regularizer that
promotes transport displacements in low-dimensional spaces, and propose to
learn such a basis change using Riemannian gradient descent on the Stiefel
manifold. We show that these changes lead to estimators that are more robust
and easier to interpret.