TL;DR
This paper investigates how much the "pushforward" of a probability measure by an optimal transport map can change when the original measure is slightly perturbed. The authors demonstrate that this change is bounded by a "Hölder-like" relationship, even when the transport map has singularities. This finding is crucial for understanding the stability of various computational methods that rely on optimal transport.
What Problem Does This Paper Address?
The paper tackles the problem of quantitative stability for the pushforward operation in the context of optimal transport. In essence, optimal transport deals with finding the most efficient way to move mass from one probability distribution to another. A key tool in this field is the optimal transport map, which dictates how individual points or infinitesimal pieces of mass should be moved.
The authors are interested in what happens when we perturb the source probability measure slightly. How much does the target measure, obtained by pushing the source measure through a fixed optimal transport map, change? This is important because many practical applications, like machine learning and numerical simulations, deal with approximations of probability measures. If the pushforward operation is not stable, small errors in the source measure could lead to large errors in the resulting distribution, undermining the reliability of these methods.
A significant challenge arises when the optimal transport map is not smooth (i.e., it has "singularities"). These singularities can arise from the underlying cost function or the geometry of the problem. The paper aims to provide a quantitative bound on the change in the pushforward measure even in these non-smooth scenarios, under minimal assumptions.
Methods
The core of the paper's contribution lies in establishing a tight Hölder-behavior for the pushforward operation. This means the change in the pushed-forward measure is controlled by a power of the change in the original measure, where the power is less than 1.
The authors' proof relies on a novel technical result: a new bound that quantifies the size of the singular sets of a convex and Lipschitz continuous function on a bounded domain. Singular sets are points where the function is not differentiable, which is where the "non-smoothness" of the transport map originates. By bounding the "size" of these singular sets, they can control the instabilities they introduce.
Specifically, they introduce a concept of covering numbers for these singular sets, which essentially measures how many small balls are needed to cover them. This allows them to relate the properties of the convex function (and thus the transport map) to the stability of the pushforward.
The paper also leverages existing tools from optimal transport theory, including:
- Wasserstein distances: A standard metric for comparing probability measures.
- Kantorovich dual problems: A pair of optimization problems that provide a way to find optimal transport potentials and maps.
- Convex analysis: Essential for understanding the properties of the cost functions and potentials.
Datasets
Not discussed in the paper. The paper focuses on theoretical results and does not present empirical evaluations on specific datasets.
Key Insights and Ideas
- Hölder stability is the best we can hope for: The paper demonstrates that even under minimal assumptions, the pushforward operation by an optimal transport map exhibits a Hölder-like stability, not a Lipschitz one. This is a fundamental limitation that needs to be accounted for in applications.
- Singularities are the source of instability: The key insight is that the instabilities in the pushforward operation are directly linked to the singularities of the underlying convex potential function that defines the transport map.
- Quantifying singularity size is crucial: The paper introduces a new technical tool to bound the "size" of these singular sets, which is instrumental in proving the main stability result. This bound is shown to be tight, meaning it cannot be significantly improved.
- Minimal assumptions are sufficient: The results hold under very general conditions, requiring only that the potential function is convex and Lipschitz continuous, and that one of the measures is absolutely continuous with a bounded density. This broad applicability makes the findings relevant to a wide range of problems.
Key Results
The main result is Theorem 3.2, which provides a quantitative bound on the difference between the pushforward of two measures, $p$ and $\tilde{p}$, by a fixed optimal transport map $T_\phi$. Specifically, it shows that:
$W_q((T_\phi)\#\rho, (T_\phi)\#\tilde{\rho}) \leq C \cdot W_r(\rho, \tilde{\rho})^{\alpha}$
where:
- $W_q$ and $W_r$ are Wasserstein distances of order $q$ and $r$.
- $C$ is a constant that depends on the dimension, the domain size, the Lipschitz constant of $\phi$, the density bound of $\rho$, and the cost function's power $p$.
- $\alpha$ is a power that is shown to be $1/3$ in the case of the $p=2$ cost (Wasserstein-2 distance).
This result establishes a tight Hölder-behavior for the pushforward operation. The paper also presents negative results (Examples 1.2, 1.3, 1.4) that demonstrate this Hölder behavior is indeed the best possible under the given minimal assumptions.
Limitations and Future Work
- Compact Setting: The main result is stated for measures supported within a bounded domain $\Omega$. Extending these results to unbounded domains would be a natural next step.
- Specific Cost Function: While the paper generalizes to $p$-costs ($||x-y||^p$), the core technical results and examples often focus on the $p=2$ case. Further exploration of the behavior for different $p$ values could be beneficial.
- Regularity of Potential: The paper highlights that the stability results are particularly important when the optimal transport potential $\phi$ is not smooth. However, the proofs often rely on properties of $\phi$ (like being Lipschitz) and its subdifferential. Investigating the precise interplay between the degree of non-smoothness and the resulting stability would be valuable.
- Numerical Implications: While the paper motivates its study with applications in numerical methods, future work could focus on directly translating these theoretical stability bounds into practical improvements or error analyses for specific algorithms.
- General Ground Costs: The paper primarily focuses on the $p$-cost $c(x,y) = ||x-y||^p$. Extending the stability results to more general ground costs would broaden their applicability.
Summary updated