# Differentially Private Conditional Independence Testing

Iden Kalemaj
Boston Unviersity
<EMAIL_ADDRESS>This work was conducted during an internship at Amazon. Shiva
Prasad Kasiviswanathan
Amazon
<EMAIL_ADDRESS>Aaditya Ramdas
Carnegie Mellon University
<EMAIL_ADDRESS>
###### Abstract

Conditional independence (CI) tests are widely used in statistical data
analysis, e.g., they are the building block of many algorithms for causal
graph discovery. The goal of a CI test is to accept or reject the null
hypothesis that $X\perp\\!\\!\\!\perp Y\mid Z$, where
$X\in\mathbb{R},Y\in\mathbb{R},Z\in\mathbb{R}^{d}$. In this work, we
investigate conditional independence testing under the constraint of
differential privacy. We design two private CI testing procedures: one based
on the generalized covariance measure of Shah and Peters (2020) and another
based on the conditional randomization test of Candès et al. (2016) (under the
model-X assumption). We provide theoretical guarantees on the performance of
our tests and validate them empirically. These are the first private CI tests
with rigorous theoretical guarantees that work for the general case when $Z$
is continuous.

##  1 Introduction

Conditional independence (CI) tests are a powerful tool in statistical data
analysis, e.g., they are building blocks for graphical models, causal
inference, and causal graph discovery [9, 20, 26]. These analyses are
frequently performed on sensitive data, such as clinical datasets and
demographic datasets, where concerns for privacy are foremost. For example, in
clinical trials, CI tests are used to answer fundamental questions such as
“After accounting for (conditioning on) a set of patient covariates $Z$ (e.g.,
age or gender), does a treatment $X$ lead to better patient outcomes $Y$?”.
Formally, given three random variables $(X,Y,Z)$ where $X\in\mathbb{R}$,
$Y\in\mathbb{R}$, and $Z\in\mathbb{R}^{d}$, denote the conditional
independence of $X$ and $Y$ given $Z$ by $X\perp\\!\\!\\!\perp Y\mid Z$. Our
problem is that of testing

$\displaystyle H_{0}\text{ (null)}:X\perp\\!\\!\\!\perp Y\mid Z\mbox{ vs.
}H_{1}\text{ (alternate) }:X\cancel{\perp\\!\\!\\!\perp}Y\mid Z$

given data drawn i.i.d. from a joint distribution of $(X,Y,Z)$. CI testing is
a much harder problem than (unconditional) independence testing, where the
variable $Z$ is omitted. Indeed, Shah and Peters [30] showed that CI testing
is a statistically impossible task for continuous random variables.111Any test
that uniformly controls the type-I error (false positive rate) for all
absolutely continuous triplets $(X,Y,Z)$ such that $X\perp\\!\\!\\!\perp Y\mid
Z$, even asymptotically, does not have nontrivial power against _any_
alternative. Thus, techniques for independence testing _do not_ extend to the
CI testing problem.

When the underlying data is sensitive and confidential, publishing statistics
(such as the value of a CI independence test statistic or the corresponding
p-value) can leak private information about individuals in the data. For
instance, Genome-Wide Association Studies (GWAS) involve finding (causal)
relations between Single Nucleotide Polymorphisms (SNPs) and diseases. CI
tests are building blocks for establishing these relations, and the existence
of a link between a specific SNP and a rare disease may indicate the presence
of a minority patient. _Differential privacy_ [13] is a widely studied and
deployed formal privacy guarantee for data analysis. The output distributions
of a differentially private algorithm must look nearly indistinguishable for
any two input datasets that differ only in the data of a single individual. In
this work, we design the first differentially private (DP) CI tests that can
handle continuous variables.

#### Our Contributions.

We design two private CI tests, each based on a different set of assumptions
about the data-generating distribution. We provide the first private CI test
with rigorous type-I error and power guarantees. Given the aforementioned
impossibility results for non-private CI testing, to obtain a CI test with
meaningful theoretical guarantees, some assumptions are necessary; in
particular we must restrict the space of possible null distributions. In
designing our private tests, we start with non-private CI tests that provide
rigorous guarantees on type-I error control.

Our first test (Section 3) is a private version of the generalized covariance
measure (GCM) by Shah and Peters [30]. The type-I error guarantees of the GCM
rely on the fairly weak assumption that the conditional means
$\mathbb{E}[X\mid Z]$ and $\mathbb{E}[Y\mid Z]$ can be estimated sufficiently
well given the dataset size. The test statistic of the GCM is a normalized sum
of the product of the residuals of (nonlinearly) regressing $X$ on $Z$ and $Y$
on $Z$. This test statistic has _unbounded_ sensitivity, thus a more careful
way of adding and analyzing the impact of the privacy noise is needed. Our
private GCM test adds appropriately scaled, zero-mean noise to the residual
products, and calculates the same statistic on the noisy residual products. We
show that even with the added noise, the GCM score converges asymptotically to
a standard Gaussian distribution under the null hypothesis. The magnitude of
the noise added to the residuals is constant (it does not vanish with
increasing sample size $n$), thus apriori it is surprising that convergence
results can be obtained in the presence of such noise. We do so by bounding
how the added noise interacts with the noise from the estimation of the
residuals. While our asymptotics justify the threshold for rejecting the null,
our private GCM test controls type-I error very well at small finite $n$, as
we demonstrate empirically (because the central limit theorem kicks in rather
quickly). Recall that finite sample guarantees on type-I error and power are
impossible even for non-private CI testing [30].

The private GCM is the _first_ private CI test with rigorous power guarantees.
It achieves the same power as the non-private GCM test with a
$O(1/\varepsilon^{2})$-inflation of the dataset size. In addition, while
private extensions of non-private hypothesis tests often suffer from
introducing excessive type-I error (see the Related Work), the private GCM
exhibits the opposite behavior: it can maintain type-I error control even when
the non-private GCM test fails to do so. This occurs in scenarios where the
regression methods used to estimate the conditional means either underfit or
overfit.

Our second test (Section 4) relies on the _model-X assumption_ that the
conditional distribution of $X\mid Z$ is known or can be well-approximated.
Recently introduced by Candès et al. [6], this assumption is useful in
settings where one has access to abundant unlabeled data, such as in GWAS, but
labeled data are scarce. The model-X assumption is also satisfied in
experimental settings where a randomization mechanism is known or designed by
the experimenter. CI tests utilizing this assumption provide exact, non-
asymptotic, type-I error control [6, 3], thus bypassing the hardness result of
Shah and Peters [30]. While this assumption has spurred a lot of recent
research in (non-private) CI testing, there are no prior private tests in the
literature that are designed to work under this assumption. In this work, we
focus on the conditional randomization test (CRT) [6]. We design a private CRT
and provide theoretical guarantees on the accuracy of its p-value. We adopt a
popular framework for obtaining DP algorithms, known as Report Noisy Max (or
the exponential mechanism), which requires defining a problem-specific score
function of low sensitivity. To obtain good utility, our score function
exploits the specific distribution of intermediate statistics calculated by
the CRT. This score function is novel and can be used for solving a more
general problem: given a set of queries on a dataset, estimate privately the
rank of a particular query amongst the rest of the queries.

We present a detailed empirical evaluation of the proposed tests, justifying
their practicality across a wide range of settings. Our experiments confirm
that our private CI tests provide the critical type-I error control, and can
in fact do so more reliably than their non-private counterparts. As expected,
our private tests achieve lower power due to the noise injected for privacy,
which can be compensated for with a larger dataset size.

###  1.1 Related Work

#### Private Conditional Independence Testing.

Wang et al. [37] is the only work, prior to ours, to explicitly study private
CI testing, motivated by an application to causal discovery. Their tests
(obtained from Kendall’s $\tau$ and Spearman’s $\rho$ score) are designed for
categorical $Z$. While these tests could be adapted to work for continuous $Z$
via clustering, in practice this method does not seem to control type-I error,
as we show in Fig. 1. The problem worsens with higher-dimensional $Z$. Our
techniques also differ from those of Wang et al. [37], who obtain their tests
by bounding the sensitivity of non-private CI scores and adding appropriately
scaled noise to the true value of the score. They state two open problems:
obtaining private CI tests for continuous $Z$ and obtaining private tests from
scores of unbounded sensitivity (as is the case with the GCM score). We solve
both open problems, and manage to privatize the GCM score by instead adding
noise to an intermediate statistic, the residuals of fitting $X$ to $Z$ and
$Y$ to $Z$.

Another line of work [31, 18, 27] has utilized the “subsample and aggregate”
framework of differential privacy [25] to obtain private versions of existing
hypothesis tests in a black-box fashion. In this approach, the dataset is
partitioned into $k$ smaller datasets; the non-private hypothesis test is
evaluated on the smaller datasets; and finally, the results are privately
aggregated. Based on this method, Kazan et al. [18] propose a test-of-tests
(ToT) framework to construct a private version of any known (non-private)
hypothesis test. However, they show guarantees on the power of their test
based on finite-sample guarantees of the power of the non-private hypothesis
test. Since finite-sample guarantees are impossible for CI testing, their
method gives _no_ power guarantees for CI testing, and thus cannot be reliably
used in practice. In addition, in Fig. 1 we compare the type-I error control
of our tests with the ToT framework and show that it can fail to control
type-I error.

Smith [31] analyzed the asymptotic properties of subsample-and-aggregate and
showed that for a large family of statistics, one can obtain a corresponding
DP statistic with the same asymptotic distribution as the original statistic.
In particular, the result of Smith [31] can be applied to obtain a DP version
of the GCM statistic. However, compared to our results on the private GCM, (a)
only a weaker notion of privacy, known as _approximate_ DP, would be
guaranteed, and (b) an additional condition on the data-generating
distribution would have to be introduced, to guarantee a bounded third moment
of the GCM statistic. Finally, the test of Peña and Barrientos [27] only
outputs a binary accept/reject decision and not a p-value as our tests
provide, and was empirically outperformed by the test of Kazan et al. [18].

#### Private (non-conditional) Independence Testing.

A line of work on private independence testing has focused on privatizing the
chi-squared statistic [36, 17, 34, 41, 38, 16, 28]. These tests operate with
categorical $X$ and $Y$. Earlier works obtained private hypothesis tests by
adding noise to the histogram of the data [17], but it was later pointed out
that this approach does not provide reliable type-I error control at small
sample sizes [14]. Consequent works used numerical approaches to obtain the
distribution of the noisy statistic and calculate p-values with that
distribution [34, 41, 38, 16], whereas Rogers and Kifer [28] obtain new
statistics for chi-squared tests whose distribution after the privacy noise
can be derived analytically. In this light, one important feature of our
private GCM test is that its type-I error control can be more reliable than
for the non-private GCM, even at small $n$, as our experiments demonstrate.
For continuous $X$ and $Y$, Kusner et al. [21] obtained DP versions of several
dependence scores (Kendall’s $\tau$, Spearman’s $\rho$, HSIC), however, they
do not provide type-I error or power guarantees. In follow-up work, Kim and
Schrab [19] obtained private versions of permutation tests, that were applied
to kernel-based independence tests, such as HSIC. Note that CI testing is a
much harder task than independence testing, and techniques for the latter do
not necessarily translate to CI testing. Our work is part of the broader
literature on private hypothesis testing [2, 5, 33, 8, 39, 1, 4, 10, 35].

#### Non-private Conditional Independence Testing.

A popular category of CI tests are kernel-based tests, obtained by extending
the Hilbert-Schmidt independence criterion to the conditional setting [15, 42,
32]. However, these tests only provide a weaker _pointwise_ asymptotic
validity guarantee. It is widely acknowledged that for a statistical test to
be useful in practice, it needs to provide the stronger guarantees of either
valid level at finite sample size or _uniformly_ asymptotic level. Our private
GCM test provides the latter guarantee.

One way of getting around the hardness result of Shah and Peters [30] is
through the model-X assumption, where the conditional distribution of $X\mid
Z$ is assumed to be accessible. Tests based on this assumption, such as CRT
(conditional randomization test) [6] and CPT (conditional permutation test)
[3], provide a general framework for conditional independence testing, where
one can use their test statistic of choice and exactly (non-asymptotically)
control the type-I error regardless of the data dimensionality.

##  2 Preliminaries

In this section, we introduce notation used in the paper as well as relevant
background. In Section 2.1, we introduce background on differential privacy.
In Section 2.2 we provide background on hypothesis testing (including standard
definitions of p-value, type-I error, uniform asymptotic level, power, etc.).
Finally, in Section 2.3 we state a result of Kusner et al. [21] used in our
paper on the residuals of kernel ridge regression

#### Notation.

If $(V_{P,n})_{n\in\mathbb{N},P\in\mathcal{P}}$ is a family of sequences of
random variables whose distributions are determined by $P\in\mathcal{P}$, we
say $V_{P,n}=o_{\mathcal{P}}(1)$ if for all $\delta>0$,
$\sup_{P\in\mathcal{P}}\Pr_{P}[|V_{P,n}|>\delta]\to 0$. Similarly,
$V_{P,n}=O_{\mathcal{P}}(1)$ if for all $\delta>0$, $\exists M>0$ such that
$\sup_{n\in\mathbb{N}}\sup_{P\in\mathcal{P}}\Pr_{P}[|V_{P,n}|>M]<\delta$.

###  2.1 Background on Differential Privacy

The notion of neighboring datasets is central to differential privacy. In this
work, we consider datasets $\mathbf{D}=(\mathbf{X},\mathbf{Y},\mathbf{Z})$ of
$n$ datapoints $\\{(x_{i},y_{i},z_{i})\\}_{i=1}^{n}$, drawn i.i.d. from a
joint distribution $P$ on some domain
$\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$. Let $\mathcal{D}$ denote the
universe of datasets. A dataset $\mathbf{D}^{\prime}\in\mathcal{D}$ is a
neighbor of $\mathbf{D}$ if it can be obtained from $\mathbf{D}$ by replacing
at most one datapoint $(x_{i},y_{i},z_{i})\in\mathbf{D}$ with an arbitrary
entry
$(x^{\prime}_{i},y^{\prime}_{i},z^{\prime}_{i})\in\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$,
for some $i\in[n]$. For the purposes of CRT, where we use the distributional
information about $X\mid Z$ to resample additional data, we define
$\mathbf{D}$ to include the new samples (see Section 4).

######  Definition 2.1 (Differential privacy [13]).

A randomized algorithm Alg is $\varepsilon$-DP if for all neighboring datasets
$\mathbf{D},\mathbf{D}^{\prime}$ and all events $\mathcal{R}$ in the output
space of Alg, it holds
$\Pr[\text{Alg}(\mathbf{D})\in\mathcal{R}]\leq\exp(\varepsilon)\cdot\Pr[\text{Alg}(\mathbf{D}^{\prime})\in\mathcal{R}],$
where the probability is over the randomness of the algorithm.

The Laplace mechanism is a widely used framework for obtaining DP algorithms
[13].

######  Definition 2.2 ($\ell_{1}$-sensitivity).

For a function $f\colon\mathcal{D}\to\mathbb{R}^{d}$, its
$\ell_{1}$-sensitivity $\Delta_{f}$ is defined as

$\Delta_{f}=\max_{\mathbf{D},\mathbf{D}^{\prime}\mathrm{neighbors}}\lVert
f(\mathbf{D})-f(\mathbf{D}^{\prime})\rVert_{1}.$

######  Lemma 2.3 (Laplace Mechanism [13]).

Let $\varepsilon>0$ and $f\colon\mathcal{D}\to\mathbb{R}^{d}$ be a function
with $\ell_{1}$-sensitivity $\Delta_{f}$. Let
$W\sim\mathrm{Lap}(0,\Delta_{f}/\varepsilon)$ be a noise vector from the
Laplace distribution with scale parameter $\Delta_{f}/\varepsilon$. The
Laplace Mechanism that, on input $\mathbf{D}$ and $\varepsilon$, outputs
$f(\mathbf{D})+W$ is $\varepsilon$-DP.

Differential privacy satisfies a post-processing property.

######  Lemma 2.4 (Post-Processing [13]).

If the algorithm $\mathcal{A}$ is $\varepsilon$-differentially private, and
$g$ is any randomized function, then the algorithm $g(\mathcal{A}(x))$ is
$\varepsilon$-differentially private.

###  2.2 Background on Hypothesis Testing

Let $\mathcal{P}$ be the class of the joint distributions for the random
variables $(X,Y,Z)$. We say $P\in\mathcal{P}$ is a null distribution if
$X\perp\\!\\!\\!\perp Y\mid Z$. The null-hypothesis, denoted
$\mathcal{P}_{0}$, is the class of null distributions,

#### Type-I error and validity.

Consider a (potentially) randomized test $\varphi_{n}$ that is run on $n$
samples from a distribution $P\in\mathcal{P}$ and outputs a binary decision:
$1$ for rejecting the null hypothesis and $0$ for accepting the null
hypothesis. The quantity $\Pr_{P}[\varphi_{n}=1]$, where $P$ is a null
distribution, refers to the type-I error of the test, i.e., the probability
that it erroneously rejects the (true) null hypothesis. Given level
$\alpha\in(0,1)$ and the null hypothesis $\mathcal{P}_{0}$, we say that the
test has _valid level at sample size $n$_ if the type-I error is bounded by
$\alpha$, i.e.,:

$\displaystyle\sup_{P\in\mathcal{P}_{0}}\Pr_{P}[\varphi_{n}=1]\leq\alpha.$

The sequence $\\{\varphi_{n}\\}_{n=1}^{\infty}$ has

uniformly asymptotic level
$\displaystyle\text{if}\quad\lim_{n\to\infty}\sup_{P\in\mathcal{P}_{0}}\Pr_{P}[\varphi_{n}=1]\leq\alpha,$
pointwise asymptotic level
$\displaystyle\text{if}\quad\sup_{P\in\mathcal{P}_{0}}\lim_{n\to\infty}\Pr_{P}[\varphi_{n}=1]\leq\alpha.$

Usually, we want at least uniformly asymptotic level to hold for a test.
Otherwise, for any sample size $n$, there can be some null distribution that
does not control type-I error at that sample size.

A hypothesis test is usually derived from a statistic $T_{n}$ (such as the GCM
statistic) calculated on $n$ samples drawn i.i.d from the distribution $P$ of
$(X,Y,Y)$. Having obtained a value $t$ for the statistic $T_{n}$, the two-
sided p-value is:

$\displaystyle\text{p-value}=\Pr_{P}[|T_{n}|\geq t].$

The hypothesis test $\varphi_{n}$ with desired validity level $\alpha$ can
then be defined as

$\displaystyle\varphi_{n}=\mathbf{1}[\text{p-value}\leq\alpha].$ (1)

Therefore, to obtain a test with the desired validity we need to compute the
p-value. The p-value is typically calculated using information about the
distribution of $T_{n}$. We say that $T_{n}$ converges uniformly over
$\mathcal{P}_{0}$ to the standard Gaussian distribution if:

$\displaystyle\lim_{n\to\infty}\sup_{P\in\mathcal{P}_{0}}\sup_{t\in\mathbb{R}}|\Pr_{P}[T_{n}\leq
t]-\Phi(t)|=0,$

where $\Phi$ is the CDF of the standard Gaussian. For the GCM statistic, we
are given that (under mild assumptions) $T_{n}$ converges uniformly over the
null hypothesis $\mathcal{P}_{0}$ to a standard Gaussian distribution [30].
Thus, if we set $\text{p-value}=2(1-\Phi(|t|)$ and define the hypothesis test
$\varphi_{n}$ as in (1), we obtain that $\varphi_{n}$ has uniformly asymptotic
level $\alpha$.

#### Power.

Once we have a test with uniformly asymptotic level, we would also like the
test to correctly accept the alternate hypothesis, when this hypothesis holds.
Let $\mathcal{Q}$ be the set of alternate distributions (for which
$X\cancel{\perp\\!\\!\\!\perp}Y\mid Z$). The power of a test is the
probability that it correctly rejects the null hypothesis, given that the
alternate hypothesis holds. A sequence $\\{\varphi_{n}\\}_{n=1}^{\infty}$ of
tests has

$\displaystyle\textit{uniformly asymptotic
power}\quad\text{if}\quad\lim_{n\to\infty}\inf_{P\in\mathcal{Q}}\Pr_{P}[\varphi_{n}=1]=1.$

###  2.3 Residuals of Kernel Ridge Regression

In our algorithms and experiments, we use kernel ridge regression (KRR) as a
procedure for regressing $\mathbf{X}$ and $\mathbf{Y}$ on $\mathbf{Z}$, and
rely on the following result by Kusner et al. [21] about the sensitivity of
the residuals of KRR.222One could also use other regression techniques within
our private GCM and private CRT frameworks, and theoretical guarantees
continue to hold if similar ($\approx O(1/n)$) bounds on the sensitivity of
the residuals are true.

######  Theorem 2.5 (Restated Theorem 5 of Kusner et al. [21]).

Let $(\mathbf{U},\mathbf{V})$ be a dataset of $n$ datapoints $(u_{i},v_{i})$,
$i\in[n]$ from the domain
$\mathcal{U}\times\mathcal{V}\subset\mathbb{R}\times\mathbb{R}^{d}$. Suppose
that $|\mathcal{U}|\leq 1$. Given a Hilbert space $\mathcal{H}$, let
$\mathbf{w}$ be the vector that minimizes the kernel ridge regression
objective

$(\lambda/2)\lVert\mathbf{w}\rVert^{2}_{\mathcal{H}}+(1/n)\sum_{i=1}^{n}(u_{i}-\mathbf{w}^{\top}\phi(v_{i}))^{2},$

for kernel $\phi\colon\mathbb{R}^{d}\to\mathcal{H}$ with
$\lVert\phi(v)\rVert_{\mathcal{H}}\leq 1$ for all $v\in\mathcal{V}$. Define
$\mathbf{w}^{\prime}$ analogously for a neighboring dataset
$(\mathbf{U}^{\prime},\mathbf{V}^{\prime})$ that is obtained by replacing one
datapoint in $(\mathbf{U},\mathbf{V})$. Then
$\lVert\mathbf{w}\rVert_{\mathcal{H}}\leq\sqrt{2/\lambda}$ and for all
$v\in\mathbf{V}$ it holds:

$|\mathbf{w}^{\top}\phi(v)-\mathbf{w}^{\prime\top}\phi(v)|\leq
8\sqrt{2}/(\lambda^{3/2}n)+8/(\lambda n).$

##  3 Private Generalized Covariance Measure

Here, we present our private Generalized Covariance Measure (GCM) test.
Missing proofs are in Appendix A.

#### GCM Test.

We first describe the non-private GCM test of Shah and Peters [30]. Given a
joint distribution $P$ of the random variables $(X,Y,Z)$, we can always write:

$\displaystyle X=f_{P}(Z)+\chi_{P},\quad Y=g_{P}(Z)+\xi_{P},$

where $f_{P}(z)=\mathbb{E}_{P}[X|Z=z]$, $g_{P}(z)=\mathbb{E}_{P}[Y|Z=z]$,
$\chi_{P}=X-f_{P}(z)$, and $\xi_{P}=Y-g_{P}(z)$.

Let $\mathbf{D}=(\mathbf{X},\mathbf{Y},\mathbf{Z})$ be a dataset of $n$ i.i.d.
samples from $P$. Let $\hat{f}$ and $\hat{g}$ be approximations to the
conditional expectations $f_{P}$ and $g_{P}$, obtained by fitting $\mathbf{X}$
to $\mathbf{Z}$ and $\mathbf{Y}$ to $\mathbf{Z}$, respectively. We consider
the products of the residuals from the fitting procedure:

$\displaystyle R_{i}=((x_{i}-\hat{f}(z_{i}))(y_{i}-\hat{g}(z_{i}))\text{ for
}i\in[n].$ (2)

The GCM test statistic $T$ is defined as the normalized mean of the residual
products, i.e.,

$\displaystyle{\small
T(R_{1},\dots,R_{n})=\frac{\frac{1}{\sqrt{n}}\sum_{i=1}^{n}R_{i}}{(\frac{1}{n}\sum_{i=1}^{n}R_{i}^{2}-(\frac{1}{n}\sum_{k=1}^{n}R_{k})^{2})^{1/2}}.}$
(3)

The normalization critically ensures that $T$ follows a standard normal
distribution asymptotically. However, it also leads to the unbounded
sensitivity of the statistic $T$.

#### Private GCM Test.

To construct a DP version of the GCM test, we focus on the vector of residual
products, $\mathbf{R}=(R_{1},\dots,R_{n})$. Let $\Delta$ denote the
$\ell_{1}$-sensitivity of $\mathbf{R}$. Given $\Delta$, we use the Laplace
mechanism (Lemma 2.3) to add scaled Laplace noise to $\mathbf{R}$ and then
compute $T$ on the noisy residual products. The private GCM test we present
(in Algorithm 1) can be used with any fitting procedure, as long as a bound on
the sensitivity of the residuals for that procedure is known.

Algorithm 1 Private Generalized Covariance Measure

1:Input: Dataset
$(\mathbf{X},\mathbf{Y},\mathbf{Z})=\\{(x_{i},y_{i},z_{i})\\}_{i=1}^{n}$,
privacy parameter $\varepsilon>0$, fitting procedure $\mathcal{F}$, bound
$\Delta>0$ on the sensitivity of residual products of $\mathcal{F}$.

2:Let $\hat{f}=\mathcal{F}(\mathbf{Z},\mathbf{X})$ and
$\hat{g}=\mathcal{F}(\mathbf{Z},\mathbf{Y})$

3:for $i=1,\dots,n$ do

4: $r_{X,i}\leftarrow x_{i}-\hat{f}(z_{i})$, $r_{Y,i}\leftarrow
y_{i}-\hat{g}(z_{i})$

5: $R_{i}\leftarrow r_{X,i}\cdot r_{Y,i}$

6: $W_{i}\sim\mathrm{Lap}(0,\Delta/\varepsilon)$

7:Let $T^{(n)}\leftarrow T(R_{1}+W_{1},\dots,R_{n}+W_{n})$ $\triangleright$
See (3)

8:Output p-value $=2\cdot(1-\Phi(|T^{(n)}|)$

While the algorithm uses a simple noise addition strategy to privatize the GCM
test, its asymptotic behavior is rather unexpected. Notice that the noise
added to the residuals has constant variance that does not vanish with
$n\to\infty$. Yet, we show (in Theorem 3.2) that $T^{(n)}$ converges to a
standard Gaussian distribution similarly to the non-private GCM statistic. The
key step in the analysis is to show that the error introduced by the noise
random variables grows at a slower rate than the error introduced by the
fitting procedure. Our algorithmic framework opens up a question of which
fitting procedures have residuals with constant bounded sensitivity. We show
such a result when Kernel Ridge Regression is used as the fitting method.

Next, we show theoretical guarantees on the type-I error control and power of
Algorithm 1 under mild assumptions on the fitting procedures $\hat{f}$ and
$\hat{g}$, listed in Definition 3.1.

######  Definition 3.1 (Good fit).

Consider $u_{P}(z)=\mathbb{E}_{P}[\chi_{P}^{2}\mid Z=z]$,
$v_{P}(z)=\mathbb{E}_{P}[\xi_{P}^{2}\mid Z=z]$, and the following error terms:

$\displaystyle A_{f}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}(f_{P}(z_{i})-\hat{f}(z_{i}))^{2},\quad\quad
B_{f}=\frac{1}{n}\sum_{i=1}^{n}(f_{P}(z_{i})-\hat{f}(z_{i}))^{2}v_{P}(z_{i}),$
$\displaystyle A_{g}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}(g_{P}(z_{i})-\hat{g}(z_{i}))^{2},\quad\quad
B_{g}=\frac{1}{n}\sum_{i=1}^{n}(g_{P}(z_{i})-\hat{g}(z_{i}))^{2}u_{P}(z_{i}).$
(4)

Let $\mathcal{P}$ be a class of distributions for $(X,Y,Z)$ that are
continuous with respect to the Lebesgue measure and such that
$\sup_{P\in\mathcal{P}}\mathbb{E}[|\chi_{P}\xi_{P}|^{2+\eta}]\leq c$ for some
constants $c,\eta>0$. We say the classifiers $\hat{f}$ and $\hat{g}$ are a
good fit for $\mathcal{P}$ if
$A_{f}A_{g}=o_{\mathcal{P}}(n^{-1}),B_{f}=o_{\mathcal{P}}(1)$, and
$B_{g}=o_{\mathcal{P}}(1)$.

The key part of Definition 3.1 is that the product of mean squared errors of
the fitting method (for fitting $X$ to $Z$ and $Y$ to $Z$) converge to zero at
a sublinear rate in the sample size. This is known as the “doubly robust”
assumption and is common in many analyses in theoretical ML [7]. It is a mild
assumption because it only requires one of two regressions, either fitting $X$
to $Z$ or fitting $Y$ to $Z$, to be sufficiently accurate. These assumptions
are in fact slightly weaker than those of Shah and Peters [30] for
guaranteeing uniformly asymptotic level333Given a level $\alpha\in(0,1)$ and
null hypothesis $\mathcal{P}_{0}$, a test $\psi_{n}$ has uniformly asymptotic
level if its asymptotic type-I error is bounded by $\alpha$ over all
distributions in $\mathcal{P}_{0}$, i.e.,
$\lim_{n\to\infty}\sup_{P\in\mathcal{P}_{0}}\Pr_{P}[\psi_{n}\mbox{ rejects
null}]\leq\alpha$. See Section 2.2. and power of the GCM, as we do not require
a lower bound on the variance $\mathbb{E}[\chi_{P}^{2}\xi_{P}^{2}]$ of the
true residuals. This requirement is no longer necessary as we add finite-
variance noise to the residual products.

#### Type-I Error Control.

We show that as with the GCM test of Shah and Peters [30], the private
counterpart has uniformly asymptotic level. While the original GCM test of
Shah and Peters [30] does not require the input variables to be bounded, we
assume bounded random variables $X$ and $Y$ to obtain bounds on the
sensitivity $\Delta$ of the residual products. For the rest of this section,
we assume publicly known bounds $a$ and $b$ on the domain $\mathcal{X}$ of $X$
and $\mathcal{Y}$ of $Y$, (i.e., $|x|\leq a,\forall x\in\mathcal{X}$ and
$|y|\leq b,\forall y\in\mathcal{Y}$).444 These bounds can also be replaced
with high probability bounds, but the privacy guarantees of our CI test would
be replaced with what is known as approximate differential privacy. Note that
we do not assume such bounds on the domain of $Z$, which is important as $Z$
could be high-dimensional.

######  Theorem 3.2.

_(Type-I Error Control of Private GCM)_ Let $a$ and $b$ be known bounds on the
domains of $X$ and $Y$, respectively. Given a dataset
$\mathbf{D}=(\mathbf{X},\mathbf{Y},\mathbf{Z})$, let
$(\hat{\mathbf{X}},\hat{\mathbf{Y}},\mathbf{Z})$ be the rescaled dataset
obtained by setting $\hat{\mathbf{X}}=\mathbf{X}/a$ and
$\hat{\mathbf{Y}}=\mathbf{Y}/b$. Consider $R_{i},i\in[n]$, as defined in (2),
for the rescaled dataset $(\hat{\mathbf{X}},\hat{\mathbf{Y}},\mathbf{Z})$. Let
$W_{i}\sim\mathrm{Lap}(0,\Delta/\varepsilon)$ for $i\in[n]$, where
$\Delta,\varepsilon>0$ are constants. Let $\mathcal{P}$ be the set of null
distributions from Definition 3.1 for which $\hat{f},\hat{g}$ are a good fit.
The statistic $T^{(n)}=T(R_{1}+W_{1},\dots,R_{n}+W_{n})$, defined in Algorithm
1, converges uniformly over $\mathcal{P}$ to the standard Gaussian
distribution $\mathcal{N}(0,1)$.

Since $T^{(n)}$ converges uniformly to a standard Gaussian distribution, this
implies that the CI test in Algorithm 1 has uniformly asymptotic level (see
Section 2.2). It also satisfies a weaker pointwise asymptotic level guarantee
that holds under slightly weaker assumptions (Theorem A.1). Note that this
result is independent of the bound on $|X|$ and $|Y|$. While the guarantee of
Theorem 3.2 is asymptotic, type-I error control “kicks in” at very small
sample sizes (like $n=100$) as confirmed by our experimental results. This
behavior is typical for many statistics that converge to a standard Gaussian
distribution. Recall that finite-sample guarantees are impossible even for
non-private CI testing, even under the assumptions of Definition 3.1, since
these assumptions are only asymptotic in nature.

#### Noise Addition Leads to Better Type-I Error Control.

A beneficial consequence of the privacy noise is that there are scenarios,
under the null hypothesis, where the non-private GCM fails to provide type-I
error control, but our private GCM does. If the functions $\hat{f}$ and
$\hat{g}$ fail to fit the data (i.e., the conditions on
$A_{f},A_{g},B_{f},B_{g}$ in Theorem 3.2 are violated), private GCM can still
provide type-I error control. We show in Section 5 one such scenario, when the
learned model underfits the data. Consider on the other hand the case when the
model overfits, and more extremely, when the model interpolates
asymptotically, i.e. $\hat{f}(z_{i})\to x_{i}$ and $\hat{g}(z_{i})\to y_{i}$
as $n\to\infty$ for all $i\in[n]$ [22]. It is not too hard to show that
convergence to the standard Gaussian still holds for the private GCM, and thus
type-I error control is provided. Instead, the rejection rate of the non-
private GCM converges to 1 when the model interpolates.

#### Power of the Private GCM.

Next, we show a result on the power of our private GCM test.

######  Theorem 3.3.

_(Power of Private GCM)._ Consider the setup of Theorem 3.2. Define the
“signal” ($\rho_{P}$) and “noise” ($\sigma_{P}$) of the true residuals
$\chi_{P},\xi_{P}$ as:

$\displaystyle\rho_{P}=\mathbb{E}_{P}[\mathrm{cov}(X,Y\mid
Z)],\quad\sigma_{P}=\sqrt{\mathrm{Var}_{P}(\chi_{P}\xi_{P})}.$

Let $\mathcal{P}$ be the set of alternate distributions from Definition 3.1
for which $\hat{f},\hat{g}$ are a good fit. Then

$\displaystyle
T^{(n)}-\frac{\sqrt{n}\rho_{P}}{\sigma_{P}^{\prime}},\quad\mbox{ where
}\sigma_{P}^{\prime}=\sqrt{\sigma_{P}^{2}+(\frac{\sqrt{2}ab\Delta}{\varepsilon})^{2}}$
(5)

converges uniformly over $\mathcal{P}$ to $\mathcal{N}(0,1)$.

#### Discussion on Power.

Theorem 3.3 implies that $T^{(n)}$ has uniform (asymptotic) power of $1$ if
$\rho_{P}\neq 0$. See Corollary A.5 for a short proof. In Theorem A.3, we also
show a pointwise (asymptotic) power guarantee, under weaker assumptions. We
remark that the bounds $a$ and $b$ on $|X|$ and $|Y|$ could depend on the
dataset size $n$. Algorithm 1 has uniform asymptotic power of $1$ as long as
$a\cdot b=o(\sqrt{n})$.

Shah and Peters [30] show a similar result on the power of the (non-private)
GCM, but with $\sigma_{P}^{\prime}=\sigma_{P}$. Suppose $\sigma_{P}=1$. Then,
Theorem 3.3 states that a $(\frac{ab\Delta}{\varepsilon})^{2}$-factor of the
dataset size used in the non-private case is required to obtain the same power
in the private case. A blow-up in the sample size is typical in DP analyses
[11].

#### Private GCM with Kernel Ridge Regression (PrivGCM).

To obtain a bound on the sensitivity of the vector of residual products, we
use kernel ridge regression (KRR) as the model for regressing $X$ on $Z$ and
$Y$ on $Z$, respectively. Let PrivGCM denote Algorithm 1 with KRR as the
fitting procedure and the bound on $\Delta$.

The vector of residual products has $\ell_{1}$-sensitivity $O_{\lambda}(1)$
(as formally shown in Lemma 3.4 using Theorem 2.5). Along with Lemma 2.3, this
implies that PrivGCM is $\varepsilon$-DP. In addition, as shown by Shah and
Peters [30], the requirements on $A_{f},A_{g},B_{f},B_{g}$ are satisfied when
using KRR. If the additional conditions listed in Definition 3.1 are also
satisfied, then PrivGCM has uniformly asymptotic level and uniform asymptotic
power of $1$ (see Corollary A.6).

######  Lemma 3.4.

_(Sensitivity of residual products)._ Let $\mathbf{R}$ be the vector of
residual products, as defined in (2), of fitting a KRR model of $\mathbf{X}$
to $\mathbf{Z}$ and $\mathbf{Y}$ to $\mathbf{Z}$ with regularization parameter
$\lambda>0$. If $|x_{i}|,|y_{i}|\leq 1$ for all $i\in[n]$, then
$\Delta_{\mathbf{R}}\leq C$ where
$C=4(1+\frac{\sqrt{2}}{\sqrt{\lambda}})(1+\frac{\sqrt{2}}{\sqrt{\lambda}}+\frac{4\sqrt{2}}{\lambda^{3/2}}+\frac{4}{\lambda})$.

##  4 Private Conditional Randomized Testing

Here, we propose a private version of the conditional randomization test
(CRT), which uses access to the distribution of $X\mid Z$ as a key assumption.
Recall that such an assumption is useful, for example, when one has access to
abundant unlabeled data $(X,Z)$. Missing proofs are in Appendix B.

#### CRT.

As before, consider a dataset $(\mathbf{X},\mathbf{Y},\mathbf{Z})$ of $n$
i.i.d. samples $(x_{i},y_{i},z_{i}),i\in[n]$ from the joint distribution $P$.
For ease of notation, denote the original $\mathbf{X}$ as $\mathbf{X}^{(0)}$.
The key idea of CRT is to sample $m$ copies of $\mathbf{X}^{(0)}$ from $X\mid
Z$, where $Z$ is fixed to the values in $\mathbf{Z}$. That is, for $j\in[m]$
and $i\in[n]$, a new datapoint $x_{i}^{(j)}$ is sampled from $X\mid Z=z_{i}$.
Then $\mathbf{X}^{(j)}=(x_{1}^{(j)},\dots,x_{n}^{(j)})$.

Under the null hypothesis, the triples
$(\mathbf{X}^{(0)},\mathbf{Y},\mathbf{Z}),\dots,(\mathbf{X}^{(m)},\mathbf{Y},\mathbf{Z})$
are identically distributed. Thus, for every statistic $T$ chosen
independently of the data, the random variables
$T(\mathbf{X}^{(0)},\mathbf{Y},\mathbf{Z}),\dots,T(\mathbf{X}^{(m)},\mathbf{Y},\mathbf{Z})$
are also identically distributed. Denote these random variables by
$T_{0},\dots,T_{m}$. The p-value is computed by ranking $T_{0}$, obtained by
using the original $\mathbf{X}^{(0)}$ vector, against $T_{1},\dots,T_{m}$,
obtained from the resamples:

$\displaystyle\textrm{p-value}=\frac{1+\sum_{j=1}^{m}\mathbf{1}(T_{j}\geq
T_{0})}{m+1}.$

For every choice of $T$, the p-value is uniformly distributed and finite-
sample type-I error control is guaranteed.

#### Private CRT.

Let
$\mathbf{D}=(\mathbf{X}^{(0)},\dots,\mathbf{X}^{(m)},\mathbf{Y},\mathbf{Z})$
denote the aggregated dataset. We say $\mathbf{D}^{\prime}$ is a neighbor of
$\mathbf{D}$ if they differ in at most one row. By defining $\mathbf{D}$ to
include the resamples $\mathbf{X}^{(1)},\dots,\mathbf{X}^{(m)}$, we also
protect the privacy of the data obtained in the resampling step.

Our private CRT test is shown in Algorithm 2: it obtains a private estimate of
the rank of $T_{0}$ amongst the statistics $T_{1},\dots,T_{m}$, sorted in
decreasing order. Using the Laplace mechanism to privately estimate the rank
is not a viable option, since the rank has high sensitivity: changing one
point in $\mathbf{D}$ could change all the values $T_{0},\dots,T_{m}$ and
change the rank of $T_{0}$ by $O(m)$. Another straightforward approach is to
employ the widely used Sparse Vector Technique [12, 11] to privately answer
questions ”Is $T_{i}>T_{0}$?” for all $i\in[m]$. However, this algorithm pays
a privacy price for each $T_{i}$ that is above the “threshold” $T_{0}$, which
under the null is $\Omega(m)$, thus resulting in lower utility of the
algorithm. Instead, we define a new score function and algorithm which
circumvents this problem by intuitively only incurring a cost for the queries
$T_{i}$ that are very close to $T_{0}$ in value.

Our key algorithmic idea is to define an appropriate score function of bounded
sensitivity. It assigns a score to each rank $c\in[0,m]$ that indicates how
well $c$ approximates the true rank of $T_{0}$. The score of a rank $c$ equals
the negative absolute difference between $T_{0}$ and the statistic at rank
$c$. The true rank of $T_{0}$ has the highest score (equal to $0$), whereas
all other ranks have negative scores. We show that this score function has
bounded sensitivity for statistics $T$ of bounded sensitivity. The rank with
the highest score is privately selected using Report Noisy Max, a popular DP
selection algorithm [11]. To obtain good utility, the design of the score
function exploits the fact that for CRTs, the values $T_{i}$ are distributed
in a very controlled fashion, as explained in the remark following Theorem
4.7.

Algorithm 2 Private Conditional Randomization Test

1:Input: Dataset $(\mathbf{X}^{(0)},\mathbf{Y},\mathbf{Z})$, privacy parameter
$\varepsilon$, bound $\Delta_{T}$ on the sensitivity of $T$, number of
resamples $m$.

2:$T_{0}\leftarrow T(\mathbf{X}^{(0)},\mathbf{Y},\mathbf{Z})$,
$s_{0}\leftarrow 0$.

3:for $i=1,\dots,m$ do

4: Sample $\mathbf{X}^{(i)}\mid\mathbf{Z}$ from $X\mid Z$ .

5: $T_{i}\leftarrow T(\mathbf{X}^{(i)},\mathbf{Y},\mathbf{Z})$.

6:Let $Q_{0},\dots,Q_{m}$ denote the values $\\{T_{i}\\}_{i\in[0,m]}$ sorted
in decreasing order.

7:for $i=0,1\dots,m$ do

8: $s_{i}\leftarrow-\frac{|Q_{i}-T_{0}|}{2\Delta_{T}}$.

9:$\hat{c}\leftarrow\mathtt{ReportNoisyMax}(\\{s_{i}\\}_{i\in[0,m]},\varepsilon)$.
$\triangleright$ Theorem 4.1

10:Output p-value $\hat{p}=\frac{1+\hat{c}}{m+1}$.

######  Theorem 4.1 (Report Noisy Max [11, 24, 10]).

Let $\varepsilon>0$. Given scores $s_{i}\in\mathbb{R}$, $i\in[B]$ evaluated
from a score function of sensitivity at most $1$, the algorithm
$\mathtt{ReportNoisyMax}$ samples
$Z_{1},\dots,Z_{B}\sim\mathrm{Exp}(2/\varepsilon)$ and returns
$\hat{\imath}=\operatorname*{arg\,max}_{i\in[B]}(s_{i}+Z_{i})$. This algorithm
is $\varepsilon$-DP and for $\delta\in(0,1)$, with probability at least
$1-\delta$, it holds $s_{\hat{\imath}}\geq
s^{*}-2\log(B/\delta)\varepsilon^{-1}$, where $s^{*}=\max_{i\in[B]}s_{i}$.

We describe our score function in Definition 4.2 and bound its sensitivity in
Lemma 4.3. The bound on the sensitivity of the score function is obtained by
assuming a bound $\Delta_{T}$ on the sensitivity of the statistic $T$.

######  Definition 4.2 (Score function for rank of query).

Let $\\{T_{i}\\}_{i\in[0,m]}$ be $m+1$ queries of sensitivity at most
$\Delta_{T}$ on a dataset $\mathbf{D}$. Let $Q_{0},\dots,Q_{m}$ denote the
values $\\{T_{i}\\}_{i\in[0,m]}$ sorted in decreasing order. Let $k\in[0,m]$
be the index of the query whose rank we wish to know. Then for all
$c\in[0,m]$, define

$\displaystyle s_{k}(c,\mathbf{D})=-\frac{|Q_{c}-T_{k}|}{2\Delta_{T}}.$

######  Lemma 4.3.

_(Sensitivity of the score function)._ Let $\\{T_{i}\\}_{i\in[0,m]}$ be the
values of $m+1$ queries of sensitivity at most $\Delta_{T}$ on a dataset
$\mathbf{D}$. Let $\\{T_{i}^{\prime}\\}_{i\in[B]}$ be the values of the same
queries on a neighboring dataset $\mathbf{D}^{\prime}$. Let
$Q_{0},\dots,Q_{m}$ (respectively $Q_{0}^{\prime},\dots,Q_{m}^{\prime}$)
denote the values $\\{T_{i}\\}_{i\in[0,m]}$ (respectively
$\\{T_{i}^{\prime}\\}_{i\in[0,m]}$ ) sorted in decreasing order. Then
$|Q_{c}-Q_{c}^{\prime}|\leq\Delta_{T}$ for all $c\in[0,m]$. As a result, the
score function $s_{k}(c,\mathbf{D})$ has sensitivity at most 1 for all
$c\in[0,m]$.

#### Statistic $T$ and its Sensitivity.

The statistic $T$ that we use to obtain our private CRT test is defined as the
numerator of the GCM statistic. The residuals of $\mathbf{Y}$ with respect to
$\mathbf{Z}$ are calculated by fitting a KRR model of $\mathbf{Y}$ to
$\mathbf{Z}$. Denote such residuals $r_{Y,i}$, for $i\in[n]$. The residuals of
$\mathbf{X}$ with respect to $\mathbf{Z}$ are exact, since we have access to
the distribution $X\mid Z$. Denote such residuals $r_{X,i}$ for $i\in[n]$. The
residual products are calculated as $R_{i}=r_{X,i}r_{Y,i}$ for $i\in[n]$.

######  Definition 4.4 (Statistic $T$ for the private CRT).

Given a dataset $(\mathbf{X},\mathbf{Y},\mathbf{Z})$ of $n$ points, let
$(R_{1},\dots,R_{n})$ be the vector of residual products of the exact
residuals of $\mathbf{X}$ with respect to $\mathbf{Z}$ and the residuals of
fitting a kernel ridge regression model of $\mathbf{Y}$ to $\mathbf{Z}$.
Define $T(\mathbf{X},\mathbf{Y},\mathbf{Z})=\sum_{i=1}^{n}R_{i}$.

We obtain a bound of $O_{\lambda}(1)$ on the $\ell_{1}$-sensitivity of the
statistic $T$ by bounding the sensitivity of the $R_{i}$. To bound the
sensitivity of the $r_{Y,i}$ we assume that the domain of the variable $Y$ is
bounded and use the result of Theorem 2.5. We assume a known bound on the
magnitude of the residuals $r_{X,i}$, motivated by the fact that we have
access to the distribution $X\mid Z$. This differs from the assumptions for
our PrivGCM test, where we assumed bounds on both $X$ and $Y$. Assuming a
bound on the residuals $r_{X,i}$ gives a tighter sensitivity bound for $T$.

######  Lemma 4.5.

_(Sensitivity of $T$)._ Consider two neighboring datasets
$\mathbf{D}=(\mathbf{X}^{(0)},\dots,\mathbf{X}^{(m)},\mathbf{Y},\mathbf{Z})$
and
$\mathbf{D}^{\prime}=(\mathbf{X}^{\prime(0)},\dots,\mathbf{X}^{\prime(m)},\mathbf{Y}^{\prime},\mathbf{Z}^{\prime})$.
For $j\in[0,m]$, let $T_{j}=T(\mathbf{X}^{(j)},\mathbf{Y},\mathbf{Z})$. Define
$T_{j}^{\prime}$ analogously. If $|y_{i}|,|y^{\prime}_{i}|\leq 1$ for all
$i\in[n]$ and $|r_{X,i}^{(j)}|,|{r^{\prime}}_{X,i}^{(j)}|\leq 1$ for all
$i\in[n],j\in[0,m]$,555The bound of $1$ can be replaced by any constant. then
$|T_{j}-T_{j}^{\prime}|\leq C^{\prime}$, where
$C^{\prime}=4\cdot(1+\frac{\sqrt{2}}{\sqrt{\lambda}}+\frac{2\sqrt{2}}{\lambda^{3/2}}+\frac{2}{\lambda})$.

#### Accuracy of the Private CRT.

We define the accuracy of Algorithm 2 in terms of the difference between the
private p-value it outputs and its non-private counterpart.

######  Definition 4.6 ($(\gamma,\delta)$-accuracy).

Let $G_{\gamma}=|\\{i\in[m]\mid|T_{i}-T_{0}|\leq\gamma\\}|$. Let $c^{*}$ be
the rank of $T_{0}$ given statistics $T_{i},i\in[0,m]$, and
$p^{*}=(1+c^{*})/(m+1)$ be the non-private p-value. We say Algorithm 2 is
$(\gamma,\delta)$-accurate if with probability at least $1-\delta$ it holds
$|\hat{p}-p^{*}|\leq\frac{G_{\gamma}}{m+1}$.

Define PrivCRT as Algorithm 2 where $T$ is the statistic from Definition 4.4
and $\Delta_{T}$, the bound on the sensitivity of the statistic $T$, is as
given in Lemma 4.5.

######  Theorem 4.7.

_PrivCRT_ is $\varepsilon$-DP and $(\gamma,\delta)$-accurate for
$\gamma=\frac{4\Delta_{T}}{\varepsilon}\log\Big{(}\frac{m}{\delta}\Big{)}.$

Remark on the Accuracy. While the guarantees from the above theorem does not
translate into a meaningful type-I error control bound, empirically, we
observe that, under the null, the p-values output by PrivCRT are uniformly
distributed (Fig. 10, Appendix C), and thus the test provides type-I error
control. Under the alternate, $T_{0}$ is much larger (or smaller) than all the
other values $T_{i},i\geq 1$ and thus $G_{\gamma}$ is small. However, the
power of PrivCRT can be affected if we increase $m$, as this can increase the
value of $G_{\gamma}$ (see Fig. 9, Appendix C). An interesting open question
is whether the dependence on $m$ in the accuracy of a private CRT is
avoidable. For now, we recommend using $m=O(1/\alpha)$ for rejection level
$\alpha$.

##  5 Empirical Evaluation

We evaluate our algorithms on a real-world dataset and synthetic data. We
start with the latter as it has the advantage that we know the ground-truth of
whether $X\perp\\!\\!\\!\perp Y\mid Z$.

#### Setup.

To generate synthetic data, we use a setup similar to that of Shah and Peters
[30] proposed for evaluating the performance of GCM. Fix an RKHS $\mathcal{H}$
that corresponds to a Gaussian kernel. The function
$f_{s}(z)=\exp(-s^{2}/2)\sin(sz)$ satisfies $f_{s}\in\mathcal{H}$.
$Z=(Z_{1},\dots,Z_{d})$ is a $d$-dimensional variable, where $d\in\\{1,5\\}$.
The distribution of $(X,Y,Z)$ is as follows:

$\displaystyle Z_{1},\dots,Z_{d}\sim N_{Z},\quad X=f_{s}(Z_{1})+N_{X},\quad
Y=-f_{s}(Z_{1})+N_{Y}+\beta\cdot N_{X},$

where $N_{Z}\sim\mathcal{N}(0,4)$,
$N_{X}\sim\mathcal{N}(0,1),N_{Y}\sim\mathcal{N}(0,1)$, and $\beta\geq 0$ is a
constant controlling the strength of dependence between $X$ and $Y$. If
$\beta=0$, then $X\perp\\!\\!\\!\perp Y\mid Z$, but not otherwise. For
experiments with PrivGCM, the dataset $(\mathbf{X},\mathbf{Y},\mathbf{Z})$
consists of $n$ points sampled as above. For experiments with PrivCRT, we
additionally sample $m$ copies $\mathbf{X}^{(j)}$, $j\in[m]$, by fixing
$\mathbf{Z}$. We study how varying $\beta$, $s$, and $n$ affects the rejection
rate of our tests (averaged over 500 resampled datasets). Shaded error bars
represent 95% confidence intervals. We set type-I error level $\alpha=0.05$.

We rescale $X$ and $Y$ so that all datapoints $x_{i}$ and $y_{i}$ satisfy
$|x_{i}|\leq 1,|y_{i}|\leq 1$ (recall that we assume known bounds for the
data; for this simulation, standard Gaussian concentration implies
$\max_{i\leq n}X_{i}\leq\sqrt{2\log n}$ with very high probability, so
choosing $\sqrt{C\log n}$ suffices here for a sufficiently large constant
$C$). We then fit a KRR model with a Gaussian kernel of $\mathbf{X}$ to
$\mathbf{Z}$ and $\mathbf{Y}$ to $\mathbf{Z}$. The best model is chosen via
5-fold cross-validation and grid search over the regularization parameter
$\lambda$ and the parameter of the Gaussian kernel.666Hyper-parameters are
optimized non-privately, as is common in the literature on privately training
ML models. Our algorithm can be combined in a black box fashion with methods
for performing private hyper-parameter search such as [23]. The choice of
$\lambda$ requires balancing the performance of the fitting step of the
algorithm with the magnitude of noise added (see Lemma 3.4), and thus some
lower bound on $\lambda$ is needed. We enforce $\lambda\geq 10$ and find that
this does not hurt performance of the fitting step even for large $n$. See
Fig. 8 (Appendix C) for an example.

#### Comparison to the Private Kendall CI test [37] and Test-of-Tests [18].

We start with a comparison to two other private CI tests in the literature.
The first is the private Kendall’s CI test, proposed by Wang et al. [37] for
categorical variables. The second, which we call PrivToT, is obtained from the
Test-of-Tests framework of Kazan et al. [18] and uses the non-private GCM as a
black-box. See Appendix C for details on the implementations of these two
tests.

Figure 1: Type-I error control of PrivToT, private Kendall, PrivGCM, and
PrivCRT (under the null): the first two fail to control Type-I error.

In Fig. 1, we compare the performance of these two tests with our private
tests under the null hypothesis. We vary $s$, the model complexity from $1$ to
$32$, and use a sample size $n=10^{4}$ and privacy parameter $\varepsilon=2$.
The larger $s$, the harder it is to learn the function $f_{s}$. As the model
complexity increases, the private Kendall test and PrivToT cannot control
type-I error, even with a large sample size ($n=10^{4}$). They perform even
worse when $Z$ is $5$-dimensional. On the other hand, both PrivGCM and PrivCRT
have consistent type-I error control across model complexity and
dimensionality of $Z$. This experiment motivates the need for tests with
rigorous theoretical type-I error guarantees, as we derive.777Note that for
tests without the desired type-I error control, statements about power are
vacuous.

Next, we compare our private CI tests with their non-private counterparts. We
fix $s=2$ for $f_{s}$.

Figure 2: Comparison of the power of private and nonprivate GCM tests as the
dependence strength $\beta$ increases. At $d=5$, the (nonprivate) GCM fails to
provide type-I error control when $\beta=0$.

Figure 3: Comparison of the type-I error and power of private and nonprivate
GCM tests as the dataset size $n$ increases. Again, at $d=5$ with $\beta=0$,
the (nonprivate) GCM fails to provide type-I error control even at large $n$
(in fact, its type-I error gets worse with $n$).

Figure 4: Comparing power of private and nonprivate CRT tests as we increase
dependence $\beta$.

Figure 5: Comparison of the type-I error and power of private and nonprivate
CRT tests as we increase the dataset size $n$.

#### Performance of PrivGCM.

In Fig. 3, we vary $\beta$, the strength of the dependence between $X$ and $Y$
from $0$ to $1.5$ and compare the rejection rate of PrivGCM with the (non-
private) GCM. We set $n=10^{4}$ and privacy parameter $\varepsilon=7$. In the
one-dimensional case, i.e., when $d=1$, the rejection rate of both tests goes
from $0.05$ to $1$, with the rejection rate of GCM converging faster to 1 than
for PrivGCM, as a consequence of the noise added for privacy. Crucially
though, when $d=5$, the privacy noise helps PrivGCM provide the critical
type-I error control at $\beta=0$, which non-private GCM fails at. In Fig. 3,
we examine the performance of PrivGCM on synthetic data.

The failure of (non-private) GCM to provide type-I error control is better
examined in Fig. 3, where we vary the dataset size $n$ from $10^{2}$ to
$10^{4}$, and plot the rejection rate of PrivGCM and GCM for $\beta=0$ and
$\beta>0$. When $d=5$, the privacy noise helps PrivGCM provide the critical
type-I error control at $\beta=0$, which non-private GCM fails at. At $d=5$,
the KRR model fails to fit the data (it returns a predicted function that is
nearly-zero). In this case, for $\beta=0$, the GCM statistic converges to a
Gaussian of standard deviation 1, but whose mean is removed from zero. The
larger $n$, the further the mean of the Gaussian is from zero, and the worse
the type-I error. The noise added for privacy brings the mean closer to zero
since the standard deviation of the noisy residuals, $\sigma_{P}^{\prime}$, is
much larger than $\sigma_{P}$ (see (5)). For $\beta>0$, PrivGCM needs a higher
dataset size to achieve the same power as GCM, concordant with our discussion
following Theorem 3.3. As $n\to\infty$, the power of PrivGCM is expected to
approach $1$.

#### Performance of PrivCRT.

We study the performance of PrivCRT in Figs. 5-5. PrivCRT achieves better
power than PrivGCM for our setup, so we use a smaller privacy parameter of
$\varepsilon=2$ and set $m=19$ (an extreme, but valid choice). In Fig. 5, we
vary $\beta$, the dependence strength between $X$ and $Y$, from $0$ to $1.5$,
using $n=10^{3}$. Both non-private CRT and PrivCRT provide type-I error
control. Also, the power of both PrivCRT and (non-private) CRT converges to
$1$, with a faster convergence for the non-private test. In Fig. 5, we vary
the dataset size $n$ and $\beta\in\\{0,0.5,1.5\\}$.

#### PrivCRT vs. PrivGCM.

In Fig. 6 we compare the performance of PrivCRT with PrivGCM for different
privacy parameters $\varepsilon\in[2^{-3},2^{3}]$. We set $n=10^{4}$ and, for
PrivCRT, $m=19$. Both tests control type-I error, but PrivCRT achieves better
power than PrivGCM for all privacy parameters $\varepsilon$. Therefore,
PrivCRT appears preferable to PrivGCM when dataholders have access to the
distribution $X\mid Z$. This result is consistent with the non-private
scenario where the CRT has higher power because it does not have to learn
$\mathbb{E}[X\mid Z]$.

Figure 6: Power of PrivCRT and PrivGCM versus privacy $\varepsilon$.

#### Real Data Experiments.

We now demonstrate the performance of our private tests on real-world data.
For these experiments, we use the “Concrete Compressive Strength” dataset that
consists of $1030$ datapoints and $9$ continuous features [40]. We set $Y$ to
be the outcome feature: the concrete compressive strength. The choice of the
$X$ variable is varied, and $Z$ consists of the $7$ remaining features. $Y$ is
assumed to be a complex non-linear function of the other $8$ features, thus we
expect the CI tests to reject. We focus on the private GCM because among our
two algorithms, as it is the more generally applicable one, i.e., it does not
require access to the conditional distribution. In Fig. 7, we evaluate the
power of the PrivGCM. As desired, the power of PrivGCM tends to $1$ as $n$
increases approaching the power of the the non-private case.

Figure 7: Power of the non-private GCM and PrivGCM on the “Concrete
Compressive Strength” dataset. The power of PrivGCM tends to $1$ with
increasing sample size.

##  6 Concluding Remarks

This work studies the fundamental statistical task of conditional independence
testing under privacy constraints. We design the first DP conditional
independence tests that support the general case of continuous variables and
have strong theoretical guarantees on both statistical validity and power. Our
experiments support our theoretical results and additionally demonstrate that
our private tests have more robust type-I error control than their non-private
counterparts.

We envision two straightforward generalizations of our private GCM test.
First, our test can be generalized to handle multivariate $X$ and $Y$,
following Shah and Peters [30], who obtain the test statistic from the
residual products of fitting each variable in $X$ and each variable in $Y$ to
$Z$. A natural extension would be to compute the same statistic on our noisy
residual products. Secondly, following Scheidegger et al. [29], a private
version of the weighted GCM would allow the test to achieve power against a
wider class of alternatives than the unweighted version. Finally, constructing
private versions of other model-X based tests, such as the Conditional
Permutation Test [3], could be another interesting direction.

### Acknowledgements

We would like to thank Patrick Blöbaum for helpful initial discussions
surrounding this project.

## References

  * Awan and Slavkovic [2018] Jordan Awan and Aleksandra B. Slavkovic.  Differentially private uniformly most powerful tests for binomial data.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 4212–4222, 2018.
  * Barrientos et al. [2017] Andrés F. Barrientos, Jerome P. Reiter, Ashwin Machanavajjhala, and Yan Chen.  Differentially private significance tests for regression coefficients.  _Journal of Computational and Graphical Statistics_ , 28:440 – 453, 2017.
  * Berrett et al. [2019] Thomas B. Berrett, Yi Wang, Rina Foygel Barber, and Richard J. Samworth.  The conditional permutation test for independence while controlling for confounders.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 82, 2019.
  * Brenner and Nissim [2014] Hai Brenner and Kobbi Nissim.  Impossibility of differentially private universally optimal mechanisms.  _SIAM Journal on Computing (SICOMP)_ , 43(5):1513–1540, 2014.
  * Campbell et al. [2018] Zachary Campbell, Andrew Bray, Anna M. Ritz, and Adam Groce.  Differentially private ANOVA testing.  In _International Conference on Data Intelligence and Security_ , pages 281–285, 2018.
  * Candès et al. [2016] Emmanuel J. Candès, Yingying Fan, Lucas Janson, and Jinchi Lv.  Panning for gold: ‘model‐X’ knockoffs for high dimensional controlled variable selection.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 80, 2016.
  * Chernozhukov et al. [2018] Victor Chernozhukov, Denis Chetverikov, Mert Demirer, Esther Duflo, Christian Hansen, Whitney Newey, and James Robins.  Double/debiased machine learning for treatment and structural parameters.  _The Econometrics Journal_ , 21:C1–C68, 2018.
  * Couch et al. [2019] Simon Couch, Zeki Kazan, Kaiyan Shi, Andrew Bray, and Adam Groce.  Differentially private nonparametric hypothesis testing.  In _Proceedings of the ACM Conference on Computer and Communications Security, CCS_ , pages 737–751, 2019.
  * Dawid [1979] A Philip Dawid.  Conditional independence in statistical theory.  _Journal of the Royal Statistical Society: Series B (Methodological)_ , 41(1):1–15, 1979.
  * Ding et al. [2021] Zeyu Ding, Daniel Kifer, Sayed M. Saghaian N. E., Thomas Steinke, Yuxin Wang, Yingtai Xiao, and Danfeng Zhang.  The Permute-and-Flip mechanism is identical to Report-Noisy-Max with exponential noise.  _arXiv 2105.07260_ , 2021.
  * Dwork and Roth [2014] Cynthia Dwork and Aaron Roth.  The algorithmic foundations of differential privacy.  _Found. Trends Theor. Comput. Sci._ , 9(3-4):211–407, 2014.
  * Dwork et al. [2009] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil P. Vadhan.  On the complexity of differentially private data release: efficient algorithms and hardness results.  In _Proceedings, ACM Symposium on Theory of Computing (STOC)_ , pages 381–390, 2009.
  * Dwork et al. [2016] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith.  Calibrating noise to sensitivity in private data analysis.  _Journal of Privacy and Confidentiality_ , 7(3):17–51, 2016.
  * Fienberg et al. [2010] Stephen E. Fienberg, Alessandro Rinaldo, and Xiaolin Yang.  Differential privacy and the risk-utility tradeoff for multi-dimensional contingency tables.  In _Privacy in Statistical Databases_ , volume 6344 of _Lecture Notes in Computer Science_ , pages 187–199. Springer, 2010.
  * Fukumizu et al. [2007] Kenji Fukumizu, Arthur Gretton, Xiaohai Sun, and Bernhard Schölkopf.  Kernel measures of conditional dependence.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 20, 2007.
  * Gaboardi et al. [2016] Marco Gaboardi, Hyun-Woo Lim, Ryan M. Rogers, and Salil P. Vadhan.  Differentially private Chi-Squared hypothesis testing: Goodness of fit and independence testing.  In _Proceedings, International Conference on Machine Learning (ICML)_ , volume 48, 2016.
  * Johnson and Shmatikov [2013] Aaron Johnson and Vitaly Shmatikov.  Privacy-preserving data exploration in genome-wide association studies.  In _ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pages 1079–1087, 2013.
  * Kazan et al. [2023] Zeki Kazan, Kaiyan Shi, Adam Groce, and Andrew P. Bray.  The test of tests: A framework for differentially private hypothesis testing.  In _Proceedings, International Conference on Machine Learning (ICML)_ , volume 202, pages 16131–16151, 2023.
  * Kim and Schrab [2023] Ilmun Kim and Antonin Schrab.  Differentially private permutation tests: Applications to kernel methods.  _CoRR_ , abs/2310.19043, 2023.  doi: 10.48550/ARXIV.2310.19043.  URL https://doi.org/10.48550/arXiv.2310.19043.
  * Koller and Friedman [2009] Daphne Koller and Nir Friedman.  _Probabilistic graphical models: principles and techniques_.  MIT Press, 2009.
  * Kusner et al. [2016] Matt J. Kusner, Yu Sun, Karthik Sridharan, and Kilian Q. Weinberger.  Private causal inference.  In _Proceedings, International Conference on Artificial Intelligence and Statistics (AISTATS)_ , volume 51, pages 1308–1317, 2016.
  * Liang and Rakhlin [2020] Tengyuan Liang and Alexander Rakhlin.  Just interpolate: Kernel “ridgeless” regression can generalize.  _The Annals of Statistics_ , 48(3):1329 – 1347, 2020.
  * Liu and Talwar [2019] Jingcheng Liu and Kunal Talwar.  Private selection from private candidates.  In _Proceedings, ACM Symposium on Theory of Computing (STOC)_ , pages 298–309. ACM, 2019.
  * McKenna and Sheldon [2020] Ryan McKenna and Daniel Sheldon.  Permute-and-flip: A new mechanism for differentially private selection.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2020.
  * Nissim et al. [2007] Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith.  Smooth sensitivity and sampling in private data analysis.  In _Proceedings, ACM Symposium on Theory of Computing (STOC)_ , pages 75–84. ACM, 2007.
  * Pearl [2000] Judea Pearl.  Models, reasoning and inference.  _Cambridge, UK: Cambridge University Press_ , 19(2), 2000\.
  * Peña and Barrientos [2022] Víctor Peña and Andrés F. Barrientos.  Differentially private hypothesis testing with the subsampled and aggregated randomized response mechanism.  _Statistica Sinica_ , 2022.
  * Rogers and Kifer [2017] Ryan Rogers and Daniel Kifer.  A new class of private chi-square hypothesis tests.  In _Proceedings, International Conference on Artificial Intelligence and Statistics (AISTATS)_ , volume 54, pages 991–1000, 2017.
  * Scheidegger et al. [2022] Cyrill Scheidegger, Julia Hörrmann, and Peter Bühlmann.  The weighted generalised covariance measure.  _Journal of Machine Learning Research_ , 23(273):1–68, 2022.
  * Shah and Peters [2020] Rajen D. Shah and Jonas Peters.  The hardness of conditional independence testing and the generalised covariance measure.  _The Annals of Statistics_ , 48(3), 2020.
  * Smith [2011] Adam Smith.  Privacy-preserving statistical estimation with optimal convergence rates.  In _Proceedings, ACM Symposium on Theory of Computing (STOC)_ , pages 813–822, 2011.
  * Strobl et al. [2019] Eric V Strobl, Kun Zhang, and Shyam Visweswaran.  Approximate kernel-based conditional independence tests for fast non-parametric causal discovery.  _Journal of Causal Inference_ , 7(1), 2019.
  * Swanberg et al. [2019] Marika Swanberg, Ira Globus-Harris, Iris Griffith, Anna M. Ritz, Adam Groce, and Andrew Bray.  Improved differentially private analysis of variance.  _Proc. Priv. Enhancing Technol._ , 2019(3):310–330, 2019.
  * Uhler et al. [2013] Caroline Uhler, Aleksandra B. Slavkovic, and Stephen E. Fienberg.  Privacy-preserving data sharing for genome-wide association studies.  _J. Priv. Confidentiality_ , 5(1), 2013.
  * Vepakomma et al. [2022] Praneeth Vepakomma, Mohammad Mohammadi Amiri, Clément L. Canonne, Ramesh Raskar, and Alex Pentland.  Private independence testing across two parties.  _CoRR_ , abs/2207.03652, 2022.
  * Vu and Slavkovic [2009] Duy Vu and Aleksandra B. Slavkovic.  Differential privacy for clinical trial data: Preliminary evaluations.  In _ICDM Workshops_ , pages 138–143, 2009.
  * Wang et al. [2020] Lun Wang, Qi Pang, and Dawn Song.  Towards practical differentially private causal graph discovery.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2020.
  * Wang et al. [2015] Yue Wang, Jaewoo Lee, and Daniel Kifer.  Revisiting differentially private hypothesis tests for categorical data.  _arXiv 1511.03376_ , 2015.
  * Wang et al. [2018] Yue Wang, Daniel Kifer, Jaewoo Lee, and Vishesh Karwa.  Statistical approximating distributions under differential privacy.  _J. Priv. Confidentiality_ , 8(1), 2018.
  * Yeh [2007] I-Cheng Yeh.  Concrete Compressive Strength.  UCI Machine Learning Repository, 2007.  DOI: https://doi.org/10.24432/C5PK67.
  * Yu et al. [2014] Fei Yu, Stephen E. Fienberg, Aleksandra B. Slavkovic, and Caroline Uhler.  Scalable privacy-preserving data sharing methodology for genome-wide association studies.  _J. Biomed. Informatics_ , 50:133–141, 2014.
  * Zhang et al. [2011] Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf.  Kernel-based conditional independence test and application in causal discovery.  In _Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI)_ , pages 804–813, 2011.

##  Appendix A Proofs of Section 3

###  A.1 Proof of Theorem 3.2

In this section, we state and prove a longer version of Theorem 3.2. Item 1 of
Theorem A.1 gives the pointwise asymptotic level guarantee of the private GCM,
whereas Item 2 shows the more desirable uniform asymptotic level guarantee
under a slightly stronger condition. Item 2 corresponds exactly to Theorem
3.2.888The assumptions in Item 2, Theorem A.1 are identical to those of
Definition 3.1. The assumptions in Item 1 of Theorem A.1 are slightly weaker
than those of Definition 3.1. See Section 2.2 for definitions of pointwise
asymptotic level and uniformly asymptotic level.

From a privacy perspective, the proof of Item 2 is more involved. While Shah
and Peters [30] consider the asymptotic behavior of variables
$\chi_{i}\xi_{i}$ (the product of the true residuals), we instead study the
behavior of $\chi_{i}\xi_{i}W_{i}$ (the product of the true residuals with the
noise random variables). Similarly, while they study the product of error
terms of the fitting method,
$(f(z_{i})-\hat{f}(z_{i}))(g(z_{i})-\hat{g}(z_{i}))$, we instead need to
consider $(f(z_{i})-\hat{f}(z_{i}))(g(z_{i})-\hat{g}(z_{i}))W_{i}$, the
product of error terms with the noise variables. A key step in the proof is to
show that the noise variables grow at a slower rate than the rate of decay of
the error terms, with increasing sample size $n$.

Let $\mathcal{E}_{0}$ be the set of distributions for $(X,Y,Z)$ that are
absolutely continuous with respect to the Lebesgue measure. The null
hypothesis, $\mathcal{P}_{0}\subset\mathcal{E}_{0}$, is the subset of
distributions for which $X\perp\\!\\!\\!\perp Y\mid Z$. Given
$P\in\mathcal{P}$, let $P^{\prime}$ be the joint distribution of variables
$(X,Y,Z,W)$ where $W\sim\mathrm{Lap}(\Delta/\varepsilon)$ is independent of
$(X,Y,Z)$. For a set of distributions $\mathcal{P}$, let
$\mathcal{P}^{\prime}$ denote the set of distributions $P^{\prime}$ for all
$P\in\mathcal{P}$. Denote by $\Phi$ the CDF of the standard normal
distribution.

######  Theorem A.1.

_(Type-I Error Control of Private GCM)_ Let $a$ and $b$ be known bounds on the
domains of $X$ and $Y$, respectively. Let
$\mathcal{P}_{0}\subset\mathcal{E}_{0}$ be the set of null distributions
defined above. Given a dataset
$\mathbf{D}=(\mathbf{X},\mathbf{Y},\mathbf{Z})$, let
$(\hat{\mathbf{X}},\hat{\mathbf{Y}},\mathbf{Z})$ be the rescaled dataset
obtained by setting $\hat{\mathbf{X}}=\mathbf{X}/a$ and
$\hat{\mathbf{Y}}=\mathbf{Y}/b$. Consider $R_{i},i\in[n]$, as defined in (2),
for the rescaled dataset $(\hat{\mathbf{X}},\hat{\mathbf{Y}},\mathbf{Z})$. Let
$W_{i}\sim\mathrm{Lap}(0,\Delta/\varepsilon)$ for $i\in[n]$, where
$\Delta,\varepsilon>0$ are constants. Then
$T^{(n)}=T(R_{1}+W_{1},\dots,R_{n}+W_{n})$, defined in Algorithm 1, satisfies:

  1. 1.

For $P\in\mathcal{P}_{0}$ such that
$A_{f}A_{g}=o_{P}(n^{-1}),B_{f}=o_{P}(1),B_{g}=o_{P}(1)$, and
$\mathbb{E}[\chi_{P}^{2}\xi_{P}^{2}]<\infty$, then

$\displaystyle\lim_{n\to\infty}\sup_{t\in\mathbb{R}}|\Pr_{P^{\prime}}[T^{(n)}\leq
t]-\Phi(t)|=0.$

  2. 2.

Let $\mathcal{P}\subset\mathcal{P}_{0}$ be a set of distributions such that
$A_{f}A_{g}=o_{\mathcal{P}}(n^{-1}),B_{f}=o_{\mathcal{P}}(1)$ and
$B_{g}=o_{\mathcal{P}}(1)$. If in addition
$\sup_{P\in\mathcal{P}}\mathbb{E}[|\chi_{P}\xi_{P}|^{2+\eta}]\leq c$, for some
constants $c,\eta>0$, then

$\displaystyle\lim_{n\to\infty}\sup_{P^{\prime}\in\mathcal{P}^{\prime}}\sup_{t\in\mathbb{R}}|\Pr_{P^{\prime}}[T^{(n)}\leq
t]-\Phi(t)|=0.$ (6)

###### Proof.

Let $\sigma_{P}=\sqrt{\mathrm{Var}(\chi_{P}\xi_{P})}$,
$\sigma_{\mathrm{priv}}=\Delta/\varepsilon$, and
$\sigma_{\mathrm{joint}}=\sqrt{\frac{\sigma_{P}^{2}}{a^{2}b^{2}}+2\sigma_{\mathrm{priv}}^{2}}$.
Denote by $\tau_{N}$ the numerator of $T^{(n)}$ and by $\tau_{D}$ the
denominator. We sometimes omit $P$ from the notation for ease of presentation.

#### Item 1:

We first show Item 1. Specifically, we show that
$\tau_{N}\to\mathcal{N}(0,\sigma_{\mathrm{joint}}^{2})$ and
$\tau_{D}\to\sigma_{\mathrm{joint}}$, which, by Slutsky’s lemma (Lemma A.7),
would imply that $T^{(n)}\to\mathcal{N}(0,1)$. For $i\in[n]$, let
$\chi_{i}=x_{i}-f(z_{i})$ and $\xi_{i}=y_{i}-g(z_{i})$. Note that

$\displaystyle\tau_{N}$
$\displaystyle=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}(R_{i}+W_{i})$
$\displaystyle=\frac{1}{ab\sqrt{n}}\sum_{i=1}^{n}(f(z_{i})-\hat{f}(z_{i}))(g(z_{i})-\hat{g}(z_{i}))+\frac{1}{ab\sqrt{n}}\sum_{i=1}^{n}(f(z_{i})-\hat{f}(z_{i}))\xi_{i}$
$\displaystyle+\frac{1}{ab\sqrt{n}}\sum_{i=1}^{n}(g(z_{i})-\hat{g}(z_{i}))\chi_{i}+\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\Big{(}\frac{\chi_{i}\xi_{i}}{ab}+W_{i}\Big{)}$
(7)

We use the following claim obtained from the proof of Theorem 6 of Shah and
Peters [30].

######  Claim A.2 ([30]).

Under the assumptions listed in Item 1 of Theorem A.1, the following hold

  1. 1.

$\frac{1}{\sqrt{n}}\sum_{i=1}^{n}(f(z_{i})-\hat{f}(z_{i}))(g(z_{i})-\hat{g}(z_{i}))\overset{P}{\to}0$.

  2. 2.

$\frac{1}{\sqrt{n}}\sum_{i=1}^{n}(f(z_{i})-\hat{f}(z_{i}))\xi_{i}\overset{P}{\to}0$.

  3. 3.

$\frac{1}{\sqrt{n}}\sum_{i=1}^{n}(g(z_{i})-\hat{g}(z_{i}))\chi_{i}\overset{P}{\to}0$.

  4. 4.

$\frac{1}{n}\sum_{i=1}^{n}R_{i}\overset{P}{\to}0$.

  5. 5.

$\frac{1}{n}\sum_{i=1}^{n}R_{i}^{2}\overset{P}{\to}\frac{\sigma_{P}^{2}}{a^{2}b^{2}}$.

Additionally, under the assumptions of Item 2, all convergence statements
above are uniform over $\mathcal{P}$.

By Claim A.2, Items 1-3, the first three terms of the sum in (7) are
$o_{P}(1)$. We show that the last term of the sum converges to
$\mathcal{N}(0,\sigma_{\mathrm{joint}}^{2})$. Note that
$\mathbb{E}[\frac{\chi_{i}\xi_{i}}{ab}+W_{i}]=0$ and
$\mathrm{Var}(\frac{\chi_{i}\xi_{i}}{ab}+W_{i})=\mathrm{Var}(\chi_{i}\xi_{i})+\mathrm{Var}(W_{i})=\sigma_{\mathrm{joint}}^{2}$.
Since $\sigma_{\mathrm{priv}}$ is a constant and $\sigma_{P}<\infty$, we can
apply the Central Limit Theorem to obtain the desired convergence to a
Gaussian. By Slutsky’s lemma, we obtain that
$\tau_{N}\to\mathcal{N}(0,\sigma_{\mathrm{joint}}^{2})$.

We now consider $\tau_{D}$. Since $\mathbb{E}[W_{i}]=0$ for all $i\in[n]$, by
the Weak Law of Large Numbers it holds that $\frac{1}{n}\sum_{i=1}^{n}W_{i}\to
0$. From Item 4 of Claim A.2, we obtain
$\frac{1}{n}\sum_{i=1}^{n}(R_{i}+W_{i})\overset{P}{\to}0$. It remains to show
that $\frac{1}{n}\sum_{i=1}^{n}(R_{i}+W_{i})^{2}\overset{P}{\to}\sigma_{P}$.
We have

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}(R_{i}+W_{i})^{2}=\frac{1}{n}\sum_{i=1}^{n}R_{i}^{2}+\frac{2}{n}\sum_{i=1}^{n}R_{i}W_{i}+\frac{1}{n}\sum_{i=1}^{n}W_{i}^{2}.$

Since $R_{i}$ and $W_{i}$ are independent, we have
$\mathbb{E}[R_{i}W_{i}]=\mathbb{E}[R_{i}]\mathbb{E}[W_{i}]=0$. Another
application of the Weak Law of Large Numbers yields
$\frac{2}{n}\sum_{i=1}^{n}R_{i}W_{i}\overset{P}{\to}0$. Finally, let
$B^{(n)}=\frac{1}{n}\sum_{i=1}^{n}W_{i}^{2}$. We have
$\mathbb{E}[W_{i}^{2}]=\mathrm{Var}[W_{i}]=2\sigma_{\mathrm{priv}}^{2}$. The
Weak Law of Large numbers gives that $B^{(n)}\to 2\sigma_{\mathrm{priv}}^{2}$.
By Item 5 of Claim A.2 and Slutsky’s lemma, we obtain that
$\tau_{D}\to\sigma_{\mathrm{joint}}$, as desired. This concludes the proof of
Item 1.

#### Item 2:

Turning to Item 2, more care is needed to replace statements of convergence
with statements of uniform convergence due to the presence of privacy noise.
We first show that $\tau_{N}$ converges to
$\mathcal{N}(0,\sigma_{\mathrm{joint}}^{2})$ uniformly. Consider again the sum
in (7). By Claim A.2, Items 1-3, the first three terms of the sum in (7) are
$o_{\mathcal{P}}(1)$, and as a consequence, $o_{\mathcal{P}^{\prime}}(1)$. We
show that

$\displaystyle\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\Big{(}\frac{\chi_{i}\xi_{i}}{ab}+W_{i}\Big{)}\to\mathcal{N}\Big{(}0,\sigma_{\mathrm{joint}}^{2}\Big{)}\text{
uniformly over }\mathcal{P}^{\prime}.$ (8)

Then, applying Item 1 of Lemma A.10 we would obtain the desired convergence of
$\tau_{N}$. We prove (8) by showing that the random variables
$\frac{\chi_{i}\xi_{i}}{ab}+W_{i},i\in[n]$ satisfy the conditions of Lemma
A.8. Recall that $\mathbb{E}[\frac{\chi_{i}\xi_{i}}{ab}+W_{i}]=0$ and
$\mathbb{E}[(\frac{\chi_{i}\xi_{i}}{ab}+W_{i})^{2}]=\mathrm{Var}(\frac{\chi_{i}\xi_{i}}{ab}+W_{i})=\sigma_{\mathrm{joint}}^{2}$,
which is a constant. It remains to bound the $(2+\eta)$-absolute moment of
$\frac{\chi_{i}\xi_{i}}{ab}+W_{i}$. By Claim A.12 and our assumption on
$\chi_{i}\xi_{i}$, we have

$\displaystyle\mathbb{E}\Big{[}\Big{|}\frac{\chi_{i}\xi_{i}}{ab}+W_{i}\Big{|}^{2+\eta}\Big{]}\leq
2^{1+\eta}\Big{(}\mathbb{E}\Big{[}\Big{|}\frac{\chi_{i}\xi_{i}}{ab}\Big{|}^{2+\eta}\Big{]}+\mathbb{E}[|W_{i}|^{2+\eta}]\Big{)}\leq
2^{(1+\eta)}\cdot\Big{(}\frac{c}{(ab)^{2+\eta}}+c^{\prime}\Big{)}$

where $c^{\prime}$ is the (constant) bound on $\mathbb{E}[|W_{i}|^{2+\eta}])$
given by Claim A.13. Thus, all the conditions of Lemma A.8 are satisfied, and
(8) holds. This concludes our argument on the convergence of $\tau_{N}$.

We now show that $\tau_{D}$ converges uniformly over $\mathcal{P}^{\prime}$ to
$\sigma_{\mathrm{joint}}$. We first show that
$n^{-1}\sum_{i=1}^{n}(R_{i}+W_{i})=o_{\mathcal{P}^{\prime}}(1)$. By Item 4 of
Claim A.2, we have that
$n^{-1}\sum_{i=1}^{n}R_{i}=o_{\mathcal{P}^{\prime}}(1)$. We also showed that
$\frac{1}{n}\sum_{i=1}^{n}W_{i}=o_{\mathcal{P}^{\prime}}(1)$. Applying Lemma
A.10, we obtain that
$n^{-1}\sum_{i=1}^{n}(R_{i}+W_{i})=o_{\mathcal{P}^{\prime}}(1)$.

Next, we show that
$n^{-1}\sum_{i=1}^{n}R_{i}W_{i}=o_{\mathcal{P}^{\prime}}(1)$. Note that

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}R_{i}W_{i}$
$\displaystyle=\frac{1}{ab}\Big{(}\frac{1}{n}\sum_{i=1}^{n}(f(z_{i})-\hat{f}(z_{i})+\chi_{i})(g(z_{i})-\hat{g}(z_{i})+\xi_{i})W_{i}\Big{)}$
$\displaystyle=\frac{1}{ab}\Big{(}\frac{1}{n}\sum_{i=1}^{n}(f(z_{i})-\hat{f}(z_{i}))(g(z_{i})-\hat{g}(z_{i}))W_{i}+\frac{1}{n}\sum_{i=1}^{n}(f(z_{i})-\hat{f}(z_{i}))\xi_{i}W_{i}$
$\displaystyle+\frac{1}{n}\sum_{i=1}^{n}(g(z_{i})-\hat{g}(z_{i}))\chi_{P,i}W_{i}+\frac{1}{n}\sum_{i=1}^{n}\chi_{i}\xi_{i}W_{i}\Big{)}$
(9)

We show that each of the terms of the sum in (9) is
$o_{\mathcal{P}^{\prime}}(1)$, starting with
$n^{-1}\sum_{i=1}^{n}\chi_{i}\xi_{i}W_{i}$. We do so by showing that the
conditions of Lemma A.9 hold for the random variables $\chi_{i}\xi_{i}W_{i}$.
More precisely, we need to show that for all
$P^{\prime}\in\mathcal{P}^{\prime}$ it holds that
$\mathbb{E}_{P^{\prime}}[|\chi_{i}\xi_{i}W_{i}|^{1+\eta}]<c_{2}$ for some
$c_{2},\eta>0$. By the assumptions in Item 2, we know
$\mathbb{E}_{P^{\prime}}[|\chi_{P}\xi_{P}|^{1+\eta}]\leq\mathbb{E}_{P^{\prime}}[|\chi_{P}\xi_{P}|^{2+\eta}]\leq
c$. By the independence of $\chi_{i}\xi_{i}$ and $W_{i}$ we have

$\displaystyle\mathbb{E}_{P^{\prime}}[|\chi_{i}\xi_{i}W_{i}|^{1+\eta}]=\mathbb{E}_{P^{\prime}}[|\chi_{P}\xi_{P}|^{1+\eta}]\mathbb{E}_{P^{\prime}}[|W_{i}|^{1+\eta}]\leq
c\cdot c^{\prime},$

where $c^{\prime}$ is a bound on $\mathbb{E}_{P^{\prime}}[|W_{i}|^{1+\eta}]$
given by Claim A.13. Therefore, we have that the variables
$\chi_{i}\xi_{i}W_{i}$ satisfy all properties listed in Lemma A.9, and thus

$\displaystyle n^{-1}\sum_{i=1}^{n}\chi_{i}\xi_{i}W_{i}=o_{\mathcal{P}}(1).$
(10)

Next, we show that

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}(f(z_{i})-\hat{f}(z_{i}))(g(z_{i})-\hat{g}(z_{i}))W_{i}=o_{\mathcal{P}^{\prime}}(1).$
(11)

Denote the term in the LHS of (11) by $b$. We have

$\displaystyle|b|\leq\max_{i\in[n]}|W_{i}|\cdot\Big{(}\frac{1}{n}\sum_{i=1}^{n}(f(z_{i})-\hat{f}(z_{i}))(g(z_{i})-\hat{g}(z_{i}))\Bigr{)}$
(12)

We show that $\max_{i\in[n]}|W_{i}|=O_{\mathcal{P}^{\prime}}(\log n)$ in Claim
A.11. By Item 1 of Claim A.2, the other term in the product in the RHS of (12)
is $o_{\mathcal{P}}(n^{-1/2})$. As a result, $b=o_{\mathcal{P}^{\prime}}(1)$.
By a similar proof, and using Claim A.2, the other terms in the sum in (9) are
equal to $o_{\mathcal{P}^{\prime}}(1)$.

By Item 5 of Claim A.2, we have that $\frac{1}{n}\sum_{i=1}^{n}R_{i}^{2}$
converges uniformly over $\mathcal{P}^{\prime}$ to
$\frac{\sigma_{P}^{2}}{a^{2}b^{2}}$. In addition, we showed that
$\frac{1}{n}\sum_{i\in[n]}W_{i}^{2}$ converges uniformly over
$\mathcal{P}^{\prime}$ to $2\sigma_{\mathrm{priv}}^{2}$. Applying Lemma A.10
we obtain that $\tau_{D}$ converges uniformly over $\mathcal{P}^{\prime}$ to
$\sigma_{\mathrm{joint}}$. One final application of Lemma A.10 yields that
$T^{(n)}$ converges uniformly over $\mathcal{P}^{\prime}$ to
$\mathcal{N}(0,1)$. ∎

###  A.2 Proof of Theorem 3.3

In this section, we state and prove a longer version of Theorem 3.3. Item 1 of
Theorem A.3 gives the pointwise power guarantee, whereas Item 2shows the
uniform power guarantee under a slightly stronger condition. Item 2
corresponds exactly to Theorem 3.3.999The assumptions in Item 2, Theorem A.3
are identical to those of Definition 3.1. The assumptions in Item 1 of Theorem
A.3 are slightly weaker than those of Definition 3.1.

Following Shah and Peters [30], to facilitate the theoretical analysis of
power, we separate the model fitting step from the calculation of the
residuals. We calculate $\hat{f}$ and $\hat{g}$ on the first half of the
dataset and calculate the residuals $R_{i},i\in[n]$ on the second half. In
practice, it is still advised to perform both steps on the full dataset.

######  Theorem A.3.

_(Power of Private GCM)._ Consider the setup of Theorem 3.2. Let
$A_{f},A_{g},B_{f},B_{g}$ be as defined in (4), with the difference that
$\hat{f}$ and $\hat{g}$ are estimated on the first half of the dataset
$(\hat{\mathbf{X}},\hat{\mathbf{Y}},\mathbf{Z})$, and $R_{i},i\in[n/2,n]$ are
calculated on the second half. Define the “signal” ($\rho_{P}$) and “noise”
($\sigma_{P}$) of the true residuals $\chi_{P},\xi_{P}$ as:

$\displaystyle\rho_{P}=\mathbb{E}_{P}[\mathrm{cov}(X,Y\mid
Z)],\sigma_{P}=\sqrt{\mathrm{Var}_{P}(\chi_{P}\xi_{P})}.$

  1. 1.

If for $P\in\mathcal{E}_{0}$ we have
$A_{f}A_{g}=o_{P}(n^{-1}),B_{f}=o_{P}(1),B_{g}=o_{P}(1)$ and
$\sigma_{P}<\infty$, then

$\displaystyle\lim_{n\to\infty}\sup_{t\in\mathbb{R}}\Bigl{|}\Pr_{P^{\prime}}\Bigl{[}T^{(n)}-\frac{\sqrt{n}\rho_{P}}{\sigma_{P}^{\prime}}\leq
t\Bigr{]}-\Phi(t)\Bigr{|}=0,\mbox{ where
}\sigma_{P}^{\prime}=\sqrt{\sigma_{P}^{2}+(\frac{\sqrt{2}ab\Delta}{\varepsilon})^{2}}.$
(13)

  2. 2.

Let $\mathcal{P}\subset\mathcal{E}_{0}$ such that
$A_{f}A_{g}=o_{\mathcal{P}}(n^{-1}),B_{f}=o_{\mathcal{P}}(1)$ and
$B_{g}=o_{\mathcal{P}}(1)$. If in addition
$\sup_{P\in\mathcal{P}}\mathbb{E}[|\chi_{P}\xi_{P}|^{2+\eta}]\leq c$, for some
constants $c,\eta>0$, then (13) holds over $\mathcal{P}^{\prime}$ uniformly.

###### Proof.

Note that $\mathbb{E}[\frac{\chi_{P}\xi_{P}}{ab}]=\frac{\rho}{ab}$ and
$\sqrt{\mathrm{Var}(\frac{\chi_{P}\xi_{P}}{ab})}=\frac{\sigma_{P}}{ab}$. The
proof is similar to that of Theorem A.1, using Claim A.4 below from Shah and
Peters [30]. ∎

######  Claim A.4.

Under the assumptions listed in Theorem 3.3, as $n\to\infty$, the following
hold.

  1. 1.

$\frac{1}{\sqrt{n}}\sum_{i=1}^{n}(f(z_{i})-\hat{f}(z_{i}))(g(z_{i})-\hat{g}(z_{i}))\overset{P}{\to}0$.

  2. 2.

$\frac{1}{\sqrt{n}}\sum_{i=1}^{n}(f(z_{i})-\hat{f}(z_{i}))\xi_{i}\overset{P}{\to}0$.

  3. 3.

$\frac{1}{\sqrt{n}}\sum_{i=1}^{n}(g(z_{i})-\hat{g}(z_{i}))\chi_{i}\overset{P}{\to}0$.

  4. 4.

$\frac{1}{n}\sum_{i=1}^{n}R_{i}\overset{P}{\to}0$.

  5. 5.

$\frac{1}{n}\sum_{i=1}^{n}R_{i}^{2}\overset{P}{\to}\frac{\sigma_{P}^{2}}{a^{2}b^{2}}$.

Additionally, under the assumptions in Item 2 of Theorem 3.3, all convergence
statements above are uniform over $\mathcal{P}$.

######  Corollary A.5.

Under the assumptions of Theorem A.3, Algorithm 1 has asymptotic power of $1$
if $\rho_{P}\neq 0$.

Next, we show that Theorem 3.3 implies that the private GCM has asymptotic
power of $1$. A similar claim and proof holds for uniformly asymptotic power.

###### Proof.

Note that Algorithm 1 has asymptotic power of $1$ if, for all $M>0$, it holds
$\Pr_{P}[T^{(n)}>M]\to 1$ as $n\to\infty$. Given $M>0$, note that

$\displaystyle\Pr[T^{(n)}\leq M]$
$\displaystyle=\Pr_{P^{\prime}}\Bigl{[}T^{(n)}-\frac{\sqrt{n}\rho_{P}}{\sigma_{P}^{\prime}}\leq
M-\frac{\sqrt{n}\rho_{P}}{\sigma_{P}^{\prime}}\Bigr{]}\to\Phi\Bigl{(}M-\frac{\sqrt{n}\rho_{P}}{\sigma_{P}^{\prime}}\Bigr{)},$

where the convergence statement follows from Theorem 3.3. Since $\rho_{P}\neq
0$ and $\sigma_{P}^{\prime}$ is a constant, then
$M-\frac{\sqrt{n}\rho_{P}}{\sigma_{P}^{\prime}}\to-\infty$ as $n\to\infty$.
Therefore
$\Phi\Bigl{(}M-\frac{\sqrt{n}\rho_{P}}{\sigma_{P}^{\prime}}\Bigr{)}\to 0$, and
as a result $\Pr[T^{(n)}\leq M]\to 0$, as desired. ∎

###  A.3 Guarantees of PrivGCM

In this section, we prove Lemma 3.4 on the sensitivity of the residuals
products for kernel ridge regression. We then use Lemma 3.4 to prove Corollary
A.6 on the type-I error and power gurantess of PrivGCM.

See 3.4

###### Proof.

Consider two neighboring datasets $(\mathbf{X},\mathbf{Y},\mathbf{Z})$ and
$(\mathbf{X}^{\prime},\mathbf{Y}^{\prime},\mathbf{Z}^{\prime})$. For
$i\in[n]$, let $r_{X,i},r_{Y,i}$ denote the residuals of fitting a kernel
ridge regression model of $\mathbf{X}$ to $\mathbf{Z}$ and $\mathbf{Y}$ to
$\mathbf{Z}$, respectively. Suppose without loss of generality that
$(\mathbf{X},\mathbf{Y},\mathbf{Z})$ and
$(\mathbf{X}^{\prime},\mathbf{Y}^{\prime},\mathbf{Z}^{\prime})$ differ only in
the last datapoint, i.e.,
$(x_{i},y_{i},z_{i})=(x_{i}^{\prime},y_{i}^{\prime},z_{i}^{\prime})$ for
$i\in[n-1]$. Then, by Theorem 2.5, for $i\in[n-1]$, we have

$\displaystyle|r_{X,i}-r_{X,i}^{\prime}|=|(x_{i}-\mathbf{w}^{\top}\phi(z_{i}))-(x_{i}^{\prime}-\mathbf{w}^{\prime\top}\phi(z_{i}^{\prime}))|=|\mathbf{w}^{\top}\phi(z_{i})-\mathbf{w}^{\prime\top}\phi(z_{i})|\leq\frac{8\sqrt{2}}{\lambda^{3/2}n}+\frac{8}{\lambda
n}.$

For the last datapoint we have

$\displaystyle|r_{X,n}-r_{X,n}^{\prime}|$
$\displaystyle=|(x_{n}-\mathbf{w}^{\top}\phi(z_{n}))-(x_{n}^{\prime}-\mathbf{w}^{\prime\top}\phi(z_{n}^{\prime}))|$
$\displaystyle\leq|x_{n}-x_{n}^{\prime}|+\lVert\mathbf{w}^{\prime}\rVert_{\mathcal{H}}|\phi(z_{n}^{\prime})-\phi(z_{n})|+|\mathbf{w}^{\prime\top}\phi(z_{n})-\mathbf{w}^{\top}\phi(z_{n})|$
$\displaystyle\leq
2+\frac{2\sqrt{2}}{\sqrt{\lambda}}+\frac{8\sqrt{2}}{\lambda^{3/2}n}+\frac{8}{\lambda
n}.$

Finally, note that for all $i\in[n]$, we
have$|r_{X,i}|\leq|x_{i}|+\lVert\mathbf{w}\rVert_{\mathcal{H}}\lVert\phi(z_{i})\rVert_{\mathcal{H}}\leq
1+\frac{\sqrt{2}}{\sqrt{\lambda}}$. The same bound holds for $|r_{Y,i}|$. Let
$c_{1}=2+\frac{2\sqrt{2}}{\sqrt{\lambda}}$ and
$c_{2}=\frac{8\sqrt{2}}{\lambda^{3/2}}+\frac{8}{\lambda}$. This gives us that
for all $i\in[n-1]$:

$\displaystyle|R_{i}-R_{i}^{\prime}|\leq|r_{X,i}|||r_{Y,i}-r_{Y,i}^{\prime}|+|r_{Y,i}^{\prime}||r_{X,i}-r_{X,i}^{\prime}|\leq
2\Big{(}1+\frac{\sqrt{2}}{\sqrt{\lambda}}\Big{)}\Big{(}\frac{8\sqrt{2}}{\lambda^{3/2}n}+\frac{8}{\lambda
n}\Big{)}=\frac{c_{1}c_{2}}{n}.$

For $i=n$ we have

$\displaystyle|R_{n}-R_{n}^{\prime}|\leq
2\Big{(}1+\frac{\sqrt{2}}{\sqrt{\lambda}}\Big{)}\Big{(}2+\frac{2\sqrt{2}}{\sqrt{\lambda}}+\frac{8\sqrt{2}}{\lambda^{3/2}n}+\frac{8}{\lambda
n}\Big{)}=c_{1}(c_{1}+\frac{c_{2}}{n}).$

Finally,

$\displaystyle\lVert\mathbf{R}-\mathbf{R}^{\prime}\rVert_{1}=\sum_{i=1}^{n}|R_{i}-R_{i}^{\prime}|\leq(n-1)\cdot\frac{c_{1}c_{2}}{n}+c_{1}(c_{1}+\frac{c_{2}}{n})=c_{1}^{2}+c_{1}c_{2},$

as desired. ∎

######  Corollary A.6.

Let $a$ and $b$ be known bounds on the domains of $X$ and $Y$, respectively.
Given a dataset $\mathbf{D}=(\mathbf{X},\mathbf{Y},\mathbf{Z})$, let
$(\hat{\mathbf{X}},\hat{\mathbf{Y}},\mathbf{Z})$ be the rescaled dataset
obtained by setting $\hat{\mathbf{X}}=\mathbf{X}/a$ and
$\hat{\mathbf{Y}}=\mathbf{Y}/b$. Let PrivGCM be the algorithm which runs
Algorithm 1 with kernel ridge regression as the fitting procedure
$\mathcal{F}$ and sensitivity bound $\Delta=C$, where $C$ is the constant from
Lemma 3.4. Algorithm PrivGCM is $\varepsilon$-differentially private.

The statistic $T^{(n)}=T(R_{1}+W_{1},\dots,R_{n}+W_{n})$, defined in Algorithm
1, satisfies the following.

  1. 1.

Let $\mathcal{P}\subset\mathcal{P}_{0}$ be a family of distributions such that
$A_{f}A_{g}=o_{\mathcal{P}}(n^{-1}),B_{f}=o_{\mathcal{P}}(1),B_{g}=o_{\mathcal{P}}(1)$.
If in addition
$\sup_{P\in\mathcal{P}}\mathbb{E}[|\chi_{P}\xi_{P}|^{2+\eta}]\leq c$, for some
constants $c,\eta>0$, then

$\displaystyle\lim_{n\to\infty}\sup_{P^{\prime}\in\mathcal{P}^{\prime}}\sup_{t\in\mathbb{R}}|\Pr_{P^{\prime}}[T^{(n)}\leq
t]-\Phi(t)|=0.$

  2. 2.

Define $\rho_{P}=\mathbb{E}_{P}[\mathrm{cov}(X,Y\mid Z)]$ and
$\sigma_{P}=\sqrt{\mathrm{Var}_{P}(\chi_{P}\xi_{P})}$. Let
$\mathcal{P}\subset\mathcal{E}_{0}$ be a family of distributions such that
$A_{f}A_{g}=o_{\mathcal{P}}(n^{-1}),B_{f}=o_{\mathcal{P}}(1)$ and
$B_{g}=o_{\mathcal{P}}(1)$. If in addition we have
$\sup_{P\in\mathcal{P}}\mathbb{E}[|\chi_{P}\xi_{P}|^{2+\eta}]\leq c$, for some
constants $c,\eta>0$, then

$\displaystyle\lim_{n\to\infty}\sup_{P^{\prime}\in\mathcal{P}^{\prime}}\sup_{t\in\mathbb{R}}\Bigl{|}\Pr_{P^{\prime}}\Bigl{[}T^{(n)}-\frac{\sqrt{n}\rho_{P}}{\sigma_{P}^{\prime}}\leq
t\Bigr{]}-\Phi(t)\Bigr{|}=0,$

where $\sigma_{P}^{\prime}=\sqrt{\sigma_{P}^{2}+(\frac{\sqrt{2}ab\cdot
C}{\varepsilon})^{2}}$.

###### Proof.

The fact that PrivGCM is $\varepsilon$-differentially private follows from
Lemmas 2.3 and 3.4. Note that if the regularization parameter $\lambda$ is
chosen adaptively based on the data, then obtaining the value of the constant
$C$ by plugging in $\lambda$ might not be $\varepsilon$-differentially
private. This can be resolved by setting an a priori lower bound on $\lambda$,
independent of the data, e.g., $\lambda\geq 1$, and plugging that lower bound
to obtain $C$.

Item 1 follows from Theorem 3.2 and Lemma 3.4. Item 2 follows from Theorem 3.3
and Lemma 3.4 ∎

###  A.4 Auxiliary Lemmas

######  Lemma A.7 (Slutsky’s Lemma).

Let $A_{n},B_{n}$ be sequences of random variables. If $A_{n}$ converges in
distribution to $A$ and $B_{n}$ converges in probability to a constant $c$,
then (1) $A_{n}+B_{n}\to A+c$, (2) $A_{n}\cdot B_{n}\to c\cdot A$, and (3)
$A_{n}/B_{n}\to A/c$.

######  Lemma A.8 (Uniform version of the Central Limit Theorem (Lemma 18 of
Shah and Peters [30])).

Let $\mathcal{P}$ be a family of distributions for a random variable $\zeta$
such that for all $P\in\mathcal{P}$ it holds $\mathbb{E}_{P}[\zeta]=0$,
$\mathbb{E}_{P}[\zeta^{2}]=1$, and $\mathbb{E}_{P}[|\zeta|^{2+\eta}]<c$ for
some $\eta,c>0$. Let $(\zeta_{i})_{i\in\mathbb{N}}$ be i.i.d copies of
$\zeta$. For $n\in\mathbb{N}$, define
$S_{n}=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\zeta_{i}$. Then

$\displaystyle\lim_{n\to\infty}\sup_{P\in\mathcal{P}}\sup_{t\in\mathbb{R}}|\Pr_{P}[S_{n}\leq
t]-\Phi(t)|=0.$

######  Lemma A.9 (Uniform version of the Weak Law of Large Numbers (Lemma 19
of Shah and Peters [30])).

Let $\mathcal{P}$ be a family of distributions for a random variable $\zeta$
such that for all $P\in\mathcal{P}$ it holds $\mathbb{E}_{P}[\zeta]=0$ and
$\mathbb{E}_{P}[|\zeta|^{1+\eta}]<c$ for some $\eta,c>0$. Let
$(\zeta_{i})_{i\in\mathbb{N}}$ be i.i.d copies of $\zeta$. For
$n\in\mathbb{N}$, define $S_{n}=\frac{1}{n}\sum_{i=1}^{n}\zeta_{i}$. Then for
all $\delta>0$ it holds

$\displaystyle\lim_{n\to\infty}\sup_{P\in\mathcal{P}}\Pr_{P}[|S_{n}|>\delta]=0.$

######  Lemma A.10 (Uniform version of Slutsky’s Lemma (Lemma 20 of Shah and
Peters [30])).

Let $\mathcal{P}$ be a family of distributions that determines the law of
sequences $(A_{n})_{n\in\mathbb{N}}$ and $(B_{n})_{n\in N}$ of random
variables.

  1. 1.

If $A_{n}$ converges uniformly over $\mathcal{P}$ to $\mathcal{N}(0,1)$, and
$B_{n}=o_{\mathcal{P}}(1)$, then $A_{n}+B_{n}$ converges uniformly over
$\mathcal{P}$ to $\mathcal{N}(0,1)$.

  2. 2.

If $A_{n}$ converges uniformly over $\mathcal{P}$ to $\mathcal{N}(0,1)$, and
$B_{n}=1+o_{\mathcal{P}}(1)$, then $A_{n}/B_{n}$ converges uniformly over
$\mathcal{P}$ to $\mathcal{N}(0,1)$.

  3. 3.

If $A_{n}=M+o_{\mathcal{P}}(1)$ for some $M>0$ and $B_{n}=o_{\mathcal{P}}(1)$,
then $A_{n}+B_{n}=M+o_{\mathcal{P}}(1)$.

  4. 4.

If $A_{n}=o_{\mathcal{P}}(1)$ and $B_{n}=o_{\mathcal{P}}(1)$, then
$A_{n}+B_{n}=o_{\mathcal{P}}(1)$.

######  Claim A.11.

Let $(W_{i})_{i\in\mathbb{N}}$ be i.i.d copies of
$W\sim\mathrm{Lap}(0,\sigma)$. Let $S_{n}=\max_{i\in[n]}|W_{i}|$. Then
$\mathbb{E}[S_{n}]\leq\sigma(1+\ln n)$.

###### Proof.

If $W_{i}\sim\mathrm{Lap}(0,\sigma)$, then
$|W_{i}|\sim\mathrm{Exponential}(\sigma^{-1})$. It is a known fact that
$\mathbb{E}[\max{|W_{1}|,\dots,|W_{n}|}]=\sigma\cdot H(n)$, where $H(n)$ is
the harmonic number $H(n)=\sum_{i=1}^{n}1/i$. The claim follows from the fact
that $H(n)\leq\ln(n)+1$. ∎

######  Claim A.12.

Let $A$ and $B$ be random variables and $p>1$. Then $\mathbb{E}[|A+B|^{p}]\leq
2^{p-1}(\mathbb{E}[|A|^{p}]+\mathbb{E}[|B|^{p}])$.

######  Claim A.13.

Let $W\sim\mathrm{Laplace}(0,\sigma)$. Then for $n\in\mathrm{N}$ we have
$\mathbb{E}[|W|^{n}]=\frac{n!}{\sigma^{n}}$.

###### Proof.

This claim follows from the fact that
$|W|\sim\mathrm{Exponential}(\sigma^{-1})$. ∎

##  Appendix B Proofs of Section 4

In this section, we collect all missing proofs from Section 4.

See 4.3

###### Proof.

Fix $c\in[0,m]$. First, we bound the sensitivity of $Q_{c}$. Suppose by
contradiction that $|Q_{c}-Q_{c}^{\prime}|>\Delta_{T}$. Consider the case when
$Q_{c}>Q_{c}^{\prime}$. Then $Q_{c}>Q_{c}^{\prime}+\Delta_{T}$. Let
$\mathtt{Above}_{c}=\\{i\in[0,m]\mid T_{i}\geq Q_{c}\\}$. Define
$\mathtt{Above}^{\prime}_{c}$ similarly. Then, for all
$i\in\mathtt{Above}_{c}$, we have

$\displaystyle T_{i}^{\prime}\geq T_{i}-\Delta_{T}\geq
Q_{c}-\Delta_{T}>Q_{c}^{\prime},$ (14)

where the first inequality holds since the values $T_{i}$ have sensitivity at
most $\Delta_{T}$, the second inequality holds from $i\in\mathtt{Above}_{c}$,
and the last inequality holds from our assumption by contradiction. Thus
$i\in\mathtt{Above}^{\prime}_{c}$, and as a result
$\mathtt{Above}_{c}\subseteq\mathtt{Above}_{c}^{\prime}$. Moreover, for $j$
such that $T_{j}^{\prime}=Q_{c}^{\prime}$ we have that
$j\notin\mathtt{Above}_{c}$ since it does not satisfy (14). Therefore
$|\mathtt{Above}^{\prime}_{c}|>|\mathtt{Above}_{c}|$, a contradiction.

For the case when $Q_{c}<Q_{c}^{\prime}$ we obtain a contradiction by a
symmetric argument. This concludes the proof on the sensitivity of $Q_{c}$.
Next, we bound the sensitivity of the score function. We have,

$\displaystyle|s_{k}(c,\mathbf{D})-s_{k}(c,\mathbf{D})|\leq\frac{\Big{|}|Q_{c}-T_{k}|-|Q_{c}^{\prime}-T_{k}^{\prime}|\Big{|}}{2\Delta_{T}}\leq\frac{|Q_{c}-Q_{c}^{\prime}|+|T_{k}-T_{k}^{\prime}|}{2\Delta_{T}}.$

We just showed that $|Q_{c}-Q_{c}^{\prime}|\leq\Delta_{T}$. Since the queries
$T_{i}$ have sensitivity at most $\Delta_{T}$, we also have
$|T_{k}-T_{k}^{\prime}|\leq\Delta_{T}$. We obtain that
$|s(c,\mathbf{D})-s(c,\mathbf{D})|\leq 1$ for all neighboring datasets
$\mathbf{D},\mathbf{D}^{\prime}$. ∎

See 4.5

###### Proof.

Suppose that $\mathbf{D}$ and $\mathbf{D}^{\prime}$ differ in the last row. In
the following, we assume that $j\in[m]$ is fixed. To ease notation, we remove
the superscript $(j)$ from all $r_{X,i}^{(j)},r_{Y,i}^{(j)}$ and
$R_{i}^{(j)}$. Since we know $\mathbb{E}[X\mid Z]$ exactly, we have
$r_{X,i}=x_{i}-\mathbb{E}[X\mid Z=z_{i}]$ for $i\in[n],j\in[m]$. Then for
$i\in[n]$ we have

$\displaystyle|r_{X,i}-r_{X,i}^{\prime}|=|(x_{i}-\mathbb{E}[X\mid
Z=z_{i}])-(x_{i}^{\prime}-\mathbb{E}[X\mid Z=z_{i}^{\prime}])|.$

If $i\in[n-1]$, then $x_{i}=x_{i}^{\prime}$ and $z_{i}=z_{i}^{\prime}$, so
that $|r_{X,i}-r_{X,i}|=0$. For $i=n$, we have $|r_{X,n}-r_{X,n}|\leq 2$ by
the triangle inequality and since $|r_{X,n}|\leq 1$.

Let $c_{1}=2+\frac{2\sqrt{2}}{\sqrt{\lambda}}$ and
$c_{2}=\frac{8\sqrt{2}}{\lambda^{3/2}}+\frac{8}{\lambda}$. Turning to the
residuals of fitting $\mathbf{Y}$ to $\mathbf{Z}$, by the same argument as in
Lemma 3.4 we have, for all $i\in[n-1]$,

$\displaystyle|r_{Y,i}-r_{Y,i}^{\prime}|\leq\frac{8\sqrt{2}}{\lambda^{3/2}n}+\frac{8}{\lambda
n}=\frac{c_{2}}{n}.$

For the last datapoint it holds

$\displaystyle|r_{Y,n}-r_{Y,n}^{\prime}|\leq
2+\frac{2\sqrt{2}}{\sqrt{\lambda}}+\frac{8\sqrt{2}}{\lambda^{3/2}n}+\frac{8}{\lambda
n}=c_{1}+\frac{c_{2}}{n}.$

Additionally, $|r_{Y,i}|\leq c_{1}/2$ for all $i\in[n]$.

We can now bound the sensitivity of the residual products
$R_{i}=r_{X,i}r_{Y,i}$. For $i\in[n-1]$, we have

$\displaystyle|R_{i}-R_{i}^{\prime}|\leq|r_{X,i}|||r_{Y,i}-r_{Y,i}^{\prime}|+|r_{Y,i}^{\prime}||r_{X,i}-r_{X,i}^{\prime}|\leq\frac{c_{2}}{n}+0.$

For $i=n$ we have

$\displaystyle|R_{n}-R_{n}^{\prime}|\leq\Big{(}c_{1}+\frac{c_{2}}{n}\Big{)}+\frac{c_{1}}{2}\cdot
2=2c_{1}+\frac{c_{2}}{n}.$

Finally,

$\displaystyle|T_{j}-T_{j}^{\prime}|=\Big{|}\sum_{i=1}^{n}R_{i}-\sum_{i=1}^{n}R_{i}^{\prime}\Big{|}\leq\sum_{i=1}^{n}|R_{i}-R_{i}^{\prime}|\leq(n-1)\cdot\frac{c_{2}}{n}+2c_{1}+\frac{c_{2}}{n}=2c_{1}+c_{2}.$

∎

See 4.7

###### Proof.

We first show that PrivCRT is $\varepsilon$-differentially private. The scores
$T_{i},i\in[0,m]$ have sensitivity at most $\Delta_{T}=O(1)$ by Lemma 4.5.
Therefore, the scores $s_{i},i\in[0,m]$ have sensitivity at most $1$ by Lemma
4.3. Finally, by Theorem 4.1 we have that outputting $\hat{c}$ is
$\varepsilon$-DP. Therefore, PrivCRT is $\varepsilon$-DP. Note that if the
regularization parameter $\lambda$ is chosen adaptively based on the data,
then obtaining the value of the constant $C^{\prime}$ by plugging in $\lambda$
might not be $\varepsilon$-differentially private. This can be resolved by
setting an a priori lower bound on $\lambda$, independent of the data, e.g.,
$\lambda\geq 1$, and plugging that lower bound to obtain $C^{\prime}$.

Next, we analyze the accuracy of PrivCRT. Let $c^{*}$ be the true rank of
$T_{0}$ amongst the statistics $\\{T_{i}\\}_{i\in[0,m]}$, sorted in decreasing
order. Then $p^{*}=(1+c^{*})/(m+1)$. Note that $s_{c^{*}}=0$. By Theorem 4.1,
with probability at least $1-\delta$, it holds

$\displaystyle s_{\hat{c}}\geq-\frac{2\log(m/\delta)}{\varepsilon}.$

As a result,

$\displaystyle|Q_{\hat{c}}-T_{0}|=-2\Delta_{T}\cdot
s_{\hat{c}}\leq\frac{4\Delta_{T}\log(m/\delta)}{\varepsilon}.$

Let $\gamma=\frac{4\Delta_{T}\log(m/\delta)}{\varepsilon}$. The rank $c^{*}$
of $T_{0}$ cannot differ from $\hat{c}$ by more than $G_{\gamma}$, since
$Q_{\hat{c}}$ is within distance $\gamma$ of $T_{0}$. Therefore,
$|\hat{p}-p^{*}|\leq\frac{G_{\gamma}}{m+1}$, and since $\Delta_{T}=O(1)$, we
obtain the desired result. ∎

##  Appendix C Additional Experimental Details and Results

#### Example Dataset.

In Fig. 8 we show one example dataset from our simulations. We fit a kernel
ridge regression model of $X$ to $Z$. As can be observed, the model we fit
matches $\mathbb{E}[X|Z]$ closely.

Figure 8: Values of $X$ and $Z$ (after rescaling) of one sampled dataset from
our simulations, with $n=1000$, $\beta=0$, $s=2$, $d=1$. A kernel ridge
regression model is fitted to the data. The model we fit closely matches
$\mathbb{E}[X|Z]$.

#### Implementation of Private Kendall and PrivToT.

The implementation of PrivToT requires setting a parameter $k$ for the number
of subsets into which the original dataset is divided. We use $k=10$ for the
experiments in Fig. 1. We additionally experimented with $k\in[20,50,100]$ and
found that $k=10$ performs the best in terms of type-I error. The
implementation of PrivToT was adapted from the implementation of Kazan et al.
[18]. The private Kendall test works for categorical $Z$. To adapt it to
continuous $Z$ we apply $k$-means clustering to $Z$ to obtain $100$ clusters.
The implementation of private Kendall was adapted from Wang et al. [39].

Figure 9: Effect on the power of PrivCRT with increasing $m$. Figure 10:
Distribution of p-values output by PrivCRT for different dependence strengths
$\beta$ under the setup in Section 5. Under the null, i.e., $\beta=0$, the
p-values are uniformly distributed as desired.

#### The Effect of Varying $m$ on the Power of PrivCRT.

In Fig. 9, we vary $m$, the number of resamples used in the CRT algorithm and
run our experiments for $\beta\in\\{0,0.5,1.5\\}$. We set $n=10^{3}$ and
$\varepsilon=2$. Increasing $m$ does not affect the type-I error control of
PrivCRT. However, we observe that the power of PrivCRT decreases as the number
of resamples $m$ increases. This is due to the increase of the variable
$G_{\gamma}$ with $m$ (see Definition 4.6). More specifically, for a fixed
$\gamma$, as $m$ increases, $T_{0}$ stays fixed, while the number of other
statistics $T_{i}$ within distance $\gamma$ of $T_{0}$ increases. Thus, the
private test is more likely to select a rank that is further from the true
rank. It is an interesting open question whether the dependence on $m$ in the
accuracy of a private CRT test is avoidable. For now, we recommend using
$m=O(1/\alpha)$ when employing PrivCRT.

#### Distribution of p-values Output by PrivCRT.

In Fig. 10 we show the distribution of the p-values output by PrivCRT for
different dependence strengths $\beta$. We set $n=10^{3}$, $m=19$, and
$\varepsilon=2$. Under the null, i.e., when $\beta=0$, the p-values output by
PrivCRT are uniformly distributed in the interval $[\frac{1}{m+1},1]$. Thus,
PrivCRT controls type-I error. When $\beta>0$, most of the p-values are close
to $\alpha=0.05$, which is the desired outcome for PrivCRT to achieve power.