Private measurement of nonlinear correlations between data hosted across
multiple parties

Praneeth Vepakomma Subha Nawer Pushpita Ramesh Raskar

MIT MIT MIT

###### Abstract

We introduce a differentially private method to measure nonlinear correlations
between sensitive data hosted across two entities. We provide utility
guarantees of our private estimator. Ours is the first such private estimator
of nonlinear correlations, to the best of our knowledge within a multi-party
setup. The important measure of nonlinear correlation we consider is distance
correlation. This work has direct applications to private feature screening,
private independence testing, private k-sample tests, private multi-party
causal inference and private data synthesis in addition to exploratory data
analysis. Code access: A link to publicly access the code is provided in the
supplementary file.

##  1 Introduction

Estimating correlations (linear and non-linear) between random variables (via
their samples) is of fundamental importance in statistics and machine
learning. The following is the main problem of consideration in this paper.
Problem statement: How can non-linear correlations between two random
variables be estimated with formal guarantees on preserving privacy while
reasonably maintaining the utility of the estimate under the constraint that
the samples from each of the random variables are correspondingly held by two
different parties?

Figure 1: Private multi-party non-linear correlation problem

###  1.1 Motivation

An ability to compute non-linear correlations between data hosted across
multiple parties while preserving privacy opens up quite a few applications.
The dependency measure we consider in this paper is called distance
correlation [Székely et al., 2007] which is an instance of ‘Energy Statistics’
introduced in [Székely and Rizzo, 2017, Rizzo and Székely, 2016, Székely and
Rizzo, 2013b]. Some of the important applications for estimating distance
correlation in a private manner are summarized below.

####  1.1.1 Benefits of privately estimating distance correlation

  1. 1.

Private multi-party feature screening with distance correlation The importance
of distance correlation in optimally selecting features with a ‘sure
independence screening’ guarantee under a model agnostic setting was shown in
the works of [Li et al., 2012, Zhong and Zhu, 2015, Fan and Lv, 2018, Lu et
al., 2021]. Thereby the measurement of distance correlation in a privacy
preserving manner in multi-party settings would potentially allow for private
feature selection. A noteworthy work by [Thakurta and Smith, 2013] shows that
under assumptions of feature selection procedures being stable with respect to
sub-sampling, the selection can be done privately and in some cases match the
optimal non-private asymptotic sample complexity.

  2. 2.

Private multi-party independence testing with distance correlation A wonderful
survey of property testing of distributions is given in [Canonne, 2020] and
also covers the specific sub-topic of independence testing. Hypothesis tests
for testing independence of distributions using distance correlation were
introduced in [Székely et al., 2007, Székely and Rizzo, 2013a]. The test
statistic is based on distance correlation. Thereby performing private
independence testing between samples that are distributed in multiple entities
requires private estimation of distance correlation. The classical Chi-Squared
hypothesis test for testing independence between categorical variables has
been extended to be made differentially private in [Gaboardi et al., 2016].
The work in [Shen et al., 2019] showed an equivalence between independence
testing using distance correlation and k-sample testing. Differentially
private procedures for analysis of variance (ANOVA) have been introduced in
[Swanberg et al., 2019].

  3. 3.

Private multi-party causal inference with distance correlation The works in
[Kusner et al., 2015, Kusner et al., 2016] privately estimate distance
correlation in a single party setting, where samples from both the random
variables are at at the same entity. They then use this private estimate of
distance correlation to infer the causal direction. We consider the more
important setting where the samples from both the random variables are at two
different corresponding entities as opposed to all of them being on-premise at
one entity.

  4. 4.

Private multi-party data synthesis by seeding copulas with distance
correlations Gaussian copulas have been used for private data synthesis as
shown in [Asghar et al., 2021, Li et al., 2014]. A key step in this process is
to seed the Gaussian copula with a correlation matrix, and it has a
significant impact on the quality of the synthesis. These current works have
so far seeded it with linear measures of correlations such as Pearson’s
correlation or Kendall’s Tau. A private multi-party measure of distance
correlation allows for better seeding of the Gaussian copula for multi-party
private data synthesis.

###  1.2 Contributions

  1. 1.

We introduce a differentially private method to measure nonlinear correlations
between sensitive data hosted across two entities.

  2. 2.

We provide utility guarantees for our private estimator. We provide
experimental results to compare the quality of our estimator against important
baselines on several benchmark datasets.

##  2 Preliminaries

We start by providing definitions of population distance covariance and
population distance correlation as these are central to rest of the paper. We
then share two existing non-private sample estimators for estimating the same.

###  2.1 Non-private estimators of distance correlation

Population distance covariance

For random variables $\mathbf{x}\in\mathbb{R}^{d}$ and
$\mathbf{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

$\mathbb{\nu}^{2}(\mathbf{x},\mathbf{y})=\int_{\mathbb{R}^{d+m}}|f_{\mathbf{x},\mathbf{y}}(t,s)-f_{\mathbf{x}}(t)f_{\mathbf{y}}(s)|^{2}w(t,s)dtds$

where $f_{\mathbf{x}},f_{\mathbf{y}}$ are characteristic functions of
$\mathbf{x},\mathbf{y}$, $f_{\mathbf{x},\mathbf{y}}$ is the joint
characteristic function, and $w(t,s)$ is a weight function defined as

$w(t,s)=(C(p,\alpha)C(q,\alpha)|t|^{\alpha+p}_{p}|s|_{q}^{\alpha+q})^{-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 refers to the choice of norm considered in
obtaining the distance matrices. $\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: We would like to note that distance covariance between a variable and
itself is referred to as distance variance.
Population distance correlation Using this above 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}(\mathbf{X},\mathbf{Y})}{\sqrt{{\Omega}(\mathbf{X},\mathbf{X}){\Omega}(\mathbf{Y},\mathbf{Y})}},&\text{if,
}{\Omega}(\mathbf{X},\mathbf{X}){\Omega}(\mathbf{Y},\mathbf{Y})>0\\\
0,&\text{if,
}{\Omega}(\mathbf{X},\mathbf{X}){\Omega}(\mathbf{Y},\mathbf{Y})=0\end{array}\right.$

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

For completeness, we provide a listing of some more popular measures of
nonlinear statistical dependency in Appendix B. That said, this paper
specifically focuses on mechanisms for privatizing the measure of distance
correlation in settings when the variables $\mathbf{X}$, $\mathbf{Y}$ are
hosted at different entities. In the setting when both of them are hosted on
the same entity, a privatized measure of a statistical dependency called
Hilbrt Schmidt Indpendence Critrion was provided in [Kusner et al., 2016].

###  2.2 Sample estimators of distance correlation

Two sample estimators currently available for estimating population distance
covariance in the non-private setting include:

a.) Unbiased sample distance covariance
Using $|\cdot|$ to represent the Euclidean norm, we first define
$a_{ij}=|X_{i}-X_{j}|$, $b_{ij}=|Y_{i}-Y_{j}|$, $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}(\mathbf{X,Y})$ as follows.

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

b.) Random projected distance covariance A faster unbiased estimator of
distance covariance based on random projections denoted by
$\overline{\Omega^{k}_{n}}(\mathbf{X,Y})$ was introduced in [Huang and Huo,
2017]. In order to define this sample estimator of distance covariance, we
first define few constants based on $\pi$ and the Gamma function as follows.
These include $c_{p}=\frac{\pi^{(p+1)/2}}{\Gamma((p+1)/2)}$ and
$c_{q}=\frac{\pi^{(q+1)/2}}{\Gamma((q+1)/2)}$ ,
$C_{p}=\frac{c_{1}c_{p-1}}{c_{p}}=\frac{\sqrt{\pi}\Gamma((p+1)/2)}{\Gamma(p/2)}$
and
$C_{q}=\frac{c_{1}c_{q-1}}{c_{q}}=\frac{\sqrt{\pi}\Gamma((q+1)/2)}{\Gamma(q/2)}.$
Let $u$ and $v$ be points on the hyper-spheres: $u\in\mathcal{S}^{p-1}=$
$\left\\{u\in\mathbb{R}^{p}:|u|=1\right\\}$ and $v\in\mathcal{S}^{q-1}$. For
any vector $u$ or $v$, let $u^{T}$ or $v^{T}$ denote its transpose. We now
share the non-private estimator below

$\overline{\Omega}(\mathbf{X,Y})=\sum_{k=1}^{K}\frac{C_{p}C_{q}\Omega_{n}(u_{k}^{T}X,v_{k}^{T}Y)}{K}$
(2)

where $u_{k}^{T}X=(u_{k}^{T}X_{1},\ldots,u_{k}^{T}X_{n})$ and
$u_{k}^{T}Y=(u_{k}^{T}Y_{1},\ldots,u_{k}^{T}Y_{n})$. Note that in this case
$a_{ij}=|u^{T}(X_{i}-X_{j})|$ and $b_{ij}=|v^{T}(Y_{i}-Y_{j})|$.

##  3 Method

###  3.1 Approach

Privately estimating sample distance correlation between
$\mathbf{X}\in\mathbb{R}^{n\times d}$ and $\mathbf{Y}\in\mathbb{R}^{n\times
p}$ requires a private estimation of a distance covariance term in the
numerator and a distance variance term in the denominator of
$\frac{\overline{{\Omega}}(\mathbf{X},\mathbf{Y})}{\sqrt{{\overline{\Omega}}(\mathbf{X},\mathbf{X}){\overline{\Omega}}(\mathbf{Y},\mathbf{Y})}}$
that depends on $\mathbf{X}$.

Privatizing ${\overline{\Omega}\mathbf{(X,Y)}}$: For the distance covariance
in the numerator, we provide a differentially private estimator of
${\overline{\Omega}\mathbf{(X,Y)}}$ that we denote by
${\overline{\Omega}^{dp}\mathbf{(X,Y)}}$. Note that
${\overline{\Omega}\mathbf{(X,Y)}}$ is the non-private ‘random projected
distance covariance estimator’ given in equation 2 to estimate population
distance covariance ${{\Omega}\mathbf{(X,Y)}}$. Note that in the setting we
consider, $\mathbf{X}$ and $\mathbf{Y}$ are hosted at two different entities,
as opposed to both of them being available on-premise at a single site. We
provide details on our differentially private estimator
${\overline{\Omega}^{dp}\mathbf{(X,Y)}}$ in section 3.2.1 and provide our
utility proofs for it in Theorems 1, 2 & 3.

Privatizing ${\overline{\Omega}\mathbf{(Y,Y)}}$:  The term of
$\overline{\Omega}(\mathbf{Y},\mathbf{Y})$ does not require private estimation
as it is computed on-premise by the entity that holds $\mathbf{Y}$. The entity
that holds $\mathbf{X}$ (say, Alice) makes a one-way communication of our
proposed private estimates for ${\overline{\Omega}^{dp}\mathbf{(X,Y)}}$,
${\overline{\Omega}^{dp}\mathbf{(X,X)}}$ to the entity that holds $\mathbf{Y}$
(say, Bob). Bob computes a non-private and ${\overline{\Omega}\mathbf{(Y,Y)}}$
on-premise. These three estimates can be put together by Bob to privately
estimate the distance correlation $\overline{\rho}^{dp}\mathbf{(X,Y)}$ as

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

Note that Bob does not reveal the estimated private distance correlation to
Alice. In a scenario, where it needs to reveal it to Alice (or anyone in the
public), it could do that by using the private estimator in the subsection on
privatizing ${\overline{\Omega}\mathbf{(X,X)}}$ with respect to $\mathbf{X}$.
This approach can be used by Bob to privatize
${\overline{\Omega}\mathbf{(Y,Y)}}$ with respect to $\mathbf{Y}$ instead. We
now describe our two proposed private estimators for
$\mathbf{\overline{\Omega}^{dp}(X,Y)}$ which is in the multi-party setting and
$\mathbf{\overline{\Omega}^{dp}(X,X)}$ which is in the single party setting.

####  3.1.1 Proposed private estimator for distance covariance

$\mathsf{PNC}\mbox{-}{\mathsf{Estimator}}$ 1. Alice’s input: Data matrix
$\mathbf{X}$ 2. Bob’s input: Data matrix $\mathbf{Y}$ 3. Alice’s side: The
client takes the following actions: (a) Computes either
$\overline{\Omega}^{dp}(\mathbf{X,Y})$ using equation 3 or
$\Omega^{dp}_{\textrm{Disjt}}(\mathbf{X,Y})$ using equation 4. (b) Computes
$\overline{\Omega}^{dp}(\mathbf{X,X})$ by adding noise calibrated to global
sensitivity of $\frac{12n-11}{(n-1)^{2}}$ to $\overline{\Omega}(\mathbf{X,X})$
(c) The client sends the obtained $\overline{\Omega}^{dp}(\mathbf{X,X})$ and
either of $\overline{\Omega}^{dp}(\mathbf{X,Y})$ or
$\Omega^{dp}_{\textrm{Disjt}}(\mathbf{X,Y})$ to Bob. 4. Bob’s side: (a) Bob
computes non-private $\overline{\Omega}(\mathbf{Y,Y})$. (b) Bob puts together
all these estimates to compute the distance correlation between $\mathbf{X}$
and $\mathbf{Y}$.

Figure 2: Protocol for private estimation of non-linear correlations between
data of Alice and Bob.

Our estimation starts with Alice sending $K$ differentially private random
projections of sensitive data $\mathbf{X}$ to Bob that hosts the sensitive
data $\mathbf{Y}$. An average of $K$ distance covariances between the random
projections of $\mathbf{X}$ and the raw data $\mathbf{Y}$ is computed at Bob’s
premises to get $\mathbf{\overline{\Omega}^{dp}(X,Y)}$. We then perform K
differentially private random projections of the data $\mathbf{X}$ by adding
the necessary noise $N$ required for privacy. The next sub-section explains
the process of choosing $N^{X}$ in order to guarantee differential privacy.
Therefore, this estimator is given by

$\overline{\Omega}^{dp}(\mathbf{X,Y})=\sum_{k=1}^{K}\frac{C_{p}C_{q}\overline{\Omega}_{n}(u_{k}^{T}X+N^{x},v_{k}^{T}Y)}{K}$
(3)

where $N^{x}=(N^{x}_{1},\ldots,N^{x}_{n})$. Note that in this case
$\tilde{a}_{ij}=|u^{T}(X_{i}-X_{j})+(N^{x}_{i}-N^{x}_{j})|$ and
$\tilde{b}_{ij}=|v^{T}(Y_{i}-Y_{j})|$.

###  3.2 Choosing $\mathbf{N^{X}}$ for differential privacy

Several mechanisms have been proposed for releasing random projections of data
with differential privacy including [Kenthapadi et al., 2013, Blocki et al.,
2012, Upadhyay, 2013] and more recently [Xu et al., 2017, Gondara and Wang,
2020]. We refer to Appendix D for details on one such mechanism.

####  3.2.1 Avoiding sequential composition

Applying $K$ differentially private random projections $u_{k}^{X}$ in the
Equation 2 would lead to a differentially private estimate of nonlinear
correlation. Studying the utility of this estimator would be of interest. That
said, if all the $K$ random projections are applied on the entire dataset
$\mathbf{X}$, it would lead to an overall privacy guarantee of $K\epsilon$ due
to the sequential composition property of differential privacy. This loss of
privacy budget can be avoided if the samples in the dataset (i.e the rows of
$\mathbf{X,Y}$) are partitioned into $K$ disjoint subsets prior to a random
projection based distance covariance measured disjointly on each subset prior
to averaging them out. This would lead to an improved accounting with regards
to the privacy budget, as this falls under the parallel composition property
of differential privacy, thereby leading to an overall $\epsilon$-DP of the
estimator if each of the individual projections was also performed with
$\epsilon$-DP. This estimator is summarized below.

##### Private estimator on disjoint partitions
$\Omega^{dp}_{\textrm{Disjt}}(X,Y)$:

Our estimator requires us to first partition the $n$ records of $\mathbf{X,Y}$
into $K$ blocks of
$\\{\left[X_{1},Y_{1}\right]\,\left[X_{2},Y_{2}\right]\ldots\left[X_{K},Y_{K}\right]\\}$
in order to avoid sequential composition. Therefore, this estimator is given
by

$\Omega^{dp}_{\textrm{Disjt}}(\mathbf{X,Y})=\sum_{k=1}^{K}\frac{C_{p}C_{q}\overline{\Omega}_{n}(u_{k}^{t}X_{k}+N,v_{k}^{t}Y_{k})}{K}$
(4)

###  3.3 Utility results

We now study the utility of the private estimator
$\overline{\Omega}^{dp}(\mathbf{X,Y})$ in estimating the non-private
$\overline{\Omega}(\mathbf{X,Y})$ given the effect of noise in the private
estimator. The utility can be expressed by
$\overline{\Omega}^{dp}(X,Y)-\overline{\Omega}(X,Y)$.

######  Theorem 1.

(Decomposition theorem) The difference between estimators of
$\overline{\Omega}^{dp}(X,Y)$ and $\overline{\Omega}(X,Y)$ can be expressed as

$\displaystyle\overline{\Omega}^{dp}(X,Y)-\overline{\Omega}(X,Y)=\overline{\Omega}(N_{X},Y)$
$\displaystyle+\sum_{n=1}^{K}\frac{4C_{p}C_{q}}{Kn(n-2)(n-3)}\sum_{i=1}^{n}\left(\sum_{l=1}^{n}|N_{i}^{X}-N_{l}^{X}|\sum_{l=1}^{n}V_{k}^{T}(Y_{i}-Y_{l})|\right)$
(5)

###### Proof.

The full proof for this theorem is given in Appendix A. ∎

Therefore, the error in estimation within this context depends on two error
terms of $\hat{\Omega}(N_{X},Y)$ and
$\frac{4C_{p}C_{q}}{Kn(n-2)(n-3)}\sum_{i=1}^{n}\left(\sum_{l=1}^{n}|N_{i}^{X}-N_{l}^{X}|\sum_{l=1}^{n}V_{k}^{T}(Y_{i}-Y_{l})|\right)$.
We now upper bound the second error term in the following theorem.

######  Theorem 2.

(Error bound) The error term

$\frac{4C_{p}C_{q}}{Kn(n-2)(n-3)}\sum_{i=1}^{n}\left(\sum_{l=1}^{n}|N_{i}^{X}-N_{l}^{X}|\sum_{l=1}^{n}V_{k}^{T}(Y_{i}-Y_{l})|\right)$

can be bounded using a $t_{1}$ and $t_{2}$ that are both greater than
$2\sigma\sqrt{(\frac{n-1}{n})(\log(2)-\frac{\log(\alpha)}{n})}$ and
$C=\frac{4C_{p}C_{q}}{Kn(n-2)(n-3)}$. The concentration bound we obtain is
given by

$\displaystyle\mathbb{P}\left\\{C\sum_{i=1}^{n}\left(\sum_{l=1}^{n}|N_{i}^{X}-N_{l}^{X}|\sum_{l=1}^{n}|V_{k}^{t}(Y_{i}-Y_{l})|\right)<Cn^{3}t_{1}t_{2}\right\\}$
(6) $\displaystyle\geq(1-n(\alpha_{1}+\alpha_{2}-\alpha_{1}\alpha_{2}))$

where $P(\sum_{l=1}^{n}|V_{k}^{t}(Y_{i}-Y_{l})|\geq nt_{1})\leq\alpha_{1}$ and
$P(\sum_{l=1}^{n}|N^{X}_{i}-N^{X}_{l}|\geq nt_{2})\leq\alpha_{2}$

###### Proof.

Sketch of proof ∎

Bounding the error term of $\overline{\Omega}(N_{X},Y)$: The error term of
$\overline{\Omega}(N_{X},Y)$ can be bounded using a simplification of our
above result by setting $\mathbf{X}$ to be zero in the decomposition theorem
and using the same strategy as the error bound in Theorem 2. That said, since
the noise parameters can be released in differential privacy, a reasonable
estimate of $\overline{\Omega}(N_{X},Y)$ can be estimated on the premises of
Bob, that holds $Y$. This analysis is provided in the Appendix A.2.

####  3.3.1 Privatizing $\overline{\Omega}(\mathbf{X,X})$

The problem of privatizing ${\overline{\Omega}\mathbf{(X,X)}}$ is simpler than
that of privatizing ${\overline{\Omega}\mathbf{(X,Y)}}$ in the sense that in
the former case, the entire data $\mathbf{X}$ is hosted on one entity as
opposed to $\mathbf{X}$ and $\mathbf{Y}$ being hosted on two entities. For the
private estimation of distance variance terms
${\overline{\Omega}^{dp}\mathbf{(X,X)}}$, we first use an equivalence between
distance covariance and another popular dependency measure called Hilbert-
Schmidt Independence Criterion (HSIC) [Gretton et al., 2005]. We then use the
global sensitivity of this equivalently obtained HSIC to privatize the
distance variance. We begin by defining the empirical estimate of the HSIC.

Given unique positive definite kernels $k,l$ in the context of kernel methods
and reproducing kernel Hilbert space (RKHS) theory in machine learning, we
have the following definition for the sample estimator of HSIC.

######  Definition 1.

(HSIC [Gretton et al., 2005]) Let
$Z:=\left\\{\left(x_{1},y_{1}\right),\ldots,\left(x_{m},y_{m}\right)\right\\}\subseteq\mathcal{X}\times\mathcal{Y}$
be a series of $m$ independent observations drawn from $p_{xy}.$ An estimator
of HSIC, written $\operatorname{HSIC}(Z,\mathcal{F},\mathcal{G})$, is given by

$\operatorname{HSIC}(Z,\mathcal{F},\mathcal{G}):=(m-1)^{-2}\operatorname{tr}KHLH$

where $H,K,L\in\mathbb{R}^{m\times
m},K_{ij}:=k\left(x_{i},x_{j}\right),L_{ij}:=l\left(y_{i},y_{j}\right)$ and
$H$ is a double-centering matrix.

We assume $k,l$ are bounded above by 1 (e.g., the squared exponential kernel,
the Matern kernel [27]). A classic way to calibrate the amount of noise
required to achieve $\epsilon-$differential privacy [Dwork et al., 2014,
Dwork, 2006, Dwork, 2008] is to add a noise with a variance of
$\frac{\Delta}{\epsilon}$ where $\Delta$ is the global sensitivity of the
query. The basic definitions for differential privacy, global sensitivity are
provided as a primer in the Appendix C. That said, the popular book of [Dwork
et al., 2014] is a wonderful resource on differential privacy.
Global sensitivity of HSIC: The global sensitivity of HSIC was derived in
[Kusner et al., 2015, Kusner et al., 2016] to be at most
$\frac{12n-11}{(n-1)^{2}}$. Specifically,

$\left|\widehat{HSIC}_{k,l}\left(\mathbf{x},\mathbf{y}\right)-\widehat{HSIC}_{k,l}\left({\mathbf{x}}^{\prime},{\mathbf{y}}^{\prime}\right)\right|\leq\frac{12n-11}{(n-1)^{2}}$

for all neighboring [Dwork et al., 2014] datasets.

(a) Privacy-utility tradeoff on the Boston Housing dataset.

(b) Privacy-utility tradeoff on the Parkinson’s tele-monitoring dataset.

(c) Privacy-utility tradeoff on the Madelon dataset.

(d) Privacy-utility tradeoff on the wine quality dataset.

(e) Privacy-utility tradeoff on the condition monitoring of gas turbine on a
frigate dataset.

(f) Privacy-utility tradeoff on the geographic origin of music dataset.

(g) Skill Craft Dataset: Effect of $\\#$ of repeated accesses to data being 3
in the no-partition estimator of $\overline{\Omega}^{dp}(X,Y)$

(h) Skill Craft Dataset: Effect of $\\#$ of repeated accesses to data being 7
in the no-partition estimator of $\overline{\Omega}^{dp}(X,Y)$. As can be seen
the variance reduced im comparison to Figure (g) while the loss in privacy
budget was more drastic due to the repeated data accesses. Thereby, we make a
case for $\overline{\Omega}^{dp}_{\textrm{Disjt}}(X,Y)$ which has disjoint
partitions and no repeated access to raw data.

Figure 3: Privacy-utility trade-offs on several datasets is studied in (a) to
(f) and the effect of partitioning or not is studied on the skill craft
dataset in (g) to (h).

The following equivalence was shown between distance covariance and HSIC. As
we have the global sensitivity for HSIC and since we have the following
equivalence, we can use this global sensitivity to privatize
$\overline{\Omega}(\mathbf{X,X})$, which belongs to the one-party setting of
privately releasing distance covariance.

###  3.4 Equivalence map between Distance Covariance and HSIC

######  Definition 2.

Bijective induced kernel

Given sample data $\left\\{x_{i},i=1,\ldots,n\right\\}.$ For any metric
$d(\cdot,\cdot)$, we define its bijective induced kernel [Shen et al., 2019,
Shen and Vogelstein, 2021] as

$\hat{k}_{d}\left(x_{i},x_{j}\right)=\max_{s,t\in[n]}\left(d\left(x_{s},x_{t}\right)\right)-d\left(x_{i},x_{j}\right)$

For any kernel $k(\cdot,\cdot)$, we define the induced metric as

$\hat{d}_{k}\left(x_{i},x_{j}\right)=\max_{s,t\in[n]}\left(k\left(x_{s},x_{t}\right)\right)-k\left(x_{i},x_{j}\right)$

The subscripts $s,t\in[n]$ is a shorthand for $s=1,\ldots,n$ and
$t=1,\ldots,n$.

Other alternative definitions for this bijection are also given in [Shen and
Vogelstein, 2021]. These are wieldy to use depending on the problem at hand.

$\displaystyle\hat{d}_{k}\left(x_{i},x_{j}\right)=1-k\left(x_{i},x_{j}\right)/\max_{s,t\in[n]}\left(k\left(x_{s},x_{t}\right)\right)$
$\displaystyle\hat{k}_{d}\left(x_{i},x_{j}\right)=1-d\left(x_{i},x_{j}\right)/\max_{s,t\in[n]}\left(d\left(x_{s},x_{t}\right)\right)$

This is an equivalent definition up-to scaling by the maximum elements, and
can be succinctly expressed in a matrix form:

$\displaystyle\hat{\mathbf{D}}_{\mathbf{K}}=\mathbf{J}-\mathbf{K}/\max(\mathbf{K})$
$\displaystyle\hat{\mathbf{K}}_{\mathbf{D}}=\mathbf{J}-\mathbf{D}/\max(\mathbf{D})$

######  Theorem 3.

[Shen and Vogelstein, 2021] Suppose distance covariance (DCOV) uses a given
metric $d(\cdot,\cdot)$, and the Hilbert Schmidt independence criterion HSIC
uses the bijective induced kernel $\hat{k}_{d}(\cdot,\cdot)$. Given any sample
data $(\mathbf{X},\mathbf{Y})$, it holds that

$\displaystyle\operatorname{DCOV}_{n}(\mathbf{X},\mathbf{Y})=\operatorname{HSIC}_{n}(\mathbf{X},\mathbf{Y})$

where the remainder term $O\left(\frac{1}{n^{2}}\right)$ is invariant to
permutation.

##  4 Computational complexity

Fast estimators of distance correlation requires $\mathcal{O}(nlogn)$
[Chaudhuri and Hu, 2019, Huo and Székely, 2016] computational complexity for
univariate and $\mathcal{O}(nKlogn)$ complexity [Huang and Huo, 2017] for
multivariate settings with $\mathcal{O}(\max(n,K))$ memory, where $K$ is the
number of random projections required as part of the estimation. In addition
to being differentiable and easily computable with a closed-form, it requires
no other tuning of parameters and is self-contained unlike HSIC or other
dependency measures such as Maximum Mean Discrepancy (MMD) or Kernel Traget
Alignment (KTA) that depend on a choice of separate kernels for features as
well as labels along with their respective tuning parameters.

##  5 Experiments

In this section, we first introduce the datasets, experimental methodology and
metrics of evaluation. We study the performance of our method in privately
estimating distance correlation across a variety of datasets. We study the
privacy-utility trade-off curves for varying values of privacy parameter
$\epsilon$. We study the effect of $\epsilon$ on the $l_{1}$ error of
estimation.

###  5.1 Datasets

  1. 1.

Condition Based Maintenance of Naval Propulsion Plants This dataset of 11934
samples has been generated from a sophisticated simulator of a Gas Turbines
(GT), mounted on a Frigate. The goal is to predict performance decay of this
equipment based on 15 features.

  2. 2.

Parkinsons Telemonitoring Data Set This dataset of 5875 instances and 24
features was created in collaboration with 10 medical centers in the US and
Intel Corporation who developed the tele-monitoring device to record the
speech signals. The goal is to predict the clinician’s Parkinson’s disease
symptom score on the UPDRS scale.

  3. 3.

Wine Quality Data This is a dataset of 4898 samples and 11 features. The goal
is to predict the red-wine quality using the input features. Due to privacy
and logistical issues, only some variables are made available.

  4. 4.

Boston Housing This small dataset of 506 samples and 18 features contains
information collected by the U.S Census Service concerning housing in the area
of Boston Mass. It has classically been used extensively throughout the
literature to benchmark algorithms.

  5. 5.

Madelon This dataset is one of five datasets used in the NIPS 2003 feature
selection challenge and has 4400 samples of 500 features. It is an artificial
dataset containing a number of distractor feature called ’probes’ having no
predictive power. The order of the features and patterns were randomized. Only
20 out of the 500 are real features with predictive value and 480 are the
distracting features/probes.

  6. 6.

Geographic origin of music This dataset was built from a personal collection
of 1059 tracks covering 33 countries/areas. The goal is to predict the
geographical origin of each music file based on the audio features extracted
from each wave file. This dataset has 3395 samples and 19 features.

  7. 7.

Skill craft 1 Master Table This is a gaming related dataset where the goal is
to predict the league (position) of any player of skill craft 1 based on
features that measure his interactions with the game. This dataset has 1059
samples and 116 features.

  8. 8.

Seoul bike sharing demand The goal is to predict the bike count required at
each hour in order to plan and maintain a stable supply of rental bikes.This
dataset has 8760 samples and 13 features. The results on this dataset are
provided in Appendix E.

##  6 Methodology

We split the feature sets for each of these datasets into two. One to
represent $\mathbf{X}$ and other to represent $\mathbf{Y}$. Note that distance
covariance and distance correlation can be computed between $\mathbf{X}$ and
$\mathbf{Y}$ that can potentially lie in different dimensions as long as their
sample sizes match up to be the same. The reason for this is that the
estimators for distance covariance and distance correlation solely depend on
the distance matrices of these samples. Since distance matrices are square and
symmetric and since the sample sizes match up, thereby the operations commute
fine even if the original data samples lied in different dimensions. We then
apply our proposed protocol for computing the private distance correlations as
shown in Figure 2. We use both the proposed estimators of
$\overline{\Omega}^{dp}(\mathbf{X,Y})$ or
$\Omega^{dp}_{\textrm{Disjt}}(\mathbf{X,Y})$ along with
$\overline{\Omega}^{dp}(\mathbf{X,X})$ on each of our considered datasets. We
compute the $l_{1}$ error between the true sample distance correlation (non-
private) and the proposed private estimators for each choice of privacy
parameter $\epsilon$. We plot these $\epsilon$ Vs. utility curves for each ouf
the considered dataset. In order to understand the sense of variability around
these utility estimates, we repeat the experiment multiple times and report
the variances observed in these plots from Figures 3 (a) to 3(f). In most
cases, we observe a substantially good utility in measuring sample distance
correlation at reasonably low levels of $\epsilon$. Furthermore, we studied
the effect of using the proposed disjoint private estimator
$\Omega^{dp}_{\textrm{Disjt}}(\mathbf{X,Y})$ Vs. using the repeated data
access private estimator $\overline{\Omega}^{dp}(\mathbf{X,Y})$ in the
following subsection. The privacy budgets in all the plots have been
calibrated according to the rules of their corresponding composition
properties for differential privacy[Dwork et al., 2014]. The effect of number
of partitions is also studied below.

###  6.1 Effect of disjoint Vs. repeated partitions

We study the effect of using the proposed estimator on disjoint partitions
$\overline{\Omega}^{dp}_{\textrm{Disjt}}(X,Y)$ as opposed to the entire
dataset being accessed for each $k$ as in the proposed estimator of
$\overline{\Omega}^{dp}(X,Y)$. Using disjoint partitions is beneficial to
conserving the privacy-budget via parallel composition property while on the
other side it reduces the number of samples the estimator for any $k$ would
have access to. This potentially has an effect on the utility or variance of
the estimator. This can been empirically observed as shown in the variances of
Figure 5 mostly being lesser than that of Figure 5 .

Figure 4: $\overline{\Omega}^{dp}(X,Y)$ \- No partitions

Figure 5: $\overline{\Omega}^{dp}_{\textrm{Disjt}}(X,Y)$ \- Disjoint
partitions

###  6.2 Effect of number of partitions

The choice of number of partitions has a trade-off between a.) reducing the
variance of the estimates and b.) losing the privacy-budget when it comes to
the estimator with repeat accesses to data. This is as opposed to the
estimator with disjoint partitions, where the trade-off is between reducing
the variance of the estimator and loss of utility for the estimator, due to
smaller set of samples being accessible within any partition.

##  7 Conclusion

We provided a method to privately compute distance correlation between data
hosted on two different parties. We provided theoretical and empirical
justification of our method. As measurement of nonlinear correlations is a
fundamental topic of interest to theoreticians and practitioners alike, we
thereby hope that this work brings this problem of private nonlinear
correlation estimation to a further mainstream consideration.

##  8 Future work

Distance correlation is a special case of a broader concept of energy
statistics [Székely and Rizzo, 2013b, Rizzo and Székely, 2016, Székely and
Rizzo, 2017]. Thereby solutions for its private estimation open up a door for
investigating multi-party private solutions for downstream problems that
depend on distance correlation such as multi-party private independence
testing, multi-party private feature screening and private multi-party private
causal inference.

##  Appendix A Proof of decomposition theorem

###### Proof.

$\displaystyle\overline{\Omega}^{dp}(X+N_{X},Y)$
$\displaystyle=\sum_{n=1}^{K}\frac{C_{p}C_{q}\Omega_{n}(u_{K}^{T}X+N_{X},v_{K}Y)}{K}=\sum_{n=1}^{K}\frac{C_{p}C_{q}}{K}\Bigl{\\{}\frac{1}{n(n-3)}\sum_{i\neq
j}\tilde{a}_{ij}\tilde{b}_{ij}-\frac{2}{n(n-2)(n-3)}\sum\tilde{a_{i\cdot}}\tilde{b_{i\cdot}}+$
$\displaystyle\frac{a_{..}b_{..}}{n(n-1)(n-2)(n-3)}\Bigr{\\}}=\sum_{n=1}^{K}\frac{C_{p}C_{q}}{K}\biggl{\\{}\frac{1}{n(n-3)}\sum_{i\neq
j}|u_{K}^{T}(X_{i}-X_{j})+N_{i}^{X}-N_{j}^{X}||V_{K}^{T}(Y_{i}-Y_{j})|$
$\displaystyle-\frac{2}{n(n-2)(n-3)}\sum_{i=1}^{n}(\sum_{j=1}^{n}|u_{K}^{T}(X_{i}-X_{j})+N_{i}^{X}-N_{j}^{X}|\sum_{j=1}^{n}|V_{K}^{T}(Y_{i}-Y_{j})|)$
$\displaystyle+\frac{(\sum_{i,j}^{n}|u_{K}^{T}(X_{i}-X_{j})+N_{i}^{X}-N_{j}^{X}|\sum_{k,l}^{n}|V_{K}^{T}(Y_{k}-Y_{l})|)}{n(n-1)(n-2)(n-3)}\biggr{\\}}$
$\displaystyle\leq\sum_{n=1}^{K}\frac{C_{p}C_{q}}{K}\Bigl{\\{}\frac{1}{n(n-3)}\sum_{i\neq
j}|u_{K}^{T}(X_{i}-X_{j})||V_{K}^{T}(Y_{i}-Y_{j})|+\frac{1}{n(n-3)}\sum_{i\neq
j}|(N_{i}^{X}-N_{j}^{X})||V_{K}^{T}(Y_{i}-Y_{j})|$
$\displaystyle-\frac{2}{n(n-2)(n-3)}\sum_{i=1}^{n}\biggl{(}\sum_{j=1}^{n}|u_{K}^{T}(X_{i}-X_{j})|\sum_{j=1}^{n}V_{K}^{T}(Y_{i}-Y_{j})|\biggr{)}$
$\displaystyle+\frac{2}{n(n-2)(n-3)}\sum_{i=1}^{n}\biggl{(}\sum_{j=1}^{n}|N_{i}^{X}-N_{j}^{X}|\sum_{j=1}^{n}V_{K}^{T}(Y_{i}-Y_{j})|\biggr{)}$
$\displaystyle+\frac{1}{n(n-1)(n-2)(n-3)}\biggl{(}\sum_{i,j}^{n}|u_{K}^{T}(X_{i}-X_{j})|\sum_{k,l}^{n}|V_{K}^{T}(Y_{k}-Y_{l})|+\sum_{i,j}^{n}|N_{i}^{X}-N_{j}^{X}|\sum_{k,l}^{n}|V_{K}^{T}(Y_{k}-Y_{l})|\biggr{)}\Bigr{\\}}$
$\displaystyle=\sum_{n=1}^{K}\frac{C_{p}C_{q}}{K}\Bigl{\\{}\frac{1}{n(n-3)}\sum_{i\neq
j}|u_{K}^{T}(X_{i}-X_{j})||V_{K}^{T}(Y_{i}-Y_{j})|-\frac{2}{n(n-2)(n-3)}\sum_{i=1}^{n}\biggl{(}\sum_{j=1}^{n}|u_{K}^{T}(X_{i}-X_{j})|\sum_{j=1}^{n}V_{K}^{T}(Y_{i}-Y_{j})|\biggr{)}$
$\displaystyle+\frac{1}{n(n-1)(n-2)(n-3)}\biggl{(}\sum_{i,j}^{n}|u_{K}^{T}(X_{i}-X_{j})|\sum_{k,l}^{n}|V_{K}^{T}(Y_{k}-Y_{l})|\biggr{)}$
$\displaystyle-\frac{2}{n(n-2)(n-3)}\sum_{i=1}^{n}\biggl{(}\sum_{j=1}^{n}|N_{i}^{X}-N_{j}^{X}|\sum_{j=1}^{n}V_{K}^{T}(Y_{i}-Y_{j})|\biggr{)}+\frac{1}{n(n-3)}\sum_{i\neq
j}|(N_{i}^{X}-N_{j}^{X})||V_{K}^{T}(Y_{i}-Y_{j})|$
$\displaystyle+\frac{1}{n(n-1)(n-2)(n-3)}\biggl{(}\sum_{i,j}^{n}|N_{i}^{X}-N_{j}^{X}|\sum_{k,l}^{n}|V_{K}^{T}(Y_{k}-Y_{l})|\biggr{)}\Bigr{\\}}$
$\displaystyle+\sum_{n=1}^{K}\frac{4C_{p}C_{q}}{Kn(n-2)(n-3)}\sum_{i=1}^{n}\biggl{(}\sum_{j=1}^{n}|N_{i}^{X}-N_{j}^{X}|\sum_{j=1}^{n}V_{K}^{T}(Y_{i}-Y_{j})|\biggr{)}$
$\displaystyle=\overline{\Omega}(X,Y)+\overline{\Omega}(N^{X},Y)+\sum_{n=1}^{K}\frac{4C_{p}C_{q}}{Kn(n-2)(n-3)}\sum_{i=1}^{n}\biggl{(}\sum_{j=1}^{n}|N_{i}^{X}-N_{j}^{X}|\sum_{j=1}^{n}V_{K}^{T}(Y_{i}-Y_{j})|\biggr{)}$
(7)

∎

We have used the inequalities $|a+b|\leq|a|+|b|$ and $|a+b|\geq|a|-|b|$ for
two vectors $a$ and $b$ where $|a|$ refers to the modulus of vector $a$. For
any fixed $n$, $\hat{\Omega}(X,Y)$ is denoted by $\Omega_{n}(X,Y)$. Here
$\overline{\Omega}(N^{X},Y)$ is defined by

######  Lemma 1.

For $a,b$ and $c$ $\in\mathbb{R}^{+}$, given that $p\left(a_{i}<c\right)>b$
for $i=1,2,\ldots,n$ we will show that $P\left(\sum a_{i}<nc\right)\geqslant
1-n(1-b)$.

###### Proof.

$p\left(\sum a_{i}<nc\right)\geqslant P\left(a_{1}<c\cap
a_{2}<c\ldots.\right.$ $\left.\cap a_{n}<c\right)$ $=1-P\left(a_{1}\geqslant
c\cup a_{2}\geqslant c\cup a_{3}\geqslant C\right.$ $\left.\ldots\quad\cup
a_{n}\geqslant c\right)$ $\geqslant 1-p\left(a_{1}\geqslant
c\right)-p\left(a_{2}\geqslant c\right)$ $\ldots-p\left(a_{n}>c\right)$ $\geq
1-n(1-b)$ ∎

###  A.1 Proof for the bound on error term

###### Proof.

Now as the $N_{i}^{X}$’s are drawn from a mean zero Gaussian distribution
where $\sigma^{2}\geq
w_{2}(P)\frac{\sqrt{2ln(1/2\delta)+\epsilon}}{\epsilon}$. Assuming $N_{i}^{X}$
and $N_{l}^{X}$ are sampled independently for any $l\neq i$, if
$s_{l}=N_{i}^{X}-N_{l}^{X}$, the distribution of $s_{l}$ terms will be
therefore $N(0,2\sigma^{2})$. Now let
$\tau_{i}=\sum_{l=1}^{n}|N_{i}^{X}-N_{l}^{X}|=\sum_{l=1,l\neq
i}^{n}|N_{i}^{X}-N_{l}^{X}|=\sum_{l=1,l\neq i}^{n}|s_{l}|$ It is critical to
note that the $s_{l}$’s are not independent anymore. Therefore, we consider
$\tau_{i}$’s instead as for the expectation $\mathbb{E}(\tau_{i})$, the
correlation between $s_{l}$’s would not matter anymore. Now,
$\mathbb{E}(\tau_{i})=(n-1)\mathbb{E}(s_{1})$. This brings us into the regime
of half-normal or folded normal distributions. If $X\sim
N(0,\sigma^{2}),Y=|X|$, then we know that
$\mathbb{E}[Y]=\sigma\sqrt{\frac{2}{\pi}}$ and
$Var(Y)=\sigma^{2}(1-\frac{2}{\pi})$. In our case
$\mathbb{E}[s_{1}]=\sigma\sqrt{2}\times\sqrt{\frac{2}{\pi}}=\frac{2\sigma}{\sqrt{\pi}}$
and $Var(s_{1})=2\sigma^{2}(1-\frac{2}{\pi})$. We now need a concentration
bound for $\sum_{l=1,l\neq i}^{n}|N_{i}^{X}-N_{l}^{X}|$.

$\displaystyle\sum_{l=1,l\neq
i}^{n}|N_{i}^{X}-N_{l}^{X}|\leq(n-1)|N_{i}^{X}|+\sum_{l=1,l\neq
i}^{n}|N_{l}^{X}|$

The moment generating function of a standard Gaussian random variable $X$ is
$\mathbb{E}[e^{tX}]=e^{\frac{\sigma^{2}t^{2}}{2}}$ for all $t\in\mathbb{R}$.
We would want to find a concentration bound on
$|(n-1)N_{i}^{X}|+\sum_{l=1,l\neq i}^{l=n}|N_{i}^{X}|$. We denote
$(n-1)N_{i}^{X}$ as $N_{i}^{\prime}$. Note that $(n-1)N_{i}^{X}$ and
$N_{l}^{X}$ where $l\neq i$ are all i.i.d. The required concentration bound
can be written in terms of the moment generating function as

$\displaystyle P\left\\{\frac{1}{n}\left(|(n-1)N_{i}^{X}|+\sum_{l=1;l\neq
i}^{l=n}|N_{i}^{X}|\right)\geq t\right\\}$
$\displaystyle=P\left\\{\exp{\left(\frac{\lambda}{n}(|(n-1)N_{i}^{X}|+\sum_{l\neq
i}^{l=n}|N_{i}^{X}|)\right)\geq e^{\lambda t}}\right\\}$ $\displaystyle\leq
e^{-\lambda
t}\mathbb{E}\left[\exp{\left(\frac{\lambda}{n}(|(n-1)N_{i}^{X}|+\sum_{l=1,l\neq
i}^{l=n}|N_{i}^{X}|)\right)}\right]$ $\displaystyle=e^{-\lambda
t}\mathbb{E}\left[\left(\prod_{k=1;k\neq
i}^{n}e^{\frac{\lambda}{n}|N_{k}^{X}|}\right)e^{\frac{\lambda}{n}|(n-1)N_{i}^{X}|}\right]$
$\displaystyle=e^{-\lambda t}\prod_{k=1;k\neq
i}^{n}\mathbb{E}\left[e^{\frac{\lambda}{n}|N_{k}^{X}|}\right]\mathbb{E}\left[e^{\frac{\lambda}{n}|(n-1)N_{i}^{X}|}\right]\text{(as
they are independent)}$

Now based on the properties of moment generating functions we have,

$\displaystyle\mathbb{E}\left[e^{t|X_{k}|}\right]$
$\displaystyle\leq\mathbb{E}\left[e^{t|X_{k}|}+e^{-t|X_{k}|}\right]$ (8)
$\displaystyle=\mathbb{E}[e^{tX_{k}}+e^{-tX_{k}}]$
$\displaystyle=\mathbb{E}[e^{tX_{k}}]+\mathbb{E}[e^{tX_{k}}]$
$\displaystyle=2\mathbb{E}[e^{tX_{k}}]$
$\displaystyle=2e^{\frac{\sigma^{2}t^{2}}{2}}\text{as m.g.f for Gaussians is
}m_{X}(t)=e^{\mu t+\frac{\sigma^{2}t^{2}}{2}}$

We have that $\mathbb{E}[e^{\frac{\lambda}{n}|N_{k}^{X}|}]\leq
2e^{\frac{\lambda^{2}\sigma^{2}}{2n^{2}}}$ and
$\mathbb{E}[e^{\frac{\lambda}{n}|(n-1)N_{i}^{X}|}]\leq
2e^{\frac{\lambda^{2}}{2n^{2}}(n-1)\sigma^{2}}$.

From eqn. A.1 the r.h.s of the inequality is $e^{-\lambda
t}2^{n}e^{\frac{\lambda^{2}\sigma^{2}(n-1)}{n^{2}}}$

Therefore

$\mathbb{P}\\{expression\geq nt\\}\leq e^{-\lambda
t}2^{n}e^{\frac{\lambda^{2}\sigma^{2}(n-1)}{n^{2}}}$

As we want to minimize the upper bound, $\therefore\frac{\partial}{\partial
l}(-\lambda t+\frac{\lambda^{2}\sigma^{2}(n-1)}{n^{2}}=0)$ or,
$-t+2\lambda\frac{(n-1)\sigma^{2}}{n^{2}}=0$. So we have,
$\lambda=\frac{n^{2}t}{2\sigma^{2}(n-1)}$.

Therefore, $\mathbb{P}\\{expression\geq nt\\}\leq
e^{-\frac{n^{2}t^{2}}{4\sigma^{2}(n-1)}}2^{n}$ and in the case, where the
probability needs to kept under a chosen level $\alpha$, then we have
$\left(\frac{2}{e^{\frac{nt^{2}}{4\sigma^{2}(n-1)}}}\right)^{n}<\alpha$. Upon
applying $\log$ on both sides we have
$n\log\left(\frac{2}{e^{\frac{nt^{2}}{4\sigma^{2}(n-1)}}}\right)<\log(\alpha)$
and upon rearranging the terms we have,

$t>2\sigma\sqrt{(\frac{n-1}{n})(\log(2)-\frac{\log(\alpha)}{n})}$

Let us denote $expression=|(n-1)N_{i}^{X}|+\sum_{l=1,l\neq
i}^{l=n}|N_{l}^{X}|$ for brevity. We know that

$P(expression\geq nt)\leq e^{-\frac{n^{2}t^{2}}{4\sigma^{2}(n-1)}}\times
2^{n}$

Note that $\sum_{l=1}^{n}|N_{i}^{X}-N_{l}^{X}|\leq expression$ . Therefore we
have,

$P(\sum_{l=1}^{n}|N_{i}^{x}-N_{l}^{X}|\geq nt)\leq
e^{-\frac{n^{2}t^{2}}{4\sigma^{2}(n-1)}}\times 2^{n}$

We now work with the next expression $\sum_{l=1}^{n}|V_{k}^{t}(Y_{i}-Y_{l})|$.
Note that each entry of $V_{k}^{T}$ is sampled independently from a Gaussian
as part of ensuring differential privacy. As $Y_{i}$’s are one-hot encoded,
therefore $V_{k}^{T}Y_{i}$ and $V_{k}^{T}Y_{l}$ are two independently sampled
entries from the vector $V_{k}^{T}$. Assuming, $V_{k}^{t}Y_{i}$ are from
distribution $N(0,\sigma_{1}^{2})$ and $N^{X}_{i}$s are from distribution
$N(0,\sigma_{2}^{2})$, we can write that

$P(\sum_{l=1}^{n}|V_{k}^{T}(Y_{i}-Y_{l})|\geq nt_{1}))\leq
e^{\frac{-n^{2}t_{1}^{2}}{4(n-1)\sigma_{1}^{2}}}\times 2^{n}$

and

$P(\sum_{l=1}^{n}|N^{X}_{i}-N^{X}_{l})|\geq nt_{2}))\leq
e^{\frac{-n^{2}t_{2}^{2}}{4(n-1)\sigma_{2}^{2}}}\times 2^{n}$

. Denoting the rhs of these inequalities as $\alpha_{1}$ and $\alpha_{2}$
respectively, we can write

$P(\sum_{l=1}^{n}|V_{k}^{T}(Y_{i}-Y_{l})|<nt_{1}))\geq 1-\alpha_{1}$

and

$P(\sum_{l=1}^{n}|N^{X}_{i}-N^{X}_{l}|<nt_{2}))\geq 1-\alpha_{2}$

Note that
$P(\sum_{l=1}^{n}|V_{k}^{T}(Y_{i}-Y_{l})|\sum_{l=1}^{n}|N^{X}_{i}-N^{X}_{l}|<n^{2}t_{1}t_{2})\geq
P(\sum_{l=1}^{n}|V_{k}^{T}(Y_{i}-Y_{l})|<nt_{1})P(\sum_{l=1}^{n}|N^{X}_{i}-N^{X}_{l}|<nt_{2})$
since these two events are clearly independent and for independent $a,b$,
$P(ab<c^{2})>P(a<c)P(b<c)$ holds.

Therefore,
$P(\sum_{l=1}^{n}|V_{k}^{T}(Y_{i}-Y_{l})|\sum_{l=1}^{n}|N^{X}_{i}-N^{X}_{l}|<n^{2}t_{1}t_{2})\geq(1-\alpha_{1})(1-\alpha_{2})$.
Now using lemma 1, we get that
$P(\sum_{i=1}^{n}(\sum_{l=1}^{n}|V_{k}^{T}(Y_{i}-Y_{l})|\sum_{l=1}^{n}|N^{X}_{i}-N^{X}_{l}|<n^{3}t_{1}t_{2}))\geq
1-n(\alpha_{1}+\alpha_{2}-\alpha_{1}\alpha_{2})$. So for any constant $C$, we
can write
$P(C\sum_{i=1}^{n}(\sum_{l=1}^{n}|V_{k}^{T}(Y_{i}-Y_{l})|\sum_{l=1}^{n}|N^{X}_{i}-N^{X}_{l}|<Cn^{3}t_{1}t_{2}))\geq
1-n(\alpha_{1}+\alpha_{2}-\alpha_{1}\alpha_{2})$. Therefore, for each $n$,
$\frac{4C_{p}C_{q}}{Kn(n-2)(n-3)}\sum_{i=1}^{n}\biggl{(}\sum_{j=1}^{n}|N_{i}^{X}-N_{j}^{X}|\sum_{j=1}^{n}V_{K}^{T}(Y_{i}-Y_{j})|\biggr{)}$
is upper bounded with a high probability. The error term is a summation for
all $n$ from $1$ to $K$ and hence the error term is bounded too with a high
probability. ∎

Dataset | min $tbd$ | max$tbd$
---|---|---
| Condition Based Maintenance
---
of Naval Propulsion Plants
0.0583 | 0.0641
Parkinsons Telemonitoring | 0.0689 | 0.0827
Wine Quality | 0.03687 | 0.0475
Boston Housing | 0.0106 | 0.0263
Madelon | 0.0919 | 0.1046
Geographic origin of music | 0.1784 | 0.2547
Skill craft 1 Master Table | 0.1368 | 0.1662
Seoul bike sharing demand | 0.1740 | 0.1844

##  Appendix B 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

##  Appendix C Preliminaries for differential privacy

######  Definition 3.

$(\epsilon,\delta)$-Differential Privacy (2014)

A randomized algorithm $\mathcal{A}:\mathcal{X}\rightarrow\mathcal{Y}$ is
$(\epsilon,\delta)$-differentially private if, for all neighboring datasets
$\mathbf{X},\mathbf{X}^{\prime}\in\mathcal{X}$ and for all $S\in\mathcal{Y}$

$\operatorname{Pr}[\mathcal{A}(\mathbf{X})\in S]\leq
e^{\epsilon}\operatorname{Pr}\left[\mathcal{A}\left(\mathbf{X}^{\prime}\right)\in
S\right]+\delta$

######  Definition 4.

Post-Processing Invariance

Differential privacy is immune to post-processing, meaning that an adversary
without any additional knowledge about the dataset $\mathbf{X}$ cannot compute
a function on the output $\mathcal{A}(\mathbf{X})$ to violate the stated
privacy guarantees.

######  Definition 5.

$\left(l_{2}\right.$-Global Sensitivity)

Let $f:\mathcal{X}\rightarrow\mathbb{R}^{k}$. The $l_{2^{-}}$ global
sensitivity of $f$ is

$\Delta_{2}^{(f)}=\max_{\mathbf{x},\mathbf{X}^{\prime}\in\mathcal{X}}\left\|f(\mathbf{X})-f\left(\mathbf{X}^{\prime}\right)\right\|_{2}$

where $\mathbf{X},\mathbf{X}^{\prime}$ are neighboring databases.

##  Appendix D Differentially private random projections

We state one of the classic mechanisms from [Kenthapadi et al., 2013] that is
relevant to some aspects of our proposed method. We first share a prerequisite
definition that is required prior to re-stating this mechanism. We denote the
random projection matrix by $\mathbf{P}$, and note that one of the popular
choices for building it is to have each entry of the matrix drawn
independently from a Normal distribution with mean $0$ and $\sigma^{2}=1/k$.
We now define the $\ell_{\rho}$-Sensitivity of $P$.

######  Definition 6.

$\left(\ell_{\rho}\right.$-Sensitivity of $\left.P\right)$. Define the
$l_{\rho}$-sensitivity of a $d\times k$ projection matrix
$P=\left\\{P_{ij}\right\\}_{d\times k}$ denoted by $w_{\rho}(P)$, as the
maximum $\ell_{\rho}$-norm of any row in $P$, i.e., $w_{\rho}(P)=\max_{1\leq
i\leq
d}\left(\sum_{j=1}^{k}\left|P_{ij}\right|^{\rho}\right)^{\frac{1}{\rho}}$
Equivalently, $w_{\rho}(P)$ can be defined as
$\max_{e_{i}}\left\|e_{i}P\right\|_{\rho}$, where
$\left\\{e_{i}\right\\}_{i=1}^{d}$ are standard basis unit vectors.

######  Theorem 4.

Let $w_{2}(P)$ be the $\ell_{2}$-sensitivity of the projection matrix $P$ (see
Definition 2). Assuming $\delta<\frac{1}{2}$, let the entries of the noise
matrix be drawn from $N\left(0,\sigma^{2}\right)$ with $\sigma\geq
w_{2}(P)\frac{\sqrt{2\left(\ln\left(\frac{1}{2\delta}\right)+\epsilon\right)}}{\epsilon}$,
then releasing $\mathbf{Z=XP+\Delta}$ satisfies
$(\epsilon,\delta)$-differential privacy.

###### Proof.

[Kenthapadi et al., 2013] ∎

## References

  * [Asghar et al., 2021] Asghar, H. J., Ding, M., Rakotoarivelo, T., Mrabet, S., and Kaafar, D. (2021).  Differentially private release of datasets using gaussian copula.  Journal of Privacy and Confidentiality, 10(2).
  * [Blocki et al., 2012] Blocki, J., Blum, A., Datta, A., and Sheffet, O. (2012).  The johnson-lindenstrauss transform itself preserves differential privacy.  In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 410–419. IEEE.
  * [Canonne, 2020] Canonne, C. L. (2020).  A survey on distribution testing: Your data is big. but is it blue?  Theory of Computing, pages 1–100.
  * [Chaudhuri and Hu, 2019] Chaudhuri, A. and Hu, W. (2019).  A fast algorithm for computing distance correlation.  Computational Statistics & Data Analysis.
  * [Dwork, 2006] Dwork, C. (2006).  Differential privacy.  In International Colloquium on Automata, Languages, and Programming, pages 1–12. Springer.
  * [Dwork, 2008] Dwork, C. (2008).  Differential privacy: A survey of results.  In International conference on theory and applications of models of computation, pages 1–19. Springer.
  * [Dwork et al., 2014] Dwork, C., Roth, A., et al. (2014).  The algorithmic foundations of differential privacy.  Found. Trends Theor. Comput. Sci., 9(3-4):211–407.
  * [Fan and Lv, 2018] Fan, J. and Lv, J. (2018).  Sure independence screening.  Wiley StatsRef: Statistics Reference Online.
  * [Gaboardi et al., 2016] Gaboardi, M., Lim, H., Rogers, R., and Vadhan, S. (2016).  Differentially private chi-squared hypothesis testing: Goodness of fit and independence testing.  In International conference on machine learning, pages 2111–2120. PMLR.
  * [Gondara and Wang, 2020] Gondara, L. and Wang, K. (2020).  Differentially private small dataset release using random projections.  In Conference on Uncertainty in Artificial Intelligence, pages 639–648. PMLR.
  * [Gretton et al., 2005] Gretton, A., Bousquet, O., Smola, A., and Schölkopf, B. (2005).  Measuring statistical dependence with hilbert-schmidt norms.  In International conference on algorithmic learning theory, pages 63–77. Springer.
  * [Huang and Huo, 2017] Huang, C. and Huo, X. (2017).  A statistically and numerically efficient independence test based on random projections and distance covariance.  arXiv preprint arXiv:1701.06054.
  * [Huo and Székely, 2016] Huo, X. and Székely, G. J. (2016).  Fast computing for distance covariance.  Technometrics, 58(4):435–447.
  * [Kenthapadi et al., 2013] Kenthapadi, K., Korolova, A., Mironov, I., and Mishra, N. (2013).  Privacy via the johnson-lindenstrauss transform.  Journal of Privacy and Confidentiality, 5(1).
  * [Kusner et al., 2015] Kusner, M. J., Sun, Y., Sridharan, K., and Weinberger, K. Q. (2015).  Inferring the causal direction privately.  stat, 1050:17.
  * [Kusner et al., 2016] Kusner, M. J., Sun, Y., Sridharan, K., and Weinberger, K. Q. (2016).  Private causal inference.  In Artificial Intelligence and Statistics, pages 1308–1317. PMLR.
  * [Li et al., 2014] Li, H., Xiong, L., and Jiang, X. (2014).  Differentially private synthesization of multi-dimensional data using copula functions.  In Advances in database technology: proceedings. International conference on extending database technology, volume 2014, page 475. NIH Public Access.
  * [Li et al., 2012] Li, R., Zhong, W., and Zhu, L. (2012).  Feature screening via distance correlation learning.  Journal of the American Statistical Association, 107(499):1129–1139.
  * [Lu et al., 2021] Lu, S., Chen, X., and Wang, H. (2021).  Conditional distance correlation sure independence screening for ultra-high dimensional survival data.  Communications in Statistics-Theory and Methods, 50(8):1936–1953.
  * [Rizzo and Székely, 2016] Rizzo, M. L. and Székely, G. J. (2016).  Energy distance.  wiley interdisciplinary reviews: Computational statistics, 8(1):27–38.
  * [Shen et al., 2019] Shen, C., Priebe, C. E., and Vogelstein, J. T. (2019).  The exact equivalence of independence testing and two-sample testing.  arXiv preprint arXiv:1910.08883.
  * [Shen and Vogelstein, 2021] Shen, C. and Vogelstein, J. T. (2021).  The exact equivalence of distance and kernel methods in hypothesis testing.  AStA Advances in Statistical Analysis, 105(3):385–403.
  * [Swanberg et al., 2019] Swanberg, M., Globus-Harris, I., Griffith, I., Ritz, A., Groce, A., and Bray, A. (2019).  Improved differentially private analysis of variance.  Proceedings on Privacy Enhancing Technologies, 2019(3):310–330.
  * [Székely and Rizzo, 2013a] Székely, G. J. and Rizzo, M. L. (2013a).  The distance correlation t-test of independence in high dimension.  Journal of Multivariate Analysis, 117:193–213.
  * [Székely and Rizzo, 2013b] Székely, G. J. and Rizzo, M. L. (2013b).  Energy statistics: A class of statistics based on distances.  Journal of statistical planning and inference, 143(8):1249–1272.
  * [Székely and Rizzo, 2017] Székely, G. J. and Rizzo, M. L. (2017).  The energy of data.  Annual Review of Statistics and Its Application, 4:447–479.
  * [Székely et al., 2007] Székely, G. J., Rizzo, M. L., and Bakirov, N. K. (2007).  Measuring and testing dependence by correlation of distances.  The annals of statistics, 35(6):2769–2794.
  * [Thakurta and Smith, 2013] Thakurta, A. G. and Smith, A. (2013).  Differentially private feature selection via stability arguments, and the robustness of the lasso.  In Conference on Learning Theory, pages 819–850. PMLR.
  * [Upadhyay, 2013] Upadhyay, J. (2013).  Random projections, graph sparsification, and differential privacy.  In International Conference on the Theory and Application of Cryptology and Information Security, pages 276–295. Springer.
  * [Xu et al., 2017] Xu, C., Ren, J., Zhang, Y., Qin, Z., and Ren, K. (2017).  Dppro: Differentially private high-dimensional data release via random projection.  IEEE Transactions on Information Forensics and Security, 12(12):3081–3093.
  * [Zhong and Zhu, 2015] Zhong, W. and Zhu, L. (2015).  An iterative approach to distance correlation-based sure independence screening.  Journal of Statistical Computation and Simulation, 85(11):2331–2345.