# A New Robust Partial $p$-Wasserstein-Based Metric for Comparing
Distributions

Sharath Raghvendra  Pouyan Shirzadian  Kaiyi Zhang

###### Abstract

The $2$-Wasserstein distance is sensitive to minor geometric differences
between distributions, making it a very powerful dissimilarity metric.
However, due to this sensitivity, a small outlier mass can also cause a
significant increase in the $2$-Wasserstein distance between two similar
distributions. Similarly, sampling discrepancy can cause the empirical
$2$-Wasserstein distance on $n$ samples in $\mathbb{R}^{2}$ to converge to the
true distance at a rate of $n^{-1/4}$, which is significantly slower than the
rate of $n^{-1/2}$ for $1$-Wasserstein distance. We introduce a new family of
distances parameterized by $k\geq 0$, called $k$-RPW that is based on
computing the partial $2$-Wasserstein distance. We show that (1) $k$-RPW
satisfies the metric properties, (2) $k$-RPW is robust to small outlier mass
while retaining the sensitivity of $2$-Wasserstein distance to minor geometric
differences, and (3) when $k$ is a constant, $k$-RPW distance between
empirical distributions on $n$ samples in $\mathbb{R}^{2}$ converges to the
true distance at a rate of $n^{-1/3}$, which is faster than the convergence
rate of $n^{-1/4}$ for the $2$-Wasserstein distance. Using the partial
$p$-Wasserstein distance, we extend our distance to any $p\in[1,\infty]$. By
setting parameters $k$ or $p$ appropriately, we can reduce our distance to the
total variation, $p$-Wasserstein, and the Lévy-Prokhorov distances.
Experiments show that our distance function achieves higher accuracy in
comparison to the $1$-Wasserstein, $2$-Wasserstein, and TV distances for image
retrieval tasks on noisy real-world data sets.

Machine Learning, ICML

##  1 Introduction

Given two probability distributions $\mu$ and $\nu$ with supports
${\mathcal{A}}$ and ${\mathcal{B}}$, let, for any
$(a,b)\in{\mathcal{A}}\times{\mathcal{B}}$, $d(a,b)$ be the cost of moving a
unit mass from $a$ to $b$. A _transport plan_ $\gamma$ is a coupling of $\mu$
and $\nu$, i.e., a joint distribution over the support
${\mathcal{A}}\times{\mathcal{B}}$ whose first and second marginals are $\mu$
and $\nu$. For $p\geq 1$, consider the case where the support of $\mu$ and
$\nu$ lie in a metric space $({\mathcal{X}},c)$ with a unit diameter, i.e.,
$c(a,b)\leq 1$ for any pair $(a,b)\in{\mathcal{X}}\times{\mathcal{X}}$ and the
cost of moving unit mass from $a$ to $b$ is given by $d(a,b)=c(a,b)^{p}$. For
any transport plan $\gamma$ between $\mu$ and $\nu$, the cost of $\gamma$ is
defined as

$w_{p}(\gamma):=\left(\int_{{\mathcal{X}}\times{\mathcal{X}}}c(x,y)^{p}\,\mathrm{d}\gamma(x,y)\right)^{1/p}.$

Let $\gamma^{*}$ be a minimum-cost transport plan between $\mu$ and $\nu$.
Then, the _$p$ -Wasserstein distance_ between $\mu$ and $\nu$ is defined as
$W_{p}(\mu,\nu):=w_{p}(\gamma^{*})$.

The $p$-Wasserstein distance is a powerful metric for measuring similarities
between probability distributions. Due to its numerous mathematical
properties, the $p$-Wasserstein distance has found diverse applications
including in machine learning (Chang et al., 2023; Chuang et al., 2022;
Mohajerin Esfahani & Kuhn, 2018; Janati et al., 2019; Luise et al., 2018;
Oquab et al., 2023; Vincent-Cuaz et al., 2021), computer vision (Backurs et
al., 2020; Gupta et al., 2010; Lai et al., 2022), and natural language
processing (Alvarez-Melis & Jaakkola, 2018; Huang et al., 2016; Yurochkin et
al., 2019). One can estimate the $p$-Wasserstein distance between two unknown
distributions $\mu$ and $\nu$ by simply taking $n$ samples from each $\mu$ and
$\nu$ and then computing the $p$-Wasserstein distance between the discrete
distributions over these samples (each sample point is assigned a mass of
$1/n$). For $p\in[1,\infty)$, it is well-known that as $n\rightarrow\infty$,
this _empirical $p$-Wasserstein_ distance converges to the true
$p$-Wasserstein distance. Due to this law of weak convergence, the
$p$-Wasserstein distance is used as a loss function in training generative
models (Arjovsky et al., 2017; Genevay et al., 2018; Salimans et al., 2018).

The $p$-Wasserstein distance is sensitive to geometric dissimilarities between
the distributions. Consider two distributions $\mu$ and
$\nu=(1-\delta)\mu+\delta\nu^{\prime}$ that differ only by a mass of $\delta$.
The $p$-Wasserstein distance between $\mu$ and $\nu$ can be as high as
$\delta^{1/p}W_{p}(\mu,\nu^{\prime})$. Thus, as $p$ increases, the
$W_{p}(\mu,\nu)$ increases by a rate of $\delta^{1/p}$, making $W_{p}$ more
sensitive to such differences for larger values of $p$. The higher sensitivity
of $p$-Wasserstein distance for $p>1$ makes it an attractive choice as a
dissimilarity metric between distributions. Consequently, it can be used in
clustering (El Malki et al., 2020; Zhuang et al., 2022) and barycenter
computation (Claici et al., 2018; Cuturi & Doucet, 2014; Vaskevicius & Chizat,
2023).

The higher sensitivity of $p$-Wasserstein distance for larger values of $p$
also makes it susceptible to noise of two types: outliers and sampling
discrepancy. Consider $\mu$ and $\nu=0.99\mu+0.01\nu^{\prime}$ and
$W_{p}(\mu,\nu^{\prime})=1$, i.e., we add an _outlier_ mass of $\delta=0.01$
that is placed at a distance $1$ from $\mu$. In this case, $\mu$ and $\nu$
differ in only $1\%$ of mass and yet, the distance between $\mu$ and $\nu$ is
$0.1$ when $p=2$, $0.21$ when $p=3$, and $1$ when $p=\infty$. Thus, for $p\geq
2$, outliers can disproportionately increase the distance between
distributions.

Similar to outliers, sampling discrepancies in empirical distributions can
also contribute disproportionately to the overall $p$-Wasserstein distance. As
a result, in $2$-dimensions, the convergence rate of the empirical
$p$-Wasserstein distance to the true distance drops to $n^{-1/2p}$ and for
$p=\infty$, the empirical distance does not even converge to the real one
(Fournier & Guillin, 2015). To understand this phenomenon better, consider
$p=2$ and a discrete distribution $\mu$ having two points $a$ and $b$ in its
support, each assigned a probability mass of $1/2$. Let $c(a,b)=1$. Consider
now two sets $X$ and $Y$ of $n$ samples drawn from $\mu$ and let $\mu_{X}$
(resp. $\mu_{Y}$) be the discrete distributions with points of $X$ (resp. $Y$)
as the support and a mass of $1/n$ at each point in the support. Note that
$\mathbb{E}[|\mu_{X}(a)-\mu_{Y}(a)|]=\Theta(1/\sqrt{n})$ and therefore,
$W_{2}(\mu_{X},\mu_{Y})\approx n^{-1/4}$ and $W_{p}(\mu_{X},\mu_{Y})\approx
n^{-1/2p}$. Thus, the rate of convergence for $p\geq 2$ is slower than for the
case with $p=1$. Therefore, one needs significantly more samples to get an
accurate estimate of the true $2$-Wasserstein distance. This restricts the use
of $2$-Wasserstein distance (and also other higher values of $p$) as a loss
function in learning tasks.

One way to overcome the impact of noise from outliers or sampling discrepancy
is by using the partial $p$-Wasserstein distance. For _$\alpha$ -partial
$p$-Wasserstein distance_, one wishes to compute the cheapest cost of a
transport plan that transports $\alpha$ mass between distributions $\mu$ and
$\nu$. Such transport plan is referred to as _$\alpha$ -optimal partial
transport plan_ (or simply _$\alpha$ -partial OT plan_). Given two
distributions $\mu$ and $\tilde{\nu}=(1-\delta)\nu+\delta\nu^{\prime}$, and
under reasonable assumptions on the outlier distribution $\nu^{\prime}$, one
can show that the transport plan associated with a $(1-\delta)$-partial
$p$-Wasserstein distance will transport mass only from the inliers. This
observation was used to eliminate the impact of outliers in two distributions
and applied to many ML tasks (Choi et al., 2024; Le et al., 2021; Nietert et
al., 2023). Most of these applications assume that the value of $\delta$ is
given; see (Caffarelli & McCann, 2010; Chapel et al., 2020; Figalli, 2010;
Nietert et al., 2022). Recently, Phatak et al. (2022) introduced the idea of
_OT-profile_ , which is a function that maps any $\alpha\in[0,1]$ to the
$\alpha$-partial $p$-Wasserstein distance between $\mu$ and $\nu$. They showed
that this function is a non-decreasing function111Their function maps $\alpha$
to the $p$th power of the $\alpha$-partial $p$-Wasserstein distance. In this
paper, however, we assume that the function maps $\alpha$ to the partial
$p$-Wasserstein distance and not its $p^{th}$ power., which can be used to
also identify the value of $\delta$. All existing works that use partial
$p$-Wasserstein distance to identify outliers are described for pairs of
distribution. It is not clear how one can apply this distance on a set
containing noisy distributions.

Additionally, there are two major drawbacks of using $(1-\delta)$-partial
$p$-Wasserstein distance as a dissimilarity measure on sets of probability
distributions.

  * •

The $(1-\delta)$-partial $p$-Wasserstein distance does not satisfy the
triangle inequality, and

  * •

For two distributions $\mu$ and $\nu$ that differ by a mass less than
$\delta$, the $(1-\delta)$-partial $p$-Wasserstein distance will be $0$, i.e.,
this cost is not sensitive to minor geometric differences in distributions.

In another line of work, given a parameter $\lambda>0$, Mukherjee et al.
(2021) presented a robust distance called the $\lambda$-ROBOT, which is simply
the $p$-Wasserstein cost between $\mu$ and $\nu$ under the truncated ground
distance metric $c_{\lambda}(a,b)=\min\\{c(a,b),2\lambda\\}$ 222Originally,
Mukherjee et al. (2021) presented $\lambda$-ROBOT as the $1$-Wasserstein
distance between $\mu$ and $\nu$ under $c_{\lambda}(\cdot,\cdot)$. For any
$p>1$, one can extend their distance by computing the $p$-Wasserstein distance
under $c_{\lambda}(\cdot,\cdot)$.. Although $\lambda$-ROBOT is a metric, it
remains sensitive to outliers and sampling discrepancies. For instance,
similar to the $p$-Wasserstein distance, a mass of $\delta$ can
disproportionately increase $\lambda$-ROBOT by $2\lambda\delta^{1/p}$. Also,
the convergence rate of the empirical $\lambda$-ROBOT to the true
$\lambda$-ROBOT in two-dimensional space would be $2\lambda n^{-1/2p}$.

An important open question is the following:

Can we design a new metric that, for $p>1$, retains the sensitivity of
$p$-Wasserstein distance to minor geometric differences in the distributions,
but is robust to noise?

##### Our Results:

For any $k\geq 0$, we introduce a partial $p$-Wasserstein distance-based
metric called $(p,k)$-RPW and we denote it by $\Pi_{p,k}(\cdot,\cdot)$. Our
distance is simply the smallest $\varepsilon$ such that the
$(1-\varepsilon)$-partial $p$-Wasserstein distance is at most $k\varepsilon$.

|
---|---
(i) Distributions $\mu$ and $\nu$ | (ii) $\|\mu-\nu\|_{\mathrm{TV}}$
|
(iii) $W_{p}(\mu,\nu)$ | (iv) $\Pi_{p,k}(\mu,\nu)$
Figure 1: Interpretations of different distance functions.

Our distance combines the total variation distance with the $p$-Wasserstein
distance. Recollect that the total variation distance between $\mu$ and $\nu$
is the mass that remains after all the co-located mass is transported. In
Figure 1 (ii), the mass inside the green region represents the TV distance
between two distributions. The $p$-Wasserstein distance measures the cost of
the cheapest transport plan that leaves no mass behind. In Figure 1 (iii), the
cost of moving all the mass from the red region to the blue region represents
the $p$-Wasserstein distance. Our distance balances the two, i.e., we find an
$\varepsilon$ such that a transport plan that leaves $\varepsilon$ mass behind
has a cost of $k\varepsilon$. In Figure 1 (iv), our distance balances the cost
of moving mass from the red region to the blue region with the mass remaining
inside the green region. The robustness of our distance follows from the
observation that noisy mass will be part of the green region (i.e., mass that
is not transported) and therefore, cannot contribute disproportionately to the
cost. We establish the following properties for our distance function:

  * •

Metric Property: For any choice of $p\geq 1$ and $k\geq 0$, the distance
$(p,k)$-RPW is a metric. Unlike the $(1-\delta)$-partial $p$-Wasserstein
distance, our distance function satisfies the triangle inequality.
Furthermore, unlike the $(1-\delta)$-partial $p$-Wasserstein distance, where
two distributions $\mu$ and $\nu$ can have a cost of $0$ even if they differ
by a mass of $\delta$, for any two distributions $\mu$ and $\nu$ with
$\mu\neq\nu$, $\Pi_{p,k}(\mu,\nu)>0$. See Theorem 3.

  * •

Robust to Outliers: Given two distributions $\mu$ and $\nu$, adding a mass of
$\delta$ to $\nu$ will change $\Pi_{p,k}(\mu,\nu)$ by at most $\pm\delta$. In
other words, an outlier mass of $\delta=0.01$ cannot increase the
$\Pi_{p,k}(\mu,\nu)$ by more than $0.01$. Recollect that this can be as high
as $0.1$ for $2$-Wasserstein distance and $0.21$ for $3$-Wasserstein distance.
See Theorem 3.1.

  * •

Robust to Sampling Discrepancy: In $2$ dimensions, the $(p,1)$-RPW between
empirical distributions converges to the true $(p,1)$-RPW distance at a rate
of $n^{-\frac{p}{4p-2}}$. In contrast, the rate of convergence of the
$2$-Wasserstein and the $\lambda$-ROBOT distances are $n^{-1/2p}$ and
$2\lambda n^{-1/2p}$, respectively. Note that, for $p=\infty$, our distance
converges at the rate of $n^{-1/4}$ whereas the $\infty$-Wasserstein distance
does not converge. Our results extend to any dimension. For $d\geq 2$ and
$p>\frac{d}{2}$, we show that the convergence rate of the empirical
$(p,1)$-RPW is significantly faster than that of the $p$-Wasserstein distance.
See Theorem 3.3.

Alternatively, in Figure 2, suppose point $(x^{*},y^{*})$ is the intersection
point of the line $y=k(1-x)$ with the OT-profile. Then, our distance is simply
$(1-x^{*})$. Note that when $k=0$, our distance becomes the total variation
distance. When we set $k$ to be sufficiently large, our distance becomes
$W_{p}(\mu,\nu)/k$. In this sense, our distance interpolates between the total
variation distance and the $p$-Wasserstein distance. By choosing the
parameters $k$ or $p$ correctly, we can reduce our distance to several well-
known distances.

Figure 2: Interpretation of distances based on the OT-profile.

  * •

Relation to Lévy-Prokhorov distance: $(\infty,1)$-RPW between any two
distributions $\mu$ and $\nu$ is equal to their Lévy-Prokhorov distance. See
Lemma 4.

  * •

Relation to total variation distance: For any $p\geq 1$, $(p,0)$-RPW between
any two distributions $\mu$ and $\nu$ is equal to the total variation distance
between $\mu$ and $\nu$. See Lemma 4.

  * •

Relation to $p$-Wasserstein distance: For any $p\geq 1$, as
$k\rightarrow\infty$, $k\times\Pi_{p,k}(\mu,\nu)$ approaches the
$p$-Wasserstein distance. See Lemma 4.

In our experiments, we use our distance from a query image to rank images in a
database of noisy images. Using this, we identify the top ten images in our
database that are similar to the query. For the MNIST, CIFAR-10, and COREL
datasets, our distance produces a higher accuracy in comparison to the
accuracy produced by the $1$-Wasserstein, $2$-Wasserstein, and the TV
distances.

###  1.1 Notations.

For any distribution $\mu$ defined over a compact set ${\mathcal{X}}$, let
${\mathcal{M}}(\mu):=\int_{\mathcal{X}}\mathrm{d}\mu(x)$ denote the total mass
of $\mu$. For a metric space $({\mathcal{X}},c)$, define the diameter of
${\mathcal{X}}$ as $\max_{(a,b)\in{\mathcal{X}}\times{\mathcal{X}}}c(a,b)$.
For any pair of distributions $\mu$ and $\nu$ defined over $({\mathcal{X}},c)$
and parameters $p\geq 1$ and $\alpha\in[0,1]$, let $W_{p,\alpha}(\mu,\nu)$
denote the $\alpha$-partial $p$-Wasserstein distance between $\mu$ and $\nu$.

##  2 Robust Partial $p$-Wasserstein Metric

Given two probability distributions $\mu$ and $\nu$ defined over a metric
space $({\mathcal{X}},c)$ with a unit diameter and any parameters $p\geq 1$
and $k\geq 0$, we define the $(p,k)$-_Robust Partial $p$-Wasserstein distance_
or simply $(p,k)$-_RPW_ between $\mu$ and $\nu$, denoted by
$\Pi_{p,k}(\mu,\nu)$, to be the minimum value $\varepsilon\geq 0$ such that
the $(1-\varepsilon)$-partial $p$-Wasserstein distance between $\mu$ and $\nu$
is at most $k\varepsilon$; more precisely,

$\Pi_{p,k}(\mu,\nu)=\inf\\{\varepsilon\geq 0\mid
W_{p,1-\varepsilon}(\mu,\nu)\leq k\varepsilon\\}.$ (1)

Alternatively, let $P=(x^{*},y^{*})$ be the intersection point of the OT-
profile curve with the line $y=k(1-x)$. Then, $(p,k)$-RPW between $\mu$ and
$\nu$ would be $\Pi_{p,k}(\mu,\nu)=1-x^{*}$.

We show that $(p,k)$-RPW distance satisfies all the metric properties. The
triangle inequality is the only property for which the proof is non-trivial.
We provide a sketch of the proof below; see Appendix A.1 for details.

For any three probability distributions $\mu$, $\nu$, and $\kappa$, suppose
$\Pi_{p,k}(\mu,\kappa)=\varepsilon_{1}$ and
$\Pi_{p,k}(\kappa,\nu)=\varepsilon_{2}$. Let $\gamma_{1}$ denote a
$(1-{\varepsilon_{1}})$-partial OT plan from $\mu$ to $\kappa$ and
$\gamma_{2}$ be a $(1-\varepsilon_{2})$-partial OT plan from $\kappa$ to
$\nu$. In Figure 3, the blobs in the left, middle, and right show the
distributions $\mu$, $\kappa$, and $\nu$, respectively, and the blue (resp.
red) arrows correspond to the transport plan $\gamma_{1}$ (resp.
$\gamma_{2}$). Let $\kappa_{1}$ (resp. $\kappa_{2}$) be the mass of $\kappa$
that is transported from $\mu$ (resp. to $\nu$) by $\gamma_{1}$ (resp.
$\gamma_{2}$) (shown in Figure 3 by the blue (resp. red) region inside the
distribution $\kappa$). Define $\kappa_{\mathrm{c}}$ to be the distribution of
mass of $\kappa$ that is common to both $\kappa_{1}$ and $\kappa_{2}$ (the
purple region inside the distribution $\kappa$ in Figure 3). Note that the
total mass of $\kappa_{1}$ that is not transported by $\gamma_{2}$ is at most
$\varepsilon_{2}$; therefore,

${\mathcal{M}}(\kappa_{c})\geq{\mathcal{M}}(\kappa_{1})-\varepsilon_{2}=1-\varepsilon_{1}-\varepsilon_{2}.$
(2)

Define $\mu_{\mathrm{c}}$ (resp. $\nu_{\mathrm{c}}$) to be the distribution
whose mass is transported to (resp. from) $\kappa_{c}$ in $\gamma_{1}$ (resp.
$\gamma_{2}$). In Figure 3, the distribution $\mu_{\mathrm{c}}$ (resp.
$\nu_{\mathrm{c}}$) is depicted by the purple region inside distribution $\mu$
(resp. $\nu$). From Equation (2),

${\mathcal{M}}(\mu_{\mathrm{c}})={\mathcal{M}}(\nu_{\mathrm{c}})={\mathcal{M}}(k_{\mathrm{c}})\geq
1-\varepsilon_{1}-\varepsilon_{2}$ (3)

Therefore, we have

$\displaystyle W_{p,1-\varepsilon_{1}-\varepsilon_{2}}(\mu,\nu)$
$\displaystyle\leq W_{p}(\mu_{\mathrm{c}},\nu_{\mathrm{c}})$
$\displaystyle\leq
W_{p}(\mu_{\mathrm{c}},\kappa_{\mathrm{c}})+W_{p}(\kappa_{\mathrm{c}},\nu_{\mathrm{c}})$
$\displaystyle\leq k(\varepsilon_{1}+\varepsilon_{2}).$ (4)

The second inequality follows from the triangle inequality of $p$-Wasserstein
distances and the third inequality follows from the definition of our
distance. Furthermore, since $\Pi_{p,k}(\mu,\nu)$ is the minimum $\varepsilon$
with $W_{p,1-\varepsilon}(\mu,\nu)\leq k\varepsilon$, from Equation (4),
$\Pi_{p,k}(\mu,\nu)\leq\varepsilon_{1}+\varepsilon_{2}$, as desired.

Figure 3: The triangle inequality of the RPW distance function.

theoremmetric Given a metric space $({\mathcal{X}},c)$ with a unit diameter
and any parameters $p\geq 1$ and $k\geq 0$, the $(p,k)$-RPW distance function
$\Pi_{p,k}(\cdot,\cdot)$ for all probability distributions defined over
$({\mathcal{X}},c)$ is a metric.

The following lemma highlights a useful feature of our metric, which is used
in deriving its important properties.

lemmamaxalphabeta Given two probability distributions $\mu$ and $\nu$ defined
over a metric space $({\mathcal{X}},c)$ with a unit diameter and parameters
$p\geq 1$ and $k\geq 0$, suppose $W_{p,1-\alpha}(\mu,\nu)=k\beta$ for some
$\alpha,\beta\geq 0$. Then, $\Pi_{p,k}(\mu,\nu)\leq\max\\{\alpha,\beta\\}$.
Furthermore, if $k\neq 0$, then
$\Pi_{p,k}(\mu,\nu)\leq\min\\{\alpha,\beta\\}$.

##  3 Robustness Properties

In Section 3.1, we show that an outlier mass of $\delta$ cannot increase the
RPW distance by more than $\delta$, i.e., the RPW distance is robust to
outliers. In Section 3.2, we show that the rate of convergence of the
empirical RPW distance to the real RPW distance is asymptotically smaller than
the rate of convergence for $p$-Wasserstein distance. Thus, we show that the
RPW distance is more robust to outliers as well as sampling discrepancies than
the $p$-Wasserstein distance.

###  3.1 Robustness to Outlier Noise

For $\delta\in(0,1)$, let $\tilde{\nu}:=(1-\delta)\nu+\delta\nu^{\prime}$ be a
noisy distribution obtained from $\nu$ contaminated with $\delta$ mass from a
noise distribution $\nu^{\prime}$. In Theorem 3.1, we show that by distorting
the noise distribution $\nu^{\prime}$, an adversary cannot arbitrarily change
the $(p,k)$-RPW distance between $\mu$ and $\tilde{\nu}$.

theoremdistortion For any probability distributions $\mu,\nu$, and
$\nu^{\prime}$ defined over a metric space $({\mathcal{X}},c)$ with a unit
diameter and parameters $p\geq 1,k\geq 0$, and $\delta\in(0,1)$, let
$\tilde{\nu}=(1-\delta)\nu+\delta\nu^{\prime}$. Then,

$\Pi_{p,k}(\mu,\nu)-\delta\leq\Pi_{p,k}(\mu,\tilde{\nu})\leq(1-\delta)\Pi_{p,k}(\mu,\nu)+\delta.$

For a distribution $\mu$ and a noisy distribution $\tilde{\mu}$ that differs
from $\mu$ by only a $\delta$ fraction of mass (i.e.,
$\|\mu-\tilde{\mu}\|_{TV}=\delta$), consider the following assumption:

  * (A1)

The $(1-\frac{\delta}{10})$-partial $p$-Wasserstein distance between $\mu$ and
$\tilde{\mu}$ is at least $\frac{1}{2}W_{p}(\mu,\tilde{\mu})$.

Assuming (A1), in the following lemma, we show that the $(p,k)$-RPW distance
between $\mu$ and $\tilde{\mu}$ is proportionate to
$\min\left\\{\delta,\frac{1}{k}W_{p}(\mu,\tilde{\mu})\right\\}$.

lemmarobustnesss For a probability distribution $\mu$ defined over a metric
space $({\mathcal{X}},c)$ with a unit diameter and $\delta>0$, let
$\tilde{\mu}$ be a probability distribution that differs from $\mu$ by a
$\delta$ fraction of mass satisfying assumption (A1). Then, for any parameters
$p\geq 1$ and $k>0$,

$\displaystyle\Pi_{p,k}(\mu,\tilde{\mu})=\Theta\left(\min\left\\{\delta,\frac{1}{k}W_{p}(\mu,\tilde{\mu})\right\\}\right).$

Intuitively, if $\tilde{\mu}$ is only slightly different from $\mu$, i.e.,
$W_{p}(\mu,\tilde{\mu})\leq k\delta$, then the sensitivity of our metric would
be similar to that of the $p$-Wasserstein distance. On the other hand, if
$\tilde{\mu}$ is far from $\mu$ (i.e., the $\delta$ fraction of the mass of
$\tilde{\mu}$ that is different from $\mu$ is an outlier noise and
disproportionately increases the $p$-Wasserstein distance), then the
sensitivity of $(p,k)$-RPW is bounded by $\delta$.

###  3.2 Robustness to Sampling Discrepancies.

Next, we show that in the $2$-dimensional Euclidean space, the rate of
convergence of the empirical $(p,1)$-RPW to the true distance is
$\tilde{O}(n^{-\frac{p}{4p-2}})$, which is significantly faster than the
convergence rate of $\tilde{O}(n^{-\frac{1}{2p}})$ of the empirical
$p$-Wasserstein distance (Fournier & Guillin, 2015)333$\tilde{O}()$ hides
$\mathrm{poly}(\log n)$ from the convergence rate.. In particular, for
$p=\infty$, the convergence rate of our metric is
$\tilde{O}(n^{-\frac{1}{4}})$, whereas the empirical $p$-Wasserstein distance
does not converge to the true distance. For simplicity in presentation, we
restrict our analysis to $p=2$. Our bounds for any $p\geq 1$ and $d\geq 2$ are
stated in Theorem 3.3, whose proof is provided in Appendix A.2.

######  Lemma 3.1.

For any two probability distributions $\mu$ and $\nu$ defined over a metric
space with a unit diameter, suppose $\mu_{n}$ and $\nu_{n}$ are two empirical
distributions of $\mu$ and $\nu$, respectively. Then, with a high probability,

$|\Pi_{2,1}(\mu,\nu)-\Pi_{2,1}(\mu_{n},\nu_{n})|=\tilde{O}(n^{-\frac{1}{3}}).$

Note that for any pair of distributions $\mu$ and $\nu$ and their empirical
distributions $\mu_{n}$ and $\nu_{n}$, by the triangle inequality,

$|\Pi_{2,1}(\mu,\nu)-\Pi_{2,1}(\mu_{n},\nu_{n})|\leq\Pi_{2,1}(\mu,\mu_{n})+\Pi_{2,1}(\nu,\nu_{n}).$

Therefore, to prove Lemma 3.1, we bound $(2,1)$-RPW of any distribution $\mu$
to its empirical distribution $\mu_{n}$ in the following lemma.

######  Lemma 3.2.

Given a continuous probability distribution $\mu$ in the $2$-dimensional
Euclidean space and an empirical distribution $\mu_{n}$ of $\mu$,
$\Pi_{2,1}(\mu,\mu_{n})=\tilde{O}(n^{-\frac{1}{3}})$ with a high probability.

We begin by defining a set of notations that assist in proving Lemma 3.2. Let
${\mathcal{G}}$ be a grid with cell side length $n^{-\alpha}$ inside the unit
square. For any cell $\Box\in{\mathcal{G}}$, let $\mu(\Box)$ denote the mass
of $\mu$ inside $\Box$. Define the _excess mass_ of a cell $\Box$ as
$\mathrm{Exc}_{\mu}(\Box):=\max\\{0,\mu(\Box)-\mu_{n}(\Box)\\}$ and the excess
of the grid ${\mathcal{G}}$, denoted by $\mathrm{Exc}_{\mu}({\mathcal{G}})$,
as the total excess of all cells of ${\mathcal{G}}$, i.e.,
$\mathrm{Exc}_{\mu}({\mathcal{G}}):=\sum_{\Box\in{\mathcal{G}}}\mathrm{Exc}_{\mu}(\Box)$.
When $\mu$ is clear from context, we simplify notation and denote the excess
of ${\mathcal{G}}$ by $\mathrm{Exc}({\mathcal{G}})$.

lemmaconvergenceexcess For any distribution $\mu$ inside the unit square, an
empirical distribution $\mu_{n}$ of $\mu$, and a grid ${\mathcal{G}}$ with
cell side length $n^{-\alpha}$,
$\mathrm{Exc}_{\mu}({\mathcal{G}})=\tilde{O}(n^{\alpha-\frac{1}{2}})$ with a
high probability.

To better explain our proof for Lemma 3.2, we first present a weaker bound of
$\tilde{O}(n^{-\frac{3}{10}})$. In Appendix A.2.2, we improve our analysis and
obtain a rate of $\tilde{O}(n^{-\frac{1}{3}})$.

A weaker bound for Lemma 3.2. In the following, we construct a transport plan
$\gamma$ that transports all except $\tilde{O}(n^{-\frac{3}{10}})$ mass with a
cost of $\tilde{O}(n^{-\frac{3}{10}})$. Having computed such transport plan,
we then use Lemma 3 to conclude that
$\Pi_{p,k}(\mu,\nu)=\tilde{O}(n^{-\frac{3}{10}})$. The details are provided
next.

Define ${\mathcal{G}}_{1}$ (resp. ${\mathcal{G}}_{2}$) to be a grid with cell
side length $O(n^{-\alpha_{1}})$ (resp. $O(n^{-\alpha_{2}})$) for
$\alpha_{1}:=\frac{3}{10}$ (resp. $\alpha_{2}:=\frac{1}{5}$). The grids
${\mathcal{G}}_{1}$ and ${\mathcal{G}}_{2}$ are constructed in a way that
their boundaries are aligned with each other. Let $\gamma_{1}$ be a partial
transport plan that arbitrarily transports, for any cell
$\Box\in{\mathcal{G}}_{1}$, a mass of $\min\\{\mu(\Box),\mu_{n}(\Box)\\}$ from
$\mu_{n}$ to $\mu$. Define $\mu^{1}$ (resp. $\mu_{n}^{1}$) to be the
distribution of mass of $\mu$ (resp. $\mu_{n}$) that is not transported by
$\gamma_{1}$. Let $\gamma_{2}$ be a transport plan that transports, for any
cell $\Box\in{\mathcal{G}}_{2}$, a mass of
$\min\\{\mu^{1}(\Box),\mu_{n}^{1}(\Box)\\}$ from $\mu_{n}^{1}$ to $\mu^{1}$.
Define $\gamma=\gamma_{1}+\gamma_{2}$. This completes the construction of
$\gamma$. In the appendix, instead of two grids, we consider $O(\log\log n)$
grids and obtain the bound claimed in Lemma 3.2.

The transport plan $\gamma$ transports as much mass as possible inside each
cell of ${\mathcal{G}}_{2}$; therefore, the total mass that is not transported
by $\gamma$ is equal to the excess of the grid ${\mathcal{G}}_{2}$, which from
Lemma 3.2 is

$1-{\mathcal{M}}(\gamma)=\mathrm{Exc}({\mathcal{G}}_{2})=\tilde{O}(n^{\alpha_{2}-\frac{1}{2}})=\tilde{O}(n^{-\frac{3}{10}}).$
(5)

|
---|---
(a) | (b)
|
(c) | (d)

Figure 4: (a) A distribution $\mu$ (shaded gray area) and an empirical
distribution $\mu_{n}$ (red dots), (b) $\gamma_{1}$ transports as much mass as
possible inside each cell of ${\mathcal{G}}_{1}$, (c) for the remaining mass,
$\gamma_{2}$ transports as much remaining mass as possible inside the cells of
${\mathcal{G}}_{2}$, and (d) the transport plan $\gamma$, which is the sum of
$\gamma_{1}$ and $\gamma_{2}$.

Next, we show that the cost $w_{2}(\gamma)$ of the transport plan $\gamma$ is
$\tilde{O}(n^{-\frac{3}{10}})$. Recall that $\gamma=\gamma_{1}+\gamma_{2}$. In
our analysis, we first show that $w_{2}^{2}(\gamma_{1})=O(n^{-\frac{3}{5}})$
and then show that $w_{2}^{2}(\gamma_{2})=O(n^{-\frac{3}{5}})$. Using these
two bounds, we then conclude that $w_{2}^{2}(\gamma)=O(n^{-\frac{3}{5}})$, or
equivalently, $w_{2}(\gamma)=O(n^{-\frac{3}{10}})$.

Since $\gamma_{1}$ transports mass between points inside the same cell of
${\mathcal{G}}_{1}$, all mass transportation in $\gamma_{1}$ has a squared
cost of $O(n^{-2\alpha_{1}})=O(n^{-\frac{3}{5}})$ and
$w_{2}^{2}(\gamma_{1})=O(n^{-\frac{3}{5}})$. Furthermore, by Lemma 3.2, with a
high probability, the total mass of $\mu^{1}$ is
${\mathcal{M}}(\mu^{1})=\tilde{O}(n^{\alpha_{1}-\frac{1}{2}})=\tilde{O}(n^{-\frac{1}{5}})$.
Since the transport plan $\gamma_{2}$ transports at most
${\mathcal{M}}(\mu^{1})$ mass, each at a squared cost of
$O(n^{-2\alpha_{2}})=O(n^{-\frac{2}{5}})$,

$w_{2}^{2}(\gamma_{2})=\tilde{O}\big{(}{\mathcal{M}}(\mu^{1})\times
n^{-2\alpha_{2}}\big{)}=\tilde{O}(n^{-\frac{3}{5}}).$

As a result, the cost of $\gamma$ is

$\displaystyle w_{2}(\gamma)$
$\displaystyle=\sqrt{w_{2}^{2}(\gamma_{1})+w_{2}^{2}(\gamma_{2})}=\tilde{O}(n^{-\frac{3}{10}}).$
(6)

Note that $\gamma$ is a transport plan that transports all except
$\alpha=\tilde{O}(n^{-\frac{3}{10}})$ mass (Equation (5)) and has cost
$\tilde{O}(n^{-\frac{3}{10}})$ (Equation (6)). Hence,

$W_{2,1-\alpha}(\mu,\mu_{n})\leq w_{2}(\gamma)=\tilde{O}(n^{-\frac{3}{10}}).$

Plugging into Lemma 3, $\Pi_{2,1}(\mu,\mu_{n})=\tilde{O}(n^{-\frac{3}{10}})$.

In the appendix, we use an identical approach to obtain the rate of
convergence for any dimension $d\geq 1$ and any parameter $p\geq 1$. The
following lemma summarizes the results.

lemmaconvergenceGeneral Given a continuous probability distribution $\mu$ in
the $d$-dimensional Euclidean space, an empirical distribution $\mu_{n}$ of
$\mu$, and parameters $p\geq 1$ and $k>0$ constant, with a high probability,

$\Pi_{p,k}(\mu,\mu_{n})=\begin{cases}\tilde{O}(n^{-\frac{1}{d}}),\qquad&p\leq\frac{d}{2},\\\
\tilde{O}(n^{-\frac{p}{p(d+2)-d}}),&p>\frac{d}{2}.\end{cases}$

For any pair of distributions $\mu$ and $\nu$ and their empirical
distributions $\mu_{n}$ and $\nu_{n}$, by the triangle inequality,

$|\Pi_{p,k}(\mu,\nu)-\Pi_{p,k}(\mu_{n},\nu_{n})|\leq\Pi_{p,k}(\mu,\mu_{n})+\Pi_{p,k}(\nu,\nu_{n}).$

Combined with Lemma 4, we get the following corollary.

######  Theorem 3.3.

For two probability distributions $\mu$ and $\nu$ defined over a metric space
$({\mathcal{X}},c)$ with a unit diameter, suppose $\mu_{n}$ and $\nu_{n}$ are
two empirical distributions of $\mu$ and $\nu$, respectively. Then, for any
$p\geq 1$ and $k>0$ constant, with a high probability,

$|\Pi_{p,k}(\mu,\nu)-\Pi_{p,k}(\mu_{n},\nu_{n})|=\begin{cases}\tilde{O}(n^{-\frac{1}{d}}),\qquad&p\leq\frac{d}{2},\\\
\tilde{O}(n^{-\frac{p}{p(d+2)-d}}),&p>\frac{d}{2}.\end{cases}$

##### Extension to arbitrary diameter.

We can extend our distance and its properties to the case where the diameter
of the support is bounded by any $\Delta>0$ as follows. Define $(p,k)$-RPW
between distributions $\mu$ and $\nu$ to be the minimum value $\varepsilon>0$
such that $W_{p,1-\varepsilon}(\mu,\nu)\leq k\Delta\varepsilon$. In this case,
the metric property (Theorem 3) and the robustness to outliers (Theorem 3.1)
holds without any changes, and given that the diameter $\Delta$ is a constant,
our bounds for the convergence rate of the empirical $(p,k)$-RPW also holds as
stated in Theorem 3.3.

##  4 Relation to Other Distances

In this section, we discuss the relation of the $(p,k)$-RPW metric with three
other well-known distance functions, namely (i) Lévy-Prokhorov distance, (ii)
total variation, and (iii) $p$-Wasserstein distance. In particular, we first
show that the $(\infty,1)$-RPW is the same as the Lévy-Prokhorov distance. We
next show that for any $p\geq 1$, the $(p,k)$-RPW metric is an interpolation
between total variation and the $p$-Wasserstein distance. More precisely,
$\Pi_{p,0}(\cdot,\cdot)$ is the same as the total variation distance, and for
large values of $k$, the $(p,k)$-RPW will be close to
$\frac{1}{k}W_{p}(\cdot,\cdot)$.

##### Lévy-Prokhorov distance.

For any two distributions $\mu$ and $\nu$ defined over a set ${\mathcal{X}}$
in the $d$-dimensional Euclidean space, let $\pi(\mu,\nu)$ denote the Lévy-
Prokhorov distance of $\mu$ and $\nu$. In the following lemma, we show that
the $(\infty,1)$-RPW metric is equal to the Lévy-Prokhorov distance. The proof
of this lemma, which is provided in Appendix A.3, is similar to the approach
described by Lahn et al. (2021).

lemmarelationLevyy For any pair of probability distributions $\mu$ and $\nu$
in a metric space $({\mathcal{X}},c)$ with a unit diameter,
$\Pi_{\infty,1}(\mu,\nu)=\pi(\mu,\nu)$.

##### Total Variation.

For any pair of distributions $\mu$ and $\nu$, let $\|\mu-\nu\|_{\mathrm{TV}}$
denote the total variation of $\mu$ and $\nu$. In Lemma 4, we show that for
any $p\geq 1$, the $(p,0)$-RPW distance between $\mu$ and $\nu$ is equal to
their total variation. Intuitively, the $(p,0)$-RPW distance measures the
maximum amount of mass that can be transported from $\mu$ to $\nu$ at a $0$
cost, i.e., $(p,0)$-RPW distance is the amount of mass of $\mu$ and $\nu$ that
overlap, which is the same as their total variation.

lemmarelationTV For any two probability distributions $\mu$ and $\nu$ in a
metric space $({\mathcal{X}},c)$ with a unit diameter and any parameter $p\geq
1$, $\Pi_{p,0}(\mu,\nu)=\|\mu-\nu\|_{\mathrm{TV}}$.

#####  $p$-Wasserstein distance.

Finally, we show that for large enough values of $k$, the $(p,k)$-RPW metric
would be close to $\frac{1}{k}W_{p}(\mu,\nu)$.

lemmarelationWasserstein For any two probability distributions $\mu$ and $\nu$
over a metric space $({\mathcal{X}},c)$ with a unit diameter and any
parameters $p\geq 1$ and $k>0$,
$\Pi_{p,k}(\mu,\nu)\leq\frac{1}{k}W_{p}(\mu,\nu)\leq\Pi_{p,k}(\mu,\nu)+k^{-\frac{p+1}{p}}$.

##  5 Algorithms to Compute $(p,k)$-RPW

In this section, we describe two approximation algorithms for computing the
$(p,k)$-RPW distance between two discrete distributions defined over supports
of $n$ points. The first algorithm uses a binary search on the value of
$\Pi_{p,k}(\mu,\nu)$ and computes a $\delta$-additive approximation of
$(p,k)$-RPW (or simply _$\delta$ -close $(p,k)$-RPW_) for any $\delta>0$ in
$O(n^{3}\log n\log\delta^{-1})$ time. Our second algorithm relies on the
algorithm by (Lahn et al., 2019) (LMR algorithm) to approximate the OT-profile
and computes a $\delta$-additive approximation of our metric in
$O(\frac{n^{2}}{\delta^{p}}+\frac{n}{\delta^{2p}})$ time. A high-level
overview of each algorithm is presented below. See Appendix A.4 for full
details.

Note that when $k=0$, as discussed in Lemma 4, the $(p,0)$-RPW is simply the
total variation distance and can be computed on discrete distributions in
linear time. Hence, in the following, we assume $k>0$.

Highly-Accurate Algorithm. For any $\varepsilon\in[0,1]$, computing the
$(1-\varepsilon)$-partial $p$-Wasserstein distance for discrete distributions
can be done using a standard OT solver in an augmented space (Chapel et al.,
2020), which takes $O(n^{3}\log n)$ time (Edmonds & Karp, 1972; Orlin, 1988).
Our first algorithm is based on this observation and uses a simple binary
search on the value of $(p,k)$-RPW to obtain a $\delta$-additive approximation
in $O(n^{3}\log n\log\delta^{-1})$ time.

Computing Through an Approximate OT-Profile. We can also approximate the
$(p,k)$-RPW distance by using the LMR algorithm (Lahn et al., 2019) to
approximate the OT-profile. Given two discrete probability distributions, an
error parameter $\delta^{\prime}>0$, and any cost function, the LMR algorithm
incrementally constructs a $(\delta^{\prime})^{1/p}$-additive approximation of
the OT-profile, i.e., for any $\alpha\in[0,1]$, the LMR algorithm computes a
$(\delta^{\prime})^{1/p}$-additive approximation of the $\alpha$-partial
$p$-Wasserstein distance (Phatak et al., 2022).

In Lemma A.4 in the appendix, we show that computing our metric using a
$\delta^{\prime}$-additive approximation of the OT-profile leads to a
$\frac{2\delta^{\prime}}{k}$-close $(p,k)$-RPW. Therefore, to compute a
$\delta$-close $(p,k)$-RPW distance function, we use the LMR algorithm with an
error parameter $\delta^{\prime}=(\frac{k\delta}{2})^{p}$ to approximate the
OT-profile and to compute a $\delta$-close $\Pi_{p,k}(\mu,\nu)$ in
$O(\frac{n^{2}}{\delta^{p}}+\frac{n}{\delta^{2p}})$ time.

##  6 Experimental Results

In this section, we present the results of our experiments showing that our
distance is robust to noise from outliers and sample discrepancies.

In our first experiment, we use the $1$-Wasserstein distance, $2$-Wasserstein
distance, TV distance, $(2,1)$-RPW, and $(2,0.1)$-RPW to rank images from the
MNIST (LeCun, 1998), CIFAR-10 (Hinton et al., 2012), and COREL datasets and
measure the accuracy of the results. In our second experiment, we measure the
convergence rate of empirical $(2,k)$-RPW distance to the true $(2,k)$-RPW and
compare it with the convergence rate for $2$-Wasserstein distance for
synthetic data sets. For both experiments, we compute an additive
approximation of the RPW metric using the LMR algorithm (Lahn et al., 2019).

###  6.1 Image Retrieval.

Following the experimental setup introduced by Rubner et al. (2000), we
conduct experiments on retrieving images using $(2,1)$-RPW and $(2,0.1)$-RPW
distances and compare their accuracy against the $1$-Wasserstein,
$2$-Wasserstein, and TV distances. In this experiment, given a dataset of
labeled images and a set of unlabeled query images, the goal is to retrieve,
for each query image, a set of $m$ similar images from the labeled dataset.
The accuracy of a distance function in the image retrieval task is then
computed as the ratio of the retrieved images with the correct label, averaged
over all retrievals for all query images. In our experiments, we vary the
value of $m$ from $1$ to $100$.

Datasets. We conduct the experiments using three datasets, namely, MNIST,
CIFAR-10, and COREL. In our experiments on each dataset, we randomly select
$2k$ images as the labeled dataset and randomly select $50$ images as the
query. For each dataset, we introduce three scenarios of perturbation:

  * (i)

(noise in datasets) In this scenario, we add random noise to the images in the
datasets. For the MNIST dataset, for each image, we add a random amount of
noise between $0\%$ and $10\%$ to a random pixel in the image. For CIFAR-10
and COREL datasets, we replaced randomly selected $10\%$ of pixels with white
pixels in each image.

  * (ii)

(shift in datasets) In this scenario, we shift up each labeled image by $2$
pixels for the MNIST dataset and increase the intensity of a random RGB
channel by $20$ in each image of the CIFAR-10 and COREL datasets.

  * (iii)

(noise and shift in datasets) In the last scenario, we introduce both random
noise (scenario (i)) and random shift (scenario (ii)) to the images in
datasets.

Results. Figure 5 shows the results of our experiments on MNIST and CIFAR-10
datasets. The results of our experiments on the COREL dataset are provided in
Appendix B. In Figure 5, the left (resp. right) column corresponds to our
experiments on the MNIST (resp. CIFAR-10) dataset in the three scenarios
described above. In each plot, the horizontal axis is the number $m$ of
retrieved images for each query, and the vertical axis is the accuracy of the
retrieved images. The results of our experiments suggest that our metric
performs better than the $1$-Wasserstein, $2$-Wasserstein, and the TV
distances for the task of image retrieval with perturbations.

|
---|---
(i) Noise in datasets
|
(ii) Shift in datasets
|
(iii) Noise and shift in datasets
Figure 5: The results of our experiments on image retrieval on (left column)
MNIST dataset and (right column) CIFAR-10 dataset.

First, for experiments on the MNIST dataset, we observe that for datasets (ii)
and (iii), the accuracy achieved by the $2$-Wasserstein distance is better
than that of the $1$-Wasserstein distance. This, we believe is due to the
higher sensitivity of $2$-Wasserstein distance, which enables it to detect
minor differences effectively. However, for dataset (i), the presence of noise
distorts $2$-Wasserstein distance, causing it to underperform.

Results for MNIST dataset (i): The TV, $1$-Wasserstein, and $(2,1)$-RPW
distances are more robust to noise and therefore, perform better than the
$2$-Wasserstein distance. The $(2,1)$-RPW distance outperforms $1$-Wasserstein
distance. This is because it retains the higher sensitivity of $2$-Wasserstein
distance, which enables it to effectively detect minor differences.

Results for MNIST dataset (ii): TV distance is known to be sensitive to
shifts. As a result, the accuracy of TV distance drops significantly. In
contrast, the $2$-Wasserstein distance and the $(2,1)$-RPW distance handle
such shifts more effectively.

Results for MNIST dataset (iii): The $2$-Wasserstein distance is sensitive to
noise and the TV distance is sensitive to shifts. Therefore, both these
distances produce lower accuracy results. Recollect that the $(2,1)$-RPW
distance combines the TV distance and the $2$-Wasserstein distance and
therefore, can handle both shifts and noise effectively. Therefore, it
outperforms all distances in this setting.

Results for CIFAR-10 dataset:  In the CIFAR-10 dataset, images that have the
same labels may already have significant variations and shifts. Due to these
variations, $2$-Wasserstein and TV distances achieve lower accuracy in
comparison to the $1$-Wasserstein distance. The $(2,0.1)$-RPW distance,
however, outperforms the $1$-Wasserstein distance for this dataset.

###  6.2 Rate of Convergence

We conduct numerical experiments to compare the convergence rate of the
empirical $(2,k)$-RPW metric with that of the $2$-Wasserstein distance and TV
distance on discrete distributions. We compute the convergence rate of each
metric by drawing two sets of $n$ i.i.d samples from a discrete distribution
and compute the empirical distance between the corresponding empirical
distributions.

Datasets. We employ two synthetic $2$-dimensional discrete distributions,
namely (i) (2-point distribution) a discrete distribution defined over $2$
points $a$ and $b$ each with a probability $1/2$, where $\|a-b\|=1$, and (ii)
(grid distribution) a discrete distribution defined over $16$ points that are
placed in a grid of $4\times 4$, where each point has a probability of
$\frac{1}{16}$.

In our experiments, we vary the sample size $n$ from $10$ to $10^{6}$. For
each value of $n$, we conduct the experiment $10$ times and take the mean
distance among all $10$ executions.

Results. As shown in Figure 6, experiments suggest that for both
distributions, the empirical $(2,1)$-RPW distance converges to $0$
significantly faster than the $2$-Wasserstein distance. We also observe that
for a small value of $k$ (e.g., $k=0.1$), $(2,k)$-RPW is close to the TV
distance, whereas for a large value of $k$ (e.g., $k=10$), the $(2,k)$-RPW
distance values are similar to $\frac{1}{k}W_{2}(\cdot,\cdot)$. These results
are in line with our theoretical bounds in Section 4.

Figure 6: The convergence rate of different metrics on (left) 2-point
distribution and (right) grid distribution.

##  7 Conclusion

In this paper, we designed a new partial $p$-Wasserstein-based metric called
the $(p,k)$-RPW that is robust to outlier noise as well as sampling
discrepancies but retains the sensitivity of $p$-Wasserstein distance in
capturing the minor geometric differences in distributions. We showed that our
distance interpolates between the $p$-Wasserstein and TV distances and
inherits robustness to both noise and shifts in distribution. We also showed
that, for $p=\infty$, our metric is the same as the Lévy-Prokhorov distance.

The main contribution of this paper is to introduce a new metric and derive
its useful properties. Experiments suggest that the new distance is a
promising alternative to TV and $p$-Wasserstein distances. Including this
distance into many potential machine learning use cases, including as a loss
function in GANs or for computing barycenters of a set of distributions,
remains an open question. Designing a parallel algorithm to approximate the
$(p,k)$-RPW distance also remains an important open question.

## Acknowledgement

We would like to acknowledge Advanced Research Computing (ARC) at Virginia
Tech, which provided us with the computational resources used to run the
experiments. The research presented in this paper was funded by NSF
CCF-2223871. We thank the anonymous reviewers for their useful feedback.

## Impact Statement

This paper presents work whose goal is to advance the field of Machine
Learning. There are many potential societal consequences of our work, none
which we feel must be specifically highlighted here.

## References

  * Alvarez-Melis & Jaakkola (2018) Alvarez-Melis, D. and Jaakkola, T. S.  Gromov-Wasserstein alignment of word embedding spaces.  _arXiv preprint arXiv:1809.00013_ , 2018.
  * Arjovsky et al. (2017) Arjovsky, M., Chintala, S., and Bottou, L.  Wasserstein generative adversarial networks.  In _Proc. 34th International Conference on Machine Learning_ , pp. 214–223, 2017.
  * Backurs et al. (2020) Backurs, A., Dong, Y., Indyk, P., Razenshteyn, I., and Wagner, T.  Scalable nearest neighbor search for optimal transport.  In _Proc. 37th International Conference on Machine Learning_ , pp. 497–506, 2020.
  * Bansil & Kitagawa (2021) Bansil, M. and Kitagawa, J.  $W_{\infty}$-transport with discrete target as a combinatorial matching problem.  _Archiv der Mathematik_ , 117(2):189–202, 2021.
  * Caffarelli & McCann (2010) Caffarelli, L. A. and McCann, R. J.  Free boundaries in optimal transport and Monge-Ampere obstacle problems.  _Annals of Mathematics_ , pp. 673–730, 2010.
  * Chang et al. (2023) Chang, W., Shi, Y., and Wang, J.  Csot: Curriculum and structure-aware optimal transport for learning with noisy labels.  _ArXiv preprint arXiv:2312.06221_ , 2023.
  * Chapel et al. (2020) Chapel, L., Alaya, M. Z., and Gasso, G.  Partial optimal tranport with applications on positive-unlabeled learning.  _Advances in Neural Information Processing Systems_ , 33:2903–2913, 2020.
  * Choi et al. (2024) Choi, J., Choi, J., and Kang, M.  Generative modeling through the semi-dual formulation of unbalanced optimal transport.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Chuang et al. (2022) Chuang, C.-Y., Hjelm, R. D., Wang, X., Vineet, V., Joshi, N., Torralba, A., Jegelka, S., and Song, Y.  Robust contrastive learning against noisy views.  In _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 16670–16681, 2022.
  * Claici et al. (2018) Claici, S., Chien, E., and Solomon, J.  Stochastic Wasserstein barycenters.  In _International Conference on Machine Learning_ , pp. 999–1008. PMLR, 2018.
  * Cuturi & Doucet (2014) Cuturi, M. and Doucet, A.  Fast computation of Wasserstein barycenters.  In _International Conference on machine learning_ , pp. 685–693. PMLR, 2014.
  * Edmonds & Karp (1972) Edmonds, J. and Karp, R. M.  Theoretical improvements in algorithmic efficiency for network flow problems.  _J. of the ACM_ , 19(2):248–264, 1972.
  * El Malki et al. (2020) El Malki, N., Cugny, R., Teste, O., and Ravat, F.  Decwa: Density-based clustering using Wasserstein distance.  In _Proc. 29th ACM International Conference on Information & Knowledge Management_, pp. 2005–2008, 2020.
  * Figalli (2010) Figalli, A.  The optimal partial transport problem.  _Archive for Rational Mechanics and Analysis_ , 195(2):533–560, 2010.
  * Fournier & Guillin (2015) Fournier, N. and Guillin, A.  On the rate of convergence in Wasserstein distance of the empirical measure.  _Probability theory and related fields_ , 162(3-4):707–738, 2015.
  * Genevay et al. (2018) Genevay, A., Peyre, G., and Cuturi, M.  Learning generative models with Sinkhorn divergences.  _In International Conference on Artificial Intelligence and Statistics_ , pp. 1608–1617, 2018.
  * Gupta et al. (2010) Gupta, R., Indyk, P., and Price, E.  Sparse recovery for earth mover distance.  In _Proc. 48th Annual Allerton Conference on Communication, Control, and Comput._ , pp. 1742–1744. IEEE, 2010.
  * Hinton et al. (2012) Hinton, G. E., Srivastava, N., Krizhevsky, A., Sutskever, I., and Salakhutdinov, R. R.  Improving neural networks by preventing co-adaptation of feature detectors.  _arXiv preprint arXiv:1207.0580_ , 2012.
  * Huang et al. (2016) Huang, G., Guo, C., Kusner, M. J., Sun, Y., Sha, F., and Weinberger, K. Q.  Supervised word mover’s distance.  _Advances in neural information processing systems_ , 29, 2016.
  * Janati et al. (2019) Janati, H., Cuturi, M., and Gramfort, A.  Wasserstein regularization for sparse multi-task regression.  In _Proc. 22nd International Conference on Artificial Intelligence and Statistics_ , pp. 1407–1416. PMLR, 2019.
  * Lahn et al. (2019) Lahn, N., Mulchandani, D., and Raghvendra, S.  A graph theoretic additive approximation of optimal transport.  In _Advances in Neural Information Processing Systems_ , pp. 13813–13823, 2019.
  * Lahn et al. (2021) Lahn, N., Raghvendra, S., and Ye, J.  A faster maximum cardinality matching algorithm with applications in machine learning.  _Advances in Neural Information Processing Systems_ , 34:16885–16898, 2021.
  * Lai et al. (2022) Lai, Z., Wang, C., Cheung, S.-c., and Chuah, C.-N.  Sar: Self-adaptive refinement on pseudo labels for multiclass-imbalanced semi-supervised learning.  In _Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 4091–4100, 2022.
  * Le et al. (2021) Le, K., Nguyen, H., Nguyen, Q. M., Pham, T., Bui, H., and Ho, N.  On robust optimal transport: Computational complexity and barycenter computation.  _Advances in Neural Information Processing Systems_ , 34:21947–21959, 2021.
  * LeCun (1998) LeCun, Y.  The mnist database of handwritten digits.  _http://yann.lecun.com/exdb/mnist/_ , 1998.
  * Luise et al. (2018) Luise, G., Rudi, A., Pontil, M., and Ciliberto, C.  Differential properties of Sinkhorn approximation for learning with Wasserstein distance.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Mohajerin Esfahani & Kuhn (2018) Mohajerin Esfahani, P. and Kuhn, D.  Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations.  _Mathematical Programming_ , 171(1):115–166, 2018.
  * Mukherjee et al. (2021) Mukherjee, D., Guha, A., Solomon, J. M., Sun, Y., and Yurochkin, M.  Outlier-robust optimal transport.  In _International Conference on Machine Learning_ , pp. 7850–7860. PMLR, 2021.
  * Nietert et al. (2022) Nietert, S., Goldfeld, Z., and Cummings, R.  Outlier-robust optimal transport: Duality, structure, and statistical analysis.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 11691–11719. PMLR, 2022.
  * Nietert et al. (2023) Nietert, S., Goldfeld, Z., and Shafiee, S.  Outlier-robust Wasserstein DRO.  _ArXiv preprint arXiv:2311.05573_ , 2023.
  * Oquab et al. (2023) Oquab, M., Darcet, T., Moutakanni, T., Vo, H., Szafraniec, M., Khalidov, V., Fernandez, P., Haziza, D., Massa, F., El-Nouby, A., et al.  Dinov2: Learning robust visual features without supervision.  _arXiv preprint arXiv:2304.07193_ , 2023.
  * Orlin (1988) Orlin, J.  A faster strongly polynomial minimum cost flow algorithm.  In _Proc. 20th Annual ACM Symposium on Theory of Computing_ , pp. 377–387, 1988.
  * Phatak et al. (2022) Phatak, A., Raghvendra, S., Tripathy, C., and Zhang, K.  Computing all optimal partial transports.  In _Proc. 11th International Conference on Learning Representations_ , 2022.
  * Rubner et al. (2000) Rubner, Y., Tomasi, C., and Guibas, L. J.  The earth mover’s distance as a metric for image retrieval.  _International J. of Comput. Vision_ , 40(2):99, 2000.
  * Salimans et al. (2018) Salimans, T., Zhang, H., Radford, A., and Metaxas, D.  Improving GANs using optimal transport.  _In International Conference on Learning Representations_ , 2018.
  * Sedrakyan & Sedrakyan (2018) Sedrakyan, H. and Sedrakyan, N.  _The HM-GM-AM-QM Inequalities_ , pp. 21–43.  Springer International Publishing, 2018.
  * Vaskevicius & Chizat (2023) Vaskevicius, T. and Chizat, L.  Computational guarantees for doubly entropic Wasserstein barycenters.  In _Proc. 37th Conference on Neural Information Processing Systems_ , 2023.
  * Vincent-Cuaz et al. (2021) Vincent-Cuaz, C., Flamary, R., Corneli, M., Vayer, T., and Courty, N.  Semi-relaxed Gromov-Wasserstein divergence with applications on graphs.  _arXiv preprint arXiv:2110.02753_ , 2021.
  * Yurochkin et al. (2019) Yurochkin, M., Claici, S., Chien, E., Mirzazadeh, F., and Solomon, J. M.  Hierarchical optimal transport for document representation.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Zhuang et al. (2022) Zhuang, Y., Chen, X., and Yang, Y.  Wasserstein $k$-means for clustering probability distributions.  _Advances in Neural Information Processing Systems_ , 35:11382–11395, 2022.

##  Appendix A Missing Proofs and Details

###  A.1 Missing Proofs of Section 2.

In this section, we provide the proofs for Theorem 3 and Lemma 3.

*

###### Proof.

To prove this lemma, we show that $(p,k)$-RPW satisfies all four properties of
the metric spaces, namely (i) identity, (ii) positivity, (iii) symmetry, and
(iv) triangle inequality, and conclude that it is metric.

For any probability distribution $\mu$ defined over $({\mathcal{X}},c)$,
$W_{p}(\mu,\mu)=0$ and therefore, $\varepsilon=0$ satisfies the condition in
Equation (1); hence, $\Pi_{p,k}(\mu,\mu)=0$ and property (i) holds.
Furthermore, if $\nu$ is another probability distribution over
$({\mathcal{X}},c)$ that is distinct from $\mu$, then $W_{p}(\mu,\nu)>0$.
Hence, $\varepsilon=0$ does not satisfy the condition in Equation (1), and
$\Pi_{p,k}(\mu,\nu)$, which is the smallest $\varepsilon\geq 0$ with
$W_{p,1-\varepsilon}(\mu,\nu)\leq k\varepsilon$, will be positive and property
(ii) holds. Additionally, for any $\varepsilon\geq 0$, the
$(1-\varepsilon)$-partial $p$-Wasserstein distance is symmetric, i.e.,
$W_{p,1-\varepsilon}(\mu,\nu)=W_{p,1-\varepsilon}(\nu,\mu)$. Therefore, from
Equation (1), RPW is also symmetric, i.e.,
$\Pi_{p,k}(\mu,\nu)=\Pi_{p,k}(\nu,\mu)$ and property (iii) holds as well.

Finally, we show that the $(p,k)$-RPW satisfies the triangle inequality. For
any three probability distributions $\mu$, $\nu$, and $\kappa$, suppose
$\Pi_{p,k}(\mu,\kappa)=\varepsilon_{1}$ and
$\Pi_{p,k}(\kappa,\nu)=\varepsilon_{2}$. In the following, we show that
$\Pi_{p,k}(\mu,\nu)\leq\varepsilon_{1}+\varepsilon_{2}$ and conclude property
(iv).

Note that if $\varepsilon_{1}+\varepsilon_{2}\geq 1$, then the triangle
inequality holds trivially since $\Pi_{p,k}(\mu,\nu)\leq
1\leq\varepsilon_{1}+\varepsilon_{2}$. Therefore, we assume that
$\varepsilon_{1}+\varepsilon_{2}<1$. Let $\gamma_{1}$ denote a
$(1-{\varepsilon_{1}})$-partial OT plan from $\mu$ to $\kappa$ and define
$\kappa_{1}:=\gamma_{1}\\#\mu$ to be the mass of $\kappa$ that is transported
from $\mu$ by $\gamma_{1}$; here, $\\#$ denotes the push-forward operation.
Similarly, let $\gamma_{2}$ denote a $(1-{\varepsilon_{2}})$-partial OT plan
from $\kappa$ to $\nu$ and define $\kappa_{2}:=(\gamma_{2})^{-1}\\#\nu$ to be
the mass of $\kappa$ that is transported to $\nu$ by $\gamma_{2}$. Then, both
$\kappa_{1}$ and $\kappa_{2}$ are distributions over ${\mathcal{X}}$ that are
dominated by $\kappa$ and have masses
${\mathcal{M}}(\kappa_{1})=1-\varepsilon_{1}$ and
${\mathcal{M}}(\kappa_{2})=1-\varepsilon_{2}$.

Define $\kappa_{\mathrm{c}}$ to be the distribution of mass of $\kappa$ that
is common to both $\kappa_{1}$ and $\kappa_{2}$; more precisely, for each
$x\in{\mathcal{X}}$,

$\kappa_{\mathrm{c}}(x)=\min\\{\kappa_{1}(x),\kappa_{2}(x)\\}.$

Note that the total mass of $\kappa_{1}$ that is not transported by
$\gamma_{2}$ is at most $\varepsilon_{2}$; therefore,

${\mathcal{M}}(\kappa_{c})\geq{\mathcal{M}}(\kappa_{1})-\varepsilon_{2}=1-\varepsilon_{1}-\varepsilon_{2}.$
(7)

Define $\mu_{\mathrm{c}}:=(\gamma_{1})^{-1}\\#\kappa_{\mathrm{c}}$ (resp.
$\nu_{\mathrm{c}}:=\gamma_{2}\\#\kappa_{\mathrm{c}}$) to be distribution
dominated by $\mu$ (resp. $\nu$) whose mass is transported to (resp. from)
$\kappa_{c}$ in $\gamma_{1}$ (resp. $\gamma_{2}$). From Equation (7),

${\mathcal{M}}(\mu_{\mathrm{c}})={\mathcal{M}}(\nu_{\mathrm{c}})={\mathcal{M}}(k_{\mathrm{c}})\geq
1-\varepsilon_{1}-\varepsilon_{2}$ (8)

By the triangle inequality of the $p$-Wasserstein distance,

$W_{p}(\mu_{\mathrm{c}},\nu_{\mathrm{c}})\leq
W_{p}(\mu_{\mathrm{c}},\kappa_{\mathrm{c}})+W_{p}(\kappa_{\mathrm{c}},\nu_{\mathrm{c}}).$
(9)

Furthermore,

$\displaystyle W_{p}(\mu_{\mathrm{c}},\kappa_{\mathrm{c}})\leq
w_{p}(\gamma_{1})\leq k\varepsilon_{1}.$ (10)

Similarly,

$\displaystyle W_{p}(\kappa_{\mathrm{c}},\nu_{\mathrm{c}})\leq
w_{p}(\gamma_{2})\leq k\varepsilon_{2}.$ (11)

Combining Equations (8), (9), (10), and (11),

$\displaystyle W_{p,1-\varepsilon_{1}-\varepsilon_{2}}(\mu,\nu)$
$\displaystyle\leq W_{p}(\mu_{\mathrm{c}},\nu_{\mathrm{c}})\leq
W_{p}(\mu_{\mathrm{c}},\kappa_{\mathrm{c}})+W_{p}(\kappa_{\mathrm{c}},\nu_{\mathrm{c}})\leq
k(\varepsilon_{1}+\varepsilon_{2}).$ (12)

Since $\Pi_{p,k}(\mu,\nu)$ is the minimum $\varepsilon$ with
$W_{p,1-\varepsilon}(\mu,\nu)\leq k\varepsilon$, from Equation (12),
$\Pi_{p,k}(\mu,\nu)\leq\varepsilon_{1}+\varepsilon_{2}$, as desired. ∎

*

###### Proof.

Let $\delta:=\Pi_{p,k}(\mu,\nu)$. We prove this lemma by considering two
cases:

  * •

If $\alpha\leq\beta$, then $W_{p,1-\beta}(\mu,\nu)\leq
W_{p,1-\alpha}(\mu,\nu)=k\beta$; hence, $\beta$ satisfies the condition in
Equation (1), and $\Pi_{p,k}(\mu,\nu)\leq\beta=\max\\{\alpha,\beta\\}$.
Furthermore, if $k>0$, then $\delta\geq\alpha=\min\\{\alpha,\beta\\}$ because
otherwise, if $\delta<\alpha$, then

$W_{p,1-\delta}(\mu,\nu)\geq W_{p,1-\alpha}(\mu,\nu)=k\beta\geq
k\alpha>k\delta,$

which is a contradiction.

  * •

Otherwise, $\alpha>\beta$ and $W_{p,1-\alpha}(\mu,\nu)=k\beta<k\alpha$; hence,
$\alpha$ satisfies the condition in Equation (1), and
$\Pi_{p,k}(\mu,\nu)\leq\alpha=\max\\{\alpha,\beta\\}.$ Additionally, if $k>0$,
then $\delta\geq\beta=\min\\{\alpha,\beta\\}$, since otherwise, if
$\delta<\beta$, then

$\displaystyle W_{p,1-\delta}(\mu,\nu)$ $\displaystyle\geq
W_{p,1-\beta}(\mu,\nu)\geq W_{p,1-\alpha}(\mu,\nu)=k\beta>k\delta,$

which is a contradiction.

∎

###  A.2 Missing Proofs and Details of Section 3

####  A.2.1 Robustness to Outlier Nosie

*

###### Proof.

First, note that by the triangle inequality,
$\Pi_{p,k}(\mu,\tilde{\nu})+\Pi_{p,k}(\tilde{\nu},\nu)\geq\Pi_{p,k}(\mu,\nu)$.
Furthermore, by the definition of $\tilde{\nu}$,
$W_{p,1-\delta}(\nu,\tilde{\nu})=0$. Therefore, by Lemma 3,
$\Pi_{p,k}(\nu,\tilde{\nu})\leq\max\\{\delta,0\\}=\delta$ and

$\Pi_{p,k}(\mu,\tilde{\nu})\geq\Pi_{p,k}(\mu,\nu)-\Pi_{p,k}(\nu,\tilde{\nu})\geq\Pi_{p,k}(\mu,\nu)-\delta.$

Define $\alpha:=\Pi_{p,k}(\mu,\nu)$ and let $\gamma$ be a $(1-\alpha)$-partial
OT plan from $\mu$ to $\nu$. Since $\tilde{\nu}$ is defined as
$(1-\delta)\nu+\delta\nu^{\prime}$, the transport plan
$\gamma^{\prime}:=(1-\delta)\gamma$ can be seen as a
$((1-\delta)(1-\alpha))$-partial transport plan from $\mu$ to $\tilde{\nu}$;
therefore,

$W_{p,(1-\delta)(1-\alpha)}(\mu,\tilde{\nu})\leq
w_{p}(\gamma^{\prime})=(1-\delta)^{\frac{1}{p}}w_{p}(\gamma)\leq
k(1-\delta)^{\frac{1}{p}}\alpha,$

where the last inequality holds by the definition of the $(p,k)$-RPW distance.
Using Lemma 3,

$\displaystyle\Pi_{p,k}(\mu,\tilde{\nu})$
$\displaystyle\leq\max\left\\{1-(1-\delta)(1-\alpha),(1-\delta)^{\frac{1}{p}}\alpha\right\\}=(1-\delta)\alpha+\delta=(1-\delta)\Pi_{p,k}(\mu,\nu)+\delta.$

∎

The following lemma helps in proving Lemma 3.1.

lemmarobustness For two probability distributions $\mu$ and $\tilde{\mu}$
defined over a metric space $({\mathcal{X}},c)$ with a unit diameter,
parameters $p\geq 1,k>0$, and a constant $\alpha\in(0,1)$, let
$\delta:=\|\mu-\tilde{\mu}\|_{TV}$. Then,

$\min\bigg{\\{}\delta(1-\alpha),\frac{1}{k}W_{p,1-\delta(1-\alpha)}(\mu,\tilde{\mu})\bigg{\\}}\leq\Pi_{p,k}(\mu,\tilde{\mu})\leq\min\left\\{\delta,\frac{1}{k}W_{p}(\mu,\tilde{\mu})\right\\}.$

###### Proof.

Using Lemma 3 on distributions $\mu$ and $\tilde{\mu}$,

$\Pi_{p,k}(\mu,\tilde{\mu})\geq\min\bigg{\\{}\delta(1-\alpha),\frac{1}{k}W_{p,1-\delta(1-\alpha)}(\mu,\tilde{\mu})\bigg{\\}}.$

Next, since $\delta=\|\mu-\tilde{\mu}\|_{TV}$, we get
$W_{p,1-\delta}(\mu,\tilde{\mu})=0$. Plugging into Lemma 3,

$\Pi_{p,k}(\mu,\tilde{\mu})\leq\max\\{\delta,0\\}=\delta.$ (13)

Furthermore, since $W_{p,1-0}(\mu,\tilde{\mu})=W_{p}(\mu,\tilde{\mu})$, by
Lemma 3,

$\Pi_{p,k}(\mu,\tilde{\mu})\leq\max\\{0,\frac{1}{k}W_{p}(\mu,\tilde{\mu})\\}=\frac{1}{k}W_{p}(\mu,\tilde{\mu}).$
(14)

Combining Equations (13) and (14),

$\Pi_{p,k}(\mu,\tilde{\mu})\leq\min\left\\{\delta,\frac{1}{k}W_{p}(\mu,\tilde{\mu})\right\\},$

as claimed. ∎

Assuming that the assumption (A1) holds for the distributions $\mu$ and
$\tilde{\mu}$, by plugging $\alpha=0.9$ in Lemma A.2.1, we can derive the
following lemma.

*

####  A.2.2 Robustness to Sampling Discrepancies

lemmaconvergenceexcessd For any distribution $\mu$ inside the unit
$d$-dimensional hypercube, an empirical distribution $\mu_{n}$ of $\mu$, and a
grid ${\mathcal{G}}$ with cell side length $n^{-\alpha}$,
$\mathrm{Exc}_{\mu}({\mathcal{G}})=\tilde{O}(n^{\frac{d\alpha}{2}-\frac{1}{2}})$
with a high probability.

###### Proof.

First, note that if $\alpha\geq\frac{1}{d}$, then
$n^{\frac{d\alpha}{2}-\frac{1}{2}}\geq 1$, and the lemma statement holds
trivially. Therefore, from now on, we assume $\alpha$ to be less than
$\frac{1}{d}$. For any cell $\Box$ of the grid ${\mathcal{G}}$, define
$p_{\Box}:=\mu(\Box)$ to be the total probability mass of $\mu$ inside $\Box$,
i.e., the probability that a point drawn from $\mu$ lies inside $\Box$. Any
cell $\Box\in{\mathcal{G}}$ is considered a sparse cell if
$p_{\Box}\leq\frac{9\log n}{n}$, and a dense cell otherwise. Let
${\mathcal{G}}_{\mathcal{S}}$ (resp. ${\mathcal{G}}_{\mathcal{D}}$) denote the
subset of sparse (resp. dense) cells of ${\mathcal{G}}$. For each sparse cell
$\Box$, $\mathrm{Exc}_{\mu}(\Box)\leq p_{\Box}\leq\frac{9\log n}{n}$;
therefore, using $\alpha<\frac{1}{d}$, the total contribution of sparse cells
to the excess of ${\mathcal{G}}$ is at most

$O(|{\mathcal{G}}_{\mathcal{S}}|\times\frac{\log
n}{n})=O(n^{d\alpha}\times\frac{\log
n}{n})=\tilde{O}(n^{d\alpha-1})=\tilde{O}(n^{\frac{d\alpha}{2}-\frac{1}{2}}).$

Next, we analyze the excess of the dense cells. Let $X=(x_{1},\ldots,x_{n})$
denote the set of $n$ samples drawn from $\mu$ that were used to construct the
empirical distribution $\mu_{n}$. For each dense cell $\Box$, let $Y_{\Box}$
be a random variable denoting the number of samples in $X$ that lie inside
$\Box$. Using the Chernoff bound,

$Pr\big{[}Y_{\Box}\leq np_{\Box}-3\sqrt{np_{\Box}\log n}\big{]}\leq
n^{-\frac{9}{2}}.$

In other words, for each $\Box\in{\mathcal{G}}_{\mathcal{D}}$,
$\mathrm{Exc}_{\mu}(\Box)=O(\frac{1}{n}\sqrt{np_{\Box}\log n})$ with
probability at least $1-n^{-\frac{9}{2}}$. Therefore, with probability at
least $(1-n^{-9/2})^{|{\mathcal{G}}_{\mathcal{D}}|}\geq(1-n^{-9/2})^{n}\geq
1-n^{-\frac{7}{2}}$, the total excess of the dense cells would be

$\displaystyle\sum_{\Box\in{\mathcal{G}}_{\mathcal{D}}}\mathrm{Exc}_{\mu}(\Box)$
$\displaystyle=O\left(\sum_{\Box\in{\mathcal{G}}_{\mathcal{D}}}\sqrt{\frac{p_{\Box}\log
n}{n}}\right)=O\left(\sqrt{\frac{\log
n}{n}}\sum_{\Box\in{\mathcal{G}}_{\mathcal{D}}}\sqrt{p_{\Box}}\right)$
$\displaystyle=O\left(\sqrt{\frac{\log
n}{n}}\times\sqrt{|{\mathcal{G}}_{\mathcal{D}}|}\right)=\tilde{O}(n^{\frac{d\alpha}{2}-\frac{1}{2}}),$

where the third equality holds since
$\frac{\sum_{\Box\in{\mathcal{G}}}\sqrt{p_{\Box}}}{|{\mathcal{G}}_{\mathcal{D}}|}\leq\sqrt{\frac{\sum_{\Box\in{\mathcal{G}}_{\mathcal{D}}}p_{\Box}}{|{\mathcal{G}}_{\mathcal{D}}|}}$
(Sedrakyan & Sedrakyan, 2018) and
$\sum_{\Box\in{\mathcal{G}}_{\mathcal{D}}}p_{\Box}\leq 1$, and the last
equality holds since $|{\mathcal{G}}_{\mathcal{D}}|\leq n^{d\alpha}$. ∎

We obtain the following lemma by simply plugging $d=2$ in Lemma A.2.2.

*

Improved proof of Lemma 3.2. We improve our bounds for the convergence rate of
the empirical $(2,1)$-RPW by extending our approach and considering
$O(\log\log n)$ grids instead of two grids. In the following, we construct a
transport plan $\gamma$ that transports all except
$\tilde{O}(n^{-\frac{1}{3}})$ mass with a cost of
$\tilde{O}(n^{-\frac{1}{3}})$. We then conclude that
$\Pi_{p,k}(\mu,\nu)=\tilde{O}(n^{-\frac{1}{3}})$.

Without loss of generality, assume $n=2^{2^{h}}$ for some integer $h>0$. Let
$\beta:=\frac{\log n}{3\log n-2}$. Define a set of $h$ grids
$\langle{\mathcal{G}}_{1},\ldots,{\mathcal{G}}_{h}\rangle$, where each grid
${\mathcal{G}}_{i}$ has a side length $O(n^{-\alpha_{i}})$ for
$\alpha_{i}:=\frac{1}{2}-\beta\left(1-\frac{1}{2^{i}}\right)$. We construct
the grids in a way that their boundaries are aligned with each other.

Let $\mu^{0}:=\mu$ and $\mu_{n}^{0}:=\mu_{n}$. Starting from $i=1$, we compute
a partial transport plan $\gamma_{i}$ from $\mu_{n}^{i-1}$ to $\mu^{i-1}$ that
transports as much mass as possible inside each cell of ${\mathcal{G}}_{i}$.
We then define $\mu^{i}$ (resp. $\mu_{n}^{i}$) as the distribution of the mass
of $\mu^{i-1}$ (resp. $\mu_{n}^{i-1}$) that is not transported by
$\gamma_{i}$, set $i\leftarrow i+1$, and continue the same process until we
process the last grid ${\mathcal{G}}_{h}$. Define
$\gamma:=\sum_{i=1}^{h}\gamma_{i}$. By our construction, the transport plan
$\gamma$ transports as much mass as possible inside each cell of
${\mathcal{G}}_{h}$. Therefore, the total mass that is not transported by
$\gamma$ is equal to the excess $\mathrm{Exc}({\mathcal{G}}_{h})$, which by
Lemma 3.2, with a high probability, is

$\displaystyle\tilde{O}(n^{\alpha_{h}-\frac{1}{2}})$
$\displaystyle=\tilde{O}(n^{-\beta(1-\frac{1}{2^{h}})})=\tilde{O}(n^{\frac{-\log
n+1}{3\log n-2}})=\tilde{O}(n^{-\frac{1}{3}+\frac{1}{3(3\log
n-2)}})=\tilde{O}(n^{-\frac{1}{3}}).$ (15)

Next, we analyze the cost of $\gamma$ by computing the cost of each transport
plan $\gamma_{i}$ separately. For $\gamma_{1}$, since each mass transportation
is between points inside the same cell of ${\mathcal{G}}_{1}$ and has a
squared cost of $O((n^{-\alpha_{1}})^{2})$,

$\displaystyle w_{2}^{2}(\gamma_{1})$
$\displaystyle=O(n^{-2\alpha_{1}})=O(n^{-1+\beta})=O(n^{-\frac{2\log
n-2}{3\log n-2}})=O(n^{-\frac{2}{3}+\frac{2}{3(3\log
n-2)}})=O(n^{-\frac{2}{3}}).$

Furthermore, for each $i>1$, the transport plan $\gamma_{i}$ transports a
total mass of at most ${\mathcal{M}}(\mu^{i-1})$, which is equal to the excess
of the grid ${\mathcal{G}}_{i-1}$, and by Lemma 3.2 is
$\tilde{O}(n^{\alpha_{i-1}-\frac{1}{2}})$. Since $\gamma_{i}$ transports mass
between points inside the same cell of ${\mathcal{G}}_{i}$, each mass
transportation in $\gamma_{i}$ has a squared cost of $O(n^{-2\alpha_{i}})$,
and therefore,

$\displaystyle w_{2}^{2}(\gamma_{i})$
$\displaystyle=\tilde{O}(n^{\alpha_{i-1}-\frac{1}{2}-2\alpha_{i}})=\tilde{O}(n^{-1+\beta})=\tilde{O}(n^{-\frac{2}{3}}).$

Therefore,

$w_{2}(\gamma)=\sqrt{\sum_{i=1}^{h}w_{2}^{2}(\gamma_{i})}=\tilde{O}(\sqrt{hn^{-\frac{2}{3}}})=\tilde{O}(n^{-\frac{1}{3}}).$
(16)

By Equations (15) and (16), we have computed a transport plan $\gamma$ from
$\mu_{n}$ to $\mu$ that, with a high probability, transports all except
$\tilde{O}(n^{-\frac{1}{3}})$ mass with a cost $\tilde{O}(n^{-\frac{1}{3}})$.
Therefore, $\Pi_{2}(\mu,\mu_{n})=\tilde{O}(n^{-\frac{1}{3}})$ with a high
probability.

We extend the same approach to any dimension $d\geq 2$ and any $p\geq 1$ in
Lemma 4.

*

###### Proof.

In Lemma 4, we show that for any $p\geq 1$ and $k>0$,
$\Pi_{p,k}(\mu,\nu)\leq\frac{1}{k}W_{p}(\mu,\nu)$. Therefore, for any constant
$k>0$, the convergence rate of the empirical $(p,k)$-RPW is upper-bounded by
the convergence rate of the empirical $p$-Wasserstein distance. Fournier &
Guillin (2015) showed that when $p\leq\frac{d}{2}$, the $p$-Wasserstein
distance achieves a convergence rate of $\tilde{O}(n^{-\frac{1}{d}})$.
Therefore, our metric also achieves a convergence rate of
$\tilde{O}(n^{-\frac{1}{d}})$ in this case, proving the bound claimed in the
lemma statement for $p\leq\frac{d}{2}$. In the remaining of this proof, we
prove our bounds for $p>\frac{d}{2}$.

Let $h=\log_{\frac{2p}{d}}\log_{2}n$. We assume that $h$ is an integer. Let
$\beta:=\frac{\log n}{(p+\frac{2p}{d}-1)\log n-p}$. Define a set of $h$ grids
$\langle{\mathcal{G}}_{1},\ldots,{\mathcal{G}}_{h}\rangle$, where each grid
${\mathcal{G}}_{i}$ has a cell side length of $n^{-\alpha_{i}}$ for

$\alpha_{i}:=\frac{1}{d}-\frac{2p}{d^{2}}\beta\left(1-(\frac{d}{2p})^{i}\right).$

Following the approach discussed in Section 3.2, we construct $h$ transport
plans $\gamma_{1},\ldots,\gamma_{h}$ and define a transport plan
$\gamma:=\sum_{i=1}^{h}\gamma_{i}$ to be a transport plan that transports
total mass of $\min\\{\mu(\Box),\mu_{n}(\Box)\\}$ inside each cell
$\Box\in{\mathcal{G}}_{h}$. By Lemma A.2.2, the total free mass with respect
to $\gamma$ would be

$\displaystyle 1-{\mathcal{M}}(\gamma)=\mathrm{Exc}({\mathcal{G}}_{h})$
$\displaystyle=\tilde{O}\left(n^{\frac{d\alpha_{h}}{2}-\frac{1}{2}}\right)=\tilde{O}\left(n^{\frac{1}{2}-\frac{p}{d}\beta+\frac{p}{d}\beta\cdot(\frac{d}{2p})^{h}-\frac{1}{2}}\right)=\tilde{O}\left(n^{-\frac{\log_{2}n-1}{(d+2-\frac{d}{p})\log
n-d}}\right)$
$\displaystyle=\tilde{O}\left(n^{-\frac{1}{d+2-\frac{d}{p}}+\frac{1-\frac{d}{d+2-\frac{d}{p}}}{(d+2-\frac{d}{p})\log
n-d}}\right)=\tilde{O}\left(n^{-\frac{p}{(d+2)p-d}}\right).$ (17)

Next, we bound the cost of $\gamma$ by analyzing the cost of each transport
plan $\gamma_{i},i\in[1,h]$ separately. For $\gamma_{1}$, each mass
transportation is inside a cell of ${\mathcal{G}}_{1}$ and has a $p$th power
cost of $\tilde{O}(n^{-p\alpha_{1}})$; hence,

$w_{p}^{p}(\gamma_{1})=\tilde{O}(n^{-p\alpha_{1}})=\tilde{O}\left(n^{-\frac{p}{d}+\frac{2p^{2}}{d^{2}}\beta\left(1-\frac{d}{2p}\right)}\right)=\tilde{O}\left(n^{-\frac{p^{2}}{(d+2)p-d}}\right).$
(18)

Finally, for each $i>1$, the total mass transported by $\gamma_{i}$ is equal
to the excess of ${\mathcal{G}}_{i-1}$, which by Lemma 3.2 is
$\tilde{O}(n^{\frac{d\alpha_{i-1}}{2}-\frac{1}{2}})$. Each mass transportation
in $\gamma_{i}$ is between points within the same cell of ${\mathcal{G}}_{i}$
and thus has a $p$th power cost of $\tilde{O}(n^{-p\alpha_{i}})$. Therefore,

$\displaystyle w_{p}^{p}(\gamma_{i})$
$\displaystyle=\tilde{O}(n^{\frac{d\alpha_{i-1}}{2}-\frac{1}{2}-p\alpha_{i}})=\tilde{O}\left(n^{-\frac{p^{2}}{(d+2)p-d}}\right).$
(19)

Adding the cost of all transport plans,

$\displaystyle w_{p}(\gamma)$
$\displaystyle=\bigg{(}\sum_{i=1}^{h}w_{p}^{p}(\gamma_{i})\bigg{)}^{1/p}=\tilde{O}\big{(}(n^{-\frac{p^{2}}{(d+2)p-d}}\log\log
n)^{1/p}\big{)}=\tilde{O}(n^{-\frac{p}{(d+2)p-d}}).$ (20)

Combining Equations (17) and (20),
$\Pi_{p}(\mu,\mu_{n})=\tilde{O}(n^{-\frac{p}{(d+2)p-d}})$. ∎

###  A.3 Missing Proofs of Section 4.

To prove Lemma 4, we begin by showing in Lemma A.3 that when $\mu$ and $\nu$
are discrete distributions, $\Pi_{\infty,1}(\mu,\nu)=\pi(\mu,\nu)$. We then
use Lemma A.3 to show that the same also holds for continuous distributions.

lemmarelationLevy For any pair of discrete probability distributions $\mu$ and
$\nu$ in a metric space $({\mathcal{X}},c)$ with a unit diameter,
$\Pi_{\infty,1}(\mu,\nu)=\pi(\mu,\nu)$.

###### Proof.

To prove this lemma, we first show that
$\Pi_{\infty,1}(\mu,\nu)\leq\pi(\mu,\nu)$. We then show that
$\pi(\mu,\nu)\leq\Pi_{\infty,1}(\mu,\nu)$ and conclude the lemma statement.

Let $\delta:=\pi(\mu,\nu)$ and suppose $A$ and $B$ denote the support of
$\mu^{\prime}$ and $\nu^{\prime}$, respectively. Define the $\delta$-disc
graph $G_{\delta}$ between points in $A$ and $B$ to be a bipartite graph where
for each pair $(a,b)\in A\times B$ with $c(a,b)\leq\delta$, there is an edge
between $a$ and $b$ in $G_{\delta}$. For any set $S$ of vertices of
$G_{\delta}$, let ${\mathcal{N}}(S)$ denote the set of neighbors of $S$ in
$G_{\delta}$. By the definition of the Lévy-Prokhorov distance, for any set of
points $S\subseteq A$, $\mu(S)\leq\nu({\mathcal{N}}(S))+\delta$. Similarly,
for any subset $T\subseteq B$, $\nu(T)\leq\mu({\mathcal{N}}(T))+\delta$.

We prove that $\Pi_{\infty,1}(\mu,\nu)\leq\pi(\mu,\nu)$ by showing that the
maximum transport plan $\gamma$ on the $\delta$-disc graph $G_{\delta}$
transports a total mass of at least $1-\delta$. In this case, since all edges
of $\gamma$ has a cost of at most $\delta$, $w_{\infty}(\gamma)\leq\delta$.
Hence, the $(1-\delta)$-partial $\infty$-Wasserstein distance from $\mu$ to
$\nu$ would be at most $\delta$ and $\Pi_{\infty,1}(\mu,\nu)\leq\delta$, as
claimed.

Consider a bipartite graph $G^{\prime}_{\delta}$ obtained from $G_{\delta}$ by
adding a fake vertex $b^{\prime}$, where $b^{\prime}$ has a mass of $\delta$
and is connected to all points of $A$ with a cost $\delta$. For any subset
$S\subseteq A$ (resp. $T\subseteq B$), let ${\mathcal{N}}^{\prime}(S)$ (resp.
${\mathcal{N}}^{\prime}(T)$) denote the set of neighbors of $S$ (resp. $T$) in
$G^{\prime}_{\delta}$ and suppose $\mu^{\prime}(S)$ (resp. $\nu^{\prime}(T)$)
denotes the total mass of points in $S$ (resp. $T$) for any subset $S\subseteq
A$ (resp. $T\subseteq B\cup\\{b^{\prime}\\}$). By construction, for any subset
$S\subseteq A$, $\mu^{\prime}(S)\leq\nu^{\prime}({\mathcal{N}}^{\prime}(S))$
and similarly, for any subset $T\subseteq B$,
$\nu^{\prime}(T)\leq\mu^{\prime}({\mathcal{N}}^{\prime}(T))$; hence, by the
extension of Hall’s marriage theorem (Bansil & Kitagawa, 2021), there exists a
transport plan $\gamma^{\prime}$ on the graph $G^{\prime}_{\delta}$ that
transports all mass of the points in $A$ to the points in
$B\cup\\{b^{\prime}\\}$. Let $\gamma$ denote the transport plan obtained from
$\gamma^{\prime}$ after removing the fake vertex $b^{\prime}$ and all mass
transportation to $b^{\prime}$. The transport plan $\gamma$ transports at
least $1-\delta$ mass and has a cost $w_{\infty}(\gamma^{\prime})\leq\delta$.
Therefore, if $\gamma$ transports a total mass of $1-\delta^{\prime}$ for some
$\delta^{\prime}\leq\delta$,

$W_{\infty,1-\delta}(\mu,\nu)\leq W_{\infty,1-\delta^{\prime}}(\mu,\nu)\leq
w_{\infty}(\gamma)\leq\delta,$

which means that $\Pi_{\infty,1}(\mu,\nu)\leq\delta=\pi(\mu,\nu)$. We next
show that $\Pi_{\infty,1}(\mu,\nu)\geq\pi(\mu,\nu)$ in a similar way and
conclude that $\Pi_{\infty,1}(\mu,\nu)=\pi(\mu,\nu)$.

Let $\delta:=\Pi_{\infty,1}(\mu,\nu)$. Let $\gamma$ be a $(1-\delta)$-partial
OT plan from $\mu$ to $\nu$ and let $G_{\delta}$ be a $\delta$-disk graph on
$A\cup B$. Since $w_{\infty}(\gamma)\leq\delta$, all mass transportation by
$\gamma$ has a cost at most $\delta$, i.e., all edges carrying a positive mass
in $\gamma$ are present in $G_{\delta}$. For any subset $S\subseteq A$, let
$\mu_{S}$ be the distribution of the mass of $\mu$ on the points in $S$.
Define $\nu_{S}:=\gamma\\#\mu_{S}$ to be the subset of mass of $\nu$ that is
transported from $\mu_{S}$ according to $\gamma$, and let $T_{S}\subseteq B$
be the support of $\nu_{S}$. Recall that all edges carrying a positive mass in
$\gamma$ are present in $G_{\delta}$; therefore, all points in $T_{S}$ are
neighbors of $S$ in $G_{\delta}$, i.e., $T\subseteq{\mathcal{N}}(S)$ and
$\nu(T_{S})\leq\nu({\mathcal{N}}(S))$. Furthermore, since $\gamma$ is a
$(1-\delta)$-partial OT plan, the total mass of $\mu_{S}$ that is not
transported by $\gamma$ is at most $\delta$, and hence,

$\mu(S)\leq\nu(T_{S})+\delta\leq\nu({\mathcal{N}}(S))+\delta.$

One can also show that for each subset $T\subseteq B$,
$\nu(T)\leq\mu({\mathcal{N}}(T))+\delta$ using an identical argument.
Therefore, by the definition of the Lévy-Prokhorov distance,
$\pi(\mu,\nu)\leq\delta=\Pi_{\infty,1}(\mu,\nu)$. ∎

In the following, we show that for any pair of (continuous) probability
distributions $\mu$ and $\nu$ and any $\varepsilon>0$,

$|\Pi_{\infty,1}(\mu,\nu)-\pi(\mu,\nu)|\leq\varepsilon$ (21)

and conclude that $\Pi_{\infty,1}(\mu,\nu)=\pi(\mu,\nu)$ for any pair of
probability distributions (discrete or continuous).

Define $\Box$ to be a unit $d$-dimensional hypercube containing the set
${\mathcal{X}}$. Let ${\mathcal{G}}$ be a grid of cell side length
$\frac{\varepsilon}{4\sqrt{d}}$ that partitions $\Box$ into smaller cells.
Using the grid ${\mathcal{G}}$, we construct two discrete distributions
$\mu^{\varepsilon}$ and $\nu^{\varepsilon}$ as follows. Let
${\mathcal{G}}_{\mathcal{X}}$ denote the subset of cells of ${\mathcal{G}}$
that intersects the set ${\mathcal{X}}$. For each cell
$\xi\in{\mathcal{G}}_{\mathcal{X}}$, we pick an arbitrary point $r_{\xi}$
inside $\xi\cap{\mathcal{X}}$ as the representative point of $\xi$. Let
${\mathcal{R}}:=\bigcup_{\xi\in{\mathcal{G}}}\\{r_{\xi}\\}$. Define
$\mu^{\varepsilon}$ (resp. $\nu^{\varepsilon}$) as a discrete distribution
over ${\mathcal{R}}$ that assigns, for each
$\xi\in{\mathcal{G}}_{\mathcal{X}}$, a mass of $\mu(\xi)$ (resp. $\nu(\xi)$)
to its representative point $r_{\xi}$. This completes the construction of
$\mu^{\varepsilon}$ and $\nu^{\varepsilon}$. Note that by Lemma 4,

$\Pi_{\infty,1}(\mu^{\varepsilon},\nu^{\varepsilon})=\pi(\mu^{\varepsilon},\nu^{\varepsilon}).$
(22)

Furthermore, $W_{\infty}(\mu,\mu^{\varepsilon})\leq\frac{\varepsilon}{4}$,
since there is a transport plan that transports the mass of $\mu$ inside each
cell $\xi\in{\mathcal{G}}$ to the mass of $\mu^{\varepsilon}$ at $r_{\xi}$ and
each mass transportation has a cost at most $\frac{\varepsilon}{4}$. From
Lemma 3, $\Pi_{\infty,1}(\mu,\mu^{\varepsilon})\leq\frac{\varepsilon}{4}$.
Similarly, $\Pi_{\infty,1}(\nu,\nu^{\varepsilon})\leq\frac{\varepsilon}{4}$.
Therefore, using the triangle inequality,

$|\Pi_{\infty,1}(\mu,\nu)-\Pi_{\infty,1}(\mu^{\varepsilon},\nu^{\varepsilon})|\leq\Pi_{\infty,1}(\mu,\mu^{\varepsilon})+\Pi_{\infty,1}(\nu,\nu^{\varepsilon})\leq\frac{\varepsilon}{2}.$
(23)

One can also show in a similar way that

$|\pi(\mu,\nu)-\pi(\mu^{\varepsilon},\nu^{\varepsilon})|\leq\frac{\varepsilon}{2}.$
(24)

We conclude Equation (21) by combining Equations (22), (23), and (24).

*

###### Proof.

We prove this lemma by first showing that
$\Pi_{p,0}(\mu,\nu)\leq\|\mu-\nu\|_{\mathrm{TV}}$ and then showing that
$\|\mu-\nu\|_{\mathrm{TV}}\leq\Pi_{p,0}(\mu,\nu)$.

Let ${\mathcal{P}}({\mathcal{X}})$ denote the set of all probability
distributions defined over the compact set ${\mathcal{X}}$. Nietert et al.
(2023) showed that one can rewrite the $(1-\varepsilon)$-partial
$p$-Wasserstein distance between $\mu$ and $\nu$ as

$W_{p,1-\varepsilon}(\mu,\nu)=\inf_{\mu^{\prime}\in{\mathcal{P}}({\mathcal{X}}):\|\mu-\mu^{\prime}\|_{\mathrm{TV}}\leq\varepsilon}W_{p}(\mu^{\prime},\nu).$
(25)

Define $\delta=\|\mu-\nu\|_{\mathrm{TV}}$. Plugging $\varepsilon=\delta$ in
Equation (25),

$W_{p,1-\delta}(\mu,\nu)=0.$ (26)

Therefore, by Lemma 3,

$\Pi_{p,0}(\mu,\nu)\leq\max\\{0,\delta\\}=\delta=\|\mu-\nu\|_{\mathrm{TV}}.$
(27)

Next, let $\delta^{\prime}=\Pi_{p,0}(\mu,\nu)$. By definition of the
$(p,0)$-RPW, $W_{p,1-\delta^{\prime}}(\mu,\nu)\leq 0\times\delta^{\prime}=0$
(since the parameter $k$ is set to $0$), and since the partial $p$-Wasserstein
distance is non-negative, $W_{p,1-\delta^{\prime}}(\mu,\nu)=0$. Therefore,

$0=W_{p,1-\delta^{\prime}}(\mu,\nu)=\inf_{\mu^{\prime}\in{\mathcal{P}}({\mathcal{X}}):\|\mu-\mu^{\prime}\|_{\mathrm{TV}}\leq\delta^{\prime}}W_{p}(\mu^{\prime},\nu).$
(28)

Let $\mu^{*}$ be the distribution realizing the infimum in Equation (28).
Then, $W_{p}(\mu^{*},\nu)=0$, and by the metric properties of the
$p$-Wasserstein distance, $\mu^{*}=\nu$; hence,

$\|\mu-\nu\|_{\mathrm{TV}}=\|\mu-\mu^{*}\|_{\mathrm{TV}}\leq\delta^{\prime}=\Pi_{p,0}(\mu,\nu).$
(29)

Combining Equations (27) and (29),
$\Pi_{p,0}(\mu,\nu)=\|\mu-\nu\|_{\mathrm{TV}}$. ∎

*

###### Proof.

Let $\delta^{\prime}:=W_{p}(\mu,\nu)$. In this case,

$W_{p,1-\min\\{1,\frac{\delta^{\prime}}{k}\\}}(\mu,\nu)\leq
W_{p}(\mu,\nu)=k\times\frac{\delta^{\prime}}{k}.$

Therefore, by Lemma 3,
$\Pi_{p,k}(\mu,\nu)\leq\max\\{\min\\{1,\frac{\delta^{\prime}}{k}\\},\frac{\delta^{\prime}}{k}\\}=\frac{1}{k}W_{p}(\mu,\nu)$.

We next show that
$\frac{1}{k}W_{p}(\mu,\nu)\leq\Pi_{p,k}(\mu,\nu)+k^{-\frac{p+1}{p}}$. Note
that the inequality holds trivially for any $k\leq 1$, since
$k^{-\frac{p+1}{p}}\geq\frac{1}{k}\geq\frac{1}{k}W_{p}(\mu,\nu)$. We therefore
assume that $k>1$. Let $\delta=\Pi_{p,k}(\mu,\nu)$. Since the
$(1-\frac{1}{k})$-partial $p$-Wasserstein distance is at most $1$, by Lemma 3,
$\delta\leq\max\\{\frac{1}{k},\frac{1}{k}W_{p,1-\frac{1}{k}}(\mu,\nu)\\}\leq\frac{1}{k}$.
Let $\gamma$ be a $(1-\delta)$-partial OT plan. Since the underlying metric
space has a unit diameter, the remaining $\delta$ mass of $\mu$ and $\nu$ with
respect to $\gamma$ can be transported at a cost at most $\delta$; therefore,

$\displaystyle
W_{p}(\mu,\nu)\leq\big{(}w_{p}^{p}(\gamma)+\delta\big{)}^{1/p}\leq\big{(}(k\delta)^{p}+\frac{1}{k}\big{)}^{1/p}\leq
k\delta+k^{-1/p}.$

Equivalently,
$\frac{1}{k}W_{p}(\mu,\nu)\leq\Pi_{p,k}(\mu,\nu)+k^{-\frac{p+1}{p}}$. ∎

###  A.4 Missing Details of Section 5.

In this section, we provide the details of the algorithms mentioned in Section
5.

Highly-Accurate Algorithm. In this algorithm, we obtain an approximation of
our metric by a simple guessing procedure as follows. Starting from an initial
guess $g_{1}=0.5$ for the value of our metric, at any step $i$ of our
algorithm and for any guess value $g_{i}\geq 0$, define
$w_{i}:=W_{p,1-g_{i}}(\mu,\nu)$. If $w_{i}\leq kg_{i}$, then by Lemma 3,
$w_{i}\leq\Pi_{p,k}(\mu,\nu)\leq g_{i}$, i.e., our guess value is large and we
set $g_{i+1}\leftarrow g_{i}-2^{-(i+1)}$. Otherwise, $w_{i}>kg_{i}$, and in
this case, by Lemma 3, $g_{i}\leq\Pi_{p,k}(\mu,\nu)<w_{i}$, i.e., our guess
value is small and we set $g_{i+1}\leftarrow g_{i}+2^{-(i+1)}$. Note that at
any step $i$, $|g_{i}-\Pi_{p,k}(\mu,\nu)|\leq 2^{-i}$. Therefore, to obtain a
$\delta$-additive approximation of the $(p,k)$-RPW, the algorithm returns the
guess value $g_{i}$ when $2^{-i}\leq\delta$. This completes the description of
our algorithm.

We next analyze the running time of this algorithm. Computing the
$(1-g_{i})$-partial $p$-Wasserstein distance can be done using a standard OT
solver in an augmented space (Chapel et al., 2020), which takes $O(n^{3}\log
n)$ time (Edmonds & Karp, 1972; Orlin, 1988). The total number of iterations
of our algorithm is $O(\log\delta^{-1})$ and therefore, our algorithm runs in
$O(n^{3}\log n\log\delta^{-1})$ time.

Computing Through an Approximate OT-Profile. In this part, we show that an
approximation of the OT-profile can be used to approximate our metric. We then
conclude that one can use the LMR algorithm to obtain such approximations of
the OT-profile and to obtain a $\delta$-additive approximation of the RPW
distance in $O(\frac{n^{2}}{\delta^{p}}+\frac{n}{\delta^{2p}})$ time.

For a $\delta^{\prime}\in(0,1]$, $p\geq 1$, and $\alpha\in[0,1]$, let
$\overline{W}_{p,\alpha}(\mu,\nu)$ denote a $\delta^{\prime}$-close
$\alpha$-partial $p$-Wasserstein distance, i.e.,
$W_{p,\alpha}(\mu,\nu)\leq\overline{W}_{p,\alpha}(\mu,\nu)\leq
W_{p,\alpha}(\mu,\nu)+\delta^{\prime}$. Define

$\overline{\Pi}_{p,k}(\mu,\nu)=\min\\{\varepsilon\geq
0\mid\overline{W}_{p,1-\varepsilon}(\mu,\nu)\leq k\varepsilon\\}$

to be the $(p,k)$-RPW distance function when computed using the approximate
partial $p$-Wasserstein distances. In the following lemma, we show that
$\overline{\Pi}_{p,k}(\mu,\nu)$ is a $\frac{2\delta^{\prime}}{k}$-additive
approximation of $\Pi_{p,k}(\mu,\nu)$.

lemmaapprox For any pair of distributions $\mu$ and $\nu$ in a metric space
$({\mathcal{X}},c)$ with a unit diameter and any parameters $p\geq 1$, $k>0$,
and $\delta^{\prime}>0$,

$\Pi_{p,k}(\mu,\nu)\leq\overline{\Pi}_{p,k}(\mu,\nu)\leq\Pi_{p,k}(\mu,\nu)+\frac{2\delta^{\prime}}{k}.$

###### Proof.

Let $\overline{\delta}:=\overline{\Pi}_{p,k}(\mu,\nu)$. By definition,

$W_{p,1-\overline{\delta}}(\mu,\nu)\leq\overline{W}_{p,1-\overline{\delta}}(\mu,\nu)\leq
k\overline{\delta}.$ (30)

Therefore,
$\Pi_{p,k}(\mu,\nu)\leq\overline{\delta}=\overline{\Pi}_{p,k}(\mu,\nu)$. Next,
let $\delta:=\Pi_{p,k}(\mu,\nu)$. By definition,

$\overline{W}_{p,1-\delta}(\mu,\nu)\leq
W_{p,1-\delta}(\mu,\nu)+\delta^{\prime}\leq k\delta+\delta^{\prime}.$ (31)

By properties of the partial $p$-Wasserstein distance,

$\displaystyle\overline{W}_{p,1-\delta-\frac{2\delta^{\prime}}{k}}(\mu,\nu)$
$\displaystyle\leq
W_{p,1-\delta-\frac{2\delta^{\prime}}{k}}(\mu,\nu)+\delta^{\prime}\leq
W_{p,1-\delta}(\mu,\nu)+\delta^{\prime}\leq\overline{W}_{p,1-\delta}(\mu,\nu)+\delta^{\prime}.$
(32)

Combining Equations (31) and (32),

$\overline{W}_{p,1-\delta-\frac{2\delta^{\prime}}{k}}(\mu,\nu)\leq\overline{W}_{p,1-\delta}(\mu,\nu)+\delta^{\prime}\leq
k(\delta+\frac{2\delta^{\prime}}{k}).$

Therefore,
$\overline{\Pi}_{p,k}(\mu,\nu)\leq\delta+\frac{2\delta^{\prime}}{k}=\Pi_{p,k}(\mu,\nu)+\frac{2\delta^{\prime}}{k}$.
∎

##  Appendix B Additional Experiment Results of Section 6

In this section, we present the results of our experiments on the COREL
dataset for the task of image retrieval.

|  |
---|---|---
(i) Noise in datasets | (ii) Shift in datasets | (iii) Noise and shift in datasets
Figure 7: The results of our experiments on image retrieval on the COREL
dataset.

Similar to the CIFAR-10 dataset, the COREL dataset also consists of color
images, where images with the same labels may have significant variations and
shifts. Due to these variations, $2$-Wasserstein and TV distances achieve
lower accuracy in comparison to the $1$-Wasserstein distance. The
$(2,0.1)$-RPW distance, however, outperforms the $1$-Wasserstein distance for
this dataset.