Optimal Transport (OT) has become a powerful framework for finding the most efficient way to "move" one probability distribution onto another. It is now a staple in fields ranging from biology (mapping cell trajectories) to computer vision (color transfer) and machine learning (domain adaptation).
However, as presented at NeurIPS 2022, practitioners face a fundamental "blind spot": how do we know if our transport map is actually accurate when we don't have a ground truth to compare it against?
The Problem: Flying Blind in Optimal Transport
There are dozens of ways to compute an OT map—using Sinkhorn iterations, Input Convex Neural Networks (ICNNs), or smooth nearest-neighbor models. Each of these methods comes with its own set of hyperparameters, such as regularization strength.
In real-world scenarios, the "true" map is unknown. Consequently, practitioners have lacked a quantitative way to decide which model or parameter set is the most accurate.
Without a ground truth, selecting the right regularization parameter (like $\epsilon$ in the figure above) is essentially guesswork. To solve this, the authors propose a "semi-dual" criterion based on the Brenier formulation of Optimal Transport to perform principled parameter tuning and model selection.
Methods: The Semi-Dual Criterion
The authors leverage the semi-dual Brenier formulation. In classical OT, the dual problem involves two potential functions subject to a strict constraint. The authors simplify this into a single convex functional:
$$J_{\mu,\nu}(f) := \int f d\mu + \int f^* d\nu$$
where $f^*$ is the Fenchel-Legendre transform of $f$.
Key Technical Innovations: * Theoretical Bound: The authors prove that the difference between the semi-dual value of a candidate map and the true map is bounded by the $L^2$ distance (quadratic error) between them. This mathematically justifies using the semi-dual as a proxy for accuracy. * Self-Concordance for Sinkhorn: They show that Sinkhorn potentials are "self-concordant." This technical optimization property allows them to use second-order (Newton-type) methods to compute the Fenchel conjugate much faster and more stably than standard gradient descent. * Model Benchmarking: The criterion is applied to three popular OT models: Input Convex Neural Networks (ICNNs), Sinkhorn Potentials (entropic regularization), and Smooth and Strongly convex Nearest Brenier (SSNB) models.
Key Insights and Results
To validate their criterion, the authors tested it on synthetic 8-dimensional distributions (where the ground truth is known) and the Caltech-Office Dataset for Domain Adaptation (DA).
The Semi-Dual as a Universal Ruler
The most significant takeaway is that the semi-dual objective is a reliable, computable metric that correlates almost perfectly with the true quadratic error across different model architectures.
As shown above, minimizing the test semi-dual value reliably minimizes the actual $L^2$ error on the maps, particularly for Sinkhorn and SSNB models. This provides a much-needed "compass" for researchers. Using this criterion, the authors successfully identified optimal regularization parameters and found that the SSNB model generally outperformed ICNNs by nearly an order of magnitude in terms of quadratic error.
The Domain Adaptation Paradox
Perhaps the most surprising finding occurred in the Domain Adaptation experiments. The authors discovered that the potential function mathematically closest to the true OT map (according to their criterion) was often not the one that performed best for the downstream classification task.
This suggests that the common assumption in DA—that finding the "true" OT map between domains leads to the best feature transfer—might be flawed. Sometimes, a "distorted" map is actually more useful for classification than a mathematically "perfect" one.
Limitations and Future Work
- Regularity Assumptions: The strongest theoretical guarantees rely on the potentials being $M$-smooth and $\gamma$-strongly convex. While the criterion works empirically even when these aren't strictly met, the theory is most robust for "well-behaved" functions.
- Quadratic Cost Only: The current formulation is specific to the quadratic cost ($L^2$ distance). Extending this to more general cost functions remains an open area for research.
- The DA Gap: The disconnect between OT accuracy and classification accuracy in Domain Adaptation opens a fascinating new research direction: how do we design OT criteria that are "task-aware" rather than just "geometry-aware"?
Summary updated