📊 statistics

A Unified Kantorovich Duality for Multimarginal Optimal Transport

This paper establishes Kantorovich duality and proves the existence of optimal dual potentials within the class of mutually $c$ -conjugate families for multimarginal optimal transport with bounded continuous costs, covering both compact metric spaces and non-compact Polish spaces under a support-splitting condition.

Original authors: Yehya Cheryala, Mokhtar Z. Alaya, Salim Bouzebda

Published 2026-10-02

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yehya Cheryala, Mokhtar Z. Alaya, Salim Bouzebda

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine trying to move a pile of sand from one shape to another, but with a twist: you must do it while minimizing the total effort, and you are not just moving sand from one place to one destination. Instead, you are coordinating the movement of three, four, or even more distinct piles simultaneously. This is the heart of a mathematical field known as optimal transport. For centuries, mathematicians have studied how to move mass efficiently, a problem that began with a simple question about moving earth but has grown to underpin modern machine learning, economics, and statistics. The core challenge is finding the most efficient way to rearrange distributions of data or resources. While the two-pile version of this problem is well understood, the version involving many piles at once is far more complex. It is like trying to solve a puzzle where every piece must fit perfectly with every other piece at the same time, rather than just pairing them up.

The difficulty in these multi-pile scenarios often lies not just in finding the minimum cost, but in understanding the hidden structure of the solution itself. In the simpler two-pile case, mathematicians have long known that the optimal solution is governed by a pair of "potential" functions—think of them as invisible maps or guides that tell every grain of sand where to go. These maps are linked in a specific, reciprocal way. However, when you add more piles, the rules change. The question becomes whether a similar set of linked guides exists for the complex, multi-pile world, and if so, what they look like. Without these guides, it is difficult to predict how the solution will behave if the starting conditions change slightly, or to build reliable computer algorithms to solve the problem.

A team of researchers has now provided a definitive answer to this structural question for a broad class of these problems. They proved that even in the complex setting of multiple piles, there is indeed a special, canonical set of guides that governs the optimal movement. These guides are not just any set of functions; they are tightly interlocked. Each guide is mathematically derived from all the others, creating a self-consistent family where no single guide can be improved without changing the whole group. The researchers showed that this structure holds true whether the spaces where the piles exist are finite and compact, like a closed box, or infinite and open, like an endless plane, provided the cost of moving the sand does not explode to infinity.

The work is significant because it moves beyond simply stating that a solution exists. Instead, it identifies the exact nature of the solution's "skeleton." In the case of finite spaces, the researchers used a powerful argument involving the continuity of these guides to show that a perfect set of them must exist. They demonstrated that these guides inherit the smoothness of the cost function, meaning if the cost of moving sand changes smoothly, the guides do too. By carefully normalizing these guides to remove arbitrary shifts, they proved that one can always find a set that is perfectly balanced and optimal.

For the more challenging infinite spaces, the approach required a different strategy. The researchers showed that even though the space is unbounded, the optimal plan naturally concentrates its mass in a way that allows them to approximate the problem using finite chunks. They proved that by looking at the specific region where the optimal plan actually operates, one can construct a set of guides that are not only optimal but also bounded and well-behaved. This means that even in an infinite world, the rules governing the movement are local and manageable. The key insight was that the geometry of the optimal plan itself forces these guides to be mutually consistent, creating a stable structure that can be found and used.

These findings provide a solid foundation for future work in statistics and machine learning. Because the researchers have identified a specific, stable form for these guides, it becomes possible to study how small changes in the data affect the solution, a property known as stability. This is crucial for applications like training artificial intelligence models or analyzing large datasets, where one needs to know if a slight error in the input will cause a massive shift in the output. The paper establishes that the multi-pile transport problem has a natural, canonical representation, much like the two-pile case, but with a richer, more interconnected structure. This clarity allows mathematicians and scientists to move forward with confidence, knowing exactly what the optimal solution looks like and how it is built, rather than just knowing that it exists.

Technical Summary: A Unified Kantorovich Duality for Multimarginal Optimal Transport

Problem Statement
This paper investigates the Kantorovich duality for the Multimarginal Optimal Transport (MOT) problem. Given $K \geq 3$ Polish spaces $X_1, \dots, X_K$ , marginal probability measures $\mu_k \in \mathcal{P}(X_k)$ , and a cost function $c: X_1 \times \dots \times X_K \to \mathbb{R}$ , the primal problem seeks to minimize the transport cost:
$\text{MOT}_c(\mu_1, \dots, \mu_K) = \inf_{\pi \in \Pi(\mu_1, \dots, \mu_K)} \int c \, d\pi,$
where $\Pi(\mu_1, \dots, \mu_K)$ is the set of couplings with prescribed marginals. The dual problem seeks to maximize:
$\sup_{f \in \mathcal{F}_c} \sum_{k=1}^K \int f_k \, d\mu_k,$
subject to the constraint $\sum_{k=1}^K f_k(x_k) \leq c(x_1, \dots, x_K)$ .

While the equality of primal and dual values (duality identity) is well-established for general marginals (e.g., via Kellerer's theorem), this work focuses on two specific gaps in the multimarginal literature:

Dual Attainment: Proving the existence of an optimal dual family (maximizer) rather than just the value.
Structural Characterization: Identifying a canonical class of optimal dual potentials, specifically mutually $c$ -conjugate families, where each component $f_k$ is the partial $c$ -transform of the remaining components. This structure is crucial for statistical applications, numerical stability, and understanding the geometry of optimal supports.

Methodology
The authors treat the compact and non-compact cases separately, employing distinct analytical tools for each.

Compact Case:
- Convex Analysis: The dual problem is reformulated on the Banach space of continuous functions $E = C(X_1 \times \dots \times X_K)$ using two convex functionals, $\Theta$ (indicator of the cost constraint) and $\Xi$ (representing the additive structure of potentials).
- Fenchel–Rockafellar Duality: The duality identity is derived via the Fenchel–Rockafellar theorem.
- Compactness Arguments: To establish attainment, the authors utilize the Arzelà–Ascoli theorem. They demonstrate that partial $c$ -transforms inherit the modulus of continuity of the cost function $c$ . By normalizing the dual potentials (removing additive indeterminacy via zero-sum constants), they establish uniform boundedness and equicontinuity of maximizing sequences, ensuring the existence of a limit in the class of mutually $c$ -conjugate potentials.
Non-Compact (Polish) Case:
- Tightness and Truncation: Since global compactness is unavailable, the authors use the tightness of the marginals and Prokhorov's theorem to establish the narrow compactness of the set of couplings.
- Localization: They employ a truncation argument, restricting the problem to compact subsets $X_k^0$ where the marginals concentrate. The compact duality result is applied to these subsets.
- Normalization and Extension: Truncated dual potentials are normalized and adjusted component-wise to ensure uniform bounds dependent only on $\|c\|_\infty$ and $K$ . These are then extended to the full space by assigning sufficiently negative constants outside the compact sets, preserving global admissibility.
- Geometry of Supports: For dual attainment, the authors rely on the geometry of the support of an optimal plan $\pi^*$ . They utilize the concept of $c$ -splitting sets (where the dual constraint saturates). Using a Zorn's lemma argument on the componentwise order, they upgrade a real-valued splitting family to a mutually $c$ -conjugate one. The boundedness of $c$ ensures these potentials are bounded, yielding a bounded Borel measurable optimizer.

Key Contributions and Results

Unified Duality Identity (Theorems 1 & 2):
- The paper recovers the Kantorovich duality identity for bounded continuous costs on both compact metric spaces and general non-compact Polish spaces.
- In the non-compact case, this is achieved without coercivity assumptions on the cost, relying instead on the boundedness of $c$ and the tightness of marginals.
Existence of Canonical Dual Maximizers (Theorems 3 & 4):
- Compact Case: The dual maximum is attained by a family $f \in \mathcal{G}_c$ , where $\mathcal{G}_c$ is the class of admissible, mutually $c$ -conjugate families. This is proven via equicontinuity and the Arzelà–Ascoli theorem.
- Non-Compact Case: Under the assumption that the support of an optimal plan admits a real-valued splitting family, the dual problem admits a bounded, Borel measurable, mutually $c$ -conjugate optimizer. This is derived via $c$ -splitting set geometry and maximality arguments.
Structural Characterization:
- The paper establishes that mutually $c$ -conjugate potentials are the natural representatives of optimal dual families in the multimarginal setting. Unlike the two-marginal case where conjugacy is pairwise, the multimarginal case requires a $K$ -fold coupling where each component is recovered from the others via partial $c$ -transforms.

Significance and Claims
The authors position their work as a structural complement to existing literature. While prior results (e.g., Kellerer, Rigo, Gangbo–Świech) often focus on the primal-dual value equality or attain optimality by relaxing the problem (e.g., using finitely additive plans or generalized bidual objects), this paper:

Maintains $\sigma$ -additivity (standard probability measures).
Works with bounded continuous costs ( $c \in C_b$ ).
Addresses the genuine multimarginal setting ( $K \geq 3$ ).
Provides canonical maximizers within the class of mutually $c$ -conjugate families.

The paper claims that identifying these potentials as canonical representatives provides a necessary structural basis for further work in statistical and probabilistic MOT. Specifically, this structure is required for:

Stability analysis with respect to marginals and costs.
Differentiability of the transport value (essential for functional delta methods and central limit theorems in empirical transport).
Numerical approximation schemes that rely on $c$ -transforms.

The authors do not claim to solve the existence of optimal plans (which is known) or to remove all regularity assumptions on the cost, but rather to clarify the structure of the dual side under standard boundedness and continuity hypotheses.

More like this