Constrained Approximate Optimal Transport Maps

Eloi Tanguy, Agnès Desolneux, Julie Delon

TL;DR

This paper provides a rigorous framework for finding "best-fit" Optimal Transport (OT) maps when the ideal map is either too complex or doesn't exist. By restricting the search to specific function classes—such as Lipschitz neural networks or gradients of convex functions—the authors establish theoretical guarantees for existence and develop practical numerical tools for applications like robust color transfer.

What Problem Does This Paper Address?

In classical Optimal Transport, the goal is to find a map $T$ that perfectly pushes a source distribution $\mu$ onto a target $\nu$ ($T\#\mu = \nu$) while minimizing a displacement cost. However, in many real-world scenarios, such a map might not exist (e.g., if $\mu$ is continuous and $\nu$ is discrete) or might be too "wild" for practical use.

In machine learning, we often want the transport map to belong to a specific, well-behaved class $G$ (like a neural network with a bounded Lipschitz constant). This paper tackles the Constrained Approximate OT Map problem: finding the map $g \in G$ that gets the push-forward $g\#\mu$ as close as possible to the target $\nu$ in terms of OT cost. This is particularly relevant for generative modeling and domain adaptation where regularity and robustness are paramount.

Methods

The authors bridge the gap between abstract OT theory and practical optimization through several key approaches:

  • Theoretical Existence: They prove that a minimizer exists for generic subclasses of $L$-Lipschitz functions, including neural networks with Lipschitz activations and gradients of strongly convex potentials.
  • Alternate Minimization: For the squared Euclidean cost ($W_2$), they show the problem can be viewed as an alternating optimization between a transport plan $\pi$ and a map $g$. When $\pi$ is fixed, finding $g$ becomes an $L^2$ projection of a "barycentric map" onto the class $G$.
  • Numerical Toolkits:
    • QCQP for Convex Potentials: They use Quadratically Constrained Quadratic Programming to solve for maps that are gradients of strongly convex functions.
  • Kernel Methods: They introduce a method to find maps within a Reproducing Kernel Hilbert Space (RKHS), providing a flexible, non-parametric approach for discrete data.
  • SGD for Neural Networks: They analyze the convergence of Stochastic Gradient Descent for training neural network maps, utilizing the framework of semi-algebraic analysis to handle non-smoothness.

Datasets

The paper evaluates these methods using:

  • Synthetic Toy Datasets: 1D and 2D Gaussian mixtures and uniform distributions used to illustrate existence, uniqueness, and the failure of 1D equivalences in higher dimensions.
  • Color Transfer Application: Pairs of images where the goal is to map the color palette of a source image to a target image. This demonstrates the map's ability to generalize to new images and its inherent robustness to outliers.

Key Insights and Ideas

  • The Necessity of Lipschitz Constraints: The authors demonstrate that without a Lipschitz constraint, a solution might not even exist. For example, if a target distribution has "gaps," a continuous map cannot perfectly reach both sides without being forced to be discontinuous.
  • The 1D vs. High-Dimension Divide: In 1D, the problem simplifies beautifully: the global solution is just the $L^2$ projection of the optimal transport plan's barycentric map onto $G$. The authors provide a counter-example showing this elegant property does not hold in 2D or higher.
  • Implicit Robustness: A major "aha" moment is that constraints on the function class $G$ act as a natural regularizer. If the target distribution contains outliers, a Lipschitz-constrained map will effectively ignore them because "reaching" those outliers would require a slope that exceeds the allowed Lipschitz constant.
  • Generalization: Unlike standard discrete OT, which only tells you where specific points go, these constrained maps are defined on the entire space. This allows a map learned on one pair of images (color transfer) to be applied to a completely new "evaluation" image.

Key Results

  • Theoretical Foundation: Established existence and uniqueness results for a wide range of constrained map problems.
  • Algorithmic Convergence: Proved that SGD for neural network-based OT maps converges to Clarke critical points.
  • Robust Color Transfer: Qualitative results show that constrained maps produce more natural color transfers than unconstrained ones, specifically by avoiding the "color bleeding" caused by outliers in the target image's distribution.
  • Computational Contributions: The authors contributed a solver for the QCQP problem to the popular Python Optimal Transport (POT) library.

Limitations and Future Work

  • Uniqueness: While existence is well-handled, uniqueness remains a difficult question for general function classes in high dimensions, with the authors conjecturing it isn't guaranteed for $d \geq 2$.
  • Computational Complexity: The QCQP approach for convex potentials has a prohibitive $O(n^4)$ complexity, making it difficult to scale to very large datasets without further optimization.
  • RKHS Integration: The authors suggest future work on how to better incorporate geometric constraints (like convexity) directly into the RKHS representation to combine the flexibility of kernels with the structural guarantees of convex analysis.

Summary updated

Abstract

We investigate finding a map $g$ within a function class $G$ that minimises an Optimal Transport (OT) cost between a target measure $ν$ and the image by $g$ of a source measure $μ$. This is relevant when an OT map from $μ$ to $ν$ does not exist or does not satisfy the desired constraints of $G$. We address existence and uniqueness for generic subclasses of $L$-Lipschitz functions, including gradients of (strongly) convex functions and typical Neural Networks. We explore a variant that approaches a transport plan, showing equivalence to a map problem in some cases. For the squared Euclidean cost, we propose alternating minimisation over a transport plan $π$ and map $g$, with the optimisation over $g$ being the $L^2$ projection on $G$ of the barycentric mapping $\overlineπ$. In dimension one, this global problem equates the $L^2$ projection of $\overline{π^*}$ onto $G$ for an OT plan $π^*$ between $μ$ and $ν$, but this does not extend to higher dimensions. We introduce a simple kernel method to find $g$ within a Reproducing Kernel Hilbert Space in the discrete case. We present numerical methods for $L$-Lipschitz gradients of $\ell$-strongly convex potentials, and study the convergence of Stochastic Gradient Descent methods for Neural Networks. We finish with an illustration on colour transfer, applying learned maps on new images, and showcasing outlier robustness.
BibTeX
@inproceedings{tanguy2025constrained,
  author = {Eloi Tanguy and Agnès Desolneux and Julie Delon},
  title = {{Constrained Approximate Optimal Transport Maps}},
  booktitle = {ESAIM},
  year = {2025},
  doi = {10.1051/cocv/2025057},
}
Figure