Relative-Translation Invariant Wasserstein Distance

## Abstract

Abstract We introduce a new family of distances, relative-translation invariant Wasserstein distances ( R ⁢ W p 𝑅 subscript 𝑊 𝑝 RW_{p} italic_R italic_W start_POSTSUBSCRIPT italic_p end_POSTSUBSCRIPT ), for measuring the similarity of two probability distributions under distribution shift. Generalizing it from the classical optimal transport model, we show that R ⁢ W p 𝑅 subscript 𝑊 𝑝 RW_{p} italic_R italic_W start_POSTSUBSCRIPT italic_p end_POSTSUBSCRIPT distances are also real distance metrics defined on the quotient set 𝒫 p ( ℝ n ) / ∼ \mathcal{P}_{p}(\mathbb{R}^{n})/\sim caligraphic_P start_POSTSUBSCRIPT italic_p end_POSTSUBSCRIPT ( blackboard_R start_POSTSUPERSCRIPT italic_n end_POSTSUPERSCRIPT ) / ∼ and invariant to distribution translations. When p = 2 𝑝 2 p=2 italic_p = 2 , the R ⁢ W 2 𝑅 subscript 𝑊 2 RW_{2} italic_R italic_W start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT distance enjoys more exciting properties, including decomposability of the optimal transport model, translation-invariance of the R ⁢ W 2 𝑅 subscript 𝑊 2 RW_{2} italic_R italic_W start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT distance, and a Pythagorean relationship between R ⁢ W 2 𝑅 subscript 𝑊 2 RW_{2} italic_R italic_W start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT and the classical quadratic Wasserstein distance ( W 2 subscript 𝑊 2 W_{2} italic_W start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT ). Based on these properties, we show that a distribution shift, measured by W 2 subscript 𝑊 2 W_{2} italic_W start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT distance, can be explained in the bias-variance perspective. In addition, we propose a variant of the Sinkhorn algorithm, named R ⁢ W 2 𝑅 subscript 𝑊 2 RW_{2} italic_R italic_W start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT Sinkhorn algorithm, for efficiently calculating R ⁢ W 2 𝑅 subscript 𝑊 2 RW_{2} italic_R italic_W start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT distance, coupling solutions, as well as W 2 subscript 𝑊 2 W_{2} italic_W start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT distance. We also provide the analysis of numerical stability and time complexity for the proposed algorithm. Finally, we validate the R ⁢ W 2 𝑅 subscript 𝑊 2 RW_{2} italic_R italic_W start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT distance metric and the algorithm performance with three experiments. We conduct one numerical validation for the R ⁢ W 2 𝑅 subscript 𝑊 2 RW_{2} italic_R italic_W start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT Sinkhorn algorithm and show two real-world applications demonstrating the effectiveness of using R ⁢ W 2 𝑅 subscript 𝑊 2 RW_{2} italic_R italic_W start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT 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 R ⁢ W 2 𝑅 subscript 𝑊 2 RW_{2} italic_R italic_W start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT distance is robust to distribution translations compared with baselines.

## 1 Introduction

Optimal transport (OT) theory and Wasserstein distance (Peyré and Cuturi, ; Janati et al., ; Villani, ) provide a rigorous measurement of similarity between two probability distributions. Numerous state-of-the-art machine learning applications are developed based on the OT formulation and Wasserstein distances, including domain adaptation, score-based generative model, Wasserstein generative adversarial networks, Fréchet inception distance (FID) score, Wasserstein auto-encoders, distributionally robust Markov decision processes, distributionally robust regressions, graph neural networks based objects tracking, etc (Shen et al., ; Pinheiro, ; Courty et al., ; Damodaran et al., ; Courty et al., ; Arjovsky et al., ; Heusel et al., ; Tolstikhin et al., ; Clement and Kroer, ; Shafieezadeh-Abadeh et al., ; Chen and Paschalidis, ; Yu et al., ; Sarlin et al., ). However, the classical Wasserstein distance has major limitations in certain machine learning and computer vision applications. For example, a meteorologist often focuses on identifying similar weather patterns in a large-scale geographical region Wang et al. (); Roberts and Lean (); Dixon and Wiener (), where he/she cares more about the ‘‘shapes’’ of weather events rather than their exact locations. The weather events are represented as images or point clouds from the radar reflectivity map. Here the classical Wasserstein distance is not useful since the relative location difference or relative translation between two very similar weather patterns will add to the Wasserstein distance value. Another example is the inevitable distribution shift in real-world datasets. A distribution shift may be introduced by sensor calibration error, environment changes between train and test datasets, simulation to real-world (*sim2real*) deployment, etc. Motivated by these practical use cases and the limitations of Wasserstein distances, we ask the following research question:

*Can we find a new distance metric and a corresponding efficient algorithm to measure the similarity between probability distributions (and their supports) regardless of their relative translation?*

To answer this research question, we introduce the relative translation optimal transport (ROT) problem and the corresponding relative-translation invariant Wasserstein distance $RW_{p}$. We then focus on the quadratic case ($p=2$) and identify three exciting properties of the $RW_{2}$ distance. We leverage these properties to design a variant of the Sinkhorn algorithm to compute $RW_{2}$ distance, coupling solutions, as well as $W_{2}$ distance. In addition, we provide analysis and numerical experiment results to demonstrate the effectiveness of the new $RW_{2}$ distance against translation shifts. Finally, we show the scalability and practical usage of the $RW_{2}$ in a real-world meteorological application.

#### Contributions.

The main contributions of this paper are highlighted as follows: *(a)* we introduce a family of new similarity metrics, relative-translation invariant Wasserstein ($RW_{p}$) distances, which are real distance metrics like the Wasserstein distance and invariant to the relative translation of two distributions; *(b)* we identify three useful properties of the quadratic case $RW_{2}$ to support our algorithm design: decomposability of the ROT problem, translation-invariance of both the ROT problem solution and the resulted $RW_{2}$, and Pythagorean relationship between $RW_{2}$ and the classical $W_{2}$; *(c)* we show that the $RW_{2}$ can be used to analyze and explain a general distribution shift (measured by $W_{2}$) in the bias-variance perspective; and *(d)* we propose an efficient variant of Sinkhorn algorithm, named the $RW_{2}$ Sinkhorn, for calculating $RW_{2}$ distance, coupling solutions as well as $W_{2}$ distance with significantly reduced computational complexity and enhanced numerical stability under relative translations. Empirically, we report promising performance from the proposed $RW_{2}$ distance when the relative translation is large, and the $RW_{2}$ Sinkhorn algorithm in illustrative numerical examples and a large-scale real-world task for similar weather detection. Figure 3(a) shows our major findings in this work.

#### Notations.

Assume that $\mathcal{P}_{p}(\mathbb{R}^{n})$ is the set of all probability distributions with finite moments of order $p$ defined on the space $\mathbb{R}^{n}$ and $\mathcal{M}(\mathbb{R}^{n})$ is the set of all probability distributions with finite supports defined on the space $\mathbb{R}^{n}$. $\mathbb{R}_{*}^{m_{1}\times m_{2}}$ represents the set of all $m_{1}\times m_{2}$ matrices with non-negative entries. $[\mu]$ represents the equivalence class (orbit) of $\mu$ under the shift equivalence relation in $\mathcal{P}_{p}(\mathbb{R}^{n})$. $\bar{\mu}$ represents the mean of probability distribution $\mu$ (data points). $\mathop{{}\mathbf{e}}\nolimits_{m}$ denotes a vector in $\mathbb{R}^{m}$ where all elements are ones. $./$ represents the component-wise division.

#### Related work.

Optimal transport theory is a classical area of mathematics with strong connections to probability theory, diffusion processes and PDEs. Due to the vast literature, we refer readers to (Villani and Society, ; Ambrosio et al., ; Villani, ; Oll, ) for comprehensive reviews. Computational OT methods have been widely explored, including Greenkhorn algorithm (Altschuler et al., ), Network Simplex method (Peyré and Cuturi, ), Wasserstein gradient flow (Mokrov et al., ; Fan et al., ), neural network approximation (Chen and Wang, ). Significant research has also been conducted on Wasserstein distances, such as the sliced Wasserstein distance (Nguyen and Ho, ; Mahey et al., ; Nguyen and Ho, ), Gromov-Wasserstein distance (Sejourne et al., ; Le et al., ; Alvarez-Melis et al., ), etc. Other important topics include Wasserstein barycenter (Guo et al., ; Vaskevicius and Chizat, ; Korotin et al., ; Lin et al., ; Korotin et al., ) and unbalanced optimal transport (Nguyen et al., ; Chizat, ).

## 2 Preliminaries

Before delving into the details of our proposed method, it is essential to focus on the groundwork with an introduction to key aspects of classical optimal transport theory and formulations. This foundation will support the subsequent derivations and proofs presented in Section 3.

### 2.1 Optimal Transport Theory

The optimal transport theory focuses on finding the minimal-cost transport plans for moving one probability distribution to another probability distribution in a metric space. The core of this theory involves a cost function, denoted as $c(x,y)$, alongside two probability distributions, $\mu(x)$ and $\nu(y)$. The optimal transport problem is to find the transport plans (coupling solutions) that minimize the cost of moving the distribution $\mu(x)$ to $\nu(y)$, under the cost function $c(x,y)$. Although the cost function can take any non-negative form, our focus will be on those derived from the $p$-norm, expressed as $\|x-y\|_{p}^{p}$ for $p\geq 1$, because the optimal transport problem is well-defined (Villani, ).

Assuming $\mu(x)$ as the source distribution and $\nu(y)$ as the target distribution, $\mu,\nu\in\mathcal{P}_{p}(\mathbb{R}^{n})$, we can formulate the optimal transport problem as a functional optimization problem, detailed below:

###### Definition 1 ( $p$ -norm optimal transport problem ( Villani , 2009 ) ) .

$$ $\text{OT}(\mu,\nu,p)=\underset{\gamma\in\Gamma\in\mathbb{R}^{n}}{\min}\int_{ \mathbb{R}^{n}}\|x-y\|_{p}^{p}d\gamma(x,y),$ (1) $$

with $\Gamma(\mu,\nu)=\{\gamma\in\mathcal{P}_{p}(\mathbb{R}^{n}\times\mathbb{R}^{n})
|\int_{\mathbb{R}^{n}}\gamma(x,y)dx=\nu(y),\;\int_{\mathbb{R}^{n}}\gamma(x,y)
dy=\mu(x),\;\gamma(x,y)\geq 0\}.\small$

Here $\gamma(x,y)$ represents the transport plan (or the coupling solution), indicating the amount of probability mass transported from source support $x$ to target support $y$. The objective function is to minimize the total transport cost, which is the integrated product cost of distance and transported mass across all source-target pairs $(x,y)$.

After the foundational optimal transport problem is outlined, we can introduce a family of real metrics, the Wasserstein distances, for measuring the distance between probability distributions on the set $\mathcal{P}_{p}(\mathbb{R}^{n})$. These distances are defined based on the optimal transport problem.

###### Definition 2 (Wasserstein distances ( Villani , 2009 ) ) .

The Wasserstein distance between $\mu$ and $\nu$ is the $p$th root of the minimal total transport cost from $\mu$ to $\nu$, denoted as $W_{p},(p\geq 1)$:

$$ $W_{p}(\mu,\nu)=\text{OT}(\mu,\nu,p)^{\frac{1}{p}}.$ (2) $$

The Wasserstein distance is a powerful tool for assessing the similarity between probability distributions. It is a real metric admitting the properties of indiscernibility, non-negativity, symmetry, and triangle inequality Villani (). Meanwhile, it is well-defined for any probability distribution pairs, including discrete-discrete, discrete-continuous, and continuous-continuous.

For practical machine learning applications, the functional optimization described in Equation (1) can be adapted into a discrete optimization framework. This adaptation involves considering the distributions, $\mu$ and $\nu$, as comprised of finite supports, $\{x_{i}\}_{i=1}^{m_{1}}$ and $\{y_{j}\}_{j=1}^{m_{2}}$, with corresponding probability masses $\{a_{i}\}_{i=1}^{m_{1}}$ and $\{b_{j}\}_{j=1}^{m_{2}}$, respectively, where $m_{1}$ and $m_{2}$ are the number of supports (data points). Since all $m_{1}$ and $m_{2}$ are finite numbers, we can use an $m_{1}\times m_{2}$ matrix $C$ to represent the cost between supports, where each entry represents the transporting cost from $x_{i}$ to $y_{j}$, i.e., $C_{ij}=\|x_{i}-y_{j}\|_{p}^{p}$. This discrete version of the optimal transport problem can then be expressed as a linear programming problem, denoted as $\text{OT}(\mu,\nu,p)$:

$$ $\text{OT}(\mu,\nu,p)=\underset{P_{ij}\in\Pi(\mu,\nu)}{\min}\sum_{i=1}^{m_{1}} \sum_{j=1}^{m_{2}}C_{ij}P_{ij},$ (3) $$

with $\Pi(\mu,\nu)=\{P\in\mathbb{R}_{*}^{m_{1}\times m_{2}}|P\mathop{{}\mathbf{e}}
\nolimits_{m_{1}}=a,P^{\top}\mathop{{}\mathbf{e}}\nolimits_{m_{2}}=b\}$, where $\Pi(\mu,\nu)$ is the feasible set of this problem, vectors $a$ and $b$ are the probability masses of $\mu$ and $\nu$, respectively. coupling solutions $P_{ij}$ indicates the amount of probability mass transported from the source point $x_{i}$ to the target point $y_{j}$. This linear programming approach provides a scalable and efficient way for solving discrete optimal transport problems in various data-driven applications.

###### Definition 1 ( p 𝑝 p italic_p -norm optimal transport problem ( Villani , 2009 ) ) .

###### Definition 2 (Wasserstein distances ( Villani , 2009 ) ) .

### 2.2 Sinkhorn Algorithm

Equation (3) formulates a linear programming problem, which is commonly solved by simplex methods or interior-point methods Peyré and Cuturi (). Because of the special structure of the feasible set $\Pi(\mu,\nu)$, another approach for solving this problem is to transform it into a matrix scaling problem by adding an entropy regularization in the objective function Cuturi (). The matrix scaling problem can be solved by the Sinkhorn algorithm, which is an iterative algorithm that enjoys both efficiency and scalability. In detail, the Sinkhorn algorithm will initially assign $u^{(0)}$ and $v^{(0)}$ with vector $\mathop{{}\mathbf{e}}\nolimits_{m_{1}}$ and $\mathop{{}\mathbf{e}}\nolimits_{m_{2}}$, then the vector $u^{(k)}$ and $v^{(k)}$ $(k\geq 1)$ are updated alternatively by the following equations:

$$ $u^{(k+1)}\leftarrow a./Kv^{(k)},\quad v^{(k+1)}\leftarrow b./K^{\top}u^{(k+1)},$ (4) $$

where $K_{ij}=e^{-\frac{C_{ij}}{\lambda}}$ ($\lambda$ is the coefficient of the entropy regularized term) and the division is component-wise. When the convergence precision is satisfied, the coupling solution $P$ will be calculated by the matrix $\text{diag(u)}K\text{diag(v)}$. It has been proved the solution calculated by the Sinkhorn algorithm can converge to the exact coupling solution of the linear programming model, as $\lambda$ goes to zero (Cominetti and Martín, ). One caveat of this calculation is the exponent operation, which may cause ‘‘division by zero", we will show how we can improve the numerical stability in Section 4.

## 3 Relative Translation Optimal Transport and R ⁢ W p 𝑅 subscript 𝑊 𝑝 RW_{p} italic_R italic_W start_POSTSUBSCRIPT italic_p end_POSTSUBSCRIPT Distances

Here we present the relative translation optimal transport model and the $RW_{p}$ distances. We first introduce the general case of the relative translation optimal transport problem and the $RW_{p}$ distances. We will then focus on the quadratic $RW_{2}$ case and its properties.

### 3.1 Relative Translation Optimal Transport (ROT) Formulation and R ⁢ W p 𝑅 subscript 𝑊 𝑝 RW_{p} italic_R italic_W start_POSTSUBSCRIPT italic_p end_POSTSUBSCRIPT Distances

As discussed in Section 1, the classical optimal transport (OT) problem is not useful when there is a relative translation between two distributions (or the two datasets known as their supports). We introduce the *relative translation optimal transport* problem, $ROT(\mu,\nu,p)$, which is formulated to find the minimal total transport cost under any translation.

###### Definition 3 (Relative translation optimal transport problem) .

Continuing with the previous notations,

$$ $\text{ROT}(\mu,\nu,p)=\underset{s\in\mathbb{R}^{n}}{\inf}\underset{P\in\Pi(\mu ,\nu)}{\min}\sum_{i=1}^{m_{1}}\sum_{j=1}^{m_{2}}\|x_{i}+s-y_{j}\|_{p}^{p}P_{ij},$ (5) $$

where variable $s$ represents the translation of source distribution $\mu$, and variables $P_{ij}$ represent the coupling solution between the support $x_{i}$ and the support $y_{j}$.

The ROT problem can be viewed as a generalized form of the classical OT in Equation (1). Different from the one-stage optimization in the classical OT problem, there are two stages in this optimization. The inner optimization is exactly the classical OT, whereas the outer optimization finds the best relative translation for the source distribution to minimize the total transport cost.

###### Theorem 1 (Compactness and existence of the minimizer) .

For Equation (5), the domain of the variable $s$ can be confined to a compact set $\{s\in\mathbb{R}^{n}|\;\|s\|_{p}\leq 2\max_{ij}\|x_{i}-y_{j}\|_{p}\}$. Thus, we have

$$ $\text{ROT}(\mu,\nu,p)=\underset{s\in\mathbb{R}^{n}}{\min}\underset{P\in\Pi(\mu ,\nu)}{\min}\sum_{i=1}^{m_{1}}\sum_{j=1}^{m_{2}}\|x_{i}+s-y_{j}\|_{p}^{p}P_{ij},$ $$

where the minimum can be achieved.

The proof of Theorem 1 is provided in Appendix A.

From the perspective of group theory, we could have a better view of which space the ROT problem is defined on. Assume that $\sim$ is the translation relation on the set $\mathcal{P}_{p}(\mathbb{R}^{n})$. When distribution $\mu$ can be translated to distribution $\mu^{\prime}$, we denote it by $\mu\sim\mu^{\prime}$. Because the translation is an equivalence relation defined on the set $\mathcal{P}_{p}(\mathbb{R}^{n})$, we may divide set $\mathcal{P}_{p}(\mathbb{R}^{n})$ by the translation relation, which leads to a quotient set, $\mathcal{P}_{p}(\mathbb{R}^{n})/\sim$. $\mathcal{P}_{p}(\mathbb{R}^{n})/\sim$ consists of the equivalence class of distributions, and each equivalence class, denoted by $[\mu]$, contains all mutually translatable probability distributions. Therefore, the ROT problem can also be regarded as an OT problem defined on the quotient set, $\mathcal{P}_{p}(\mathbb{R}^{n})/\sim$, which tries to find the minimal total transport cost between $[\mu]$ and $[\nu]$. Figure LABEL:Fig_quo_set illustrates this idea.
We can see that the value of the ROT problem is invariant to translations. This is because the ROT problem is only associated with the equivalence classes of probability distributions.

Building upon the ROT model, we introduce a new family of Wasserstein distances to measure the minimal total transport cost between different equivalence classes of probability distributions. As mentioned above, the value of the ROT problem is invariant to any relative translations, thus, we name the corresponding Wasserstein distances as relative-translation invariant Wasserstein distances, denoted by $RW_{p},(p\geq 1)$:

###### Definition 4 (Relative-translation invariant Wasserstein distances) .

$$ $RW_{p}(\mu,\nu)=\text{ROT}(\mu,\nu,p)^{\frac{1}{p}}.$ $$

Similar to the situation where $W_{p}$ is a real metric on $\mathcal{P}_{p}(\mathbb{R}^{n})$, we can obtain the following theorem.

###### Theorem 2 .

$RW_{p}$ is a real metric on the quotient set $\mathcal{P}_{p}(\mathbb{R}^{n})/\sim$.

The proof of Theorem 2 is provided in Appendix A. The $RW_{p}$ can also be regarded as a pseudo-metric defined on the $\mathcal{P}_{p}(\mathbb{R}^{n})$, where the indiscernibility is no longer admitted.

It should be noted that we can not incorporate rotation in our equation 5 since rotation will violate the metric properties and convexity.

###### Definition 3 (Relative translation optimal transport problem) .

###### Theorem 1 (Compactness and existence of the minimizer) .

###### Definition 4 (Relative-translation invariant Wasserstein distances) .

###### Theorem 2 .

### 3.2 Quadratic ROT and Properties of the R ⁢ W 2 𝑅 subscript 𝑊 2 RW_{2} italic_R italic_W start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT Distance

We show three useful properties in the quadratic case of ROT and the resulted $RW_{2}$ distance: decomposability of the ROT optimization model (Theorem 3), translation-invariance of coupling solutions of the ROT problem (Corollary 1), and Pythagorean relationship of $RW_{2}$ and $W_{2}$ (Corollary 2). Decomposability will motivate our algorithm design for efficiently solving an ROT problem, translation-invariance provides $RW_{2}$ the robustness against distribution shift, and the Pythagorean relationship helps us better understand a distribution shift in the perspective of bias-variance.

###### Theorem 3 (Decomposition of the quadratic ROT) .

Continuing with previous notations, the two-stage optimization problem in quadratic ROT can be decomposed into two independent single-stage optimization problems:

$$ $\text{ROT}(\mu,\nu,2)=\underset{s\in\mathbb{R}^{n}}{\min}\underset{P\in\Pi(\mu ,\nu)}{\min}H(P,s)=\underset{P\in\Pi(\mu,\nu)}{\min}(E(P))+\underset{s\in \mathbb{R}^{n}}{\min}(V(s))$ (6) $$

where horizontal function $H(P,s)$ is described by $H(P,s)=\sum_{i=1}^{m_{1}}\sum_{j=1}^{m_{2}}\|x_{i}+s-y_{j}\|_{2}^{2}P_{ij},$
the overall function $E(P)$ is described by,
$E(P)=\sum_{i=1}^{m_{1}}\sum_{j=1}^{m_{2}}\|x_{i}-y_{j}\|_{2}^{2}P_{ij},$
and vertical function $V(s)$ is described by,
$V(s)=\|s\|_{2}^{2}+2s\cdot(\bar{\mu}-\bar{\nu}).$
Moreover, the variables $P_{ij}$ are fully determined by $\underset{P\in\Pi(\mu,\nu)}{\min}E(P)$, which is the classical optimal transport problem between $\mu$ and $\nu$; and the variable $s$ is fully determined by $\underset{s\in\mathbb{R}^{n}}{\min}V(s)$, which is a minimization problem of a quadratic function in $\mathbb{R}^{n}$ and the minimum is achieved when $s=\bar{\nu}-\bar{\mu}$.

Function $E(P)$, $V(P,s)$ and $V(s)$ are illustrated in Figure LABEL:Fig_decom. Due to the page limit, the proof of Theorem 3 is provided in Appendix A.

Theorem 3 is the core idea for our algorithm design in Section 4. It indicates that the coupling solutions $P_{ij}$ to the OT problem are always the same as its ROT version, and verse versa. In other words,

###### Corollary 1 (Translation-invariance of both the ROT solution and $RW_{2}$ ) .

The coupling solutions to the quadratic ROT problem are invariant to any translation of distributions.

Corollary 1 not only guarantees the robustness of $RW_{2}$ against translational shifts but also suggests that the coupling solution of a ROT problem (including the classical OT problem) can be calculated by finding a more ‘‘proper’’ cost matrix of a translated probability distribution pair. This helps us improve the numerical stability and reduce the time complexity in many practical conditions. We provide a detailed analysis in Section 4 and demonstrate it in Section 5.

###### Corollary 2 (Relationship between $RW_{2}$ and $W_{2}$ ) .

Let $s$ be the minimizer $\bar{\nu}-\bar{\mu}$, it follows that,

$$ $W_{2}^{2}(\mu,\nu)=\|\bar{\mu}-\bar{\nu}\|_{2}^{2}+RW_{2}^{2}(\mu,\nu).$ (7) $$

Corollary 2 indicates that there exists a Pythagorean relationship among three types of distances, $W_{2}$, $RW_{2}$, and $L_{2}$, as illustrated in Figure LABEL:Fig_Pythagorean.

Corollary 2 provides a refinement to understand a distribution shift (measured by $W_{2}$) in the perspective of bias and variance decomposition. The $L_{2}$ Euclidean distance between the expectations of two distributions corresponds to the ‘‘bias’’ between two distributions, and the value of $RW_{2}$ corresponds to the difference of ‘‘variances’’ or the ‘‘shapes’’ of two distributions. When the source distribution is a Dirac distribution, the situation degenerates to a classical bias-variance decomposition.

###### Theorem 3 (Decomposition of the quadratic ROT) .

###### Corollary 1 (Translation-invariance of both the ROT solution and R ⁢ W 2 𝑅 subscript 𝑊 2 RW_{2} italic_R italic_W start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT ) .

###### Corollary 2 (Relationship between R ⁢ W 2 𝑅 subscript 𝑊 2 RW_{2} italic_R italic_W start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT and W 2 subscript 𝑊 2 W_{2} italic_W start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT ) .

## 4 R ⁢ W 2 𝑅 subscript 𝑊 2 RW_{2} italic_R italic_W start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT Sinkhorn Algorithm

Based on the first two properties of $RW_{2}$, we design a variant of the Sinkhorn algorithm, named $RW_{2}$ Sinkhorn, to compute $RW_{2}$ under translational shift. Furthermore, we show the new algorithm can be used as a technique to compute $W_{2}$ distance, and it provides enhanced numerical stability and a reduction of time complexity when the difference between the means of two distributions is large.

Figure: Algorithm 1 $RW_{2}$ Sinkhorn Algorithm

### 4.1 R ⁢ W 2 𝑅 subscript 𝑊 2 RW_{2} italic_R italic_W start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT Algorithm Design

Based on Theorem 3 and Corollary 1, we propose the $RW_{2}$ Sinkhorn algorithm for computing $RW_{2}$ distance and coupling solution $P_{ij}$, which is described in Algorithm 1. The key idea of this algorithm involves precomputing the difference between the means of two distributions, as shown in Line 3. Subsequently, it addresses a specific instance of the optimal transport problem where the means of the two distributions are identical by a regular Sinkhorn algorithm. It is important to note that alternative algorithms, such as the network-simplex algorithm or the auction algorithm (Peyré and Cuturi, ), can also be employed to complete the specific instance procedure.

### 4.2 R ⁢ W 2 𝑅 subscript 𝑊 2 RW_{2} italic_R italic_W start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT Technique for W 2 subscript 𝑊 2 W_{2} italic_W start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT Computation

With the observation of Corollary 2, we can also propose a new approach to compute the $W_{2}$ distance from the right side of the Equation (7). When $\|\bar{\nu}-\bar{\mu}\|_{2}$ is large enough, this new $RW_{2}$ based technique has advantages than the regular Sinkhorn in terms of numerical stability and time complexity. We provide an analysis of this new approach in the rest of this section. In addition, experiment in Section 5.1 validates the analysis of our proposed $RW_{2}$ Sinkhorn algorithm for computing $W_{2}$ distance.

### 4.3 Numerical Stability

The division by zero is a known numerical issue of the Sinkhorn algorithm, as shown in Equation (4), and infinitesimal value often occurs in the exponential process of the (negative) cost matrix, that is, $K\leftarrow e^{-\frac{C}{\lambda}}$. The results of the Corollary 1 suggest that it is possible to switch to another ‘‘mutually translated" cost matrix under a relative translation $s$ to increase the numerical stability while preserving the same coupling solutions.

To measure the numerical stability of the matrix, we introduce $g(K)$, defined by the product of all entries $K_{ij}$. Since all entries $K_{ij}$ are in the exponential format and lie in the range of $(0,1]$, $g(K)$ is also in the range of $(0,1]$. As $g(K)$ increases, most entries $K_{ij}$ deviate from zero, which means numerical computation will be more stable. Because of the following transformation,

$$ $g(K)=\prod_{i=1}^{m_{1}}\prod_{j=1}^{m_{2}}K_{ij}=\prod_{i=1}^{m_{1}}\prod_{j= 1}^{m_{2}}\exp(-\frac{C_{ij}}{\lambda})=\exp(-\frac{\sum_{i=1}^{m_{1}}\sum_{j= 1}^{m_{2}}\|x_{i}+s-y_{j}\|_{2}^{2}}{\lambda}),$ $$

one can choose the relative translation $s=\bar{y}-\bar{x}$, so that $g(K)$ can achieve its maximum. When we assume the probability mass on each data is equal, $\bar{y}-\bar{x}$ is the same as $\bar{\nu}-\bar{\mu}$.

### 4.4 Complexity Analysis

Altschuler et al. () provided a proof for the time complexity of the optimal transport model by Sinkhorn algorithm with $\tau$ approximation, which is $O(m^{2}\|C\|_{\infty}^{3}(\log m)\tau^{-3})$, where $\|C\|_{\infty}=\max_{ij}C_{ij}$, with assuming $m=m_{1}=m_{2}$ for the sake of simplicity. When the translated cost matrix has a smaller infinity norm $\|C\|_{\infty}$, we can see that the time complexity will be reduced. When two distributions are sub-Gaussian and $\|\bar{\nu}-\bar{\mu}\|_{2}$ is large enough, we can have a more rigorous analysis for the complexity analysis, which is provided in Appendix C. Our results from the first experiment in Section 5 also empirically validate this idea.

## 5 Experiments

To comprehensively evaluate and validate our proposed method, we conducted three experiments: numerical validation, digit recognition, and similar weather pattern detection. The three experiments are motivated differently: the first experiment is used to validate the numerical stability and computational time of the $RW_{2}$ Sinkhorn algorithm; the second experiment serves as validation of the robustness of $RW_{2}$ distance to the distribution translation in a real-world application; and the third experiment is to show the $RW_{2}$ can scale up to large-scale datasets to identify the similar weather patterns. All tests are executed on a workstation with a 2.60 GHz Intel Core i7 processor and 16GB of RAM using a single computation thread.

### 5.1 Numerical Validation

Figure: Figure 4: Schematic illustration of the first experiment. Assume that the distributions $\mu$ and $\nu$ are the same type of distribution. We compare the performance of Algorithm 1 and the classical Sinkhorn by translating the distribution $\mu$ along vector $s$, i.e., $s=\bar{\nu}-\bar{\mu}$.
Refer to caption: x1.png

First we demonstrate the benefits of applying the $RW_{2}$ Sinkhorn algorithm for computing $W_{2}$ distance on specially designed examples. Let us consider two sets of data points randomly sampled from two identical distributions $\mu$ and $\nu$, each with $1,000$ samples. To compare the performance of Algorithm 1 and the classical Sinkhorn, we translate the distribution $\mu$ with a vector $s$, where the length of translation $s$ ranges within $[0,3]$. The idea is illustrated in Figure 4.

#### Experimental setting

We compare the two versions of Sinkhorn algorithms in $W_{2}$ error and running time. We repeat each experiment and data sampling 10 times. We test a pair of Gaussian distributions in $\mathbb{R}$ (Figure 3(a) and 3(d)), a pair of Gaussians in $\mathbb{R}^{10}$ (Figure 3(b) and 3(e)), and a pair of uniform distributions in $\mathbb{R}^{10}$ (Figure 3(c) and 3(e)). We set $\lambda=0.1$ and $\epsilon=0.01$ for both algorithms.

#### Experiment results

Figure LABEL:Exp1 shows that when the length of the translation increases, the proposed $RW_{2}$ Sinkhorn algorithm significantly outperforms the regular Sinkhorn algorithm in both the running time and computational errors. We also test the performance of the $RW_{2}$ Sinkhorn algorithm on other distributions. See more results in Appendix B.

### 5.2 Digit Recognition

We test the robustness of the $RW_{2}$ distance on the MNIST dataset, perturbed by random translations. Each digital image is a 28 x 28 grid and can be converted into a discrete probability distribution by normalizing the intensity on each pixel by the sum of all intensities. We consider a subset of $N$ data points randomly sampled from the MNIST dataset, where $N=\{100,1000\}$. We embed each image in a larger 84 x 84 grid and translate each image with a random vector $s$ (varying lengths and directions). We test performance on the length of $s$ ranging within $\{0,4,8,12,16,20,24,28\}$ pixels.

#### Experimental setting

We report the mean and standard deviation of classification error using a 1/4 test ratio scheme, repeated 10 times. We use the nearest neighbor search as a classifier with $RW_{2}$ distance, as well as other distances ($L_{1},L_{2},W_{1},W_{2}$) as the baselines. We set the $\lambda=0.1$ and $\epsilon=0.1$ for the $RW_{2}$ Sinkhorn algorithm.

#### Experiment results

Figure LABEL:Exp2 shows that $RW_{2}$ distance significantly outperforms the other distances when the translation $s$ is large in both sample sizes $N=100$ and $N=1,000$.

### 5.3 Similar Thunderstorm Pattern Detection

We apply $RW_{2}$ distance on the real-world thunderstorm dataset, to show that $RW_{2}$ can be used for identifying similar weather patterns and focus more on shape similarity compared with $W_{2}$ distance. Our data are radar images from MULTI-RADAR/MULTI-SENSOR SYSTEM (MRMS) (Zhang et al., ) with a $150$ $km$ $\times$ $150$ $km$ rectangular area centered at the Dallas Fort Worth International Airport (DFW), where each pixel represents a $3$ $km$ $\times$ $3$ $km$ area. The data is assimilated every 10 minutes tracking a long time range of history from 2014 to 2022, with 205,848 images in total. Vertically Integrated Liquid Density (VIL density) and reflectivity are two common measurements for assessing thunderstorm intensity, with threshold values of 3 $kg\cdot m^{-3}$ and 35 $dBZ$, respectively (Matthews and Delaura, ). For the sake of simplicity, we will focus on reflectivity as our main indicator for thunderstorm intensity.

We consider two types of thunderstorm events: thunderstorm snapshots and thunderstorm sequences. More comparison results can be found in the Appendix B.

#### Experimental setting

We apply the $RW_{2}$ Sinkhorn algorithm to compute both the $W_{2}$ distance and the $RW_{2}$ distance to identify the most similar thunderstorm event given a reference event, with $\lambda=0.1$ and $\epsilon=0.01$. For the thunderstorm sequence identification, we consider a one-hour thunderstorm event as our reference, consisting of 6 images in time order.

#### Thunderstorm snapshot results

Given the same reference thunderstorm snapshot, Figure LABEL:Exp3_snapshot shows that the similar events identified by $RW_{2}$ focus more on shape similarity compared with $W_{2}$.

#### Thunderstorm sequence results

Given a reference thunderstorm sequence, Figure LABEL:Exp3_seq shows that the similar sequences identified by $RW_{2}$ focus more on shape similarity compared with $W_{2}$.

## 6 Conclusions

In this paper, we introduce a new family of distances, relative-translation invariant Wasserstein ($RW_{p}$) distances, for measuring the pattern similarity between two probability distributions (and their data supports). Generalizing from the classical optimal transport model, we show that the proposed $RW_{p}$ distances are real distance metrics defined on the quotient set $\mathcal{P}_{p}(\mathbb{R}^{n})/\sim$ and invariant to the translations of distributions. When $p=2$, this distance enjoys more useful properties, including decomposability of the reformulated optimal transport model, translation-invariance of coupling solutions and $RW_{2}$, and Pythagorean relationship of $RW_{2}$ and $W_{2}$ distances. Based on these properties, we show a distribution shift, measured by $W_{2}$ distance, which can be explained from the perspective of bias-variance. 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 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 illustrative and real-world experiments. The experimental results report that our proposed algorithm significantly improves the computational efficiency of Sinkhorn in practical applications with large translations, and the $RW_{2}$ distance is robust to distribution translations compared with baselines.

## Appendix A Main Proofs

### A.1 Theorem 1

###### Proof of Theorem 1 .

It is clear to verify that when $\|s\|_{p}\geq 2\max_{ij}\|x_{i}-y_{j}\|_{p}$, for any $i,j,(1\leq i\leq m_{1},1\leq j\leq m_{2})$, it follows that $\|x_{i}+s-y_{j}\|_{p}\geq\|s\|_{p}-\|x_{i}-y_{j}\|_{p}\geq 2\max_{ij}\|x_{i}-y
_{j}\|_{p}-\|x_{i}-y_{j}\|_{p}\geq\|x_{i}-y_{j}\|_{p}$. In other words, when $\|s\|_{p}\geq 2\max_{ij}\|x_{i}-y_{j}\|_{p}$, the relative distance between each pair of support $x_{i}$ and $y_{j}$ are always greater than or equal to the non-translated distance, which implies the total transport cost for the translated case will also greater than or equal to the cost for the non-translated distance. Since we are trying to find the minimal value, we can only focus on the compact set $\{s\in\mathbb{R}^{n}|\|s\|_{p}\leq 2\max_{ij}\|x_{i}-y_{j}\|_{p}\}$.
∎

###### Proof of Theorem 1 .

### A.2 Theorem 2

###### Proof of Theorem 2 .

With the previous notations, firstly, we will show that the translation relation $\sim$ is an equivalence relation on set $\mathcal{P}_{p}(\mathbb{R}^{n})$.

Equivalence relation requires reflexivity, symmetry, and transitivity, and the following observations show translation relation is indeed an equivalence relation.

- •
Reflexivity, $(x\sim x)$.
For any distribution $\mu\in\mathcal{P}_{p}(\mathbb{R}^{n})$, it can translate to itself with zero vector.
- •
Symmetry, $(x\sim y\implies y\sim x)$.
For any distribution $\mu,\nu\in\mathcal{P}_{p}(\mathbb{R}^{n})$, if $\mu$ can be translated to $\nu$, then $\nu$ can also be translated to $\mu$.
- •
Transitivity, $(x\sim y\text{ and }y\sim z\implies x\sim z)$.
For any distribution $\mu,\nu,\eta\in\mathcal{P}_{p}(\mathbb{R}^{n})$, if $\mu$ can be translated to $\nu$, and $\nu$ can be translated to $\eta$, then $\mu$ can also be translated to $\eta$.

Based on the property of equivalence relation, it is clear that set $\mathcal{P}_{p}(\mathbb{R}^{n})/\sim$ is well-defined. Let $[\mu]$ be an element in set $M/\sim$, where $\mu$ is a representative of $[\mu]$, i.e. $[\mu]$ is the set of distributions that can be mutually translated from $\mu$. Noticing that $W_{p}(\cdot,\cdot)$ is a real distance metric on $\mathcal{P}_{p}(\mathbb{R}^{n})$ [Villani and Society, ], it implies that $W_{p}(\cdot,\cdot)$ satisfied with identity, positivity, symmetry, and the triangle inequality. Based on $W_{p}(\cdot,\cdot)$, we show $RW_{p}(\cdot,\cdot)$ satisfies with identity, positivity, symmetry, and triangle inequality with respect to elements in $\mathcal{P}_{p}(\mathbb{R}^{n})/\sim$.

For any $\mu,\nu,\eta\in\mathcal{P}_{p}(\mathbb{R}^{n})/\sim$,

- •
Identity,
$RW_{p}([\mu],[\mu])=\underset{\mu\in[\mu],\mu\in[\mu]}{\text{min.}}[W_{p}(\mu,
\mu)]=0.$
- •
Positivity,
$RW_{p}([\mu],[\nu])=\underset{\mu\in[\mu],\nu\in[\nu]}{\text{min.}}[W_{p}(\mu,
\nu)]\geq 0.$
- •
Symmetry,
$RW_{p}(\mu,\nu)=\underset{\mu\in[\mu],\nu\in[\nu]}{\text{min.}}[W_{p}(\mu,\nu)
]=\underset{\nu\in[\nu],\mu\in[\mu]}{\text{min.}}[W_{p}(\nu,\mu)]=RW_{p}(\nu,
\mu).$
- •
Triangle inequality,
$\begin{split}&RW_{p}(\mu,\nu)\\
=&\underset{\mu\in[\mu],\nu\in[\nu]}{\text{min.}}[W_{p}(\mu,\nu)]\\
\leq&\underset{\eta,\eta^{\prime}\in[\eta]}{\text{min.}}\underset{\mu\in[\mu],
\nu\in[\nu]}{\text{min.}}[W_{p}(\mu,\eta)+W_{p}(\eta,\eta^{\prime})+W_{p}(\eta
^{\prime},\nu)]\\
=&\underset{\mu\in[\mu],\nu\in[\nu],\eta,\eta^{\prime}\in[\eta]}{\text{min.}}[
W_{p}(\mu,\eta)+0+W_{p}(\eta^{\prime},\nu)]\\
=&\underset{\mu\in[\mu],\eta\in[\eta]}{\text{min.}}[W_{p}(\mu,\eta)]+\underset
{\nu\in[\nu],\eta^{\prime}\in[\eta]}{\text{min.}}[W_{p}(\eta^{\prime},\nu)]\\
=&\underset{\mu\in[\mu],\eta\in[\eta]}{\text{min.}}[W_{p}(\mu,\eta)]+\underset
{\nu\in[\nu],\eta\in[\eta]}{\text{min.}}[W_{p}(\eta,\nu)]\\
=&RW_{p}(\mu,\eta)+RW_{p}(\eta,\nu).\end{split}$

∎

###### Proof of Theorem 2 .

### A.3 Theorem 3

###### Proof of Theorem 3 .

With the previous notations, firstly, we show the two-stage optimization problem, $\underset{s\in\mathbb{R}^{n}}{\min}\underset{P\in\Pi(\mu,\nu)}{\min}H(P,s)$, can be decomposed into two independent one-stage optimization problems, $\underset{P\in\Pi(\mu,\nu)}{\min}(E(P))$ and $\underset{s\in\mathbb{R}^{n}}{\min}(V(s))$.

For the objective function $H(P,s)$, we expand it with respect to $s$,

$$ $\displaystyle\begin{split}&H(P,s)\\ =&\sum_{i=1}^{m_{1}}\sum_{j=1}^{m_{2}}\|x_{i}+s-y_{j}\|_{2}^{2}P_{ij}\\ =&\sum_{i=1}^{m_{1}}\sum_{j=1}^{m_{2}}\bigg{(}\|x_{i}-y_{j}\|_{2}^{2}+\|s\|_{2 }^{2}+2s\cdot(x_{i}-y_{j})\bigg{)}P_{ij}\\ =&\sum_{i=1}^{m_{1}}\sum_{j=1}^{m_{2}}\|x_{i}-y_{j}\|_{2}^{2}P_{ij}+\sum_{i=1} ^{m_{1}}\sum_{j=1}^{m_{2}}\|s\|_{2}^{2}P_{ij}+2\sum_{i=1}^{m_{1}}\sum_{j=1}^{m _{2}}s\cdot(x_{i}-y_{j})P_{ij}.\\ \end{split}$ (8) $$

We can rewrite the second and the third terms in Equation (8) under the condition $P\in\Pi(\mu,\nu)$, which implies that,

$$ $\sum_{i=1}^{m_{1}}\sum_{j=1}^{m_{2}}P_{ij}=1,\sum_{j=1}^{m_{2}}P_{ij}=a_{i}, \sum_{i=1}^{m_{1}}P_{ij}=b_{j},1\leq i\leq m_{1},1\leq j\leq m_{2}.$ $$

For the second term, it follows that

$$ $\sum_{i=1}^{m_{1}}\sum_{j=1}^{m_{2}}\|s\|_{2}^{2}P_{ij}=\|s\|_{2}^{2}\cdot( \sum_{i=1}^{m_{1}}\sum_{j=1}^{m_{2}}P_{ij})=\|s\|_{2}^{2}\cdot 1=\|s\|_{2}^{2}.$ $$

For the third term, it follows that

$$ $\begin{split}&2\sum_{i=1}^{m_{1}}\sum_{j=1}^{m_{2}}s\cdot(x_{i}-y_{j})P_{ij}\\ &=2s\cdot\sum_{i=1}^{m_{1}}\sum_{j=1}^{m_{2}}(x_{i}-y_{j})P_{ij}\\ &=2s\cdot(\sum_{i=1}^{m_{1}}\sum_{j=1}^{m_{2}}x_{i}\cdot P_{ij}-\sum_{i=1}^{m_ {1}}\sum_{j=1}^{m_{2}}y_{j}\cdot P_{ij})\\ &=2s\cdot(\sum_{i=1}^{m_{1}}x_{i}\cdot(\sum_{j=1}^{m_{2}}P_{ij})-\sum_{j=1}^{m _{2}}y_{j}\cdot(\sum_{i=1}^{m_{1}}P_{ij}))\\ &=2s\cdot(\sum_{i=1}^{m_{1}}x_{i}\cdot a_{i}-\sum_{j=1}^{m_{2}}y_{j}\cdot b_{j })\\ &=2s\cdot(\bar{\mu}-\bar{\nu}).\\ \end{split}$ $$

Thus, we have the following transformation,

$$ $\begin{split}&\underset{s\in\mathbb{R}^{n}}{\min}\underset{P\in\Pi(\mu,\nu)}{ \min}H(P,s)\\ &=\underset{s\in\mathbb{R}^{n}}{\min}\underset{P\in\Pi(\mu,\nu)}{\min}(\sum_{i =1}^{m_{1}}\sum_{j=1}^{m_{2}}\|x_{i}-y_{j}\|_{2}^{2}P_{ij}+\sum_{i=1}^{m_{1}} \sum_{j=1}^{m_{2}}\|s\|_{2}^{2}P_{ij}+2\sum_{i=1}^{m_{1}}\sum_{j=1}^{m_{2}}s \cdot(x_{i}-y_{j})P_{ij})\\ &=\underset{s\in\mathbb{R}^{n}}{\min}\underset{P\in\Pi(\mu,\nu)}{\min}\sum_{i= 1}^{m_{1}}\sum_{j=1}^{m_{2}}\|x_{i}-y_{j}\|_{2}^{2}P_{ij}+\underset{s\in \mathbb{R}^{n}}{\min}\underset{P\in\Pi(\mu,\nu)}{\min}(\sum_{i=1}^{m_{1}}\sum_ {j=1}^{m_{2}}\|s\|_{2}^{2}P_{ij}+2\sum_{i=1}^{m_{1}}\sum_{j=1}^{m_{2}}s\cdot(x _{i}-y_{j})P_{ij})\\ &=\underset{s\in\mathbb{R}^{n}}{\min}\underset{P\in\Pi(\mu,\nu)}{\min}\sum_{i= 1}^{m_{1}}\sum_{j=1}^{m_{2}}\|x_{i}-y_{j}\|_{2}^{2}P_{ij}+\underset{s\in \mathbb{R}^{n}}{\min}(\|s\|_{2}^{2}+2s\cdot(\bar{\mu}-\bar{\nu}))\\ &=\underset{P\in\Pi(\mu,\nu)}{\min}\sum_{i=1}^{m_{1}}\sum_{j=1}^{m_{2}}\|x_{i} -y_{j}\|_{2}^{2}P_{ij}+\underset{s\in\mathbb{R}^{n}}{\min}(\|s\|_{2}^{2}+2s \cdot(\bar{\mu}-\bar{\nu}))\\ &=\underset{P\in\Pi(\mu,\nu)}{\min}(E(P))+\underset{s\in\mathbb{R}^{n}}{\min}( V(s))\\ \end{split}$ $$

Since $V(s)$ is a high-dimensional quadratic function of variable $s$, it is easy to follow that the minimum is achieved when $s=\bar{\nu}-\bar{\mu}$.

∎

###### Proof of Theorem 3 .

## Appendix B Additional Experiment Results

### B.1 Additional experiment results for Section 5.1 - Numerical Validation

### B.2 Additional experiment results for Section 5.3 - Similar Thunderstorm Pattern Detection

## Appendix C Complexity Analysis for Algorithm 1 under sub-Gaussian Distributions

This section is organized as follows. In section C.1, we state and prove the theorem regarding the time complexity of Algorithm 1. We leave the definitions and theorems used in the proof to section C.2.

### C.1 Theoretical Results of Time Complexity

Assuming the two distributions are sub-Gaussian and $\|\bar{\nu}-\bar{\mu}\|_{2}^{2}$ is large enough, we can prove that with high probability, the translated cost matrix has a smaller norm $\|C\|_{\infty}$, thus the time complexity can be reduced.

###### Theorem 4 .

Let $\mu,\nu$ be two high-dimensional sub-Gaussian distributions in $\mathbb{R}^{n}$. $(X_{1},X_{2},\ldots,X_{m_{1}})$, $(Y_{1},Y_{2},\ldots,Y_{m_{2}})$ are i.i.d data sampled from $\mu$ and $\nu$ separately. Let $\bar{\mu}=\mathbb{E}\mu$, $\bar{\nu}=\mathbb{E}\nu$, $\bar{X}=\sum_{i=1}^{m_{1}}X_{i}/{m_{1}}$, $\bar{Y}=\sum_{i=1}^{m_{2}}Y_{i}/{m_{2}}$. Assume $\|\mu-\bar{\mu}\|_{\psi_{2}}<\infty$, $\|\nu-\bar{\nu}\|_{\psi_{2}}<\infty$. $l=\|\bar{\mu}-\bar{\nu}\|_{2}$. If

$$ $\displaystyle l$ $\displaystyle\geq C\sqrt{n}\bigg{[}1+\|\mu-\bar{\mu}\|_{\psi_{2}}+\|\nu-\bar{ \nu}\|_{\psi_{2}}\bigg{]}$ $\displaystyle\qquad+C\bigg{[}\sqrt{\log(4{m_{1}}/\delta)}\cdot\|\mu-\bar{\mu} \|_{\psi_{2}}+\sqrt{\log(4{m_{2}}/\delta)}\big{)}\cdot\|\nu-\bar{\nu}\|_{\psi_ {2}}\bigg{]},$ $$

where $C$ is an absolute constant,
then with probability at least $1-\delta$, we have

$$ $\displaystyle\max_{i,j}\|X_{i}-\bar{X}-Y_{j}+\bar{Y}\|_{2}\leq\max_{i,j}\|X_{i }-Y_{j}\|_{2}.$ $$

###### Remark 1 .

Sub-Gaussian distributions represent a broad class of distributions that encompass many common types, including multivariate normal distribution, multivariate symmetric Bernoulli, and uniform distribution on the sphere. Theorem LABEL:thm:xxx demonstrates that when the translation is significant, the maximum absolute entry of the cost matrix $\|C\|_{\infty}=\max_{ij}|C_{ij}|$ tends to decrease. Consequently, our RW2 method achieves better time complexity compared to W2. This theoretical finding is consistent with our experimental results, as shown in Figure LABEL:Exp1.

###### Proof of Theorem 4 .

For $i=1,2,\ldots,{m_{1}}$, $X_{i}-\bar{\mu}$ is a sub-Gaussian random vector. Using Theorem 6 and taking a union bound over all the random vectors, we have for all $X_{i}$ with probability at least $1-\delta/4$, the following inequality holds

$$ $\displaystyle\|X_{i}-\bar{\mu}\|_{2}\leq c\big{(}\sqrt{n}+\sqrt{\log(4{m_{1}}/ \delta)}\big{)}\cdot\|\mu-\bar{\mu}\|_{\psi_{2}}.$ (9) $$

Similarly, we have for all $Y_{j}$, with probability at least $1-\delta$, the following inequality holds

$$ $\displaystyle\|Y_{j}-\bar{\nu}\|_{2}\leq c\big{(}\sqrt{n}+\sqrt{\log(4{m_{2}}/ \delta)}\big{)}\cdot\|\nu-\bar{\nu}\|_{\psi_{2}}.$ (10) $$

Using Theorem 5, $\sum_{i=1}^{m}(X_{i}-\bar{\mu})$ is a sub-Gaussian random vector, with $\|\sum_{i=1}^{m_{1}}(X_{i}-\bar{\mu})\|_{\psi_{2}}\leq\sqrt{C\sum_{i=1}^{m_{1}
}\|X_{i}-\bar{\mu}\|_{\psi_{2}}^{2}}$ Then using Theorem 6, with probability at least $1-\delta/4$, we have

$$ $\displaystyle\Big{\|}\sum_{i=1}^{m_{1}}X_{i}-{m_{1}}\bar{\mu}\Big{\|}_{2}$ $\displaystyle\leq c\big{(}\sqrt{n}+\sqrt{\log(1/\delta)}\big{)}\cdot\Big{\|} \sum_{i=1}^{m_{1}}(X_{i}-\bar{\mu})\Big{\|}_{\psi_{2}}$ $\displaystyle=c\big{(}\sqrt{n}+\sqrt{\log(1/\delta)}\big{)}\cdot\sqrt{C\sum_{i =1}^{m_{1}}\|X_{i}-\bar{\mu}\|_{\psi_{2}}^{2}}$ $\displaystyle=c^{\prime}\big{(}\sqrt{n}+\sqrt{\log(1/\delta)}\big{)}\cdot\sqrt {m_{1}}\|\mu-\bar{\mu}\|_{\psi_{2}},$ (11) $$

where $c^{\prime}$ is an absolute constant. Similarly, with probability at least $1-\delta$, we have

$$ $\displaystyle\Big{\|}\sum_{j=1}^{m_{2}}Y_{j}-m_{2}\bar{\nu}\Big{\|}_{2}\leq c^ {\prime}\big{(}\sqrt{n}+\sqrt{\log(1/\delta)}\big{)}\cdot\sqrt{m_{2}}\|\nu- \bar{\nu}\|_{\psi_{2}},$ (12) $$

where $c^{\prime}$ is an absolute constant. In the following proof, we consider the union bound of all the high-probability events above, such that (9), (10), (11) and (12) hold. It occurs with probability at least $1-\delta$.
First, for $\max_{i,j}\|X_{i}-Y_{j}\|_{2}$, we have

$$ $\displaystyle\max_{i,j}\|X_{i}-Y_{j}\|_{2}$ $\displaystyle\geq\max_{i,j}\|\bar{\mu}-\bar{\nu}\|_{2}-\|X_{i}-\bar{\mu}\|_{2} -\|Y_{j}-\bar{\nu}\|_{2}$ $\displaystyle\geq l-\bigg{[}c\big{(}\sqrt{n}+\sqrt{\log(4m_{1}/\delta)}\big{)} \cdot\|\mu-\bar{\mu}\|_{\psi_{2}}\bigg{]}$ $\displaystyle\qquad-\bigg{[}c\big{(}\sqrt{n}+\sqrt{\log(4m_{2}/\delta)}\big{)} \cdot\|\nu-\bar{\nu}\|_{\psi_{2}}\bigg{]}$ $\displaystyle=l-2c\sqrt{n}-c\sqrt{\log(4m_{1}/\delta)})\cdot\|\mu-\bar{\mu}\|_ {\psi_{2}}$ $\displaystyle\qquad-c\sqrt{\log(4m_{2}/\delta)}\big{)}\cdot\|\nu-\bar{\nu}\|_{ \psi_{2}},$ $$

where the first inequality holds due to the triangle inequality. The second inequality holds due to (9) and (10).
For $\max_{i,j}\|X_{i}-Y_{j}-\bar{X}_{i}+\bar{Y}_{j}\|_{2}$, we have

$$ $\displaystyle\max_{i,j}\|X_{i}-Y_{j}-\bar{X}_{i}+\bar{Y}_{j}\|_{2}\leq\max_{i, j}\|X_{i}-\bar{\mu}\|_{2}+\|Y_{j}-\bar{\nu}\|_{2}$ $\displaystyle\qquad+\|\bar{X}_{i}-\bar{\mu}\|_{2}+\|\bar{Y}_{j}-\bar{\nu}\|_{2}$ $\displaystyle\leq\bigg{[}c\big{(}\sqrt{n}+\sqrt{\log(4m_{1}/\delta)}\big{)} \cdot\|\mu-\bar{\mu}\|_{\psi_{2}}\bigg{]}+\bigg{[}c\big{(}\sqrt{n}+\sqrt{\log( 4m_{2}/\delta)}\big{)}\cdot\|\nu-\bar{\nu}\|_{\psi_{2}}\bigg{]}$ $\displaystyle\qquad+\bigg{[}c^{\prime}\frac{\sqrt{n}+\sqrt{\log(1/\delta)}}{ \sqrt{m_{1}}}\|\mu-\bar{\mu}\|_{\psi_{2}}\bigg{]}+\bigg{[}c^{\prime}\frac{ \sqrt{d}+\sqrt{\log(1/\delta)}}{\sqrt{m_{2}}}\|\nu-\bar{\nu}\|_{\psi_{2}}\bigg {]}$ $\displaystyle\leq C\sqrt{n}\Big{[}1+\frac{\|\mu-\bar{\mu}\|_{\psi_{2}}}{\sqrt{ m_{1}}}+\frac{\|\nu-\bar{\nu}\|_{\psi_{2}}}{\sqrt{m_{2}}}\Big{]}$ $\displaystyle\qquad+C\bigg{[}\sqrt{\log(4m_{1}/\delta)}\cdot\|\mu-\bar{\mu}\|_ {\psi_{2}}+\sqrt{\log(4m_{2}/\delta)}\big{)}\cdot\|\nu-\bar{\nu}\|_{\psi_{2}} \bigg{]},$ $$

where the first inequality holds due to (9), (10), (11) and (12).
Therefore, we have the following conclusion:
As long as

$$ $\displaystyle l$ $\displaystyle\geq C\sqrt{n}\bigg{[}1+\|\mu-\bar{\mu}\|_{\psi_{2}}+\|\nu-\bar{ \nu}\|_{\psi_{2}}\bigg{]}$ $\displaystyle\qquad+C\bigg{[}\sqrt{\log(4m_{1}/\delta)}\cdot\|\mu-\bar{\mu}\|_ {\psi_{2}}+\sqrt{\log(4m_{2}/\delta)}\big{)}\cdot\|\nu-\bar{\nu}\|_{\psi_{2}} \bigg{]},$ $$

where $C$ is an absolute constant, we can conclude that

$$ $\displaystyle\max_{i,j}\|X_{i}-Y_{j}-\bar{X}_{i}+\bar{Y}_{j}\|_{2}\leq\max_{i, j}\|X_{i}-Y_{j}\|_{2}.$ $$

This completes the proof of Theorem 4.
∎

###### Theorem 4 .

###### Remark 1 .

###### Proof of Theorem 4 .

### C.2 High Dimensional Probability Basics

In this section, we introduce some basic knowledge we will use in the proof of Theorem.
The results mostly come from Vershynin [].
We first introduce a broad and widely used distribution class.

###### Definition 5 (Sub-Gaussian) .

A random variable $X$ that
satisfies one of the following equivalent properties is called a subgaussian random variable.

- (a)
There exists $K_{1}>0$ such that the tails of $X$ satisfy
$\displaystyle\mathbb{P}\{|X|\geq t\}\leq 2\exp(-t^{2}/K^{2}_{1})\text{ for all
}t\geq 0.$
- (b)
There exists $K_{2}>0$ such that the moments of $X$ satisfy
$\displaystyle\|X\|_{L^{p}}=(\mathbb{E}|X|^{p})^{1/p}\leq K_{2}\sqrt{p}\text{
for all }p\geq 1.$
- (c)
There exists $K_{3}>0$ such that the moment-generating function (MGF) of $X^{2}$ satisfies
$\displaystyle\mathbb{E}\exp(\lambda^{2}X^{2})\leq\exp(K^{2}_{3}\lambda^{2})
\text{ for all }\lambda\text{ such that }|\lambda|\leq\frac{1}{K_{3}}.$
- (d)
There exists $K_{4}>0$ such that the MGF of $X^{2}$
is bounded at some point,
namely,
$\displaystyle\mathbb{E}\exp(X^{2}/K^{2}_{4})\leq 2.$
- (e)
Moreover, if $\mathbb{E}X=0$, the following property is also equivalent.
There exists $K_{5}>0$ such that the MGF of X satisfies
$\displaystyle\mathbb{E}\exp(\lambda X)\leq\exp(K^{2}_{5}\lambda^{2})\text{ for
all }\lambda\in\mathbb{R}.$

The parameters $K_{i}>0$ appearing in
these properties differ from each other by at most an absolute constant factor.
The sub-gaussian norm of $X$, denoted $\|X\|_{\psi_{2}}$, is defined to be

$$ $\displaystyle\|X\|_{\psi_{2}}=\inf\{t>0:\mathbb{E}\exp(X^{2}/t^{2})\leq 2\}.$ $$

###### Definition 6 .

A random vector $X\in\mathbb{R}^{d}$
is sub-Gaussian
if for any vector $\mathbf{u}\in\mathbb{R}^{d}$
the inner product $\langle X,\mathbf{u}\rangle$ is a sub-Gaussian random variable. And the
corresponding $\psi_{2}$ norm of $X$ is defined as

$$ $\displaystyle\|X\|_{\psi_{2}}=\sup_{\|\mathbf{u}\|_{2}=1}\|\langle X,\mathbf{u }\rangle\|_{\psi_{2}}.$ $$

###### Theorem 5 .

Let $X_{1},\ldots,X_{N}\in\mathbb{R}^{d}$ be
independent, mean zero, sub-Gaussian random vectors. Then
$\sum_{i=1}^{N}X_{i}$ is also a
sub-Gaussian random vector, and

$$ $\displaystyle\Big{\|}\sum_{i=1}^{N}X_{i}\Big{\|}^{2}_{\psi_{2}}\leq C\sum_{i=1 }^{N}\|X_{i}\|^{2}_{\psi_{2}}.$ $$

where C is an absolute constant.

###### Proof of Theorem 5 .

For any vector $\mathbf{u}\in\mathbb{R}$, $\|\mathbf{u}\|_{2}=1$, consider $\langle\sum_{i=1}^{N}X_{i},\mathbf{u}\rangle$. Using independence, we have for all $\lambda$,

$$ $\displaystyle\mathbb{E}\exp\Big{(}\lambda\sum_{i=1}^{N}\langle X_{i},\mathbf{u }\rangle\Big{)}$ $\displaystyle=\prod_{i=1}^{N}\mathbb{E}\exp\big{(}\lambda\langle X_{i},\mathbf {u}\rangle\big{)}$ $\displaystyle\leq\prod_{i=1}^{N}\exp\big{(}C\|\langle X_{i},\mathbf{u}\rangle \|_{\psi_{2}}^{2}\lambda^{2}\big{)}$ $\displaystyle=\exp\bigg{(}C\lambda^{2}\sum_{i=1}^{N}\|\langle X_{i},\mathbf{u} \rangle\|_{\psi_{2}}^{2}\bigg{)},$ $$

where $C$ is an absolute constant and the first inequality holds due to property (e) of the sub-Gaussian variables. Taking supreme over $\mathbf{u}$, we prove that $\sum_{i=1}^{N}X_{i}$ is also a
sub-Gaussian random vector. Moreover,

$$ $\displaystyle\Big{\|}\sum_{i=1}^{N}X_{i}\Big{\|}^{2}_{\psi_{2}}\leq C\sum_{i=1 }^{N}\|X_{i}\|^{2}_{\psi_{2}}.$ $$

where C is an absolute constant.
∎

###### Theorem 6 .

Let $X\in\mathbb{R}^{d}$ be a sub-Gaussian random vector. Then with probability at least $1-\delta$,

$$ $\displaystyle\|X\|_{2}\leq c\big{(}\sqrt{d}+\sqrt{\log(1/\delta)}\big{)}\cdot \|X\|_{\psi_{2}}.$ $$

###### Proof.

Let $B_{d}$ be the $d$-dimensional unit ball, $N$
be a $1/2$-covering of $B_{d}$ in 2-norm with covering number $=N(B_{d},\|\cdot\|_{2},1/2)$. Therefore,

$$ $\displaystyle\forall\mathbf{x}\in B_{d},\exists\mathbf{z}\in N,\text{ s.t. }\| \mathbf{x}-\mathbf{z}\|\leq 1/2.$ $$

Using Lemma 1, we have

$$ $\displaystyle N\leq 5^{d}.$ (13) $$

Using the fact $\|\mathbf{x}\|_{2}=\max_{\|\mathbf{y}\|_{2}\leq 1}\langle\mathbf{x},\mathbf{y}\rangle$, we have

$$ $\displaystyle\|X\|_{2}$ $\displaystyle=\max_{\mathbf{x}\in B_{d}}\langle\mathbf{x},X\rangle$ $\displaystyle\leq\max_{\mathbf{z}\in N}\langle\mathbf{z},X\rangle+\max_{ \mathbf{y}\in(1/2)B_{d}}\langle\mathbf{y},X\rangle$ $\displaystyle=\max_{\mathbf{z}\in N}\langle\mathbf{z},X\rangle+\frac{1}{2}\max _{\mathbf{y}\in B_{d}}\langle\mathbf{y},X\rangle.$ $$

Therefore, we have

$$ $\displaystyle\|X\|_{2}\leq 2\max_{\mathbf{z}\in N}\langle\mathbf{z},X\rangle.$ (14) $$

Then we can provide a high probability upper bound for the Euclidean norm of the random vector $X$ by considering the probability $\mathbb{P}(\|X\|_{2}\geq t)$.

$$ $\displaystyle\mathbb{P}(\|X\|_{2}\geq t)$ $\displaystyle\leq\mathbb{P}\Big{(}\max_{\mathbf{z}\in N}\langle\mathbf{z},X \rangle\geq\frac{t}{2}\Big{)}$ $\displaystyle\leq\mathbb{P}\Big{(}\exists\mathbf{z}\in N,\langle\mathbf{z},X \rangle\geq\frac{t}{2}\Big{)}$ $\displaystyle\leq\sum_{\mathbf{z}\in N}\mathbb{P}\Big{(}\langle\mathbf{z},X \rangle\geq\frac{t}{2}\Big{)}$ $\displaystyle\leq N\exp\Big{(}-c\frac{t^{2}}{\|X\|_{\psi_{2}}^{2}}\Big{)}$ $\displaystyle\leq 5^{d}\exp\Big{(}-\frac{ct^{2}}{\|X\|_{\psi_{2}}^{2}}\Big{)},$ $$

where $c$ is an absolute constant. Here the first inequality holds due to (14). The second inequality holds due to $\{\max_{\mathbf{z}\in N}\langle\mathbf{z},X\rangle\geq t/2\}\subseteq\{\exists
\mathbf{z}\in N,\langle\mathbf{z},X\rangle\geq t/2\}$. The third inequality holds due to the union bound. The fourth inequality holds due to the definition of the sub-Gaussian vector and the property
(a) of a sub-Gaussian variable. The last inequality holds due to (13).

Finally, let $t=\sqrt{[d\log 5+\log(1/\delta)]/c}\cdot\|X\|_{\psi_{2}}$. We have with probability at least $1-\delta$,

$$ $\displaystyle\|X\|_{2}\geq t.$ $$

Finally, using $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$, we complete the proof of Theorem 6.
∎

###### Definition 7 ( $\epsilon$ -covering) .

Let $(V,\|\cdot\|)$ be a normed space, and $\Theta\subset V$. ${V_{1},\ldots,V_{N}}$ is an
$\epsilon$-covering of $\Theta$ if $\Theta\subseteq\cup_{i=1}^{N}V_{i}$, or equivalently, $\forall\theta\in\Theta,\exists i$ such that $\|\theta-V_{i}\|\leq\epsilon$.

###### Definition 8 (Covering number) .

The covering number is defined by

$$ $\displaystyle N(\Theta,\|\cdot\|,\epsilon):=\min\{n:\exists\epsilon\text{- covering over }\Theta\text{ of size }n\}.$ $$

###### Lemma 1 .

Let $B_{d}$ be the $d$-dimensional Euclidean unit ball. Consider $N(B_{d},\|\cdot\|_{2},\epsilon)$. When $\epsilon\geq 1$, $N(B_{d},\|\cdot\|_{2},\epsilon)=1$. When $\epsilon<1$, we have

$$ $\displaystyle\Big{(}\frac{1}{\epsilon}\Big{)}^{d}\leq N(B_{d},\|\cdot\|_{2}, \epsilon)\leq\Big{(}1+\frac{2}{\epsilon}\Big{)}^{d}.$ $$

###### Definition 5 (Sub-Gaussian) .

###### Definition 6 .

###### Theorem 5 .

###### Proof of Theorem 5 .

###### Theorem 6 .

###### Proof.

###### Definition 7 ( ϵ italic-ϵ \epsilon italic_ϵ -covering) .

###### Definition 8 (Covering number) .

###### Lemma 1 .

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: **Minor Typos**
- M179: « coupling «  —> « Coupling »
- L325: « Thoorem »
soundness: 2
strengths: - The authors propose relative translation optimal transport (ROT) which induces a Wasserstein like distance on the quotient space of probability measures induced by the translation relation. 
- For quadratic ROT, a decomposition in terms of Wasserstein distance (horizontal function) summed with a quadratic term including the shifting parameter $s$. 
- The authors test ROT approach on weather detection dataset.
- I checked the proofs of the main results and they sound correct.
summary: Many machine learning pipelines rely on training objective losses involving comparing probabilities measures. One of the mostly used in these pipelines are optimal transport (OT), aka Wasserstein distance,  that leverages the geometrical information of the distributions in question. In a nutshell, Wasserstein distance seeks for the cheaper cost to transport a source distribution to a target one, where the optimization problem behind consists in a linear programming problem. 

This paper addresses a major limitation of classical Wasserstein distance that corresponds to a translation shift in the source distribution. It introduces a family of relative-translation invariant Wasserstein $RW_p$ that behave like to Wasserstein distance and invariant to translation. For $p=2$, $RW_2$ enjoys a decomposition of the relative translation optimal transport (ROT). In addition, $RW_2$ can be solved using Sinkhorn iterations. The papers ends up with empirical results on weather detection dataset.
weaknesses: - In Definition 4, the relative transplantation invariant Wasserstein, $RW_p(\mu, \nu)$ is given with respect to an $s$-shifting of the source distribution $\mu$. However in Theorem 2, $RW_p$ is proper distance on the quotient set of shifting probabilities. Since the main results of the paper are based with respect to a shifting of the source, I’am wondering about the properties of $RW_p$ outside the quotient set. 
- The quadratic $RW_2$ is very closed to the translation property of Wasserstein distance with a quadratic cost (see Remark 2.19 in Peyré and Cuturi, 2019). namely, if one considers only the case of shifting the source distribution, the decomposition of Quadratic ROT can be straiforwardly from this remark and  a simple optimization minimisation over the shifting parameter $s$. I think this point weakens the novelty of this paper. 
- I think that the computational efficiency of Sinkhorn $RW_2$ over classical Sinkhorn is not significant since the maximum over the shift cost matrix needs a lower bound of the L2 norm $\||\bar{\mu} - \bar{\mu}\||$ with an order of $\sqrt{n}$.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: - Corollary 1 seems to be extendable to all values of p and not only p=2. The proof of it might not be straightforward, but I am curious to know if you already have some counter-examples showing that if $P$ is an optimal map for the untranslated distributions, then after translating the distributions, the same $P$ would not have an optimal cost. 
- For the experiments on numerical validation, can you explain why the Sinkhorn algorithm running time is not changing for the values of $s\in[0,2.4]$ and then suddenly drops to around 0 times (Figure 3 (c))? Based on your discussion in Section 4.4, when the shift increases, the diameter should also increase and we should expect to see higher running times.  
- In the same experiment, why is there a sharp increase in the error of the Sinkhorn algorithm for $s>2.4$ (Figure 3 (d))? Am I right that for $s>2.4$, the Sinkhorn algorithm did not compute anything and just returned 0 as the output cost? 
- Figure 3 (b): what is the computation error? Why do the two methods have the same set of errors for all values of s?  
- Also, based on the experiments in the appendix on numerical validation, there are sharp increases and decreases in the results, which is unintuitive. What is the number of runs you performed for each value of $s$ that resulted in those plots?
soundness: 3
strengths: - The paper presents the properties of finding the Wasserstein distance when we are allowed to shift the distributions.
- The paper also presents algorithms for approximating the $RW_p$.
summary: This paper presents a new Wasserstein-based distance function, called the relative-translation invariant Wasserstein distance $RW_p$, which given two distributions $\mu$ and $\nu$, finds the optimal pair of shift and transport map $(s, P)$ that minimizes the transport cost of $P$ between $\mu$ and the translated distribution $\nu$ by a vector $s$. It is shown that this distance is a metric and can be computed by computing the gradients and alternatively updating the shift $s$ and the transport map $P$. 

When $p=2$, the paper shows that the object function of $RW_2$ can be expressed as minimizing the sum of two functions, where one is independent of the shift and the other is independent of the transport map. In this case, the authors use the Sinkhorn algorithm to speed up the computation of $RW_2$. Furthermore, the authors show that the diameter of the point sets after applying the optimal shift would reduce for empirical distributions derived from sub-Gaussian distributions, hence improving the execution time of the Sinkhorn algorithm.
weaknesses: - I think the proof of triangle inequality has some mistakes. My main concern is where you set $W_p(\eta, \eta')$ to 0 from line 2 to line 3. If $[W_p]$ refers to the Wasserstein distance between the classes of $\mu$ and $\nu$, then essentially $RW_p=[W_p]$ and from line 1 to line 2 of the Equation, you are assuming the triangle inequality holds for your distance. If $[W_p]$ just means the Wasserstein distance, then $W_p(\eta, \eta')$ might not be 0. (It seems reasonable that $RW_p$ is a metric, so my concern mostly is that the proof is not written correctly and not that the theorem is incorrect.)
- It is good that the method is implementable and can be used to test the performance of the new distance function, but current experimental results do not convey the message. For the numerical validation part, see my questions below. For the thunderstorm pattern detection, although visually $RW_2$ performs better than $W_2$ in Figure 4, I would say it is hard to judge the results in Figure 9 and Figure 8. I would strongly suggest adding experiments with a ground truth to your next version; something like an image retrieval task on labeled images, where you randomly shift a dataset of labeled images and show an improvement in the accuracy of the retrieved images for each query image when using $RW_2$ instead of $W_2$.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: - How does the proposed $RW_p$ distance compare with the GW distance in theory and experiment, which is also translation-invariant and focuses on shape similarity? Which types of distributions translation where the $RW_p$ distances may not perform well compared to other invariant metrics? Again, including such comparisons supports the paper with the broader range of translation invariant Wasserstein-based distances.

- Could you provide theoretical analysis or empirical observations on the convergence rates of $RW_p$? 

- Can the $RW_p$ be extended to handle other types of distribution shifts, such as scaling or rotation? 

- For the pattern detection experiment, is the thunderstorm snapshot data labeled? If it is, could you provide the accuracy of retrieved similar patterns to better quantify the performance of $RW_p$?

- Is the code public for the experiment section?
soundness: 2
strengths: - Novelty, paper presents a novel shifting-invariant Wasserstein-based metric, which extends the original Wasserstein distance to be invariant under shifting translations
- Clarity and Mathematical Soundness, this paper is generally well-written with clear explanations. The authors provide solid mathematical proofs for the metric properties and the relation to Wasserstein distance.
- Algorithm Development, this paper proposed two algorithm implementations for the $RW_p$ distances, the $RW_2$ Sinkhorn preforms better than the original Sinkhorn according to the experiment results
summary: The paper introduces a shifting invariant Wasserstein-based metric called relative-translation invariant Wasserstein distances $RW_p$ to measure the similarity between shifted distributions. We can see this distance generalized the original Wasserstein by being invariant to distribution translations. For $p = 2 $, the $RW_2$ distance shows promising properties such as the decomposability of the optimal transport model and translation invariance of coupling solutions. The authors propose two algorithms for computing general $RW_p$ and a variant of the Sinkhorn algorithm for $RW_2$ computation. Also, the theoretical analysis of numerical stability and time complexity is provided. In the end, they conducted two experiments in comparison with Sinkhorn to validate the new metric performance, which includes a computational time comparison and an image retrieval task with a weather dataset.
weaknesses: - This paper does not provide an analysis of the convergence rates of the $RW_p$ distances as a distribution measure. 

- This paper lacks theoretical and experimental comparisons with Gromov-Wasserstein (GW) distance that has similar invariance properties. The GW distance is also translation-invariant and compares distributions based on the shapes, which makes it a good benchmark for comparison in the experiment section [1]. A recent work [2] proposed a robust p-Wasserstein distance (RPW), that claims robustness under shifting perturbations, especially when $p = 2$. A similar image retrieval task was conducted in this work. In general, I feel like the paper lacks comparisons with related works, such as GW distance and RPW both in theory and practice. 

With these two major drawbacks, I tend to reject this paper for major revisions.

[1] Mémoli, Facundo. "Gromov–Wasserstein distances and the metric approach to object matching." Foundations of computational mathematics.

[2] Raghvendra, Sharath, Pouyan Shirzadian, and Kaiyi Zhang. "A New Robust Partial p-Wasserstein-Based Metric for Comparing Distributions." Forty-first International Conference on Machine Learning.

---

confidence: 3
contribution: 1
initial_rating: 3
presentation: 3
questions: The first approach that comes to mind for solving this problem is to subtract the mean of both distributions, thereby transforming them into zero-mean distributions. We could then calculate the Wasserstein distance between these two zero-mean distributions. However, I am concerned about why the method proposed by the authors is superior to this straightforward option. If the authors can address this question, I may reconsider my score.
soundness: 3
strengths: The paper is well written, and the mathematical proofs are rigorous.
summary: This paper focuses on finding a distance metric between distributions that is invariant to translation while also possessing the desirable properties of the Wasserstein distance. The authors propose a new metric and provide both theoretical and numerical proofs demonstrating that it satisfies the properties of a metric and is invariant to translation. Their analysis is conducted specifically for discrete distributions. Additionally, the paper introduces an algorithm for measuring a special case referred to as RW_2.
weaknesses: The literature review section needs improvement; it fails to explain why this problem is important and does not address previous efforts made to solve it. Additionally, the work is not clearly positioned within the existing literature.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: Some minor comments:

In Algorithm 1, where was $\eta_2$ used?

In Theorem 4, $\bar{\mu}$ and $\bar{\nu}$ are not defined. They are only defined later.
soundness: 2
strengths: Classical Wasserstein distance $W_p$ cannot identify similar "shape" patterns in data when their exact locations are irrelevant. Motivated by detecting weather patterns from geographical images and robustness in distributional shift, the paper proposed a new distance metric on the space of probability distributions, called the relative-translation invariant Wasserstein ($RW_p$) distance.

The decomposition of the relative translation optimal transport (ROT) problem into a vertical move along orbit in the quotient space and a horizontal move is interesting. For $p=2$, this decomposition turns out to be an orthogonal "bias-variance" structure of the $W_2$ distance. This effectively generalizes the Bures-Wasserstein distance for Gaussians to translation invariant distributions.

The proposed Algorithm 1 for general $RW_p$ is a coordinate-type algorithm for solving ROT: the vertical component is solved via gradient descent and the horizontal is solved by Sinkhorn or linear programming. When $p=2$, proposed Algorithm 2 is essentially an orbit debiased Sinkhorn algorithm, to avoid numeric instability. Some numerical experiments are performed to demonstrate better numeric stability.
summary: This paper proposed a relative-translation invariant Wasserstein distance $RW_p$. Two algorithms were proposed to compute the RW distance: a two-stage algorithm for the general $p$ case, and a variant Sinkhorn algorithm to compute $RW_2$.
weaknesses: In Section 4.4, the paper claims that "Consequently, our $RW_2$ method achieves better time complexity compared to $W_2$" in Remark 1 (page 8). I am not convinced why it is so. Theorem 5 only proves that with high probability the largest value of centered pairwise distances between source and target distributions (i.e., worst cost value) gets improved. It is widely unclear why this result alone implies better time or iteration complexity for solving $RW_p$ than $W_p$. In particular, if $p \neq 2$, solving $W_p$ requires only a pass of solving Sinkhorn, while $RW_p$ (with unknown means of source and target) has to solve many Sinkhorn subproblems. In such case, an iteration complexity should be given to justify better time complexity compared to $W_p$. If $p=2$, the proposed Algorithm 2 is almost identical to the Sinkhorn algorithm with an additional step to pre-compute the mean vectors to avoid numeric instability. I don't see much computational advantage in practice for using $RW_p$.

In practice, we need to choose $p$. Different $p$'s seem to give very different results (e.g., Section 5.2). What is the practical and/or theoretical guidance of choosing $p$? Moreover, for $p \neq 2$, how to determine the step size parameter $\eta_1$ in the horizontal gradient descent? Is it constant step size or is it annealed? Any theoretical justification should be helpful to guide the choice of $\eta_1$.

The simulation example in Section 5.1 is too simple. For Gaussians, it is not necessary to compute Wasserstein distances (vanilla and proposed) based on Sinkhorn. One should have closed form for both distances. More extensive settings (such as much higher-dimensional non-Gaussian distributions for general $p \geq 1$) should be used to demonstrate numerical benefit of debiasing the centers.

Meta-review: The authors propose a novel relative-translation invariant Wasserstein ($RW_p$) distance to deal with the translation shift for Wasserstein distance. The authors prove that it satisfies the metric property. The authors propose two algorithmic approach for the proposed problem: two-stage optimization, and a variant of Sinkhorn algorithm. The authors test the proposed distance on a toy example and thunderstorm pattern detection task. 

The Reviewers raised concerns on the related works/baselines for the translation shift with optimal transport based approach (e.g., Gromov Wasserstein and robust partial p-Wasserstein which are highly relevant to the considered problem), and the simple baseline based on zero-means (which is highly related to the case $p=2$, and the translation property of the standard optimal transport with squared Euclidean cost). The Reviewers raised concerns about the instability (e.g., dividing by zero issue in which more attention should be required to address). The Reviewers also raised concerns on the empirical evidence for the advantages of the proposed method (e.g., the toy example with Gaussian distribution is not clear, given the closed-form solution of Wasserstein; and there is no ground truth on the thunderstorm patter detection task which leads to unclear evaluation on advantages of the proposed approach. Additionally, it is not clear for the Reviewers why the proposed method can have better time complexity than the standard OT given its definition.

Overall, it is necessary for a major revision to improve the submission. The authors may consider the Reviewers' comments to revise the submission.

Decision: Reject