Parameter tuning and model selection in Optimal Transport with semi-dual Brenier formulation

Adrien Vacher, François-Xavier VialardNeurIPS 2022 · OpenReview

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.

1D transport maps with varying regularization

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.

Correlation between semi-dual value and L2 error across models

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

Abstract

Over the past few years, numerous computational models have been developed to solve Optimal Transport (OT) in a stochastic setting, where distributions are represented by samples and where the goal is to find the closest map to the ground truth OT map, unknown in practical settings. So far, no quantitative criterion has yet been put forward to tune the parameter of these models and select maps that best approximate the ground truth. To perform this task, we propose to leverage the Brenier formulation of OT. Theoretically, we show that this formulation guarantees that, up to sharp a distortion parameter depending on the smoothness/strong convexity and a statistical deviation term, the selected map achieves the lowest quadratic error to the ground truth. This criterion, estimated via convex optimization, enables parameter tuning and model selection among entropic regularization of OT, input convex neural networks and smooth and strongly convex nearest-Brenier (SSNB) models. We also use this criterion to question the use of OT in Domain-Adaptation (DA). In a standard DA experiment, it enables us to identify the potential that is closest to the true OT map between the source and the target. Yet, we observe that this selected potential is far from being the one that performs best for the downstream transfer classification task.
BibTeX
@inproceedings{vacher2022parameter,
  author = {Adrien Vacher and François-Xavier Vialard},
  title = {{Parameter tuning and model selection in Optimal Transport with semi-dual Brenier formulation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=toleacrf7Hv},
}
Figure