# Investigation of Alternative Measures for Mutual Information

Bulut Kuskonmaz  Jaron S. Gundersen  Rafal Wisniewski  Department of
Electronical Systems, Aalborg University, Aalborg, Denmark (e-mails:
$\\{$bku,jaron,raf$\\}$@es.aau.dk).

###### Abstract

Mutual information $I(X;Y)$ is a useful definition in information theory to
estimate how much information the random variable $Y$ holds about the random
variable $X$. One way to define the mutual information is by comparing the
joint distribution of $X$ and $Y$ with the product of the marginals through
the KL-divergence. If the two distributions are close to each other there will
be almost no leakage of $X$ from $Y$ since the two variables are close to
being independent. In the discrete setting the mutual information has the nice
interpretation of how many bits $Y$ reveals about $X$ and if $I(X;Y)=H(X)$
(the Shannon entropy of $X$) then $X$ is completely revealed. However, in the
continuous case we do not have the same reasoning. For instance the mutual
information can be infinite in the continuous case. This fact enables us to
try different metrics or divergences to define the mutual information. In this
paper, we are evaluating different metrics or divergences such as Kullback-
Leibler (KL) divergence, Wasserstein distance, Jensen-Shannon divergence and
total variation distance to form alternatives to the mutual information in the
continuous case. We deploy different methods to estimate or bound these
metrics and divergences and evaluate their performances.

###### keywords:

Mutual information, information leakage, metric/divergence.

##  1 Introduction

Mutual information has been used as a measure of privacy leakage in several
contexts. It dates back to the introduction of information theory in Shannon
(1948) where it was introduced through the Shannon entropy. Afterwards, it has
been used to measure leakage in several contexts such as multiparty
computation, differential privacy, and machine learning Cristiani et al.
(2020); Farokhi and Kaafar (2020); Sankar et al. (2013); Urrutia (2018); Cuff
and Yu (2016); Li et al. (2021). In this paper we focus mainly on the use of
mutual information in privacy-preserving distributed computations, such as for
instance multiparty computation. Even though you want to compute on real
numbers, a multiparty computation protocol is usually converted into finite
field operations, and hence the mutual information is between two discrete
random variables. However, Tjell and Wisniewski (2021) suggest secret sharing
scheme over the real numbers. With this secret sharing scheme the multiparty
computation can be carried out directly in the real numbers which gives the
advantage that some real number computations (for example division) are easier
to carry out. The drawback of this is that a share might leak a small amount
of information, but as described in the paper the amount can be very limited.
In any case, this gives rise to study and investigate different ways to
measure the leakage in the continuous case as well. We give more details about
how mutual information is used to measure leakage in multiparty computation in
Section 3.

The interpretation of the mutual information $I(X;Y)$ in the discrete case is
how many bits $Y$ on average reveals about $X$ and hence if we want to keep
$X$ private we want this mutual information to be small if someone can/will
get access to $Y$. However, this bit interpretation goes out of the window
when the random variables are continuous random variables (since we need an
infinite number of bits to describe a real number). Therefore, in the
continuous case there might be other alternatives which are just as good as
mutual information to measure information leakage. For instance, if we define
the mutual information through the KL divergence we measure the difference
between the joint distribution of $X$ and $Y$ and the product of the
marginals. Intuitively, this makes sense since if $X$ and $Y$ are independent
the product of the marginals and the joint coincide meaning no difference and
hence mutual information is equal to zero. A large difference means dependency
and hence $Y$ tells more about $X$.

However, there could be other alternatives which can be just as good as the KL
divergence. For instance several other measures of distances between
probability distributions exist such as Jensen-Shannon divergence,
Wasserstein/Earth mover distance, or Total variation distance. In this paper
we define these alternatives for mutual information (Section 2), consider
different ways to estimate them from samples (Section 3), and evaluate the
performance of the estimators (Section 4).

##  2 Preliminaries

Let $\mathcal{X}$ be a probability space with $\sigma$-algebra $\mathcal{E}$
and measure $P$. We consider two random variables $X$ and $Y$ on this space,
i.e. $X,Y\colon\mathcal{X}\to\mathbb{R}^{d}$. We equip the measurable space
$\mathbb{R}^{d}$ with the Borel $\sigma$-algebra $\mathcal{B}$ and Lebesgue
measure $\lambda$. The measure on $\mathbb{R}^{d}$ induced by $X$ given by
$P(X^{-1}(B))$ for all $B\in\mathcal{B}$ is called the distribution $P_{X}$
(similarly for $Y$) and the probability density function (pdf) $p(x)$ if it
exists is defined to be the function satisfying

$P(X^{-1}(B))=\int_{B}p(x)d\lambda(x)$ (1)

for all $B\in\mathcal{B}$, also known as the Radon-Nikodym derivative
$p(x)=\frac{dP_{X}}{d\lambda}$. Hence, we remark that we will use the
following two equivalent notations for integrals

$\int_{\mathcal{X}}dP_{X}=\int_{\mathbb{R}^{d}}p(x)d\lambda(x).$ (2)

###  2.1 Definition of Mutual Information and Alternatives

Now, we present the definitions of the different divergences/metrics and we
start with the original definition of mutual information from the KL
divergence.111We remark that the mutual information can also be defined using
the differential entropy but this is equivalent to the KL-definition.

###### Definition

Let $P$ and $Q$ be two probability distributions, where $P$ is absolutely
continuous with respect to $Q$. The Kullback-Leibler (KL) divergence between
them is defined as

$\displaystyle D_{KL}(P\parallel Q)$
$\displaystyle=\int_{\mathcal{X}}\log\left(\frac{dP}{dQ}\right)dP$ (3)
$\displaystyle=\int_{\mathbb{R}^{d}}p(x)\log\left(\frac{p(x)}{q(x)}\right)d\lambda(x),$
(4)

where $\frac{dP}{dQ}$ is the Radon-Nikodym derivative and the last equality
holds if the pdf’s $p(x)$ and $q(x)$ exists.

###### Definition

Let $X\colon\mathcal{X}\to\mathbb{R}^{d}$ and
$Y\colon\mathcal{Y}\to\mathbb{R}^{m}$ be two continuous random variables with
distributions $P_{X}$ and $P_{Y}$ respectively. If $P_{(X,Y)}$ is the joint
distribution of $X$ and $Y$, then the mutual information between $X$ and $Y$
is given by

$I_{KL}(X;Y)=D_{KL}(P_{(X,Y)}\parallel P_{X}\otimes P_{Y}).$ (5)

As we can see, the mutual information is a comparison (using the KL-
divergence) of the joint distribution with the product of the marginals.
However, as described in the introduction we can also make this comparison
using other divergences/metrics on probability measures. We will introduce
some of these below. We first look at some other divergences, which similar to
the KL-divergence is a special class of divergences called $f$-divergences
Rényi (1961). An $f$-divergence between two probability distributions $P$ and
$Q$, where $P$ is absolutely continuous with respect to $Q$, is defined as

$D_{f}(P\parallel Q)=\int_{\mathcal{X}}f\left(\frac{dP}{dQ}\right)dQ,$ (6)

and if both $P$ and $Q$ are absolutely continuous with respect to the Lebesgue
measure $\lambda$ we have the densities satisfying $dP=p(x)d\lambda(x)$ and
$dQ=q(x)d\lambda(x)$ implying that we can write

$D_{f}(P\parallel
Q)=\int_{\mathbb{R}^{d}}f\left(\frac{p(x)}{q(x)}\right)q(x)d\lambda(x).$ (7)

With this notation the KL-divergence is an $f$-divergence with
$f(t)=t\log(t)$.

###### Definition

Let $P$ and $Q$ be two probability distributions. The Jensen-Shannon (JS)
divergence of $P$ and $Q$ is an $f$-divergence with
$f(t)=\frac{1}{2}\left((t+1)\log(\frac{2}{t+1})+t\log(t)\right)$.

From this, it can be deduced that

$\displaystyle D_{JS}(P\parallel Q)=$
$\displaystyle\frac{1}{2}D_{KL}(P\parallel\frac{P+Q}{2})+\frac{1}{2}D_{KL}(Q\parallel\frac{P+Q}{2})$
(8) $\displaystyle=$
$\displaystyle\frac{1}{2}\int_{\mathbb{R^{d}}}p(x)\log\left(\frac{2p(x)}{p(x)+q(x)}\right)$
$\displaystyle+q(x)\log\left(\frac{2q(x)}{p(x)+q(x)}\right)d\lambda(x),$

and we remark, that the JS divergence is a symmetric version of the KL
divergence.

###### Definition

Let $P$ and $Q$ be two probability distributions. The Total variation (TV)
divergence between them is an $f$-divergence with $f(t)=\frac{1}{2}|t-1|$.

Again, this shows that

$\displaystyle D_{TV}(P\parallel Q)$
$\displaystyle=\frac{1}{2}\int_{\mathcal{X}}|dP-dQ|$ (9)
$\displaystyle=\frac{1}{2}\int_{\mathbb{R}^{d}}|p(x)-q(x)|d\lambda(x).$

Intuitively, it makes sense to compare how much the two densities differ from
each other throughout the whole domain. But on the other hand, the total
variation can sometimes be a too strong metric.

As an alternative to the $f$-divergences we also consider a metric of
probability measures, namely the Wasserstein distance.

###### Definition

Let $P$ and $Q$ be two probability measures on a metric space and let $d(x,y)$
be a metric on this space. Then the $k$’th Wasserstein distance is

$W_{k}(P,Q)=\inf_{\gamma\in\Gamma(P,Q)}\left(\int_{\mathcal{X}\times\mathcal{X}}d(x,y)^{k}d\gamma(x,y)\right)^{\frac{1}{k}}$
(10)

where $\Gamma(P,Q)$ is the set of all couplings of $P$ and $Q$, i.e. the set
of measures having $P$ and $Q$ as the marginals.

One can see $\gamma$ as a transportation plan for transforming $P$ into $Q$.
Therefore, $W_{1}(P,Q)$ is also known as the earth mover distance since it
measures the cost of “moving the mass” from $P$ to $Q$. Since $W_{1}$ has the
earth mover interpretation this will be the one we are focusing on the most in
this paper.

In fact, both the $W_{1}$ and the TV distance can be described as an integral
probability metric (IPM) Müller (1997).

###### Definition

For two probability measures ${P}$ and $Q$ on a measurable space
$\mathcal{X}$, IPM is given by

$\gamma(\mathcal{F},P,Q)=\sup_{f\in\mathcal{F}}{\int f(x)dP(x)-\int
f(y)dQ(y)}$ (11)

where $\mathcal{F}$ is a space for measurable functions on $\mathcal{X}$.

For different $\mathcal{F}$ we obtain different metrics. In fact, the
Rubenstein-Kantorovich duality shows that the
Wasserstein-1 distance can be captured as an IPM

$\displaystyle\gamma(\mathcal{L}_{M},P,Q)$
$\displaystyle=\sup_{f\in\mathcal{L}_{M}}{\int f(x)d{P}(x)-\int f(y)d{Q}(y)}$
(12) $\displaystyle=W_{1}({P},{Q})$

where $\mathcal{L}_{M}$ is the set of all functions that are 1-Lipschitz
functions Villani (2009). Similarly, we can capture the TV by setting
$\mathcal{F}_{TV}=\left\\{f\mid\|f\|_{\infty}\leq\frac{1}{2}\right\\}$ 222We
choose $\frac{1}{2}$ ($\beta-\alpha=1$) as our bound so that we can have
correspondence with our definition for total variation in eq. (9) referring to
Theorem 2 in Sriperumbudur et al. (2009) where
$\|f\|_{\infty}=\sup_{x\in\mathcal{X}}|f(x)|$.

To measure information leakage we compare the joint distribution with the
product of the marginals of two random variables $X$ and $Y$, like in (5).
Since the other divergences/metrics can be used as alternatives for measuring
the information leakage we will use a mutual information-like notation. Hence,
we write $I_{JS}(X;Y)$, $I_{TV}(X;Y)$, and $I_{W_{k}}(X;Y)$ when we do the
same comparison as in (5) but with another divergence/metric.

###  2.2 Relation Between Different Measures

Many of the divergences are related to each other as for instance it is seen
in (8) where the JS divergence can be defined from the KL divergence. But
beside this there exists several bounds on the different divergences. We will
present some of these here but refer the reader to Sason and Verdú (2016) for
more theory about this. First, we relate the JS and the TV divergences. The
following relations holds when the base of the logarithm used in the JS
divergence is base $2$

$0\leq D_{JS}(P\parallel Q)\leq D_{TV}(P\parallel Q)\leq 1.$ (13)

We can also relate the TV divergence to the KL divergence with the following
upper bounds on $D_{TV}$

$D_{TV}(P\parallel Q)\leq\sqrt{\frac{1}{2}D_{KL}(P\parallel Q)}$ (14)
$D_{TV}(P\parallel Q)\leq\sqrt{1-e^{-D_{KL}(P\parallel Q)}}.$ (15)

Furthermore, the Wasserstein-1 distance is related to the TV divergence by the
following bounds

$\displaystyle W_{1}(P,Q)$ $\displaystyle\geq D_{TV}(P\parallel Q)\cdot
d_{min}$ (16) $\displaystyle W_{1}(P,Q)$
$\displaystyle\leq\mathrm{diam}(\mathcal{X})D_{TV}(P\parallel Q),$

where $d_{min}=\inf_{x\neq y}\\{d(x,y)\\}$ for $x,y\in\mathcal{X}$ and
$\mathrm{diam}(\mathcal{X})=\sup_{x,y\in\mathcal{X}}\\{d(x,y)\\}$. We remark
that the bounds on the Wasserstein distance is not very useful for instance if
$\mathcal{X}=\mathbb{R}^{d}$ and we are using the Euclidean distance since
$d_{min}=0$ and $\mathrm{diam}(\mathcal{X})=\infty$ in this case. However, if
$\mathcal{X}$ a bounded set then $\mathrm{diam}(\mathcal{X})<\infty$.
Furthermore, we remark that if we use the discrete metric

$d(x,y)=\begin{cases}1\text{ if }x\neq y\\\ 0\text{ if }x=y\end{cases}$ (17)

then the inequalities actually show that the total variation and the
Wasserstein distance are equivalent. Hence, we can consider the total
variation as a special case of the Wasserstein-1 distance where we use the
discrete metric in the Wasserstein. However, we will stick to the Euclidean
norm for the Wasserstein distance in this paper.

We also mention, that increasing the $k$ in the Wasserstein distance will
increase the distance, i.e. $W_{k_{1}}(P,Q)\leq W_{k_{2}}(P,Q)$ when
$k_{1}\leq k_{2}$ Villani (2009).

##  3 Mutual information as leakage measure in multiparty computation

In multiparty computation $n$ parties would like to compute
$f(x_{1},\ldots,x_{n})$ where $x_{i}$ is held by the $i$’th party. The
computation needs to be secure even in the presence of an adversary corrupting
a number of the parties. This means for instance that the adversary is not
allowed to learn more than it will learn from the input of the corrupted
parties and the output $f(x_{1},\ldots,x_{n})$. The security is usually proven
through a simulation proof but the privacy requirement can also be stated via
mutual information in the following way

$I(X_{i};\mathrm{View}_{\mathcal{A}})=I(X_{i};f(X_{1},\ldots,X_{n}),\\{X_{j}\\}_{j\in\mathcal{A}})$
(18)

where $\mathrm{View}_{\mathcal{A}}$ is everything the adversary $\mathcal{A}$
sees through the algorithm. Some privacy-preserving algorithms do not
guarantee the equality in (18) but instead they ensure that the leakage is
small meaning that $I(X_{i};\mathrm{View}_{\mathcal{A}})$ is not much higher
than $I(X_{i};f(X_{1},\ldots,X_{n}),\\{X_{j}\\}_{j\in\mathcal{A}})$. Hence, it
is interesting to be able to compute $I(X_{i};\mathrm{View}_{\mathcal{A}})$
but the density of $\mathrm{View}_{\mathcal{A}}$ might not always be known
which makes it difficult for computation. Hence, approximating this mutual
information is interesting from a multiparty computation perspective.

Thus, we present different ways to approximate the different
metrics/divergences defined in Section 2.1 on probability distributions $P$
and $Q$ in the following sections. The approximations are based on samples
$\mathbf{X}=\\{x_{i}\\}_{i=1}^{N}$ from a random variable $X$ having
distribution $P$ and density $p(x)$ and samples
$\mathbf{Y}=\\{y_{i}\\}_{i=1}^{N}$ from a random variable $Y$ having
distribution $Q$ and density $q(y)$. Often in practice $p$ and $q$ are not
known so we compute approximations of them.

###  3.1 Leakage Estimation via Histograms

In this section we give a general way to approximate the pdf’s using
histograms. We build up histograms by splitting the domain into $K$ bins and
count the number of instances in each bins. I.e. the domain equals
$\bigcup_{i=1}^{K}B_{i}$ where $B_{i}\cap B_{j}=\emptyset$ when $i\neq j$.
This gives rise to an approximate pdf of $p$, where we let $n_{p,i}$ be the
number of instances in bin $B_{i}$ from the samples of $X$;

$\hat{p}(x)=\sum_{i=1}^{K}\mathds{1}_{x\in
B_{i}}\frac{n_{p,i}}{N\cdot\lambda(B_{i})},$ (19)

where $\mathds{1}_{x\in B_{i}}$ is the indicator function for $x$ in $B_{i}$.
We remark that the $B_{i}$’s are disjoint and hence for each $x$ exactly one
of the terms in the sum is nonzero. Hence,
$\hat{p}(x)=\frac{n_{p,i}}{N\cdot\lambda(B_{i})}$ if $x\in B_{i}$. Since all
the divergences we look at are $f$-divergences, they can be described as an
integral with respect to the Lebesgue measure of some function of the pdf’s,
i.e. $f(p(x),q(x))$. Hence, we can split the interval up in a sum of intervals
where we integrate over a constant. It means that

$\displaystyle\int_{\mathbb{R}^{d}}f(p(x),q(x))d\lambda(x)=\sum_{i=1}^{K}\int_{B_{i}}f(p(x),q(x))d\lambda(x)$
(20)
$\displaystyle\approx\sum_{i=1}^{K}\int_{B_{i}}f(\hat{p}(x),\hat{q}(x))d\lambda(x)=\sum_{i=1}^{K}\mathrm{\lambda}(B_{i})c_{i},$

where the last equality follows from the fact that $\hat{p}(x)$ and
$\hat{q}(x)$ is constant inside bin $B_{i}$ and hence
$f(\hat{p}(x),\hat{q}(x))=c_{i}$ is constant inside this bin. This implies the
following approximations of the different divergences.

$\displaystyle\begin{aligned} D_{KL,hist}(P\parallel
Q)=&\sum_{i=1}^{K}\frac{n_{p,i}}{N}\log\left(\frac{n_{p,i}}{n_{q,i}}\right)\\\
D_{TV,hist}(P\parallel
Q)=&\frac{1}{2}\sum_{i=1}^{K}\left|\frac{n_{p,i}}{N}-\frac{n_{q,i}}{N}\right|\\\
D_{JS,hist}(P\parallel
Q)=&\frac{1}{2}\left(\sum_{i=1}^{K}\frac{n_{p,i}}{N}\log\left(\frac{2n_{p,i}}{n_{q,i}+n_{p,i}}\right)\right.\\\
&+\left.\frac{n_{q,i}}{N}\log\left(\frac{2n_{q,i}}{n_{q,i}+n_{p,i}}\right)\right).\end{aligned}$
(21)

We can also use (22) to approximate $W_{1}$ using the histogram method. We
describe this through optimal transport below.

###  3.2 Wasserstein Distance Via Optimal Transport

Optimal transport is often formulated in a discrete setting, so we start by
considering the optimal transport between two discrete distributions. Hence,
we consider a situation where we have $p(x)$ and $q(y)$ and they can be
described by two vectors $\mathbf{p}$ and $\mathbf{q}$ where the entries are
the probabilities for the different outcomes and hence the entries in
$\mathbf{p}$ (and $\mathbf{q}$) sum to $1$. Optimal transport describes the
cost (how far the mass needs to be moved and how much mass) of transporting
$p(x)$ to $q(y)$.

The solution to the optimal transportation problem between $\mathbf{p}$ and
$\mathbf{q}$ (and hence the distributions) is nothing but a matrix
$[M_{ij}]_{i,j=1}^{N}\in\mathbb{R}_{+}^{N\times N}$ where the element $M_{ij}$
represents the amount of mass transported from $p_{i}$ to $q_{j}$. In order to
find the optimal transportation plan $M$ using the cost function $C$, one can
form linear program as

$\displaystyle d(x,y)=$ $\displaystyle\underset{M\geq 0}{\min}\langle
C,M\rangle$ (22) $\displaystyle\text{ subject to }M\mathbf{1}=\mathbf{p},$
$\displaystyle\qquad\qquad\quad M^{T}\mathbf{1}=\mathbf{q},$

where $\mathbf{1}$ is the vector of all ones. The optimal transportation plan
between $\mathbf{p}$ and $\mathbf{q}$ is obtained after solving the linear
program problem in (22) Haasler et al. (2021).

Now we look at the continuous case. We still have $p(x)$ and $q(y)$ but they
are now continuous functions. The equivalence of minimizing $\langle
C,M\rangle$ with respect to $M$ in the discrete setting is to take the infimum
with respect to all possible $m(x,y)$ of

$\int_{\mathbb{R}^{d}\times\mathbb{R}^{d}}c(x,y)m(x,y)d\lambda(x,y)$

satisfying $\int_{\mathbb{R}^{d}}m(x,y)\d{\lambda}(x)=q(y)$ and
$\int_{\mathbb{R}^{d}}m(x,y)\d{\lambda}(y)=p(x)$. But with $c(x,y)$ being a
metric (and in our case the Euclidean distance) this is nothing else than the
$W_{1}$ distance from definition 2.1. However, this problem can be hard to
solve. But approximating $p(x)$ and $q(x)$ by histograms from samples we can
approximate the Wasserstein distance by solving (22) setting the entries in
$\mathbf{p}$ equal $\frac{n_{p,i}}{N}$ and similarly for $\mathbf{q}$. In this
case we need to define the distance matrix $C$ but a natural way to do so, is
to compute the distance between the centers of the bins.

The optimal transportation is very useful when we have a relatively small
number of bins. However, when we have a large amount of bins, solving the
linear program problem can be computationally heavy. To address this issue, it
is suggested to apply the Sinkhorn distance. The optimization problem can be
converted into a Sinkhorn distance between two probability vectors
$\mathbf{p}$ and $\mathbf{q}$ by introducing a Lagrange multiplier for the
entropy constraint as

$\displaystyle d_{\lambda}(x,y)=$ $\displaystyle\underset{M\geq
0}{\min}\langle C,M\rangle-\frac{1}{\lambda}h(M)$ (23) $\displaystyle\text{
subject to }M\mathbf{1}=\mathbf{p},$ $\displaystyle\qquad\qquad\quad
M^{T}\mathbf{1}=\mathbf{q},$

where $\lambda\geq 0$ is a tuning parameter that scales the entropy constraint
$h(M)=-\sum_{i,j=1}^{N}m_{ij}\log(m_{ij})$ (Cuturi (2013), equation (2)). By
optimizing $d_{\lambda}(x,y)$, implies an upper bound on the Wasserstein-1
distance which computationally should be easier to compute. Furthermore, we
mention that if $\lambda$ is large, the Sinkhorn distance would be a good
approximation of the Wasserstein distance. We used Algorithm (1) in Cuturi
(2013) and please refer to here for a detailed description of the Sinkhorn
distance.

###  3.3 A KL-estimator From Samples

In this section we describe a KL-divergence estimator given a set of samples
from two distributions. The estimator is presented in Perez-Cruz (2008). The
estimator is computed by approximating $p(x)$ and $q(y)$ around $x_{i}$ by
looking at the $k$-th nearest neighbor to $x_{i}$. They show that even though
the approximations of $p(x)$ and $q(y)$ do not necessarily converge to $p(x)$
and $q(y)$ the estimator will converge to the true KL-divergence when
increasing the sample size. The estimator is given by

$D_{KL,k-nn}(P\parallel
Q)=\frac{d}{n}\sum_{i=1}^{N}\log\left(\frac{s_{k}(x_{i})}{r_{k}(x_{i})}\right)+\log\left(\frac{N}{N-1}\right),$
(24)

where $r_{k}(x_{i})$ is the Euclidean distance from $x_{i}$ to the $k$-the
nearest neighbor in $\mathbf{X}\setminus\\{x_{i}\\}$, and $s_{k}(x_{i})$ is
the Euclidean distance to the $k$-the nearest neighbor in $\mathbf{Y}$.

###  3.4 Leakage Estimation via Kernel Mean Embedding

The use of kernel functions range widely in classical machine learning topics
such as support vector machines, the principal component analysis and
perceptron for deploying inner product $\langle x\,,x^{{}^{\prime}}\rangle$ of
two data instances $x,x^{{}^{\prime}}\in\mathcal{X}$ which measures the
distance between those instances. However, linear functions applied to the
inner product sometimes fail when generalizing the distance measure.

In order to overcome this issue, one can apply a ”kernel trick” and make the
distance measure accurate enough by replacing the inner product with a
possible non-linear mapping. Kernel methods rely on kernel functions and can
be defined as an inner product of a mapping function which transforms data
instances into a higher dimensional feature space as

$k(x,x^{{}^{\prime}})=\langle\phi(x)\,,\phi(x^{{}^{\prime}})\rangle_{\mathscr{H}}$
(25)

where $k(\cdot,\cdot)$ is the kernel function, $\phi(\cdot)$ is the mapping
function for data instances as
$\\{\phi:\mathcal{X}\rightarrow\mathscr{H},x\rightarrow\phi(x)\\}$, and
$\langle\phi(x)\,,\phi(x^{{}^{\prime}})\rangle_{\mathscr{H}}$ is the inner
product in the reproducing kernel Hilbert space (RKHS) $\mathscr{H}$. By
introducing this trick, which depends on substituting the $\langle
x\,,x^{{}^{\prime}}\rangle$ with
$\langle\phi(x)\,,\phi(x^{{}^{\prime}})\rangle_{\mathscr{H}}$, it is possible
to apply the inner product in a higher dimension, and measure the similarities
between $x\text{ and }x^{{}^{\prime}}$ Muandet et al. (2016). In this way, we
do not need to explicitly construct $\phi(x)$ and not need to know
$\mathscr{H}$ specifically. It will be sufficient to use positive definite
kernels in $\mathscr{H}$ for the benefits. As a such kernel, we used the
Gaussian kernel
$k\left({x},{x}^{\prime}\right)=\exp(-\frac{\|{x}-{x}^{\prime}\|_{2}^{2}}{2\sigma^{2}})$
with $\sigma=\sqrt{1/2}$ for this paper.

When it comes to defining a metric for probability distributions, it is useful
to consider the IPM setting in definition 2.1, where we could change the
function class $\mathcal{F}$ to specify different metrics.

Hence, we define yet another metric from IPM, namely the maximum mean
discrepancy (MMD) (with the help of kernel function eventually) using
$\mathcal{F}:=\left\\{f\mid\|f\|_{\mathscr{H}}\leq 1\right\\}$ to get the
functions from a unit ball in $\mathscr{H}$. Let $X,X^{\prime},Y,\text{ and
}Y^{\prime}$ be independent representations as $X,X^{\prime}\sim{P}$ and
$Y,Y^{\prime}\sim{Q}$ and set $\mu_{{P}}=\mathbb{E}_{X}[k(\cdot,X)]$ and
similarly for $\mu_{Q}$. For a more in depth walk through of this, we refer
the reader to Muandet et al. (2016). In here, it is also described that for a
function $f$, the kernel function can be seen as the evaluation of $f$ in the
following way $f(x)=\langle f,k(\cdot,x)\rangle$. From this one can define MMD
as the distance between mean embedding in $\mathscr{H}$ as

$\displaystyle\text{MMD}[\mathscr{H},{P},{Q}]$
$\displaystyle=\sup_{\|f\|_{\mathscr{H}}\leq 1}{\int f(x)d{P}(x)-\int
f(y)d{Q}(y)}$ (26) $\displaystyle=\sup_{\|f\|_{\mathscr{H}}\leq
1}\mathbb{E}_{P}[f(X)]-\mathbb{E}_{Q}[f(Y)]$
$\displaystyle=\sup_{\|f\|_{\mathscr{H}}\leq 1}\mathbb{E}_{P}[\langle
f,k(\cdot,X)\rangle]-\mathbb{E}_{Q}[\langle f,k(\cdot,Y)\rangle]$
$\displaystyle=\sup_{\|f\|_{\mathscr{H}}\leq 1}\langle
f,\mu_{{P}}-\mu_{{Q}}\rangle_{\mathscr{H}}$
$\displaystyle=\|\mu_{{P}}-\mu_{{Q}}\|_{\mathscr{H}}$

with the use of the reproducing property of $\mathscr{H}$ and the linearity of
the inner product and expectation. The $\mu_{{P}}$ in the equation (26) can be
used as
$\left\|\mu_{{P}}\right\|_{\mathscr{H}}^{2}=\langle\mathbb{E}_{X}[k(\cdot,X)],\mathbb{E}_{X^{\prime}}[k(\cdot,X^{\prime})]\rangle_{\mathscr{H}}=\mathbb{E}_{X,X^{\prime}}[k(X,X^{\prime})]$.
Then, the use of kernel functions become practical to calculate the MMD metric
using the expression

$\displaystyle\text{MMD}^{2}[\mathscr{H},{P},{Q}]$
$\displaystyle=\mathbb{E}_{P,P}[k(X,X^{\prime})]+\mathbb{E}_{Q,Q}[k(Y,Y^{\prime})]$
(27) $\displaystyle-2\mathbb{E}_{P,Q}[k(X,Y)].$

One can form empirical MMD using the i.i.d. samples from
$\mathbf{X}=\\{x_{i}\\}_{i=1}^{N}$ and $\mathbf{Y}=\\{y_{i}\\}_{i=1}^{N}$ with
respect to the kernel function as

$\displaystyle\widehat{\mathrm{MMD}_{u}^{2}}[\mathscr{H},\mathbf{X},\mathbf{Y}]$
$\displaystyle=\frac{1}{N(N-1)}\sum_{i=1}^{N}\sum_{j\neq
i}^{N}k({x_{i}},{x_{j}})$ (28)
$\displaystyle+\frac{1}{N(N-1)}\sum_{i=1}^{N}\sum_{j\neq
i}^{N}k({y_{i}},{y_{j}})$
$\displaystyle-\frac{2}{N^{2}}\sum_{i=1}^{N}\sum_{j=1}^{N}k({x_{i}},{y_{j}})$

which is the unbiased estimator of the MMD Borgwardt et al. (2006). This
estimation of MMD is informative in a sense that it provides a lower bound for
$W_{k1}(P,Q)\text{ and }\gamma(\mathcal{F}_{TV},P,Q)$ due to the inequalities
$\text{MMD}[\mathscr{H},P,Q]\leq
W_{k1}(P,Q)\leq\sqrt{\text{MMD}[\mathscr{H},P,Q]^{2}+4C}$ and
$\text{MMD}[\mathscr{H},P,Q]\leq\sqrt{C}\gamma(\mathcal{F}_{TV},P,Q)$
satisfying $\\\ \sup_{{x}\in X}k({x},{x})\leq C\leq\infty$ for a constant $C$,
and $W_{k1}$ is the kernel-based $W_{1}$ by defining
$d(x,y)=\|k(\cdot,x)-k(\cdot,y)\|_{\mathscr{H}}$ Sriperumbudur et al. (2010).
While estimation of MMD only provides a lower bound for total variation, it
provides both lower and upper bound for Wasserstein distance. Convergence of
MMD is another advantage of using it as a measure. According to Muandet et al.
(2016), MMD appears to be converging with the rate of $\sqrt{1/N}$. Dimension
of $d$ does not effect the convergence apart from a constant $c_{d}$ that
depending on $d$ as
$\left|\widehat{\mathrm{MMD}_{u}^{2}}[\mathscr{H},\mathbf{X},\mathbf{Y}]-\operatorname{MMD}^{2}[\mathscr{H},{P},{Q}]\right|\leq
c_{d}\sqrt{1/N}$.

##  4 Experiment and Results

Since the motivation is especially leakage of information in a distributed
computation such as a multiparty computation protocol we evaluate the metrics
in such setups. We take our inspiration from Tjell and Wisniewski (2021) where
secret sharing is defined over the real numbers. In contrast to the
traditional finite field multiparty computation a share might reveal some (but
limited) information. Hence, we will evaluate the leakage of a share and a
small multiparty computation using this concept.

###  4.1 A Secret and Its Share Scenario

First, we consider the leakage of information of a normal distributed
$X\sim\mathcal{N}(\mu_{x},\sigma_{x}^{2})$ from an obfuscated version of $X$,
namely $X-R$ where $R\sim\mathcal{N}(\mu_{r},\sigma_{r}^{2})$. This can also
be seen as a share of $X$ in the real number secret sharing scheme from Tjell
and Wisniewski (2021). The joint distribution of $(X,X-R)$ is

$\mathcal{N}\left(\begin{bmatrix}\mu_{x}\\\
\mu_{x}-\mu_{r}\end{bmatrix},\begin{bmatrix}\sigma_{x}^{2}&\sigma_{x}^{2}\\\
\sigma_{x}^{2}&\sigma_{x}^{2}+\sigma_{r}^{2}\end{bmatrix}\right),$ (29)

and the product of the marginals is

$\mathcal{N}\left(\begin{bmatrix}\mu_{x}\\\
\mu_{x}-\mu_{r}\end{bmatrix},\begin{bmatrix}\sigma_{x}^{2}&0\\\
0&\sigma_{x}^{2}+\sigma_{r}^{2}\end{bmatrix}\right),$ (30)

and hence we can actually determine the KL-divergence explicitly in this case.
In our experiments, we assume that both $X$ and $R$ has $0$ mean so for
simplicity we do the same here. In this situation we have

$I_{KL}(X;X-R)=\frac{1}{2}\ln\left(1+\frac{\sigma_{x}^{2}}{\sigma_{r}^{2}}\right).$
(31)

In the experiments we set $\sigma_{x}^{2}=1$ and $\sigma_{r}^{2}=10$ implying
that

$I_{KL}(X;X-R)=\frac{1}{2}\ln\left(1.1\right)=0.048.$ (32)

The upper bound on TV in (14) is less than the bound in (15) in this case, and
it implies that

$I_{JS}(X;X-R)\leq I_{TV}(X;X-R)\leq 0.154.$ (33)

However, we can also use the fact that the JS-divergence can be defined from
the KL-divergence as in (8). We have

$\displaystyle I_{JS}(X;X-R)=$ (34)
$\displaystyle\frac{1}{2}D_{KL}\left(P_{(X,X-R)}||\frac{P_{X}\otimes
P_{X-R}+P_{X,X-R}}{2}\right)$
$\displaystyle+\frac{1}{2}D_{KL}\left(P_{X}\otimes P_{X-R}||\frac{P_{X}\otimes
P_{X-R}+P_{X,X-R}}{2}\right)$

Both of these KL-divergences are between a Gaussian and a mixture of two
Gaussians with coefficients $\frac{1}{2}$. In Durrieu et al. (2012) they give
upper bounds on KL-divergence between mixture of Gaussians and from this we
can derive

$\displaystyle I_{JS}(X;X-R)\leq$ (35)
$\displaystyle-\frac{1}{2}\log\left(\frac{1}{2}(1+e^{-D_{KL}(P_{(X,X-R)})||P_{X}\otimes
P_{X-R})})\right)$
$\displaystyle-\frac{1}{2}\log\left(\frac{1}{2}(1+e^{-D_{KL}(P_{X}\otimes
P_{X-R}||P_{(X,X-R)})})\right).$

Here we only have KL-divergences between Gaussians which we have closed form
solutions for. Plugging in the distributions from (29) and (30) with zero mean
and $\sigma_{x}^{2}=1$, $\sigma_{r}^{2}=10$, we obtain that

$I_{JS}(X;X-R)\leq 0.0356$ (36)

Furthermore, there exists a closed form expression for the Wasserstein-2
distance with the Euclidean norm when the two distributions are normal. Let
$\Sigma_{1}$ and $\Sigma_{2}$ be the covariance matrices of the two
distributions (and assume 0-mean) then the Wasserstein-2 distance is

$\sqrt{\mathrm{trace}\left(\Sigma_{1}+\Sigma_{2}-2\left(\Sigma_{2}^{\frac{1}{2}}\Sigma_{1}\Sigma_{2}^{\frac{1}{2}}\right)^{\frac{1}{2}}\right)}.$
(37)

This implies that

$I_{W_{1}}(X;X-R)\leq W_{2}(P_{(X,X-R)},P_{X}\otimes P_{(X-R)})=0.292$ (38)

when we use the covariance matrices from (29) and (30).

###  4.2 Multiplication Using Three Parties Scenario

In this scenario we consider a situation with three parties where two of them
having a value $s$ and $t$ respectively and the parties wants to learn the
product $st$. We treat $s$ and $t$ as outcomes of random variables $S$ and $T$
and we use the Shamir secret sharing scheme from Tjell and Wisniewski (2021)
with privacy threshold $1$ and evaluation points $p_{1}=-1$, $p_{2}=1$, and
$p_{3}=2$. In this situation the shares can be constructed by evaluating
$f_{s}(x)=s+(r_{s}-s)x$ at $p_{i}$ and hence the shares of $s$ is
$(2s-r_{s},r_{s},-s+2r_{s})$. Notice that having two shares leaks everything
about $s$. The algorithm goes on like this. The party having $s$, secret
shares $s$ by sending $f_{s}(p_{i})$ to the $i$’th party. Similarly, is $t$
shared by sending $f_{t}(p_{i})$ to the $i$’th party. Now, the $i$’th party
computes $f_{s}(p_{i})f_{t}(p_{i})$ and sends this value to the other two
parties. Since this is a evaluation of a degree-2 polynomial and each party
has three evaluations they are able to determine the polynomial having
constant term $st$. We assume that the first party is not having an input and
we want to evaluate how much he learns about $s$ from following this
distributed algorithm. I.e. we want to evaluate

$I(S;2S-R_{s},2T-R_{t},R_{t}R_{s},(-S+2R_{s})(-T+2R_{t})).$ (39)

In the experiments we assume that $S$ and $T$ are following a
$\mathcal{N}(0,1)$ distribution and $R_{s}$ and $R_{t}$ are normal as well
with $0$ mean and variance $\sigma_{r}^{2}=10$.

###  4.3 Experimental Setup

For both scenarios explained in Section 4.1 and Section 4.2, we will consider
the convergences for all divergences and metrics with respect to the number of
samples and the number of bins we used. We will also report and comment on the
run time for each approximation and computation. However, we were unable to
compute the Wasserstein and Sinkhorn distance due to memory problems for the
scenario in Section 4.2 which indicates that the two methods are impractical
for measuring information leakage. Furthermore, the $k$-nearest neighbor
approach does not seem to converge for the amount of samples we were able to
evaluate. Therefore, we only show the convergence for the histogram-based
divergences in this case.

First of all, we set the number of samples $N$ for all experiments to be in
the span of $N=[100,500,10^{3},2\times 10^{3},3\times 10^{3},5\times
10^{3},10^{4},10^{5},10^{6},10^{7},10^{8}]$ for histogram based approximations
(while we set the number of bins as $24$ in each dimension) and
$N=[100,500,10^{3},2\times 10^{3},3\times 10^{3},4\times 10^{3},5\times
10^{3},7\times 10^{3},10^{4},2\times 10^{4}]$ for the sample based
approximations. Span of the number of bins (in each dimension) is
$[8,10,12,16,20,24,28,30]$ while we set the number of samples as $N=10^{7}$
for scenario 4.1. We set the $\lambda$ parameter in Sinkhorn approximation as
$\lambda=700$ for scenario 4.1.

Since we deal with histograms, some bins will be empty when we represent
distributions with them. This can cause problems when we try to compute the KL
divergence referring to the definition 2.1. For the histogram of $q(x)$, empty
bins will produce $\log(0)$ and this will cause an error in the
implementation. To overcome this issue, we attain a small number ($10^{-8}$)
that is close to $0$ whenever we have an empty bin for $q(x)$.

###  4.4 Results

We evaluate and interpret the results for our experiments.

Figure 1: Average values of metrics for the scenario in 4.1 with respect to
logarithm of the number of samples. Dotted lines represent the standard
deviation for each metric. Red line is KL, green is TV and blue is JS
divergences from Section 3.1. Dotted lines represent the standard deviations.
Dotted black line is from bound (33). Magenta line is the histogram based
$W_{1}$ calculation and cyan line is the Sinkhorn’s estimation for $W_{1}$.

In Figure 1, we observe for the scenario described in Section 4.1 that we have
a nice convergence for the histogram based estimations from Section 3.1 of the
KL, TV and JS divergences when sufficient amount of samples are used. After
$10^{5}$ samples, divergences started to converge smoothly as well as their
standard deviation narrows down. Furthermore, the KL divergence seems to
converge to the right value in (32). On the other hand, the histogram based
Wasserstein distance calculation via LP started to converge when we used a
$10^{7}$ number of samples while the Sinkhorn estimation converged using
$10^{5}$ samples. We also see that the bounds in (33) and (36) hold after
convergence. In Table 1, we do not observe significant run time change when
the number of samples used is increased from $100$ to $10^{7}$. Noticeable
change is seen when we used $10^{8}$ samples which implies around an increase
in run time by a factor of 100 for the divergences and a doubling in runtime
for the LP histogram based Wasserstein distance calculation. We also see that
Sinkhorn approximation is much faster when compared with LP calculation.

| 100 | 500 | $10^{3}$ | $2\times 10^{3}$ | $3\times 10^{3}$ | $5\times 10^{3}$ | $10^{4}$ | $10^{5}$ | $10^{6}$ | $10^{7}$ | $10^{8}$
---|---|---|---|---|---|---|---|---|---|---|---
| kl with
---
histogram
$4.45\times 10^{-4}$ | $4.45\times 10^{-4}$ | $1.92\times 10^{-4}$ | $1.91\times 10^{-4}$ | $2.15\times 10^{-4}$ | $5.14\times 10^{-5}$ | $2.48\times 10^{-4}$ | $2.47\times 10^{-4}$ | $2.50\times 10^{-4}$ | $2.77\times 10^{-4}$ | $0.18\times 10^{-1}$
| tv with
---
histogram
$2.32\times 10^{-4}$ | $2.59\times 10^{-4}$ | $9.0\times 10^{-5}$ | $1.12\times 10^{-4}$ | $1.23\times 10^{-4}$ | $4.93\times 10^{-6}$ | $1.29\times 10^{-4}$ | $1.46\times 10^{-4}$ | $1.41\times 10^{-4}$ | $1.57\times 10^{-4}$ | $0.03\times 10^{-1}$
| js with
---
histogram
$4.45\times 10^{-4}$ | $3.63\times 10^{-4}$ | $1.50\times 10^{-4}$ | $1.69\times 10^{-4}$ | $2.00\times 10^{-4}$ | $4.93\times 10^{-5}$ | $1.99\times 10^{-4}$ | $2.04\times 10^{-4}$ | $2.06\times 10^{-4}$ | $2.05\times 10^{-4}$ | $0.04\times 10^{-1}$
| wass. dist
---
with LP
2.99 | 2.72 | 2.63 | 2.66 | 2.11 | 1.89 | 2.46 | 2.60 | 1.96 | 2.04 | 4.26
| wass. dist
---
with Sinkhorn
0.016 | 0.019 | 0.017 | 0.021 | 0.017 | 0.018 | 0.017 | 0.015 | 0.010 | 0.015 | 0.138

Table 1: Average run times for the scenario in 4.1 in seconds. Rows represent
the approximations in 3.1 and 3.2 and columns represent the number of samples
used. Figure 2: Average values of metrics for the scenario in 4.1 with respect
to number of bins. Dotted lines represent the standard deviation for each
metric. Red line is KL, green is TV and blue is JS divergences from Section
3.1. Dotted black line is from bound (33) and dotted cyan line is from bound
(36). Magenta line is the histogram based $W_{1}$ calculation and cyan line is
the Sinkhorn’s estimation for $W_{1}$.

In Figure 2, we evaluate for the scenario 4.1 that histogram based $W_{1}$ via
LP started to converge when using 30 bins in both dimensions for the
histograms (in total 900 bins). Also Sinkhorn behaves like an upper bound for
$W_{1}$ at the convergence level. The change in the number of bins does not
seem to affect the behavior of TV and JS divergences. KL divergence is
slightly increased but still around the expected value. The bounds in (33) and
(36) also hold after convergence. Table 2 represents the advantage of Sinkhorn
approximation over LP calculation for $W_{1}$ in terms of the speed. For
divergences, it seems that the choice of the number of bins has a minor effect
on run time.

| 8 | 10 | 12 | 16 | 20 | 24 | 28 | 30
---|---|---|---|---|---|---|---|---
| wass. dist.
---
with LP
$0.0135$ | $0.0313$ | $0.0518$ | $0.2064$ | $0.7365$ | $1.9925$ | $4.8592$ | $12.0733$
| wass. dist.
---
with Sinkhorn
$8.8232\times 10^{-4}$ | $0.0012$ | $0.0013$ | $0.0026$ | $0.0078$ | $0.0151$ | $0.0357$ | $0.0993$
| kl with
---
histograms
$2.2967\times 10^{-4}$ | $1.9046\times 10^{-4}$ | $1.8846\times 10^{-4}$ | $0.0011$ | $2.2896\times 10^{-4}$ | $2.4345\times 10^{-4}$ | $3.5389\times 10^{-4}$ | $0.0069$
| tv with
---
histograms
$1.2121\times 10^{-4}$ | $0.8717\times 10^{-4}$ | $0.8518\times 10^{-4}$ | $1.3931\times 10^{-4}$ | $1.0123\times 10^{-4}$ | $1.1391\times 10^{-4}$ | $1.1795\times 10^{-4}$ | $0.0010$
| js with
---
histograms
$1.6072\times 10^{-4}$ | $2.0740\times 10^{-4}$ | $1.2036\times 10^{-4}$ | $1.4439\times 10^{-4}$ | $1.4119\times 10^{-4}$ | $1.6904\times 10^{-4}$ | $2.8426\times 10^{-4}$ | $0.0012$

Table 2: Average run times for the scenario in 4.1 in seconds. Rows represent
the approximations in 3.1 and 3.2 and columns represent the number of bins
used. Figure 3: Average values of kernel and knn based metrics for the
scenario in 4.1 with respect to logarithm of the number of samples. Red, blue,
green and cyan lines are KL divergences using knn approximation in 3.3 for
$k=1,2,5,10$ respectively. Magenta line mmd with Gaussian kernel from 3.4.
Dotted black line is for the kl value in (32)

In Figure 3, we observe that knn estimators for different $k$ oscillates for
the samples smaller than $10000$ in the scenario 4.1. However, it started to
converge when $2000$ samples were used. MMD approximation also seems converged
as well with the sufficient amount of samples. In Table 3, it is obvious that
the run time increases gradually for MMD approximation as the number of
samples in use increases in the both scenarios 4.1 and 4.2. When using knn
estimator, there is insignificant increase in runtime as we use more samples
for scenario 4.1 unlike MMD. Hence, knn estimator works poorly for the
scenario 4.2 since it did not converge to a specific value as we increase the
number of samples for the estimation.

| 100 | 500 | $10^{3}$ | $2\times 10^{3}$ | $3\times 10^{3}$ | $4\times 10^{3}$ | $5\times 10^{3}$ | $7\times 10^{3}$ | $10^{4}$ | $2\times 10^{4}$
---|---|---|---|---|---|---|---|---|---|---
| mmd with Gaussian
---
for scenario 4.1
$0.0094$ | $0.1024$ | $0.4214$ | $2.0664$ | $4.0022$ | $7.3511$ | $11.6014$ | $22.8216$ | $47.6443$ | $193.6788$
| knn (for all k)
---
for scenario 4.1
$0.0030$ | $0.0084$ | $0.0186$ | $0.0301$ | $0.0450$ | $0.0598$ | $0.0700$ | $0.1002$ | $0.1511$ | $0.2941$
| mmd with Gaussian
---
for scenario 4.2
$0.0062$ | $0.1013$ | $0.4119$ | $2.2072$ | $4.7782$ | $8.4296$ | $15.4711$ | $25.5461$ | $50.4929$ | $198.4727$

Table 3: Average run times for scenarios 4.1 and 4.2 in seconds. Rows
represent the approximations in 3.3 and 3.4 and columns represent the number
of samples used. Figure 4: Average values of metrics for scenario 4.2 with
respect to logarithm of the number of samples. Red line is KL, the green line
is total variation and the blue line is Jensen-Shannon divergences from 3.1.
Dotted lines represent the standard deviation for each metric. Cyan line is
from bound (14) and magenta line is from bound (15). Dark yellow line is MMD
approximation from 3.4

In Figure 4, we observe for the scenario described in Section 4.2 that the
convergence of approximations started to emerge when we use $10^{5}$ number of
samples for histogram based estimations of the KL, TV and JS divergences.
Standard deviation is quite tight after such a number of samples used. Since
we do not know the explicit value of KL, we plug in the estimate into the
bounds in (14) and (15), which are shown in the figure as well. MMD
approximation could only be possible to run with $20000$ samples maximum but
it is sufficient for its convergence. Table 4 shows that there is not a
significant change in run times regardless of the number of samples used.

| 100 | 500 | $10^{3}$ | $2\times 10^{3}$ | $3\times 10^{3}$ | $5\times 10^{3}$ | $10^{4}$ | $10^{5}$ | $10^{6}$ | $10^{7}$ | $10^{8}$
---|---|---|---|---|---|---|---|---|---|---|---
| kl with
---
histogram
$0.218$ | $0.21$ | $0.22$ | $0.21$ | $0.22$ | $0.23$ | $0.22$ | $0.21$ | $0.21$ | $0.26$ | $0.30$
| tv with
---
histogram
$0.034$ | $0.03$ | $0.03$ | $0.03$ | $0.03$ | $0.03$ | $0.03$ | $0.03$ | $0.03$ | $0.03$ | $0.03$
| js with
---
histogram
$0.331$ | $0.34$ | $0.33$ | $0.34$ | $0.33$ | $0.35$ | $0.33$ | $0.32$ | $0.33$ | $0.35$ | $0.42$

Table 4: Average run times for the scenario in 4.2 in seconds. Rows represent
the approximations in 3.1 and columns represent the number of samples used.

We were not able to run the LP calculation and the Sinkhorn’s approximation
for $W_{1}$ in the scenario 4.2 when using both histogram-based evaluations
due to a memory problem. This indicates that the use of LP and Sinkhorn is
impractical when the dimension of the samples are higher than 5. This seems to
be due to the high amount of bins needed for the histograms in higher
dimensions, which make the $C$ matrix too large with respect to memory.

##  5 Conclusion and Future Work

To sum up, we evaluate the possible divergences and metrics to measure the
mutual information $I(X;Y)$ for specific scenarios using multiparty
computation in this paper. Results show that the histogram-based estimators of
the divergences are strong for approximating the mutual information in terms
of the number of samples used and the run time of the approximation. The MMD
metric is also a useful measure for its convergence but it can be
computationally heavy for applications requiring a high number of samples.
Wasserstein distance is a quite informative metric as well. On the other hand,
calculating it using LP or estimating it with Sinkhorn’s algorithm becomes
useless for the samples in the $5$ dimension.

## References

  * Borgwardt et al. (2006) Borgwardt, K.M., Gretton, A., Rasch, M.J., Kriegel, H.P., Schölkopf, B., and Smola, A.J. (2006).  Integrating structured biological data by kernel maximum mean discrepancy.  _Bioinformatics_ , 22(14), e49–e57.
  * Cristiani et al. (2020) Cristiani, V., Lecomte, M., and Maurine, P. (2020).  Leakage assessment through neural estimation of the mutual information.  In _Applied Cryptography and Network Security Workshops_ , 144–162. Springer International Publishing, Cham.
  * Cuff and Yu (2016) Cuff, P. and Yu, L. (2016).  Differential privacy as a mutual information constraint.  In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , CCS ’16, 43–54. Association for Computing Machinery, New York, NY, USA.  10.1145/2976749.2978308.
  * Cuturi (2013) Cuturi, M. (2013).  Sinkhorn distances: Lightspeed computation of optimal transport.  _Advances in neural information processing systems_ , 26, 2292–2300.
  * Durrieu et al. (2012) Durrieu, J.L., Thiran, J.P., and Kelly, F. (2012).  Lower and upper bounds for approximation of the kullback-leibler divergence between gaussian mixture models.  In _2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 4833–4836.  10.1109/ICASSP.2012.6289001.
  * Farokhi and Kaafar (2020) Farokhi, F. and Kaafar, M.A. (2020).  Modelling and quantifying membership information leakage in machine learning.
  * Haasler et al. (2021) Haasler, I., Karlsson, J., and Ringh, A. (2021).  Control and estimation of ensembles via structured optimal transport.  _IEEE Control Systems Magazine_ , 41(4), 50–69.
  * Li et al. (2021) Li, Q., Gundersen, J.S., Heusdens, R., and Christensen, M.G. (2021).  Privacy-preserving distributed processing: Metrics, bounds and algorithms.  _IEEE Transactions on Information Forensics and Security_ , 16, 2090–2103.  10.1109/TIFS.2021.3050064.
  * Muandet et al. (2016) Muandet, K., Fukumizu, K., Sriperumbudur, B., and Schölkopf, B. (2016).  Kernel mean embedding of distributions: A review and beyond.  _arXiv preprint arXiv:1605.09522_.
  * Müller (1997) Müller, A. (1997).  Integral probability metrics and their generating classes of functions.  _Advances in Applied Probability_ , 29(2), 429–443.
  * Perez-Cruz (2008) Perez-Cruz, F. (2008).  Kullback-leibler divergence estimation of continuous distributions.  In _2008 IEEE International Symposium on Information Theory_ , 1666–1670.  10.1109/ISIT.2008.4595271.
  * Rényi (1961) Rényi, A. (1961).  On measures of entropy and information.  In _Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics_ , 547–561. University of California Press.
  * Sankar et al. (2013) Sankar, L., Rajagopalan, S.R., and Poor, H.V. (2013).  Utility-privacy tradeoffs in databases: An information-theoretic approach.  _IEEE Transactions on Information Forensics and Security_ , 8(6), 838–852.  10.1109/TIFS.2013.2253320.
  * Sason and Verdú (2016) Sason, I. and Verdú, S. (2016).  $f$ -divergence inequalities.  _IEEE Transactions on Information Theory_ , 62(11), 5973–6006.  10.1109/TIT.2016.2603151.
  * Shannon (1948) Shannon, C.E. (1948).  A mathematical theory of communication.  _The Bell System Technical Journal_ , 27(3), 379–423.  10.1002/j.1538-7305.1948.tb01338.x.
  * Sriperumbudur et al. (2009) Sriperumbudur, B.K., Fukumizu, K., Gretton, A., Schölkopf, B., and Lanckriet, G.R. (2009).  On integral probability metrics,$\backslash$phi-divergences and binary classification.  _arXiv preprint arXiv:0901.2698_.
  * Sriperumbudur et al. (2010) Sriperumbudur, B.K., Gretton, A., Fukumizu, K., Schölkopf, B., and Lanckriet, G.R. (2010).  Hilbert space embeddings and metrics on probability measures.  _The Journal of Machine Learning Research_ , 11, 1517–1561.
  * Tjell and Wisniewski (2021) Tjell, K. and Wisniewski, R. (2021).  Privacy in distributed computations based on real number secret sharing.
  * Urrutia (2018) Urrutia, F. (2018).  Information theory for multi-party peer-to-peer communication protocols. (théorie de l’information pour protocoles de communication peer-to-peer).
  * Villani (2009) Villani, C. (2009).  _Optimal transport: old and new_ , volume 338.  Springer.