# Private independence testing across two parties

Praneeth Vepakomma Massachusetts Institute of Technology, USA Mohammad
Mohammadi Amiri Massachusetts Institute of Technology, USA Clément L. Canonne
The University of Sydney, Australia
Ramesh Raskar Massachusetts Institute of Technology, USA Alex Pentland
Massachusetts Institute of Technology, USA

###### Abstract

We introduce $\pi$-test, a privacy-preserving algorithm for testing
statistical independence between data distributed across multiple parties. Our
algorithm relies on privately estimating the distance correlation between
datasets, a quantitative measure of independence introduced in Székely et al.
[2007]. We establish both additive and multiplicative error bounds on the
utility of our differentially private test, which we believe will find
applications in a variety of distributed hypothesis testing settings involving
sensitive data.

##  1 Introduction

Hypothesis testing is a staple of theoretical and applied statistics, whose
impact in decision making has gone beyond that of statistics into a wide-range
of adjacent and seemingly far-flung fields of science and engineering. At a
high level, hypothesis testing formalizes the choice to reject (or not reject)
a _null_ hypothesis $\mathcal{H}_{0}$ in comparison to an alternate hypothesis
$\mathcal{H}_{1}$, where both hypotheses are defined as disjoint sets of
probability distributions. The decision is to be made with a high probability
upon looking at samples from some unknown distribution, assumed to belong to
$\mathcal{H}_{0}\cup\mathcal{H}_{1}$.

Examples of hypothesis testing abound, including, to name a few, goodness-of-
fit and testing validity of a purported statistical model, testing
stationarity of a time series, hypothesis tests for sequential decision making
such as change-point detection, and so on. Central to our study is one of the
most fundamental hypotheses testing problems, dating back to Pearson [1900]:
that of _statistical independence_. In contexts where the underlying data
(i.e., samples) is personal or conveys sensitive information, guaranteeing
privacy (of data samples) in hypothesis testing has recently become the focus
of much theoretical and practical interest, both for legal and societal
reasons. Indeed, privacy-preserving computation is necessitated by a range of
motivations, including regulatory compliance, personal preferences,
confidentiality, as well a a migration to distributed forms of computation
where client data or intermediate computations of their data are shared among
various (not necessarily trusted) parties. In this paper, we quantify privacy
in the framework of _differential privacy_ , a rigorous and widely used notion
of privacy introduced in Dwork et al. [2014], and focus on a two-party
setting. The following is the main problem of consideration in this paper.

Problem statement: How can the sample _test-statistic_ for a hypothesis test
of independence between two random variables of arbitrary dimension be
estimated _privately_ when samples from these random variables are held by two
different parties? The central importance of a test-statistic (to hypothesis
testing) is detailed in the preliminaries (Section 2).

Communication setup: In terms of communication, we consider a two-party setup,
with Alice holding $\boldsymbol{X}$ and Bob holding $\boldsymbol{Y}$. The
communication is one-way, from Alice to Bob: Alice sends an intermediate
computation in a privatized form to Bob, who then finishes the rest of the
computation on its premise. Bob never reveals the answer to Alice and
therefore the on-device computation of Bob involves its own non-privatized
data. Therefore, Bob obtains the results (on its side) of the hypothesis test
of independence between its data and that of Alice’s, while maintaining the
privacy of Alice’s (already privatized) data, regardless of the one-way
communications that happen. We refer to this setup as _one-way local privacy_
or _one-way local differential privacy_ , as the privatization mechanism used
by Alice ensures differential privacy Dwork et al. [2014]. A more general way
to think about it is as a data summary that when published by Alice, allows
any analyst to test independence with another data set they themselves hold.
We illustrate this setup in Figure 1.

Figure 1: Model of privacy considered, where Alice releases a private summary
of data as a sufficient statistic which allows any analyst (here, either Bob
or Carol) to test independence with another data set they hold with respect to
that of Alice’s original data. This private statistic suffices to compute the
rest of the test statistic for independence testing on any analyst’s premise.
We provide utility bounds on the computation of this test-statistic in Section
4.1.

###  1.1 Related Work

In view of the large amount of literature addressing the problem of
independence testing over the years in a variety of statistical settings, we
focus here on the closest and most relevant to our work. Private independence
testing for contingency tables. This first line of work, which aims to develop
differentially private independence tests, itself comes in two distinct
flavors: one is the so-called _asymptotic regime_ (limiting distribution and
properties of the test statistic as sample size goes to infinity), and the
second is the _finite-sample regime_ (coarser utility guarantees, but with
explicit, finite bounds on the sample size required to achieve them).

  1. 1.

Asymptotic tests: The work of Gaboardi et al. [2016] considers independence
testing in the (central) model of differentially privacy, from an _asymptotic_
perspective: namely, they propose a differentially private analogue of the
classical chi-squared tests of independence, and analyse the limiting
distribution of the test-statistic along with its resulting power (1-Type II
error). Note that, Type II error is the probability of failing to reject null
hypothesis when the null hypothesis is not true.

  2. 2.

Non-asymptotic tests: Later work by Sheffet [2018] focuses on the _finite
sample_ (non-asymptotic) version of the test under a more stringent model of
local privacy. The question is formulated, in a manner that is standard in
theoretical computer science (specifically in the domain of distribution
testing) and in minimax analysis in statistics as part of a composite
hypthesis testing problem. They consider a set of product distributions as
part of the null hypothesis and frame the alternative hypothesis to contain
all the distributions that are “far” from product distributions, where
“farness” is quantified by the total variation distance. They focus on the
minimax sample complexity achievable using a specific locally private
mechanism of Randomized Response [Warner, 1965]. Subsequent work by Acharya et
al. [2021] improves on these results, by showing a way to achieve
significantly lower sample complexity (still in the locally private setting)
by considering a different privacy mechanism and upon establishing matching
lower bounds.

Non-private independence testing with dependency measures. There have been
advances in development of various statistical dependency measures, and an
active route of modern independence testing is based on derivation of test-
statistics that depend on these measures in addition to on other required
terms. We now share some related works that fall in this category. Distance
covariance was introduced in [Székely et al., 2007] and can be expressed as a
weighted $L_{2}$ norm between the characteristic function of the joint
distribution and the product of the marginal characteristic functions. This
concept has also been studied in high dimensions [Székely and Rizzo, 2013, Yao
et al., 2018], and for testing independence of several random vectors [Gao et
al., 2021]. In [Sejdinovic et al., 2013], tests based on distance covariance
were shown to be equivalent to a reproducing kernel Hilbert space (RKHS) test
for a specific choice of kernel. RKHS tests have been widely studied in the
machine learning community, with a survey of the subject given by [Harchaoui
et al., 2013] and [Gretton et al., 2005, Heller et al., 2016] in which the
Hilbert-Schmidt independence criterion was proposed. These tests are based on
embedding the joint distribution and product of the marginal distributions
into a Hilbert space and considering the norm of their difference in this
space. One drawback of the kernel paradigm here is the computational
complexity, though [Jitkrittum et al., 2017, 2016] and [Zhang et al., 2018]
have recently attempted to address this issue.

Conditional independence tests and causal discovery. A conditional measure of
dependence called conditional distance correlation was introduced by [Wang et
al., 2015]. The works in [Zhang et al., 2012, 2017, Wang et al., 2020, Shen et
al., 2022] performed conditional independence testing and applied them to the
problem of causal discovery.

To the best of our knowledge, no other work addresses the question of
independence testing under differential privacy (be it local or central) other
than the differentially private distribution estimation approach (under total
variation distance) [Diakonikolas et al., 2015] or two-sample goodness-of-fit
[Acharya et al., 2018, Aliakbarpour et al., 2018] that can be used to obtain
sub-optimal sample complexity guarantees for this problem. We note that this
body of work differs from ours, both in the distributed model assumed (the way
the data is partitioned across users) and in the guarantee provided
(dependency measure used). They also restrict themselves to the discrete
setting as opposed to ours. Our method can also be applied to test between
samples lying in different dimensions. In particular, most of the works
discussed above (except for Gaboardi et al. [2016]), follow the norm in
distribution testing and focus on very stringent notion of minimax testing
under total variation distance, which might be overly conservative in many
settings.

###  1.2 Our contributions

Our contributions are threefold, and can be summarized as follows:

  1. 1.

We provide a mechanism to privatize the test-statistic required to perform a
hypothesis test of independence between $\boldsymbol{x}\in\mathbb{R}^{d}$
hosted by Alice and $\boldsymbol{y}\in\mathbb{R}^{m}$ hosted by Bob under the
regime of one-way local differential privacy.

  2. 2.

We show one can express our test statistic as a ratio of sums of _directional
variance_ queries (of non-private data) with respect to ‘specific’ covariance
matrices of sensitive data (for the formal definition of _directional
variance_ queries, the reader is referred to Section 2). This reduction
enables us to privatize the test-statistic via privatization of these
covariances. This brings up the next question of deriving utility guarantees
for the privatized test-statistic, leading to our next contribution.

  3. 3.

We derive both lower and upper bounds on the utility of our private estimator
in terms of additive and multiplicative errors. For a chosen $0<\eta<1$, to
achieve $(\epsilon,\delta)$-differential privacy our approach results in a
multiplicative error factor of $1\pm\eta$, and an additive error $\Delta$
bounded as

$-\frac{(1-\eta)^{2}}{2(1+\eta)}\leq\Delta\leq\frac{2\tau}{(1-\eta)[(1-\eta)s-\tau]},$

where

$\tau\coloneqq\left(\frac{2048\ln(2/(m+n)\nu)\ln(2/\delta)}{\eta\epsilon^{2}}\right)\ln^{2}\\!\left(\frac{128\ln\frac{1}{(m+n)\nu}}{\eta^{2}\delta}\right),$

for some $s>\frac{\tau}{1-\eta}$. The additive and multiplicative
approximations hold together at the same time with probability at least
$1-(m+n)\nu$ for the user’s choice of $\nu$.

###  1.3 Our techniques: Privatization Strategy

We now give a high-level summary of our approach along with its organization.
Setup: We let $\boldsymbol{X}_{n\times d}$ and $\boldsymbol{Y}_{n\times m}$
denote the sample data matrices held by two clients (whom we refer to by)
Alice and Bob, respectively. The number of samples is denoted by $n$ and each
sample lies correspondingly in $\mathbb{R}^{d}$ and $\mathbb{R}^{m}$,
respectively. Note that, in the rest of the paper we refer to rows $k,l$ in
$\boldsymbol{X}$ using lower-case representation of
$\boldsymbol{x}_{k},\boldsymbol{x}_{l}$. Similarly, we refer to columns $k,l$
in $\boldsymbol{X}$ using upper-case representation of
$\boldsymbol{X}_{k},\boldsymbol{X}_{l}$.

As a starting point for the problem of private independence testing, we first
provide the test-statistic for non-private independence testing in section 3.
Privatizing this test-statistic requires privatization of (a). it’s numerator,
given by the _distance covariance_ and denoted by
$\hat{\Omega}^{2}(\boldsymbol{X},\boldsymbol{Y})$ as well as (b). it’s
denominator, given by a product of individually computed means of pairwise
distances of $\boldsymbol{X}$ and $\boldsymbol{Y}$, that is denoted by
$\hat{S}(\boldsymbol{X},\boldsymbol{Y})$. These terms are formally defined in
Section 3. The privatization strategy that we employ for both of these terms
relies on a reduction to _directional variance queries_ , which we define
below.

######  Definition 1.1 (Directional variance).

For an $n\times d$ matrix $\boldsymbol{M}$, a _directional variance query_ is
specified by a unit-length direction $\boldsymbol{x}$, and is given by
$\Phi_{\boldsymbol{M}}(\boldsymbol{x})=\boldsymbol{x}^{\top}\boldsymbol{M}^{\top}\boldsymbol{M}\boldsymbol{x}$.

Privatization strategy for $\hat{\Omega}^{2}(\boldsymbol{X},\boldsymbol{Y})$:
We first express $\hat{\Omega}^{2}(\boldsymbol{X},\boldsymbol{Y})$ as a
function of i) a covariance matrix formed by incidence matrices (or a matrix
square root) of a specific weighted graph formed over samples in
$\boldsymbol{X}$ as its vertices (that we refer to as incidence-covariance)
and ii) the covariance matrix of $\boldsymbol{Y}$. We then show that
$\hat{\Omega}^{2}(\boldsymbol{X},\boldsymbol{Y})$ is exactly equal to a sum of
_directional variances_ of columns of $\boldsymbol{Y}$ with respect to the
incidence-covariance matrix of $\boldsymbol{X}$.

Privatization strategy for $\hat{S}(\boldsymbol{X},\boldsymbol{Y})$: We are
able to express $\hat{S}(\boldsymbol{X},\boldsymbol{Y})$ in a similar form as
$\hat{\Omega}^{2}(\boldsymbol{X},\boldsymbol{Y})$, but with some key
differences. Namely, we can write it as a function of the covariance of
$\boldsymbol{X}$ (given by $\boldsymbol{XX}^{\top}$) and a data-independent
graph Laplacian matrix
$\boldsymbol{L^{S}}=n\boldsymbol{I}-\boldsymbol{ee^{\top}}$. We show that this
is exactly equal to the sum of directional variances of the columns of
incidence matrix (or a matrix square root such that
$\boldsymbol{L^{S}}=\boldsymbol{BB^{\top}}$) with respect to covariance matrix
$\boldsymbol{XX}^{\top}$. A key difference with respect to the case of
${\hat{\Omega}^{2}(\boldsymbol{X},\boldsymbol{Y})}$ is that, in here, the
directional variance is with respect to the covariance matrix of
$\boldsymbol{X}$ while in ${\hat{\Omega}^{2}(\boldsymbol{X},\boldsymbol{Y})}$
the directional variance is with respect to the incidence-covariance matrix
defined over $\boldsymbol{X}$.

Therefore, in the notation of directional variances, we show that
${\hat{\Omega}^{2}(\boldsymbol{X},\boldsymbol{Y})}=\sum_{i}\Phi_{\boldsymbol{B(X)}}(\boldsymbol{y}_{i})$
where $\boldsymbol{y}_{i}$ refers to the $i$’th column of $\boldsymbol{Y}$,
and
$\hat{S}(\boldsymbol{X},\boldsymbol{Y})=\sum_{i}\Phi_{\boldsymbol{X}}(\boldsymbol{g}_{i})$
where $\boldsymbol{g}_{i}$ refers to the $i$’th column of $\boldsymbol{G}$. A
utility bound on computing directional variance queries upon privatization of
covariance matrices can be expressed in terms of additive and multiplicative
errors. We now define the structure of such approximations as below. In the
rest of the paper, for presentation simplicity, we refer to
${\hat{\Omega}^{2}}(\boldsymbol{X},\boldsymbol{Y})$ and
$\hat{S}(\boldsymbol{X},\boldsymbol{Y})$ by ${\hat{\Omega}^{2}}$ and
$\hat{S}$, respectively.

######  Definition 1.2 (Additive and multiplicative approximation).

We say a privacy mechanism that privatizes an estimate $\hat{A}(x)$ using
$\bar{A}(x)$, provides an _$(\eta,\tau,\nu)$ -approximation_, if the following
holds.

$\operatorname{Pr}\left[(1-\eta)\hat{A}(x)-\tau\leq{\bar{A}(x)}\leq(1+\eta)\hat{A}(x)+\tau\right]\geq
1-\nu.$

We use $\bar{\Omega}^{2},\bar{S}$ to denote the privatized versions of
$\hat{\Omega}^{2}$ and $\hat{S}$ respectively that can be obtained upon
privatization of the covariance matrix $\boldsymbol{XX^{\top}}$ and incidence-
covariance
$\boldsymbol{B}(\boldsymbol{X})\boldsymbol{B}^{\top}(\boldsymbol{X})$.

$\displaystyle\alpha_{\ell}\frac{\hat{\Omega}^{2}}{\hat{S}}+\beta_{\ell}\leq\frac{\bar{\Omega}^{2}}{\bar{S}}\leq\alpha_{u}\frac{\hat{\Omega}^{2}}{\hat{S}}+\beta_{u},$
(1)

In section 4, we first show that a privatization of covariances and incidence-
covariances results in separate additive and multiplicative approximations for
$\hat{\Omega}^{2}$ and $\hat{S}^{2}$ respectively. A first-pass attempt
towards using this result towards our main goal of an approximation of the
form in (1), just involves a simple rearrangement of the terms using the
individual bounds on $\hat{\Omega}^{2}$ and $\hat{S}$, leading us to the
following result with probability $\geq 1-2\nu$ where we have,
$\frac{(1-\eta)\hat{\Omega}^{2}-\tau}{(1+\eta)\hat{S}+\tau}\leq\frac{\bar{\Omega}^{2}}{\bar{S}}\leq\frac{(1+\eta)\hat{\Omega}^{2}+\tau}{(1-\eta)\hat{S}-\tau}.$
Unfortunately, this first attempt falls short of our goal, as the additive and
multiplicative errors in (1.3) do not decompose well to provide a more
convenient expression of the form in (1). Obtaining a final form of this kind
requires extra work, leading to our main result.

##  2 Preliminaries

Preliminaries for independence testing To formalise the problem of hypothesis
testing for independence, consider random variables $\mathcal{X}$ and
$\mathcal{Y}$ that have densities $f_{\mathcal{X}}$ on $\mathbb{R}^{d}$ and
$f_{\mathcal{Y}}$ on $\mathbb{R}^{m}$, respectively, and let
$\mathcal{Z}=(\mathcal{X},\mathcal{Y})$ have density $f$ on $\mathbb{R}^{q}$,
where $q\coloneqq d+m$. Given independent and identically distributed copies
$Z_{1},\ldots,Z_{n}$ of $\mathcal{Z}$, we wish to test the null hypothesis
that $\mathcal{X}$ and $\mathcal{Y}$ are independent, denoted
$H_{0}\colon\mathcal{X}\perp\\!\\!\\!\perp\mathcal{Y}$, against the
alternative hypothesis that $\mathcal{X}$ and $\mathcal{Y}$ are not
independent, denoted by
$H_{1}\colon\mathcal{X}\not\\!\perp\\!\\!\\!\perp\mathcal{Y}$. A distribution
$D$ is said to be _independent_ , if it is equal to the product of its
marginals.

Test-statistic A predominant methodology for hypothesis testing (in the non-
private setting) involves computation of a sample test statistic from the
data. The key idea is that the asymptotic distribution of a test statistic
(that can be estimated from data samples) is derived (and hence, known) upon
conditioning on the null hypothesis being true. Therefore, the observed value
of the sample test-statistic (a scalar) is compared with this asymptotic
distribution in conjunction with a chosen level of confidence to decide if the
observed value falls within the acceptance region or the rejection region. The
rejection region refers to the observed value of the sample test statistic
being highly unlikely given the asymptotic distribution, if the null
hypothesis was supposed to be true.
Preliminaries for differential privacy We now take a quick detour into
differential privacy. A widely used mathematical notion of privacy is that of
_differential privacy_ [Dwork et al., 2014], which we recall below.

######  Definition 2.1 ($(\epsilon,\delta)$-Differential Privacy [Dwork et
al., 2014]).

A randomized algorithm $\mathcal{A}:\mathcal{X}\to\mathcal{Y}$ is
$(\epsilon,\delta)$-differentially private, if, for all neighboring datasets
$\boldsymbol{X,X^{\prime}}\in\mathcal{X}$ and for all (measurable)
$M\subseteq\mathcal{Y}$, we have $\Pr[\mathcal{A}(\boldsymbol{X})\in M]\leq
e^{\epsilon}\Pr[\mathcal{A}(\boldsymbol{X^{\prime}})\in M]+\delta$ and two
datasets are said to be neighboring if they differ in a single element while
$\delta$ is a slack probability of a privacy-failure.

Post-Processing Invariance A major advantage is that differentially private
mechanisms are immune to post-processing, meaning that an adversary without
any additional knowledge about the dataset $\boldsymbol{X}$ cannot compute a
function on the output $\mathcal{A}(\boldsymbol{X})$ to violate the stated
privacy guarantees.

Preliminaries for energy statistics We introduce a measure of statistical
dependence called distance correlation. This is relevant because the test-
statistic that we use for independence testing is a function of distance
covariance (an un-normalized version of distance correlation).

Population distance covariance For random variables
$\mathcal{X}\in\mathbb{R}^{d}$ and $\mathcal{Y}\in\mathbb{R}^{m}$ with finite
first moments, the population distance covariance [Székely et al., 2007]
between them is a non-negative number given by
${\Omega}(\mathcal{X},\mathcal{Y})=\int_{\mathbb{R}^{d+m}}|f_{\mathcal{X},\mathcal{Y}}(t,s)-f_{\mathcal{X}}(t)f_{\mathcal{Y}}(s)|^{2}w(t,s)dtds$,where
$f_{\mathcal{X}},f_{\mathcal{Y}}$ are characteristic functions of
$\mathcal{X},\mathcal{Y}$, $f_{\mathcal{X},\mathcal{Y}}$ is the joint
characteristic function, and $w(t,s)$ is a weight function defined as
$w(t,s)=(C(d,\alpha)C(m,\alpha)|t|^{\alpha+d}_{d}|s|_{m}^{\alpha+m})^{-1}$,
with $C(d,\alpha)=\frac{2\pi^{d/2}\Gamma(1-\alpha/2)}{\alpha
2^{\alpha}\Gamma((\alpha+d)/2)}$ for chosen values of $\alpha$ which impacts
the choice of the norm. More details about this weight function and the
reasoning being its appropriateness for evaluating this integral is given in
Székely et al. [2007]. $\Gamma$ refers to the popular complete Gamma function,
that is defined to be an extension of the concept of a factorial to complex
and real numbers as opposed to just the integers. Note that for random
variables that admit a density, the characteristic function is the Fourier
transform of the probability density function. Note that, for complex-valued
functions such as the characteristic function used in (2), the norm is
dependent on itself and its complex conjugate $\bar{f}$ as $|f|^{2}=f\bar{f}$.
Estimators for distance covariance We first define
$a_{ij}=\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|^{2}$,
$b_{ij}=\left\|\boldsymbol{y}_{i}-\boldsymbol{y}_{j}\right\|^{2}$,
$a_{i}=\sum_{l=1}^{n}a_{il}$, $b_{i}=\sum_{l=1}^{n}b_{il}$,
$a=\sum_{k,l=1}^{n}a_{kl}$ and $b=\sum_{k,l=1}^{n}b_{kl}$. We now use these
quantities to define an unbiased statistical estimator of distance covariance
$\hat{\Omega}{{}^{2}}(\boldsymbol{X},\boldsymbol{Y})$ as follows.

$\hat{\Omega}{{}^{2}}(\boldsymbol{X},\boldsymbol{Y})=\frac{1}{n(n-3)}\sum_{i\neq
j}a_{ij}b_{ij}-\frac{2}{n(n-2)(n-3)}\sum_{i=1}^{n}a_{i}b_{i}+\frac{ab}{n(n-1)(n-2)(n-3)}$

A generalization to powers of the norm being other than 2, is referred to in
the literature as $\alpha-$distance correlation.

$\mathsf{\pi}\mathsf{-test}$ mechanism 1. Alice’s input: Data matrix
$\boldsymbol{X}_{n\times d}$, parameters for privacy ($\epsilon,\delta$),
confidence $\nu$ & error $\eta$. 2. Bob’s input: Data matrix $\boldsymbol{Y}$.
3. Alice’s side: Compute adjacency matrix
$\boldsymbol{W}(\boldsymbol{X})=\boldsymbol{J}\boldsymbol{E}_{\boldsymbol{X}}\boldsymbol{J}$
4. Alice’s side: Compute graph Laplacian
$\boldsymbol{L}^{\boldsymbol{W}}(\boldsymbol{X})$for adjacency of
$\boldsymbol{W}(\boldsymbol{X})$. 5. Alice’s side: Express
$\boldsymbol{L}^{\boldsymbol{W}}(\boldsymbol{X})$ as
$\boldsymbol{B(X)B(X)^{T}}$ via a matrix square-root. 6. Alice’s side:
Privatize covariances $\boldsymbol{B(X)B(X)^{T}}$ using either of Blocki et
al. [2012], Biswas et al. [2020], Amin et al. [2019]. Send them to Bob. 7.
Alice’s side: Compute $\boldsymbol{XX^{T}}$ and privatize these covariances as
in previous step. Send them to Bob. 8. Bob’s side: Compute
$\bar{\Omega}{{}^{2}}(\boldsymbol{X},\boldsymbol{Y})=\frac{1}{n}\sqrt{2\operatorname{Tr}\left(\boldsymbol{Y^{\top}L^{W}(X){Y}}\right)}$
using Alice’s private estimate of $\mathbb{L^{W}(X)}$. 9. Bob’s side: Compute
$\bar{S}(\boldsymbol{X},\boldsymbol{Y})=\frac{4}{n^{4}}\operatorname{Tr}\left(\boldsymbol{G}^{\boldsymbol{T}}\boldsymbol{X}\boldsymbol{X}^{\top}\boldsymbol{G}\right).\operatorname{Tr}\left(\boldsymbol{Y}^{\top}\boldsymbol{L}^{\boldsymbol{S}}\boldsymbol{Y}\right)$
using Alice’s private $\boldsymbol{XX^{\top}}$. 10. Bob’s side: Perform the
test-using a rejection region of
$\Gamma(\mathbb{X,Y},\alpha,n)=\frac{n\bar{\Omega}_{n}^{2}(\mathbb{X},\mathbb{Y})}{\bar{S}(\mathbb{X,Y})}>\left(\Phi^{-1}(1-\alpha/2)\right)^{2}$.
Figure 2: Protocol for the proposed $\pi$-test mechanism for two-party
independence testing

##  3 Test statistic for independence testing

The test-statistic we consider is a ratio of sample distance covariance (an
un-normalized measure of statistical dependency) denoted by
$\hat{\Omega}^{2}(\boldsymbol{X},\boldsymbol{Y})$ and a product of average of
distances denoted by $\hat{S}(\boldsymbol{X},\boldsymbol{Y})$ defined as
$\hat{S}(\boldsymbol{X},\boldsymbol{Y})=\frac{1}{n^{2}}\sum_{k,l=1}^{n}\left\|\boldsymbol{x}_{k}-\boldsymbol{x}_{l}\right\|^{2}\frac{1}{n^{2}}\sum_{k,l=1}^{n}\left\|\boldsymbol{y}_{k}-\boldsymbol{y}_{l}\right\|^{2}$.
In order to define the test statistic, we need to define distance covariance
denoted as
${\hat{\Omega}}^{2}(\boldsymbol{X},\boldsymbol{Y})=\hat{R}+\hat{S}-2\hat{T}\text{
where, }$

$\displaystyle\hat{R}=\frac{1}{n^{2}}\sum_{k,l=1}^{n}\left\|\boldsymbol{x}_{k}-\boldsymbol{x}_{l}\right\|^{2}\left\|\boldsymbol{y}_{k}-\boldsymbol{y}_{l}\right\|^{2},$
$\displaystyle\hat{S}=\frac{1}{n^{2}}\sum_{k,l=1}^{n}\left\|\boldsymbol{x}_{k}-\boldsymbol{x}_{l}\right\|^{2}\frac{1}{n^{2}}\sum_{k,l=1}^{n}\left\|\boldsymbol{y}_{k}-\boldsymbol{y}_{k}\right\|^{2},$
$\displaystyle\hat{T}=\frac{1}{n^{3}}\sum_{k=1}^{n}\sum_{l,m=1}^{n}\left\|\boldsymbol{x}_{k}-\boldsymbol{x}_{l}\right\|^{2}\left\|\boldsymbol{y}_{k}-\boldsymbol{y}_{l}\right\|^{2}.$

We use $\Gamma(X,Y,\alpha,n)$ to denote the test statistic Székely et al.
[2007] that rejects independence when

$\Gamma(\mathbb{X,Y},\alpha,n)=\frac{n\hat{\Omega}^{2}(\mathbb{X},\mathbb{Y})}{\hat{S}(\mathbb{X,Y})}>\left(\phi^{-1}(1-\alpha/2)\right)^{2},$

where $\phi(\cdot)$ denotes the standard normal cumulative distribution
function, and $\alpha$ denotes the achieved significance level. A test
rejecting independence of $X$ and $Y$ when
$\sqrt{n\hat{\Omega}^{2}(\boldsymbol{X,Y})/\hat{S}(\boldsymbol{X,Y})}\geq\phi^{-1}(1-$
$\alpha/2)$ is said to have an asymptotic significance level of at most
$\alpha$.

##  4 Privatization of test statistic

We first express the numerator and denominator of the test-statistic as
different functions of directional variance. This is useful because the
directional variance in our case is solely a function of a specific covariance
(specific to the choice of numerator or denominator) of our sensitive data and
the non-sensitive $\boldsymbol{Y}$. Therefore, the directional variances
corresponding to numerator and denominator of test-statistic is private upon
applying the post-processing property of differential privacy after
privatization of that specific covariance. The following two results express
the numerator $\hat{\Omega}^{2}(\boldsymbol{X,Y})$ in terms of directional
variance.

######  Lemma 4.1.

Distance covariance $\hat{\Omega}^{2}\boldsymbol{(X,Y)}$ can be estimated
using the Euclidean distance matrix $\boldsymbol{E_{X}}$ formed over the rows
in $\boldsymbol{X}$, the double-centering matrix
$\boldsymbol{J=I}-n^{-1}\boldsymbol{ee^{T}}$, to form an adjacency matrix
given by $\boldsymbol{W(X)=JE_{X}J}$ and a corresponding graph Laplacian
$\boldsymbol{L^{W}(X)=D(W(X))-W(X)}$ where $\boldsymbol{D(W(X))}$ is the
degree matrix of $\boldsymbol{W(X)}$ to get

${\hat{\Omega}{{}^{2}}(\boldsymbol{X},\boldsymbol{Y})=\frac{1}{n}\sqrt{2\operatorname{Tr}\left(\boldsymbol{Y^{\top}L^{W}(X){Y}}\right)}=\frac{1}{n}\sqrt{2\operatorname{Tr}\left(\boldsymbol{X^{\top}L^{W}(Y){X}}\right)}}$

###### Proof.

The proof is provided in supplementary material. ∎

Now that distance covariance has been expressed in-terms of a specific graph
Laplacian, the following corollary follows to reformulate it as a sum of
specific kinds of directional variances that depend on this graph Laplacian.

######  Corollary 4.1.1.

Distance covariance can be expressed as a sum of directional variances as
$\hat{\Omega}^{2}(\boldsymbol{X,Y})=\sum_{i}\Phi_{\boldsymbol{B(X)}}(\boldsymbol{y}_{i})$
where directional variance was defined above in definition 1.1.

###### Proof.

We expand the distance covariance estimator as follows to get this result.

$\displaystyle\hat{\Omega}^{2}(\boldsymbol{X,Y})$
$\displaystyle=\operatorname{Tr}\left(\boldsymbol{X}^{\mathrm{T}}\boldsymbol{L}^{\boldsymbol{W}}(\boldsymbol{Y)}\boldsymbol{X}\right)=\operatorname{Tr}\left(\boldsymbol{X}\boldsymbol{X}^{\mathrm{T}}\boldsymbol{L}^{\boldsymbol{W}}(\boldsymbol{Y})\right)=\sum_{i}^{d}\left(\boldsymbol{X_{i}^{T}\boldsymbol{L}^{\boldsymbol{W}}(\boldsymbol{Y})X_{i}}\right)$
(2)
$\displaystyle=\sum_{i=1}^{d}\operatorname{Tr}\left(\boldsymbol{X_{i}}\boldsymbol{X_{i}}^{\mathrm{T}}\boldsymbol{L}^{\boldsymbol{W}}(\boldsymbol{Y})\right)=\sum_{i=1}^{m}\operatorname{Tr}\left(\boldsymbol{Y_{i}}\boldsymbol{Y_{i}}^{\mathrm{T}}\boldsymbol{L}^{\boldsymbol{W}}(\boldsymbol{X})\right)=\sum_{i=1}^{m}\operatorname{Tr}\left(\boldsymbol{Y_{i}}\boldsymbol{Y_{i}}^{\mathrm{T}}\boldsymbol{B}(\boldsymbol{X})\boldsymbol{B}^{T}(\boldsymbol{X})\right)$
$\displaystyle=\sum_{i}^{m}\left(\boldsymbol{Y_{i}^{T}\boldsymbol{B}(\boldsymbol{X})\boldsymbol{B}^{T}(\boldsymbol{X})Y_{i}}\right)=\sum_{i=1}^{m}\hat{\Omega}_{i}(\boldsymbol{X,Y})=\sum_{i}\Phi_{\boldsymbol{B(X)}}(\boldsymbol{Y}_{i})$
(3)

∎

######  Lemma 4.2.

We now express the denominator term of the test-statistic as a specific sum of
directional variances as follows. The denominator in the test-statistic,

${\hat{S}}(\boldsymbol{X,Y})=\frac{1}{n^{2}}\sum_{k,l=1}^{n}\left\|\boldsymbol{x}_{k}-\boldsymbol{x}_{l}\right\|^{2}\frac{1}{n^{2}}\sum_{k,l=1}^{n}\left\|\boldsymbol{y}_{k}-\boldsymbol{y}_{l}\right\|^{2},$

can be expressed as a sum of directional variances as
$\hat{S}(\boldsymbol{X,Y})=\sum_{i}\phi_{\boldsymbol{X}}(\boldsymbol{g_{i}})$
where $\boldsymbol{g}_{i}$ is the $i$’th column of a matrix $\boldsymbol{G}$
such that $\boldsymbol{L^{S}}=\boldsymbol{G}\boldsymbol{G}^{T}$ for a graph
Laplacian matrix $\mathbb{L^{S}}$ given by
$\mathbb{L^{S}}=n\boldsymbol{I-ee^{T}}$. We use the superscript
$\boldsymbol{S}$ to distinguish from the Laplacian $\boldsymbol{L^{W}}$ used
in the expression for $\hat{\Omega}^{2}$.

###### Proof.

The proof is provided in supplementary material. ∎

The privatization strategy therefore is to privatize
$\boldsymbol{B(X)B^{T}(X)}$ in order to privatize
$\hat{\Omega}^{2}(\boldsymbol{X,Y})=\sum_{i}\phi_{\boldsymbol{B(X)}}(\boldsymbol{y}_{i})$.
This privatizes the numerator of the test-statistic. With regards to the
denominator, the strategy is to privatize $\boldsymbol{XX^{T}}$ in order to
privatize
$\hat{S}(\boldsymbol{X,Y})=\sum_{i}\phi_{\boldsymbol{X}}(\boldsymbol{g_{i}})$.
Note that in both cases, the privatization required is with respect to
covariance matrices. Privatization of covariances was studied in Blocki et al.
[2012], Amin et al. [2019], Biswas et al. [2020]. We summarize our proposed
mechanism called $\pi$-test in Figure 2. With covariance matrices being
central to many down-stream queries, the question of understanding the effect
of their privatization on utility of downstream queries often arises.

###  4.1 Utility results

In that spirit, the work in Blocki et al. [2012] provides a utility analysis
of directional variances (expressed as functions of covariances) upon
privatization of these covariances. This utility bound is formulated in terms
of additive and multiplicative errors as part of a probability bound. The
notion of additive and multiplicative approximation was defined in
preliminaries under definition 1.2. This result only provides us individual
bounds (with additive and multiplicative factors) separately for each summand
(in summation of directional variances) in the numerator and denominator of
our test-statistic. But we need a single bound (with additive and
multiplicative factors) for the test-statistic in its entirety, which is a
ratio of sums of directional variances. The following results that we workout
in the rest of the paper lets us obtain that bound. We denote each summand in
the sum of directional variances corresponding to the numerator and
denominator by ${\hat{\Omega}_{i}^{2}}$ for $i\in[1,2\ldots m]$ and
${\hat{S}_{i}}$ for $i\in[1,2\ldots,k\leq n]$, respectively, where $k$ denotes
the rank of $\boldsymbol{G}$. That is,
$\hat{\Omega}^{2}=\sum_{i}\hat{\Omega}_{i}^{2}=\sum_{i}\phi_{\boldsymbol{B(X)}}(\boldsymbol{y}_{i})$
and
$\hat{S}=\sum_{i}{\hat{S}}_{i}=\sum_{i}\phi_{\boldsymbol{X}}(\boldsymbol{g_{i}})$.

We use $\bar{\Omega}^{2}_{i},\bar{S}_{i}$ to denote the privatized versions of
$\hat{\Omega}^{2}_{i}$ and $\hat{S}_{i}$ respectively that can be obtained
upon privatization of the covariance matrix $\boldsymbol{XX^{\top}}$ and
incidence-covariance
$\boldsymbol{B}(\boldsymbol{X})\boldsymbol{B}^{\top}(\boldsymbol{X})$. As a
starting point, Blocki et al. [2012] provided these additive and
multiplicative error bounds using $r=\frac{8\ln(2/\nu)}{\eta^{2}}\text{,
}w=\frac{16\sqrt{r\ln(2/\delta)}}{\epsilon}\ln(16r/\delta)$ for utility of a
single directional variance query expressed using private covariance, which in
our setting refers to ${\bar{\Omega}^{2}_{i}}$ and ${\bar{S}_{i}}$ for any
$i\in[1,2\ldots,k\leq n]$.

$\displaystyle\mathbb{P}\left((1-\eta)\hat{\Omega}_{i}^{2}-\tau\leq\bar{\Omega}_{i}^{2}\leq(1+\eta)\hat{\Omega}_{i}^{2}+\tau\right)\geq
1-\nu,$ (4)

and similarly for $S$ as

$\displaystyle\mathbb{P}\left((1-\eta)\hat{S}_{i}-\tau\leq\bar{S}_{i}\leq(1+\eta)\hat{S}_{i}+\tau\right)\geq
1-\nu.$ (5)

But we need a bound on the ratio of summation of specific directional
variances. From the inequality on the intersection of $e$ events
$E_{1},...,E_{e}$ given as
$\mathbb{P}(\cap_{i=1}^{e}E_{i})\geq\sum_{i=1}^{e}\mathbb{P}(E_{i})-(e-1)$,
for $\nu\geq 1/(m+n)$, it follows that

$\displaystyle\mathbb{P}\left((1-\eta)\hat{\Omega}^{2}-m\tau\leq\bar{\Omega}^{2}\leq(1+\eta)\hat{\Omega}^{2}+m\tau\right)\geq
1-m\nu,$ (6)

and

$\displaystyle\mathbb{P}\left((1-\eta)\hat{S}-n\tau\leq\bar{S}\leq(1+\eta)\hat{S}+n\tau\right)\geq
1-n\nu.$ (7)

We now provide results for our lower and upper bounds.

floatrowsep=qquad [3][] [] []

Figure 3: Privacy-utility trade offs ($\epsilon$ vs⋅mean % relative error &
std.dev) for test-statistic estimates with 50 replications using $\eta=0.05$
(red) & $\eta=0.1$ (blue). Figure 4: Privacy-utility trade offs ($\epsilon$
vs⋅mean % relative error & std.dev) for $\bar{S}$ estimates with 50
replications using $\eta=0.05$ (red) & $\eta=0.1$. (blue). Figure 5: Privacy-
utility trade offs ($\epsilon$ vs⋅mean % relative error & std.dev) for
$\bar{\Omega}^{2}$ estimates with 50 replications using $\eta=0.05$ (red) &
$\eta=0.1$.

####  4.1.1 Lower bound

######  Theorem 4.3.

For $S>\frac{n\tau}{1-n}$ and $n\gg m$, we have the following lower bound on
$\frac{\bar{\Omega}^{2}}{\bar{S}}$.

$\mathbb{P}\left(\frac{\bar{\Omega}^{2}}{\bar{S}}\geq\frac{1-\eta}{1+\eta}\left(\frac{\hat{\Omega}}{\hat{S}}\right)-\frac{2}{1-\eta}\right)\geq
1-(m+n)\nu.$

###### Proof.

The proof is provided in supplementary. ∎

####  4.1.2 Upper bound

######  Theorem 4.4.

For some $s>\frac{\tau}{1-\eta}$ and $n\gg m$, we have the following upper
bound on $\frac{\bar{\Omega}^{2}}{\bar{S}}$.

$\mathbb{P}\left(\frac{\bar{\Omega}^{2}}{\bar{S}}\leqslant\frac{1+\eta}{1-\eta}\left(\frac{\hat{\Omega}^{2}}{\hat{S}}\right)+\frac{\tau}{(1-\eta)s-\tau}\right)\geq
1-(m+n)\nu.$

###### Proof.

The proof is provided in supplementary.∎

Although, the primary contribution of our paper is theoretical, we perform a
brief empirical utilility analysis of our mechanism using the publicly
available BostonHousing dataset. We share the privacy-utility trade-offs of
our private estimator of the test-statistic in Figure 5 for varying values of
$\epsilon$, for a $\delta=0.0002$. We measure utility using relative error (in
%), also referred to as percent error for two values of $\eta=0.05$ and
$\eta=0.1$. We also study this trade-off in individually understanding the
utility of the denominator (in Figure 5) and numerator (in Figure 5) of the
test-statistic.

##  5 Conclusion

Current works on private independence testing focus on discrete data
(contingency tables) and is based on stringent minimax testing under total
variation distance, which might be overly conservative in many settings. Our
work differs in this sense in terms of distributed model assumed (the way the
data is partitioned across users), being compatible with continuous data, its
applicability to samples lying in different dimensions unlike these prior
methods. While information-theoretic formulations are fairly matured,
inference with energy statistics in general brings a newer viewpoint to
private testing problems.

##  6 Limitations and future work

That said, universality results on power analysis of distance covariance based
tests are being formulated by various groups in recent preprints such as Han
and Shen [2021]. A further analysis of our test from this viewpoint is needed
as part of future work. Although, we used the privacy mechanism for covariance
given in Blocki et al. [2012] as part of our $\pi$-test protocol, other
options such as [Biswas et al., 2020, Amin et al., 2019] could be used and
theoretical effects of their utility in privatizing the test-statistic is of
open interest. We used Blocki et al. [2012] given it’s suitability to our
theoretical study. Similarly, the question of coming up with mechanisms for
private conditional independence testing using conditional distance covariance
is still of open interest.

##  Appendix A Lower bound

######  Theorem.

For $\hat{S}>\frac{n\tau}{1-n}$ and $n\gg m$, we have the following lower
bound on $\frac{\bar{\Omega}^{2}}{\bar{S}}$.

$\mathbb{P}\left(\frac{\bar{\Omega}^{2}}{\bar{S}}\geq\frac{1-\eta}{1+\eta}\left(\frac{\hat{\Omega}}{\hat{S}}\right)-\frac{(1-\eta)^{2}}{2(1+\eta)}\right)\geq
1-(m+n)\nu.$

###### Proof.

From the naive re-arrangement of the individual bounds, we have the following
with probability $\geq 1-(m+n)\nu$

$\displaystyle\frac{(1-\eta)\hat{\Omega}^{2}-m\tau}{(1+\eta)\hat{S}+n\tau}\leq\frac{\bar{\Omega}^{2}}{\bar{S}}\leq\frac{(1+\eta)\hat{\Omega}^{2}+m\tau}{(1-\eta)\hat{S}-n\tau}.$
(8)

Rearranging the lower bound on $\frac{\bar{\Omega}^{2}}{\bar{S}}$ yields

$\displaystyle\frac{\bar{\Omega}^{2}}{\bar{S}}$
$\displaystyle\geqslant\frac{(1-\eta)\hat{\Omega}^{2}-m\tau}{(1+\eta)\hat{S}+n\tau}=\frac{(1-\eta)\hat{\Omega}^{2}-m\tau}{(1+\eta)\hat{S}\left(1+\frac{n\tau}{(1+\eta)\hat{S}}\right)}=\frac{(1-\eta)\hat{\Omega}^{2}\left(1+\frac{n\tau}{(1+\eta)\hat{S}}\right)-m\tau-\frac{(1-\eta)\hat{\Omega}^{2}n\tau}{(1+\eta)\hat{S}}}{(1+\eta)\hat{S}\left(1+\frac{n\tau}{(1+\eta)\hat{S}}\right)}$
$\displaystyle=\left(\frac{1-\eta}{1+\eta}\right)\frac{\hat{\Omega}^{2}}{\hat{S}}-\frac{m\tau(1+\eta)\hat{S}+n\tau(1-\eta)\hat{\Omega}^{2}}{(1+\eta)\hat{S}\left((1+\eta)\hat{S}+n\tau\right)}.$
(9)

For $\hat{S}>\frac{n\tau}{1-\eta}$, we have

$\displaystyle\frac{m\tau(1+\eta)\hat{S}+n\tau(1-\eta)\hat{\Omega}^{2}}{(1+\eta)\hat{S}\left((1+\eta)\hat{S}+n\tau\right)}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny(a)}}}{\leq}}\frac{m\tau(1+\eta)+n\tau(1-\eta)}{(1+\eta)\left((1+\eta)\hat{S}+n\tau\right)}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny(b)}}}{\leq}}\frac{m(1+\eta)+n(1-\eta)}{2n\left(\frac{1+\eta}{1-\eta}\right)},$
(10)

where (a) follows from Lemma C.1, i.e., $\hat{\Omega}^{2}\leq\hat{S}$, and (b)
follows by replacing $\hat{S}$ with $\frac{n\tau}{1-\eta}$ since
$\hat{S}>\frac{n\tau}{1-\eta}$. For $n\gg m$, we can approximate (10) as
follows

$\displaystyle\frac{m\tau(1+\eta)\hat{S}+n\tau(1-\eta)\hat{\Omega}^{2}}{(1+\eta)\hat{S}\left((1+\eta)\hat{S}+n\tau\right)}\leq\frac{m(1+\eta)+n(1-\eta)}{2n\left(\frac{1+\eta}{1-\eta}\right)}\approx\frac{(1-\eta)^{2}}{2(1+\eta)}.$
(11)

Plugging (11) into (A) yields

$\displaystyle\frac{\bar{\Omega}^{2}}{\bar{S}}\geq\left(\frac{1-\eta}{1+\eta}\right)\frac{\hat{\Omega}^{2}}{\hat{S}}-\frac{(1-\eta)^{2}}{2(1+\eta)}$
(12)

∎

##  Appendix B Upper bound

######  Theorem.

For some $s>\frac{\tau}{1-\eta}$ and $n\gg m$, we have the following upper
bound on $\frac{\bar{\Omega}^{2}}{\bar{S}}$.

$\mathbb{P}\left(\frac{\bar{\Omega}^{2}}{\bar{S}}\leqslant\frac{1+\eta}{1-\eta}\left(\frac{\hat{\Omega}^{2}}{\hat{S}}\right)+\frac{\tau}{(1-\eta)s-\tau}\right)\geq
1-(m+n)\nu.$

###### Proof.

Rearranging the upper bound on $\frac{\bar{\Omega}^{2}}{\bar{S}}$, given in
(8), yields

$\displaystyle\frac{\bar{\Omega}^{2}}{\bar{S}}$
$\displaystyle\leq\frac{(1+\eta)\hat{\Omega}^{2}+m\tau}{(1-\eta)\hat{S}\left(1-\frac{n\tau}{(1-\eta)\hat{S}}\right)}=\frac{(1+\eta)\hat{\Omega}^{2}\left(1-\frac{n\tau}{(1-\eta)\hat{S}}\right)+m\tau+\frac{(1+\eta)\hat{\Omega}^{2}n\tau}{(1-\eta)\hat{S}}}{(1-\eta)\hat{S}\left(1-\frac{n\tau}{(1-\eta)\hat{S}}\right)}$
$\displaystyle=\left(\frac{1+\eta}{1-\eta}\right)\frac{\hat{\Omega}^{2}}{\hat{S}}+\frac{m\tau(1-\eta)\hat{S}+n\tau(1+\eta)\hat{\Omega}^{2}}{(1-\eta)\hat{S}\left((1-\eta)\hat{S}-n\tau\right)}.$
(13)

We have

$\displaystyle\frac{m\tau(1-\eta)\hat{S}+n\tau(1+\eta)\hat{\Omega}^{2}}{(1-\eta)\hat{S}\left((1-\eta)\hat{S}-n\tau\right)}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny(a)}}}{\leq}}\frac{m\tau(1-\eta)+n\tau(1+\eta)}{(1-\eta)\left((1-\eta)\hat{S}-n\tau\right)}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny(b)}}}{\leq}}\frac{m\tau(1-\eta)+n\tau(1+\eta)}{(1-\eta)\left((1-\eta)ns-n\tau\right)},$
(14)

where (a) follows from Lemma C.1, i.e., $\hat{\Omega}^{2}\leq\hat{S}$, and (b)
follows since $S\geq ns$, for some $s>\frac{\tau}{1-\eta}$. For $n\gg m$, (14)
is approximated as

$\displaystyle\frac{m\tau(1-\eta)\hat{S}+n\tau(1+\eta)\hat{\Omega}^{2}}{(1-\eta)\hat{S}\left((1-\eta)\hat{S}-n\tau\right)}\leq\frac{m\tau(1-\eta)+n\tau(1+\eta)}{(1-\eta)\left((1-\eta)ns-n\tau\right)}\approx\frac{\tau}{(1-\eta)s-\tau}.$
(15)

Plugging (15) into (B) yields

$\displaystyle\frac{\hat{\Omega}^{2}}{\hat{S}}\leq\left(\frac{1+\eta}{1-\eta}\right)\frac{\Omega^{2}}{S}+\frac{\tau}{(1-\eta)s-\tau}.$
(16)

∎

##  Appendix C Error bound on ratio of estimators

######  Lemma C.1.

Assuming that $d_{\rm{max}}/d_{\rm{min}}^{2}\leq\frac{(n-1)}{2}$, where
$d_{\rm{max}}=\max_{i,j}\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|^{2}$
and $d_{\rm{min}}=\min_{i,j,i\neq
j}\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|^{2}$, we have
$\Omega^{2}\leq S$.

###### Proof.

We have

$\displaystyle\Omega^{2}$
$\displaystyle=\frac{1}{n}\sqrt{2\operatorname{Tr}\left(\boldsymbol{Y}^{\top}\boldsymbol{L_{X}{Y}}\right)}=\frac{1}{n}\sqrt{\sum_{i,j}{W^{X}_{i,j}}\left\|\boldsymbol{y}_{i}-\boldsymbol{y}_{j}\right\|^{2}}$
$\displaystyle=\frac{1}{n}\sqrt{\sum_{i,j}{[\boldsymbol{JE_{X}J}]_{i,j}}\left\|\boldsymbol{y}_{i}-\boldsymbol{y}_{j}\right\|^{2}},$
(17a) $\displaystyle S$
$\displaystyle=\frac{1}{n^{4}}\sum_{i,j}\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|^{2}\sum_{i,j}\left\|\boldsymbol{y}_{i}-\boldsymbol{y}_{j}\right\|^{2}.$
(17b)

Assuming that there are a total of $c$ classes in the dataset, we denote by
$\mathcal{C}_{l}$ the set of data samples indices that belong to the label
$l$, $l=0,...,c-1$. For $i\in\mathcal{C}_{l}$, we assume that
$\boldsymbol{y}_{i}$ is a vector with only one non-zero entry at the $l$-th
coordinate, where for simplicity we set the value in the $l$-th coordinate to
1. Accordingly, for $l=0,...,c-1$, we have

$\displaystyle\left\|\boldsymbol{y}_{i}-\boldsymbol{y}_{j}\right\|^{2}=\begin{cases}0,&i,j\in\mathcal{C}_{l}\\\
2,&\mbox{otherwise},\end{cases}$ (18)

which results in

$\displaystyle\Omega^{2}$
$\displaystyle=\frac{1}{n}\sqrt{2\sum_{i,j,(i,j)\notin\mathcal{C}_{l}^{2}}{[\boldsymbol{JE_{X}J}]_{i,j}}}$
$\displaystyle\leq\frac{1}{n}\sqrt{2\sum_{i,j}{[\boldsymbol{JE_{X}J}]_{i,j}}}$
$\displaystyle\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny(a)}}}{=}}\frac{1}{n}\sqrt{\frac{2}{n}\sum_{i,j}\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|^{2}},$
(19)

where (a) follows from Lemma D.1. For simplicity of the analysis, we assume
that the number of data samples with each class is uniform, i.e.,
$\left|\mathcal{C}_{l}\right|=n/c$, in which case
$\sum_{i,j}\left\|\boldsymbol{y}_{i}-\boldsymbol{y}_{j}\right\|^{2}=2n^{2}(1-1/c)$.
Accordingly, we have

$\displaystyle S$
$\displaystyle=\frac{2(1-1/c)}{n^{2}}\sum_{i,j}\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|^{2},$
(20)

which is minimized for $c=2$ (assuming that $c\geq 2$), i.e.,

$\displaystyle
S\geq\frac{1}{n^{2}}\sum_{i,j}\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|^{2}.$
(21)

According to (C) and (21), in order to prove $\Omega^{2}\leq S$, it suffices
to show that

$\displaystyle\sum_{i,j}\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|^{2}\leq\frac{1}{2n}\Big{(}\sum_{i,j}\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|^{2}\Big{)}^{2}.$
(22)

We have

$\displaystyle\sum_{i,j}\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|^{2}$
$\displaystyle\leq n(n-1)d_{\rm{max}},$
$\displaystyle\frac{1}{2n}\Big{(}\sum_{i,j}\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|^{2}\Big{)}^{2}$
$\displaystyle\geq\frac{n^{2}(n-1)^{2}}{2n}d_{\rm{min}}^{2}.$ (23)

Accordingly, having $d_{\rm{max}}\leq\frac{(n-1)}{2}d_{\rm{min}}^{2}$
guarantees (22).

∎

##  Appendix D Double-centering lemmas

######  Lemma D.1.

For the centering matrix given by
$\boldsymbol{J}=\boldsymbol{I}-\frac{1}{n}\boldsymbol{ee}^{\top}$, we have the
following property when applied to Euclidean distance matrices of data sample
$X$ denoted by $E_{X}$,

$\sum_{i,j}\left[\boldsymbol{JE_{X}J}\right]_{i,j}=\frac{1}{n}\sum_{i,j}d_{i,j}^{2}(X)$

###### Proof.

We have

$\displaystyle\boldsymbol{JE_{X}J}=\left(\boldsymbol{I}-\frac{1}{n}\boldsymbol{ee}^{\top}\right)\boldsymbol{E_{X}}\left(\boldsymbol{I}-\frac{1}{n}\boldsymbol{ee}^{\top}\right)$
(24)
$\displaystyle=\boldsymbol{E_{X}}-\frac{1}{n}\boldsymbol{ee}^{\top}\boldsymbol{E_{X}}-\frac{1}{n}\boldsymbol{E_{X}ee}^{\top}+\frac{1}{n^{2}}\boldsymbol{ee}^{\top}\boldsymbol{E_{X}ee}^{\top},$
(25)

according to which

$\displaystyle\left(\boldsymbol{JE_{X}J}\right)_{ij}=d_{ij}^{2}(\boldsymbol{X})-\frac{1}{n}\sum_{i^{\prime}=1}^{n}d_{i^{\prime}j}^{2}(\boldsymbol{X})-\frac{1}{n}\sum_{j^{\prime}=1}^{n}d_{ij^{\prime}}^{2}(\boldsymbol{X})+\frac{1}{n^{2}}\sum_{i^{\prime}j^{\prime}}d_{i^{\prime}j^{\prime}}^{2}(\boldsymbol{X}).$
(26)

Summing (26) over all $i,j$ yields

$\displaystyle\sum_{i,j}\left[\boldsymbol{JE_{X}J}\right]_{ij}=$
$\displaystyle\sum_{i,j}d_{ij}^{2}(\boldsymbol{X})-\frac{1}{n}\sum_{i,j}\sum_{i^{\prime}=1}^{n}d_{i^{\prime}j}^{2}(\boldsymbol{X})$
(27)
$\displaystyle-\frac{1}{n}\sum_{i,j}\sum_{j^{\prime}=1}^{n}d_{i^{\prime}j^{\prime}}^{2}(\boldsymbol{X})+\frac{n(n-1)}{n^{2}}\sum_{i^{\prime},j^{\prime}}d_{i^{\prime}j^{\prime}}^{2}(\boldsymbol{X})$
(28) $\displaystyle=$
$\displaystyle\sum_{ij}d_{ij}^{2}(\boldsymbol{X})-\frac{n-1}{n}\sum_{ij}d_{ij}^{2}(\boldsymbol{X})-\frac{n-1}{n}\sum_{i,j}d_{ij}^{2}(\boldsymbol{X})+\frac{n-1}{n}\sum_{i,j}d_{ij}^{2}(\boldsymbol{X})$
(29) $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i,j}d_{ij}^{2}(\boldsymbol{X}).$ (30)

∎

######  Lemma D.2.

The data matrix $\boldsymbol{X}$ and its Euclidean distance matrix
$\boldsymbol{E_{X}}$ can be connected using the centering matrix given by
$\boldsymbol{J}=\boldsymbol{I}-\frac{1}{n}\boldsymbol{ee}^{\top}$ as,

$\boldsymbol{JX^{T}XJ}=-\frac{1}{2}\boldsymbol{JE_{X}J}$

###### Proof.

$\displaystyle\left(\left\|\mathbb{x}_{i}-\mathbb{x}_{j}\right\|^{2}=\mathbb{x}_{i}^{\top}\mathbb{x}_{i}+\mathbb{x}_{j}^{\top}\mathbb{x}_{j}-2\mathbb{x}_{i}^{\top}\mathbb{x}_{j}\right)$
(31)
$\displaystyle\mathbb{x}_{i}^{T}\mathbb{x}_{j}=-\frac{1}{2}\left(\left\|\mathbb{x}_{i}-\mathbb{x}_{j}\right\|^{2}-\left\|\mathbb{x}_{i}\right\|^{2}-\left\|\mathbb{x}_{j}\right\|^{2}\right)$
(32)
$\displaystyle\mathbb{X}^{T}\mathbb{X}=\frac{-1}{2}\mathbb{E}_{\mathbb{X}}+\frac{1}{2}\mathbb{\delta.1}^{T}+\frac{1}{2}\mathbb{1\delta}^{T}\textrm{
where }\delta\textrm{ is a vector with }\delta_{i}=\|\mathbb{x}_{i}\|.$ (33)
$\mathbb{JX^{T}XJ}=-\frac{1}{2}\mathbb{JE_{X}J}+\frac{1}{2}J\mathbb{\delta}.\mathbb{1}^{T}\mathbb{J}+\frac{1}{2}\mathbb{J1\delta}^{T}\mathbb{J}$

But since, $\mathbb{1}^{T}\mathbb{J}=0$ and $\mathbb{J1}=\mathbb{0}$, we have

$\mathbb{JX}^{T}\mathbb{XJ}=-\frac{1}{2}\mathbb{JE_{X}J}$

∎

##  Appendix E Proof of Lemma C.1

We have

$\displaystyle\Omega^{2}(\mathbb{X,Y})$
$\displaystyle=\frac{1}{n}\sqrt{2\operatorname{Tr}\left(\mathbb{Y}^{\top}\mathbb{L_{X}{Y}}\right)}=\frac{2}{n^{2}}\sum_{ij}{\mathbb{W}^{\mathbb{{X}}}_{ij}}d_{ij}^{2}(\mathbb{Y})$
$\displaystyle=\frac{1}{n}\sqrt{\sum_{ij}{[\mathbb{JE_{X}J}]_{ij}}d_{ij}^{2}(\mathbb{Y})}.$

##  Appendix F Laplacian formulation of $\Omega^{2}(\mathbb{X,Y})$ Vepakomma
et al. [2018]

######  Lemma F.1.

Distance covariance $\hat{\Omega}^{2}\boldsymbol{(X,Y)}$ can be estimated
using the Euclidean distance matrix $\boldsymbol{E_{X}}$ formed over the rows
in $\boldsymbol{X}$, the double-centering matrix
$\boldsymbol{J=I}-n^{-1}\boldsymbol{ee^{T}}$, to form an adjacency matrix
given by $\boldsymbol{W(X)=JE_{X}J}$ and a corresponding graph Laplacian
$\boldsymbol{L^{W}(X)=D(W(X))-W(X)}$ where $\boldsymbol{D(W(X))}$ is the
degree matrix of $\boldsymbol{W(X)}$ to get

${\hat{\Omega}{{}^{2}}(\boldsymbol{X},\boldsymbol{Y})=\frac{1}{n}\sqrt{2\operatorname{Tr}\left(\boldsymbol{Y^{\top}L^{W}(X){Y}}\right)}=\frac{1}{n}\sqrt{2\operatorname{Tr}\left(\boldsymbol{X^{\top}L^{W}(Y){X}}\right)}}$

###### Proof.

This result and corresponding proof is from Vepakomma et al. [2018]. We
replicate the same over here for quick reference. Given matrices
$\widehat{\boldsymbol{E}}_{\boldsymbol{X}},\widehat{\boldsymbol{E}}_{\boldsymbol{Y}}$,
and column centered matrices
$\widetilde{\boldsymbol{X}},\tilde{\boldsymbol{Y}}$, from result of Torgerson
[1952] we have that
$\widehat{\boldsymbol{E}}_{\boldsymbol{X}}=-2\widetilde{\boldsymbol{X}}\widetilde{\boldsymbol{X}}^{T}$
and
$\widehat{\boldsymbol{E}}_{\boldsymbol{Y}}=-2\widetilde{\boldsymbol{Y}}\tilde{\boldsymbol{Y}}^{T}$.
In the problem of multidimensional scaling (MDS) (Borg and Groenen, 2005), we
know for a given adjacency matrix say $\boldsymbol{W}$ and a Laplacian matrix
$\boldsymbol{L}$,

$\operatorname{Tr}\left(\boldsymbol{X}^{T}\boldsymbol{L}\boldsymbol{X}\right)=\frac{1}{2}\sum_{i,j}[\boldsymbol{W}]_{ij}[\boldsymbol{E}_{\boldsymbol{X}}]_{i,j}$

Now for the Laplacian $\boldsymbol{L}=\boldsymbol{L}_{\boldsymbol{X}}$ and
adjacency matrix $\boldsymbol{W}=\widehat{\boldsymbol{E}}_{\boldsymbol{Y}}$ we
can represent
$\operatorname{Tr}\left(\boldsymbol{X}^{T}\boldsymbol{L}_{\boldsymbol{Y}}\boldsymbol{X}\right)$
in terms of $\widehat{\boldsymbol{E}}_{\boldsymbol{Y}}$ as follows,

$\operatorname{Tr}\left(\boldsymbol{X}^{T}\boldsymbol{L}_{\boldsymbol{Y}}\boldsymbol{X}\right)=\frac{1}{2}\sum_{i,j=1}^{n}\left[\widehat{\boldsymbol{E}}_{\boldsymbol{Y}}\right]_{i,j}\left[\boldsymbol{E}_{\boldsymbol{X}}\right]_{i,j}$

From the fact
$\left[\boldsymbol{E}_{\boldsymbol{X}}\right]_{i,j}=\left(\left\langle\widetilde{\boldsymbol{x}}_{i},\widetilde{\boldsymbol{x}}_{i}\right\rangle+\left\langle\widetilde{\boldsymbol{x}}_{j},\widetilde{\boldsymbol{x}}_{j}\right\rangle-2\left\langle\widetilde{\boldsymbol{x}}_{i},\widetilde{\boldsymbol{x}}_{j}\right\rangle\right)$,
and also
$\widehat{\boldsymbol{E}}_{\boldsymbol{X}}=-2\widetilde{\boldsymbol{X}}\widetilde{\boldsymbol{X}}^{T}$
we get

$\displaystyle\operatorname{Tr}\left(\boldsymbol{X}^{T}\boldsymbol{L}_{\boldsymbol{Y}}\boldsymbol{X}\right)=$
$\displaystyle-\frac{1}{4}\sum_{i,j=1}^{n}\left[\widehat{\boldsymbol{E}}_{\boldsymbol{Y}}\right]_{i,j}\left(\left[\widehat{\boldsymbol{E}}_{\boldsymbol{X}}\right]_{i,i}+\left[\widehat{\boldsymbol{E}}_{\boldsymbol{X}}\right]_{j,j}-2\left[\widehat{\boldsymbol{E}}_{\boldsymbol{X}}\right]_{i,j}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{i,j}\left[\widehat{\boldsymbol{E}}_{\boldsymbol{X}}\right]_{i,j}\left[\widehat{\boldsymbol{E}}_{\boldsymbol{Y}}\right]_{i,j}-\frac{1}{4}\sum_{j}^{n}\left[\widehat{\boldsymbol{E}}_{\boldsymbol{X}}\right]_{j,j}\sum_{i}^{n}\left[\widehat{\boldsymbol{E}}_{\boldsymbol{Y}}\right]_{i,j}$
$\displaystyle-\frac{1}{4}\sum_{i}^{n}\left[\widehat{\boldsymbol{E}}_{X}\right]_{i,i}\sum_{j}^{n}\left[\widehat{\boldsymbol{E}}_{\boldsymbol{Y}}\right]_{i,j}$

Since $\widehat{\boldsymbol{E}}_{\boldsymbol{X}}$ and
$\widehat{\boldsymbol{E}}_{\boldsymbol{Y}}$ are double centered matrices
$\sum_{i=1}^{n}\left[\widehat{\boldsymbol{E}}_{\boldsymbol{Y}}\right]_{i,j}=\sum_{j=1}^{n}\left[\widehat{\boldsymbol{E}}_{\boldsymbol{Y}}\right]_{i,j}=0$
it follows that

$\operatorname{Tr}\left(\boldsymbol{X}^{T}\boldsymbol{L}_{\boldsymbol{Y}}\boldsymbol{X}\right)=\frac{1}{2}\sum_{i,j}\left[\widehat{\boldsymbol{E}}_{\boldsymbol{X}}\right]_{i,j}\left[\widehat{\boldsymbol{E}}_{\boldsymbol{Y}}\right]_{i,j}$

It also follows that

$\hat{\nu^{2}}(\boldsymbol{X},\boldsymbol{Y})=\frac{1}{n^{2}}\sum_{i,j=1}^{n}\left[\widehat{\boldsymbol{E}}_{\boldsymbol{Y}}\right]_{i,j}\left[\boldsymbol{E}_{\boldsymbol{X}}\right]_{i,j}=\frac{2}{n^{2}}\operatorname{Tr}\left(\boldsymbol{X}^{T}\boldsymbol{L}_{\boldsymbol{Y}}\boldsymbol{X}\right)$

Similarly, we can express the sample distance covariance using Laplacians
$\boldsymbol{L}_{\boldsymbol{X}}$ and $\boldsymbol{L}_{\boldsymbol{Y}}$ as

$\hat{\nu^{2}}(\boldsymbol{X},\boldsymbol{Y})=\left(\frac{2}{n^{2}}\right)\operatorname{Tr}\left(\boldsymbol{X}^{T}\boldsymbol{L}_{\boldsymbol{Y}}\boldsymbol{X}\right)=\left(\frac{2}{n^{2}}\right)\operatorname{Tr}\left(\boldsymbol{Y}^{T}\boldsymbol{L}_{\boldsymbol{X}}\boldsymbol{Y}\right)$

The sample distance variances can be expressed as
$\hat{\nu}^{2}(\boldsymbol{X},\boldsymbol{X})=\left(\frac{2}{n^{2}}\right)\operatorname{Tr}\left(\boldsymbol{X}^{T}\boldsymbol{L}_{\boldsymbol{X}}\boldsymbol{X}\right)$
and
$\hat{\nu}^{2}(\boldsymbol{Y},\boldsymbol{Y})=\left(\frac{2}{n^{2}}\right)\operatorname{Tr}\left(\boldsymbol{Y}^{T}\boldsymbol{L}_{\boldsymbol{Y}}\boldsymbol{Y}\right)$
substituting back into expression of sample ∎

##  Appendix G $S(\mathbb{X,Y})$ as a sum of directional variances

######  Lemma G.1.

We now express the denominator term of the test-statistic as a specific sum of
directional variances as follows. The denominator in the test-statistic,

${\hat{S}}(\boldsymbol{X,Y})=\frac{1}{n^{2}}\sum_{k,l=1}^{n}\left\|\boldsymbol{x}_{k}-\boldsymbol{x}_{l}\right\|^{2}\frac{1}{n^{2}}\sum_{k,l=1}^{n}\left\|\boldsymbol{y}_{k}-\boldsymbol{y}_{l}\right\|^{2},$

can be expressed as a sum of directional variances as
$\hat{S}(\boldsymbol{X,Y})=\sum_{i}\phi_{\boldsymbol{X}}(\boldsymbol{g_{i}})$
where $\boldsymbol{g}_{i}$ is the $i$’th column of a matrix $\boldsymbol{G}$
such that $\boldsymbol{L^{S}}=\boldsymbol{G}\boldsymbol{G}^{T}$ for a graph
Laplacian matrix $\mathbb{L^{S}}$ given by
$\mathbb{L^{S}}=n\boldsymbol{I-ee^{T}}$. We use the superscript
$\boldsymbol{S}$ to distinguish from the Laplacian $\boldsymbol{L^{W}}$ used
in the expression for $\hat{\Omega}^{2}$.

###### Proof.

We first start simple, by expressing the Euclidean distance between any two
pairs of points using a matrix trace formulation as follows.

$d_{ij}^{2}(\boldsymbol{X})=\sum_{a=1}^{m}\boldsymbol{x}_{a}^{\top}\left(\boldsymbol{e}_{i}-\boldsymbol{e}_{j}\right)\left(\boldsymbol{e}_{i}-\boldsymbol{e}_{j}\right)^{\top}\boldsymbol{x}_{a}=\sum_{a=1}^{m}\boldsymbol{x}_{a}^{\top}\boldsymbol{A}_{ij}\boldsymbol{x}_{a}=\operatorname{tr}\boldsymbol{X}^{\top}\boldsymbol{A}_{ij}\boldsymbol{X}$

where $\boldsymbol{A}_{ij}=(e_{i}-e_{j})(e_{i}-e_{j})^{\top}$. Similarly,
$\sum_{i<j}d_{ij}(\boldsymbol{X})=\operatorname{tr}\boldsymbol{X}^{\top}\left(\sum_{i<j}d_{ij}^{-1}(\boldsymbol{X})\boldsymbol{A}_{ij}\right)\boldsymbol{X}$.
We now extend this to express the sum of all pairs of Euclidean distance
matrices as follows

$\eta(\boldsymbol{X})=\sum_{i<j}w_{ij}d_{ij}^{2}(\boldsymbol{X})=\operatorname{tr}\boldsymbol{X}^{\top}\left(\sum_{i<j}w_{ij}\boldsymbol{A}_{ij}\right)\boldsymbol{X}=\operatorname{tr}\boldsymbol{X}^{\top}\boldsymbol{L^{S}}\boldsymbol{X}$

where $\mathbb{L^{S}}=\left(\sum_{i<j}w_{ij}\boldsymbol{A}_{ij}\right)$. As we
would like to express the sum of all pairs of distances, we consider the case
where $\boldsymbol{W}_{ij}=1,\forall i,j\in[n]$. Note that this matrix exactly
has the structure of a graph Laplacian. This results in a graph Laplacian
$\boldsymbol{L^{S}}$ where

$L^{S}=\left[\begin{array}[]{ccc}n-1&-1&-1\\\ -1&\ddots&\vdots\\\
-1&\cdots&n-1\end{array}\right]=n\boldsymbol{I-ee^{T}}$

Therefore,

$\boldsymbol{S^{\alpha}(X,Y)}=\eta(\boldsymbol{X})\eta(\boldsymbol{Y})=\frac{4}{n^{4}}Tr\left(\boldsymbol{X}^{\top}\boldsymbol{L^{S}X}\right)\cdot\operatorname{Tr}\left(\boldsymbol{Y}^{T}\boldsymbol{L^{S}Y}\right)$

Note that we could also express
$Tr\left(\boldsymbol{X}^{\top}\boldsymbol{L^{S}X}\right)$ as

$Tr\left(\boldsymbol{X}^{\top}\boldsymbol{L^{S}X}\right)=Tr\left(\boldsymbol{X}^{\top}\boldsymbol{GG^{T}X}\right)=Tr\left(\boldsymbol{G^{T}XX}^{\top}\boldsymbol{G}\right)=\sum_{i}^{k\leq
n}\left(\boldsymbol{g_{i}}^{\boldsymbol{T}}\boldsymbol{X}\boldsymbol{X}^{\boldsymbol{T}}\boldsymbol{g_{i}}\right)=\sum_{i}\phi_{\boldsymbol{X}}(\boldsymbol{g_{i}}),$

where $k$ is the rank of the matrix $\boldsymbol{L^{S}}$. ∎

##  Appendix H Population distance correlation

Using the definition of distance covariance, we have the following expression
for the square of distance correlation Székely et al. [2007] between random
variables

$\left\\{\begin{array}[]{cc}\frac{{\Omega^{2}}(\boldsymbol{X},\boldsymbol{Y})}{\sqrt{{\Omega^{2}}(\boldsymbol{X},\boldsymbol{X}){\Omega^{2}}(\boldsymbol{Y},\boldsymbol{Y})}},&\text{if
}{\Omega^{2}}(\boldsymbol{X},\boldsymbol{X}){\Omega^{2}}(\boldsymbol{Y},\boldsymbol{Y})>0\\\
0,&\text{if
}{\Omega^{2}}(\boldsymbol{X},\boldsymbol{X}){\Omega^{2}}(\boldsymbol{Y},\boldsymbol{Y})=0\end{array}\right.$

This always lies within the interval $[0,1]$ with $0$ referring to
independence and $1$ referring to dependence.

##  Appendix I Families of some dependency measures

  1. 1.

Energy statistics: Distance correlation (DCOR), Brownian distance covariance,
Partial distance correlation, Partial martingale difference correlation

  2. 2.

Kernel covariance operators: Constrained covariance (COCO), Hilbert-Schmidt
independence criterion (HSIC), Kernel Target Alignment (KTA)

  3. 3.

Integral probability metrics: Maximum mean discrepancey (MMD), Wasserstein
distance, Dudley metric and Fortet-Mourier metric, Total variation distance.

  4. 4.

Information theoretic measures: Mutual information, f-divergence, Renyi
divergence, Hellinger distance, Total variation distance, Maximal information
coefficient, Total information coefficient

## References

  * Székely et al. [2007] Gábor J Székely, Maria L Rizzo, and Nail K Bakirov.  Measuring and testing dependence by correlation of distances.  _The annals of statistics_ , 35(6):2769–2794, 2007.
  * Pearson [1900] Karl Pearson.  On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling.  _The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science_ , 50(302):157–175, 1900.
  * Dwork et al. [2014] Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  _Found. Trends Theor. Comput. Sci._ , 9(3-4):211–407, 2014.
  * Gaboardi et al. [2016] Marco Gaboardi, Hyun Lim, Ryan Rogers, and Salil Vadhan.  Differentially private chi-squared hypothesis testing: Goodness of fit and independence testing.  In _International conference on machine learning_ , pages 2111–2120. PMLR, 2016.
  * Sheffet [2018] Or Sheffet.  Locally private hypothesis testing.  In _International Conference on Machine Learning_ , pages 4605–4614. PMLR, 2018.
  * Warner [1965] Stanley L Warner.  Randomized response: A survey technique for eliminating evasive answer bias.  _Journal of the American Statistical Association_ , 60(309):63–69, 1965.
  * Acharya et al. [2021] Jayadev Acharya, Clément L Canonne, Cody Freitag, Ziteng Sun, and Himanshu Tyagi.  Inference under information constraints iii: Local privacy constraints.  _IEEE Journal on Selected Areas in Information Theory_ , 2(1):253–267, 2021.
  * Székely and Rizzo [2013] Gábor J Székely and Maria L Rizzo.  The distance correlation t-test of independence in high dimension.  _Journal of Multivariate Analysis_ , 117:193–213, 2013\.
  * Yao et al. [2018] Shun Yao, Xianyang Zhang, and Xiaofeng Shao.  Testing mutual independence in high dimension via distance covariance.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 80(3):455–480, 2018.
  * Gao et al. [2021] Lan Gao, Yingying Fan, Jinchi Lv, and Qi-Man Shao.  Asymptotic distributions of high-dimensional distance correlation inference.  _The Annals of Statistics_ , 49(4):1999–2020, 2021.
  * Sejdinovic et al. [2013] Dino Sejdinovic, Bharath Sriperumbudur, Arthur Gretton, and Kenji Fukumizu.  Equivalence of distance-based and rkhs-based statistics in hypothesis testing.  _The Annals of Statistics_ , pages 2263–2291, 2013.
  * Harchaoui et al. [2013] Zaid Harchaoui, Francis Bach, Olivier Cappe, and Eric Moulines.  Kernel-based methods for hypothesis testing: A unified view.  _IEEE Signal Processing Magazine_ , 30(4):87–97, 2013.
  * Gretton et al. [2005] Arthur Gretton, Olivier Bousquet, Alex Smola, and Bernhard Schölkopf.  Measuring statistical dependence with hilbert-schmidt norms.  In _International conference on algorithmic learning theory_ , pages 63–77. Springer, 2005.
  * Heller et al. [2016] Ruth Heller, Yair Heller, Shachar Kaufman, Barak Brill, and Malka Gorfine.  Consistent distribution-free k-sample and independence tests for univariate random variables.  _The Journal of Machine Learning Research_ , 17(1):978–1031, 2016.
  * Jitkrittum et al. [2017] Wittawat Jitkrittum, Wenkai Xu, Zoltán Szabó, Kenji Fukumizu, and Arthur Gretton.  A linear-time kernel goodness-of-fit test.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Jitkrittum et al. [2016] Wittawat Jitkrittum, Zoltán Szabó, and Arthur Gretton.  An adaptive test of independence with analytic kernel embeddings.  _arXiv preprint arXiv:1610.04782_ , 2016.
  * Zhang et al. [2018] Qinyi Zhang, Sarah Filippi, Arthur Gretton, and Dino Sejdinovic.  Large-scale kernel methods for independence testing.  _Statistics and Computing_ , 28(1):113–130, 2018\.
  * Wang et al. [2015] Xueqin Wang, Wenliang Pan, Wenhao Hu, Yuan Tian, and Heping Zhang.  Conditional distance correlation.  _Journal of the American Statistical Association_ , 110(512):1726–1734, 2015.
  * Zhang et al. [2012] Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf.  Kernel-based conditional independence test and application in causal discovery.  _arXiv preprint arXiv:1202.3775_ , 2012.
  * Zhang et al. [2017] Hao Zhang, Shuigeng Zhou, Kun Zhang, and Jihong Guan.  Causal discovery using regression-based conditional independence tests.  In _Thirty-First AAAI Conference on Artificial Intelligence_ , 2017\.
  * Wang et al. [2020] Lun Wang, Qi Pang, and Dawn Song.  Towards practical differentially private causal graph discovery.  _Advances in Neural Information Processing Systems_ , 33:5516–5526, 2020.
  * Shen et al. [2022] Cencheng Shen, Sambit Panda, and Joshua T Vogelstein.  The chi-square test of distance correlation.  _Journal of Computational and Graphical Statistics_ , 31(1):254–262, 2022.
  * Diakonikolas et al. [2015] Ilias Diakonikolas, Moritz Hardt, and Ludwig Schmidt.  Differentially private learning of structured discrete distributions.  In _NIPS_ , pages 2566–2574, 2015.
  * Acharya et al. [2018] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang.  Differentially private testing of identity and closeness of discrete distributions.  In _NeurIPS_ , pages 6879–6891, 2018.
  * Aliakbarpour et al. [2018] Maryam Aliakbarpour, Ilias Diakonikolas, and Ronitt Rubinfeld.  Differentially private identity and equivalence testing of discrete distributions.  In _ICML_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 169–178. PMLR, 2018.
  * Blocki et al. [2012] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet.  The johnson-lindenstrauss transform itself preserves differential privacy.  In _2012 IEEE 53rd Annual Symposium on Foundations of Computer Science_ , pages 410–419. IEEE, 2012.
  * Biswas et al. [2020] Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan Ullman.  Coinpress: Practical private mean and covariance estimation.  _Advances in Neural Information Processing Systems_ , 33:14475–14485, 2020.
  * Amin et al. [2019] Kareem Amin, Travis Dick, Alex Kulesza, Andres Munoz, and Sergei Vassilvitskii.  Differentially private covariance estimation.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Han and Shen [2021] Qiyang Han and Yandi Shen.  Generalized kernel distance covariance in high dimensions: non-null clts and power universality.  _arXiv preprint arXiv:2106.07725_ , 2021.
  * Vepakomma et al. [2018] Praneeth Vepakomma, Chetan Tonde, and Ahmed Elgammal.  Supervised dimensionality reduction via distance correlation maximization.  _Electronic Journal of Statistics_ , 12(1):960–984, 2018.
  * Torgerson [1952] Warren S Torgerson.  Multidimensional scaling: I. theory and method.  _Psychometrika_ , 17(4):401–419, 1952.