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}$.
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:
- 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.
- 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.
- 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.
- 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