###### Abstract

Recent years have witnessed growing concerns about the privacy of sensitive
data. In response to these concerns, differential privacy has emerged as a
rigorous framework for privacy protection, gaining widespread recognition in
both academic and industrial circles. While substantial progress has been made
in private data analysis, existing methods often suffer from impracticality or
a significant loss of statistical efficiency. This paper aims to alleviate
these concerns in the context of hypothesis testing by introducing
differentially private permutation tests. The proposed framework extends
classical non-private permutation tests to private settings, maintaining both
finite-sample validity and differential privacy in a rigorous manner. The
power of the proposed test depends on the choice of a test statistic, and we
establish general conditions for consistency and non-asymptotic uniform power.
To demonstrate the utility and practicality of our framework, we focus on
reproducing kernel-based test statistics and introduce differentially private
kernel tests for two-sample and independence testing: $\mathrm{dpMMD}$ and
$\mathrm{dpHSIC}$. The proposed kernel tests are straightforward to implement,
applicable to various types of data, and attain minimax optimal power across
different privacy regimes. Our empirical evaluations further highlight their
competitive power under various synthetic and real-world scenarios,
emphasizing their practical value. The code is publicly available to
facilitate the implementation of our framework.

Differentially Private Permutation Tests:
Applications to Kernel Methods

Ilmun Kim†,⋄ Antonin Schrab‡,⋄

†Department of Statistics and Data Science, Yonsei University
---
‡Centre for Artificial Intelligence, Gatsby Computational Neuroscience Unit,
University College London & Inria London
⋄Both authors contributed equally to this work

##  1 Introduction

Ensuring the privacy of sensitive data has become a critical concern in modern
data analysis. As organizations collect and analyze vast amounts of personal
information, safeguarding individual privacy has emerged as a crucial ethical
and legal imperative. In response to these challenges, differential privacy
(DP), introduced by Dwork et al., 2006b , has emerged as a rigorous framework
for addressing privacy concerns, and has gained widespread recognition not
only in academia but also in industrial companies. For instance, major
industry players such as Apple (Apple,, 2017), Google (Erlingsson et al.,,
2014) and Microsoft (Ding et al.,, 2017) have embraced differential privacy as
a robust definition of privacy. This growing trend has sparked a recent surge
of research in statistics and related fields, aiming at integrating
differential privacy and its variants (Dwork et al., 2006a, ; Bun and
Steinke,, 2016; Mironov,, 2017; Dong et al.,, 2022) into data analysis and
developing privacy-preserving methodologies. In this line of work, a major
challenge is to strike a balance between privacy guarantees and statistical
efficiency. Notably, a high privacy guarantee requires substantial data
perturbation, which in turn degrades statistical performance. Conversely,
releasing less perturbed data can improve statistical efficiency but at the
expense of reduced privacy guarantees. Therefore, balancing this trade-off
between privacy and efficiency has been a central topic in the existing
literature (_e.g._ , Duchi et al.,, 2018; Cai et al.,, 2021; Kamath and
Ullman,, 2020).

Broadly, there are two major statistical problems tackled under privacy
constraints: estimation and hypothesis testing (Kamath and Ullman,, 2020, for
a recent review). This paper focuses on the latter problem, which requires
access to the null distribution of a test statistic in order to effectively
calibrate a test statistic. Analyzing the distribution of a test statistic
becomes particularly more challenging in private settings due to additional
random sources arising from privacy mechanisms. As we review in Section 1.1,
substantial efforts have been made to address private testing problems. These
efforts involve adapting classical hypothesis tests to private settings or
developing new testing procedures that achieve an optimal balance between
privacy and statistical power.

Despite the significant progress made over the last decade, there are still
several areas where further improvements can be made. One such area includes
the reliance on asymptotic methods for determining the critical value of a
test statistic. The practical quality of this asymptotic approach depends on
the convergence rate of a privatized statistic to the limiting distribution.
This convergence rate is often slow in private settings, and more importantly,
the limiting distribution may vary depending on the delicate interplay between
privacy and other parameters. This issue puts practitioners in a bind as it is
unclear which limiting distribution should be considered a priori. All these
concerns lead to the unreliability of asymptotic private tests in real-world
applications.

Another area of concern is the limited practicality of existing methods. Many
private statistical tests are designed specifically for discrete data, not
directly applicable to handling continuous or mixed-type data. Moreover,
existing methods often rely on unspecified constants and heuristics, making
them less user-friendly and potentially undermining their reliability. We also
point out that the majority of research has concentrated on theoretical
aspects of private testing, and only a handful of papers are equipped with
thorough empirical evaluations and open-source code.

In this work, we aim to tackle the aforementioned concerns by introducing
differentially private permutation tests. The primary goal is to extend
classical non-private permutation tests to differentially private settings,
applicable to any test statistic with finite global sensitivity. The proposed
private permutation test inherits the finite-sample validity of the classical
permutation test under the exchangeability condition, while ensuring
differential privacy. The power of the proposed test depends on the choice of
a test statistic, and we establish sufficient conditions for consistency and
non-asymptotic uniform power. To demonstrate the effectiveness of our
framework, we focus on the two-sample and independence testing problems and
propose differentially private versions of the maximum mean discrepancy (MMD)
and Hilbert–Schmidt independence criterion (HSIC), which we coin as “dpMMD”
and “dpHSIC”, respectively. On the theoretical side, we prove minimax
optimality of $\mathrm{dpMMD}$ and $\mathrm{dpHSIC}$ tests over the entire
privacy regimes in terms of kernel metrics. On the empirical side, we showcase
the competitive power performance of the proposed tests across various
practical scenarios. The code that implements our methods is publicly
available at https://github.com/antoninschrab/dpkernel to allow practitioners
to build on our findings.

###  1.1 Related Work

In recent years, there has been a growing body of research on hypothesis
testing problems under privacy constraints. Since the early work by Vu and
Slavkovic, (2009) and Fienberg et al., (2011), numerous attempts have been
made to extend classical non-private tests to their private counterparts.
Examples include ANOVA (Campbell et al.,, 2018; Swanberg et al.,, 2019),
likelihood ratio tests (Canonne et al.,, 2019), tests for regression
coefficients (Sheffet,, 2017; Alabi and Vadhan,, 2022), rank or sign-based
nonparametric tests (Task and Clifton,, 2016; Couch et al.,, 2019),
conditional independence tests (Kalemaj et al.,, 2023) and $\chi^{2}$-tests
(Fienberg et al.,, 2011; Wang et al.,, 2015; Gaboardi et al.,, 2016; Rogers
and Kifer,, 2017; Kakizaki et al.,, 2017; Friedberg and Rogers,, 2023). While
most of the aforementioned work focuses on asymptotic settings where the
sample size goes to infinity, a recent line of work within computer science
has placed greater emphasis on finite-sample analysis. In particular, Cai et
al., (2017) propose a two-step algorithm for identity testing for discrete
distributions, and studies the sample complexity under DP. The work of Acharya
et al., (2018) explores both identity (goodness-of-fit) testing and closeness
(two-sample) testing in finite-sample settings, and improves the upper bound
result by Cai et al., (2017) and Aliakbarpour et al., (2018) for identity
testing. Aliakbarpour et al., (2019) privatize the non-private test proposed
by Diakonikolas and Kane, (2016), and investigate the sample complexity for
closeness testing and independence testing. In line with these advancements,
our work develops private permutation tests, and studies their non-asymptotic
performance under DP settings.

Despite the extensive body of literature, the majority of research has focused
on private tests designed for discrete or bounded data. There are a few
notable exceptions that have explored other data types. For example, Canonne
et al., (2020) and Narayanan, (2022) have investigated goodness-of-fit testing
for high-dimensional Gaussian distributions. In addition, Raj et al., (2020)
have proposed private two-sample tests based on finite dimensional
approximations of kernel mean embeddings. The flexibility offered by kernels
methods enables these tests to handle a wide variety of data types. However,
their tests are asymptotic in nature, which may introduce reliability concerns
when working with small sample sizes. Moreover, their analysis requires the
number of features to be fixed. Such requirement potentially limits the power
of the test when dealing with alternatives which are not well-represented by
these fixed numbers of features.

Another line of work aims to develop a generic way to create private tests
from non-private ones. The subsample-and-aggregate idea (Nissim et al.,, 2007)
has emerged as a useful tool for this purpose. In particular, it offers a
strategy to convert non-private sample complexity results into private ones in
a black-box manner as pointed out by Cai et al., (2017); Canonne et al.,
(2019, 2020). Recent studies by Peña and Barrientos, (2022) and Kazan et al.,
(2023) have focused specifically on the practical implementation of the
subsample-and-aggregate approach. However, it is worth mentioning that this
generality typically comes at the cost of suboptimal power, and often fails to
recover the optimal sample complexity (Canonne et al.,, 2019, 2020). Moreover,
the performance of this subsample-and-aggregate approach is sensitive to the
number of subsamples, and determining the optimal value of this parameter
remains an open problem.

Beyond global differential privacy, there has been a substantial amount of
work on hypothesis testing under local differential privacy. Some of the
notable works include Liao et al., (2017); Gaboardi and Rogers, (2018);
Sheffet, (2018); Acharya et al., (2019); Berrett and Butucea, (2020); Dubois
et al., (2023); Lam-Weil et al., (2022) and see the references therein. Local
differential privacy requires data perturbation at the individual level,
proving particularly useful in settings where data providers lack trust in
data analysts. This individual-wise approach demands different analyses than
global differential privacy, and the results under global and local
differential privacy are not directly comparable.

Our work is also related to recent advances in kernel-based minimax testing
(Li and Yuan,, 2019; Albert et al.,, 2022; Schrab et al.,, 2023; Kim et al.,
2022a, ). Specifically, we extend the non-private minimax testing rates
established in this line of work to private counterparts. To achieve this, we
leverage the techniques therein, such as the two moments method and
exponential inequalities for permuted statistics in Kim et al., 2022a , and
adapt them to private settings.

###  1.2 An Overview of Our Results

The main contributions of this work are summarized below.

  * •

DP Permutation Tests (Section 3). We introduce differentially private
permutation tests in Algorithm 1, and establish their theoretical properties.
A naive way of extending the classical permutation tests to private settings
is to first make the original test statistic and its permuted counterparts
differentially private, and then carry out the permutation test based on these
individually privatized statistics. However, this naive approach results in an
unnecessary power loss by adding more noise as the number of permutations
increases. The proposed framework addresses this issue by utilizing the
quantile representation of a permutation test. This strategy leads to a
substantial power gain over the naive approach, while being finite-sample
valid. We present sufficient conditions for pointwise consistency (Theorem 3)
and non-asymptotic uniform power (Theorem 4) of the proposed tests. The latter
uniform power condition can be regarded as an extension of the two moments
method (Kim et al., 2022a, ) to private settings.

  * •

DP Kernel Tests (Section 4). We showcase the versatility of our framework by
applying it to two specific tasks: differentially private two-sample and
independence testing based on reproducing kernel-based test statistics. We
consider the plug-in estimators of the MMD and HSIC, and privatize them
through the proposed method employing the standard Laplace mechanism. The
practical performance of the resulting differentially private kernel tests
heavily depends on the global sensitivity used in the Laplace mechanism. To
boost the empirical performance, we put significant effort into establishing
sharp upper bounds for the global sensitivity of the plug-in estimators of MMD
and HSIC, as well as matching lower bounds for popular kernels (Lemma 5 and
Lemma 6). We then establish key properties of the proposed kernel tests,
including non-asymptotic validity and consistency against any fixed
alternatives in Theorem 5 and Theorem 6.

  * •

Uniform Power and Optimality (Section 5). We characterize the trade-off
between differential privacy and statistical power through the lens of minimax
analysis. To this end, we analyze the minimum separation required for the
differentially private MMD test to achieve significant power in terms of the
MMD metric. We derive an upper bound on this minimum separation in Theorem 7,
and a lower bound in Theorem 8, which matches in all relevant parameters
including testing error rates and privacy levels. Our minimax results suggest
that there is an unavoidable loss of power when the privacy parameter is
smaller than a certain threshold (_i.e._ , high privacy). On the other hand,
the privacy guarantee comes for free in terms of separation rate when the
privacy parameter exceeds this threshold (_i.e._ , low privacy). We also
derive the minimum separation in terms of the $L_{2}$ metric in Theorem 9 that
extends the prior work (Li and Yuan,, 2019; Schrab et al.,, 2023) on non-
private minimax testing to private settings. In Section B.5 and Section B.6,
we present analogous findings for the differentially private HSIC test, which
closely resemble the results obtained for the MMD test.

  * •

Negative Results of U-statistics (Section 5.3). We also derive perhaps
unexpected negative results of U-statistics in private settings. U-statistics
have played an important role, arguably more popular than V-statistics, in
deriving non-private minimax rates for various testing problems (Li and Yuan,,
2019; Albert et al.,, 2022; Kim et al., 2022a, ; Berrett et al.,, 2021; Schrab
et al.,, 2023). Given this trend, it is natural to consider U-statistics as an
initial building block for obtaining private minimax rates. However, it turns
out that the U-statistics suffer from higher global sensitivity than the
corresponding V-statistics, requiring a higher level of noise to effectively
privatize the resulting procedure. We formalize this observation in the
context of kernel testing and show that the private tests based on
U-statistics have sub-optimal power in high privacy regimes. This negative
result naturally justifies our approach based on the V-statistics
(equivalently, plug-in estimators) of the MMD and HSIC.

  * •

Empirical Validation (Section 6). A significant portion of the prior work on
differentially private testing has focused on theoretical aspects, often
lacking practical values. On the other hand, practical approaches to
differentially private testing frequently rely on heuristics without proper
theoretical validation. Our work serves a role in bridging the gap between
theory and practice by balancing both theoretical and practical aspects. In
particular, we highlight that our method is simple to use and comes with
strong theoretical guarantees as we demonstrate throughout the paper. The
empirical results in Section 6 and Appendix C also illustrate the competitive
performance of the proposed method across diverse scenarios, highlighting its
practical value.

We further make contributions by presenting asymptotic distributions of
privatized kernel statistics (Section B.1), general consistency results for
resampling-based tests (Section B.2) as well as other technical innovations
(Appendix G). We also introduce private kernel tests obtained through the
subsample-and-aggregate idea (Appendix D). Due to space constraints, we
relegate these additional results to the appendix.

###  1.3 Organization

The rest of this paper is organized as follows. We begin in Section 2 by
providing a brief overview of the fundamental concepts of differential
privacy. Section 3 presents our main proposal, namely the differentially
private permutation test, and investigates its finite-sample validity and
consistency in power. Moving forward to Section 4, we apply our proposed
permutation framework to specific scenarios, focusing on differentially
private kernel testing. In particular, we explore the privatization of kernel
MMD and HSIC tests, and delve into minimum separation rates of the resulting
tests in Section 5. To validate our theoretical findings, Section 6 presents
empirical evaluations of the proposed algorithms, comparing their performance
with existing methods. Finally, we conclude in Section 7 with a discussion
outlining potential directions for future work. All the proofs and additional
results are deferred to the appendix.

###  1.4 Notation

Given two datasets $\mathcal{X}_{n}\coloneqq(X_{1},\ldots,X_{n})$ and
$\tilde{\mathcal{X}}_{n}\coloneqq(\tilde{X}_{1},\ldots,\tilde{X}_{n})$, we
denote the Hamming distance between $\mathcal{X}_{n}$ and
$\tilde{\mathcal{X}}_{n}$ by
$d_{\mathrm{ham}}(\mathcal{X}_{n},\tilde{\mathcal{X}}_{n}):=\sum_{i=1}^{n}\mathds{1}(X_{i}\neq\tilde{X}_{i})$.
For two sequences of real numbers $a_{n},b_{n}$, we write $a_{n}\lesssim
b_{n}$ (and similarly $a_{n}\gtrsim b_{n}$) if there exists some positive
constant $C>0$ independent of $n$ such that $a_{n}\leq Cb_{n}$ for all $n\geq
1$. We also write $a_{n}\asymp b_{n}$ if $a_{n}\lesssim b_{n}$ and
$b_{n}\lesssim a_{n}$. For $x\in\mathbb{R}$, $\lfloor x\rfloor$ denotes the
largest integer smaller than or equal to $x$. For a natural number
$k\in\mathbb{N}$, we use $[k]$ to denote the set $\\{1,\ldots,k\\}$. We let
$\bm{\Pi}_{n}$ denote the set of all permutations of $[n]$. For a continuous
function $f:\mathbb{R}^{d}\mapsto\mathbb{R}$, the $L_{2}$ and $L_{\infty}$
norms of $f$ are given as
$\|f\|_{L_{2}}=\\{\int_{\mathbb{R}^{d}}f^{2}(\bm{x})\mathrm{d}\bm{x}\\}^{1/2}$
and $\|f\|_{L_{\infty}}=\sup_{\bm{x}\in\mathbb{R}^{d}}|f(\bm{x})|$,
respectively. We say $X\sim\mathsf{Laplace}(0,1)$ if $X$ follows a Laplace
distribution with local and scale parameters $(0,1)$. We often denote

$\displaystyle\xi_{\varepsilon,\delta}\coloneqq\varepsilon+\log\bigl{(}1/(1-\delta)\bigr{)}$
(1)

to simplify the notation in various places.

##  2 Background: Differential Privacy

This section presents a brief overview of the basic concepts and properties
regarding differential privacy. For a comprehensive treatment, we refer the
readers to Dwork et al., (2014). In our work, we adhere to the definition of
differential privacy (Dwork et al.,, 2014, page 25), allowing for the
inclusion of additional auxiliary variables. This extended definition requires
that the standard differential privacy condition holds for every possible
value of the auxiliary variable. In our permutation testing framework, we
treat random permutations as the auxiliary variables independent of the
dataset.

######  Definition 1 (Differential Privacy).

Consider a randomized algorithm $\mathcal{A}$, which takes as input a dataset
$\mathcal{X}_{n}$ and an additional auxiliary variable $w\in\mathcal{W}$. For
$\varepsilon>0$ and $\delta\in[0,1)$, the algorithm $\mathcal{A}$ is said to
be $(\varepsilon,\delta)$-differentially private if for (i) all
$S\in\mathrm{range}(\mathcal{A})$, (ii) all $w\in\mathcal{W}$ and (iii) all
two datasets $\mathcal{X}_{n}$ and $\tilde{\mathcal{X}}_{n}$ with
$d_{\mathrm{ham}}(\mathcal{X}_{n},\tilde{\mathcal{X}}_{n})\leq 1$, the
following inequality holds:

$\displaystyle\mathbb{P}\bigl{(}\mathcal{A}(\mathcal{X}_{n};w)\in
S\,|\,\mathcal{X}_{n},w\bigr{)}~{}\leq~{}e^{\varepsilon}\mathbb{P}\bigl{(}\mathcal{A}(\tilde{\mathcal{X}}_{n};w)\in
S\,|\,\tilde{\mathcal{X}}_{n},w\bigr{)}+\delta.$

We note that $(\varepsilon,0)$-differential privacy is often simply referred
to as $\varepsilon$-DP or pure-DP. On the other hand,
$(\varepsilon,\delta)$-differential privacy with $\delta\in(0,1)$ is referred
to as approximate-DP, considered as a relaxation of pure-DP. As mentioned by
Dwork et al., (2014, page 18), employing a large value of $\delta$ may lead to
serious privacy breaches, potentially exposing the complete information of a
small number of individuals with a non-trivial probability. Hence, it is
generally desirable to choose small values of $\delta$ such as
$\delta\lesssim\varepsilon^{2}n^{-1}$. Nevertheless, our interest lies in
exploring entire privacy regimes, and developing comprehensive results
applicable in a variety of settings. Consequently, we do not place
restrictions on privacy parameters other than $\varepsilon>0$ and
$\delta\in[0,1)$.

We collect several fundamental properties of differential privacy that are
useful in our contexts. The first property is called post-processing (Dwork et
al.,, 2014, Proposition 2.1), which asserts that any arbitrary post-processing
applied to the outcome of a differentially private algorithm preserves the
same level of privacy.

######  Lemma 1 (Post-Processing).

Suppose that an algorithm $\mathcal{A}$ is
$(\varepsilon,\delta)$-differentially private. Then for an arbitrary
randomized function $f$, the composition $f\circ\mathcal{A}$ also preserves
$(\varepsilon,\delta)$-differentially privacy.

Another important property of differential privacy, called the composition
theorem (Dwork et al.,, 2014, Theorem 3.16), presents the overall privacy
guarantee for a composition of multiple DP mechanisms.

######  Lemma 2 (Composition).

Suppose that each algorithm $\mathcal{A}_{i}$ is
$(\varepsilon,\delta)$-differentially private for $i\in[m]$. Then, the
composed algorithm $\mathcal{A}_{1:m}$ defined as
$\mathcal{A}_{1:m}\coloneqq(\mathcal{A}_{1},\dots,\mathcal{A}_{m})$ is
$(\sum_{i=1}^{m}\varepsilon_{i},\sum_{i=1}^{m}\delta_{i})$-differentially
private.

The definition of $(\varepsilon,\delta)$-DP immediately leads to the following
group property (Acharya et al.,, 2021, Lemma 19), which plays an important
role in constructing minimax lower bounds under DP.

######  Lemma 3 (Group Privacy).

Suppose that an algorithm $\mathcal{A}$ is
$(\varepsilon,\delta)$-differentially private. Then for (i) all
$S\in\mathrm{range}(\mathcal{A})$, (ii) all $w\in\mathcal{W}$, and (iii) all
two datasets $\mathcal{X}_{n}$ and $\tilde{\mathcal{X}}_{n}$ with
$d_{\mathrm{ham}}(\mathcal{X}_{n},\tilde{\mathcal{X}}_{n})\leq m$, the
following inequality holds:

$\displaystyle\mathbb{P}\bigl{(}\mathcal{A}(\mathcal{X}_{n};w)\in
S\,|\,\mathcal{X}_{n},w\bigr{)}~{}\leq~{}e^{m\varepsilon}\mathbb{P}\bigl{(}\mathcal{A}(\tilde{\mathcal{X}}_{n};w)\in
S\,|\,\tilde{\mathcal{X}}_{n},w\bigr{)}+me^{(m-1)\varepsilon}\delta.$ (2)

Several mechanisms have been developed to safeguard differential privacy, with
the Laplace mechanism (Dwork et al., 2006b, ) standing out as one of the most
commonly used approaches. To formally state the Laplace mechanism, we first
describe the global sensitivity, which is a keystone in the differential
privacy framework. We stress that the definition presented below allows us to
take into account an additional auxiliary variable $w$, and thus it is more
general than the definition commonly encountered in the DP literature, such as
in Dwork et al., 2006b .

######  Definition 2 (Global $\ell_{p}$-Sensitivity).

Consider a function $f$ taking as input a dataset $\mathcal{X}_{n}$ and an
additional auxiliary variable $w\in\mathcal{W}$, and assume that the output of
$f$ lies in $\mathbb{R}^{r}$. For $p\geq 1$, the global $\ell_{p}$-sensitivity
of $f$ is defined as

$\Delta_{\\!f}^{p}~{}\coloneqq~{}\sup_{w\in\mathcal{W}}\sup_{\begin{subarray}{c}\mathcal{X}_{n},\tilde{\mathcal{X}}_{n}:\\\
d_{\mathrm{ham}}(\mathcal{X}_{n},\tilde{\mathcal{X}}_{n})\leq
1\end{subarray}}\big{\|}f(\mathcal{X}_{n};w)-f(\tilde{\mathcal{X}}_{n};w)\big{\|}_{p},$

where $\|x\|_{p}$ denotes the $\ell_{p}$ norm of a vector $x$.

The Laplace mechanism works with the $\ell_{1}$-sensitivity, which determines
the scaling factor of the Laplace noise injected into the outputs of the
function. Formally, the Laplace mechanism is given as follows.

######  Definition 3 (Laplace Mechanism).

Consider a function $f$ with the $\ell_{1}$-sensitivity $\Delta_{f}^{1}$
described in Definition 2. For a given privacy parameter $\xi>0$, the Laplace
mechanism is defined as the random function:

$\mathcal{M}_{\\!f}^{\xi}(\mathcal{X}_{n};w)\coloneqq
f(\mathcal{X}_{n};w)+\frac{\Delta_{\\!f}^{1}}{\xi}(\zeta_{1},\dots,\zeta_{r})^{\top},$

where
$\zeta_{1},\dots,\zeta_{r}\overset{\mathrm{i.i.d.}}{\sim}\mathsf{Laplace}(0,1)$
generated independent of $\mathcal{X}_{n}$ and $w$.

The privacy guarantee of the Laplace mechanism depends crucially on the choice
of privacy parameter $\xi$. It is well-known that the Laplace mechanism is
$(\varepsilon,0)$-DP when $\xi=\varepsilon$ (Dwork et al.,, 2014, Theorem
3.6). In general, Acharya et al., (2018, Lemma 5) shows that any
$(\varepsilon+\delta,0)$-DP algorithm is also $(\varepsilon,\delta)$-DP. While
this strategy is effective for small values of $\delta$, it returns a
suboptimal result when $\delta$ is close to one. Concretely, when $\delta$
approaches one, we are entering the non-private regime where adding noise is
unnecessary. However, the Laplace mechanism with $\xi=\varepsilon+\delta$
injects a non-negligible amount of noise to the algorithm. The refined
calibration result proposed by Holohan et al., (2015) avoids such issue,
proving that $\mathcal{M}_{\\!f}^{\xi_{\varepsilon,\delta}}$ with
$\xi_{\varepsilon,\delta}=\varepsilon+\log(1/(1-\delta))$ is also
$(\varepsilon,\delta)$-DP. We record this guarantee in the following lemma.

######  Lemma 4 (Differential Privacy of Laplace Mechanism).

Let $\varepsilon>0$ and $\delta\in[0,1)$. The Laplace mechanism
$\mathcal{M}_{\\!f}^{\xi_{\varepsilon,\delta}}$ in Definition 3 with
$\xi_{\varepsilon,\delta}=\varepsilon+\log\bigl{(}1/(1-\delta)\bigr{)}$ is
$(\varepsilon,\delta)$-differentially private.

It is worth noting that Holohan et al., (2015) consider typical differential
privacy without considering an auxiliary variable $w$. Nevertheless, the same
proof can be applied to differential privacy involving auxiliary variables,
provided that we consider the global sensitivity holding uniformly over
$w\in\mathcal{W}$ as in Definition 2.

######  Remark 1 (Gaussian Mechanism).

For $(\varepsilon,\delta)$-DP, one can also consider the Gaussian mechanism
with the $\ell_{2}$-sensitivity, another common method for preserving privacy
(Dwork et al., 2006b, ; Dwork et al.,, 2014). The Gaussian mechanism can be
beneficial over the Laplace mechanism when the $\ell_{2}$-sensitivity is
significantly smaller than the $\ell_{1}$-sensitivity. However, such benefit
is not immediately clear when the outcome of $f$ is one-dimensional where the
$\ell_{p}$ sensitivity remains the same for any $p\geq 1$. As our framework is
mainly concerned with one-dimensional numeric outcomes, we simply focus on the
Laplace mechanism and refer to the _global $\ell_{1}$-sensitivity_ as the
_global sensitivity_ whenever it is clear from the context, and simply denote
it by $\Delta_{f}$.

##  3 Differentially Private Permutation Tests

In this section, we introduce a general framework for constructing a
differentially private permutation test. To begin, consider a class of
distributions $\mathcal{P}$, which is formed by the union of two disjoint
subclasses: $\mathcal{P}_{0}$ and $\mathcal{P}_{1}$. Suppose that we observe a
random sample $\mathcal{X}_{n}$ of size $n$ drawn from $P\in\mathcal{P}$.
Given $\mathcal{X}_{n}$, our ultimate goal is to test whether
$H_{0}:P\in\mathcal{P}_{0}$ or $H_{1}:P\in\mathcal{P}_{1}$, while preserving
differential privacy. Consider a test statistic
$T:\mathcal{X}_{n}\mapsto\mathbb{R}$, which is assumed to take a large value
under the alternative hypothesis $H_{1}$. To build on the permutation
principle (Lehmann and Romano,, 2005, Chapter 15.2), we make the assumption
that $\mathcal{X}_{n}$ is exchangeable under the null $H_{0}$. That is, for
any permutation $\bm{\pi}\coloneqq(\pi_{1},\ldots,\pi_{n})\in\bm{\Pi}_{n}$,
the joint distribution of $\mathcal{X}_{n}$ is the same as that of
$\mathcal{X}_{n}^{\bm{\pi}}\coloneqq(X_{\pi_{1}},\ldots,X_{\pi_{n}})$. Under
the exchangeability assumption, the permutation test rejects the null when $T$
is significantly larger than the permuted counterparts. More formally, let
$\bm{\pi}_{1},\ldots,\bm{\pi}_{B}$ be i.i.d. random permutations of $[n]$, and
denote by
$T(\mathcal{X}_{n}^{\bm{\pi}_{1}}),\ldots,T(\mathcal{X}_{n}^{\bm{\pi}_{B}})$,
the test statistics computed based on
$\mathcal{X}_{n}^{\bm{\pi}_{1}},\ldots,\mathcal{X}_{n}^{\bm{\pi}_{B}}$,
respectively. The (Monte Carlo) permutation test then rejects the null
hypothesis when the permutation $p$-value is less than or equal to
significance level $\alpha$, _i.e._ ,

$\displaystyle\widehat{p}\coloneqq\frac{1}{B+1}\bigg{\\{}\sum_{i=1}^{B}\mathds{1}\bigl{(}T(\mathcal{X}_{n}^{\bm{\pi}_{i}})\geq
T(\mathcal{X}_{n})\bigr{)}+1\bigg{\\}}\leq\alpha.$ (3)

It is well-known that $\widehat{p}$ is super-uniform, _i.e._ ,
$\mathbb{P}(\widehat{p}\leq t)\leq t$ for all $t\in[0,1]$, under
exchangeability of $\mathcal{X}_{n}$ (_e.g._ , Lemma 15). Therefore the
permutation test $\mathds{1}(\widehat{p}\leq\alpha)$ controls the type I error
for any finite sample size $n$. Our aim is to privatize the permutation test
under the DP constraint, while maintaining finite-sample validity and
achieving competitive (potentially optimal) power.

For notational convenience, we often write $T_{0}=T(\mathcal{X}_{n})$ and
$T_{i}=T(\mathcal{X}_{n}^{\bm{\pi}_{i}})$ for $i\in[B]$, and set
$\bm{\pi}_{0}=(1,2,\ldots,n)$ in what follows.

###  3.1 Proposed Privatization Method

To describe the proposed method, suppose that the test statistic $T$ has the
global sensitivity (Definition 2) with the permutation $\bm{\pi}$ as an
auxiliary variable:

$\displaystyle\Delta_{T}\coloneqq\sup_{\bm{\pi}\in\bm{\Pi}_{n}}\sup_{\begin{subarray}{c}\mathcal{X}_{n},\tilde{\mathcal{X}}_{n}:\\\
d_{\mathrm{ham}}(\mathcal{X}_{n},\tilde{\mathcal{X}}_{n})\leq
1\end{subarray}}\big{|}T(\mathcal{X}_{n}^{\bm{\pi}})-T(\tilde{\mathcal{X}}_{n}^{\bm{\pi}})\big{|}.$
(4)

Our tailored definition of global sensitivity to permutation tests above is
stronger than the usual one since it measures the sensitivity over all
possible permutations. However, this additional requirement is not overly
restrictive as we demonstrate below for integral probability metrics.

######  Example 1 (Sensitivity of Integral Probability Metric).

Consider a two-sample setting where we observe random variables
$\mathcal{Y}_{n}=\\{Y_{1},\ldots,Y_{n}\\}$ and
$\mathcal{Z}_{m}=\\{Z_{1},\ldots,Z_{m}\\}$, each supported on $\mathbb{S}$.
Let $\mathcal{F}$ be a class of real-valued functions on $\mathbb{S}$. A plug-
in estimator of the corresponding integral probability metric (IPM) is given
as

$\displaystyle
T=\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}f(Y_{i})-\frac{1}{m}\sum_{i=1}^{m}f(Z_{i})\bigg{|}.$
(5)

As detailed in Section B.3, the global sensitivity of $T$ is precisely equal
to

$\displaystyle\Delta_{T}=\frac{1}{\min\\{n,m\\}}\sup_{X,X^{\prime}\in\mathbb{S}}\sup_{f\in\mathcal{F}}|f(X)-f(X^{\prime})|.$

The IPM includes several metrics commonly used in the literature
(Sriperumbudur et al.,, 2012) and their sensitivity can be analyzed as
follows.

  1. (a)

_Mean difference in $\ell_{p}$_: Let $\mathbb{S}\subset\mathbb{R}^{d}$, and
set $1\leq p,q\leq\infty$ such that $1/p+1/q=1$. Choosing
$\mathcal{F}=\\{f:\mathbb{S}\mapsto\mathbb{R}\,|\,f(x)=a^{\top}x,\|a\|_{q}\leq
1\\}$, the IPM becomes the $p$th norm of the sample mean difference between
$\mathcal{Y}_{n}$ and $\mathcal{Z}_{m}$. In this case, we have
$\sup_{X,X^{\prime}\in\mathbb{S}}\sup_{f\in\mathcal{F}}|f(X)-f(X^{\prime})|=\sup_{X,X^{\prime}\in\mathbb{S}}\|X-X^{\prime}\|_{p}$.

  2. (b)

_Wasserstein distance_ : When
$\mathcal{F}=\\{f:\mathbb{S}\mapsto\mathbb{R}\,|\,\|f\|_{\mathrm{Lip}}\leq
1\\}$ where $\|f\|_{\mathrm{Lip}}$ denotes the minimal Lipschitz constant for
$f$ on a metric space $(\mathbb{S},\|\cdot\|)$, the IPM corresponds to the
Wasserstein 1-distance. By the Lipschitz property of $f$, we have
$\sup_{X,X^{\prime}\in\mathbb{S}}\sup_{f\in\mathcal{F}}|f(X)-f(X^{\prime})|\leq\sup_{X,X^{\prime}\in\mathbb{S}}\|X-X^{\prime}\|$.

  3. (c)

_Total variation distance_ : Let
$\mathcal{F}=\\{f:\mathbb{S}\mapsto\mathbb{R}\,|\,\sup_{x\in\mathbb{S}}|f(x)|\leq
1\\}$. The corresponding IPM is the total variation distance for which we have
$\sup_{X,X^{\prime}\in\mathbb{S}}\sup_{f\in\mathcal{F}}|f(X)-f(X^{\prime})|\leq
2$.

  4. (d)

_Kolmogorov distance_ : When
$\mathcal{F}=\\{\mathds{1}(-\infty,x]:x\in\mathbb{R}^{d}\\}$, the IPM is
called the Kolmogorov distance. In this case, we have
$\sup_{X,X^{\prime}\in\mathbb{S}}\sup_{f\in\mathcal{F}}|f(X)-f(X^{\prime})|\leq
1$ with $\mathbb{S}=\mathbb{R}^{d}$.

  5. (e)

_Maximum mean discrepancy_ : Let $\|f\|_{\mathcal{H}_{k}}$ be the norm of a
function $f$ in a reproducing kernel Hilbert space $\mathcal{H}_{k}$ equipped
with kernel $k$. When
$\mathcal{F}=\\{f:\mathbb{S}\mapsto\mathbb{R}\,|\,\|f\|_{\mathcal{H}_{k}}\leq
1\\}$, the IPM corresponds to the maximum mean discrepancy and it satisfies
that
$\sup_{X,X^{\prime}\in\mathbb{S}}\sup_{f\in\mathcal{F}}|f(X)-f(X^{\prime})|\leq\sqrt{2K}$
where $K$ is the maximum value of a non-negative kernel $k$. See Lemma 5 for
details.

In general, obtaining the exact value of the global sensitivity $\Delta_{T}$
can be challenging, and thus we often work with an upper bound for
$\Delta_{T}$. We remark that the differential privacy guarantee of the Laplace
mechanism in Lemma 4 remains valid when we replace the sensitivity in the
Laplace mechanism with any upper bound. With an abuse of notation, we also use
$\Delta_{T}$ to denote an upper bound for the global sensitivity, when the
exact value of the global sensitivity is not available.

##### Naive Approach.

Given the global sensitivity of $T$, one naive attempt to privatize the
permutation test is to apply the basic composition theorem (Lemma 2). To
depict the idea, let $\\{\zeta_{i}\\}_{i=0}^{B}$ be a sequence of i.i.d.
$\mathsf{Laplace}(0,1)$ random variables, and define

$\displaystyle\widetilde{M}_{i}\coloneqq
T_{i}+\frac{\Delta_{T}}{\varepsilon(B+1)^{-1}+\log\bigl{(}1/\\{1-\delta(B+1)^{-1}\\}\bigr{)}}\zeta_{i},\quad\text{for
$i\in\\{0\\}\cup[B]$.}$

By the Laplace mechanism, each $\widetilde{M}_{i}$ is
$\big{(}\varepsilon/(B+1),\delta/(B+1)\big{)}$-DP and the composition theorem
in Lemma 2 then ensures that the permutation $p$-value given as

$\displaystyle\widehat{p}_{\mathrm{dp}}^{\,\mathrm{naive}}\coloneqq\frac{1}{B+1}\bigg{\\{}\sum_{i=1}^{B}\mathds{1}\bigl{(}\widetilde{M}_{i}\geq\widetilde{M}_{0}\bigr{)}+1\bigg{\\}}$
(6)

is $(\varepsilon,\delta)$-DP. Moreover, $\\{\widetilde{M}_{i}\\}_{i=0}^{B}$
are exchangeable under the null, which in turn yields that
$\widehat{p}_{\mathrm{dp}}^{\,\mathrm{naive}}$ is a valid $p$-value by Lemma
15. While this naive approach returns rigorous guarantees on both privacy and
validity, it has room for improvement in regard to the power performance.
Observe that the noise level grows linearly in the number of permutations $B$.
This means that the Laplace noise overwhelms the signal when $B$ is
significantly large, leading to a loss of power. It is also worth noting that
the permutation $p$-value is lower bounded by $(B+1)^{-1}$. This means that in
order to have non-zero power, the number of permutations $B$ must be greater
than $\alpha^{-1}-1$. Hence, one cannot take $B$ to be arbitrarily small. This
issue serves as the motivation for our proposal, which is described below.

##### Refined Approach.

The factor of $B+1$ arises from an application of the composition theorem
(Lemma 2), which cannot be improved in general (_e.g._ , Section 2.1 of
Steinke,, 2022). As one of our key contributions, we remove this unpleasant
dependence on $B$ via the quantile representation of the permutation test
(Lemma 17). To describe our proposal, define

$\displaystyle M_{i}\coloneqq
T_{i}+\frac{2\Delta_{T}}{\xi_{\varepsilon,\delta}}\zeta_{i},$

for $i\in\\{0\\}\cup[B]$, where $\xi_{\varepsilon,\delta}$ can be recalled in
(1). Notably, the noise level $2\Delta_{T}\xi_{\varepsilon,\delta}^{-1}$ is
independent of $B$ and strictly smaller than that of the naive approach for
any $B>1$. Given $\\{M_{i}\\}_{i=0}^{B}$, we define the private permutation
$p$-value as

$\displaystyle\widehat{p}_{\mathrm{dp}}\coloneqq\frac{1}{B+1}\bigg{\\{}\sum_{i=1}^{B}\mathds{1}\bigl{(}M_{i}\geq
M_{0}\bigr{)}+1\bigg{\\}},$ (7)

and reject the null when $\widehat{p}_{\mathrm{dp}}\leq\alpha$. We summarize
the proposed method in Algorithm 1.

Algorithm 1 Differentially Private Permutation Test

Input: Data $\mathcal{X}_{n}$, significance level $\alpha\in(0,1)$, privacy
parameters $\varepsilon>0$ and $\delta\in[0,1)$, test statistic $T$, global
sensitivity (or its upper bound) $\Delta_{T}$, number of permutations
$B\in\mathbb{N}$.
For $i\in[B]$ do

Generate a random permutation $\bm{\pi}_{i}$ of $[n]$.

Generate $\zeta_{i}\sim\mathsf{Laplace}(0,1)$.

Set $M_{i}\leftarrow
T(\mathcal{X}_{n}^{\bm{\pi}_{i}})+2\Delta_{T}\xi_{\varepsilon,\delta}^{-1}\zeta_{i}$
where $\xi_{\varepsilon,\delta}\coloneqq\varepsilon+\log(1/(1-\delta))$.

End For

Generate $\zeta_{0}\sim\mathsf{Laplace}(0,1)$ and set $M_{0}\leftarrow
T(\mathcal{X}_{n})+2\Delta_{T}\xi_{\varepsilon,\delta}^{-1}\zeta_{0}$.

Compute the permutation $p$-value $\widehat{p}_{\mathrm{dp}}$ as in (7).

Output: Reject $H_{0}$ if $\widehat{p}_{\mathrm{dp}}\leq\alpha$.

###  3.2 Validity and Privacy Guarantee

Having introduced our method, we next investigate its theoretical guarantees
and provide intuition behind our proposal. We start with the validity of the
private test, which follows immediately from Lemma 15.

######  Theorem 1 (Validity Guarantee).

Suppose that $\mathcal{X}_{n}$ are exchangeable under the null
$H_{0}:P\in\mathcal{P}_{0}$. Then for any $\alpha\in(0,1)$ and $B,n\geq 1$,
the type I error of the test $\mathds{1}(\widehat{p}_{\mathrm{dp}}\leq\alpha)$
from Algorithm 1 satisfies

$\displaystyle\sup_{P\in\mathcal{P}_{0}}\mathbb{P}_{P}(\widehat{p}_{\mathrm{dp}}\leq\alpha)=\frac{\lfloor(B+1)\alpha\rfloor}{B+1}\leq\alpha.$

It is worth emphasizing that type I error control of the proposed test is both
non-asymptotic and uniform over the entire class of null distributions
$\mathcal{P}_{0}$. Another distinct feature is that the type I error is equal
to ${\lfloor(B+1)\alpha\rfloor}/{(B+1)}$, which can be strictly smaller than
$\alpha$. If this small gap is a concern, one can make the type I error
exactly equal to $\alpha$ through randomization (Lemma 16). We also remark
that even if we replace the global sensitivity $\Delta_{T}$ in the procedure
with any other value, type I error control remains valid. In other words, the
validity of the proposed test is not affected by the noise level of the
Laplace mechanism.

Next we turn to the privacy guarantee of the proposed test and show that it is
$(\varepsilon,\delta)$-DP.

######  Theorem 2 (Privacy Guarantee).

For any $\alpha\in(0,1)$, the permutation test
$\mathds{1}(\widehat{p}_{\mathrm{dp}}\leq\alpha)$ from Algorithm 1 is
$(\varepsilon,\delta)$-differentially private.

It is worth highlighting that the privacy guarantee does not require the
exchangeability of $\mathcal{X}_{n}$. Hence the proposed test is
$(\varepsilon,\delta)$-DP under both the null and the alternative. As
mentioned before, we prove the privacy guarantee of the proposed test via the
quantile representation of the permutation test (Lemma 17). That is, rejecting
the null when $\widehat{p}\leq\alpha$ where $\widehat{p}$ is given in (3) is
equivalent to rejecting the null when $T_{0}>Q_{1-\alpha}$ where
$Q_{1-\alpha}$ is the $1-\alpha$ quantile of $\\{T_{i}\\}_{i=0}^{B}$. Roughly
speaking, our proof proceeds by privatizing $T_{0}$ and $Q_{1-\alpha}$,
separately, which raises the factor of $2$ in
$2\Delta_{T}\xi_{\varepsilon,\delta}^{-1}$. However, a direct application of
the Laplace mechanism to $T_{0}$ and $Q_{1-\alpha}$ destroys the
exchangeability of random variables, thereby type I error control is no longer
guaranteed. Making both $T_{0}$ and $Q_{1-\alpha}$ private while ensuring the
finite-sample validity of the resulting test is non-trivial, and thus we
highlight it as our main contribution. Along the way, we develop a general
sensitivity result of quantiles in Lemma 19, which may be of independent
interest. We also point out that the factor of $2$ in the noise level is a
price to pay for not knowing the null distribution of $T$. When $T$ is
distribution-free under the null, then it is possible to sharpen the constant
factor from two to one.

###  3.3 Power Analysis

Moving our focus to the power property, we aim to provide tractable conditions
for pointwise consistency and non-asymptotic uniform power. Starting with
pointwise consistency, the following result provides conditions under which
the power converges to one as the sample size increases against a fixed
alternative. Below, we add the subscript $n$ to $B_{n}$ to indicate that the
number of permutations can vary with the sample size.

######  Theorem 3 (Pointwise Consistency).

Let $\alpha\in(0,1)$ be a fixed constant. For a given alternative distribution
$P$, suppose that $\lim_{n\rightarrow\infty}\mathbb{P}_{P}(M_{0}\leq
M_{1})=0$. Then for any positive sequence of $B_{n}$ such that $\min_{n\geq
1}B_{n}+1>\alpha^{-1}$, the differentially private permutation test is
consistent in power as
$\lim_{n\rightarrow\infty}\mathbb{P}_{P}(\widehat{p}_{\mathrm{dp}}\leq\alpha)=1$.

In view of the above result, proving consistency of the permutation test
essentially boils down to verifying the condition $M_{0}>M_{1}$, _i.e._ , the
original statistic is greater than a permuted statistic, with probability
approaching one. In Section 4, we showcase the consistency results based on
kernel-based methods for two-sample and independence testing. We note that
Theorem 3 can be proven in a straightforward manner via a union bound when
$B_{n}$ is fixed. A similar result for fixed $B_{n}$ can be found in Dobriban,
(2022, Lemma 5.2) and Rindt et al., (2021, Theorem 6). Extending this result
to any arbitrary sequence of $B_{n}$ requires a different technique that
exploits the conditional i.i.d. structure of given variables. To broaden the
scope of our paper, we develop a consistency result for general resampling-
based tests in Lemma 8 of Section B.2, from which we can derive Theorem 3 as a
corollary.

While pointwise consistency is a useful property, it is often regarded as a
relatively weak guarantee. We now shift our focus to the second result of this
subsection, providing a non-asymptotic, uniform guarantee on the power under
stronger assumptions. In particular, we identify the moment conditions under
which the proposed test has significant power. These conditions can be
regarded as the private extension of Kim et al., 2022a (, Lemma 3.1). Below,
the symbols $\mathbb{E}_{P,\bm{\pi}}$ and $\mathrm{Var}_{P,\bm{\pi}}$ denote
the expectation and the variance, respectively, taken over both
$\mathcal{X}_{n}$ and $\bm{\pi}$.

######  Theorem 4 (Uniform Power).

For $\alpha\in(0,1)$, $\beta\in(0,1-\alpha)$ and $\xi_{\varepsilon,\delta}>0$,
assume that $B\geq 16\alpha^{-2}\log(8/\beta)$ and for any
$P\in\mathcal{P}_{1}$,

$\displaystyle\mathbb{E}_{P}[T(\mathcal{X}_{n})]-\mathbb{E}_{P,\bm{\pi}}[T(\mathcal{X}_{n}^{\bm{\pi}})]~{}\geq{}$
$\displaystyle
C_{1}\sqrt{\frac{\mathrm{Var}_{P}[T(\mathcal{X}_{n})]+\mathrm{Var}_{P,\bm{\pi}}[T(\mathcal{X}_{n}^{\bm{\pi}})]}{\alpha\beta}}$
(8) $\displaystyle+{}$ $\displaystyle
C_{2}\frac{\Delta_{T}}{\xi_{\varepsilon,\delta}}\max\bigg{\\{}\\!\log\biggl{(}\frac{1}{\alpha}\biggr{)},\,\log\biggl{(}\frac{1}{\beta}\biggr{)}\bigg{\\}},$

where $C_{1}$ and $C_{2}$ are universal constants. Then the uniform power of
the private permutation test is bounded below by $1-\beta$ as

$\displaystyle\inf_{P\in\mathcal{P}_{1}}\mathbb{P}_{P}(\widehat{p}_{\mathrm{dp}}\leq\alpha)\geq
1-\beta.$

A few remarks are in order.

  * •

The above theorem ensures that the private permutation test has significant
power as long as the signal of the problem, namely the difference between the
expected values of the original test statistic and of the permuted test
statistic, is larger than the noise of the problem, namely the square root of
the variances and the noise level of the Laplace mechanism.

  * •

The proof of Theorem 4, given in Section E.2, builds on the proof of Kim et
al., 2022a (, Lemma 3.1) where the key idea is to replace the random
permutation threshold with a deterministic one using concentration
inequalities. The main distinction from Kim et al., 2022a  is the
incorporation of Laplace noises in the analysis, which results in the second
line of the condition (8). We also note that Theorem 4 concerns the Monte
Carlo permutation test, which is computationally more efficient than the full
permutation test analyzed in Kim et al., 2022a (, Lemma 3.1).

  * •

Notably, the condition on $B$ is independent of the sample size, which is a
consequence of the Dvoretzky–Kiefer–Wolfowitz (DKW) inequality (Massart,,
1990), and similar conditions can be found in Schrab et al., (2023) and Schrab
et al., (2022). One can improve this restriction, especially constant factors,
with more technical effort or by using other techniques, such as the one based
on order statistics (Domingo-Enrich et al.,, 2023, Lemma 6).

  * •

It is worth mentioning that the first line of the condition (8) relies on a
polynomial dependence on $\alpha$ and $\beta$, which arise from the
application of Chebyshev’s and Markov’s inequalities. If the considered test
statistic has an exponential tail bound, these polynomial factors can be
improved to logarithmic ones as we illustrate in Section 5.

Before moving on, let us briefly illustrate Theorem 4 based on the plug-in IPM
statistic considered in Example 1.

######  Example 2 (Power Analysis against IPM alternatives).

Continuing our discussion from Example 1, denote the IPM between $P$ and $Q$
with a class of functions $\mathcal{F}$ as

$\displaystyle\mathrm{IPM}_{\mathcal{F}}(P,Q)=\sup_{f\in\mathcal{F}}\big{|}\mathbb{E}_{P}[f(Y)]-\mathbb{E}_{Q}[f(Z)]\big{|}.$

Without loss of generality, assume $n\leq m$ and write the pooled sample as
$\mathcal{X}_{n+m}=\mathcal{Y}_{n}\cup\mathcal{Z}_{m}=\\{X_{1},\ldots,X_{n+m}\\}$.
Consider the maximum Rademacher complexity of $\mathcal{F}$ over all possible
permuted samples given as

$\displaystyle\mathcal{R}_{n}(\mathcal{F})=\sup_{\bm{\pi}\in\bm{\Pi}_{n+m}}\mathbb{E}\biggl{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\omega_{i}f(X_{\pi_{i}})\bigg{|}\biggr{]},$

where $\\{\omega_{i}\\}_{i=1}^{n}$ are i.i.d. Rademacher random variables
independent of $\mathcal{X}_{n+m}$. Suppose that we implement Algorithm 1
using the plug-in IPM estimator $T(\mathcal{X}_{n+m})$ in (5). Then Theorem 4
yields that the resulting permutation test has the power greater than
$1-\beta$ if

$\displaystyle\mathrm{IPM}_{\mathcal{F}}(P,Q)\geq
C_{1}\frac{\mathcal{R}_{n}(\mathcal{F})}{\sqrt{\alpha\beta}}+C_{2}\frac{\sqrt{n}\Delta_{T}}{\sqrt{\alpha\beta}}+C_{3}\frac{\Delta_{T}}{\xi_{\varepsilon,\delta}}\max\bigg{\\{}\\!\log\biggl{(}\frac{1}{\alpha}\biggr{)},\,\log\biggl{(}\frac{1}{\beta}\biggr{)}\bigg{\\}},$

where $C_{1},C_{2},C_{3}$ are some positive constants. We defer a detailed
analysis that leads to the above result to Section B.4. We also refer to van
der Vaart and Wellner, (1996); Bartlett and Mendelson, (2002); Wainwright,
(2019) for additional information on the Rademacher complexity and
illustrative examples.

So far we have examined the properties of the private permutation test in a
general context. In the next section, we will apply our framework to the
specific problem of kernel testing, and provide a detailed analysis.

##  4 Application: Differentially Private Kernel Tests

In recent years, there has been a growing trend in employing kernel-based
methods for hypothesis testing problems, such as the MMD and the HSIC. This
popularity is partly due to their ability to capture complex, non-linear
relationships and to their straightforward implementation. Equipped with such
benefits, the MMD (Gretton et al.,, 2012) is used to measure the difference
between two probability distributions, while the HSIC (Gretton et al.,, 2005)
is used to quantify the dependence between two random variables. In this and
subsequent sections, we propose differentially private tests based on these
two kernel-based measures, and provide an in-depth analysis of their
theoretical properties.

##### Terminology.

Before we begin, let us establish the terminology related to kernels. Consider
a reproducing kernel $k:\mathbb{S}\times\mathbb{S}\mapsto\mathbb{R}$ defined
on a separable topological space $\mathbb{S}$. Let $\mathcal{H}_{k}$ be a
reproducing kernel Hilbert space (RKHS) endowed with kernel $k$. A kernel $k$
is said to be _characteristic_ if the kernel mean embedding

$\displaystyle\mu_{P}=\int_{\mathbb{S}}k(\cdot,x)\mathrm{d}P(x)\in\mathcal{H}_{k}$

is injective. In addition, a kernel
$k:\mathbb{S}\times\mathbb{S}\mapsto\mathbb{R}$ is said to be _translation
invariant_ if there exists a symmetric positive definite function $\kappa$
such that $k(x,y)=\kappa(x-y)$ for all $x,y\in\mathbb{S}$. Assuming that
$0\leq k(x,y)\leq K$ for all $x,y\in\mathbb{S}$, we say that the kernel $k$
has _non-empty level sets_ on $\mathbb{S}$ if, for any $\epsilon\in(0,K)$,
there exist $x,y\in\mathbb{S}$, such that $k(x,y)\leq\epsilon$. Some popular
examples of kernels include the Gaussian kernel
$k(x,y)=e^{-\sigma\|x-y\|_{2}^{2}}$ and the Laplacian kernel
$k(x,y)=e^{-\sigma\|x-y\|_{1}}$ for $\sigma>0$. These two kernels are
translation invariant and known to be characteristic on $\mathbb{R}^{d}$
(_e.g._ , Sriperumbudur et al.,, 2011). They also have non-empty level sets on
$\mathbb{R}^{d}$, which can be deduced from the continuity of the kernel
function.

###  4.1 Differentially Private MMD Test

Starting with the MMD, suppose we are given mutually independent samples
$\mathcal{Y}_{n}\coloneqq\\{Y_{1},\ldots,Y_{n}\\}\overset{\mathrm{i.i.d.}}{\sim}P$
and
$\mathcal{Z}_{m}\coloneqq\\{Z_{1},\ldots,Z_{m}\\}\overset{\mathrm{i.i.d.}}{\sim}Q$
on a domain $\mathbb{S}$. Without loss of generality, assume $n\leq m$
throughout the rest of this paper. Based on these samples, the two-sample
problem aims to determine whether two probability distributions $P$ and $Q$
coincide. A majority of two-sample methodologies target a certain metric
between $P$ and $Q$, and use their empirical counterpart as a test statistic.
One such method is the non-private MMD test (Gretton et al.,, 2012) where the
difference between $P$ and $Q$ is quantified in terms of MMD. To elaborate,
consider the unit ball in a RKHS $\mathcal{H}_{k}$ denoted by
$\mathcal{F}_{k}\coloneqq\\{f\in\mathcal{H}_{k}:\|f\|_{\mathcal{H}_{k}}\leq
1\\}$. The maximum mean discrepancy between $P$ and $Q$ is defined as

$\displaystyle\mathrm{MMD}_{k}(P,Q)\coloneqq\sup_{f\in\mathcal{F}_{k}}\bigl{\\{}\mathbb{E}_{P}[f(Y)]-\mathbb{E}_{Q}[f(Z)]\bigr{\\}}.$

The empirical MMD is a plug-in estimator of MMD that replaces $P$ and $Q$ with
the corresponding empirical probability measures. Formally, letting
$\mathcal{X}_{n+m}=\mathcal{Y}_{n}\cup\mathcal{Z}_{m}$ be the pooled sample as
before, the empirical MMD is given as

$\displaystyle\widehat{\mathrm{MMD}}(\mathcal{X}_{n+m})\coloneqq\sup_{f\in\mathcal{F}_{k}}\biggl{\\{}\frac{1}{n}\sum_{i=1}^{n}f(Y_{i})-\frac{1}{m}\sum_{j=1}^{m}f(Z_{i})\biggr{\\}}.$
(9)

Thanks to the reproducing kernel property, the empirical MMD can be computed
straightforwardly. In particular, the squared empirical MMD can be calculated
in quadratic time using the kernel-based expression

$\displaystyle\widehat{\mathrm{MMD}}^{2}(\mathcal{X}_{n+m})=\frac{1}{n^{2}}\sum_{i,j=1}^{n}k(Y_{i},Y_{j})+\frac{1}{m^{2}}\sum_{i,j=1}^{m}k(Z_{i},Z_{j})-\frac{2}{nm}\sum_{i=1}^{n}\sum_{j=1}^{m}k(Y_{i},Z_{j}).$
(10)

In order to propose a private version of the MMD test, we begin with the
global sensitivity of the empirical MMD.

######  Lemma 5 (Sensitivity of Empirical MMD).

Assume that the kernel $k$ is bounded as $0\leq k(x,y)\leq K$ for all
$x,y\in\mathbb{S}$. Then the global sensitivity of the empirical MMD satisfies

$\displaystyle\sup_{\bm{\pi}\in\bm{\Pi}_{n+m}}\sup_{\begin{subarray}{c}\mathcal{X}_{n+m},\tilde{\mathcal{X}}_{n+m}:\\\
d_{\mathrm{ham}}(\mathcal{X}_{n+m},\tilde{\mathcal{X}}_{n+m})\leq
1\end{subarray}}\bigl{|}\widehat{\mathrm{MMD}}(\mathcal{X}_{n+m}^{\bm{\pi}})-\widehat{\mathrm{MMD}}(\tilde{\mathcal{X}}_{n+m}^{\bm{\pi}})\bigr{|}\leq\frac{\sqrt{2K}}{n}.$

Moreover assume that $k$ is translation invariant, and has non-empty level
sets in $\mathbb{S}$. Then the inequality becomes an equality.

The proof of Lemma 5 can be found in Section E.5. Note that the sensitivity of
the empirical MMD in Lemma 5 can be equivalently defined without the supremum
over the permutations $\bm{\pi}\in\bm{\Pi}_{n+m}$ as
$d_{\mathrm{ham}}(\mathcal{X}_{n+m},\tilde{\mathcal{X}}_{n+m})$ is the same as
$d_{\mathrm{ham}}(\mathcal{X}_{n+m}^{\bm{\pi}},\tilde{\mathcal{X}}_{n+m}^{\bm{\pi}})$
for any $\bm{\pi}\in\bm{\Pi}_{n+m}$. As we will see in Section 4.2, however,
this property does not hold for independence testing. We also highlight our
lower bound result, indicating that the upper bound $\sqrt{2K}/n$ cannot be
improved for translation invariant kernels with non-empty level sets on their
domain.

With Lemma 5 in place, we set the sensitivity parameter
$\Delta_{T}=\sqrt{2K}n^{-1}$ and run Algorithm 1 with the empirical MMD in (9)
as the test statistic. We refer to the resulting private permutation test as
the $\mathrm{dpMMD}$ test and denote it as $\phi_{\mathrm{dpMMD}}$. The
$\mathrm{dpMMD}$ test has the following properties, which are proven in
Section E.6.

######  Theorem 5 (Properties of $\mathrm{dpMMD}$ test).

Let $\alpha\in(0,1)$ be a fixed constant and the kernel $k$ be bounded as
$0\leq k(x,y)\leq K$ for all $x,y\in\mathbb{S}$. Then $\phi_{\mathrm{dpMMD}}$
satisfies the following properties:

  1. P1.

(Differential Privacy) For $\varepsilon>0$ and $\delta\in[0,1)$,
$\phi_{\mathrm{dpMMD}}$ is $(\varepsilon,\delta)$-differentially private.

  2. P2.

(Validity) The type I error of $\phi_{\mathrm{dpMMD}}$ is controlled at level
$\alpha$ non-asymptotically.

  3. P3.

(Consistency) Suppose that $\mathrm{MMD}_{k}(P,Q)$ is independent of the
sample sizes and strictly positive for a fixed pair of $(P,Q)$. Moreover
assume that $n^{-1}\xi_{\varepsilon,\delta}^{-1}\rightarrow 0$ as
$n\rightarrow\infty$. Then for any sequence $B_{n}$ such that $\min_{n\geq
1}B_{n}+1>\alpha^{-1}$, we have
$\lim_{n\rightarrow\infty}\mathbb{E}_{P,Q}[\phi_{\mathrm{dpMMD}}]=1$.

The first two properties on differential privacy and validity are clear in
view of Theorem 1 and Theorem 2. It is well-known that the population MMD is
strictly positive under the alternative if the kernel is characteristic
(Gretton et al.,, 2012). Hence the condition on the MMD metric in (_P3_) is
satisfied for characteristic kernels against any fixed alternative. Another
highlight is that consistency holds irrespective of the relationship between
$n$ and $m$. The power converges to one as long as the minimum sample size
goes to infinity. We also remark that the condition
$n^{-1}\xi_{\varepsilon,\delta}^{-1}\rightarrow 0$ is critical for obtaining
consistency. If not, the empirical MMD is overwhelmed by the Laplace noise,
which leads to a significant loss of power.

We note in passing the recent work of Yang et al., (2023) that also utilizes
the MMD in differentially private data analysis. Despite the fact that both
Yang et al., (2023) and ours consider the differentially private MMD, their
primary focus is on differentially private data generation, which is different
from our focus on hypothesis testing.

###  4.2 Differentially Private HSIC Test

Turning to the second application, suppose that we are given an i.i.d. paired
sample $\mathcal{X}_{n}=\\{(Y_{i},Z_{i})\\}_{i=1}^{n}$ from a joint
distribution $P_{YZ}$ on domain $\mathbb{Y}\times\mathbb{Z}$. Given
$\mathcal{X}_{n}$, the aim of independence testing is to assess whether $Y$
and $Z$ are statistically independent or not. As a kernel dependence measure,
the HSIC compares the joint probability measure $P_{YZ}$ to the product of
marginals $P_{Y}P_{Z}$. To formally define it, let $k$ and $\ell$ be kernels
on $\mathbb{Y}$ and $\mathbb{Z}$, and let $k\otimes\ell$ be the product kernel
given as
$k\otimes\ell\bigl{(}(y,z),(y^{\prime},z^{\prime})\bigr{)}=k(y,y^{\prime})\ell(z,z^{\prime})$
for all $y,y^{\prime}\in\mathbb{Y}$ and $z,z^{\prime}\in\mathbb{Z}$. Further
denoting the unit ball in the RKHS associated with $k\otimes\ell$ by
$\mathcal{F}_{k\otimes\ell}$, HSIC is defined as111We remark that in the
literature HSIC is often defined as the square of this quantity. However, for
consistency with MMD, we define it without the square.

$\displaystyle\mathrm{HSIC}_{k\otimes\ell}(P_{YZ})\coloneqq\sup_{f\in\mathcal{F}_{k\otimes\ell}}\big{\\{}\mathbb{E}_{P_{YZ}}[f(Y,Z)]-\mathbb{E}_{P_{Y}P_{Z}}[f(Y,Z)]\big{\\}}.$

In other words, the HSIC of $Y$ and $Z$ is simply the MMD between $P_{YZ}$ and
$P_{Y}P_{Z}$ with the product kernel $k\otimes\ell$. The empirical HSIC is a
plug-in estimator given as

$\displaystyle\widehat{\mathrm{HSIC}}(\mathcal{X}_{n})\coloneqq\sup_{f\in\mathcal{F}_{k\otimes\ell}}\bigg{\\{}\frac{1}{n}\sum_{i=1}^{n}f(Y_{i},Z_{i})-\frac{1}{n^{2}}\sum_{i,j=1}^{n}f(Y_{i},Z_{j})\bigg{\\}}.$
(11)

Similarly to the empirical MMD, the squared empirical HSIC also has an
explicit form in terms of the kernels $k$ and $\ell$ as

$\displaystyle\widehat{\mathrm{HSIC}}^{2}\\!(\mathcal{X}_{n})~{}={}$
$\displaystyle\frac{1}{n^{2}}\sum_{i,j=1}^{n}k(Y_{i},Y_{j})\ell(Z_{i},Z_{j})+\frac{1}{n^{4}}\sum_{i_{1},i_{2},j_{1},j_{2}=1}^{n}k(Y_{i_{1}},Y_{j_{1}})\ell(Z_{i_{2}},Z_{j_{2}})$
(12) $\displaystyle-$
$\displaystyle\frac{2}{n^{3}}\sum_{i,j_{1},j_{2}=1}^{n}k(Y_{i},Y_{j_{1}})\ell(Z_{i},Z_{j_{2}}),$

which can be computed in quadratic time as described in Song et al., (2012,
Theorem 1). For independence testing, the permutation test proceeds by
randomly permuting either the $Y$ observations or the $Z$ observations. Here,
we permute the $Z$ observations and denote
$\mathcal{X}_{n}^{\bm{\pi}}=\\{(Y_{i},Z_{\pi_{i}})\\}_{i=1}^{n}$. With this
notation in place, the next lemma explores the global sensitivity of the
empirical HSIC.

######  Lemma 6 (Sensitivity of Empirical HSIC).

Assume that the kernels $k$ and $\ell$ are bounded as $0\leq
k(y,y^{\prime})\leq K$ and $0\leq\ell(z,z^{\prime})\leq L$ for all
$y,y^{\prime}\in\mathbb{Y}$ and $z,z^{\prime}\in\mathbb{Z}$. Then the global
sensitivity of the empirical HSIC satisfies

$\displaystyle\sup_{\bm{\pi}\in\bm{\Pi}_{n}}\sup_{\begin{subarray}{c}\mathcal{X}_{n},\tilde{\mathcal{X}}_{n}:\\\
d_{\mathrm{ham}}(\mathcal{X}_{n},\tilde{\mathcal{X}}_{n})\leq
1\end{subarray}}\bigl{|}\widehat{\mathrm{HSIC}}(\mathcal{X}_{n}^{\bm{\pi}})-\widehat{\mathrm{HSIC}}(\tilde{\mathcal{X}}_{n}^{\bm{\pi}})\bigr{|}\leq\frac{4(n-1)}{n^{2}}\sqrt{KL}.$

Moreover assume that $k$ and $\ell$ are translation invariant, and have non-
empty level sets on $\mathbb{Y}$ and $\mathbb{Z}$, respectively. Then the
global sensitivity is lower bounded by $4(n-2.5)n^{-2}\sqrt{KL}$.

The proof of Lemma 5 can be found in Section E.7. Contrary to the MMD case, we
observe that the two hamming distances, namely
$d_{\mathrm{ham}}(\mathcal{X}^{\bm{\pi}}_{n},\tilde{\mathcal{X}}^{\bm{\pi}}_{n})$
and $d_{\mathrm{ham}}(\mathcal{X}_{n},\tilde{\mathcal{X}}_{n})$, can differ
for independence testing. Consequently, the supremum over the permutations
$\bm{\pi}\in\bm{\Pi}_{n}$ plays a non-trivial role in the sensitivity of the
empirical HSIC. We mention the work of Kusner et al., (2016) that also
examines the global sensitivity of the empirical HSIC. Our upper bound result
improves theirs by replacing the constant factor $12$ to $4$ with a tighter
analysis. In fact, as the lower bound result states, the proposed upper bound
is asymptotically tight under mild conditions for $k$ and $\ell$.

In view of the above lemma, we set $\Delta_{T}=4(n-1)n^{-2}\sqrt{KL}$ and run
Algorithm 1 with the empirical HSIC in (11) as the test statistic. We refer to
the resulting permutation test as the $\mathrm{dpHSIC}$ test and denote it as
$\phi_{\mathrm{dpHSIC}}$. Similar to Theorem 5, the $\mathrm{dpHSIC}$ test has
the following properties, which are proven in Section E.8.

######  Theorem 6 (Properties of $\mathrm{dpHSIC}$ test).

Let $\alpha\in(0,1)$ be a fixed constant and assume that the kernels $k$ and
$\ell$ are bounded as $0\leq k(y,y^{\prime})\leq K$ and
$0\leq\ell(z,z^{\prime})\leq L$ for all $y,y^{\prime}\in\mathbb{Y}$ and
$z,z^{\prime}\in\mathbb{Z}$. Then $\phi_{\mathrm{dpHSIC}}$ satisfies the
following properties:

  1. P1.

(Differential Privacy) For $\epsilon>0$ and $\delta\in[0,1)$,
$\phi_{\mathrm{dpHSIC}}$ is $(\varepsilon,\delta)$-differentially private.

  2. P2.

(Validity) The type I error of $\phi_{\mathrm{dpHSIC}}$ is controlled at level
$\alpha$ non-asymptotically.

  3. P3.

(Consistency) Suppose that $\mathrm{HSIC}_{k\otimes\ell}(P_{YZ})$ is
independent of the sample sizes and strictly positive for a fixed distribution
$P_{YZ}$. Moreover assume that $n^{-1}\xi_{\varepsilon,\delta}^{-1}\rightarrow
0$ as $n\rightarrow\infty$. Then for any sequence $B_{n}$ such that
$\min_{n\geq 1}B_{n}+1>\alpha^{-1}$, we have
$\lim_{n\rightarrow\infty}\mathbb{E}_{P_{YZ}}[\phi_{\mathrm{dpHSIC}}]=1$.

As for the $\mathrm{dpMMD}$ test, the first two properties on differential
privacy and validity are direct consequences of Theorem 1 and Theorem 2. The
condition for consistency is ensured under any alternative when the kernels
are characteristic (Gretton,, 2015). Therefore the $\mathrm{dpHSIC}$ test
equipped with a characteristic kernel is pointwise consistent against any
fixed alternative, provided that
$n^{-1}\xi_{\varepsilon,\delta}^{-1}\rightarrow 0$ and $\min_{n\geq
1}B_{n}+1>\alpha^{-1}$.

Before moving on and studying uniform power properties, let us briefly remark
on the asymptotic null distributions of private kernel test statistics.

######  Remark 2 (Asymptotic null distributions).

As mentioned earlier, when the null distribution is tractable, we can improve
the power by eliminating the factor of 2 in the noise level. However,
characterizing the limiting distribution is not a trivial task, even for non-
private kernel statistics. In Section B.1, we show that a private kernel
statistic converges in distribution to a mixture of Gaussian chaos and Laplace
distributions, which is even more intricate than the limiting distribution of
a non-private kernel statistic. A recent line of work (Shekhar et al., 2022a,
; Shekhar et al., 2022b, ) propose cross MMD and cross HSIC that have a
tractable limiting distribution with competitive power. We leave the
exploration of extending these variants to the private setting and comparing
their power performance with our proposed methods as an avenue for future
research.

##  5 Uniform Power and Optimality

In the previous section, we examined the fundamental properties of the private
kernel tests, including their asymptotic power against fixed alternatives.
This section delves into a more challenging setting where the alternative can
shrink to the null as the sample size increases, and develops uniform power
results. Moreover we highlight an intrinsic trade-off between privacy and
statistical power through the lens of minimax analysis, and explore optimality
of the proposed private tests under the differential privacy constraint. In
the main text, we focus on the analysis of the $\mathrm{dpMMD}$ test, and
defer analogous results for the $\mathrm{dpHSIC}$ test to Section B.5 and
Section B.6.

###  5.1 Separation in MMD Metric

Consider the setting described in Section 4.1, and denote by
$\mathcal{P}_{\mathbb{S}}$ the class of distributions defined on $\mathbb{S}$.
Our first goal is to determine the minimum separation for
$\phi_{\mathrm{dpMMD}}$ based on the MMD metric with kernel $k$. To this end,
for $\rho>0$, we define a class of paired distributions $(P,Q)$ such that

$\displaystyle\mathcal{P}_{\mathrm{MMD}_{k}}\\!(\rho)\coloneqq\big{\\{}(P,Q)\in\mathcal{P}_{\mathbb{S}}\times\mathcal{P}_{\mathbb{S}}:\mathrm{MMD}_{k}(P,Q)\geq\rho\big{\\}}.$

For a given target type II error $\beta\in(0,1-\alpha)$, the minimum
separation for the $\mathrm{dpMMD}$ test against
$\mathcal{P}_{\mathrm{MMD}_{k}}\\!(\rho)$ is given by

$\displaystyle\rho_{\phi_{\mathrm{dpMMD}}}(\alpha,\beta,\varepsilon,\delta,m,n)\coloneqq\inf\biggl{\\{}\rho>0:\sup_{(P,Q)\in\mathcal{P}_{\mathrm{MMD}_{k}}\\!(\rho)}\mathbb{E}_{P,Q}[1-\phi_{\mathrm{dpMMD}}]\leq\beta\biggr{\\}}.$
(13)

In simpler terms, the minimum separation $\rho_{\phi_{\mathrm{dpMMD}}}$ refers
to the smallest MMD metric between $P$ and $Q$ that can be correctly detected
by the $\mathrm{dpMMD}$ test with probability at least $1-\beta$. The next
theorem provides an upper bound for $\rho_{\phi_{\mathrm{dpMMD}}}$ as a
function of the parameters $\alpha$, $\beta$, $\varepsilon$, $\delta$, $m$,
and $n$. The proof can be found in Section E.9.

######  Theorem 7 (Minimum Separation of $\mathrm{dpMMD}$ over
$\mathcal{P}_{\mathrm{MMD}_{k}}$).

Assume that the kernel $k$ is bounded as $0\leq k(x,y)\leq K$ for all
$x,y\in\mathbb{S}$, and $n\leq m\leq\tau n$ for some fixed constant $\tau\geq
1$. Then for all values of $\alpha\in(0,1)$, $\beta\in(0,1-\alpha)$,
$\varepsilon>0$, $\delta\in[0,1)$ and $B\geq
16\alpha^{-2}\log\bigl{(}8/\beta\bigr{)}$, the minimum separation for
$\phi_{\mathrm{dpMMD}}$ satisfies

$\displaystyle\rho_{\phi_{\mathrm{dpMMD}}}\leq
C_{K,\tau}\max\Biggl{\\{}\sqrt{\frac{\max\\!\big{\\{}\\!\log(1/\alpha),\,\log(1/\beta)\big{\\}}}{n}},\,\frac{\max\\!\big{\\{}\\!\log(1/\alpha),\,\log(1/\beta)\big{\\}}}{n\xi_{\varepsilon,\delta}}\Biggr{\\}},$

where $C_{K,\tau}$ is a positive constant that depends only on $K$ and $\tau$,
and $\xi_{\varepsilon,\delta}$ can be recalled in (1).

We present several comments on the upper bound result.

  * •

Theorem 7 states that the separation rate for the $\mathrm{dpMMD}$ test
becomes $n^{-1/2}$ in low privacy regimes (_i.e._ ,
$\xi_{\varepsilon,\delta}\gtrsim n^{-1/2}$), whereas it becomes
$n^{-1}\xi_{\varepsilon,\delta}^{-1}$ in high privacy regimes (_i.e._ ,
$\xi_{\varepsilon,\delta}\lesssim n^{-1/2}$). Notably, this upper bound result
allows the parameters $\alpha,\beta,\xi_{\varepsilon,\delta}$ to vary freely
within the constraints in the theorem statement. We also mention that the
minimum separation is meaningful only when
$n^{-1}\xi_{\varepsilon,\delta}^{-1}\to 0$, which coincides with the condition
for consistency established in Theorem 5.

  * •

We point out that $\phi_{\mathrm{dpMMD}}$ is equivalent to the non-DP MMD test
(Gretton et al.,, 2012) when $\varepsilon\to\infty$ or $\delta\to 1$ (_i.e._ ,
$\xi_{\varepsilon,\delta}\to\infty$). Thus, our result also yields the minimum
separation rate for the non-DP MMD test as a byproduct.

  * •

One can prove Theorem 7 by verifying the general conditions in Theorem 4.
However this strategy results in polynomial factors of $\alpha$ and $\beta$
instead of logarithmic ones. To obtain logarithmic dependence in both $\alpha$
and $\beta$, we modify the proof of Theorem 4 and utilize exponential
concentration inequalities for the empirical MMD statistic (Lemma 13) and
permuted MMD statistic (Lemma 10). As we will see in Theorem 8, these
logarithmic factors cannot be improved further when $\alpha\asymp\beta$.

  * •

The constraint on the sample size ratio can be completely removed by using the
Markov inequality for a permuted MMD statistic (Lemma 11). Nevertheless, this
alternative approach yields a polynomial factor of $\alpha$ instead of a
logarithmic one. See Remark 3. It is currently unknown whether the constraint
on $m$ and $n$ can be eliminated, while preserving the logarithmic factors.

We next investigate minimax optimality of $\phi_{\mathrm{dpMMD}}$ under
certain regimes in $\mathbb{S}=\mathbb{R}^{d}$. To set the stage, let
$\phi:\mathcal{Y}_{n}\cup\mathcal{Z}_{m}\mapsto\\{0,1\\}$ be a test function,
and denote the set of $(\varepsilon,\delta)$-DP level $\alpha$ tests as

$\displaystyle\Phi_{\alpha,\varepsilon,\delta}\coloneqq\Big{\\{}\phi:\sup_{P\in\mathcal{P}_{\mathbb{S}}}\mathbb{E}_{P,P}[\phi]\leq\alpha\
\text{and}\ \text{$\phi$ is $(\varepsilon,\delta)$-DP}\Big{\\}}.$

From a theoretical point of view, it is of interest to figure out an
information-theoretic lower bound on the minimum separation for any test. This
is often called the minimax separation or critical radius in the literature
(Ingster,, 1994; Ingster et al.,, 2003; Baraud,, 2002). Formally, the minimax
separation in terms of the MMD metric is defined as

$\displaystyle\rho^{\star}_{\mathrm{MMD}}(\alpha,\beta,\varepsilon,\delta,m,n)\coloneqq\inf\Bigl{\\{}\rho>0:\inf_{\phi\in\Phi_{\alpha,\varepsilon,\delta}}\sup_{(P,Q)\in\mathcal{P}_{\mathrm{MMD}_{k}}\\!(\rho)}\mathbb{E}_{P,Q}[1-\phi]\leq\beta\Big{\\}}.$

In simpler terms, the minimax separation $\rho^{\star}_{\mathrm{MMD}}$ refers
to the largest MMD metric between $P$ and $Q$ that cannot be correctly
detected with probability at least $1-\beta$ by any level $\alpha$ test. We
say that a test $\phi$ is minimax rate optimal in terms of the MMD metric if
the minimum separation of $\phi$ is equivalent to
$\rho^{\star}_{\mathrm{MMD}}$ up to constant factors. The next theorem, proved
in Section E.10, establishes a lower bound for the minimax separation under
the DP constraint, from which we demonstrate minimax optimality of the
$\mathrm{dpMMD}$ test.

######  Theorem 8 (Minimax Separation over $\mathcal{P}_{\mathrm{MMD}_{k}}$).

Let $\alpha$ and $\beta$ be real numbers in the interval $(0,1/5)$,
$\varepsilon>0$ and $\delta\in[0,1)$. Assume that the kernel function $k$ is
translation invariant on $\mathbb{R}^{d}$. In particular there exists some
function $\kappa$ such that $k(x,y)=\kappa(x-y)$ for all
$x,y\in\mathbb{R}^{d}$. Moreover, the kernel is non-constant in the sense that
there exists a positive constant $\eta$ such that
$\kappa(0)-\kappa(z)\geq\eta$ for some $z\in\mathbb{R}^{d}$. Then the minimax
separation over $\mathcal{P}_{\mathrm{MMD}_{k}}$ is lower bounded as

$\displaystyle\rho^{\star}_{\mathrm{MMD}}\geq
C_{\eta}\max\Biggl{\\{}\min\\!\Bigg{(}\\!\sqrt{\frac{\log(1/(\alpha+\beta))}{n}},\,1\Bigg{)},\,\min\Biggl{(}\frac{\log(1/\beta)}{n\xi_{\varepsilon,\delta}},\,1\Biggr{)}\Biggr{\\}},$

where $C_{\eta}$ is a positive constant that only depends on $\eta$, and
$\xi_{\varepsilon,\delta}$ can be recalled in (1).

Several remarks are in order.

  * •

First of all, the restriction on $\alpha$ and $\beta$ is mild as we are
typically interested in small values of $\alpha$ and $\beta$. In fact, the
same result holds for any $\alpha,\beta$ such that $\alpha+\beta\leq C$ where
$C$ is some fixed constant strictly smaller than $1/2$. We also note that for
a bounded kernel ranging from $0$ and $K$, the MMD as well as the
corresponding minimax separation cannot exceed $\sqrt{2K}$. Our lower bound
result captures this restriction through the minimum operator.

  * •

Second, our proof builds on the $(\varepsilon,\delta)$-DP Le Cam’s method
outlined in Acharya et al., (2018, 2021). This technique generalizes classical
Le Cam’s two-point method (Le Cam,, 1973) to private settings via coupling
argument. As pointed out by Acharya et al., (2018, Lemma 5), one can obtain a
lower bound result for $(\varepsilon,\delta)$-DP by replacing $\varepsilon$
with $\varepsilon+\delta$ in the lower bound result for $\varepsilon$-DP.
However, this method fails to yield a tight lower bound in terms of $\beta$.
Our approach differs from Acharya et al., (2018, Lemma 5) and returns a sharp
lower bound for all parameters of interest, namely
$\beta,n,\varepsilon,\delta$.

  * •

Theorem 8 holds for translation invariant kernels. Indeed, many kernels
commonly used in practice are translation invariant including the Gaussian,
Laplacian, inverse multiquadrics and Matérn kernels. Moreover, as discussed in
Tolstikhin et al., (2017), if we further assume that the kernel $k$ is
characteristic, it guarantees the existence of $z\in\mathbb{R}^{d}$ and
$\eta>0$ that satisfy the conditions of Theorem 8. For instance, for the
Gaussian kernel $k(x,y)=e^{-\sigma\|x-y\|_{2}^{2}}$, one can take
$\eta=\frac{\sigma}{2}\|z\|_{2}^{2}$ for any non-zero $z$ such that
$\|z\|_{2}^{2}\leq\sigma^{-1}$.

  * •

The last point worth highlighting is that our lower bound permits varying
values of $\alpha$ and $\beta$, which is in contrast to most existing research
on minimax testing. A notable exception is the recent work by Diakonikolas et
al., (2021), which examines the sample complexity of testing for discrete
distributions with high probability.

We now compare the results of Theorem 7 and Theorem 8, and observe that the
lower bound for $\rho^{\star}_{\mathrm{MMD}}$ matches the upper bound for
$\rho_{\phi_{\mathrm{dpMMD}}}$ in the regime where $m\asymp n$ and
$\alpha\asymp\beta$ for $\mathbb{S}=\mathbb{R}^{d}$. This shows that the
proposed $\mathrm{dpMMD}$ test is minimax rate optimal against the class of
alternatives determined by the MMD metric in the considered regime. It is
noteworthy that there is no restriction on the privacy parameters
$\varepsilon>0$ and $\delta\in[0,1)$, and hence the $\mathrm{dpMMD}$ test
achieves optimal separation rates in all privacy regimes.

###  5.2 Separation in $L_{2}$ Metric

We next investigate the minimum separation of the $\mathrm{dpMMD}$ test in
terms of the $L_{2}$ metric. Let $p$ and $q$ denote the Lebesgue density
functions of $P$ and $Q$, respectively, defined on $\mathbb{R}^{d}$. As in
Schrab et al., (2023) and Li and Yuan, (2019), we restrict our attention to a
smooth class of density functions defined over a Sobolev ball. In particular,
for a smoothness parameter $s>0$ and a radius $R>0$, the Sobolev ball
$\mathcal{S}_{d}^{s}(R)$ is given as

$\displaystyle\mathcal{S}_{d}^{s}(R):=\Bigg{\\{}f\in L_{1}(\mathbb{R}^{d})\cap
L_{2}(\mathbb{R}^{d}):\int_{\mathbb{R}^{d}}\|w\|_{2}^{2s}|\widehat{f}(w)|^{2}\mathrm{d}w\leq(2\pi)^{d}R^{2}\Bigg{\\}},$
(14)

where $\widehat{f}$ is the Fourier transform of $f$, _i.e._ ,
$\widehat{f}(w)=\int_{\mathbb{R}^{d}}f(x)e^{-ix^{\top}w}\mathrm{d}x$ for
$w\in\mathbb{R}^{d}$. The condition $f\in L_{1}(\mathbb{R}^{d})\cap
L_{2}(\mathbb{R}^{d})$ simply requires the function
$f\colon\mathbb{R}^{d}\to\mathbb{R}$ to be both integrable and square-
integrable with respect to the Lebesgue measure. For $\rho>0$, let
$\mathcal{P}_{L_{2}}\\!(\rho)$ be the collection of paired distributions
$(P,Q)$ on $\mathbb{R}^{d}\times\mathbb{R}^{d}$ where $P$ and $Q$ are equipped
with the Lebesgue density functions $p$ and $q$, respectively, such that
$\|p-q\|_{L_{2}}\geq\rho$. The target class of distributions is a subset of
$\mathcal{P}_{L_{2}}\\!(\rho)$ defined as

$\displaystyle\mathcal{P}_{L_{2}}^{s}\\!(\rho)\coloneqq\big{\\{}(P,Q)\in\mathcal{P}_{L_{2}}\\!(\rho):p-q\in\mathcal{S}_{d}^{s}(R),\
\max(\|p\|_{L_{\infty}},\|q\|_{L_{\infty}})\leq M\big{\\}}.$

The aim of this subsection is to characterize the minimum value of $\rho$ for
which the $\mathrm{dpMMD}$ test has significant power uniformly over
$\mathcal{P}_{L_{2}}^{s}(\rho)$. For simplicity, we focus on the
$\mathrm{dpMMD}$ test with a Gaussian kernel. This choice is motivated by the
observation that the population MMD with the Gaussian kernel approximates
$\|p-q\|_{L_{2}}^{2}$ for small bandwidth values (Li and Yuan,, 2019), and a
similar result can be derived using other kernels in view of Schrab et al.,
(2023). For $x=(x_{1},\ldots,x_{d})^{\top}\in\mathbb{R}^{d}$ and
$y=(y_{1},\ldots,y_{d})^{\top}\in\mathbb{R}^{d}$, the Gaussian kernel with
bandwidth
$\bm{\lambda}=(\lambda_{1},\ldots,\lambda_{d})^{\top}\in(0,\infty)^{d}$ is
given as

$\displaystyle
k_{\bm{\lambda}}(x,y)=\prod_{i=1}^{d}\frac{1}{\sqrt{2\pi}\lambda_{i}}e^{-\frac{(x_{i}-y_{i})^{2}}{2\lambda_{i}^{2}}}.$

Let us denote the minimum separation of the $\mathrm{dpMMD}$ test with the
Gaussian kernel against $L_{2}$ alternatives as

$\displaystyle\rho_{\phi_{\mathrm{dpMMD}},L_{2}}(\alpha,\beta,\varepsilon,\delta,m,n,d,s,R,M)\coloneqq\inf\Biggl{\\{}\rho>0:\sup_{(P,Q)\in\mathcal{P}_{L_{2}}^{s}\\!(\rho)}\mathbb{E}_{P,Q}[1-\phi_{\mathrm{dpMMD}}]\leq\beta\Biggr{\\}}.$
(15)

The next theorem, proved in Section E.11, provides an upper bound for
$\rho_{\phi_{\mathrm{dpMMD}},L_{2}}$ in terms of a set of parameters,
including the bandwidth $\bm{\lambda}$ and sample sizes.

######  Theorem 9 (Minimum Separation of $\mathrm{dpMMD}$ over
$\mathcal{P}_{L_{2}}^{s}$).

Assume that $n\leq m\leq\tau n$ for some fixed constant $\tau\geq 1$, and that
$\alpha\in(0,e^{-1})$, $\beta\in(0,1-\alpha)$, $\varepsilon>0$,
$\delta\in[0,1)$, $B\geq 16\alpha^{-2}\log(8/\beta)$ and
$\prod_{i=1}^{d}\lambda_{i}\leq 1$. The minimum separation of the
$\mathrm{dpMMD}$ test with the Gaussian kernel over $\mathcal{P}_{L_{2}}^{s}$
is upper bounded as

$\displaystyle\rho_{\phi_{\mathrm{dpMMD}},L_{2}}^{2}\leq
C_{\tau,\beta,s,R,M,d}\Biggl{\\{}\sum_{i=1}^{d}\lambda_{i}^{2s}$
$\displaystyle+\frac{\log(1/\alpha)}{n\sqrt{\lambda_{1}\cdots\lambda_{d}}}+\frac{\log(1/\alpha)}{n^{3/2}\lambda_{1}\cdots\lambda_{d}\xi_{\varepsilon,\delta}}$
$\displaystyle+\frac{\log^{2}(1/\alpha)}{n^{2}\lambda_{1}\cdots\lambda_{d}\xi_{\varepsilon,\delta}^{2}}+\frac{\log^{3/2}(1/\alpha)}{n^{3/2}(\lambda_{1}\cdots\lambda_{d})^{3/4}\xi_{\varepsilon,\delta}}\Bigg{\\}},$

where $C_{\tau,\beta,s,R,M,d}$ is a positive constant, depending only on
$\tau,\beta,s,R,M,d$, and $\xi_{\varepsilon,\delta}$ is as in (1).

There are several points needed to be highlighted. To facilitate our
discussion, assume that $\alpha$ is a fixed number and write

$\displaystyle(\mathrm{I})=\frac{\log(1/\alpha)}{n\sqrt{\lambda_{1}\cdots\lambda_{d}}},\
(\mathrm{II})=\frac{\log(1/\alpha)}{n^{3/2}\lambda_{1}\cdots\lambda_{d}\xi_{\varepsilon,\delta}},\
(\mathrm{III})=\frac{\log^{2}(1/\alpha)}{n^{2}\lambda_{1}\cdots\lambda_{d}\xi_{\varepsilon,\delta}^{2}},\
(\mathrm{IV})=\frac{\log^{3/2}(1/\alpha)}{n^{3/2}(\lambda_{1}\cdots\lambda_{d})^{3/4}\xi_{\varepsilon,\delta}}.$

When $\alpha$ is fixed, we can absorb the term $(\mathrm{IV})$ into the term
$(\mathrm{II})$ as $\lambda_{1}\cdots\lambda_{d}\leq 1$, and simplify the
interpretation of the result as follows.

  * •

In the low privacy regime where the first term $(\mathrm{I})$ dominates the
others, our result recovers Schrab et al., (2023, Theorem 6), which studies
the minimum separation of the non-private MMD test against
$\mathcal{P}_{L_{2}}^{s}$. In this low privacy regime, by setting bandwidths
$\lambda_{i}=n^{-2/(4s+d)}$ for $i\in[d]$, we can achieve the optimal
separation rate over the Sobolev ball, that is $n^{-2s/(4s+d)}$.

  * •

In the mid privacy regime where the term $(\mathrm{II})$ becomes a leading
term, equating $(\mathrm{II})$ with $\sum_{i=1}^{d}\lambda_{i}^{2s}$ yields
the optimal choice of bandwidths
$\lambda_{i}=n^{-3/(4s+2d)}\xi_{\varepsilon,\delta}^{-1/(2s+d)}$ for
$i\in[d]$. The resulting separation rate is
$n^{-3s/(4s+2d)}\xi_{\varepsilon,\delta}^{-s/(2s+d)}$. Similarly, in the high
privacy regime where the term $(\mathrm{III})$ dominates the others, equating
$(\mathrm{III})$ with $\sum_{i=1}^{d}\lambda_{i}^{2s}$ yields the optimal
choice of bandwidths $\lambda_{i}=(n\xi_{\varepsilon,\delta})^{-2/(2s+d)}$ for
$i\in[d]$. This returns the separation rate
$(n\xi_{\varepsilon,\delta})^{-2s/(2s+d)}$. By tracking conditions for each
term dominating the others, the minimum separation rate that one can achieve
using different bandwidths is summarized as

$\displaystyle\rho_{\phi_{\mathrm{dpMMD}},L_{2}}\lesssim\begin{cases}n^{-\frac{2s}{4s+d}},&\textrm{if
}n^{-\frac{2s-d/2}{4s+d}}\lesssim\xi_{\varepsilon,\delta}\ \textrm{(low
privacy)},\\\\[5.69054pt]
(n^{\frac{3}{2}}\xi_{\varepsilon,\delta})^{-\frac{s}{2s+d}},&\textrm{if
}n^{-\frac{1}{2}}\lesssim\xi_{\varepsilon,\delta}\lesssim
n^{-\frac{2s-d/2}{4s+d}}\ \textrm{(mid privacy)},\\\\[5.69054pt]
\left(n\xi_{\varepsilon,\delta}\right)^{-\frac{2s}{2s+d}},&\textrm{if
}\xi_{\varepsilon,\delta}\lesssim n^{-\frac{1}{2}}\ \textrm{(high
privacy)}.\end{cases}$ (16)

In particular, when $\xi_{\varepsilon,\delta}\asymp n^{-1/2}$, the separation
rate becomes $n^{-2/(2s+d)}$, which is known to be the minimax optimal rate of
density estimation under the $L_{2}$ loss. We refer to Section B.8 for a
detailed discussion of the separation rate.

  * •

It is important to note that all these separation rates are achieved by using
different bandwidths, which requires knowledge of the smoothness parameter
$s$. Building on the idea of Ingster, (2000); Schrab et al., (2023); Biggs et
al., (2023), one can develop an aggregated $\mathrm{dpMMD}$ test that is
adaptive to $s$ without losing much power. The main idea would be to consider
a wide range of private MMD statistics with different bandwidths and aggregate
them properly. A detailed analysis of this approach is left for future
research.

  * •

While the $\mathrm{dpMMD}$ test can achieve the minimax rate in the low
privacy regime, it remains unknown whether the derived separation rates are
optimal in the mid/high privacy regimes. We believe that
$(\varepsilon,\delta)$-DP Le Cam’s method (Acharya et al.,, 2021, Theorem 1)
plays an important role in constructing a lower bound for the $L_{2}$
separation as well. The key challenge lies in finding a coupling between
continuous distributions, yielding a small expected Hamming distance. We leave
this important direction for future work.

In contrast to the prior work (Li and Yuan,, 2019; Schrab et al.,, 2023) that
utilize a U-statistic for minimax two-sample testing, our approach is based on
a plug-in estimator, also known as a V-statistic, of the MMD. While plug-in
estimators can often exhibit suboptimal performance in estimation problems due
to their inherent bias, they can still achieve optimal results in testing
problems. This can be explained by the interplay between the test statistic
and the critical value in a testing procedure, where the bias terms in these
components may offset each other. Theorem 9 demonstrates this phenomenon by
showing that the test based on the plug-in estimator of the MMD attains the
minimax separation rate over $\mathcal{P}_{L_{2}}^{s}$ in the low privacy
regime. Perhaps more interestingly, the plug-in estimator can outperform the
U-statistic by having lower sensitivity and thus leading to greater power in
high privacy regimes. This aspect of plug-in estimators has not been noticed
in the literature, and we provide a more detailed discussion in the next
subsection.

###  5.3 Private Test based on the MMD U-statistic

It has been shown that kernel tests based on U-statistics often produce
optimal separation rates in non-DP settings (Li and Yuan,, 2019; Schrab et
al.,, 2023; Albert et al.,, 2022; Kim et al., 2022a, ). Therefore, one can
naturally expect that their private extensions perform similarly well across
different privacy regimes. In this section, we prove that this is not
necessarily the case. In particular, we illustrate that the private MMD
permutation test based on a U-statistic is provably outperformed by our
approach based on the plug-in MMD estimate in high privacy regimes. A similar
result for HSIC can be found in Section B.7.

We begin with the explicit form of the MMD U-statistic, which is an unbiased
estimator of $\mathrm{MMD}^{2}_{k}$, given as

$\displaystyle
U_{\mathrm{MMD}}(\mathcal{X}_{n+m})\coloneqq\frac{1}{n(n-1)}\sum_{1\leq i\neq
j\leq n}k(Y_{i},Y_{j})+\frac{1}{m(m-1)}\sum_{1\leq i\neq j\leq
m}k(Z_{i},Z_{j})-\frac{2}{nm}\sum_{i=1}^{n}\sum_{j=1}^{m}k(Y_{i},Z_{j}).$

The following lemma calculates the global sensitivity of $U_{\mathrm{MMD}}$,
which is proved in Section E.12.

######  Lemma 7 (Global Sensitivity of $U_{\mathrm{MMD}}$).

Assume that the kernel $k$ is bounded as $0\leq k(x,y)\leq K$ for all
$x,y\in\mathbb{S}$. In addition, assume that $k$ is translation invariant, and
have non-empty level sets on $\mathbb{S}$. Then there exists a positive
sequence $c_{m,n}\in[4,8]$ such that for all $2\leq n\leq m$,

$\displaystyle\sup_{\bm{\pi}\in\bm{\Pi}_{n+m}}\sup_{\begin{subarray}{c}\mathcal{X}_{n+m},\tilde{\mathcal{X}}_{n+m}:\\\
d_{\mathrm{ham}}(\mathcal{X}_{n+m},\tilde{\mathcal{X}}_{n+m})\leq
1\end{subarray}}\bigl{|}U_{\mathrm{MMD}}(\mathcal{X}_{n+m}^{\bm{\pi}})-U_{\mathrm{MMD}}(\tilde{\mathcal{X}}_{n+m}^{\bm{\pi}})\bigr{|}=\frac{c_{m,n}K}{n}.$

The lemma above indicates that the global sensitivity of the U-statistic has
the same dependence on $n$ as that of the plug-in MMD in Lemma 5. However, it
is important to mention that their target parameters are different. The
U-statistic is an estimator of $\mathrm{MMD}^{2}_{k}$, whereas the plug-in
estimator given in (9) estimates $\mathrm{MMD}_{k}$ without squaring. This key
difference can lead to a significant gap in their power performance in privacy
regimes as explored below.

Given the sensitivity of $U_{\mathrm{MMD}}$ in Lemma 7, we consider the
private permutation test in Algorithm 1 using the test statistic
$U_{\mathrm{MMD}}$ and the global sensitivity $\Delta_{T}=c_{m,n}Kn^{-1}$. Let
us denote the resulting private test by $\phi_{\mathrm{dpMMD}}^{u}$. We
analyze the minimum separations of $\phi_{\mathrm{dpMMD}}^{u}$ over
$\mathcal{P}_{\mathrm{MMD}_{k}}$ and $\mathcal{P}_{L_{2}}^{s}$ in Theorem 10
and Theorem 11, respectively, and compare them with those of
$\phi_{\mathrm{dpMMD}}$ based on the plug-in estimator. Starting with the MMD
alternative, the following theorem demonstrates that
$\phi_{\mathrm{dpMMD}}^{u}$ fails to achieve the minimax separation rate over
$\mathcal{P}_{\mathrm{MMD}_{k}}$.

######  Theorem 10 (Suboptimality of $\phi_{\mathrm{dpMMD}}^{u}$ against MMD
Alternatives).

Assume that the kernel $k$ fulfills the conditions specified in Lemma 7.
Moreover, assume that if $P,Q\in\mathcal{P}_{\mathbb{S}}$, then
$wP+(1-w)Q\in\mathcal{P}_{\mathbb{S}}$ for all $w\in[0,1]$, and there exist
$P_{0},Q_{0}\in\mathcal{P}_{\mathbb{S}}$ such that
$\mathrm{MMD}_{k}(P_{0},Q_{0})=\varrho_{0}$ for some fixed $\varrho_{0}>0$.
Let $\alpha\in\bigl{(}(B+1)^{-1},1\bigr{)}$, $\beta\in(0,1-\alpha)$ be fixed
values. Consider the high privacy regime where $\xi_{\varepsilon,\delta}\asymp
n^{-1/2-r}$ with fixed $r\in(0,1/2)$, for $\xi_{\varepsilon,\delta}$ as in
(1). Then the uniform power of $\phi_{\mathrm{dpMMD}}^{u}$ is asymptotically
at most $\alpha$ over $\mathcal{P}_{\mathrm{MMD}_{k}}\\!(\rho)$ where

$\displaystyle\rho=\log(n)\times\max\Biggl{\\{}\sqrt{\frac{\max\\!\big{\\{}\\!\log(1/\alpha),\,\log(1/\beta)\big{\\}}}{n}},\,\frac{\max\\!\big{\\{}\\!\log(1/\alpha),\,\log(1/\beta)\big{\\}}}{n\xi_{\varepsilon,\delta}}\Biggr{\\}}.$
(17)

In other words, it holds that

$\displaystyle\limsup_{n\rightarrow\infty}\inf_{(P,Q)\in\mathcal{P}_{\mathrm{MMD}_{k}}\\!(\rho)}\mathbb{E}_{P,Q}[\phi_{\mathrm{dpMMD}}^{u}]\leq\alpha.$

Theorem 10, proven in Section E.13, clearly shows that
$\phi_{\mathrm{dpMMD}}^{u}$ is not minimax optimal in the MMD metric as
$\rho/\rho^{\star}_{\mathrm{MMD}}\rightarrow\infty$ as $n\rightarrow\infty$.
We also mention that the factor $\log(n)$ in $\rho$ is chosen for convenience,
and it can be replaced by any other positive sequence that increases slower
than $n^{r}$ for $r\in(0,1/2)$. The suboptimal performance of
$\phi_{\mathrm{dpMMD}}^{u}$ primarily stems from the relatively high noise
level associated with the Laplace mechanism. Intuitively, we expect that
$\phi_{\mathrm{dpMMD}}^{u}$ is powerful in the private regime when the target
parameter $\mathrm{MMD}^{2}_{k}(P,Q)$ is larger than the Laplace noise level
$(n\xi_{\varepsilon,\delta})^{-1}$, equivalently, $\mathrm{MMD}_{k}(P,Q)$ is
larger than $(n\xi_{\varepsilon,\delta})^{-1/2}$. Otherwise, the test
statistic will be dominated by the Laplace noise. Importantly, the minimax
separation under high privacy regimes in Theorem 8 is associated with
$\min\\{(n\xi_{\varepsilon,\delta})^{-1},1\\}$, which is smaller than
$(n\xi_{\varepsilon,\delta})^{-1/2}$. This briefly explains the suboptimality
of $\phi_{\mathrm{dpMMD}}^{u}$ against the MMD alternative. Nevertheless, our
analysis is limited to the U-statistic with the Laplace mechanism, and it is
unknown whether the U-statistic in conjunction with other DP mechanisms can
lead to optimality.

Turning to the $L_{2}$ alternative, let us denote the minimum separation of
$\phi_{\mathrm{dpMMD}}^{u}$ with the Gaussian kernel over
$\mathcal{P}_{L_{2}}^{s}$ as $\rho_{\phi_{\mathrm{dpMMD}}^{u},L_{2}}$, which
is similarly defined as (15). Our next concern is characterizing
$\rho_{\phi_{\mathrm{dpMMD}}^{u},L_{2}}$ and comparing it with the minimum
separation of the $\mathrm{dpMMD}$ test established in Theorem 9.

######  Theorem 11 (Minimum Separation of $\phi_{\mathrm{dpMMD}}^{u}$ over
$\mathcal{P}_{L_{2}}^{s}$).

Assume that $n\leq m\leq\tau n$ for some fixed constant $\tau\geq 1$, and that
$\alpha\in(0,e^{-1})$, $\beta\in(0,1)$, $\varepsilon>0$, $\delta\in[0,1)$,
$B\geq 16\alpha^{-2}\log(8/\beta)$ and $\prod_{i=1}^{d}\lambda_{i}\leq 1$. The
minimum separation of $\phi_{\mathrm{dpMMD}}^{u}$ with the Gaussian kernel
over $\mathcal{P}_{L_{2}}^{s}$ is upper bounded as

$\displaystyle\rho_{\phi_{\mathrm{dpMMD}}^{u},L_{2}}^{2}\leq
C_{\tau,\beta,s,R,M,d}\Biggl{\\{}\sum_{i=1}^{d}\lambda_{i}^{2s}$
$\displaystyle+\frac{\log(1/\alpha)}{n\sqrt{\lambda_{1}\cdots\lambda_{d}}}+\frac{\log(1/\alpha)}{n\lambda_{1}\cdots\lambda_{d}\xi_{\varepsilon,\delta}}\Bigg{\\}},$

where $C_{\tau,\beta,s,R,M,d}$ is a positive constant, depending only on
$\tau,\beta,s,R,M,d$, and $\xi_{\varepsilon,\delta}$ is as in (1).

The proof of Theorem 11 is given in Section E.14. To simplify our discussion,
assume that $\alpha$ is a fixed constant. In this case, by comparing Theorem
11 with Theorem 9, the upper bound for
$\rho_{\phi_{\mathrm{dpMMD}}^{u},L_{2}}^{2}$ is smaller than that for
$\rho_{\phi_{\mathrm{dpMMD}},L_{2}}^{2}$, up to a constant, only when
$n\xi_{\varepsilon,\delta}\lesssim 1$. Since $\prod_{i=1}^{d}\lambda_{i}\leq
1$ and $\alpha$ is fixed, the condition $n\xi_{\varepsilon,\delta}\lesssim 1$
essentially means that $\|p-q\|_{L_{2}}$ needs to be sufficiently larger than
a specific constant for significant power. However, this condition may be
infeasible as we assume that $\|p\|_{L_{\infty}}$ and $\|q\|_{L_{\infty}}$ are
bounded by $M$. In fact, our earlier result in Theorem 5 suggests that the
test is not even consistent in a pointwise sense when
$n\xi_{\varepsilon,\delta}\lesssim 1$. Therefore, except for this boundary
case, it is more beneficial to use $\phi_{\mathrm{dpMMD}}$ than
$\phi_{\mathrm{dpMMD}}^{u}$ to achieve tighter separation rates over
$\mathcal{P}_{L_{2}}^{s}$ in high privacy regimes.

As we mentioned before, it remains an open question whether there exist
alternative privacy mechanisms that could potentially yield an optimal test
based on $U_{\mathrm{MMD}}$ in high privacy regimes. While we still advocate
using the plug-in MMD estimate over $U_{\mathrm{MMD}}$ due to its smaller
sensitivity, it would be interesting to explore this question in future work.

##  6 Simulations

In this section, we compare the empirical power of dpMMD against other private
two-sample tests, including the naive dpMMD introduced in Equation 6 and the
U-statistic dpMMD studied in Section 5.3. We also implement two generic
methods for privatizing the permutation MMD test, which we refer to as TOT MMD
(Kazan et al.,, 2023) and SARRM MMD (Peña and Barrientos,, 2022). Finally, we
also compare against the differentially private kernel two-sample test, TCS-
ME, proposed by Raj et al., (2020). A brief overview of these alternative
methods is provided in Section 6.1, with detailed information available in
Appendix D.

We empirically study the power attained by dpMMD on synthetic data sampled
from perturbed uniform distributions in Section 6.2, and on real-world high-
dimensional CelebA image data in Section 6.3. The latter scenario involves
sensitive information on human faces, justifying the incorporation of
differential privacy in the analysis. In both simulation settings, we observe
consistent patterns in the power behavior, and a detailed discussion on the
results is presented in Section 6.4. For all our experiments, we use a
Gaussian kernel, $B=2000$ permutations, and report power results averaged over
$200$ repetitions.

Due to space constraints, we defer the dpHSIC simulations to Appendix C, along
with test-level analysis and additional low-privacy experiments. The code to
run our tests and to reproduce the experiments is available at
https://github.com/antoninschrab/dpkernel.

###  6.1 Alternative differentially private tests

We provide a brief introduction to the alternative differentially private
tests, namely TCS-ME, TOT, and SARRM, with detailed implementation information
available in Appendix D.

##### TOT (Kazan et al.,, 2023).

TOT is constructed based on the subsample-and-aggregate idea outlined in
Canonne et al., (2019). It is guaranteed to be differentially private and to
correctly control the probability of type I error for any sample size, any
number of partitioned subsets, and any sub-test significance level. However,
for non-parametric testing, there is no principled way to choose the last two
parameters and one has to rely on heuristics in practice. This heuristic
aspect presents a notable disadvantage of TOT, being highly sensitive to the
choice of these parameters.

##### SARRM (Peña and Barrientos,, 2022).

As another method based on the subsample-and-aggregate idea, SARRM also
depends on the number of partitioned subsets and on the sub-test significance
level. Peña and Barrientos, (2022) propose a method to select these
parameters, which can be implemented for MMD/HSIC tests. However, the
differential privacy constraint and type I error control for SARRM are only
guaranteed for sufficiently large sample sizes (determined by a minimum number
of partitioned subsets to use), which means that SARRM simply cannot be run in
some settings depending on the values of $\varepsilon$, $\alpha$, and $n$.

##### TCS-ME (Raj et al.,, 2020).

The TCS-ME test is a privatized version of the ME test (Jitkrittum et al.,,
2016) that utilizes kernel mean embeddings. This method builds on a Hotelling-
type test statistic privatized by the Gaussian mechanism, and requires a
careful choice of test locations. The resulting test is
$(\varepsilon,\delta)$-DP for $\delta>0$ (run with $\delta=10^{-5}$). A major
limitation of TCS-ME is its potential for significant miscalibration,
particularly in high-dimensional settings. See our discussion on type I error
control in Section 6.5.

###  6.2 Perturbed Uniform Distributions

As recalled in Section 5.2, the minimax $L_{2}$ separation rate over the
Sobolev ball $\mathcal{S}_{d}^{s}(R)$ is $n^{-2s/(4s+d)}$ in the non-privacy
regime. A lower bound for this minimax separation rate is derived by
constructing two densities whose difference lies in the Sobolev ball with a
small $L_{2}$ norm. As explained by Schrab et al., (2023, Appendix D), the
uniform and perturbed uniform densities meet the requirements in the lower
bound construction, and we adopt this setting in our two-sample experiments.
In more detail, we compare the uniform distribution with its perturbed
counterpart, varying the amplitudes.

Figure 1:  Perturbed uniform $d$-dimensional densities on $[0,1]^{d}$ with
varying perturbation amplitude $a$.  Figure 2:  Comparing uniform vs.
perturbed uniform while varying the privacy level $\varepsilon$. We set the
sample sizes $m=n=3000$ and dimension $d=1$, and change the privacy level
$\varepsilon$ and perturbation amplitude $a$ as follows: _(Left)_ Privacy
level $\varepsilon$ from $1/n$ to $10/\sqrt{n}$, perturbation amplitude
$a=0.2$. _(Middle)_ Privacy level $\varepsilon$ from $10/\sqrt{n}$ to $1$,
perturbation amplitude $a=0.15$. _(Right)_ Privacy level $\varepsilon$ from
$1$ to $\sqrt{n}$, perturbation amplitude $a=0.1$.  Figure 3:  Comparing
uniform vs. perturbed uniform while varying the sample sizes $m=n$. We set the
dimension $d=1$ and perturbation amplitude $a=0.1$. We change the privacy
level as follows: _(Left)_ Privacy level $\varepsilon=10/\sqrt{n}$. _(Middle)_
Privacy level $\varepsilon=1$. _(Right)_ Privacy level
$\varepsilon=\sqrt{n}/10$.  Figure 4:  Comparing uniform vs. perturbed uniform
while varying the dimension $d$. We set the sample sizes $m=n=3000$ and
perturbation amplitude $a=0.2$. We change the privacy level as follows:
_(Left)_ Privacy level $\varepsilon=10/\sqrt{n}$. _(Middle)_ Privacy level
$\varepsilon=1$. _(Right)_ Privacy level $\varepsilon=\sqrt{n}/10$.

Specifically, the considered uniform distribution on $[0,1]^{d}$ has density
$\mathds{1}(x\in[0,1]^{d})$ for $x\in\mathbb{R}^{d}$, while the perturbed
uniform density on $[0,1]^{d}$ with a perturbation amplitude $a\in[0,1]$ is

$\mathds{1}\bigl{(}x\in[0,1]^{d}\bigr{)}+a\,\prod_{i=1}^{d}P(x_{i}),\quad\text{for
$x=(x_{1},\ldots,x_{d})^{\top}\in\mathbb{R}^{d}$,}$ (18)

where the one-dimensional perturbation is defined as

$\displaystyle
P(x_{i})\coloneqq\exp\\!\left(1-\frac{1}{1-(4x_{i}-1)^{2}}\right)\\!\mathds{1}\bigl{(}x_{i}\in(0,1/2)\bigr{)}-\exp\\!\left(1-\frac{1}{1-(4x_{i}-3)^{2}}\right)\\!\mathds{1}\bigl{(}x_{i}\in(1/2,1)\bigr{)}.$

This definition matches the one of Schrab et al., (2023, Equation 17) with
only one (scaled) perturbation per dimension. The one-dimensional and two-
dimensional perturbed densities with various perturbation amplitudes are
visualized in Figure 1.

We run our perturbed uniform experiments under three different settings where
we vary the privacy level $\varepsilon$ (Figure 2), the sample sizes $m=n$
(Figure 3), and the dimension $d$ (Figure 4). Additionally, we provide
experiments with ‘strong-signal’ alternatives in the low privacy regime in
Figure 12 in Section C.2, as well as a level analysis in Figure 14 in Section
C.3. We discuss all experimental results of Figures 2, 3 and 4 in Section 6.4.

Figure 5: Selected CelebA images in dimension $3\times 178\times 218$.

###  6.3 CelebA

As some potential real-world applications of differentially private two-sample
tests, we consider CelebA face images which in practice would be highly
confidential, and hence the use of DP tests is thoroughly justified. The
CelebA dataset (Liu et al.,, 2015) consists of $202,599$ face images of
$10,177$ identities with a large diversity of face attributes, poses and
backgrounds. For illustration purposes, we display a selection of CelebA
images in Figure 5. It is worth highlighting that we run our tests on the
original full-resolution images $(3\times 178\times 218)$ without any
modifications.

In our experiments, one sample consists of uniformly-sampled face images of
women, while the other is ‘corrupted’ with corruption parameter $c\in[0,1]$ in
the following sense: we uniformly sample face images of women with probability
$1-c$, and of men with probability $c$.

We run several CelebA experiments while varying the privacy level
$\varepsilon$ (Figure 6), the sample sizes $m=n$ (Figure 7), and the
corruption $c$ (Figure 8). As in Section 6.2, we consider the high/mid/low
privacy regimes for each of these. We also verify that all tests are well-
calibrated in Figure 14 in Section C.3. TCS-ME is excluded from our power
analysis on the CelebA data as we empirically observed that this method is not
well-calibrated for this dataset.

Our results consistently demonstrate that kernel tests using a simple Gaussian
kernel are able to capture complex image distribution shifts (see Figure 5)
even in this extremely high dimensional setting with $d=3\times 178\times
218=116,412$. This result is surprising given that the Gaussian kernel simply
compares the distance between pixels at the same location without using
information about the image structure. We discuss this aspect more in Section
6.4.

Figure 6:  Comparing CelebA women/men images while varying the privacy level
$\varepsilon$. We set the sample sizes $m=n=500$, and change the parameters as
follows: _(Left)_ Privacy level $\varepsilon$ from $1/n$ to $10/\sqrt{n}$,
corruption $c=1$. _(Middle)_ Privacy level $\varepsilon$ from $10/\sqrt{n}$ to
$1$, corruption $c=0.6$. _(Right)_ Privacy level $\varepsilon$ from $1$ to
$\sqrt{n}$, corruption $c=0.5$.  Figure 7:  Comparing CelebA women/men images
while varying the sample sizes $m=n$. We set the other parameters as follows:
_(Left)_ Privacy level $\varepsilon=10/\sqrt{n}$, corruption $c=0.7$.
_(Middle)_ Privacy level $\varepsilon=1$, corruption $c=0.5$. _(Right)_
Privacy level $\varepsilon=\sqrt{n}/10$, corruption $c=0.4$.  Figure 8:
Comparing CelebA women/men images while varying the corruption parameter $c$.
We set the sample sizes $m=n=500$, and privacy parameter $\varepsilon$ as
follows: _(Left)_ Privacy level $\varepsilon=10/\sqrt{n}$. _(Middle)_ Privacy
level $\varepsilon=1$. _(Right)_ Privacy level $\varepsilon=\sqrt{n}/10$.

###  6.4 Analysis of Main Experimental Results

We now analyze the results of the perturbed uniform and CelebA experiments
presented in Sections 6.2 and 6.3, respectively.

##### Overview.

First and foremost, we observe that dpMMD achieves significantly higher power
than all other tests across all privacy regimes. This trend remains consistent
when varying the other parameters $\\{$privacy, sample sizes, dimension,
corruption$\\}$. In the high and mid privacy regimes illustrated in Figures 2,
3 and 4, only dpMMD is able to detect the perturbation on the uniform
distribution. In the high and mid privacy regimes presented in Figures 6, 7
and 8, dpMMD clearly outperforms all other tests but TOT MMD and SARRM MMD
eventually manage to detect the CelebA image distributional shift. In the low
privacy regime, dpMMD also achieves the highest power, which is eventually
matched by U-stat dpMMD as the privacy parameter increases.

##### Varying privacy and free privacy.

As can be seen in Figures 2 and 6, increasing $\varepsilon$ (_i.e._ , lowering
privacy) first leads to an increase in power. However, we observe that, after
some threshold, further increasing $\varepsilon$ does not increase the power
of dpMMD. Essentially, in this low privacy regime, dpMMD already attains the
power of the non-private MMD test and the (low) privacy guarantee then comes
for free. This empirical observation is also supported by our theoretical
findings that the non-private MMD and $L_{2}$ optimal uniform separation rates
are attained by dpMMD in the low privacy regime (see Theorems 7 and 9).

##### Varying privacy for U-stat dpMMD.

Furthermore, Figures 2 and 6 shows that the dpMMD test using the U-statistic
is powerless in the high and mid privacy regimes, but it eventually reaches
the power of dpMMD (using the V-statistic) in the low privacy regime, which is
theoretically justified by our suboptimality result (Theorem 10) for dpMMD
based on the U-statistic and by the fact that the non-private MMD U-statistic
test is minimax rate optimal (Schrab et al.,, 2023).

##### Varying the sample size.

When varying the sample sizes $m=n$ in Figures 3 and 7 with fixed high/mid/low
privacy level $\varepsilon\in\\{10/\sqrt{n},1,\sqrt{n}/10\\}$, the power of
all tests naturally increase, while the power of dpMMD increases faster than
the others. In the low privacy regime of Figure 3, we see that the power of
U-stat dpMMD approaches that of dpMMD as the same size increases. This can be
explained by the aforementioned reasoning along with the observation that the
privacy level $\varepsilon=\sqrt{n}/10$ also increases (_i.e._ , lower
privacy) in this setting.

##### Varying the problem difficulty.

In Figures 4 and 8, the sample sizes and privacy levels are fixed while the
difficulty of the problem is varied. For the perturbed uniform experiment, as
the dimension of the problem increases, the perturbation becomes more
difficult to detect and hence the power decreases for each test. We observe
nonetheless that the power of dpMMD deteriorates at a much slower rate than
the one of the other tests. For the CelebA experiment, the test power
increases with the corruption parameter of the image sampler, with dpMMD
always achieving the highest power, followed by either TOT MMD or SARRM MMD.

##### The power of kernel methods.

We end this discussion with some remarks regarding the CelebA experiments of
Section 6.3. First, we emphasize again that the quadratic-time kernel tests
run swiftly on the full-resolution CelebA image data, which has $116,412$
pixels per image. Second, given the large diversity of faces, poses and
backgrounds (see Figure 5), it is remarkable that dpMMD is able to detect such
complicated differences in high-dimensional image distributions while using an
off-the-shelf Gaussian kernel which entirely ignores the image structure and
simply averages distances between pixel values at the same locations. Third,
the fact that such complex testing problems can now be solved while
guaranteeing differential privacy is extremely important, especially when
dealing with data as personal and sensitive as facial data. The DP constraint
essentially guarantees privacy in the sense that confidential information
about a single face image cannot be recovered. Fourth, we stress that the
power results reported are meaningful and that dpMMD truly detects the
difference between CelebA images of women and men, which is justified as type
I error control is correctly retained (Section C.3). We believe these CelebA
experiments strongly advocate the use of tests leveraging kernel methods for
differential privacy.

###  6.5 Analysis of Additional Experimental Results

Before concluding the paper, we briefly summarize the results of the
additional experiments in Appendix C.

##### Independence testing.

In the HSIC testing experiments of Section C.1, we consider the problem of
detecting the dependence of variables with the perturbed uniform joint density
introduced in Section 6.2, and hence with uniform marginal densities. This
setting is of particular interest as this corresponds to the joint density
used in deriving the non-private $L_{2}$ minimax independence lower bound over
Sobolev balls by Albert et al., (2022). The exact same power dynamics and
aforementioned observations, which hold for the MMD-based tests, also apply to
the HSIC variants of all tests, and indeed dpHSIC achieves substantially
higher power than all the other tests.

##### High-signal & low-privacy alternatives.

We remark that Naive dpMMD and TCS-ME have almost no power against the
alternatives considered in the previous subsections. This is not because these
tests are faulty but because the signal is too weak to be detected by these
tests. In fact, the Naive dpMMD test with privacy $\varepsilon$ is exactly
equivalent to the dpMMD test with privacy $2/(B\varepsilon)$ (recall $B=2000$
permutations), which justifies the poor performance of Naive dpMMD. For a
sanity check, we consider ‘high-signal’ & ‘low-privacy’ alternatives in
Section C.2 and show that dpMMD and TCS-ME are indeed able to detect the
difference when the signal is large enough. The results can be found in Figure
12.

##### Type I error control.

In Section C.3, we run experiments under the null hypothesis. This corresponds
to no perturbation for the perturbed uniform two-sample and independence
settings (amplitude $a=0$), and to no corruption in the CelebA sampler
(corruption $c=0$). All tests are well-calibrated with empirical level around
$\alpha$ under all settings considered, except TCS-ME. Indeed, we observe in
Figure 14 that when testing two samples from a 100-dimensional uniform
distribution, TCS-ME fails to control the type I error rate, which is
estimated to be around $0.5=10\alpha$ instead of around $\alpha=0.05$. This
depicts a major limitation of TCS-ME especially in high-dimensional settings.
However, we point out that this test is well-calibrated in the settings of
Section 6.2, ensuring a fair comparison of power therein.

##  7 Discussion

In this work, we have proposed differentially private permutation tests and
examined their theoretical and empirical performance. The prior work on
differentially private testing has often been limited in its practical
applicability, being restricted to discrete data or relying on asymptotic
theory that does not offer confidence in finite sample scenarios. Our
permutation framework addresses these challenges by introducing practical
tools, which are applicable to diverse settings with finite sample guarantees
for both type I error control and differential privacy. In addition to general
power properties, we have provided a detailed power analysis of the proposed
method in the context of kernel testing, and showed that the proposed private
kernel tests achieve minimax optimal power in terms of kernel metrics in all
privacy regimes. We have also analyzed the testing power against nonparametric
$L_{2}$ alternatives, and established minimum separation rates in all privacy
regimes. Finally, we have conducted an extensive simulation study to validate
our theoretical findings as well as to highlight the practical value of our
approach.

Our work raises several intriguing open questions that deserve further
investigation, as outlined below.

  * •

Beyond Global DP. Our work focuses on global
$(\varepsilon,\delta)$-differential privacy along with the Laplace mechanism.
While global DP is a widely used as an effective concept of data protection,
other privacy concepts may be more suitable depending on the context and
requirements. Exploring the development of private permutation tests
applicable to other privacy concepts or based on other privacy mechanisms
would be an interesting direction for future investigation.

  * •

Other Applications. We illustrated the proposed method in the context of two-
sample and independence testing, with a focus on kernel-based tests. The
permutation method has been employed successfully in other statistical
problems such as testing for regression coefficients (DiCiccio and Romano,,
2017) and conditional independence testing (Kim et al., 2022b, ). It is
therefore compelling to broaden the application of our framework by tackling
other statistical problems in privacy settings. Future work can also focus on
conducting a detailed analysis of the private permutation test using non-
kernel test statistics.

  * •

Variants of dpMMD and dpHSIC. In our analysis, we utilized the plug-in
estimators of MMD and HSIC based on single kernels. In recent years,
significant progress has been made to reduce the computational complexity
(Schrab et al.,, 2022; Domingo-Enrich et al.,, 2023) as well as to avoid the
bandwidth selection issue (Schrab et al.,, 2023; Biggs et al.,, 2023) of this
standard approach. Considering these developments, a promising avenue for
future research would be to extend these recent advances to privacy-preserving
settings.

  * •

Minimax Separation under DP. Our results in Section 5.2 provide upper bounds
for the minimax separation rates in terms of the $L_{2}$ metric, which match
the lower bound in low privacy regimes. However, as mentioned earlier, it is
unknown whether they are still tight in mid/high privacy regimes.
Consequently, future work could focus on addressing this question by
establishing matching lower bounds or sharper upper bounds. More broadly, it
would be interesting to establish minimax separation rates under DP in terms
of other metrics as well. We leave these important questions to future work.

## References

  * Acharya et al., (2019) Acharya, J., Canonne, C., Freitag, C., and Tyagi, H. (2019).  Test without trust: Optimal locally private distribution testing.  In The 22nd International Conference on Artificial Intelligence and Statistics.
  * Acharya et al., (2018) Acharya, J., Sun, Z., and Zhang, H. (2018).  Differentially private testing of identity and closeness of discrete distributions.  Advances in Neural Information Processing Systems, 31.
  * Acharya et al., (2021) Acharya, J., Sun, Z., and Zhang, H. (2021).  Differentially Private Assouad, Fano, and Le Cam.  In Algorithmic Learning Theory, pages 48–78. PMLR.
  * Alabi and Vadhan, (2022) Alabi, D. and Vadhan, S. (2022).  Hypothesis testing for differentially private linear regression.  Advances in Neural Information Processing Systems, 35:14196–14209.
  * Albert et al., (2022) Albert, M., Laurent, B., Marrel, A., and Meynaoui, A. (2022).  Adaptive test of independence based on HSIC measures.  The Annals of Statistics, 50(2):858–879.
  * Aliakbarpour et al., (2019) Aliakbarpour, M., Diakonikolas, I., Kane, D., and Rubinfeld, R. (2019).  Private Testing of Distributions via Sample Permutations.  Advances in Neural Information Processing Systems, 32.
  * Aliakbarpour et al., (2018) Aliakbarpour, M., Diakonikolas, I., and Rubinfeld, R. (2018).  Differentially Private Identity and Closeness Testing of Discrete Distributions.  In International Conference on Machine Learning, pages 169–178.
  * Apple, (2017) Apple (2017).  Learning with Privacy at Scale.  https://machinelearning.apple.com/research/learning-with-privacy-at-scale.
  * Arias-Castro et al., (2018) Arias-Castro, E., Pelletier, B., and Saligrama, V. (2018).  Remember the curse of dimensionality: The case of goodness-of-fit testing in arbitrary dimension.  Journal of Nonparametric Statistics, 30(2):448–471.
  * Awan and Slavković, (2018) Awan, J. and Slavković, A. (2018).  Differentially Private Uniformly Most Powerful Tests for Binomial Data.  Advances in Neural Information Processing Systems, 31.
  * Balle and Wang, (2018) Balle, B. and Wang, Y. (2018).  Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising.  In Dy, J. G. and Krause, A., editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 403–412. PMLR.
  * Baraud, (2002) Baraud, Y. (2002).  Non-asymptotic minimax rates of testing in signal detection.  Bernoulli, 8(5):577–606.
  * Bartlett and Mendelson, (2002) Bartlett, P. L. and Mendelson, S. (2002).  Rademacher and Gaussian complexities: Risk bounds and structural results.  Journal of Machine Learning Research, 3(Nov):463–482.
  * Berrett and Butucea, (2020) Berrett, T. and Butucea, C. (2020).  Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms.  Advances in Neural Information Processing Systems, 33:3164–3173.
  * Berrett et al., (2021) Berrett, T. B., Kontoyiannis, I., and Samworth, R. J. (2021).  Optimal rates for independence testing via U-statistic permutation tests.  The Annals of Statistics, 49(5):2457–2490.
  * Biggs et al., (2023) Biggs, F., Schrab, A., and Gretton, A. (2023).  MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting.  arXiv preprint arXiv:2306.08777.
  * Boucheron et al., (2013) Boucheron, S., Lugosi, G., and Massart, P. (2013).  Concentration inequalities: A nonasymptotic theory of independence.  Oxford university press.
  * Bun and Steinke, (2016) Bun, M. and Steinke, T. (2016).  Concentrated differential privacy: Simplifications, extensions, and lower bounds.  In Theory of Cryptography Conference, pages 635–658. Springer.
  * Cai et al., (2017) Cai, B., Daskalakis, C., and Kamath, G. (2017).  Priv’it: Private and sample efficient identity testing.  In International Conference on Machine Learning, pages 635–644. PMLR.
  * Cai et al., (2021) Cai, T. T., Wang, Y., and Zhang, L. (2021).  The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy.  The Annals of Statistics, 49(5):2825–2850.
  * Campbell et al., (2018) Campbell, Z., Bray, A., Ritz, A., and Groce, A. (2018).  Differentially private ANOVA testing.  In 2018 1st International Conference on Data Intelligence and Security (ICDIS), pages 281–285. IEEE.
  * Canonne, (2022) Canonne, C. L. (2022).  Topics and Techniques in Distribution Testing: A Biased but Representative Sample.  Foundations and Trends® in Communications and Information Theory, 19(6):1032–1198.
  * Canonne et al., (2019) Canonne, C. L., Kamath, G., McMillan, A., Smith, A., and Ullman, J. (2019).  The structure of optimal private tests for simple hypotheses.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 310–321.
  * Canonne et al., (2020) Canonne, C. L., Kamath, G., McMillan, A., Ullman, J., and Zakynthinou, L. (2020).  Private identity testing for high-dimensional distributions.  Advances in Neural Information Processing Systems, 33:10099–10111.
  * Couch et al., (2019) Couch, S., Kazan, Z., Shi, K., Bray, A., and Groce, A. (2019).  Differentially private nonparametric hypothesis testing.  In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pages 737–751.
  * Diakonikolas et al., (2021) Diakonikolas, I., Gouleakis, T., Kane, D. M., Peebles, J., and Price, E. (2021).  Optimal testing of discrete distributions with high probability.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 542–555.
  * Diakonikolas et al., (2015) Diakonikolas, I., Hardt, M., and Schmidt, L. (2015).  Differentially private learning of structured discrete distributions.  Advances in Neural Information Processing Systems, 28.
  * Diakonikolas and Kane, (2016) Diakonikolas, I. and Kane, D. M. (2016).  A new approach for testing properties of discrete distributions.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 685–694. IEEE.
  * DiCiccio and Romano, (2017) DiCiccio, C. J. and Romano, J. P. (2017).  Robust permutation tests for correlation and regression coefficients.  Journal of the American Statistical Association, 112(519):1211–1220.
  * Ding et al., (2017) Ding, B., Kulkarni, J., and Yekhanin, S. (2017).  Collecting Telemetry Data Privately.  Advances in Neural Information Processing Systems, 30.
  * Dobriban, (2022) Dobriban, E. (2022).  Consistency of invariance-based randomization tests.  The Annals of Statistics, 50(4):2443–2466.
  * Domingo-Enrich et al., (2023) Domingo-Enrich, C., Dwivedi, R., and Mackey, L. (2023).  Compress then test: Powerful kernel testing in near-linear time.  In International Conference on Artificial Intelligence and Statistics.
  * Dong et al., (2022) Dong, J., Roth, A., and Su, W. J. (2022).  Gaussian differential privacy.  Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3–37.
  * Dubois et al., (2023) Dubois, A., Berrett, T. B., and Butucea, C. (2023).  Goodness-of-Fit Testing for Hölder Continuous Densities Under Local Differential Privacy.  In Foundations of Modern Statistics, pages 53–119. Springer International Publishing.
  * Duchi et al., (2018) Duchi, J. C., Jordan, M. I., and Wainwright, M. J. (2018).  Minimax optimal procedures for locally private estimation.  Journal of the American Statistical Association, 113(521):182–201.
  * (36) Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., and Naor, M. (2006a).  Our data, ourselves: Privacy via distributed noise generation.  In Advances in Cryptology-EUROCRYPT 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28-June 1, 2006. Proceedings 25, pages 486–503. Springer.
  * (37) Dwork, C., McSherry, F., Nissim, K., and Smith, A. (2006b).  Calibrating noise to sensitivity in private data analysis.  In Theory of Cryptography Conference, pages 265–284. Springer.
  * Dwork et al., (2014) Dwork, C., Roth, A., et al. (2014).  The Algorithmic Foundations of Differential Privacy.  Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407.
  * Erlingsson et al., (2014) Erlingsson, Ú., Pihur, V., and Korolova, A. (2014).  Rappor: Randomized aggregatable privacy-preserving ordinal response.  In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pages 1054–1067.
  * Fernández and Rivera, (2022) Fernández, T. and Rivera, N. (2022).  A general framework for the analysis of kernel-based tests.  arXiv preprint arXiv:2209.00124.
  * Fienberg et al., (2011) Fienberg, S. E., Slavkovic, A., and Uhler, C. (2011).  Privacy preserving GWAS data sharing.  In 2011 IEEE 11th International Conference on Data Mining Workshops, pages 628–635. IEEE.
  * Friedberg and Rogers, (2023) Friedberg, R. and Rogers, R. (2023).  Privacy aware experimentation over sensitive groups: A general chi square approach.  In Workshop on Algorithmic Fairness through the Lens of Causality and Privacy, pages 23–66. PMLR.
  * Gaboardi et al., (2016) Gaboardi, M., Lim, H., Rogers, R., and Vadhan, S. (2016).  Differentially private chi-squared hypothesis testing: Goodness of fit and independence testing.  In International Conference on Machine Learning, pages 2111–2120. PMLR.
  * Gaboardi and Rogers, (2018) Gaboardi, M. and Rogers, R. (2018).  Local private hypothesis testing: Chi-square tests.  In International Conference on Machine Learning, pages 1626–1635. PMLR.
  * Gretton, (2015) Gretton, A. (2015).  A simpler condition for consistency of a kernel independence test.  arXiv preprint arXiv:1501.06103.
  * Gretton et al., (2012) Gretton, A., Borgwardt, K. M., Rasch, M. J., Schölkopf, B., and Smola, A. (2012).  A kernel two-sample test.  The Journal of Machine Learning Research, 13(1):723–773.
  * Gretton et al., (2005) Gretton, A., Bousquet, O., Smola, A., and Schölkopf, B. (2005).  Measuring statistical dependence with Hilbert-Schmidt norms.  In International Conference on Algorithmic Learning Theory, pages 63–77. Springer.
  * Holohan et al., (2015) Holohan, N., Leith, D. J., and Mason, O. (2015).  Differential Privacy in Metric Spaces: Numerical, Categorical and Functional Data Under the One Roof.  Information Sciences, 305:256–268.
  * Ingster et al., (2003) Ingster, Y., Ingster, J. I., and Suslina, I. (2003).  Nonparametric Goodness-of-Fit Testing under Gaussian Models.  Springer.
  * Ingster, (1994) Ingster, Y. I. (1994).  Minimax detection of a signal in $\ell_{p}$ metrics.  Journal of Mathematical Sciences, 68(4):503–515.
  * Ingster, (2000) Ingster, Y. I. (2000).  Adaptive chi-square tests.  Journal of Mathematical Sciences, 99(2):1110–1119.
  * Jitkrittum et al., (2016) Jitkrittum, W., Szabó, Z., Chwialkowski, K. P., and Gretton, A. (2016).  Interpretable distribution features with maximum testing power.  In Lee, D. D., Sugiyama, M., von Luxburg, U., Guyon, I., and Garnett, R., editors, Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 181–189.
  * Kakizaki et al., (2017) Kakizaki, K., Fukuchi, K., and Sakuma, J. (2017).  Differentially Private Chi-squared Test by Unit Circle Mechanism.  In International Conference on Machine Learning, pages 1761–1770. PMLR.
  * Kalemaj et al., (2023) Kalemaj, I., Kasiviswanathan, S. P., and Ramdas, A. (2023).  Differentially private conditional independence testing.  arXiv preprint arXiv:2306.06721.
  * Kamath et al., (2019) Kamath, G., Li, J., Singhal, V., and Ullman, J. (2019).  Privately learning high-dimensional distributions.  In Conference on Learning Theory, pages 1853–1902. PMLR.
  * Kamath et al., (2020) Kamath, G., Singhal, V., and Ullman, J. (2020).  Private mean estimation of heavy-tailed distributions.  In Conference on Learning Theory, pages 2204–2235. PMLR.
  * Kamath and Ullman, (2020) Kamath, G. and Ullman, J. (2020).  A primer on private statistics.  arXiv preprint arXiv:2005.00010.
  * Kazan et al., (2023) Kazan, Z., Shi, K., Groce, A., and Bray, A. (2023).  The Test of Tests: A Framework For Differentially Private Hypothesis Testing.  arXiv preprint arXiv:2302.04260.
  * Kim, (2021) Kim, I. (2021).  Comparing a large number of multivariate distributions.  Bernoulli, 27(1):419–441.
  * (60) Kim, I., Balakrishnan, S., and Wasserman, L. (2022a).  Minimax optimality of permutation tests.  The Annals of Statistics (arXiv:2003.13208), 50(1):225–251.
  * (61) Kim, I., Neykov, M., Balakrishnan, S., and Wasserman, L. (2022b).  Local permutation tests for conditional independence.  The Annals of Statistics, 50(6):3388–3414.
  * Kim et al., (2023) Kim, I., Neykov, M., Balakrishnan, S., and Wasserman, L. (2023).  Conditional Independence Testing for Discrete Distributions: Beyond $\chi^{2}$-and $G$-tests.  arXiv preprint arXiv:2308.05373.
  * Kusner et al., (2016) Kusner, M. J., Sun, Y., Sridharan, K., and Weinberger, K. Q. (2016).  Private causal inference.  In Artificial Intelligence and Statistics, pages 1308–1317. PMLR.
  * Lam-Weil et al., (2022) Lam-Weil, J., Laurent, B., and Loubes, J.-M. (2022).  Minimax optimal goodness-of-fit testing for densities and multinomials under a local differential privacy constraint.  Bernoulli, 28(1):579–600.
  * Le Cam, (1973) Le Cam, L. (1973).  Convergence of Estimates Under Dimensionality Restrictions.  The Annals of Statistics, 1(1):38–53.
  * Le Cam, (2012) Le Cam, L. (2012).  Asymptotic Methods in Statistical Decision Theory.  Springer Science & Business Media.
  * Lehmann and Romano, (2005) Lehmann, E. L. and Romano, J. P. (2005).  Testing Statistical Hypotheses, volume 3.  Springer.
  * Li and Yuan, (2019) Li, T. and Yuan, M. (2019).  On the optimality of Gaussian kernel based nonparametric tests against smooth alternatives.  arXiv preprint arXiv:1909.03302.
  * Liao et al., (2017) Liao, J., Sankar, L., Tan, V. Y., and du Pin Calmon, F. (2017).  Hypothesis testing under mutual information privacy constraints in the high privacy regime.  IEEE Transactions on Information Forensics and Security, 13(4):1058–1071.