Learning Costs for Structured Monge Displacements

Michal Klein, Aram-Alexandre Pooladian, Pierre Ablin, Eugène Ndiaye, Jonathan Niles-Weed, Marco CuturiarXiv 2023 · arXiv · OpenReview

Abstract

Given a source and a target probability measure supported on $\mathbb{R}^d$, the Monge problem asks to find the most efficient way to map one distribution to the other. This efficiency is quantified by defining a cost function between source and target data. Such a cost is often set by default in the machine learning literature to the squared-Euclidean distance, $\ell^2_2(\mathbf{x},\mathbf{y})=\frac{1}{2}|\mathbf{x}-\mathbf{y}|_2^2$. Recently, Cuturi et. al '23 highlighted the benefits of using elastic costs, defined through a regularizer $\tau$ as $c(\mathbf{x},\mathbf{y})=\ell^2_2(\mathbf{x},\mathbf{y})+\tau(\mathbf{x}-\mathbf{y})$. Such costs shape the displacements of Monge maps $T$, i.e., the difference between a source point and its image $T(\mathbf{x})-\mathbf{x}$, by giving them a structure that matches that of the proximal operator of $\tau$. In this work, we make two important contributions to the study of elastic costs: (i) For any elastic cost, we propose a numerical method to compute Monge maps that are provably optimal. This provides a much-needed routine to create synthetic problems where the ground truth OT map is known, by analogy to the Brenier theorem; (ii) We propose a loss to learn the parameter $\theta$ of a parameterized regularizer $\tau_\theta$, and apply it in the case where $\tau_{A}(\mathbf{z})=\|A^\perp \mathbf{z}\|^2_2$. This regularizer promotes displacements that lie on a low dimensional subspace of $\mathbb{R}^d$, spanned by the $p$ rows of $A\in\mathbb{R}^{p\times d}$.

Introduction

Optimal Transport (OT) provides a mathematical framework to map one probability distribution to another. In machine learning, this is often applied to predict trajectories, such as how a cell population evolves over time. Traditionally, the "efficiency" of this mapping is measured using the squared-Euclidean distance. However, in high-dimensional settings like genomics, data often moves along specific, low-dimensional manifolds. Standard Euclidean OT fails to capture this structure, leading to noisy and unrealistic maps—a phenomenon known as the "curse of dimensionality."

Elastic Costs and Structured Displacements

To address these limitations, this work explores Elastic Costs. Instead of a simple distance metric, the cost function is defined as $h(\mathbf{z}) = \frac{1}{2}\|\mathbf{z}\|^2 + \gamma\tau(\mathbf{z})$, where $\tau$ is a regularizer that "shapes" the displacement $\mathbf{z} = T(\mathbf{x}) - \mathbf{x}$.

Visualizing how different elastic costs shape the transport of points from a base measure. From left to right: standard Euclidean, $\ell_1$ regularization (promoting sparsity), and subspace regularization (promoting movement along a specific direction $\mathbf{b}$).

The core insight is that the displacement of an optimal map under an elastic cost is directly shaped by the proximal operator of the regularizer. For instance, an $\ell_1$ penalty promotes sparse displacements, while a projection penalty forces movement to occur primarily within a low-dimensional subspace.

Learning the Cost Function

The authors propose a framework to not only use these costs but to learn them from data:

  1. Numerical Scheme for Ground Truth: They provide an iterative algorithm to compute provably optimal Monge maps for any elastic cost. This allows for the creation of synthetic benchmarks where the ground-truth transport is known.
  2. Subspace Learning: By using a regularizer $\tau_{A}(\mathbf{z})=\|A^\perp \mathbf{z}\|^2_2$, the model learns a $p$-dimensional subspace (spanned by the rows of $A$) that captures the most relevant directions of data movement.
  3. Bilevel Optimization: To find the optimal parameters $\theta$ for a regularizer $\tau_\theta$, the authors use a bilevel loss. This involves differentiating through the Sinkhorn algorithm to update the cost function parameters via Riemannian gradient descent on the Stiefel manifold.

Key Results

The method was evaluated on both synthetic benchmarks and real-world single-cell RNA sequencing data.

The MSE ratio as a function of the regularizer strength $\gamma$. The plots demonstrate that as $\gamma$ increases towards an optimal value $\gamma^*$, the error in recovering the ground-truth map or subspace decreases significantly across different regularizer types.
  • Subspace Recovery: In high-dimensional synthetic tests, the algorithm recovered hidden ground-truth subspaces with near-perfect accuracy (errors < 1%).
  • Single-Cell RNA Prediction: On cancer cell line data (Srivatsan et al., 2020) projected to 256 dimensions, the "Elastic Subspace" approach outperformed standard Euclidean OT. By learning the low-dimensional subspace of drug response, the model produced more robust and biologically plausible predictions.
  • Sample Complexity: Theoretical analysis shows that if data movement is truly low-dimensional, the "Subspace MBO" estimator recovers the map at a rate depending on the subspace dimension ($p$) rather than the ambient dimension ($d$), effectively breaking the curse of dimensionality.

Conclusion

By introducing structured elastic costs and a framework to learn them, this work bridges the gap between the mathematical theory of Optimal Transport and the practical needs of high-dimensional data analysis. While the bilevel optimization adds computational complexity, the ability to infer the underlying "physics" of data movement provides a powerful new tool for predictive modeling in complex systems.

Summary updated

Abstract

Given a source and a target probability measure supported on $\mathbb{R}^d$, the Monge problem asks to find the most efficient way to map one distribution to the other. This efficiency is quantified by defining a \textit{cost} function between source and target data. Such a cost is often set by default in the machine learning literature to the squared-Euclidean distance, $\ell^2_2(\mathbf{x},\mathbf{y})=\tfrac12|\mathbf{x}-\mathbf{y}|_2^2$. Recently, Cuturi et. al '23 highlighted the benefits of using elastic costs, defined through a regularizer $\tau$ as $c(\mathbf{x},\mathbf{y})=\ell^2_2(\mathbf{x},\mathbf{y})+\tau(\mathbf{x}-\mathbf{y})$. Such costs shape the \textit{displacements} of Monge maps $T$, i.e., the difference between a source point and its image $T(\mathbf{x})-\mathbf{x})$, by giving them a structure that matches that of the proximal operator of $\tau$. In this work, we make two important contributions to the study of elastic costs: (i) For any elastic cost, we propose a numerical method to compute Monge maps that are provably optimal. This provides a much-needed routine to create synthetic problems where the ground truth OT map is known, by analogy to the Brenier theorem, which states that the gradient of any convex potential is always a valid Monge map for the $\ell_2^2$ cost; (ii) We propose a loss to \textit{learn} the parameter $\theta$ of a parameterized regularizer $\tau_\theta$, and apply it in the case where $\tau_{A}(\mathbf{z})=|A^\perp \mathbf{z}|^2_2$. This regularizer promotes displacements that lie on a low dimensional subspace of $\mathbb{R}^d$, spanned by the $p$ rows of $A\in\mathbb{R}^{p\times d}$.
BibTeX
@misc{klein2023learning,
  author = {Michal Klein and Aram-Alexandre Pooladian and Pierre Ablin and Eugène Ndiaye and Jonathan Niles-Weed and Marco Cuturi},
  title = {{Learning Costs for Structured Monge Displacements}},
  year = {2023},
  eprint = {2306.11895},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.11895},
}
Figure