Relative-Translation Invariant Wasserstein Distance

Binshuai Wang, Qiwei Di, Ming Yin, Mengdi Wang, Quanquan Gu, Peng Wei

Abstract: We introduce a new family of distances, relative-translation invariant Wasserstein distances ($RW_p$), for measuring the similarity of two probability distributions under distribution shift. Generalizing it from the classical optimal transport model, we show that $RW_p$ distances are also real distance metrics defined on the quotient set $\mathcal{P}_p(\mathbb{R}^n)/\sim$ and invariant to distribution translations. When $p=2$, the $RW_2$ distance enjoys more exciting properties, including decomposability of the optimal transport model, translation-invariance of the $RW_2$ distance, and a Pythagorean relationship between $RW_2$ and the classical quadratic Wasserstein distance ($W_2$). Based on these properties, we show that a distribution shift, measured by $W_2$ distance, can be explained in the bias-variance perspective. In addition, we propose a variant of the Sinkhorn algorithm, named $RW_2$ Sinkhorn algorithm, for efficiently calculating $RW_2$ distance, coupling solutions, as well as $W_2$ distance. We also provide the analysis of numerical stability and time complexity for the proposed algorithm. Finally, we validate the $RW_2$ distance metric and the algorithm performance with three experiments: numerical validation, digits recognition, and similar thunderstorm detection. The experimental results report that our proposed algorithm significantly improves the computational efficiency of Sinkhorn in certain practical applications, and the $RW_2$ distance is robust to distribution translations compared with baselines.

Introduction

Optimal Transport (OT) and the resulting Wasserstein distance ($W_p$) are gold standards for comparing probability distributions. However, standard OT has a significant "blind spot": it is highly sensitive to absolute spatial positioning. In many real-world scenarios—such as domain adaptation, sensor calibration, or computer vision—the absolute coordinates of a distribution are often less important than its underlying "shape" or structure.

Consider a meteorologist comparing two identical thunderstorm patterns shifted geographically. To a human observer, these represent the same event. However, standard $W_2$ distance would report a massive discrepancy because the mass must be "transported" across the physical distance between the two locations. This paper introduces the Relative-Translation Invariant Wasserstein Distance ($RW_p$) to address this limitation, providing a metric that focuses on shape similarity by ignoring absolute translations.

The $RW_p$ Metric and the Quadratic Case

The authors propose Relative Translation Optimal Transport (ROT). Instead of simply finding the best way to move mass from distribution $\mu$ to $\nu$, ROT identifies the optimal translation $s$ to apply to one distribution before performing the transport. This formulation defines a real distance metric on the "quotient set" of distributions, effectively treating all translated versions of a distribution as the same object.

The Quadratic Case ($RW_2$)

When $p=2$, the mathematical framework becomes particularly elegant. The authors prove a Pythagorean relationship that decomposes the total distribution shift ($W_2$) into two distinct components: $$W_2^2(\mu, \nu) = \|\bar{\mu} - \bar{\nu}\|_2^2 + RW_2^2(\mu, \nu)$$

In this view, the distribution shift is explained through a bias-variance perspective: the difference in means ($\bar{\mu}, \bar{\nu}$) represents the "bias" or mean-shift, while $RW_2$ captures the "variance" or shape-shift.

The Pythagorean relationship between $W_2$ and $RW_2$.

The $RW_2$ Sinkhorn Algorithm

Standard Sinkhorn iterations, used to approximate OT solutions, often suffer from numerical instability when distributions are far apart. In such cases, the exponential terms in the cost matrix can lead to numerical overflow or "NaN" errors.

The authors introduce the $RW_2$ Sinkhorn algorithm, which leverages the translation invariance of the optimal transport plan. By "pre-centering" the distributions based on their means before running the iterations, the algorithm ensures the cost matrix contains smaller values. This simple yet mathematically sound centering trick significantly improves numerical stability and convergence speed for shifted data.

Key Results and Applications

The approach was validated using synthetic datasets, perturbed MNIST digits, and real-world meteorological data.

Numerical Stability

Numerical experiments demonstrated that as the translation distance $s$ increases, the computational error of the standard Sinkhorn algorithm grows rapidly. Conversely, the $RW_2$ Sinkhorn algorithm maintains a low, stable error rate regardless of the translation magnitude, confirming its robustness for large-scale shifts.

Computational error of $RW_2$ Sinkhorn vs. standard Sinkhorn.

Real-World Performance

  • MNIST Digit Recognition: On a task involving translated handwritten digits, $RW_2$ maintained high classification accuracy even as translation distance increased, whereas performance for standard metrics like $L_1, L_2,$ and $W_2$ plummeted.
  • Thunderstorm Detection: Using the Multi-Radar Multi-Sensor (MRMS) dataset, $RW_2$ successfully identified structurally similar storm patterns that were geographically distant. Standard $W_2$ was often "distracted" by proximity, picking dissimilar storms simply because they were closer in space.

Conclusion

The $RW_p$ distance provides a powerful framework for comparing distributions based on shape rather than location. By establishing a Pythagorean relationship for $RW_2$, the authors provide a rigorous way to analyze distribution shifts through a bias-variance lens. While the current work focuses on translation invariance, future research may explore incorporating other group invariances, such as rotation and scaling, into the optimal transport framework.

Summary updated

Abstract

We introduce a new family of distances, relative-translation invariant Wasserstein distances ($RW_p$), for measuring the similarity of two probability distributions under distribution shift. Generalizing it from the classical optimal transport model, we show that $RW_p$ distances are also real distance metrics defined on the quotient set $\mathcal{P}_p(\mathbb{R}^n)/\sim$ and invariant to distribution translations. When $p=2$, the $RW_2$ distance enjoys more exciting properties, including decomposability of the optimal transport model, translation-invariance of the $RW_2$ distance, and a Pythagorean relationship between $RW_2$ and the classical quadratic Wasserstein distance ($W_2$). Based on these properties, we show that a distribution shift, measured by $W_2$ distance, can be explained in the bias-variance perspective. In addition, we propose a variant of the Sinkhorn algorithm, named $RW_2$ Sinkhorn algorithm, for efficiently calculating $RW_2$ distance, coupling solutions, as well as $W_2$ distance. We also provide the analysis of numerical stability and time complexity for the proposed algorithm. Finally, we validate the $RW_2$ distance metric and the algorithm performance with three experiments. We conduct one numerical validation for the $RW_2$ Sinkhorn algorithm and show two real-world applications demonstrating the effectiveness of using $RW_2$ under distribution shift: digits recognition and similar thunderstorm detection. The experimental results report that our proposed algorithm significantly improves the computational efficiency of Sinkhorn in certain practical applications, and the $RW_2$ distance is robust to distribution translations compared with baselines.
BibTeX
@misc{wang2024relative,
  author = {Binshuai Wang and Qiwei Di and Ming Yin and Mengdi Wang and Quanquan Gu and Peng Wei},
  title = {{Relative-Translation Invariant Wasserstein Distance}},
  year = {2024},
  eprint = {2409.02416},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2409.02416},
}
Figure