# Decentralized Entropic Optimal Transport for
Privacy-preserving Distributed Distribution Comparison

Xiangfeng Wang1 Hongteng Xu2 Moyi Yang1
1School of Computer Science and Technology, East China Normal University
2Gaoling School of Artificial Intelligence, Renmin University of China
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
The authors have equal contributions and are listed in alphabetical order of
their last names.

###### Abstract

Privacy-preserving distributed distribution comparison measures the distance
between the distributions whose data are scattered across different agents in
a distributed system and cannot be shared among the agents. In this study, we
propose a novel decentralized entropic optimal transport (EOT) method, which
provides a privacy-preserving and communication-efficient solution to this
problem with theoretical guarantees. In particular, we design a mini-batch
randomized block-coordinate descent (MRBCD) scheme to optimize the
decentralized EOT distance in its dual form. The dual variables are scattered
across different agents and updated locally and iteratively with limited
communications among partial agents. The kernel matrix involved in the
gradients of the dual variables is estimated by a distributed kernel
approximation method, and each agent only needs to approximate and store a
sub-kernel matrix by one-shot communication and without sharing raw data. We
analyze our method’s communication complexity and provide a theoretical bound
for the approximation error caused by the convergence error, the approximated
kernel, and the mismatch between the storage and communication protocols.
Experiments on synthetic data and real-world distributed domain adaptation
tasks demonstrate the effectiveness of our method.

##  1 Introduction

Distribution comparison plays a central role in many machine learning
problems, such as data clustering (Hammouda & Karray, 2000), generative
modeling (Bond-Taylor et al., 2021; Mattei & Frellsen, 2019), domain
adaptation (Ganin & Lempitsky, 2015; Farahani et al., 2020), etc. As a valid
metric for distributions, optimal transport (OT) distance (Villani, 2009)
provides a powerful solution to this task. Given two distributions, the
optimal transport distance corresponds to the minimum expectation of their
underlying sample distance. The corresponding optimal joint distribution of
sample pairs takes these two distributions as its marginals. Mathematically,
given two probability measures in a compact space $\mathcal{X}$, denoted as
$\mu,\gamma\in\mathcal{P}(\mathcal{X})$, the Kantorovich formulation of the
optimal transport distance between them is defined as

$\displaystyle\begin{aligned}
W(\mu,\gamma)\stackrel{{\scriptstyle\text{def.}}}{{=}}\inf_{\pi\in\Pi(\mu,\gamma)}\int_{\mathcal{X}^{2}}c(x,y)\
\mathrm{d}\pi(x,y),\end{aligned}$ (1)

where $c:\mathcal{X}^{2}\mapsto[0,\infty)$ denotes a continuous cost function,
the joint distribution on the product space $\mathcal{X}\times\mathcal{X}$ is
denoted as the coupling $\pi$, and
$\Pi(\mu,\gamma)=\\{\pi\in\mathcal{P}(\mathcal{X}\times\mathcal{X})\ \big{|}\
\forall({\mathcal{A}},{\mathcal{B}})\subset\mathcal{X}\times\mathcal{X},\pi({\mathcal{A}}\times\mathcal{X})=\mu({\mathcal{A}}),\pi(\mathcal{X}\times{\mathcal{B}})=\gamma({\mathcal{B}})\\}$
denotes the marginal constraints of the coupling. The OT distance is
applicable even if the supports of the two distributions are non-overlapped.
Therefore, leveraging it to fit a model distribution to the data distribution
(Arjovsky et al., 2017; Deshpande et al., 2018) or transferring a source
distribution to a target one (Courty et al., 2014; Damodaran et al., 2018)
usually leads to encouraging performance.

In practice, the optimal transport distance in equation 1 is often implemented
with an entropic regularizer (Cuturi, 2013; Blondel et al., 2018), which leads
to a strictly-convex optimization problem called entropic optimal transport
(EOT):

$\displaystyle\begin{aligned}
W_{\varepsilon}(\mu,\gamma)\stackrel{{\scriptstyle\text{def.}}}{{=}}\inf_{\pi\in\Pi(\mu,\gamma)}\int_{\mathcal{X}^{2}}c(x,y)\
\mathrm{d}\pi(x,y)-\varepsilon H(\pi),\end{aligned}$ (2)

where $H(\pi)=-\int_{\mathcal{X}\times\mathcal{X}}\pi(x,y)\log(\pi(x,y)-1)\
\mathrm{d}x\mathrm{d}y$ denotes the entropy of $\pi$. Given the samples of
$\mu$ and $\gamma$, this problem can be solved more efficiently using
alternate minimization schemes, e.g., the Sinkhorn algorithm (Cuturi, 2013)
and its stochastic version (Altschuler et al., 2017), the primal-dual method
(Blondel et al., 2018), and the block-coordinate descent method (Genevay et
al., 2016). These algorithms are centralized in general – a central server
records all pairwise costs, i.e., $C=[c(x,y)]$, and optimizes the objective
accordingly.

However, the samples in many real-world applications are often large-scale and
scattered across different agents in a distributed and decentralized system
(i.e., each agent only has limited storage and computation power, and none
works as a central server). In addition, sharing raw data directly can be
forbidden in this system because of privacy and security requirements. As
illustrated in Figure 1, such a scenario leads to a challenging privacy-
preserving distributed distribution comparison task, in which each agent can
access neither the whole sample sets nor the complete cost matrix $C$.
Accordingly, a decentralized method is required to solve the EOT problem with
limited and privacy-preserving communications.

Figure 1: An illustration of the privacy-preserving distributed distribution
comparison task and the corresponding decentralized entropic optimal transport
problem. To emphasis, the data in two domains obey the distribution $\mu$ and
$\gamma$, respectively, but are scattered among different agents. Each agent
merely contains a part of samples, and the local distribution is denoted as
$\mu_{i}$ (or $\gamma_{j}$).

In this study, we propose a novel decentralized entropic optimal transport
method, which provides a theoretically-guaranteed solution to privacy-
preserving distributed distribution comparison. In particular, our method
considers the dual form of the EOT problem, in which the dual objective
involves a kernel associated with the cost matrix, and the dual variables are
scattered among the agents. We approximate a sub-kernel matrix for each agent
via one-shot communication and avoid sharing raw data among the agents
(Khanduri et al., 2021). Based on the approximated kernel, the dual variables
are optimized in a mini-batch randomized block-coordinate descent (MRBCD)
scheme (Zhao et al., 2014). Each agent stores and updates the dual variables
corresponding to its local data. The dual variables’ gradients are computed
based on partial dual variables (rather than raw data) from some randomly-
selected agents.

Our method is privacy-preserving and communication-efficient because the
communications do not contain raw data, and the communication cost is
independent of the data dimension. Moreover, as our main theoretical
contribution, we make the first attempt to provide an error bound of
decentralized EOT distance caused by the convergence error, the kernel
approximation error, and the mismatch between the distributed system’s storage
and communication protocols. Experiments on synthetic data verify the
effectiveness of our method and its robustness to hyperparameters and
communication protocols. Furthermore, we test our decentralized EOT in real-
world distributed domain adaptation tasks, demonstrating its usefulness for
privacy-preserving distributed distribution comparison.

##  2 Related Work

###  2.1 Entropic optimal transport methods

Typically, the entropic optimal transport distance can be solved by the
Sinkhorn algorithm (Sinkhorn & Knopp, 1967; Cuturi, 2013; Benamou et al.,
2015) (or its logarithmic variant (Chizat et al., 2018; Schmitzer, 2019) for
improving numerical stability). Following the Sinkhorn algorithm, the method
in (Xie et al., 2020) computes the OT distance via an inexact proximal point
algorithm, which is equivalent to solving an EOT problem with a temporally-
decayed entropic regularizer. The Greenkhorn algorithm (Altschuler et al.,
2017) works as a stochastic Sinkhorn algorithm with significant computation
efficiency. Besides the Sinkhorn algorithm, some other efficient algorithms
are developed, e.g., the Bregman alternating direction method of multipliers
(Bregman ADMM) (Wang & Banerjee, 2014a; Ye et al., 2017), smoothed semi-dual
algorithm (Blondel et al., 2018), and conditional gradient algorithm (Titouan
et al., 2019). The work in (Genevay et al., 2016; Seguy et al., 2018)
introduce stochastic optimization mechanisms into the large-scale optimal
transport problem.

The above methods mainly focus on the EOT problems in centralized scenarios.
The decentralized EOT is seldom studied. Recently, the work in (Zhang & Zhu,
2019; Hughes & Chen, 2021) proposes some ADMM-based decentralized algorithms
for distributed resource allocation tasks. The formulation of their tasks is
relevant to an optimal transport problem rather than an EOT problem. Moreover,
unlike our work, their methods neither apply any privacy-preserving mechanism
nor consider the mismatch between the distributed system’s storage and
communication protocols. Additionally, the decentralized EOT problem differs
from the well-known distributed and decentralized Wasserstein barycenter
problems Staib et al. (2017); Uribe et al. (2018); Dvurechenskii et al.
(2018). In these barycenter problems, the samples of a distribution are still
stored in a single agent so that the (entropic) optimal transport distance
between the distribution and the barycenter can still be computed in a
centralized manner. On the contrary, in our study, each agent can only access
a part of the distribution samples and cannot share them with other agents, so
we need a decentralized algorithm to compute the EOT distance.

###  2.2 Distributed and decentralized optimization

Distributed and decentralized optimization methods can be broadly divided into
primal and primal-dual types (Nedic & Ozdaglar, 2009; Duchi et al., 2011).
Primal methods usually refer to gradient-based methods such as decentralized
gradient descent (DGD) (Yuan et al., 2016; Lobel & Ozdaglar, 2010), EXTRA (Shi
et al., 2015), etc. For large-scale optimization tasks, the stochastic
gradient technique is often applied, e.g., the decentralized stochastic
gradient descent method (D-SGD) (Agarwal & Duchi, 2011) is generalized from
the DGD, with significant computational efficiency acceleration. The primal-
dual approaches further employ dual variables to design distributed
optimization methods, which incorporate distributed dual decomposition
(Terelius et al., 2011), ADMM (Chang et al., 2015; Shi et al., 2014), etc.
More discussions can refer to a series of survey papers (Chang et al., 2020;
Nedic, 2020; Assran et al., 2020).

Besides computational efficiency, communication efficiency is also required
for distributed and decentralized optimization. The most intuitive way to
increase the communication efficiency is to reduce the number of agents
involved in communications (Smith et al., 2018), e.g., the random node
selection scheme (Arablouei et al., 2015; Mao et al., 2020) and the importance
sampling scheme (Chen et al., 2018; Liu et al., 2019). To reduce the
bandwidth, the information for each communication is often compressed by
sparsification (Stich et al., 2018; Basu et al., 2019; Tang et al., 2020) or
quantization (Zhu et al., 2016; Alistarh et al., 2017; Zhang et al., 2019; Lu
& De Sa, 2020). Recently, the distributed and decentralized optimization
techniques have been utilized for distributed deep learning (Tang et al.,
2020), distributed edge AI system (Shi et al., 2020), federated learning (Chen
et al., 2021), etc. As aforementioned, these applications often involve
privacy-preserving distributed distribution comparison, which motivates us to
develop the decentralized EOT method with privacy preservation and
communication efficiency.

##  3 Proposed Algorithm Framework

###  3.1 Dual formulation of decentralized EOT

Suppose that there are $I$ agents in the source domain storing the samples of
$\mu$ and $J$ agents in the target domain storing the samples of $\gamma$, as
illustrated in Figure 1. The distribution of the samples in the $i$-th source
agent (the $j$-th target agent) is denoted as $\mu_{i}$ ($\gamma_{j}$).
Accordingly, the storage of the samples in the agents can be captured by the
following hierarchical model:

$\displaystyle\begin{aligned} \text{Agent selection:}&\quad i\sim p,\quad
j\sim q,\\\ \text{Sample assignment:}&\quad
X_{i}=\\{x_{n}^{(i)}\\}_{n=1}^{N_{i}}\sim\mu_{i},\quad
Y_{j}=\\{y_{m}^{(j)}\\}_{m=1}^{M_{j}}\sim\gamma_{j},\end{aligned}$ (3)

where $p=\\{p_{i}\\}_{i=1}^{I}\in\Delta^{I-1}$ and
$q=\\{q_{j}\\}_{j=1}^{J}\in\Delta^{J-1}$, respectively. $p_{i}$ ($q_{j}$)
represents the probability of selecting the source agent $i$ (the target agent
$j$) to store the corresponding data. $X_{i}=\\{x_{n}^{(i)}\\}_{n=1}^{N_{i}}$
and $\mu_{i}$ denote the samples stored in the agent $i$ and the corresponding
sample distribution. $Y_{j}=\\{y_{m}^{(j)}\\}_{m=1}^{M_{j}}$ and $\gamma_{j}$
are denoted in the same way. Obviously, we have $\mu=\sum_{i}p_{i}\mu_{i}$,
$\gamma=\sum_{j}q_{j}\gamma_{j}$, $X=\\{x_{n}\\}_{n=1}^{N}=\cup_{i}X_{i}$, and
$Y=\\{y_{m}\\}_{m=1}^{M}=\cup_{j}Y_{j}$.

  * •

Storage Protocol. Sampling source and target agents independently from $p$ and
$q$ is equivalent to sampling the agent pairs from the distribution $p\otimes
q=[p_{i}q_{j}]$. Here, we define $p\otimes q$ as the storage protocol of the
distributed system.

Taking the storage protocol and the Fenchel dual form of the EOT distance
(Peyré & Cuturi, 2019) into account, we rewrite the EOT distance in equation 2
as follows:

$\displaystyle\begin{aligned}
W_{\varepsilon}(\mu,\gamma)&=\sideset{}{{}_{u,v\in\mathcal{C}_{\mathcal{X}}}}{\sup}\int_{\mathcal{X}}u(x)\mathrm{d}\mu(x)+\int_{\mathcal{X}}v(y)\mathrm{d}\gamma(y)-\varepsilon\int_{\mathcal{X}^{2}}e^{\frac{u(x)+v(y)-c(x,y)}{\varepsilon}}\mathrm{d}\mu(x)\mathrm{d}\gamma(y)\\\
&=\sideset{}{{}_{u,v\in\mathcal{C}_{\mathcal{X}}}}{\sup}\mathbb{E}_{x\sim\mu,y\sim\gamma}f_{\varepsilon}(x,y,u,v)\\\
&=\sideset{}{{}_{u,v\in\mathcal{C}_{\mathcal{X}}}}{\sup}\mathbb{E}_{(i,j)\sim
p\otimes
q}\mathbb{E}_{x\sim\mu_{i},y\sim\gamma_{j}}f_{\varepsilon}(x,y,u,v).\end{aligned}$
(4)

Here, $\mathcal{C}_{\mathcal{X}}$ represents the set of continuous functions
defined in $\mathcal{X}$, $u,v\in\mathcal{C}_{\mathcal{X}}$ denote the dual
functions, which are also called Kantorovich potentials, and

$\displaystyle\begin{aligned} f_{\varepsilon}(x,y,u,v)=u(x)+v(y)-\varepsilon
e^{\frac{u(x)+v(y)}{\varepsilon}}\underbrace{e^{-\frac{c(x,y)}{\varepsilon}}}_{\kappa(x,y)},\end{aligned}$
(5)

where $\kappa(x,y)$ is a kernel function associated with the cost $c(x,y)$.
The second equation in equation 4 indicates that the EOT problem can be
modeled as an unconstrained expectation maximization problem with respect to
$u$ and $v$ (Genevay et al., 2016). The third equation in equation 4 is based
on the hierarchical model in equation 3.

  * •

Communication Protocol. As shown in equation 4, computing the EOT distance
requires us to sample agent pairs based on the storage protocol. In practice,
however, the sampling of the agent pairs is determined by the communication
protocol rather than the storage protocol of the distributed system. Here, we
define the communication protocol as the distribution of the communicable
agent pairs, denoted as $E=[e_{ij}]\in\\{E\in\mathbb{R}_{+}^{I\times
J}\,|\,{\mathbf{1}}_{I}^{\top}E{\mathbf{1}}_{J}=1\\}$.

Note that, the communication protocol can be mismatched with the storage
protocol. For example, some systems do not allow multi-step routes and/or
restrict the communication between the agents to be directed, which may cause
$E\neq p\otimes q$. As a result, we actually approximate
$W_{\varepsilon}(\mu,\gamma)$ by the following surrogate:

$\displaystyle\begin{aligned}
\widetilde{W}_{\varepsilon}(\mu,\gamma)\stackrel{{\scriptstyle\text{def.}}}{{=}}\sup_{u,v\in\mathcal{C}_{\mathcal{X}}}\mathbb{E}_{(i,j)\sim
E}\mathbb{E}_{x\sim\mu_{i},y\sim\gamma_{j}}f_{\varepsilon}(x,y,u,v).\end{aligned}$
(6)

In theory, the gap between $\widetilde{W}_{\varepsilon}(\mu,\gamma)$ and
$W_{\varepsilon}(\mu,\gamma)$ is bounded under mild assumptions:

######  Theorem 1.

Let $\mu=\sum_{i}p_{i}\mu_{i}$ and $\gamma=\sum_{j}q_{j}\gamma_{j}$ be the two
distributions in a distributed system with $I$ source agents and $J$ target
agents, whose storage and communication protocols are $p\otimes
q=[p_{i}q_{j}]$ and $E=[e_{ij}]$, respectively. Let
$\max_{i,j}W_{\varepsilon}(\mu_{i},\gamma_{j})\leq\tau$ for some $\tau>0$ and
$\sum_{i,j}|e_{ij}-p_{i}q_{j}|\leq\sigma$ for some $\sigma>0$. We have

$\displaystyle|\widetilde{W}_{\varepsilon}(\mu,\gamma)-W_{\varepsilon}(\mu,\gamma)|\leq\tau\sigma.$
(7)

Theorem 1 indicates that as long as the mismatch between the storage and
communication protocols (i.e., $\sigma$) is small, we can approximate
$W_{\varepsilon}(\mu,\gamma)$ well by
$\widetilde{W}_{\varepsilon}(\mu,\gamma)$.111Theorem 1 is valid for both
continuous probability measures and sample-based discrete measures. Ideally,
$\widetilde{W}_{\varepsilon}(\mu,\gamma)=W_{\varepsilon}(\mu,\gamma)$ when
$E=p\otimes q$. Fortunately, this ideal case can be available in many
situations. For example, in a distributed system built on a connected network
and with a known storage protocol, we can first select a source agent based on
$p$ and then select a target agent based on $q$ (so that $E=p\otimes q$). In
more general settings, we often can adjust the communication protocol,
matching it with the storage protocol as much as possible.

Given the samples of $\mu$ and $\gamma$, the problem in equation 6 becomes

$\displaystyle\begin{aligned}
\max_{\begin{subarray}{c}u=\\{u^{(i)}\\}_{i=1}^{I}\in\mathbb{R}^{N}\\\
v=\\{v^{(j)}\\}_{j=1}^{J}\in\mathbb{R}^{M}\end{subarray}}\overbrace{\sideset{}{}{\sum}_{i=1}^{I}\sideset{}{}{\sum}_{j=1}^{J}\frac{e_{ij}}{N_{i}M_{j}}\underbrace{f_{\varepsilon}(K_{ij},u^{(i)},v^{(j)})}_{f_{\varepsilon}^{(i,j)}}}^{F_{\varepsilon}(u,v;K,E)},\end{aligned}$
(8)

where the dual functions $u(x)$ and $v(y)$ become the dual variables
$u\in\mathbb{R}^{N}$ and $v\in\mathbb{R}^{M}$, respectively. The dual
objective $F_{\varepsilon}(u,v;K,E)$ takes the kernel matrix
$K=[\kappa(x_{n},y_{m})]\in\mathbb{R}^{N\times M}$ and the communication
protocol $E$ as its hyperparameters. The dual objective is decomposable — for
the agent pair $(i,j)$,
$f_{\varepsilon}^{(i,j)}=\sum_{n=1}^{N_{i}}\sum_{m=1}^{M_{j}}f_{\varepsilon}(\kappa(x_{n}^{(i)},y_{m}^{(j)}),u_{n}^{(i)},v_{m}^{(j)})=u_{n}^{(i)}+v_{m}^{(j)}-\varepsilon\exp(\frac{u_{n}^{(i)}+v_{m}^{(j)}}{\varepsilon})\kappa(x_{n}^{(i)},y_{m}^{(j)})$
is the corresponding local objective, in which
$K_{ij}=[\kappa(x_{n}^{(i)},y_{m}^{(j)})]\in\mathbb{R}^{N_{i}\times M_{j}}$ is
a block of $K$. Moreover, each local objective only involves a part of dual
variables that correspond to the local samples stored in the agents, e.g., the
$u^{(i)}=[u_{n}^{(i)}]\in\mathbb{R}^{N_{i}}$ in $f_{\varepsilon}^{(i,j)}$
corresponds to the samples $\\{x_{n}^{(i)}\\}_{n=1}^{N_{i}}$ in the source
agent $i$. As a result, the dual variables can be scattered across different
agents, and accordingly, the gradient of $u^{(i)}$ can be formulated as
follows:

$\displaystyle\begin{aligned}
\nabla_{u^{(i)}}F_{\varepsilon}(u,v;K,E)=\sideset{}{}{\sum}_{j=1}^{J}\frac{e_{ij}}{N_{i}M_{j}}\nabla_{u^{(i)}}f_{\varepsilon}^{(i,j)}=\sum_{j=1}^{J}\frac{e_{ij}}{N_{i}M_{j}}\begin{bmatrix}\sum_{m=1}^{M_{j}}1-e^{\frac{u_{1}^{(i)}+v_{m}^{(j)}}{\varepsilon}}\kappa(x_{1}^{(i)},y_{m}^{(j)})\\\
\vdots\\\
\sum_{m=1}^{M_{j}}1-e^{\frac{u_{N_{i}}^{(i)}+v_{m}^{(j)}}{\varepsilon}}\kappa(x_{N_{i}}^{(i)},y_{m}^{(j)})\end{bmatrix}.\end{aligned}$
(9)

The gradient in equation 9 points out the challenges of the proposed
decentralized EOT problem. In particular, when computing the gradient of
$u^{(i)}$, we need to transmit the raw data and the dual variables of all the
agents in the other domain to the agent $i$. The communication cost of this
step is high, especially for high-dimensional data. Moreover, sharing raw data
results in the leakage of private information. Facing the above challenges, in
the following subsection, we will introduce a decentralized EOT method to
solve equation 8 in a privacy-preserving and communication-efficient way.

###  3.2 Proposed decentralized EOT method

The proposed decentralized EOT method consists of two steps: $i)$ leveraging a
theoretically-guaranteed method to approximate the kernel matrix without the
share of raw data and $ii)$ updating the dual variables locally and
iteratively in a mini-batch randomized block-coordinate descent (MRBCD)
scheme.

Privacy-preserving kernel approximation. When the cost $c(x,y)$ is Euclidean,
the kernel $\kappa(x,y)$ in equation 5 is a special case of the following
generalized inner product (GIP) kernel (Khanduri et al., 2021):

$\displaystyle\begin{aligned}
\kappa(x,y)=g(\phi(x,y),\|x\|,\|y\|),\end{aligned}$ (10)

where $\phi(x,y)=\arccos(\frac{\langle x,y\rangle}{\|x\|\|y\|})$, and
$g(\phi,\|x\|,\|y\|)$ is a $G$-Lipschitz continuous function with respect to
$\phi$.

For the GIP kernel, it is possible to approximate it without the share of raw
data (Khanduri et al., 2021). Denote $D$ as the dimension of samples.
Leveraging the random seed sharing method in (Xu et al., 2021; Richards et
al., 2020), we can sample $P$ $D$-dimensional random variables from a
multivariate normal distribution, i.e.,
$\\{\omega_{\ell}\\}_{\ell=1}^{P}\sim\mathcal{N}(0,I_{D})$, and broadcast them
to all the agents. Based on the random variables, we can construct a binary
matrix for each agent. Take the source agent $i$ as an example. Given $N_{i}$
samples $\\{x_{n}^{(i)}\\}_{n=1}^{N_{i}}$, we have

$\displaystyle\begin{aligned}
A_{\mu_{i}}=[\mathbb{I}(\langle\omega_{\ell},x_{n}^{(i)}\rangle\geq
0)]\in\\{0,1\\}^{P\times N_{i}},\end{aligned}$ (11)

where $\mathbb{I}(\cdot)$ is an indicator, which outputs 1 if the input
statement is true and outputs 0 otherwise. As a result, for each agent pair
$(i,j)$, the kernel $\kappa(x_{n}^{(i)},y_{m}^{(j)})$ of their samples can be
approximated by

$\displaystyle\begin{aligned}
\hat{\kappa}(x_{n}^{(i)},y_{m}^{(j)})=g(\hat{\psi}(a_{n}^{(i)},a_{m}^{(j)}),\|x_{n}^{(i)}\|,\|y_{m}^{(j)}\|)=g\Bigl{(}\pi\
\Bigl{|}1-\frac{2}{P}\langle
a_{n}^{(i)},a_{m}^{(j)}\rangle\Bigr{|},\|x_{n}^{(i)}\|,\|y_{m}^{(j)}\|\Bigr{)},\end{aligned}$
(12)

where $a_{n}^{(i)}$ is the $n$-th column of $A_{\mu_{i}}$ and $a_{m}^{(j)}$ is
the $m$-th column of $A_{\gamma_{i}}$. Based on equation 12, we can obtain an
approximated kernel matrix for an agent pair $(i,j)$, i.e.,
$\widehat{K}_{ij}=[\hat{\kappa}(x_{n}^{(i)},y_{m}^{(j)})]$. This approximation
preserves data privacy because it only requires two constructed binary
matrices and the norms of samples. The scheme of the privacy-preserving kernel
approximation method is shown in Algorithm 1. The communication complexity of
each step is shown in red.

Algorithm 1 Privacy-preserving Kernel Approximation

1: Draw random variables
$\\{\omega_{\ell}\in\mathbb{R}^{D}\\}_{\ell=1}^{P}\sim\mathcal{N}(0,I_{D})$
and broadcast them to all agents.

2: for Each source agent $i\in\\{1,...,I\\}$ do

3: Construct $A_{\mu_{i}}$ via equation 11 and broadcast it to all target
agents.$\mathcal{O}(JN_{i}P)$

4: If data is not normalized, broadcast $\\{\|x_{n}^{(i)}\|\\}_{n=1}^{N_{i}}$
to all target agents.$\mathcal{O}(JN_{i})$

5: end for

6: for Each target agent $j\in\\{1,...,J\\}$ do

7: Construct $A_{\gamma_{j}}$ via equation 11 and broadcast it to all source
agents.$\mathcal{O}(IM_{j}P)$

8: If data is not normalized, broadcast $\\{\|y_{m}^{(j)}\|\\}_{m=1}^{M_{j}}$
to all source agents.$\mathcal{O}(IM_{j})$

9: end for

10: Construct $\\{\widehat{K}_{ij}\\}_{j=1}^{J}$ for each source agent $i$ and
$\\{\widehat{K}_{ij}\\}_{i=1}^{I}$ for each target agent $j$ via equation 12.

As shown in Algorithm 1, by one-shot communication, each agent obtains the
matrices $A$’s from all the agents in the other domain. Accordingly, the
overall communication complexity is $\mathcal{O}((IM+JN)P)$. Note that, this
complexity is independent with the sample dimension $D$, so it is suitable for
high-dimensional cases. Moreover, even if $P=\mathcal{O}(N)$, the practical
communication cost can still be tractable because the matrices $A$’s are
binary and can be compressed before communication. The precision of the
proposed approximation is guaranteed under mild assumptions:

  * •

Assumption 1. The kernel in the objective is a GIP kernel, i.e.,
$\kappa(x,y)=g(\phi(x,y),\|x\|,\|y\|)$ and $g$ is a $G$-Lipschitz continuous
function with respect to $\phi$.

  * •

Assumption 2. Both the kernel $\kappa$ and its approximation $\hat{\kappa}$
are bounded, i.e., $|\kappa(x,y)|\leq b$ and $|\hat{\kappa}(x,y)|\leq b$ for
some $b\geq 1$.

######  Theorem 2.

Let $K\in\mathbb{R}^{N\times M}$ be the matrix defined by the GIP kernel in
equation 10 and $\widehat{K}$ be the approximation achieved via equation 12.
Based on the assumptions 1-2, with probability at least $1-\delta$, we have
$\|K-\widehat{K}\|\leq
G(N+M)\Bigl{(}\sqrt{\frac{32\pi^{2}}{P}\log\frac{2(N+M)}{\delta}}+\frac{8\pi}{3P}\log\frac{2(N+M)}{\delta}\Bigr{)}$.

Theorem 2 means that $\widehat{K}\rightarrow K$ when $P\rightarrow\infty$.
$P=\mathcal{O}(\epsilon^{-2})$ achieves an approximation error $\epsilon>0$.
Theorem 2 is based on the Lemma 4.1 in (Khanduri et al., 2021). More details
can be found at Appendix A.

Algorithm 2 MRBCD for Decentralized EOT Distance

1: For each source agent $i$ and target agent $j$, construct
$\\{\widehat{K}_{ij}\\}_{j=1}^{J}$ and $\\{\widehat{K}_{ij}\\}_{i=1}^{I}$ via
Algorithm 1, and initialize $u^{(i)}=0$ and
$v^{(j)}=0$.$\mathcal{O}((IM+JN)P)$

2: Update dual variables:$\mathcal{O}(TL(\frac{N}{I}+\frac{M}{J}))$

3: for $t=0,1,\cdots,T$ do

4: Set the learning rate $\eta_{t}=\frac{\eta}{\sqrt{t+1}}$.

5: for An agent pair $(i,j)\sim E$ do

6: Select $L$ target agents
$\mathcal{J}_{L}\sim\frac{1}{\|E[i,:]\|_{1}}E[i,:]$. Send
$\\{v^{(j),t}\\}_{j\in\mathcal{J}_{L}}$ to the source agent $i$.

7: $u^{(i),t+1}\leftarrow
u^{(i),t}+\eta_{t}\sum_{j\in\mathcal{J}_{L}}\nabla_{u^{(i)}}\hat{f}_{\varepsilon}^{(i,j),t}$

8: Select $L$ source agents
$\mathcal{I}_{L}\sim\frac{1}{\|E[:,j]\|_{1}}E[:,j]$. Send
$\\{u^{(i),t}\\}_{i\in\mathcal{I}_{L}}$ to the target agent $j$

9: $v^{(j),t+1}\leftarrow
v^{(j),t}+\eta_{t}\sum_{i\in\mathcal{I}_{L}}\nabla_{v^{(j)}}\hat{f}_{\varepsilon}^{(i,j),t}$

10: end for

11: end for

12: For an arbitrary source agent $i$, receive the optimal dual objectives
$\\{\\{\hat{f}_{\varepsilon}^{(i^{\prime},j)}\\}_{j=1}^{J}\\}_{i^{\prime}\neq
i}$ from the remaining agents in the source domain.$\mathcal{O}(IJ)$

13: Compute $\widetilde{W}_{\varepsilon}(\mu,\gamma)$ in the source agent $i$
and broadcast it to all other agents.$\mathcal{O}(IJ)$

Mini-batch randomized block-coordinate descent (MRBCD) scheme. Plugging the
approximated kernel into equation 8, we denote the dual objective using the
approximated kernel, i.e.,
$F_{\varepsilon}(u,v;\widehat{K},E)=\sum_{i,j}e_{ij}\hat{f}_{\varepsilon}^{(i,j)}$,
where
$\hat{f}_{\varepsilon}^{(i,j)}=f_{\varepsilon}(\widehat{K}_{ij},u^{(i)},v^{(j)})$.
Accordingly, we propose a mini-batch randomized block coordinate descent
scheme, computing the gradient of $\hat{f}_{\varepsilon}^{(i,j)}$ based on a
batch of agents and optimizing the decentralized EOT problem iteratively.

Figure 2: An illustration of the proposed decentralized EOT method.

Take a source agent $i$ as an example. In the $t$-th iteration, the agent $i$
receives the dual variables $\\{v^{(j),t}\\}_{j\in\mathcal{J}_{L}}$ from $L$
target agents, where $\mathcal{J}_{L}\subset\\{1,...,J\\}$ denotes the set of
the $L$ target agents. In practice, we sample $\mathcal{J}_{L}$ based on the
communication protocol $E$, i.e.,
$\mathcal{J}_{L}\sim\frac{1}{\|E_{i,:}\|_{1}}E_{i,:}$, where $E_{i,:}$ is the
$i$-th row of $E$. Then, the agent $i$ computes a stochastic gradient
$\sum_{j\in\mathcal{J}_{L}}\nabla_{u^{(i)}}\hat{f}_{\varepsilon}^{(i,j),t}$
(Zhao et al., 2014) and update $u^{(i)}$ via

$\displaystyle\begin{aligned} u^{(i),t+1}\leftarrow
u^{(i),t}+\eta_{t}\sideset{}{{}_{j\in\mathcal{J}_{L}}}{\sum}\nabla_{u^{(i)}}\hat{f}_{\varepsilon}^{(i,j),t}.\end{aligned}$
(13)

Here, $\eta_{t}$ is the learning rate in the $t$-th iteration. We set
$\eta_{t}=\frac{\eta}{\sqrt{t+1}}$, where $\eta$ is the initial learning rate.
The dual variables in the target agents can be updated in a similar way.
Applying the above steps iteratively till the dual variables converge, each
source agent $i$ can compute and store the local dual objectives
$\\{\hat{f}_{\varepsilon}^{(i,j)}\\}_{j=1}^{J}$ based on the information
received during the iterations. Accordingly, the source agent $i$ can compute
the EOT distance $\widetilde{W}_{\varepsilon}(\mu,\gamma)$ by collecting
$\\{\\{\hat{f}_{\varepsilon}^{(i^{\prime},j)}\\}_{j=1}^{J}\\}_{i^{\prime}\neq
i}$ from other source agents. Finally, the source agent $i$ broadcasts
$\widetilde{W}_{\varepsilon}(\mu,\gamma)$ to all other agents.

Algorithm 2 shows the MRBCD scheme, in which the communication complexity per
step is given in red. In particular, when updating the dual variables, the
communication cost per iteration is $\sum_{i\in I_{L}}N_{i}+\sum_{j\in
J_{L}}M_{j}$. When the numbers of samples in different agents are comparable,
i.e., $N_{i}=\mathcal{O}(\frac{N}{I})$ and $M_{j}=\mathcal{O}(\frac{M}{J})$,
the communication complexity per iteration can be represented as
$\mathcal{O}(L(\frac{N}{I}+\frac{M}{J}))$. Accordingly, the overall
communication complexity for updating dual variables is
$\mathcal{O}(TL(\frac{N}{I}+\frac{M}{J}))$, where $T$ is the number of
iterations. When $L=J$, we compute the gradient
$\nabla_{u^{(i)}}F_{\varepsilon}=\sum_{j=1}^{J}\nabla_{u^{(i)}}\hat{f}_{\varepsilon}^{(i,j)}$
exactly, and Algorithm 2 becomes the classic randomized block-coordinate
descent (RBCD) (Nesterov, 2012). When $L=1$, we only consider the exchange of
dual variables between an agent pair in each iteration. This setting is
suitable for the agent with limited computation power because each iteration
only involves a pair of agent. This MRBCD scheme is privacy-preserving, which
only transmits dual variables, local dual objectives, and the approximated EOT
distance. In summary, Figure 2 illustrates the proposed decentralized EOT
method.

Essentially, Algorithm 2 is a decentralized and mini-batch stochastic
implementation of the randomized block-coordinate descent (RBCD) method
Nesterov (2012); Richtárik & Takáč (2014); Lu & Xiao (2015). Therefore,
following the Theorem 3 in Wang & Banerjee (2014b), we analyze the convergence
error of Algorithm 2 as follows:

  * •

Assumption 3. The gradient norm is bounded, i.e.,
$\|\nabla_{u,v}F_{\varepsilon}\|_{2}\leq R$ for some $R>0$.

######  Lemma 3.

For the problem in equation 8 with approximated kernel $\widehat{K}$, let
$(u^{*},v^{*})\in\mathcal{C}^{*}$ be the optimal solution in the optimal
solution set and $\left\\{\left(u^{t},v^{t}\right)\right\\}$ be the sequence
generated by Algorithm 2. Define
$R_{0}=\min_{u,v\in\mathcal{C}^{*}}\|(u^{0},v^{0})-(u,v)\|_{2}$,
$\hat{u}^{t}=\frac{1}{t}\sum_{\ell=1}^{t}u^{\ell}$, and
$\hat{v}^{t}=\frac{1}{t}\sum_{\ell=1}^{t}v^{\ell}$. Based on the assumption 3,
we have

$\displaystyle\begin{aligned}
\mathbb{E}|F_{\varepsilon}(\hat{u}^{t},\hat{v}^{t};\widehat{K},E)-F_{\varepsilon}(u^{*},v^{*};\widehat{K},E)|\leq\mathcal{O}\Bigl{(}\frac{IJ\left((\sqrt{t}+L_{F_{\varepsilon}})R_{0}^{2}+\sqrt{t}R^{2}\right)}{t}\Bigr{)},\end{aligned}$
(14)

where $L_{F_{\varepsilon}}$ denotes the Lipschitz constant of the objective
function $F_{\varepsilon}$ and the expectation is calculated with respect to
the randomly-selected agents.

###  3.3 Theoretical error bound of decentralized EOT

The proposed decentralized EOT method is theoretically-guaranteed. We take the
convergence error of the MRBCD algorithm, the optimal loss caused by the
approximated kernel, and the mismatch between the storage and communication
protocols into account, deriving the bound of the expected approximation error
under mild assumptions. In particular, let $\mu=\sum_{i}p_{i}\mu_{i}$ and
$\gamma=\sum_{j}q_{j}\gamma_{j}$ be the two distributions in a distributed
system with $I$ source agents and $J$ target agents, whose storage and
communication protocols are $p\otimes q=[p_{i}q_{j}]$ and $E=[e_{ij}]$,
respectively. We scatter $N$ samples of $\mu$ to the source agents and $M$
samples of $\gamma$ to the target agents. The kernel matrix of the samples is
approximated via Algorithm 1, with the hyperparameter $P$. As a consequence of
Theorem 1, Theorem 2, and Lemma 3, we have

######  Theorem 4.

For the problem in equation 8 with the kernel $\widehat{K}$ derived by
Algorithm 1, let $\left\\{\left(u^{t},v^{t}\right)\right\\}$ be the sequence
generated by Algorithm 2. Define
$\hat{u}^{t}=\frac{1}{t}\sum_{\ell=1}^{t}u^{\ell}$,
$\hat{v}^{t}=\frac{1}{t}\sum_{\ell=1}^{t}v^{\ell}$, and the gap between the
storage and communication protocols as $\sigma$. Based on the assumptions 1-3,
with probability at least $1-\delta$, we have

$\displaystyle\begin{aligned}
\mathbb{E}|F_{\varepsilon}(\hat{u}^{t},\hat{v}^{t};\widehat{K},E)-W_{\varepsilon}(\mu,\gamma)|\leq\mathcal{O}\Bigl{(}\frac{IJ}{\sqrt{t}}+(N+M)\sqrt{\frac{1}{P}\log\frac{2(N+M)}{\delta}}+\sigma\Bigr{)}.\end{aligned}$
(15)

The proof of the theorem is shown in Appendix A.

##  4 Numerical Experiments

To demonstrate the effectiveness of our decentralized EOT method, we analyze
its performance on synthetic data and apply it to distributed domain
adaptation tasks. Representative results are shown below. Implementation
details and more results are in Appendix B.

###  4.1 Analytic experiments on synthetic data

We first test the performance of the proposed MRBCD scheme and analyze the
influence of the hyperparameter $L$ (i.e., the number of agents used to
compute the gradients in each iteration). In particular, we consider two
synthetic datasets in this experiment: the first dataset contains two 2D
Gaussian distributions $(\mathcal{N}_{1},\mathcal{N}_{2})$, each of which
includes 2,000 samples, and the second one contains two 2D Gaussian mixture
models $(GMM_{1},GMM_{2})$, each of which includes two Gaussian components and
2,000 samples. For each dataset, we randomly scatter one distribution’s
samples to 10 source agents and the other distribution’s samples to 10 target
agents, respectively. Following the decentralized optimization work in (Zhang
& Zhu, 2019; Hughes & Chen, 2021), we assume the network of the agents to be
connected, i.e., there always exists a route between two arbitrary agents.
Accordingly, the storage and communication protocols are uniform
distributions. The kernel matrix is approximated with $P=1000$. We approximate
$W_{\varepsilon}(\mathcal{N}_{1},\mathcal{N}_{2})$ and
$W_{\varepsilon}(GMM_{1},GMM_{2})$ via our MRBCD scheme, in which
$L\in\\{1,2,5,10\\}$, and compare the results with the ground truth achieved
by the centralized Sinkhorn algorithm Cuturi (2013). Figure 3 visualizes the
convergence of our scheme with different $L$’s. We can find that with the
increase of $L$, the convergence is faster because the gradients in each
iteration are computed with less uncertainty. When $L\geq 2$, our method can
approximate the EOT distance with a small gap after sufficient iterations.

(a) $W_{\varepsilon}(\mathcal{N}_{1},\mathcal{N}_{2})$

(b) $W_{\varepsilon}(GMM_{1},GMM_{2})$

Figure 3: The results for the convergence of our MRBCD scheme.

The influence of kernel approximation. The approximation errors shown in
Figure 3 are mainly caused by the approximated kernel (when $L\geq 2$). To
verify this claim, we decouple the influence of algorithmic convergence and
that of kernel approximation, applying our MRBCD scheme with the real kernel
matrix and approximated kernel matrix, respectively. In this experiment, we
consider computing the EOT distance between two Gaussian distributions, each
containing 2,000 samples. By setting $P\in\\{\log N,D,N\\}$, where $N=2000$ is
the number of samples per distribution and $D\in\\{10,50\\}$ is the dimension
of the samples, we approximate the kernel matrix with different precision and
apply our MRBCD accordingly. Experimental results are shown in Figure 4. When
applying the real kernel matrix, our MRBCD method converges quickly, with
results close to the ground truth. When $P=N$, the kernel matrix can be
approximated with high accuracy, and thus, the results are almost the same as
those obtained under the real kernel matrix. When $P=D$, although the
performance of our method degrades, the gap between our result and the ground
truth can be small for high-dimensional cases. Note that, $D\approx\log N$
when $D=10$ and $N=2000$, so the corresponding results in Figure 4(a) are
similar.

(a) $D=10$

(b) $D=50$

Figure 4: The results corresponding to different kernel matrices. In this
experiments, we set $L=5$ for our MRBCD scheme.

Remark. Figures 3 and 4 show an interesting phenomenon — although there are
one hundred agent pairs in the system, our method converges quickly within 50
iterations and approaches the ground truth. One potential reason for this
phenomenon is that all dual variables can be updated based on few agent pairs,
i.e., considering $\\{(i,j)\\}_{i=1}^{I}$ for an arbitrary target agent $j$
and $\\{(i,j)\\}_{j=1}^{J}$ for an arbitrary source agent $i$. Note that,
estimating the EOT distance with few agent pairs is equivalent to estimating
the EOT distance with few pairwise costs. Following this direction, the work
in (Li et al., 2023) leverages the importance sparsification strategy to solve
the primal-form EOT problem with a sparse cost matrix. The theoretical
connection between our method and the importance sparsification is left as our
future work.

Figure 5: (a) The influence of communication protocol when computing
$W_{\varepsilon}(GMM_{1},GMM_{2})$. We set $L=2$ and $P=1000$ in this
experiment. (b) The comparison for i.i.d. and non-i.i.d. data storage methods
when computing $W_{\varepsilon}(GMM_{1},GMM_{2})$. We set $E=p\otimes
q=[\frac{1}{IJ}]$ and $P=1000$ in this experiment.

The influence of communication protocol. The communication protocol also
impacts our method, as shown in Theorem 4. In Figure 5, we apply our method
with three different communication protocols: $i)$ the ideal communication
protocol, i.e., $E=p\otimes q=[\frac{1}{IJ}]$, $ii)$ a sparse $E$, i.e., each
source agent only communicate with five target agents (50% zeros in $E$), and
$iii)$ a sparse and asymmetric $E$, i.e., setting the upper-triangular part of
the sparse $E$ to be all-zero (directed communication). Experimental results
show that the deterioration of the communication environment leads to
performance degradation.

The influence of non-i.i.d. data storage. In previous experiments, we randomly
scatter the samples to different agents. Accordingly, for the agents in the
same domain, their data are independent and identically distributed (i.i.d.).
In practice, however, the agents may store non-i.i.d. data. For example, given
two Gaussian mixture models, each of which contains five Gaussian components,
we $i)$ make each agent store the data randomly sampled from the GMMs (i.e.,
i.i.d. data storage) and $ii)$ make each agent store the data from a single
Gaussian component (i.e., non-i.i.d. data storage). As shown in Figure 5, the
non-i.i.d. data storage leads to the degradation of the performance — the gaps
between our results and the ground truth become more significant, and the
convergence curves are not stable. This phenomenon is because when computing
the stochastic gradients of the dual objective, we need to select $L$ agents’
dual variables randomly. In the non-i.i.d. case, the stochastic gradients we
get are not unbiased estimations of the full-batch gradients unless $L$ equals
the number of agents. As a result, compared to the i.i.d. case, we need to use
more agents to compute the gradients in the non-i.i.d. case. The results in
Figure 5 verify our analysis — increasing $L$ can improve the performance in
the non-i.i.d. case.

###  4.2 Real-world distributed domain adaptation

Besides testing on synthetic data, we apply our method to real-world
distributed domain adaptation tasks in which the data in the source and target
domains are scattered among different agents rather than stored in the same
server. Suppose we further protect the privacy of the target domain by
preventing the source domain from accessing the data of the target domain. The
problem is even more challenging in that case, and existing domain adaptation
methods become inapplicable.

We conduct this experiment on two widely-used image datasets, USPS and MNIST
(LeCun et al., 1998), each of which has ten image categories corresponding to
the digits from 0 to 9. We follow the setting in (Courty et al., 2017a). Given
2,000 images of the MNIST domain and 1,800 images of the USPS domain, we
consider the adaptation in two directions: USPS$\rightarrow$MNIST and
MNIST$\rightarrow$USPS. We focus on the OT-based domain adaptation strategy
(Courty et al., 2017b). This strategy $i)$ computes the (entropic) optimal
transport distance between the source and target domains, $ii)$ maps the
source samples to the target domain via the optimal coupling, and $iii)$
trains the 1-Nearest Neighbor (1NN) classifier based on the mapped data in a
distributed manner. To obtain the optimal coupling, we apply various methods,
including our MRBCD scheme with real or approximated kernel matrix, the earth
mover distance (EMD) for OT distance, the Sinkhorn algorithm for EOT distance,
and the OT-LpL1 method in (Courty et al., 2014).

Experimental results in Table 1 show that without the information of the
target domain, purely training a 1NN classifier leads to unsatisfactory
performance. The traditional centralized OT methods can improve classification
accuracy. Still, they require a powerful central server to compute the OT
distance and need to access the raw data of the target domain. Our MRBCD
scheme outperforms the baselines when using the real kernel and achieves
privacy preservation with tolerable performance degradation when using the
approximated kernel. In summary, our decentralized EOT has the potential to
distributed domain adaptation tasks in challenging privacy-preserving
scenarios.

Table 1: Comparisons on classification accuracy in distributed domain adaptation tasks Structure | Method | USPS | MNIST | Preserve
---|---|---|---|---
$\rightarrow$ MNIST |  $\rightarrow$ USPS | Privacy
Source only | 1NN | $0.385$ | $0.593$ | Yes
| EMD | $0.544$ | $0.617$ | No
Centralized | Sinkhorn | $0.437$ | $0.620$ | No
| OT-LpL1 | $0.490$ | $0.676$ | No
Decentralized |  MRBCDK | $0.580$ | $0.681$ | No
(Ours) |  MRBCD${}_{\widehat{K}}$ | $0.522$ | $0.629$ | Yes

##  5 Conclusion

In this study, we proposed a decentralized mini-batch randomized block-
coordinate descent scheme to approximate the EOT distance in a decentralized
scenario and analyzed the approximation error in theory. Our method is
privacy-preserving and communicate-efficient, which provides a potential
solution to the privacy-preserving distributed distribution comparison task.
In the future, we plan to accelerate our method based on the importance
sparsification and extend it to more challenging scenarios, e.g.,
approximating the decentralized EOT for continuous distributions and achieving
decentralized Gromov-Wasserstein distance.

## References

  * Agarwal & Duchi (2011) Agarwal, A. and Duchi, J. C.  Distributed delayed stochastic optimization.  In _NeurIPS_ , 2011.
  * Alistarh et al. (2017) Alistarh, D., Grubic, D., Li, J., Tomioka, R., and Vojnovic, M.  QSGD: Communication-efficient SGD via gradient quantization and encoding.  In _NeurIPS_ , 2017.
  * Altschuler et al. (2017) Altschuler, J., Weed, J., and Rigollet, P.  Near-linear time approximation algorithms for optimal transport via sinkhorn iteration.  In _NeurIPS_ , 2017.
  * Arablouei et al. (2015) Arablouei, R., Werner, S., Doğançay, K., and Huang, Y.-F.  Analysis of a reduced-communication diffusion LMS algorithm.  _Signal Processing_ , 117:355–361, 2015.
  * Arjovsky et al. (2017) Arjovsky, M., Chintala, S., and Bottou, L.  Wasserstein generative adversarial networks.  In _ICML_ , 2017.
  * Assran et al. (2020) Assran, M., Aytekin, A., Feyzmahdavian, H. R., Johansson, M., and Rabbat, M. G.  Advances in asynchronous parallel and distributed optimization.  _Proceedings of the IEEE_ , 108(11):2013–2031, 2020.
  * Basu et al. (2019) Basu, D., Data, D., Karakus, C., and Diggavi, S.  Qsparse-local-SGD: Distributed SGD with quantization, sparsification and local computations.  In _NeurIPS_ , 2019.
  * Benamou et al. (2015) Benamou, J.-D., Carlier, G., Cuturi, M., Nenna, L., and Peyré, G.  Iterative bregman projections for regularized transportation problems.  _SIAM Journal on Scientific Computing_ , 37(2):A1111–A1138, 2015.
  * Blondel et al. (2018) Blondel, M., Seguy, V., and Rolet, A.  Smooth and sparse optimal transport.  In _AISTATS_ , 2018.
  * Bond-Taylor et al. (2021) Bond-Taylor, S., Leach, A., Long, Y., and Willcocks, C. G.  Deep generative modelling: A comparative review of vaes, gans, normalizing flows, energy-based and autoregressive models.  _arXiv preprint arXiv:2103.04922_ , 2021.
  * Chang et al. (2015) Chang, T.-H., Hong, M., and Wang, X.  Multi-agent distributed optimization via inexact consensus ADMM.  _IEEE Transactions on Signal Processing_ , 63(2):482–497, 2015.
  * Chang et al. (2020) Chang, T.-H., Hong, M., Wai, H.-T., Zhang, X., and Lu, S.  Distributed learning in the nonconvex world: From batch data to streaming and beyond.  _IEEE Signal Processing Magazine_ , 37(3):26–38, 2020.
  * Chen et al. (2021) Chen, M., Shlezinger, N., Poor, H. V., Eldar, Y. C., and Cui, S.  Communication-efficient federated learning.  _Proceedings of the National Academy of Sciences_ , 118(17), 2021.
  * Chen et al. (2018) Chen, T., Giannakis, G., Sun, T., and Yin, W.  LAG: Lazily aggregated gradient for communication-efficient distributed learning.  In _NeurIPS_ , 2018.
  * Chizat et al. (2018) Chizat, L., Peyré, G., Schmitzer, B., and Vialard, F.-X.  Scaling algorithms for unbalanced optimal transport problems.  _Mathematics of Computation_ , 87(314):2563–2609, 2018.
  * Courty et al. (2014) Courty, N., Flamary, R., and Tuia, D.  Domain adaptation with regularized optimal transport.  In _ECML/EKDD_ , 2014.
  * Courty et al. (2017a) Courty, N., Flamary, R., Habrard, A., and Rakotomamonjy, A.  Joint distribution optimal transportation for domain adaptation.  In _NeurIPS_ , 2017a.
  * Courty et al. (2017b) Courty, N., Flamary, R., Tuia, D., and Rakotomamonjy, A.  Optimal transport for domain adaptation.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 39(9):1853–1865, 2017b.
  * Cuturi (2013) Cuturi, M.  Sinkhorn distances: Lightspeed computation of optimal transport.  In _NeurIPS_ , 2013.
  * Damodaran et al. (2018) Damodaran, B. B., Kellenberger, B., Flamary, R., Tuia, D., and Courty, N.  Deepjdot: Deep joint distribution optimal transport for unsupervised domain adaptation.  In _ECCV_ , 2018.
  * Dempe & Mehlitz (2015) Dempe, S. and Mehlitz, P.  Lipschitz continuity of the optimal value function in parametric optimization.  _Journal of Global Optimization_ , 61(2):363–377, 2015.
  * Deshpande et al. (2018) Deshpande, I., Zhang, Z., and Schwing, A. G.  Generative modeling using the sliced wasserstein distance.  In _CVPR_ , 2018.
  * Duchi et al. (2011) Duchi, J. C., Agarwal, A., and Wainwright, M. J.  Dual averaging for distributed optimization: Convergence analysis and network scaling.  _IEEE Transactions on Automatic Control_ , 57(3):592–606, 2011.
  * Dvurechenskii et al. (2018) Dvurechenskii, P., Dvinskikh, D., Gasnikov, A., Uribe, C., and Nedich, A.  Decentralize and randomize: Faster algorithm for Wasserstein barycenters.  In _NeurIPS_ , 2018.
  * Farahani et al. (2020) Farahani, A., Voghoei, S., Rasheed, K., and Arabnia, H. R.  A brief review of domain adaptation.  In _Advances in Data Science and Information Engineering_ , 2020.
  * Ganin & Lempitsky (2015) Ganin, Y. and Lempitsky, V.  Unsupervised domain adaptation by backpropagation.  In _ICML_ , 2015.
  * Genevay et al. (2016) Genevay, A., Cuturi, M., Peyré, G., and Bach, F.  Stochastic optimization for large-scale optimal transport.  In _NeurIPS_ , 2016.
  * Hammouda & Karray (2000) Hammouda, K. and Karray, F.  A comparative study of data clustering techniques.  _University of Waterloo, Ontario, Canada_ , 2000.
  * He et al. (2015) He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  _CoRR_ , abs/1512.03385, 2015.  URL http://arxiv.org/abs/1512.03385.
  * Hughes & Chen (2021) Hughes, J. and Chen, J.  Fair and distributed dynamic optimal transport for resource allocation over networks.  In _CISS_ , 2021.
  * Khanduri et al. (2021) Khanduri, P., Yang, H., Hong, M., Liu, J., Wai, H. T., and Liu, S.  Decentralized learning for overparameterized problems: A multi-agent kernel approximation approach.  In _ICLR_ , 2021.
  * LeCun et al. (1998) LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Li et al. (2023) Li, M., Yu, J., Xu, H., and Meng, C.  Efficient approximation of gromov-wasserstein distance using importance sparsification.  _Journal of Computational and Graphical Statistics_ , 0(ja):1–25, 2023.
  * Liu et al. (2019) Liu, Y., Xu, W., Wu, G., Tian, Z., and Ling, Q.  Communication-censored ADMM for decentralized consensus optimization.  _IEEE Transactions on Signal Processing_ , 67(10):2565–2579, 2019.
  * Lobel & Ozdaglar (2010) Lobel, I. and Ozdaglar, A.  Distributed subgradient methods for convex optimization over random networks.  _IEEE Transactions on Automatic Control_ , 56(6):1291–1306, 2010.
  * Lu & De Sa (2020) Lu, Y. and De Sa, C.  Moniqua: Modulo quantized communication in decentralized SGD.  In _ICML_ , 2020.
  * Lu & Xiao (2015) Lu, Z. and Xiao, L.  On the complexity analysis of randomized block-coordinate descent methods.  _Mathematical Programming_ , 152(1):615–642, 2015\.
  * Mao et al. (2020) Mao, X., Yuan, K., Hu, Y., Gu, Y., Sayed, A. H., and Yin, W.  Walkman: A communication-efficient random-walk algorithm for decentralized optimization.  _IEEE Transactions on Signal Processing_ , 68:2513–2528, 2020.
  * Mattei & Frellsen (2019) Mattei, P.-A. and Frellsen, J.  Miwae: Deep generative modelling and imputation of incomplete data sets.  In _ICML_ , 2019.
  * Nedic (2020) Nedic, A.  Distributed gradient methods for convex machine learning problems in networks: Distributed optimization.  _IEEE Signal Processing Magazine_ , 37(3):92–101, 2020.
  * Nedic & Ozdaglar (2009) Nedic, A. and Ozdaglar, A.  Distributed subgradient methods for multi-agent optimization.  _IEEE Transactions on Automatic Control_ , 54(1):48–61, 2009.
  * Nesterov (2012) Nesterov, Y.  Efficiency of coordinate descent methods on huge-scale optimization problems.  _SIAM Journal on Optimization_ , 22(2):341–362, 2012.
  * Peyré & Cuturi (2019) Peyré, G. and Cuturi, M.  Computational optimal transport.  _Foundations and Trends ® in Machine Learning_ , 11(5-6):355–607, 2019.
  * Richards et al. (2020) Richards, D., Rebeschini, P., and Rosasco, L.  Decentralised learning with random features and distributed gradient descent.  In _ICML_ , 2020.
  * Richtárik & Takáč (2014) Richtárik, P. and Takáč, M.  Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function.  _Mathematical Programming_ , 144(1):1–38, 2014\.
  * Schmitzer (2019) Schmitzer, B.  Stabilized sparse scaling algorithms for entropy regularized transport problems.  _SIAM Journal on Scientific Computing_ , 41(3):A1443–A1481, 2019.
  * Seguy et al. (2018) Seguy, V., Damodaran, B. B., Flamary, R., Courty, N., Rolet, A., and Blondel, M.  Large scale optimal transport and mapping estimation.  In _ICLR_ , 2018.
  * Shi et al. (2014) Shi, W., Ling, Q., Yuan, K., Wu, G., and Yin, W.  On the linear convergence of the ADMM in decentralized consensus optimization.  _IEEE Transactions on Signal Processing_ , 62(7):1750–1761, 2014.
  * Shi et al. (2015) Shi, W., Ling, Q., Wu, G., and Yin, W.  EXTRA: An exact first-order algorithm for decentralized consensus optimization.  _SIAM Journal on Optimization_ , 25(2):944–966, 2015.
  * Shi et al. (2020) Shi, Y., Yang, K., Jiang, T., Zhang, J., and Letaief, K. B.  Communication-efficient edge AI: Algorithms and systems.  _IEEE Communications Surveys & Tutorials_, 22(4):2167–2191, 2020.
  * Sinkhorn & Knopp (1967) Sinkhorn, R. and Knopp, P.  Concerning nonnegative matrices and doubly stochastic matrices.  _Pacific Journal of Mathematics_ , 21(2):343–348, 1967.
  * Smith et al. (2018) Smith, V., Forte, S., Chenxin, M., Takáč, M., Jordan, M. I., and Jaggi, M.  Cocoa: A general framework for communication-efficient distributed optimization.  _Journal of Machine Learning Research_ , 18:230, 2018.
  * Staib et al. (2017) Staib, M., Claici, S., Solomon, J. M., and Jegelka, S.  Parallel streaming Wasserstein barycenters.  In _NeurIPS_ , 2017.
  * Stich et al. (2018) Stich, S. U., Cordonnier, J.-B., and Jaggi, M.  Sparsified SGD with memory.  In _NeurIPS_ , 2018.
  * Tang et al. (2020) Tang, Z., Shi, S., and Chu, X.  Communication-efficient decentralized learning with sparsification and adaptive peer selection.  In _ICDCS_ , pp. 1207–1208, 2020.
  * Terelius et al. (2011) Terelius, H., Topcu, U., and Murray, R. M.  Decentralized multi-agent optimization via dual decomposition.  _IFAC Proceedings Volumes_ , 44(1):11245–11251, 2011.
  * Titouan et al. (2019) Titouan, V., Courty, N., Tavenard, R., and Flamary, R.  Optimal transport for structured data with application on graphs.  In _ICML_ , 2019.
  * Uribe et al. (2018) Uribe, C. A., Dvinskikh, D., Dvurechensky, P., Gasnikov, A., and Nedić, A.  Distributed computation of wasserstein barycenters over networks.  In _CDC_ , 2018.
  * Venkateswara et al. (2017) Venkateswara, H., Eusebio, J., Chakraborty, S., and Panchanathan, S.  Deep hashing network for unsupervised domain adaptation.  In _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2017.
  * Villani (2009) Villani, C.  _Optimal transport: old and new_ , volume 338.  2009\.
  * Wang & Banerjee (2014a) Wang, H. and Banerjee, A.  Bregman alternating direction method of multipliers.  In _NeurIPS_ , 2014a.
  * Wang & Banerjee (2014b) Wang, H. and Banerjee, A.  Randomized block coordinate descent for online and stochastic optimization.  _arXiv preprint arXiv:1407.0107_ , 2014b.
  * Xie et al. (2020) Xie, Y., Wang, X., Wang, R., and Zha, H.  A fast proximal point method for computing exact wasserstein distance.  In _UAI_ , 2020.
  * Xu et al. (2021) Xu, P., Wang, Y., Chen, X., and Tian, Z.  Coke: Communication-censored decentralized kernel learning.  _Journal of Machine Learning Research_ , 22(196):1–35, 2021.
  * Ye et al. (2017) Ye, J., Wu, P., Wang, J. Z., and Li, J.  Fast discrete distribution clustering using wasserstein barycenter with sparse support.  _IEEE Transactions on Signal Processing_ , 65(9):2317–2332, 2017.
  * Yuan et al. (2016) Yuan, K., Ling, Q., and Yin, W.  On the convergence of decentralized gradient descent.  _SIAM Journal on Optimization_ , 26(3):1835–1854, 2016.
  * Zhang et al. (2019) Zhang, M., Chen, L., Mokhtari, A., Hassani, H., and Karbasi, A.  Quantized frank-wolfe: Communication-efficient distributed optimization.  _arXiv preprint arXiv:1902.06332_ , 2019.
  * Zhang & Zhu (2019) Zhang, R. and Zhu, Q.  Consensus-based distributed discrete optimal transport for decentralized resource matching.  _IEEE Transactions on Signal and Information Processing over Networks_ , 5(3):511–524, 2019.
  * Zhao et al. (2014) Zhao, T., Yu, M., Wang, Y., Arora, R., and Liu, H.  Accelerated mini-batch randomized block coordinate descent method.  In _NeurIPS_ , 2014.
  * Zhu et al. (2016) Zhu, S., Hong, M., and Chen, B.  Quantized consensus ADMM for multi-agent distributed optimization.  In _ICASSP_ , 2016.

##  Appendix A Delayed Proofs

###  A.1 The proof of Theorem 1

###### Proof.

Let
$u_{1},v_{1}=\arg\sup_{u,v\in\mathcal{C}(\mathcal{X})}\mathbb{E}_{(i,j)\sim
E}[\mathbb{E}_{x\sim\mu_{i},y\sim\gamma_{j}}[f_{\varepsilon}(x,y,u,v)]]$ be
the optimal dual functions of $W_{\varepsilon}(\mu,\gamma)$. Similarly, let
$u_{2},v_{2}$ be the optimal dual functions of
$\widetilde{W}_{\varepsilon}(\mu,\gamma)$. We have

$\displaystyle\begin{aligned}
|\widetilde{W}_{\varepsilon}(\mu,\gamma)-W_{\varepsilon}(\mu,\gamma)|&\leq\begin{cases}\sum_{i,j}(e_{ij}-p_{i}q_{j})\mathbb{E}_{x\sim\mu_{i},y\sim\gamma_{j}}[f_{\varepsilon}(x,y,u_{1},v_{1})]&\text{if}~{}\widetilde{W}_{\varepsilon}(\mu,\gamma)\geq
W_{\varepsilon}(\mu,\gamma)\\\
\sum_{i,j}(p_{i}q_{j}-e_{ij})\mathbb{E}_{x\sim\mu_{i},y\sim\gamma_{j}}[f_{\varepsilon}(x,y,u_{2},v_{2})]&\text{if}~{}\widetilde{W}_{\varepsilon}(\mu,\gamma)<W_{\varepsilon}(\mu,\gamma)\\\
\end{cases}\\\
&\leq\sideset{}{{}_{i,j}}{\sum}|e_{ij}-p_{i}q_{j}|\sideset{}{{}_{u\in\\{u_{1},u_{2}\\},v\in\\{v_{1},v_{2}\\}}}{\max}\mathbb{E}_{x\sim\mu_{i},y\sim\gamma_{j}}[f_{\varepsilon}(x,y,u,v)]\\\
&\leq\sideset{}{{}_{i,j}}{\sum}|e_{ij}-p_{i}q_{j}|\sideset{}{{}_{u,v\in\mathcal{C}_{\mathcal{X}}}}{\sup}\mathbb{E}_{x\sim\mu_{i},y\sim\gamma_{j}}[f_{\varepsilon}(x,y,u,v)]\\\
&=\sideset{}{{}_{i,j}}{\sum}|e_{ij}-p_{i}q_{j}|W_{\varepsilon}(\mu_{i},\gamma_{j})\\\
&\leq\sideset{}{{}_{i,j}}{\max}W_{\varepsilon}(\mu_{i},\gamma_{j})\sideset{}{{}_{i,j}}{\sum}|e_{ij}-p_{i}q_{j}|\\\
&\leq\tau\sigma.\end{aligned}$

∎

###  A.2 The proof of Theorem 2

###### Proof.

The proof of this Theorem 2 is based on the Lemma 4.1 in (Khanduri et al.,
2021). We aims to approximately calculate a $N\times M$ kernel matrix $K$,
which can be considered as a sub-block matrix of the $(N+M)\times(N+M)$ full
kernel matrix base on given $N+M$ data samples. This full kernel matrix can be
denoted as $K_{full}\in{\mathbb{R}}^{(N+M)\times(N+M)}$. The employed privacy-
preserving Kernel Approximation algorithm, i.e., Algorithm 1, can be
considered as a partial version of the Algorithm 1 in (Khanduri et al., 2021).
As a result, we can utilize the theoretical result, i.e., Lemma 4.1 in
(Khanduri et al., 2021) to estimate the approximate level of
$\widehat{K}_{full}\in{\mathbb{R}}^{(N+M)\times(N+M)}$ obtained through the
Algorithm 1 in (Khanduri et al., 2021). Based on the assumptions 1-2, with
probability at least $1-\delta$, we have

$\|K_{full}-\widehat{K}_{full}\|\leq
G(N+M)\Bigl{(}\sqrt{\frac{32\pi^{2}}{P}\log\frac{2(N+M)}{\delta}}+\frac{8\pi}{3P}\log\frac{2(N+M)}{\delta}\Bigr{)}.$

For the reason that $K$ is a sub-block matrix of $K_{full}$, so as the
approximated $\widehat{K}$ with respect to $\widehat{K}_{full}$, Furthermore,
based on the assumptions 1-2, with probability at least $1-\delta$, we have

$\|K-\widehat{K}\|\leq\|K_{full}-\widehat{K}_{full}\|\leq
G(N+M)\Bigl{(}\sqrt{\frac{32\pi^{2}}{P}\log\frac{2(N+M)}{\delta}}+\frac{8\pi}{3P}\log\frac{2(N+M)}{\delta}\Bigr{)},$

which indicates the result of this Theorem. ∎

###  A.3 The proof of Theorem 4

###### Proof.

Let $\hat{u}^{*},\hat{u}^{*}=\arg\max_{u,v}F_{\varepsilon}(u,v;\widehat{K},E)$
be the optimal solution of the problem equation 8 given approximated kernel
$\widehat{K}$, and
$\tilde{u}^{*},\tilde{u}^{*}=\arg\max_{u,v}F_{\varepsilon}(u,v;K,E)$ be the
optimal solution of the problem equation 8 given real kernel $K$. In order to
prove equation 15, we first establish the connections with the algorithmic
convergence error, the approximated kernel error and the mismatch between the
storage and communication protocols. In particular, applying the triangle
inequality, we have

$\displaystyle\begin{aligned}
&\mathbb{E}\left[\big{|}F_{\varepsilon}(\hat{u}^{t},\hat{v}^{t};\widehat{K},E)-W_{\varepsilon}(\mu,\gamma)\big{|}\right]\\\
\leq&\mathbb{E}\left[\big{|}F_{\varepsilon}(\hat{u}^{t},\hat{v}^{t};\widehat{K},E)-F_{\varepsilon}(\hat{u}^{*},\hat{v}^{*};\widehat{K},E)\big{|}\right]+\big{|}F_{\varepsilon}(\hat{u}^{*},\hat{v}^{*};\widehat{K},E)-F_{\varepsilon}(\tilde{u}^{*},\tilde{v}^{*};K,E)\big{|}\\\
&+\big{|}F_{\varepsilon}(\tilde{u}^{*},\tilde{v}^{*};K,E)-W_{\varepsilon}(\mu,\gamma)\big{|}\\\
=&\mathbb{E}\big{[}\underbrace{\big{|}F_{\varepsilon}(\hat{u}^{t},\hat{v}^{t};\widehat{K},E)-F_{\varepsilon}(\hat{u}^{*},\hat{v}^{*};\widehat{K},E)\big{|}}_{\hbox{convergence
error by Lemma~{}\ref{le:algorithm-
error}}}\big{]}+\underbrace{\big{|}F_{\varepsilon}(\hat{u}^{*},\hat{v}^{*};\widehat{K},E)-F_{\varepsilon}(\tilde{u}^{*},\tilde{v}^{*};K,E)\big{|}}_{\hbox{approximated
kernel error}}\\\
&+\underbrace{\big{|}\widetilde{W}_{\varepsilon}(\mu,\gamma)-W_{\varepsilon}(\mu,\gamma)\big{|}}_{\hbox{gap
by Theorem~{}\ref{thm:approx_error}}}.\end{aligned}$

The first and third terms in the above equation have been analyzed in Lemma 3
and Theorem 1 respectively. The key issue is to analyze the approximated
kernel error term.

Each $f_{\varepsilon}(x,y,u,v)$ is typically convex and Lipschitz continuous
with respect to $(u,v)$ Genevay et al. (2016). The objective function
$F_{\varepsilon}$ is Lipschitz continuous with respect to $(u,v)$. Further
based on the definition of $f_{\varepsilon}^{(i,j)}$, it is obvious that
$f_{\varepsilon}^{(i,j)}$ is a liner function with respect to
$\kappa(x_{n}^{(i)},y_{m}^{(j)})$. On the whole, the objective function
$F_{\varepsilon}$ can be considered as a linear function with respect to
kernel matrix $K$ and thus also is Lipschitz continuous with respect to $K$.
According to Dempe & Mehlitz (2015)[Lemma 3.1], if we model $K$ as the varible
of the parametric optimization problem

$\phi(K)=\max_{u,v}F_{\varepsilon}\big{(}u,v;K,E\big{)}.$

We can conclude that the optimal value function $\phi\big{(}K\big{)}$ with
respect to $K$ is $L_{\kappa}$-Lipschitz continuous, i.e.,

$\big{|}F_{\varepsilon}(\hat{u}^{*},\hat{v}^{*};\widehat{K},E)-F_{\varepsilon}(\tilde{u}^{*},\tilde{v}^{*};K,E)\big{|}=\big{|}\phi(\widehat{K})-\phi(K)\big{|}\leq
L_{\kappa}\big{\|}\widehat{K}-K\big{\|}.$

As a consequence of Theorem 1, Theorem 2, and Lemma 3, we have that for the
problem in equation 8 with the kernel $\widehat{K}$ derived by Algorithm 1,
let $\left\\{\left(u^{t},v^{t}\right)\right\\}$ be the sequence generated by
Algorithm 2. Define $\hat{u}^{t}=\frac{1}{t}\sum_{\ell=1}^{t}u^{\ell}$, and
$\hat{v}^{t}=\frac{1}{t}\sum_{\ell=1}^{t}v^{\ell}$. Based on the assumptions
1-3, with probability at least $1-\delta$, we have

$\displaystyle\begin{aligned}
&\mathbb{E}|F_{\varepsilon}(\hat{u}^{t},\hat{v}^{t};\widehat{K},E)-W_{\varepsilon}(\mu,\gamma)|\\\
\leq&\mathcal{O}\Bigl{(}\frac{IJ\left((\sqrt{t}+L_{F_{\varepsilon}})R_{0}^{2}+\sqrt{t}R^{2}\right)}{t}\Bigr{)}+L_{\kappa}G(N+M)\Bigl{(}\sqrt{\frac{32\pi^{2}}{P}\log\frac{2(N+M)}{\delta}}+\frac{8\pi}{3P}\log\frac{2(N+M)}{\delta}\Bigr{)}\\\
&+\tau\sigma\\\
\leq&\mathcal{O}\Bigl{(}\frac{IJ}{\sqrt{t}}+(N+M)\sqrt{\frac{1}{P}\log\frac{2(N+M)}{\delta}}+\sigma\Bigr{)}.\end{aligned}$
(16)

To emphasis, the second term in equation 16 has close relationship with the
number of samples per agent (i.e., $N_{i}$ and $M_{j}$). We propose a worst
case analysis, while it can be modified properly with well-designed $N_{i}$
and $M_{j}$.

∎

(a) $W_{\varepsilon}(\mathcal{N}_{1},\mathcal{N}_{2})$ (b)
$W_{\varepsilon}(GMM_{1},GMM_{2})$

Figure 6: The influence of the number of servers in each domain.

(a) $L=2$ (b) $L=5$ (c) $L=5$

Figure 7: (a, b) The robustness of our method to the communication protocol
when computing $W_{\varepsilon}(\mathcal{N}_{1},\mathcal{N}_{2})$. (c) The
influence of communication protocol when computing
$W_{\varepsilon}(GMM_{1},GMM_{2})$. In this experiment, we set $L=5$ and
$P=1000$.

##  Appendix B Implementation Details and More Experimental Results

###  B.1 Synthetic experiments

In order to gain insight into the effect of the number of servers on the
algorithm, we set $I,J\in\\{5,10,20\\}$, $L=\text{round}(0.7I)$, and the
number of samples to be $N=M=2000$. From the experimental results showed in
Figure 6, we can find that as the number of servers increases, convergence is
faster at the beginning of the iteration and is accompanied by a more
pronounced oscillation.

Additionally, Figure 7 shows more experimental results, visualizing the
impacts of different communication protocols.

###  B.2 Real-world experiments

Table 2: Summary of the domains used in the experiments Problem | Domains | Datasets | #Samples | #Features | Abbr.
---|---|---|---|---|---
Digits | USPS | USPS | $1,800$ | $256$ | U
| MNIST | MNIST | $2,000$ | $256$ | M
Objects | Art | Office-home | $2,427$ | $2,048$ | Ar
| Clipart | Office-home | $4,365$ | $2,048$ | Cl
| Product | Office-home | $4,439$ | $2,048$ | Pr
| Real-World | Office-home | $4,357$ | $2,048$ | Rw
Table 3: Comparisons on classification accuracy in distributed domain adaptation tasks Domains | Source only |  | Centralized |  | Decentralized (Ours)
---|---|---|---|---|---
1NN | EMD | Sinkhorn | OT-LpL1 |  MRBCDK |  MRBCD${}_{\widehat{K}}$
Ar$\rightarrow$Cl | $0.433$ | $0.471$ | $0.492$ | $0.490$ | $0.483$ | $0.458$
Ar$\rightarrow$Pr | $0.594$ | $0.642$ | $0.673$ | $0.633$ | $0.665$ | $0.639$
Ar$\rightarrow$Rw | $0.667$ | $0.677$ | $0.721$ | $0.686$ | $0.738$ | $0.705$
Cl$\rightarrow$Ar | $0.445$ | $0.504$ | $0.509$ | $0.478$ | $0.531$ | $0.509$
Cl$\rightarrow$Pr | $0.536$ | $0.647$ | $0.617$ | $0.642$ | $0.632$ | $0.606$
Cl$\rightarrow$Rw | $0.589$ | $0.638$ | $0.657$ | $0.664$ | $0.654$ | $0.618$
Pr$\rightarrow$Ar | $0.488$ | $0.516$ | $0.532$ | $0.494$ | $0.538$ | $0.506$
Pr$\rightarrow$Cl | $0.414$ | $0.455$ | $0.465$ | $0.450$ | $0.469$ | $0.425$
Pr$\rightarrow$Rw | $0.683$ | $0.707$ | $0.725$ | $0.714$ | $0.735$ | $0.704$
Rw$\rightarrow$Ar | $0.592$ | $0.611$ | $0.622$ | $0.605$ | $0.621$ | $0.598$
Rw$\rightarrow$Cl | $0.450$ | $0.498$ | $0.505$ | $0.509$ | $0.494$ | $0.463$
Rw$\rightarrow$Pr | $0.729$ | $0.749$ | $0.778$ | $0.770$ | $0.773$ | $0.736$

The distributed domain adaptation task is dedicated to solving the domain
adaptation problem in the case where both source and target domain data are
scattered over different agents. The aim is to use the label information
available in the source domain $\mathcal{X}$ to learn a classifier $f^{*}$
that can be applied on the target domain $\mathcal{Y}$ without label
information. Specifically, suppose we have the source domain data
$X_{i}=\\{x_{n}^{(i)}\\}_{n=1}^{N_{i}}$ associated with the class labels, and
the target domain data $Y_{j}=\\{y_{m}^{(j)}\\}_{m=1}^{M_{j}}$ with unknown
labels. Based on our algorithm MRBCD, each target agent $j$ can obtain an
optimal coupling $\\{\Pi_{ij}\\}_{i=1}^{I}$. Then, according to (Courty et
al., 2017a), when the probability measures $\mu$ and $\gamma$ are uniform, we
can derive the barycentric mapping as $\widehat{X}=N\Pi Y$, where
$\Pi=[\Pi_{ij}]$ is the complete coupling and $\widehat{X}$ is the transported
data of the source domain. Eventually, we can train the 1NN classifier $f$
given the transported data $\widehat{X}$ and perform classification prediction
on the target domain data.

We further conduct experiments on the object recognition task. Here, we use
the Office-home dataset (Venkateswara et al., 2017). A summary of the
properties of each domain used in this paper is provided in Table2. The
Office-home dataset contains around 15500 images coming from four different
domains: Art (artistic images in the form of sketches, paintings, etc),
Clipart (collection of clipart images), Product (images of objects without a
background) and RealWorld (images of objects captured with a regular camera).
For this problem, all the experiments are based on pre-trained ResNet-50 (He
et al., 2015). We consider 12 transfer tasks for the Art (Ar), Clipart (Cl),
Product (Pr) and Real-World (Rw) domains for all combinations of source and
target for the 4 domains. The results are shown in the Table3.

Hyperparameter setting. As for the experimental setup, we scattered the source
and target domain data over four agents and set $L=7$ and $P=10000$. For all
the EOT-based method, we apply grid search, finding the optimal weight of
regularizer $\varepsilon\in\\{2,1,0.5,0.1,0.05\\}$. For our method, the
learning rate is set in $\\{1,0.5,0.1,0.01,0.001\\}$.