# Federated Nonparametric Hypothesis Testing with Differential Privacy
Constraints: Optimal Rates and Adaptive Tests

T. Tony<EMAIL_ADDRESS>[ Abhinav
<EMAIL_ADDRESS>[ Lasse
<EMAIL_ADDRESS>[ Department of Statistics and Data
Science, University of Pennsylvaniapresep=, ]e1,e2,e3  T. Tony
<EMAIL_ADDRESS>[ Abhinav
<EMAIL_ADDRESS>[ Lasse
<EMAIL_ADDRESS>[ Department of Statistics and Data
Science, University of Pennsylvaniapresep=, ]e1,e2,e3

(August 28, 2024)

# Supplementary Material to “Federated Nonparametric Hypothesis Testing with
Differential Privacy Constraints: Optimal Rates and Adaptive Tests”

T. Tony<EMAIL_ADDRESS>[ Abhinav
<EMAIL_ADDRESS>[ Lasse
<EMAIL_ADDRESS>[ Department of Statistics and Data
Science, University of Pennsylvaniapresep=, ]e1,e2,e3  T. Tony
<EMAIL_ADDRESS>[ Abhinav
<EMAIL_ADDRESS>[ Lasse
<EMAIL_ADDRESS>[ Department of Statistics and Data
Science, University of Pennsylvaniapresep=, ]e1,e2,e3

(August 28, 2024)

###### Abstract

Federated learning has attracted significant recent attention due to its
applicability across a wide range of settings where data is collected and
analyzed across disparate locations. In this paper, we study federated
nonparametric goodness-of-fit testing in the white-noise-with-drift model
under distributed differential privacy (DP) constraints.

We first establish matching lower and upper bounds, up to a logarithmic
factor, on the minimax separation rate. This optimal rate serves as a
benchmark for the difficulty of the testing problem, factoring in model
characteristics such as the number of observations, noise level, and
regularity of the signal class, along with the strictness of the
$(\epsilon,\delta)$-DP requirement. The results demonstrate interesting and
novel phase transition phenomena. Furthermore, the results reveal an
interesting phenomenon that distributed one-shot protocols with access to
shared randomness outperform those without access to shared randomness. We
also construct a data-driven testing procedure that possesses the ability to
adapt to an unknown regularity parameter over a large collection of function
classes with minimal additional cost, all while maintaining adherence to the
same set of DP constraints.
Keywords: Distributed computation; Differential privacy; Federated learning;
Nonparametric goodness-of-fit testing,

###### Abstract

In this supplement, we present the detailed proofs for the main results in the
paper “Federated Nonparametric Hypothesis Testing with Differential Privacy
Constraints: Optimal Rates and Adaptive Tests”.

62G10,

62C20,

68P27,

Federated learning,

Differential privacy,

Nonparametric goodness-of-fit testing,

Distributed inference,

62G10,

62C20,

68P27,

Federated learning,

Differential privacy,

Nonparametric goodness-of-fit testing,

Distributed inference,

###### keywords:

[class=MSC]

###### keywords:

###### keywords:

[class=MSC2020]

###### keywords:

, and

##  1 Introduction

Federated learning is a collaborative distributed machine learning technique
designed to address data governance and privacy concerns. It facilitates
organizations or groups to collectively train a shared global model without
the need to expose raw data externally. Federated learning has garnered
increasing attention due to its applicability across a wide range of settings
where data is collected and analyzed across disparate locations. This includes
scenarios like medical data dispersed among different hospitals, financial
customer data stored across various branches or databases, and the utilization
of federated learning within user networks in modern technologies such as
smartphones or self-driving cars. See, for example, [59, 52, 44, 13, 68]. In
such contexts, privacy concerns often impede direct data pooling, making the
development of efficient statistical inference methods that preserve privacy
and harness the collective power of distributed data essential.

In this paper, we investigate federated nonparametric goodness-of-fit testing
under distributed differential privacy (DP) constraints. Nonparametric
hypothesis testing, a fundamental statistical problem, has been extensively
studied in conventional settings, with a rich body of classical literature
examining theoretically optimal performance. DP, introduced by Dwork et al.
(2006), serves as a mathematical guarantee determining whether results or
datasets can be deemed “privacy-preserving" and thus openly published. Many
differentially private statistical methods have since been developed. See, for
example, [11, 37, 38]. While several other privacy frameworks exist, DP holds
a prominent position both theoretically and practically, finding application
within industry giants like Google [40], Microsoft [32], Apple [78], as well
as governmental entities such as the US Census Bureau [70].

DP may significantly impact the quality of statistical inference, particularly
in testing problems where it may diminish statistical power that could be
obtained with complete data availability. In the present paper, we quantify
the cost of privacy in the canonical nonparametric goodness-of-fit testing
setting, delineating the theoretical limits of performance achievable under DP
constraints and developing methods that attain optimal performance.
Contrasting our results with those derived for federated nonparametric
estimation under DP [20], we observe that the differences persist and are
exacerbated under privacy constraints, highlighting the unique challenges
posed by privacy preservation in both testing and estimation contexts.

We first establish the minimax separation rate for the nonparametric goodness-
of-fit testing problem and construct optimal tests in the oracle setting where
the regularity parameters are known. The minimax separation rate serves as a
benchmark for the difficulty of the testing problem. However, the regularity
parameters are typically in applications. A natural question is: Without the
knowledge of the regularity parameters, is it possible to construct a test
that is as good as when the parameters are known? This is a question about
adaptation, which has been a major goal in nonparametric statistics. We
construct a data-driven test and show that the proposed method can adapt to
unknown regularity parameters with minimal additional cost while adhering the
same DP restrictions.

###  1.1 Federated privacy-constrained testing

We begin by formally introducing the general framework of federated inference
under distributed DP constraints. Consider a family of probability measures
$\\{P_{f}\\}_{f\in{\mathcal{F}}}$ on the measurable space
$(\mathcal{X},\mathscr{X})$, parameterized by $f\in{\mathcal{F}}$. We consider
a setting where $N=mn$ i.i.d. observations are drawn from a distribution
$P_{f}$ and distributed across $m$ servers. Each server $j=1,\dots,m$ holding
an equal amount ($n$ many) observations.

Let us denote by $X^{(j)}=(X^{(j)}_{i})_{i=1}^{n}$ the $n$ realizations from
$P_{f}$ on the $j$-th server. Based on $X^{(j)}$, each server outputs a
(randomized) transcript $Y^{(j)}$ to the central server that satisfies the
privacy constraint. The central server, utilizing all transcripts
$Y:=(Y^{(1)},\dots,Y^{(m)})$, decides between a null hypothesis and an
alternative hypothesis, through means of a test $T=T(Y)$. Since we are
concerned with testing between a null and alternative hypothesis, we shall
consider the decision space $\\{0,1\\}$, where $0$ corresponds to do not
reject and $1$ with reject. A _test_ is then simply to be understood as a
statistic taking values in $\\{0,1\\}$. Figure 1 gives an illustration of a
federated $(\epsilon,\delta)$-DP-constrained testing procedure.

Figure 1: Illustration of federated $(\epsilon,\delta)$-DP-constrained
testing.

The transcript $Y^{(j)}$ satisfies an $(\epsilon,\delta)$-DP constraint,
which, loosely speaking, means that the transcript $Y^{(j)}$ cannot differ too
much depending on whether a specific individual is in the data set or not.
This is achieved through randomization, which is independent of the data. We
will consider two types of sources for randomization; independently among the
servers or through a shared source of randomness $U$ (e.g., the same random
seed). Formally, shared source of randomness means that the law of the
transcript is given by a distribution conditionally on $X^{(j)}$ and $U$,
$A\mapsto{\mathbb{P}}(Y^{(j)}\in A|X^{(j)},U)$, defined on a measurable space
$({\mathcal{Y}},\mathscr{Y})$. The presence of shared randomness is a slight,
but important extension of the distributed protocols where $Y^{(j)}$ is
allowed to be random only through locally generated randomness. See further
discussion below and in Section 2. To assure that the source of shared
randomness does not erode the notion of privacy, only the local source of
randomness is used in the privacy mechanism, i.e. to guarantee privacy. We
formalize this as follows.

We shall call two data sets $x,x^{\prime}\in\mathcal{X}^{n}$ _neighboring_ if
they differ in one individual datum. That is, they are at most one apart in
_Hamming distance_ (see Section 1.6). A DP constraint is then defined as
follows.

######  Definition 1.

The transcript $Y^{(j)}$ is $(\epsilon,\delta)$-differentially private
($(\epsilon,\delta)$-DP) if for all $A\in\mathscr{Y}^{(j)}$,
$u\in{\mathcal{U}}$ and neighboring data sets $x,x^{\prime}\in\mathcal{X}^{n}$
differing in one individual datum it holds that

${\mathbb{P}}\left(Y^{(j)}\in A|X^{(j)}=x,U=u\right)\leq
e^{\epsilon}{\mathbb{P}}\left(Y^{(j)}\in
A|X^{(j)}=x^{\prime},U=u\right)+\delta.$ (1)

The above setting is concerned with distributed protocols for scenarios where
multiple parties hold sensitive data and each publishes a differentially
private summary, without sharing raw data between them. This approach is
common in cases like separate studies by different hospitals on the same
population, where privacy concerns prevent direct data pooling. We note that,
in the above definition, the outcome of the shared source of randomness $U$
does not diminish the privacy guarantee, even when it is publicly available.
This is because the shared randomness is not used in the privacy mechanism,
but as a means to enhance coordination between the transcripts, which allows
the transcripts to be more informative about the underlying signal whilst each
transcript is effectively sharing less information about their underlying
individual data.

Formally, having access to shared randomness means that $U$ can be defined on
some probability space $({\mathcal{U}},\mathscr{U},{\mathbb{P}}^{U})$, such
that $U$ is independent of the data (i.e. by taking the appropriate product
space for ${\mathbb{P}}^{X,U}$). Having no access to shared randomness
effectively corresponds to considering $U$ to be a degenerate random variable,
or $\mathscr{U}=\\{\emptyset,{\mathcal{U}}\\}$. In order to stream line the
notation between these two setups, we shall refer to the triplet
$(T,\\{\left({\mathbb{P}}^{Y^{(j)}|X^{(j)}=x,U=u}\right)_{x\in{\mathcal{X}}^{n},u\in{\mathcal{U}}}\\}_{j=1}^{m},({\mathcal{U}},\mathscr{U},{\mathbb{P}}^{U}))$
as a _$(\epsilon,\delta)$ -DP shared randomness distributed testing protocol_
with
$\\{\left({\mathbb{P}}^{Y^{(j)}|X^{(j)}=x,U=u}\right)_{x\in{\mathcal{X}}^{n},u\in{\mathcal{U}}}\\}_{j=1}^{m}$
satisfying Definition 1 for general $U$ (i.e. general
$({\mathcal{U}},\mathscr{U},{\mathbb{P}}^{U})$). The class of such triplets,
but with $\mathscr{U}=\\{\emptyset,{\mathcal{U}}\\}$, shall be referred to as
__$(\epsilon,\delta)$_ -DP local randomness distributed testing protocols_. We
shall denote these classes as $\mathscr{T}^{(\epsilon,\delta)}_{\texttt{SHR}}$
and $\mathscr{T}^{(\epsilon,\delta)}_{\texttt{LR}}$, respectively, and note
that the former is a superset of the latter.

###  1.2 Problem formulation

The white-noise-with-drift model serves as a benchmark model for nonparametric
testing and has been extensively studied outside of the DP setting, see [41,
46, 56, 75, 45]. Furthermore, the problem bares a close relationship with
“classical” nonparametric goodness-of-fit testing in the sense of [10, 73, 30,
84] and other nonparametric testing problems through asymptotic equivalence,
see Section 1.4 in [47] and references therein.

In the distributed setting, the $j=1,\dots,m$ machines each observe
$i=1,\dots,n$ i.i.d, $X^{(j)}_{i}$ taking values in ${\mathcal{X}}\subset
L_{2}[0,1]$ and subject to the stochastic differential equation

$dX^{(j)}_{t;i}=f(t)dt+\sigma dW_{t;i}^{(j)}$ (2)

under $P_{f}$, with $t\mapsto W^{(1)}_{t;i},\dots,t\mapsto W^{(m)}_{t;i}$
i.i.d. Brownian motions and $f\in L_{2}[0,1]$ for $i=1,\dots,n$, with
$\sigma>0$ the known noise level for each observation. For notational
convenience, we shall use $N=mn$ throughout the paper and will consider
asymptotic regimes where $N\to\infty$. We note that, when $m=1$, we recover
the classical white-noise-with-drift model.

We consider the canonical signal detection problem, where the goal is to test
for the presence or absence of the “signal component” $f$. More formally, we
consider testing the null hypothesis $H_{0}:f\equiv 0$ against the alternative
hypotheses that

$f\in H_{\rho}^{s,R}\equiv
H_{\rho}^{s,R,p,q}:=\left\\{f\in{\mathcal{B}}^{{s},R}_{p,q}:\|f\|_{L_{2}}\geq\rho\text{
and }\|f\|_{{\mathcal{B}}^{s}_{p,q}}\leq R\right\\}.$ (3)

Here, the alternative hypothesis consists of ${s}$-smooth functions in a Besov
space, with $\|\cdot\|_{{\mathcal{B}}^{s}_{p,q}}$ denoting the
Besov-$({s},p,q)$-norm and ${\mathcal{B}}^{{s},R}_{p,q}\subset L_{2}[0,1]$
corresponds to the Besov ball of radius $R$, see Section E in the
Supplementary Material [21] for the definitions. Besov spaces are a very rich
class of function spaces. They include many traditional smoothness spaces such
as Hölder and Sobolev spaces as special cases. We refer the reader to [80] for
a detailed discussion on Besov spaces.

Using a wavelet transform, the above testing problem is equivalent the
observations under the Gaussian sequence model, where each of the
$j=1,\dots,m$ machines observes $i=1,\dots,n$ observations
$X^{(j)}_{i}:=(X_{lk;i}^{(j)})_{l\geq 1,k=1,\dots,2^{l}}$

$X_{lk;i}^{(j)}=f_{lk}+\sigma Z_{lk;i}^{(j)},$ (4)

where the $Z_{lk;i}^{(j)}$’s are i.i.d. standard Gaussian. The equivalent
hypotheses (3) in the sequence model simply follows by replacing the
$L_{2}[0,1]$-norm with the $\ell_{2}({\mathbb{N}})$-norm and the Besov space
${\mathcal{B}}^{{s},R}_{p,q}$ set to
$\\{f\in\ell_{2}({\mathbb{N}}):\|f\|_{{\mathcal{B}}^{s}_{p,q}}<\infty\\}$,
where the Besov norm on the sequence space $\ell_{2}({\mathbb{N}})$ is defined
as

$\|f\|_{{\mathcal{B}}^{s}_{p,q}}:=\begin{cases}\left(\underset{l=1}{\overset{\infty}{\sum}}\left(2^{l({s}+1/2-1/p)}\left\|(f_{lk})_{k=1}^{2^{l}}\right\|_{p}\right)^{q}\right)^{1/q}&\text{
for }1\leq q<\infty,\\\ \;\underset{l\geq
1}{\sup}\;2^{l({s}+1/2-1/p)}\left\|(f_{lk})_{k=1}^{2^{l}}\right\|_{p}&\text{
for }q=\infty.\end{cases}$ (5)

In other words, the results for testing under DP derived for the sequence
model of (4) with hypothesis (3) apply to the model described by (2) also,
with the same corresponding hypothesis.

Given a $\\{0,1\\}$ valued test $T$, where $T(Y)=1$ corresponds to rejecting
the null hypothesis, we define the testing risk sum of the type I and worst
case type II error over the alternative class;

${\mathcal{R}}(H_{\rho}^{s,R},T)={\mathbb{P}}_{0}T(Y)+\underset{{f}\in
H_{\rho}^{{s},R}}{\sup}\,{\mathbb{P}}_{f}T(Y).$

For the range of values $2\leq p\leq\infty$, $1\leq q\leq\infty$, the _minimax
separation rate_ in the unconstrained case is known to be
$\rho\asymp{(\sigma^{2}/N)}^{\frac{{s}}{2{s}+1/2}}$ (see e.g. [46]). This
means that, for $\rho\gg{(\sigma^{2}/N)}^{\frac{{s}}{2{s}+1/2}}$, there exists
a sequence of consistent tests $T\equiv T_{N}$ such that
${\mathcal{R}}(H_{\rho}^{s,R},T)\to 0$, whilst no such sequence of tests
exists whenever $\rho\ll{(\sigma^{2}/N)}^{\frac{{s}}{2{s}+1/2}}$.

The minimax separation rate captures how the testing problem becomes easier,
or more difficult, for different model characteristics. For distributed
$(\epsilon,\delta)$-DP testing protocols, the minimax separation rate depends
on the stringency of the privacy requirement, given by $\epsilon,\delta>0$, as
well as the model characteristics $m,n,s$ and $\sigma$. That is, we aim to
find $\rho$ as a function of $m,n,s,\sigma,\epsilon,\delta$, such that
$\underset{T\in\mathscr{T}^{(\epsilon,\delta)}}{\inf}{\mathcal{R}}(H_{\rho^{\prime},R}^{s,p,q},T)$
converges to either $0$ or $1$ depending on whether $\rho^{\prime}\ll\rho$ or
$\rho^{\prime}\gg\rho$. The class of alternatives under consideration are
subsets of the Besov ball ${\mathcal{B}}^{{s},R}_{p,q}$, where $2\leq
p<\infty$, $1\leq q\leq\infty$, which offers a framework for functions in (2)
with specific smoothness characteristics. Our results extend easily to the
case where $p=\infty$ at the cost of an additional logarithmic factor in the
rate and a few additional technicalities in the proofs.

###  1.3 Main results and our contribution

We quantify the difficulty of the federated testing problem outlined in the
previous section in terms of the minimax separation rate. To achieve this, we
present constructive distributed $(\epsilon,\delta)$-DP testing protocols that
achieve consistent testing for the problem described above for certain values
of $\rho$ (Theorem 4 in Section 3). Additionally, we establish matching
minimax lower bounds, up to logarithmic factor, for the testing risk (Theorem
5 in Section 5), providing a lower bound on the performance of distributed
$(\epsilon,\delta)$-DP testing protocols.

Our analysis uncovers several novel and intriguing findings, which we briefly
highlight here. The performance guarantees for the methods demonstrated in
Section 3, along with the lower bounds established in Section 5, indicate that
the distributed $(\epsilon,\delta)$-DP testing problem for the hypotheses
given in (3) is governed by the minimax separation rate (up to logarithmic
factors)

$\rho^{2}\asymp\left(\frac{\sigma^{2}}{mn}\right)^{\frac{2{s}}{2{s}+1/2}}+\left(\frac{\sigma^{2}}{mn^{3/2}\epsilon\sqrt{1\wedge
n\epsilon^{2}}}\right)^{\frac{2{s}}{2{s}+1}}\wedge\left(\left(\frac{\sigma^{2}}{\sqrt{m}n\sqrt{1\wedge
n\epsilon^{2}}}\right)^{\frac{2{s}}{2{s}+1/2}}+\frac{\sigma^{2}}{mn^{2}\epsilon^{2}}\right).$
(6)

The precise statement is deferred to Theorem 1.

The derived rate indicates that the distributed testing problem under privacy
constraints undergoes multiple phase transitions, resulting in different
regimes where $\epsilon$ affects the detection boundary differently.
Specifically, a smaller $\epsilon$, which implies a stronger privacy
guarantee, leads to an increased detection threshold. When $\delta$ decreases
polynomially with $N$, its impact on the detection boundary is limited to a
logarithmic factor, making its effect on the error rate minor compared to that
of $\epsilon$.

For $m=1$, our theorems establish the optimal separation rate for
nonparametric goodness-of-fit testing in the central DP setting, where all
data is available on a single machine. When $\epsilon\lesssim 1/\sqrt{N}$, the
privacy constraint affects the rate polynomially. In contrast, for
$\epsilon\gtrsim 1/\sqrt{N}$, the rate approximates the classical minimax
rate, up to logarithmic factors. Thus, the privacy constraint significantly
impacts the rate only when $\epsilon$ is relatively small compared to the
total number of observations $N$.

When $n=1$, we establish the optimal separation rate for the testing problem
in the local DP setting. Here, $\epsilon$ can be seen to have a pronounced
effect on the rate whenever $\epsilon\lesssim 1$.

In the general federated setting, with $m\gg 1$, we see that $m$ and $n$ come
into play with different powers in the minimax rate whenever
$\epsilon^{2}\lesssim\sigma^{\frac{1}{2s+1}}m^{\frac{1}{4s+1}}n^{\frac{1/2-2s}{4s+1}}$.
This means that if one distributes $N=mn$ observations across $m$ machines,
the task becomes more challenging as the $N$ observations are spread over a
greater number of machines, rather than having many observations on a smaller
number of machines. This phenomenon is also observed in the comparable
estimation setting of nonparametric regression, as recently investigated in
[20]. The phase transitions, however, are not observed in its estimation
counterpart. We provide a detailed interpretation of the phase transitions in
Section 2.

Our analysis also reveals that the minimax rate obtained in Theorem 1 becomes
worse without access to shared randomness. This is revealed by Theorem 1 in
Section 2. For certain values of $\epsilon$, we show that the performance is
strictly worse for methods that use only local randomness, and we exhibit
optimal local and shared randomness methods for these regimes, respectively,
in Sections 3.2 and 3.3. The shared source of randomness does not reveal any
information on the identity of the individuals comprising the sample, even
when it is publicly available. This means that the shared randomness does not
violate the privacy constraints, and the improvement in the rate is a direct
result of the shared randomness. We comment on this further in Section 2.

In many practical applications, the regularity parameter $s$ is unknown. In
Section 4, we extend the methods of Section 3 that attain the minimax rates,
up to additional logarithmic factors, when the regularity is unknown. That is,
establish that adaptive testing is possible under DP constraints with minimal
additional cost in terms of the separation rate.

The lower bound relies on several technical innovations, which are summarized
in Section 5. There, we provide a sketch of the proof and highlight the key
innovations. The optimal methods proposed in this paper rely on carefully
tailored private test statistics that extend to the adaptive setting with
minimal cost due to exponential concentration bounds. We describe the
construction of these tests in Sections 3 and 4.

###  1.4 Related Work

The literature on the theoretical properties of DP can be mostly divided into
those studying _local_ DP or _central_ DP. In local DP, the privacy protection
is applied at the level of individual data entries or observations, which
corresponds to $n=1$ in our setting. This is a stringent form of DP because
each item of data is independently given privacy protection. In the other
extreme, central DP, only the inference output needs to satisfy the DP
constraint (i.e. $m=1$ in our setting), meaning that if the output is a test,
only the final decision needs to satisfy a DP constraint.

Locally differential private estimation has been studied in the context of the
many-normal-means model, discrete distributions and parametric models in [34,
35, 1, 85]. The problem of density estimation under local DP constraints has
been considered by [35, 71, 53, 18], of which the latter three works consider
adaptation. In the context of hypothesis testing, [42, 72, 7, 2, 14, 4, 3]
study testing under local DP for discrete distributions. Nonparametric
goodness-of-fit testing under local DP is considered in [33, 55], where in
[55], the authors consider adaptation as well. In [19], the authors consider
estimation of a quadratic functional under local differential privacy
constraints, which has connections to goodness-of-fit testing.

Settings in which the full data is assumed to be on a single server (i.e.
$m=1$), where a single privacy constraint applies to all the observations,
have also been studied for various parametric high-dimensional problems [74,
39, 12, 49, 50, 22, 65, 17, 24]. In [54], nonparametric density estimation
with known smoothness is considered. When it comes to hypothesis testing under
central DP, [25] study simple hypothesis testing. [8] considers uniformity and
independence testing in the multinomial model and [26, 66] study signal
detection in the many-normal-means model. In [9], hypothesis testing in a
linear regression setting is considered.

Investigations into the more general federated setting have been much more
limited, with estimation being considered in [63, 6], which study estimation
for discrete distributions and [57, 67] which study mean estimation, [20]
which study nonparametric regression, and [58] which consider sparse linear
regression. In the paper [27], the authors consider discrete distribution
testing in a two server setting ($m=2$) with differing DP constraints.

###  1.5 Organization of the paper

The rest of the paper is organized as follows. In Section 2, we present the
main results of the paper, for the known smoothness case and the adaptive
setting. Next, Section 3 presents the methods that achieve the optimal rates
derived in Section 2. In Section 4, we extend these methods to be adaptive in
the case that the smoothness is unknown. In Section 5, we present the lower
bound theorems for the testing problem and give a sketch of its proof. Further
proofs are deferred to the supplemental material to the article, [21].

###  1.6 Notation, definitions and assumptions

Throughout the paper, we shall write $N:=mn$. For two positive sequences
$a_{k}$, $b_{k}$ we write $a_{k}\lesssim b_{k}$ if the inequality $a_{k}\leq
Cb_{k}$ holds for some universal positive constant $C$. Similarly, we write
$a_{k}\asymp b_{k}$ if $a_{k}\lesssim b_{k}$ and $b_{k}\lesssim a_{k}$ hold
simultaneously and let $a_{k}\ll b_{k}$ denote that $a_{k}/b_{k}=o(1)$.

We use the notations $a\vee b$ and $a\wedge b$ for the maximum and minimum,
respectively, between $a$ and $b$. For $k\in{\mathbb{N}}$, $[k]$ shall denote
the set $\\{1,\dots,k\\}$. Throughout the paper $c$ and $C$ denote universal
constants whose value can differ from line to line. The Euclidean norm of a
vector $v\in\mathbb{R}^{d}$ is denoted by $\|v\|_{2}$. For a matrix
$M\in{\mathbb{R}}^{d\times d}$, the norm $M\mapsto\|M\|$ is the spectral norm
and $\text{Tr}(M)$ is its trace. Furthermore, we let $I_{d}$ denote the
$d\times d$ identity matrix.

Throughout the paper, $\mathrm{d}_{H}$ is the Hamming distance on
${\mathcal{X}}^{n}$ is defined as
$\mathrm{d}_{H}(x,\breve{x}):=\sum_{i=1}^{n}\text{1}\left\\{x_{i}\neq\breve{x}_{i}\right\\}$
for
$x=(x_{i})_{i=1}^{n},\breve{x}=(\breve{x}_{i})_{i=1}^{n}\in{\mathcal{X}}^{n}$.
Furthermore, for a vector space ${\mathcal{X}}$ and
$x=(x_{i})_{i\in[n]}\in{\mathcal{X}}^{n}$, we shall write $\overline{x}$ for
the average $n^{-1}\sum^{n}_{i=1}x_{i}$.

##  2 Minimax optimal testing rates under privacy constraints

In this section, we discuss the main results in detail. We start the
discussion with results for the oracle case where the regularity parameter is
known in Section 2.1. Section 2.2 describes the main results for when the
regularity is not known.

###  2.1 Description of the minimax separation rate

We first give a precise statement concerning the minimax separation rate shown
in (6).

######  Theorem 1.

Let ${s},R>0$ be given and consider any sequences of natural numbers $m\equiv
m_{N}$ and $n:=N/m$ such that $N=mn\to\infty$,
$1/N\ll\sigma\equiv\sigma_{N}=O(1)$, $\epsilon\equiv\epsilon_{N}$ in
$(N^{-1},1]$ and $\delta\equiv\delta_{N}\lesssim N^{-(1+\omega)}$ for any
constant $\omega>0$. Let $\rho$ a sequence of positive numbers satisfying (6).

Then,

$\underset{T\in\mathscr{T}^{(\epsilon,\delta)}_{\texttt{SHR}}}{\inf}\;\;{\mathcal{R}}(H_{\rho
M_{N}}^{{s},R},T)\to\begin{cases}0\;\text{ for any
}M_{N}^{2}\gg\log\log(N)\log^{3/2}(N)\log(1/\delta),\\\ 1\;\text{ for any
}M_{N}\to 0.\end{cases}$

The proof of the theorem is given in Section B.4 of the Supplementary Material
[21]. It is based on a combination of upper and lower bounds, where the lower
bound is established in Section 5. The upper bound is given in Section 3,
where we present an $(\epsilon,\delta)$-DP distributed testing protocol that
attains the rate in Theorem 1. These upper and lower bounds are in fact non-
asymptotic, meaning that they do not require the assumption that $N\to\infty$.

Theorem 1 shows multiple regime changes, where the distributed testing problem
under privacy constraints undergoes a change in the minimax separation rate.
Later on in this section, we highlight the different regimes and give an
interpretation to each of them.

Theorem 1 considers the minimax rate for the class of distributed protocols
with access to shared randomness,
$\mathscr{T}^{(\epsilon,\delta)}_{\texttt{SHR}}$. Theorem 2 below considers
the minimax rate for the (strictly smaller) class of distributed protocols
without access to shared randomness,
$\mathscr{T}^{(\epsilon,\delta)}_{\texttt{LR}}$. Here, transcripts depend
_only_ on their local data and possibly a local source of randomness.

######  Theorem 2.

Let ${s},R>0$ be given and consider any sequences of natural numbers $m\equiv
m_{N}$ and $n:=N/m$ such that $N=mn\to\infty$,
$1/N\ll\sigma\equiv\sigma_{N}=O(1)$ and $\epsilon\equiv\epsilon_{N}$ in
$(N^{-1},1]$ and $\delta\equiv\delta_{N}\lesssim N^{-(1+\omega)}$ for any
constant $\omega>0$. Let $\rho\equiv\rho_{N}$ a sequence of positive numbers
satisfying

$\rho^{2}\asymp\left(\frac{\sigma^{2}}{mn}\right)^{\frac{2{s}}{2{s}+1/2}}+\left(\frac{\sigma^{2}}{mn^{2}\epsilon^{2}}\right)^{\frac{2{s}}{2{s}+3/2}}\wedge\left(\left(\frac{\sigma^{2}}{\sqrt{m}n\sqrt{1\wedge
n\epsilon^{2}}}\right)^{\frac{2{s}}{2{s}+1/2}}+\left(\frac{\sigma^{2}}{mn^{2}\epsilon^{2}}\right)\right).$
(7)

Then,

$\underset{T\in\mathscr{T}^{(\epsilon,\delta)}_{\texttt{LR}}}{\inf}\;\;{\mathcal{R}}(H_{\rho
M_{N}}^{{s},R},T)\to\begin{cases}0\;\text{ for any
}M_{N}^{2}\gg\log\log(N)\log^{3/2}(N)\log(1/\delta),\\\ 1\;\text{ for any
}M_{N}\to 0.\end{cases}$

The proof of Theorem 1 is given in Section B.4 of the supplemental material
[21]. The theorem shows that, depending on the value of $\epsilon$, the
minimax rate for protocols that do not have access to shared randomness is
strictly worse than those for protocols that do have access to shared
randomness.

To more easily compare the two theorems, we provide a table in Table 1 below,
where we separate six “regimes” to aid interpretability below. Each of the
regimes correspond to the dominating term in the minimax separation rates of
Theorems 1 and 2. Which term dominates depends on the value of $\epsilon$, in
comparison to $n,m,\sigma$, $s$ and the availability of shared randomness.

| Regime 1 | Regime 2 | Regime 3 | Regime 4 | Regime 5 | Regime 6
---|---|---|---|---|---|---
Shared $U$ | $\left(\frac{\sigma^{2}}{mn}\right)^{\frac{2s}{2s+1/2}}$ | $\left(\frac{\sigma^{2}}{mn^{3/2}\epsilon}\right)^{\frac{2s}{2s+1}}$ | $\left(\frac{\sigma^{2}}{mn^{2}\epsilon^{2}}\right)^{\frac{2s}{2s+1}}$ | $\left(\frac{\sigma^{2}}{\sqrt{m}n}\right)^{\frac{2s}{2s+1/2}}$ | $\left(\frac{\sigma^{2}}{\sqrt{m}n^{3/2}\epsilon}\right)^{\frac{2s}{2s+1/2}}$ | $\frac{\sigma^{2}}{mn^{2}\epsilon^{2}}$
Local only | $\left(\frac{\sigma^{2}}{mn}\right)^{\frac{2s}{2s+1/2}}$ | $\left(\frac{\sigma^{2}}{mn^{2}\epsilon^{2}}\right)^{\frac{2s}{2s+3/2}}$ | $\left(\frac{\sigma^{2}}{mn^{2}\epsilon^{2}}\right)^{\frac{2s}{2s+3/2}}$ | $\left(\frac{\sigma^{2}}{\sqrt{m}n}\right)^{\frac{2s}{2s+1/2}}$ | $\left(\frac{\sigma^{2}}{\sqrt{m}n^{3/2}\epsilon}\right)^{\frac{2s}{2s+1/2}}$ | $\frac{\sigma^{2}}{mn^{2}\epsilon^{2}}$

Table 1: The minimax separation rates for the testing problem under privacy
constraints, for both the local randomness and shared randomness settings. The
rates are given up to logarithmic factors. The regimes are defined by the
values of $\epsilon$ and the model characteristics $m,n,\sigma,s$.

The rates in Regimes 4, 5 and 6 are the same for both types of protocols, and
these rates are attained by the same testing protocol for each of the classes,
which does not require shared randomness. We shall refer to Regime 4, 5 and 6
as the “low privacy-budget” regimes, as these rates occur for relatively small
values of $\epsilon$.

We shall refer to Regimes 1, 2 and 3 as the “high privacy-budget” regimes, as
these rates occur for relatively large values of $\epsilon$. These rates are
achieved by a different protocol, for the classes of protocols with and
without shared randomness, respectively. These protocols are given in Sections
3.2 and 3.3. Proving the tighter lower bound in case of the class of protocols
with access to local randomness only, requires a different technique to that
of the class of shared randomness protocols, which we outline in Section 5.

The improvement in the rate for the shared randomness protocols, compared to
the local randomness protocols, are visible for Regime 2 and Regime 3, but
also the values of $\epsilon$ for which the different regimes occur are
different for the two types of protocols. The improvement in the rate is
loosely speaking a consequence of the improved coordination between the
servers made possible by shared randomization. We exhibit a distributed
$(\epsilon,\delta)$-DP shared randomness protocol attaining the above rate in
Section 3.3.

In case of access to shared randomness, the high privacy-budget regime occurs
whenever
$\epsilon\gtrsim\sigma^{-\frac{2}{4s+1}}m^{-\frac{2{s}}{4{s}+1}}n^{\frac{1/2-2{s}}{4{s}+1}}$
and $\epsilon\geq n^{-1/2}$, or
$\sigma^{-\frac{1}{2s}}m^{-\frac{1}{2}}n^{\frac{1-2{s}}{4{s}}}\leq\epsilon<n^{-1/2}$.
In the case of local randomness only, the high privacy-budget regimes occur
for larger values of $\epsilon$, namely
$\epsilon\gtrsim\sigma^{-\frac{2}{4s+1}}m^{\frac{1}{4s+1}}n^{\frac{1/2-2s}{4s+1}}$
if $\epsilon\geq n^{-1/2}$ or
$\epsilon\gtrsim\sigma^{-\frac{4}{4s-1}}m^{-\frac{1}{2}}n^{\frac{5/2-2s}{4s-1}}$
for $\epsilon\lesssim n^{-1/2}$, whenever $s>1/4$. When $s\leq 1/4$ and no
shared randomness is available, we are always in the low privacy-budget regime
for the range of $N^{-1}\lesssim\sigma\lesssim 1$ and $N^{-1}<\epsilon\lesssim
1$ considered.

The testing protocols that attains the rate in the high privacy-budget regimes
are given in Section 3.2 and 3.3. These protocols bear some resemblance with
the estimation strategy in [20], where transcripts constitute noisy, lower
dimensional approximations of the original data. As $\epsilon$ increases, the
dimensionality of these approximations increases and the rate improves. In
Regime 2 and 3, the minimax rate is at least a polynomial factor of $\epsilon$
larger than the unconstrained, non-private minimax separation rate, which is
attained in Regime 1 (up to a logarithmic factor).

The observation that shared randomness can improve performance in our problem
has been noted in other contexts involving distributed privacy and
communication constraints, see for example [4, 5, 3, 76, 77]. [33, 19] studies
interactive versus non-interactive protocols and finds a difference in terms
of minimax performance between the two in the local differential privacy
setting. Interestingly, when $n=1$ (i.e. in the local differential privacy
setting), we find the similar minimax rates for nonparametric goodness-of-fit
testing in the high privacy-budget regimes, for the shared randomness and
local randomness protocols, as they do for interactive and non-interactive
protocols, whenever $\epsilon$ is in the high-budget regime. Although they
study a different model, observations from smooth densities; it is interesting
to see that the same rates seem to be attainable without sequential
interaction, by using shared randomness instead. We note here that, when
sequential- or interactive protocols are allowed, shared randomness can be
employed in particular. In real applications without interaction, one should
always use shared randomness if at all possible.

In the low privacy-budget case, i.e. Regimes 4, 5 and 6, the minimax rate for
both local and shared randomness protocols coincides. We note that the regimes
occur at different values of $\epsilon$ for the two types of protocols,
however. Within the low privacy-budget range, we find essentially three
different regimes. When
$n^{-1/2}\leq\epsilon<\sigma^{-\frac{2}{4s-1}}m^{\frac{1/4-s}{4s+1}}n^{\frac{1/2-2s}{4s+1}}$,
the rate is given by $(\frac{\sigma^{2}}{\sqrt{m}n})^{\frac{2{s}}{2{s}+1/2}}$.
What is remarkable here, is that whilst the rate is polynomially worse in $m$
than the unconstraint rate, the rate is otherwise independent of $\epsilon$.
This regime essentially corresponds to a setting where, even though a high
privacy-budget strategy is not feasible, the desired level of privacy is
achieved “for free" with the locally optimal test statistic.

We exhibit an $(\epsilon,\delta)$-DP distributed testing protocol that attains
this rate in Section 3.1. This strategy can roughly be described as first
computing a locally optimal private test statistic – a test statistic that
would result in the optimal private test using just the local data – and then
averaging these private test statistics; essentially combining the power of
the local tests. That this strategy performs well when the privacy constraint
is sufficiently stringent can intuitively be explained as that it is easier to
retain privacy when only (a private version of) a single real valued local
test statistic is shared, rather than a (private approximation of) the
original data.

When $\epsilon\lesssim n^{-1/2}$ within the low privacy-budget range,
$\epsilon$ affects the rate polynomially. For the smallest values of
$\epsilon$, i.e.
$\epsilon\lesssim\sigma^{\frac{1}{2s+1}}m^{-\frac{1}{2}}n^{-\frac{1+s}{2s+1}}$,
the rate is given by $\frac{\sigma^{2}}{mn^{2}\epsilon^{2}}$. Strikingly, the
regularity parameter does not appear in the rate in this regime. This
phenomenon has the following explanation: for such small values of $\epsilon$,
signals of size $\frac{\sigma^{2}}{mn^{2}\epsilon^{2}}$ are of larger order
than the local estimation rate of
$(\frac{\sigma^{2}}{n})^{\frac{2{s}}{2{s}+1/2}}$. Consequently, signal can
locally be estimated with high accuracy, and the bottleneck is purely the
privacy constraint, not the high-dimensional nature of the problem.

In the case of central DP (i.e. $m=1$), only the low privacy-budget regime is
observed. In this case, our results show that the non-private rate is
attainable (up to logarithmic factors) for $\epsilon\gtrsim 1/\sqrt{N}$. This
is in contrast to the local DP setting, where both the high- and low privacy
budget regimes are observed (depending on the values of $\sigma$ and $s$).
Whenever $m$ is larger than say polynomial in $N$ in the low privacy-budget
range, (i.e. $m\asymp N^{\omega}$ for some $\omega>0$) the unconstrained
minimax rate cannot be reached.

To further illustrate the difference between these classes of protocols, we
provide two plots in Figure 2. The plots show the relationship between the
minimax testing rate $\rho$ and $\epsilon$ for fixed values of $m,n,\sigma$
and four different choices for the regularity $s$. The regimes correspond to
the six regimes in Table 1. The plots show that the shared randomness setting
strictly improves the rate for certain values of $\epsilon$, and that the
values of $\epsilon$ for which the different regimes occur are different for
the two types of protocols. A full case-wise breakdown of when each of the
regimes occur is given in Section C of the Supplementary Material [21]. Below,
we give an interpretation for each of the regimes.

Figure 2: The relationship of the minimax testing rate $\rho$ and $\epsilon$,
given by (7) and (6), for $(n,m)=(5,5)$ in the left column and $(n,m)=(2,15)$
in the right column, $\sigma=1$ and smoothness levels $s=1/5$, $s=1/2$, $s=1$
and $s=3$. The panels on the first row correspond to distributed
$(\epsilon,\delta)$-DP (local randomness only) protocols (i.e. (7)), the
bottom row corresponds to distributed $(\epsilon,\delta)$-DP protocols with
shared randomness (i.e. (6)). The regimes correspond to the six regimes (e.g.
different rates) in Table 1.

What constitute “moderate” or “large” values, depends on the size of $m$
relative to $n$, as can be seen when comparing Figure 2, which compares $N=30$
observations distributed either between $m=15$ servers with $2$ observations
each, and $m=5$ servers with $n=6$ observations each. It can be seen that, as
the local sample $n$ is larger compared to the number of times the total
number of data points $N$ is divided $m$, the cost of privacy is less. This
underlines the idea that, in large samples, it is easier to retain privacy.

When $\epsilon$ becomes “very small” (smaller than a threshold depending on
$s$, $m$ and $n$), the smoothness starts to matter less and less, up to the
point where the difficulty of the problem is no different for (very) different
regularity levels. These scenarios correspond to settings where the privacy
requirement underlying the problem is so stringent, that it effectively
becomes the bottleneck of the testing problem.

###  2.2 Adaptation

In the previous section, we derived the minimax separation rate for the
nonparametric distributed testing problem. However, the proposed tests
constructed in Section 3 require knowledge of the regularity parameter $s$ of
the underlying $f$. Typically, the regularity of the function is unknown in
practice, necessitating the use of data-driven methods to find the best
adaptive testing strategies.

Given that the regularity of the underlying signal class is unknown, it makes
sense to consider the minimax testing risk

$\underset{s\in[s_{\min},s_{\max}]}{\sup}{\mathcal{R}}\left(H^{s,R}_{M_{N,s}\rho_{s}},T\right),$

for certain predetermined values $0<s_{\min}<s_{\max}<\infty$. Here, we
consider separation rates $\rho_{s}$ depending on the underlying smoothness.
In the case that the true underlying smoothness is $s=s_{\min}$, the
separation rate is relatively larger than when (for example) $s=s_{\max}$. In
the case that the true smoothness $s$ is larger than $s_{\min}$, we would like
to attain the smaller of the two rates $\rho_{s}$.

In the non-privacy constraint setting, adaptation for the above risk can be
achieved with only a minor additional cost in the separation rate (a $\log\log
N$ factor). See for example Theorem 2.3 in [75] or Section 7 in [47]. Theorem
3 below shows that also under privacy constraint, the optimal private rate can
be attained by a protocol that is adaptive to the regularity parameter $s$,
with minimal additional cost; at most a logarithmic factor.

######  Theorem 3.

Let $0<s_{\min}<s_{\max}<\infty$, $R>0$ be given and consider any sequences of
natural numbers $m\equiv m_{N}$ and $n:=N/m$ such that $N=mn\to\infty$,
$1/N\ll\sigma\equiv\sigma_{N}=O(1)$, $\epsilon\equiv\epsilon_{N}$ in
$(N^{-1},1]$ and $\delta\equiv\delta_{N}\lesssim N^{-(1+\omega)}$ for any
constant $\omega>0$.

If $\rho$ a sequence of positive numbers satisfies (6), there exists a
sequence of distributed $(\epsilon,\delta)$-DP testing protocols $T_{N}$ such
that

$\underset{s\in[s_{\min},s_{\max}]}{\sup}\;\;{\mathcal{R}}(H_{\rho
M_{N}}^{{s},R},T_{N})\to\begin{cases}0\;\text{ for any
}M_{N}^{2}\gg\log\log(N)\log^{5/2}(N)\log(1/\delta)\\\ 1\;\text{ for any
}M_{N}\to 0.\end{cases}$

Furthermore, whenever $\rho$ satisfies (7), there exists a sequence of
distributed $(\epsilon,\delta)$-DP testing protocols $T_{N}$ using only local
randomness such that the above display holds as well.

We construct such adaptive distributed $(\epsilon,\delta)$-DP testing
protocols in Section 4 and their resulting performance proofs the above
theorem. The adaptive methods can be seen as extensions of the methods
exhibited in Section 3 for when the smoothness is known. The adaptive methods
can essentially be seen as a multiple testing extension of the known
smoothness methods, testing along a grid of smoothness levels between
$s_{\min}$ and $s_{\max}$. The strain on the privacy budget stemming from
conducting multiple testing procedures is limited, due to the fact that the
cardinality of this grid is order $\log(N)$. The Type I error control is
assured by a Bonferroni correction, which leverages the exponential bounds on
the Type I error of the individual “known smoothness tests”.

##  3 Optimal differentially private testing procedures

In this section, we construct distributed $(\epsilon,\delta)$-DP testing
procedures that attain the minimax separation rates derived in Section 2.

The testing procedures are constructed in three steps. First, in Section 3.1,
we construct a distributed $(\epsilon,\delta)$-DP testing procedure that uses
only local randomness and that is optimal in the low privacy-budget regime
described in the previous section. We refer to this procedure as
$T_{\text{I}}$. Second, we construct two distributed $(\epsilon,\delta)$-DP
testing procedures that use local randomness and shared randomness,
respectively, and that are optimal in their respective high privacy-budget
regimes. We refer to these procedures as $T_{\text{II}}$ and $T_{\text{III}}$
and describe them in Sections 3.2 and 3.3, respectively.

The testing procedures differ in terms of the testing strategy. In the low
privacy-budget case where $T_{\text{I}}$ is optimal, the testing strategy can
be seen to consist of first computing a locally optimal private test statistic
in each machine; that is, a test statistic that would result in the optimal
private test using just the local data. The locally optimal test statistic is
based on the squared Euclidean norm of the truncated observation. To deal with
the nonlinearity of the Euclidean norm, the strategy appropriately restricts
the domain of the clipped locally optimal test statistic, after which we
employ a Lipschitz-extension to obtain a test statistic that is well-defined
on the sample space and more robust to outliers than the Euclidean norm
itself. The noisy version of this test statistic is locally optimal under
privacy constraints, in the sense that a corresponding (strict) p-value test
attains the lower bound rate (up to a logarithmic factor) as established by
Theorem 2 for the case where $m=1$. When $m>1$, the final test statistic is
obtained by averaging the locally optimal private test statistics.

In the large $\epsilon$ regime, instead of computing a locally optimal test
statistic, both $T_{\text{II}}$ and $T_{\text{III}}$ are based on truncated,
clipped and noisy versions of the local observations. The key difference
between the two is that the latter uses the same random rotation of the local
observations, which is made possible by the availability of shared randomness.

Together, the methods prove Theorem 4 below, which forms the “upper bound”
part of the minimax separation rate described by Theorems 2 and 1. Unlike the
formulation of the latter theorems, we note that the result is not asymptotic.

######  Theorem 4.

Let ${s},R>0$ be given. For all $\alpha\in(0,1)$, there exists a constant
$C_{\alpha}>0$ such that if

$\rho^{2}\geq
C_{\alpha}\left(\frac{\sigma^{2}}{mn}\right)^{\frac{2{s}}{2{s}+1/2}}+\left(\frac{\sigma^{2}}{mn^{2}\epsilon^{2}}\right)^{\frac{2{s}}{2{s}+3/2}}\wedge\left(\left(\frac{\sigma^{2}}{\sqrt{m}n\sqrt{1\wedge
n\epsilon^{2}}}\right)^{\frac{2{s}}{2{s}+1/2}}+\left(\frac{\sigma^{2}}{mn^{2}\epsilon^{2}}\right)\right),$
(8)

there exists a distributed $(\epsilon,\delta)$-DP testing protocol $T\equiv
T_{m,n,s,\sigma}$ such that

$\;\;{\mathcal{R}}(H_{\rho M_{N}}^{{s},R},T)\leq\alpha,$ (9)

for all natural numbers $m,N$ and $n=N/m$, $\sigma\in[1/N,\sigma_{\max}]$,
$\epsilon\in(N^{-1},1]$, $\delta\leq N^{-(1+\omega)}$ for any constant
$\omega>0$, $\sigma_{\max}>0$ and a nonnegative sequence
$M_{N}^{2}\gtrsim\log\log(N)\log^{3/2}(N)\log(1/\delta)$.

Similarly, for any $\alpha\in(0,1)$, there exists a constant $C_{\alpha}>0$
such that if

$\rho^{2}\geq
C_{\alpha}\left(\frac{\sigma^{2}}{mn}\right)^{\frac{2{s}}{2{s}+1/2}}+\left(\frac{\sigma^{2}}{mn^{3/2}\epsilon\sqrt{1\wedge
n\epsilon^{2}}}\right)^{\frac{2{s}}{2{s}+1}}\wedge\left(\left(\frac{\sigma^{2}}{\sqrt{m}n}\right)^{\frac{2{s}}{2{s}+1/2}}+\left(\frac{\sigma^{2}}{mn^{2}\epsilon^{2}}\right)\right),$
(10)

we have that there exists a distributed $(\epsilon,\delta)$-DP shared
randomness testing protocol $T\equiv T_{m,n,s,\sigma}$ such that

$\;\;{\mathcal{R}}(H_{\rho M_{N}}^{{s},R},T)\leq\alpha,$ (11)

for all natural numbers $m,N$ and $n=N/m$, $\sigma\in[1/N,\sigma_{\max}]$,
$\epsilon\in(N^{-1},1]$, $\delta\leq N^{-(1+\omega)}$ for any constant
$\omega>0$ and a nonnegative sequence
$M_{N}^{2}\gtrsim\log\log(N)\log^{3/2}(N)\log(1/\delta)$.

The proof of the theorem follows directly from the guarantees proven for each
of the three testing protocols; we defer it to Section B in the supplement.
Before giving the detailed construction of the three tests, we introduce some
common notation. Let $\Pi_{L}$ denote the projection of elements
${\mathbb{R}}^{\mathbb{N}}$ onto the first $d_{L}:=\sum_{l=1}^{L}2^{l}$
coordinates, where the elements as ordered and indexed as follows;

$\Pi_{L}x=\left(x_{11},\dots,x_{12},x_{21},\dots,x_{14},\dots,x_{L1},\dots,x_{L2^{L}},0,0,0,\dots\right).$

We shall also use the notation $d_{L}:=\sum_{l=1}^{L}2^{l}$ and let
$X^{(j)}_{L;i}$ denote vector in ${\mathbb{R}}^{d_{L}}$ formed by the first
$d_{L}$ coordinates of $\Pi_{L}X^{(j)}_{i}$ and let
$X^{(j)}_{L}=(X^{(j)}_{L;i})_{i\in[n]}$. Furthermore, we recall that for
$v=(v_{1},\dots,v_{n})\in{\mathcal{X}}^{n}$ for a vector space
${\mathcal{X}}$, $\bar{v}$ denotes the vector space average
$n^{-1}\sum_{i=1}^{n}v_{i}$.

In order to obtain statistics with (uniformly) bounded sensitivity it is
useful to bound quantities between certain thresholds. Formally, for
$a,b,x\in{\mathbb{R}}$ with $a<b$, let $[x]_{a}^{b}$ denote _$x$ clipped
between $a$ and $b$_, that is

$[x]_{a}^{b}:=\begin{cases}b\;\text{ if }x>b,\\\ x\;\text{ if }a\leq x\leq
b\\\ a\;\text{ otherwise.}\end{cases}$ (12)

The distributed privacy protocols under consideration in this paper can be
seen as noisy versions of statistics of the data. Roughly put, the “amount” of
noise added depends on the _sensitivity_ of the statistics. This brings us to
the concept of sensitivity. Formally, consider a metric $\mathrm{d}$ on a set
${\mathcal{Y}}$. Given $n$ elements $x=(x_{1},\dots,x_{n})$ in a sample space
${\mathcal{X}}$, the $\mathrm{d}$-_sensitivity at $x$_ of a map
$S:{\mathcal{X}}^{n}\to{\mathcal{Y}}$ is

$\Delta_{S}(x):=\underset{\breve{x}\in{\mathcal{X}}^{n}:\mathrm{d}_{H}(x,\breve{x})\leq
1}{\sup}\mathrm{d}\left(S(x),S(\breve{x})\right),$

where $\mathrm{d}_{H}$ is the Hamming distance on ${\mathcal{X}}^{n}$ (see
Section 1.6 for a definition). The $\mathrm{d}$-_sensitivity_ of $S$ is
defined as $\Delta_{S}:=\sup_{x}\Delta_{S}(x)$. In this paper, the main noise
mechanism is the _Gaussian mechanism_. The Gaussian mechanism yields
$(\epsilon,\delta)$-differentially private transcripts for statistics that
have bounded $L_{2}$-sensitivity, with the noise variance scaling with the
$L_{2}$-sensitivity. See [36] for a thorough treatment. We remark that for the
rates in Regime 3 up until 6 in Table 1, $(\epsilon,0)$-DP can be attained by
employing a Laplace mechanism instead. That is, for the values of $\epsilon$
for which Regime 3 up until 6 in Table 1 are optimal, the test statistics in
the sections have matching $L_{1}$\- and $L_{2}$-sensitivity, so the Gaussian
mechanism can be replaced by the Laplace mechanism instead in these regimes.

###  3.1 Private testing procedure I: low privacy-budget strategy

In the classical setting without privacy constraints (and $m=1$), a rate
optimal test for the hypotheses of (3) is given by

$\text{1}\left\\{S^{(j)}_{L}>\kappa_{\alpha}\right\\},\text{ where
}S^{(j)}_{L}:=\frac{1}{\sqrt{d_{L}}}\left(\left\|\sigma^{-1}\sqrt{n}\overline{X^{(j)}_{L}}\right\|_{2}^{2}-d_{L}\right),$
(13)

where $d_{L}:=\sum_{l=1}^{L}2^{l}$ and the rate optimal choice of $L$ is
$L_{*}=\left\lceil\frac{1}{2s+1/2}\log_{2}(N)\right\rceil$. Under the null
hypothesis, $S^{(j)}_{L_{*}}$ is Chi-square distributed degrees of freedom.
Under the alternative hypothesis, the test statistic picks up a positive
“bias” as
$\|\sigma^{-1}\sqrt{n}\overline{X^{(j)}_{L_{*}}}\|^{2}\sim\chi^{2}_{L_{*}}(\|\Pi_{L_{*}}f\|_{2}^{2})$
under ${\mathbb{P}}_{f}$, which could surpass the critical value
$\kappa_{\alpha}$ if $\sigma^{-2}n\|\Pi_{L_{*}}f\|_{2}^{2}$ is large enough.
Consequently, the level of the test is controlled by setting $\kappa_{\alpha}$
appropriately large. For a proof of its rate optimality, see e.g. [43].

As is commonly the case for superlinear functions, the test statistic
$S_{L;\tau}^{(j)}$ has poor sensitivity uniformly over the sample space,
meaning that a change in just one datum can result in a large change in the
test statistic. This means that it forms a poor candidate to base a privacy
preserving transcript on. For example, one would need to add a substantial
amount of noise guarantee DP for the statistic. To remedy this, we follow a
similar strategy as proposed in [26] and improved upon by [66]. We construct a
clipped and symmetrized version of the test statistic above, which has small
sensitivity on a set ${\mathcal{C}}_{L;\tau}$, in which $X^{(j)}$ takes values
with high probability. We define the test statistic explicitly on
${\mathcal{C}}_{L;\tau}$ only. By a version of the McShane–Whitney–Extension
Theorem, we obtain a test statistic with the same sensitivity that is defined
on the entire sample space.

Consider for $\tau>0$, $L\in{\mathbb{N}}$, $d_{L}:=\sum^{L}_{l=1}2^{l}$ and
$V^{(j)}_{L;\tau}\sim\chi^{2}_{d_{L}}$ independent of $X^{(j)}$ the random map
from $({\mathbb{R}}^{d_{L}})^{n}$ to ${\mathbb{R}}$ defined by

$\tilde{S}_{L;\tau}^{(j)}(x)=\left[\frac{1}{\sqrt{d_{L}}}\left(\left\|\sigma^{-1}\sqrt{n}\overline{x}\right\|^{2}_{2}-{V^{(j)}_{L;\tau}}\right)\right]_{-\tau}^{\tau}.$
(14)

For any $\tau$, this test statistic $\tilde{S}_{L;\tau}^{(j)}(X^{(j)}_{L})$
can be seen to have mean zero and bounded variance under the null hypothesis,
by similar reasoning as for the test statistic in (13) (see the proof of Lemma
1 for details).

Loosely speaking, the test statistic $\tilde{S}_{L;\tau}^{(j)}(X^{(j)}_{L})$
retains the signal as long as $\tau>0$ is chosen appropriately in comparison
to the signal size (i.e. $\|\Pi_{L}f\|_{2}^{2}$) and has good sensitivity for
“likely” values of $X^{(j)}$ under ${\mathbb{P}}_{f}$, but not uniformly over
the sample space. We make the latter statement precise as follows.

Let $K_{\tau}=\lceil 2\tau D^{-1}_{\tau}\rceil$ and consider the set
${\mathcal{C}}_{L;\tau}={\mathcal{A}}_{L;\tau}\cap{\mathcal{B}}_{L;\tau}$,
where

$\displaystyle{\mathcal{A}}_{L;\tau}$
$\displaystyle=\left\\{(x_{i})\in({\mathbb{R}}^{\infty})^{n}:\bigg{|}\|\sigma^{-1}\textstyle\sum_{i\in{\mathcal{J}}}\Pi_{L}x_{i}\|_{2}^{2}-kd_{L}\bigg{|}\leq\frac{1}{8}kD_{\tau}n\sqrt{d_{L}}\;\;\forall{\mathcal{J}}\subset[n],|{\mathcal{J}}|=k\leq
K_{\tau}\right\\},$ (15) $\displaystyle{\mathcal{B}}_{L;\tau}$
$\displaystyle=\left\\{(x_{i})\in({\mathbb{R}}^{\infty})^{n}:\left|\langle\sigma^{-1}\Pi_{L}x_{i},\sigma^{-1}\textstyle\sum_{k\neq
i}\Pi_{L}x_{k}\rangle\right|\leq\frac{1}{8}kD_{\tau}n\sqrt{d_{L}},\;\;\forall
i=1,\dots,n\right\\}.$

Lemma 18 in the supplement shows that $X^{(j)}$ concentrates on
${\mathcal{C}}_{L;\tau}$ when the underlying signal is, roughly speaking, not
too large compared to $\tau$ (in particular under the null hypothesis).

It can be shown that, on the set ${\mathcal{C}}_{L;\tau}$, $x\mapsto
S^{(j)}(x)$ is $D_{\tau}$-Lipschitz with respect to the Hamming distance, see
Lemma 19 in the supplement. Lemma 20 in the supplement shows that there exists
a measurable function
${S}_{L;\tau}^{(j)}:({\mathbb{R}}^{d_{L}})^{n}\to{\mathbb{R}}$,
$D_{\tau}$-Lipschitz with respect to the Hamming distance, such that
${S}_{L;\tau}^{(j)}(X^{(j)}_{L})=\tilde{S}_{L;\tau}^{(j)}(X^{(j)}_{L})$
whenever $X^{(j)}\in{\mathcal{C}}_{L;\tau}$. Lemma 20 is essentially the
construction of McShane [64] for obtaining a Lipschitz extension with respect
to the Hamming distance, but our lemma verifies in addition the Borel
measurability of the resulting map.

The Lipschitz constant upper bounds the sensitivity of a test statistic that
is Lipschitz continuous with respect to the Hamming distance. Specifically, we
have that

$\Delta_{S^{(j)}}=\underset{x,\breve{x}\in\ell_{2}({\mathbb{N}})^{n}:\mathrm{d}_{H}(x,\breve{x})\leq
1}{\sup}\left|S^{(j)}(x)-S^{(j)}(\breve{x})\right|\leq D_{\tau}.$

Using the Gaussian mechanism, the transcripts

$Y^{(j)}_{L;\tau}=\gamma_{\tau}\breve{S}_{L;\tau}^{(j)}(X^{(j)}_{L})+W^{(j)}_{\tau},\quad\text{where
}W^{(j)}_{\tau}\sim N(0,1)\text{ independent for }j\in[m],$ (16)

$\gamma_{\tau}={\epsilon}/({D_{\tau}\sqrt{2\mathfrak{c}\log(2/\delta)}})$ and
$\tau>0$, are $(\epsilon/\sqrt{\mathfrak{c}},\delta)$-differentially private
for any $\epsilon>0$ (see e.g. [36]). These transcripts are mean zero and have
bounded variance under the null hypothesis, so a test of the form

$\varphi_{\tau}:=\text{1}\left\\{\frac{1}{\sqrt{m}}\underset{j=1}{\overset{m}{\sum}}Y^{(j)}_{L;\tau}\geq\kappa(\gamma_{\tau}\vee
1)\right\\}$ (17)

has an arbitrarily small level for large enough $\kappa>0$ (see Lemma 21 in
the supplement). Furthermore, the lemma below shows that, if the signal size
is large enough in the $\sum_{l=1}^{L}2^{l}$ first coordinates, the above test
enjoys a small Type II error probability as well.

######  Lemma 1.

Consider the test $\varphi_{\tau}$ as defined by (17). If

$\tau/4\leq\frac{n\|f_{L}\|_{2}^{2}}{\log(N)\sqrt{2{\mathfrak{c}}\log(2/\delta)}\sigma^{2}\sqrt{d}}\leq\tau/2$
(18)

and

$\|\Pi_{L}f\|_{2}^{2}\geq
C_{\alpha}\kappa\log(N)\sqrt{{\mathfrak{c}}\log(1/\delta)}\left(\frac{\sqrt{2^{L}}}{\sigma^{2}\sqrt{N}\sqrt{n}(\sqrt{n}\epsilon\wedge
1)}\right)\bigvee\left(\frac{1}{\sigma^{2}Nn\epsilon^{2}}\right)$ (19)

for $C_{\alpha}>0$ large enough, it holds that
${\mathbb{P}}_{f}(1-\varphi_{\tau})\leq\alpha$.

A proof of the above lemma is given in Section B.1 of the supplement. The
above test is calibrated for the detection of signals size between $\tau/4$
and $\tau/2$. In order to detect signals of any size larger than the right-
hand side of (19), we follow what is essentially a multiple testing procedure.
For large signals, we need a larger clipping to detect them, as well as a
larger set ${\mathcal{C}}_{L;\tau}$ to assure that the data is in
${\mathcal{C}}_{L;\tau}$ with high probability, as larger signals increase the
probability of “outliers” from the perspective of the sensitivity of the
$L_{2}$-norm.

It turns out that a sufficient range of clipping thresholds to consider (for
detecting the signals $f\in{\mathcal{B}}^{{s},R}_{p,q}$ under consideration in
Lemma 2) is given by

$\tau\in\mathrm{T}_{L}:=\left\\{2^{-k+2}\frac{n(1-2^{-s})^{2-2/q}R^{2}}{\sigma^{2}\sqrt{2^{L}}}:k=1,\dots,\lceil
1+2\log_{2}(NR/\sigma)\rceil\right\\}.$ (20)

The $(\epsilon,\delta)$-differentially private testing procedure
$T_{\text{I}}$ is now constructed as follows. For each
$\tau\in\mathrm{T}_{L}$, the machine transfers (16) with
$\mathfrak{c}={|\mathrm{T}_{L}|}$. By the independence of the Gaussian noise
added in (16) for each $\tau\in\mathrm{T}_{L}$, the transcript
$Y^{(j)}=\\{Y^{(j)}_{L;\tau}:\tau\in\mathrm{T}_{L}\\}$ is
$(\epsilon,\delta)$-differentially private (see e.g. Theorem A.1 in [36]).

The test

$T_{\text{I}}:=\text{1}\left\\{\underset{\tau\in\mathrm{T}_{L}}{\max}\,\frac{1}{\sqrt{m}}\underset{j=1}{\overset{m}{\sum}}Y^{(j)}_{L;\tau}\geq\kappa_{\alpha}\left(\frac{\epsilon}{D_{\tau}\sqrt{2|\mathrm{T}_{L}|\log(2/\delta)}}\vee
1\right)\sqrt{\log|\mathrm{T}_{L}|}\right\\}$ (21)

then satisfies ${\mathbb{P}}_{0}T_{\text{I}}\leq\alpha$ via a union bound and
sub-exponential tail bound, we defer the reader to the proof of Lemma 2 for
details. Furthermore, for $f\in{\mathcal{B}}^{{s},R}_{p,q}$, we have
$\|\Pi_{L}f\|_{2}\leq\|f\|_{2}\lesssim R$. If $f$ in addition satisfies (19),
there exists $\tau^{*}\in\mathrm{T}_{L}$ such that (18) is satisfied and
consequently

${\mathbb{P}}_{f}(1-T_{\text{I}})\leq{\mathbb{P}}_{f}(1-\varphi_{\tau^{*}})\leq\alpha/2.$

The optimal choice of $L$ depends on the regularity level of the signal $f$,
balancing the approximation error $\|f-\Pi_{L}f\|_{2}^{2}$ and the right-hand
side of (19), for which we defer the details to Section B.1 in the supplement.
To summarize, we have obtained the following lemma.

######  Lemma 2.

For all $R>0$, $\alpha\in(0,1)$ there exists $\kappa_{\alpha}>0$ and
$C_{\alpha}>0$ such that the test $T_{\text{I}}$ defined in (21) satisfies
${\mathbb{P}}_{0}T_{\text{I}}\leq\alpha$. Furthermore, if
$f\in{\mathcal{B}}^{{s},R}_{p,q}$ is such that for some $L$ and
$M_{N,\delta,\tau}=\log(N)\sqrt{\log\log(NR/\sigma)\log(NR/\sigma)\log(1/\delta)}$,

$\|\Pi_{L}f\|_{2}^{2}\geq
C_{\alpha}M_{N,\delta,\tau}\left(\frac{\sqrt{2^{L}}}{\sigma^{2}\sqrt{N}\sqrt{n}(\sqrt{n}\epsilon\wedge
1)}\right)\bigvee\left(\frac{1}{\sigma^{2}Nn\epsilon^{2}}\right),$

we have that ${\mathbb{P}}_{f}(1-T_{\text{I}})\leq\alpha$.

###  3.2 Private testing procedure II: high privacy-budget strategy

In the high-privacy budget regime, we construct a testing procedure that
consists essentially of two steps. In the first step, the data is truncated,
clipped and averaged over the coordinates, after which Gaussian noise is added
to obtain a private summary of the original data. Then, as a second step, the
transcripts are averaged, and based on this average, a test statistic that is
reminiscent of a chi-square test is computed in the central server. This is in
contrast to the strategy of the previous section, where each server computes a
(private version of) a chi-square test statistic.

The approach taken here is to divide the servers equally over the first
$d_{L}$ coordinates (i.e. as uniformly as possible), where we recall the
notation $d_{L}:=\sum_{l=1}^{L}2^{l}$. That is to say, for
$L,K_{L}\in{\mathbb{N}}$, we partition the coordinates $\\{1,\ldots,d_{L}\\}$
into approximately $d_{L}/K_{L}$ sets of size $K_{L}$. The servers are then
equally divided over each of these partitions and communicate the sum of the
clipped $X^{(j)}_{L;i}$’s coefficients corresponding to their partition, were
we also recall that the notation $X^{(j)}_{L;i}$ denotes the vector in
${\mathbb{R}}^{d_{L}}$ formed by the first $d_{L}$ coordinates of
$\Pi_{L}X^{(j)}_{i}$.

More formally, take $K_{L}=\lceil n\epsilon^{2}\wedge d_{L}\rceil$ and
consider sets ${\mathcal{J}}_{lk;L}\subset[m]$ for indexes
$(l,k)\in\\{l=1,\dots,L,k=1,\dots,2^{l}\\}=:I_{L}$, such that
$|{\mathcal{J}}_{lk;L}|=\lceil\frac{mK_{L}}{d_{L}}\rceil$ and each
$j\in\\{1,\dots,m\\}$ is in ${\mathcal{J}}_{lk;L}$ for at least $K_{L}$
different indexes $k\in\\{1,\dots,d_{L}\\}$. For $(l,k)\in I_{L}$,
$j\in{\mathcal{J}}_{lk;L}$, generate the transcripts according to

$Y^{(j)}_{lk;L}|X^{(j)}\equiv
Y^{(j)}_{lk;L}(X^{(j)})=\gamma_{L}\,\sum_{i=1}^{n}\,[\sigma^{-1}(X_{i}^{(j)})_{lk}]_{-\tau}^{\tau}+W^{(j)}_{lk}$
(22)

with $\gamma_{L}={\epsilon}/({2\sqrt{2K_{L}\log(2/\delta)}\tau})$,
$\tau=\tilde{\kappa}_{\alpha}\sqrt{\log(N/\sigma)}$ and
$(W^{(j)}_{lk})_{j\in[m],(l,k)\in I_{L}}$ i.i.d. standard Gaussian noise.

Since $x\mapsto\sum^{n}_{i=1}[\sigma(x_{i}^{(j)})_{lk}]_{-\tau}^{\tau}$ has
sensitivity bounded by $2\tau$, for $k=1,\dots,K$, releasing

$Y^{(j)}_{L}(X^{(j)})=(Y^{(j)}_{L,l_{1}k_{1}}(X^{(j)}),\dots,Y^{(j)}_{L,l_{K_{L}}k_{K_{L}}}(X^{(j)}))$

satisfies $(\epsilon,\delta)$-DP, see Lemma 23 in the supplement for details.

If the privacy budget were of no concern, submitting the above transcripts
with $2^{L}\asymp N^{1/(2s+1/2)}$ would be sufficient to construct a test
statistic that attains the unconstrained rate of $\rho^{2}\asymp
N^{-2s/(2s+1/2)}$. Under (more stringent) privacy constraints, however, the
optimal number of coordinates to be transmitted should depend on the privacy
budget. Whenever $\epsilon\lesssim 1/\sqrt{n}$, it turns out that submitting
just one coordinate is in fact rate optimal. Sending more than one coordinate
leads to worse rates as the noise overpowers the benefit of having a higher
dimensional transcript. As $\epsilon$ increases, the optimal number of
coordinates to be transmitted increases as well. Whenever
$\epsilon\gtrsim\sigma^{-\frac{2}{4s+1}}m^{\frac{1}{4s+1}}n^{\frac{1/2-2s}{4s+1}}$,
the optimal number of coordinates to be transmitted is $2^{L}\asymp
N^{1/(2s+1/2)}$.

The test

$T_{\text{II}}=\text{1}\left\\{\frac{1}{\sqrt{d_{L}}}\underset{(l,k)\in
I_{L}}{\overset{}{\sum}}\left[\left(\frac{1}{\sqrt{|{\mathcal{J}}_{lk;L}|}}\underset{j\in{\mathcal{J}}_{lk;L}}{\overset{}{\sum}}Y^{(j)}_{lk;L}\right)^{2}-\frac{n\epsilon^{2}}{4{K_{L}}\tau^{2}}-1\right]\geq\kappa_{\alpha}\left(\frac{n\epsilon^{2}}{4{K_{L}}\tau^{2}}\vee
1\right)\right\\}$ (23)

satisfies ${\mathbb{P}}_{0}T_{\text{II}}\leq\alpha$ by Lemma 24 in the
supplement whenever $\tilde{\kappa}_{\alpha}>0$ and $\kappa_{\alpha}>0$ are
chosen large enough.

The power that the test attains depends on the signal size up until resolution
level $L$, i.e. $\|\Pi_{L}f\|_{2}$. Specifically, the test Type II error
${\mathbb{P}}_{f}(1-T_{\text{II}})\leq\alpha$ whenever

$\|\Pi_{L}f\|_{2}^{2}\geq
C_{\alpha}\frac{\log\log(N)\log(N)\log(1/\delta)2^{(3/2)L}}{mn^{2}\epsilon^{2}}.$
(24)

The optimal choice of $L$ for is determined by the trade-off between the
approximation error $\|f-\Pi_{L}f\|_{2}^{2}$ and the right-hand side of (24).
The proof of the following lemma is given in Section B.2 of the supplement.

######  Lemma 3.

Take $\alpha\in(0,1)$. Suppose $f$ satisfies (24) and that
$\epsilon\geq\frac{2^{L+1}}{\sqrt{mn}}$ for some $L\in{\mathbb{N}}$. Then, the
distributed $(\epsilon,\delta)$-DP testing protocol $T_{\text{II}}$ of level
$\alpha$ has Type II error ${\mathbb{P}}_{f}(1-T)\leq\alpha$ for a large
enough constant $C_{\alpha}>0$ and $\tilde{\kappa}_{\alpha}>0$, depending only
on $\alpha$.

###  3.3 Private testing procedure III: high privacy-budget shared randomness
strategy

In this section, we construct a testing procedure that is based on the same
principles as the one in the previous section, but with the difference that
the servers a source of randomness. The transcripts are still based on the
clipped and averaged coordinates of the truncated data, but instead of
dividing the servers across the coordinates, we apply the same random rotation
across the servers.

Next, we describe the testing procedure in detail. Consider for
$L\in{\mathbb{N}}$ the quantities $d_{L}=\sum_{l=1}^{L}2^{l}$ and
$K_{L}=\lceil n\epsilon^{2}\wedge d_{L}\rceil$ and let $U_{L}$ denote a random
rotation uniformly drawn (i.e. from the Haar measure) on the group of random
orthonormal ${d_{L}\times d_{L}}$-matrices.

For
$I_{L}:=\\{(l,k):l=1,\dots,\lceil\log_{2}(K_{L})\rceil,\,k=1,\dots,2^{l}\\}$,
$(l,k)\in I_{L}$ and $j=1,\dots,m$, generate the transcripts according to

$Y^{(j)}_{lk;L}|(X^{(j)},U)=\gamma_{L}\,\underset{i=1}{\overset{n}{\sum}}[(UX_{L;i}^{(j)})_{lk}]^{\tau}_{-\tau}+W^{(j)}_{lk},$
(25)

with $\gamma_{L}=\frac{\epsilon}{2\sqrt{2K_{L}\log(2/\delta)\log(N)}\tau}$,
$\tau=\tilde{\kappa}_{\alpha}\sqrt{\log(N/\sigma)}$,
$\tilde{\kappa}_{\alpha}>0$ and $(W^{(j)}_{l})_{j,l}$ i.i.d. centered standard
Gaussian noise. By an application of Lemma 25, the transcript
$Y^{(j)}_{L}:=(Y^{(j)}_{lk;L})_{(l,k)\in I_{L}}$ is
$(\epsilon,\delta)$-differentially private.

In the shared randomness strategy above, we essentially only send the first
$\sum_{l=1}^{\lceil\log_{2}(K_{L})\rceil}2^{l}$ coordinates. The random
rotation $U_{L}$ ensures that, roughly speaking, a sufficient amount of the
signal is present in these first coordinates, with high probability.

We then construct the test

$T_{\text{III}}=\text{1}\left\\{\frac{1}{\sqrt{K_{L}}}\underset{(l,k)\in
I_{L}}{\overset{}{\sum}}\left[\left(\frac{1}{\sqrt{m}}\underset{j=1}{\overset{m}{\sum}}Y^{(j)}_{lk;L}\right)^{2}-n\gamma^{2}_{L}-1\right]\geq\kappa_{\alpha}\left(n\gamma^{2}_{L}\vee
1\right)\right\\},$ (26)

which satisfies ${\mathbb{P}}_{0}\varphi\leq\alpha/2$ by Lemma 26 in the
supplement, for $\kappa_{\alpha}>0$ large enough. The lemma below is proven in
Section B of the supplement, and yields that the Type II error of the test
satisfies ${\mathbb{P}}_{f}(1-T_{\text{III}})\leq\alpha$ whenever the
coordinates up to resolution level $L$ are of sufficient size. The optimal
value for $L$ depends on the truncation level $s$, and is chosen by balancing
the approximation error $\|f-\Pi_{L}f\|_{2}^{2}$ and the right-hand side of
(27), we defer the reader to Section B.3 of the supplement for details.

######  Lemma 4.

The testing protocol $T_{\text{III}}$, with level $\alpha$ and has
corresponding Type II error probability
${\mathbb{P}}_{f}(1-T_{\text{III}})\leq\alpha$ whenever

$\|\Pi_{L}f\|_{2}^{2}\geq
C_{\alpha}\frac{2^{L}\log(1/\delta)\log(N)}{mn\sqrt{n\epsilon^{2}\wedge
2^{L}}\sqrt{n\epsilon^{2}\wedge 1}}$ (27)

for constant $C_{\alpha}>0$ and $\tilde{\kappa}_{\alpha}>0$ depending only on
$\alpha$.

##  4 Adaptive tests under DP constraints

In the previous section we have derived methods that match (up to logarithmic
factors) the theoretical lower bound established in Section 2. The proposed
tests, however, depend on the regularity parameter $s$ of the functional
parameter of interest $f$.

In this section we derive an distributed $(\epsilon,\delta)$-DP testing
protocol that adapts to the regularity when it is unknown. This method attains
the optimal rate of Theorem 3, and consequently proves the aforementioned
theorem.

The adaptive procedure builds on the tests constructed in Section 3 and
combines them using essentially a multiple testing strategy. Roughly speaking,
the method consists of taking approximately a $1/\log N$-mesh-size grid in the
regularity interval $[s_{\min},s_{\max}]$, constructing optimal tests for each
of the grid points and combining them using a type of Bonferroni’s correction.
By design, the tests constructed in Section 3 are based on sub-exponential
private test statistics, which allows a combination of the test statistics
with a Bonferroni correction of the order of $\log\log N$.

Combining $\log N$ many $(\epsilon^{\prime},\delta)$-differentially private
transcripts using Gaussian mechanisms, results in a
$(\epsilon,\delta)$-differentially private protocol, with
$\epsilon=\epsilon^{\prime}\sqrt{\log N}$. This means that the erosion of the
privacy budget by conducting a test for each grid-point is limited to a
logarithmic factor, means the method greatly improves over the potentially
polynomially worse rate of a non-adaptive method.

The detailed adaptive testing procedures are given as follows. Let $\rho_{s}$
equal the right-hand side of (7) in case there is access to local randomness
only, or the right-hand side of (6) in case shared randomness is available.
Let ${L_{s}}=\lfloor s^{-1}\log_{2}(1/\rho_{s})\rfloor\vee 1$ and define
furthermore $\mathcal{S}:=\\{L_{s_{\min}},\dots,L_{s_{\max}}\\}$ such that
$L_{s}\in{\mathcal{S}}$ for all $s\in[s_{\min},s_{\max}]$. Furthermore, we
note that the resulting “collection of resolution levels” satisfies
$|\mathcal{S}|\leq C_{s_{\max}}\log N$ for some constant $C_{s_{\max}}>0$
depending only on $s_{\max}$.

Consider the first the case without access to shared randomness. We partition
the collection of resolution levels $\mathcal{S}$, depending on the model
characteristics, as follows.

${\mathcal{S}}^{\texttt{LOW}}_{\texttt{LR}}=\left\\{L\in{\mathcal{S}}:2^{L}\leq\epsilon\sqrt{mn}(1+\sqrt{n}\text{1}_{\\{\sqrt{n}\epsilon>1\\}})\right\\},\quad{\mathcal{S}}^{\texttt{HIGH}}_{\texttt{LR}}={\mathcal{S}}\setminus{\mathcal{S}}^{\texttt{LOW}}_{\texttt{LR}}.$
(28)

If the true regularity $s_{0}$ is such that
$L_{s_{0}}\in{\mathcal{S}}^{\texttt{LOW}}$, the low privacy-budget test of
Section 3.1 (with $L=L_{s_{0}}$) is a rate optimal strategy. If
$L_{s_{0}}\in{\mathcal{S}}^{\texttt{HIGH}}$, the high privacy-budget test of
Section 3.2 is rate optimal.

For the case of shared randomness, the phase transitions occur for different
values of $s\in[s_{\min},s_{\max}]$, or their respective resolution levels
$L_{s}$. So in this case, we partition the collection of resolution levels as

${\mathcal{S}}^{\texttt{LOW}}_{\texttt{SHR}}=\left\\{L\in{\mathcal{S}}:2^{L}\leq\epsilon^{2}{mn}\right\\},\quad{\mathcal{S}}^{\texttt{HIGH}}_{\texttt{SHR}}={\mathcal{S}}\setminus{\mathcal{S}}^{\texttt{LOW}}_{\texttt{SHR}}.$
(29)

Consider some ${\mathcal{S}}^{\prime}\subset{\mathcal{S}}$. The “adaptive
version” of the low privacy-budget test defined in (21) takes the form

$T_{\text{I}}^{S}:=\text{1}\left\\{\underset{L\in{\mathcal{S}}^{\prime},\,\tau\in\mathrm{T}_{L}}{\max}\;\;\frac{1}{\sqrt{m}\left(\gamma_{L}\vee
1\right)\sqrt{\log|\mathrm{T}_{L}||{\mathcal{S}}^{\prime}|}}\;\underset{j=1}{\overset{m}{\sum}}Y^{(j)}_{L;\tau}\geq\kappa_{\alpha}\right\\},$
(30)

where $\mathrm{T}_{L}$ is as defined in (20) and
$Y^{(j)}_{L}=\\{Y^{(j)}_{L;\tau}:\tau\in\mathrm{T}_{L}\\}$ is generated
according to (16) for $L\in S$ with

$\gamma_{\tau}=\frac{\epsilon}{2D_{\tau}\sqrt{|\mathrm{T}_{L}||{\mathcal{S}}^{\prime}|\log(4/\delta)}}.$

The above choice of $\epsilon$ yields that $(Y^{(j)}_{L})_{L\in S}$ is
$(\epsilon/2,\delta/2)$-DP due to the Gaussian mechanism. The enlargement of
the critical region, which is now effectively rescaled by
$\sqrt{\log|\mathrm{T}|_{L}|{\mathcal{S}}^{\prime}|}$ instead of
$\sqrt{\log|\mathrm{T}|_{L}}$, accounts for the potentially larger set of test
statistics over which the maximum is taken. In the case of having access only
to local sources of randomness, we set
${\mathcal{S}}^{\prime}={\mathcal{S}}^{\texttt{LOW}}_{\texttt{LR}}$. If
${\mathcal{S}}^{\texttt{LOW}}_{\texttt{LR}}$ is empty, we set $T_{\text{I}}=0$
instead, which forms an $(0,0)$-differentially private protocol.

In the case of having access to local sources of randomness only; if
${\mathcal{S}}^{\texttt{HIGH}}_{\texttt{LR}}$ is non-empty, the adaptive
version of the high privacy-budget test defined in (B.3) is given by

$T_{\text{II}}=\text{1}\left\\{\underset{L\in{\mathcal{S}}^{\texttt{HIGH}}_{\texttt{LR}}}{\max}\;\frac{1}{\sqrt{d_{L}}\left(\eta_{L}\vee
1\right)}\underset{(l,k)\in
I_{L}}{\overset{}{\sum}}\left[\left(\frac{1}{\sqrt{|{\mathcal{J}}_{lk;L}|}}\underset{j\in{\mathcal{J}}_{lk;L}}{\overset{}{\sum}}Y^{(j)}_{lk;L}\right)^{2}-\eta_{L}-1\right]\geq\kappa_{\alpha}\sqrt{\log|{\mathcal{S}}^{\texttt{HIGH}}|}\right\\},$
(31)

where the transcripts are generated according to (S.74) for
$L\in{\mathcal{S}}^{\texttt{HIGH}}$, with
$\gamma_{L}={\epsilon}/({4\sqrt{|{\mathcal{S}}^{\texttt{HIGH}}|K_{L}\log(4/\delta)}\tau})$,
$\eta_{L}=\frac{n\epsilon^{2}}{4{K_{L}}\tau^{2}}$,
$\tau=\tilde{\kappa}_{\alpha}\sqrt{\log(N/\sigma)}$. Due to the Gaussian
mechanism, the transcripts satisfy an $(\epsilon/2,\delta/2)$-DP constraint.
As before, if ${\mathcal{S}}^{\texttt{HIGH}}$ is empty, set $T_{\text{II}}=0$
instead.

In the case of having access to local randomness only, the adaptive testing
procedure then consists of computing the tests
$T_{\text{I}}^{{\mathcal{S}}^{\texttt{LOW}}}$ and $T_{\text{II}}$, for which
the released transcripts satisfy $(\epsilon,\delta)$-DP. The final test is
then given by

$T=T_{\text{I}}^{{\mathcal{S}}^{\texttt{LOW}}}\vee T_{\text{II}}.$ (32)

In Section B in the supplement, it is shown that this test is adaptive and
rate optimal (up to logarithmic factors), proving the first part of Theorem 3.

In case of shared randomness, the adaptive version of the high privacy-budget
test defined in (S.84) is given by

$T_{\text{III}}=\text{1}\left\\{\underset{L\in
S^{\texttt{HIGH}}_{\texttt{SHR}}}{\max}\;\frac{1}{\sqrt{K_{L}}\left(n\gamma_{L}^{2}\vee
1\right)}\underset{(l,k)\in
I_{L}}{\overset{}{\sum}}\left[\left(\frac{1}{\sqrt{m}}\underset{j=1}{\overset{m}{\sum}}Y^{(j)}_{lk;L}\right)^{2}-n\gamma^{2}_{L}-1\right]\geq\kappa_{\alpha}\sqrt{\log|{\mathcal{S}}|}\right\\},$
(33)

where the transcripts are generated according to (S.83) for $L\in
S^{\texttt{HIGH}}_{\texttt{SHR}}$,
$\gamma_{L}=\frac{\epsilon}{4\sqrt{K_{L}|S^{\texttt{HIGH}}_{\texttt{SHR}}|\log(4/\delta)\log(N)}\tau}$,
$\tau=\tilde{\kappa}_{\alpha}\sqrt{\log(N/\sigma)}$. By similar reasoning as
earlier, the transcripts
$\\{Y^{(j)}_{L}:L\in\S^{\texttt{HIGH}}_{\texttt{SHR}}\\}$ are
$(\epsilon/2,\delta/2)$-DP. If $S^{\texttt{HIGH}}_{\texttt{SHR}}$ is empty, we
set $T_{\text{III}}=0$ instead.

The adaptive testing procedure in the case of shared randomness then consists
of computing the tests $T_{\text{I}}^{S^{\texttt{LOW}}}$ and $T_{\text{III}}$,
for which the released transcripts satisfy $(\epsilon,\delta)$-DP. The final
test is then given by

$T=T_{\text{I}}^{S^{\texttt{LOW}}_{\texttt{SHR}}}\vee T_{\text{III}}.$ (34)

In the supplement’s Section B, we prove that this test is adaptive, attaining
the optimal rate for shared randomness protocols (up to logarithmic factors),
giving us the second statement Theorem 3.

##  5 The minimax private testing lower bound

In this section, we present a single theorem outlining the lower bound for the
detection threshold for distributed testing protocols that adhere to DP
constraints, with and without the use of shared randomness. The theorem
directly yields the “lower bound part” of Theorems 2 and 1 presented in
Section 2. In conjunction with Theorem 4, the theorem shows that the tests
constructed in Section 3 are rate optimal up to logarithmic factors.

######  Theorem 5.

Let ${s},R>0$ be given. For all $\alpha\in(0,1)$, there exists a constant
$c_{\alpha}>0$ such that if

$\rho^{2}\leq
c_{\alpha}\left(\frac{\sigma^{2}}{mn}\right)^{\frac{2{s}}{2{s}+1/2}}+\left(\frac{\sigma^{2}}{mn^{2}\epsilon^{2}}\right)^{\frac{2{s}}{2{s}+3/2}}\wedge\left(\left(\frac{\sigma^{2}}{\sqrt{m}n\sqrt{1\wedge
n\epsilon^{2}}}\right)^{\frac{2{s}}{2{s}+1/2}}+\left(\frac{\sigma^{2}}{mn^{2}\epsilon^{2}}\right)\right),$
(35)

it holds that

$\underset{T\in\mathscr{T}^{(\epsilon,\delta)}}{\inf}\;\;{\mathcal{R}}(H_{\rho}^{{s},R},T)>1-\alpha,$
(36)

for all natural numbers $m,N$ and $n=N/m$, $\sigma>0$, $\epsilon\in(N^{-1},1]$
and $\delta\leq N^{-(1+\omega)}$ for any constant $\omega>0$.

Similarly, for any $\alpha\in(0,1)$, there exists a constant $c_{\alpha}>0$
such that if

$\rho^{2}\leq
c_{\alpha}\left(\frac{\sigma^{2}}{mn}\right)^{\frac{2{s}}{2{s}+1/2}}+\left(\frac{\sigma^{2}}{mn^{3/2}\epsilon\sqrt{1\wedge
n\epsilon^{2}}}\right)^{\frac{2{s}}{2{s}+1}}\wedge\left(\left(\frac{\sigma^{2}}{\sqrt{m}n}\right)^{\frac{2{s}}{2{s}+1/2}}+\left(\frac{\sigma^{2}}{mn^{2}\epsilon^{2}}\right)\right),$
(37)

we have that there exists a distributed $(\epsilon,\delta)$-DP shared
randomness testing protocol $T\equiv T_{m,n,s,\sigma}$ such that

$\underset{T\in\mathscr{T}^{(\epsilon,\delta)}_{\texttt{SHR}}}{\inf}\;\;{\mathcal{R}}(H_{\rho}^{{s},R},T)>1-\alpha,$
(38)

for all natural numbers $m,N$ and $n=N/m$, $\sigma>0$, $\epsilon\in(N^{-1},1]$
and $\delta\leq N^{-(1+\omega)}$ for any constant $\omega>0$.

The theorem states that, whenever the signal-to-noise ratio $\rho$ is below a
certain threshold times the minimax separation rate, no distributed testing
protocol can achieve a combined Type I and Type II error rate below $\alpha$.
Its proof is lengthy and involves a combination of various techniques. We
defer the full details of the proof to Section A of the supplement, but
provide an overview of the main steps below.

For Steps 1, 2 and 3, there is no distinction between local and shared
randomness. We use the same notation for distributed protocols in these steps,
but simply assume $U$ is degenerate in the case of local randomness.

  1. Step 1:

The first step is standard in minimax testing analysis: we lower bound the
testing risk by a Bayes risk,

$\underset{T\in\mathscr{T}}{\inf}\,{\mathcal{R}}(H_{\rho},T)\geq\underset{T\in\mathscr{T}}{\inf}\,\underset{\pi}{\sup}\,\left({\mathbb{P}}_{0}(T(Y)=1)+\int{\mathbb{P}}_{f}(T(Y)=0)d\pi(f)-\pi(H_{\rho}^{c})\right),$
(39)

where $\mathscr{T}$ denotes either the class of local randomness or shared
randomness $(\epsilon,\delta)$-DP protocols. This inequality allows the prior
$\pi$ to be chosen adversarially to the distribution of the transcripts. This
turns out to be crucial in the context of local randomness protocols, as is
further highlighted in Step 4. The specific prior distribution is chosen to be
a centered Gaussian distribution, with a finite rank covariance, where the
rank is of the order $2^{L}$, for some $L\in{\mathbb{N}}$. This covariance is
constructed in a way that it puts most of its mass in the dimensions in which
the privacy protocol is the least informative, whilst at the same time it
assures that the probability mass outside of the alternative hypothesis
$\pi(H_{\rho}^{c})$ is small. The particular choice for a Gaussian prior
(instead of e.g. the two point prior in [45]) is motivated by Step 3.

  2. Step 2:

In this step, we approximate the distribution of the transcripts with another
distribution that results in approximately the same testing risk, but has two
particular favorable properties for our purposes.

     * •

Whenever the distribution of a transcript satisfies an $(\epsilon,\delta)$-DP
constraint with $\delta>0$, the transcript’s density can be unbounded on a set
of small probability mass (proportional to $\delta$). Consequently, the local
likelihoods of the transcripts can have erratic behavior in the tails. To
remedy this, we consider approximations to the transcripts that have bounded
likelihoods, that differ only on a set that is negligible in terms of its
impact on the testing risk. Furthermore, these approximating transcripts
satisfy a $(\epsilon,2\delta)$-DP privacy constraint. These bounded
likelihoods enable the argument of Step 5.

     * •

Similarly, whenever $\delta>0$, the distribution of the data conditionally on
the transcript potentially has an unbounded density. For the argument employed
in Step 3, we require a uniform abound on the density of the distribution of
$X|Y$. We mitigate this by approximating the distribution of the transcripts
by a distribution that induces a bounded density for the data conditionally on
the transcript. This approximation of the original transcript satisfies a
$(\epsilon,3\delta)$-DP constraint.

Furthermore, we show that both approximations can be done in a way that the
approximating transcript distribution is $(\epsilon,6\delta)$-DP.

  3. Step 3:

By standard arguments, on can further lower bound the testing risk in (39) for
a particular transcript distribution
${\mathbb{P}}^{Y|X,U}=\bigotimes^{m}_{j=1}{\mathbb{P}}^{Y^{(j)}|X^{(j)},U}$
and prior distribution $\pi$ by a quantity depending on the chi-square
divergence between ${\mathbb{P}}_{\pi}^{Y|U=u}$ and
${\mathbb{P}}_{0}^{Y|U=u}$;

$1-\left(\sqrt{(1/2)\int{\mathbb{E}}_{0}^{Y|U=u}\left(\left(\frac{d{\mathbb{P}}_{\pi}^{Y|U=u}}{d{\mathbb{P}}_{0}^{Y|U=u}}\right)^{2}-1\right)^{2}d{\mathbb{P}}^{U}(u)}+\pi(H_{\rho}^{c})\right).$
(40)

The likelihood ratio of the transcripts depends on the privacy protocol, and
is difficult to analyze directly. We employ the technique developed in [77].
Specifically, Lemma 10.1 in [77], which states, roughly speaking, that the
inequality

${\mathbb{E}}_{0}^{{Y}|U=u}\left(\frac{d{\mathbb{P}}_{\pi}^{Y|U=u}}{d{\mathbb{P}}_{0}^{Y|U=u}}\right)^{2}\leq{G}\underset{j=1}{\overset{m}{\Pi}}{\mathbb{E}}_{0}^{{Y^{(j)}}|U=u}\left(\frac{d{\mathbb{P}}_{\pi}^{Y^{(j)}|U=u}}{d{\mathbb{P}}_{0}^{Y^{(j)}|U=u}}\right)^{2}$
(41)

holds for a finite constant $0<{G}<\infty$ and equality with the smallest
possible ${G}$ is attained whenever the conditional distribution of the data
given the transcripts is Gaussian in an appropriate sense (we defer the
details here to Section A.3 in the supplement). This result is a type of
Brascamp-Lieb inequality [16, 60]. There is an existing literature on
Brascamp-Lieb inequality in relation to information theoretical problems, in
relation to mutual information [28, 61, 62], in addition to the communication
constraint testing problem in [77]. That (41) has a “Gaussian maximizer”
allows tractable analysis of the chi-square divergence in (40), yielding that
the latter display is further lower bounded by

$1-\sqrt{(1/2)\int\left(\mathrm{A}_{u}^{\pi}\mathrm{B}_{u}^{\pi}-1\right)d{\mathbb{P}}^{U}(u)}+\pi(H_{\rho}^{c}),$
(42)

where

$\mathrm{A}_{u}^{\pi}:=\int
e^{f^{\top}\sum_{j=1}^{m}\Xi^{j}_{u}g}d(\pi\times\pi)(f,g),\quad\mathrm{B}_{u}^{\pi}:=\underset{j=1}{\overset{m}{\Pi}}{\mathbb{E}}_{0}^{{Y^{(j)}}|U=u}\left(\frac{d{\mathbb{P}}_{\pi}^{Y^{(j)}|U=u}}{d{\mathbb{P}}_{0}^{Y^{(j)}|U=u}}\right),$
(43)

where $\Xi^{j}_{u}$ denotes the covariance of (a subset of) the data
$X^{(j)}_{L}$ (defined as in (44)) conditionally on the transcript $Y^{(j)}$
and $U=u$;

$\Xi_{u}^{j}:={\mathbb{E}}_{0}^{Y^{(j)}|U=u}{\mathbb{E}}_{0}\left[\underset{i=1}{\overset{n}{\sum}}\sigma^{-1}{X}^{(j)}_{L;i}\bigg{|}Y^{(j)},U=u\right]{\mathbb{E}}_{0}\left[\underset{i=1}{\overset{n}{\sum}}\sigma^{-1}{X}^{(j)}_{L;i}\bigg{|}Y^{(j)},U=u\right]^{\top}.$
(44)

Whilst the quantities $\mathrm{A}_{u}$ and $\mathrm{B}_{u}^{\pi}$ are still
not fully tractable, sharp bounds for both are possible and form the content
of Steps 4 and 5, respectively.

  4. Step 4:

As remarked earlier, class of local randomness protocols is a strictly smaller
class. To attain the sharper (i.e. larger) lower bound for local randomness
protocols, we exploit the fact that Step 2 allows us to choose the prior
adversarially to the distribution of the transcripts. In particular, since $U$
is degenerate in the case of local randomness only, this means that the
covariance of $\pi$ to be more diffuse in the directions in which
$\Xi^{j}_{u}$ is the smallest. When considering shared randomness protocols,
$U$ is not degenerate, and the lower bound follows by taking the covariance of
$\pi$ to be an order $2^{L}$-rank approximation of the identity map on
$\ell_{2}({\mathbb{N}})$. The bounds for $\mathrm{A}_{u}^{\pi}$ are

$\mathrm{A}_{u}^{\pi}=\exp\left({C\frac{\rho^{4}}{c_{\alpha}2^{3L}}\text{Tr}\left(\Xi_{u}\right)^{2}}\right)\quad\text{
and
}\quad\mathrm{A}_{u}^{\pi}\leq\exp\left({C\frac{\rho^{4}}{c_{\alpha}2^{2L}}\|\Xi_{u}\|\text{Tr}\left(\Xi_{u}\right)}\right)$
(45)

for local randomness protocols and shared randomness protocols, respectively.

  5. Step 5:

So far, Steps 1-4 have not used the fact that the transcripts are necessarily
less informative than the original data, as a consequence of the transcripts
being $(\epsilon,\delta)$-DP. In this step, we exploit the privacy constraint
to argue that $\mathrm{A}_{u}^{\pi}$ and $\mathrm{B}_{u}^{\pi}$ are small at
the detection boundary for $\rho$.

In order to capture the information loss due to privacy in
$\mathrm{A}_{u}^{\pi}$, it suffices to bound the trace and operator norm of
$\Xi_{u}$. The quantity $\Xi_{u}$ can be seen as the Fisher information of the
finite dimensional submodel spanned by the covariance of $\pi$. This quantity,
loosely speaking, captures how much information the transcript contains on the
original data. In order to analyze $\Xi_{u}$, we rely on a “score attack” type
of technique, as employed in [23, 20].

The quantity $\mathrm{B}_{u}^{\pi}$ corresponds to the (product of) the local
likelihoods of the transcripts. Whenever $\epsilon\geq 1/\sqrt{n}$, it
suffices to consider the trivial bound

${\mathbb{E}}_{0}^{{Y^{(j)}}|U=u}\left(\frac{d{\mathbb{P}}_{\pi}^{Y^{(j)}|U=u}}{d{\mathbb{P}}_{0}^{Y^{(j)}|U=u}}\right)\leq{\mathbb{E}}_{0}^{{X^{(j)}}|U=u}\left(\frac{d{\mathbb{P}}_{\pi}^{X^{(j)}}}{d{\mathbb{P}}_{0}^{X^{(j)}}}\right),$
(46)

and further bounding the right-hand side without privacy specific arguments.
Whenever $\epsilon<1/\sqrt{n}$, more sophisticated methods are need to capture
the effect of privacy. Our argument uses a coupling method, which, combined
with the fact that the likelihoods of the transcripts are bounded in our
construction, allows us to obtain a sharp bound for $\mathrm{B}_{u}^{\pi}$.
After obtaining the bounds in terms of the rank $2^{L}$ and $\rho$, the proof
is finished by choosing $L$ such that the second and third term in (40) are
balanced (minimizing their sum).

##  6 Discussion

The findings in this paper highlight the trade-off between statistical
accuracy and privacy in federated goodness-of-fit testing under differential
privacy (DP) constraints. We characterize the problem in terms of the minimax
separation rate, which quantifies the difficulty of the testing problem based
on the regularity of the underlying function, the sample size, the degree of
data distribution, and the stringency of the DP constraint. The minimax
separation rate varies depending on whether the distributed testing protocol
has access to local or shared randomness. Furthermore, we construct data-
driven adaptive testing procedures that achieve the same optimal performance,
up to logarithmic factors, even when the regularity of the functional
parameter is unknown.

One possible extension of this work is to consider a more general distribution
of the privacy budget across the servers. Our current analysis supports
differing budgets to the extent that $\epsilon_{j}\asymp\epsilon_{k}$,
$\delta_{j}\asymp\delta_{k}$, and $n_{j}\asymp n_{k}$. However, one could
explore more heterogeneous settings where severs differ significantly in their
differential privacy constraints and number of observations. Although this
would complicate the presentation of results, the techniques developed in this
paper could, in principle, be extended to such settings.

Another interesting direction is to consider multiple testing problems, where
the goal is to test multiple hypotheses simultaneously. We anticipate that the
framework, insights, and theoretical results provided in the current paper
will serve as valuable resources for future studies in this domain.

Regarding adaptation, not much is known about the cost of privacy outside the
local DP setting (i.e., one observation per server; $n=1$ in our context).
Interestingly, the cost of adaptation is minimal in the privacy setting
considered in this paper. It remains an open question whether this minimal
cost is a general phenomenon, whether it can be characterized exactly, or
whether the cost of adaptation is more severe in other settings. We leave
these questions for future research.

Supplementary Material to “Federated Nonparametric Hypothesis Testing with
Differential Privacy Constraints: Optimal Rates and Adaptive Tests” In this
supplement, we present the detailed proofs for the main results in the paper
“Federated Nonparametric Hypothesis Testing with Differential Privacy
Constraints: Optimal Rates and Adaptive Tests”.

The research was supported in part by NIH grants R01-GM123056 and
R01-GM129781.

## References

  * [1] [author] Acharya, JayadevJ., Bonawitz, KallistaK., Kairouz, PeterP., Ramage, DanielD. and Sun, ZitengZ. (2020). Context Aware Local Differential Privacy. In Proceedings of the 37th International Conference on Machine Learning (Hal DauméH. D. III and AartiA. Singh, eds.). Proceedings of Machine Learning Research 119 52–62. PMLR.
  * [2] [author] Acharya, JayadevJ., Canonne, ClementC., Freitag, CodyC. and Tyagi, HimanshuH. (2019). Test without Trust: Optimal Locally Private Distribution Testing. In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics (KamalikaK. Chaudhuri and MasashiM. Sugiyama, eds.). Proceedings of Machine Learning Research 89 2067–2076. PMLR.
  * [3] [author] Acharya, JayadevJ., Canonne, Clément L.C. L., Freitag, CodyC., Sun, ZitengZ. and Tyagi, HimanshuH. (2021). Inference Under Information Constraints III: Local Privacy Constraints. IEEE Journal on Selected Areas in Information Theory 2 253-267. 10.1109/JSAIT.2021.3053569
  * [4] [author] Acharya, JayadevJ., Canonne, Clément L.C. L. and Tyagi, HimanshuH. (2020). Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction. IEEE Transactions on Information Theory 66 7835-7855. 10.1109/TIT.2020.3028440
  * [5] [author] Acharya, JayadevJ., Canonne, Clément LC. L. and Tyagi, HimanshuH. (2020). Inference under information constraints II: Communication constraints and shared randomness. IEEE Transactions on Information Theory 66 7856–7877.
  * [6] [author] Acharya, JayadevJ., Liu, YuhanY. and Sun, ZitengZ. (2023). Discrete Distribution Estimation under User-level Local Differential Privacy. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics (FranciscoF. Ruiz, JenniferJ. Dy and Jan-WillemJ.-W. van de Meent, eds.). Proceedings of Machine Learning Research 206 8561–8585. PMLR.
  * [7] [author] Acharya, JayadevJ., Sun, ZitengZ. and Zhang, HuanyuH. (2018). Differentially private testing of identity and closeness of discrete distributions. Advances in Neural Information Processing Systems 31\.
  * [8] [author] Acharya, JayadevJ., Sun, ZitengZ. and Zhang, HuanyuH. (2018). Differentially Private Testing of Identity and Closeness of Discrete Distributions. In Advances in Neural Information Processing Systems (S.S. Bengio, H.H. Wallach, H.H. Larochelle, K.K. Grauman, N.N. Cesa-Bianchi and R.R. Garnett, eds.) 31\. Curran Associates, Inc.
  * [9] [author] Alabi, DanielD. and Vadhan, SalilS. (2022). Hypothesis Testing for Differentially Private Linear Regression. In Advances in Neural Information Processing Systems (S.S. Koyejo, S.S. Mohamed, A.A. Agarwal, D.D. Belgrave, K.K. Cho and A.A. Oh, eds.) 35 14196–14209. Curran Associates, Inc.
  * [10] [author] AN, KOLMOGOROVK. (1933). Sulla determinazione empirica di una legge didistribuzione. Giorn Dell’inst Ital Degli Att 4 89–91.
  * [11] [author] Arachchige, Pathum Chamikara MahawagaP. C. M., Bertok, PeterP., Khalil, IbrahimI., Liu, DongxiD., Camtepe, SeyitS. and Atiquzzaman, MohammedM. (2019). Local differential privacy for deep learning. IEEE Internet of Things Journal 7 5827–5842.
  * [12] [author] Bassily, RaefR., Smith, AdamA. and Thakurta, AbhradeepA. (2014). Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science 464–473. IEEE.
  * [13] [author] Beaufays, FrancoiseF., Rao, KanishkaK., Mathews, RajivR. and Ramaswamy, SwaroopS. (2019). Federated learning for emoji prediction in a mobile keyboard.
  * [14] [author] Berrett, ThomasT. and Butucea, CristinaC. (2020). Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms. Advances in Neural Information Processing Systems 33 3164–3173.
  * [15] [author] Boucheron, StéphaneS., Lugosi, GáborG. and Massart, PascalP. (2013). Concentration inequalities: a nonasymptotic theory of independence, 1st ed ed. Oxford University Press, Oxford. OCLC: ocn818449985.
  * [16] [author] Brascamp, Herm JanH. J. and Lieb, Elliott HE. H. (1976). Best constants in Young’s inequality, its converse, and its generalization to more than three functions. Advances in Mathematics 20 151–173.
  * [17] [author] Brown, GavinG., Hopkins, SamuelS. and Smith, AdamA. (2023). Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions. In Proceedings of Thirty Sixth Conference on Learning Theory (GergelyG. Neu and LorenzoL. Rosasco, eds.). Proceedings of Machine Learning Research 195 5578–5579. PMLR.
  * [18] [author] Butucea, CristinaC., Dubois, AmandineA., Kroll, MartinM. and Saumard, AdrienA. (2020). Local differential privacy: Elbow effect in optimal density estimation and adaptation over Besov ellipsoids. Bernoulli 26 1727 – 1764. 10.3150/19-BEJ1165
  * [19] [author] Butucea, CristinaC., Rohde, AngelikaA. and Steinberger, LukasL. (2023). Interactive versus noninteractive locally differentially private estimation: Two elbows for the quadratic functional. Annals of Statistics 51\. 10.1214/22-AOS2254
  * [20] [author] Cai, T. TonyT. T., Chakraborty, AbhinavA. and Vuursteen, LasseL. (2023). Optimal federated learning for nonparametric regression with heterogenous distributed differential privacy constraints. preprint.
  * [21] [author] Cai, T TonyT. T., Chakraborty, AbhinavA. and Vuursteen, LasseL. (2024). Supplement to “Federated nonparametric hypothesis testing with differential privacy constraints: Optimal rates and adaptive tests".
  * [22] [author] Cai, T TonyT. T., Wang, YichenY. and Zhang, LinjunL. (2021). The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics 49 2825–2850.
  * [23] [author] Cai, T TonyT. T., Wang, YichenY. and Zhang, LinjunL. (2023). Score attack: A lower bound technique for optimal differentially private learning. arXiv preprint arXiv:2303.07152.
  * [24] [author] Cai, T TonyT. T., Xia, DongD. and Zha, MengyueM. (2024). Optimal differentially private PCA and estimation for spiked covariance matrices. arXiv preprint arXiv:2401.03820.
  * [25] [author] Canonne, Clément LC. L., Kamath, GautamG., McMillan, AudraA., Smith, AdamA. and Ullman, JonathanJ. (2019). The structure of optimal private tests for simple hypotheses. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing 310–321.
  * [26] [author] Canonne, Clément LC. L., Kamath, GautamG., McMillan, AudraA., Ullman, JonathanJ. and Zakynthinou, LydiaL. (2020). Private Identity Testing for High-Dimensional Distributions. In Advances in Neural Information Processing Systems (H.H. Larochelle, M.M. Ranzato, R.R. Hadsell, M. F.M. F. Balcan and H.H. Lin, eds.) 33 10099–10111. Curran Associates, Inc.
  * [27] [author] Canonne, Clément LC. L. and Sun, YuchengY. (2023). Private Distribution Testing with Heterogeneous Constraints: Your Epsilon Might Not Be Mine. arXiv preprint arXiv:2309.06068.
  * [28] [author] Carlen, Eric A.E. A. and Cordero-Erausquin, DarioD. (2008). Subadditivity of the entropy and its relation to Brascamp-Lieb type inequalities. arXiv:0710.0870 [math]. arXiv: 0710.0870.
  * [29] [author] Cohen, AlbertA., Daubechies, IngridI. and Vial, PierreP. (1993). Wavelets on the interval and fast wavelet transforms. Applied and computational harmonic analysis.
  * [30] [author] Cramér, HaraldH. (1928). On the composition of elementary errors: First paper: Mathematical deductions. Scandinavian Actuarial Journal 1928 13–74.
  * [31] [author] Daubechies, IngridI. (1992). Ten lectures on wavelets. SIAM.
  * [32] [author] Ding, BolinB., Kulkarni, JanardhanJ. and Yekhanin, SergeyS. (2017). Collecting telemetry data privately. Advances in Neural Information Processing Systems 30\.
  * [33] [author] Dubois, AmandineA., Berrett, ThomasT. and Butucea, CristinaC. (2023). Goodness-of-Fit Testing for Hölder Continuous Densities Under Local Differential Privacy. In Foundations of Modern Statistics. Springer Proceedings in Mathematics & Statistics PROMS-425 53-119. Springer International Publishing. 10.1007/978-3-031-30114-8_2
  * [34] [author] Duchi, John CJ. C., Jordan, Michael IM. I. and Wainwright, Martin JM. J. (2013). Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science 429–438. IEEE.
  * [35] [author] Duchi, John CJ. C., Jordan, Michael IM. I. and Wainwright, Martin JM. J. (2018). Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association 113 182–201.
  * [36] [author] Dwork, CynthiaC., Roth, AaronA. et al. (2014). The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science 9 211–407.
  * [37] [author] Dwork, CynthiaC. and Smith, AdamA. (2010). Differential privacy for statistics: What we know and what we want to learn. Journal of Privacy and Confidentiality 1\.
  * [38] [author] Dwork, CynthiaC., Smith, AdamA., Steinke, ThomasT. and Ullman, JonathanJ. (2017). Exposed! a survey of attacks on private data. Annual Review of Statistics and Its Application 4 61–84.
  * [39] [author] Dwork, CynthiaC., Talwar, KunalK., Thakurta, AbhradeepA. and Zhang, LiL. (2014). Analyze gauss: optimal bounds for privacy-preserving principal component analysis. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing 11–20.
  * [40] [author] Erlingsson, ÚlfarU., Pihur, VasylV. and Korolova, AleksandraA. (2014). RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. CCS ’14 1054–1067. Association for Computing Machinery, New York, NY, USA. 10.1145/2660267.2660348
  * [41] [author] Ermakov, MSM. (1990). Asymptotically minimax tests for nonparametric hypotheses concerning the distribution density. Journal of Soviet Mathematics 52 2891–2898.
  * [42] [author] Gaboardi, MarcoM., Lim, HyunH., Rogers, RyanR. and Vadhan, SalilS. (2016). Differentially private Chi-squared hypothesis testing: Goodness of fit and independence testing. In Proceedings of The 33rd International Conference on Machine Learning (Maria FlorinaM. F. Balcan and Kilian Q.K. Q. Weinberger, eds.). Proceedings of Machine Learning Research 48 2111–2120. PMLR, New York, New York, USA.
  * [43] [author] Gine, EvaristE. and Nickl, RichardR. (2016). Mathematical Foundations of Infinite-Dimensional Statistical Models. Cambridge University Press, Cambridge. 10.1017/CBO9781107337862
  * [44] [author] Hard, AndrewA., Rao, KanishkaK., Mathews, RajivR., Ramaswamy, SwaroopS., Beaufays, FrançoiseF., Augenstein, SeanS., Eichner, HubertH., Kiddon, ChloéC. and Ramage, DanielD. (2018). Federated learning for mobile keyboard prediction. arXiv preprint arXiv:1811.03604.
  * [45] [author] Ingster, YuriY. and Suslina, Irina AI. A. (2003). Nonparametric goodness-of-fit testing under Gaussian models 169\. Springer Science & Business Media.
  * [46] [author] Ingster, Yuri IY. I. (1993). Asymptotically minimax hypothesis testing for nonparametric alternatives. I, II, III. Math. Methods Statist 2 85–114.
  * [47] [author] Ingster, Yu. I.Y. I. and Suslina, Irina A.I. A. (2003). Nonparametric Goodness-of-Fit Testing Under Gaussian Models. Lecture Notes in Statistics 169\. Springer New York, New York, NY. 10.1007/978-0-387-21580-8
  * [48] [author] Johnstone, Iain MI. M. (2019). Function Estimation and Gaussian Sequence Models. Unpublished manuscript.
  * [49] [author] Kamath, GautamG., Li, JerryJ., Singhal, VikrantV. and Ullman, JonathanJ. (2019). Privately learning high-dimensional distributions. In Conference on Learning Theory 1853–1902. PMLR.
  * [50] [author] Kamath, GautamG., Singhal, VikrantV. and Ullman, JonathanJ. (2020). Private mean estimation of heavy-tailed distributions. In Conference on Learning Theory 2204–2235. PMLR.
  * [51] [author] Karwa, VisheshV. and Vadhan, SalilS. (2017). Finite sample differentially private confidence intervals. arXiv preprint arXiv:1711.03908.
  * [52] [author] Konečnỳ, JakubJ., McMahan, H BrendanH. B., Ramage, DanielD. and Richtárik, PeterP. (2016). Federated optimization: Distributed machine learning for on-device intelligence. arXiv preprint arXiv:1610.02527.
  * [53] [author] Kroll, MartinM. (2021). On density estimation at a fixed point under local differential privacy. Electronic Journal of Statistics 15 1783 – 1813. 10.1214/21-EJS1830
  * [54] [author] Lalanne, ClémentC., Garivier, AurélienA. and Gribonval, RémiR. (2023). About the Cost of Central Privacy in Density Estimation. Transactions on Machine Learning Research.
  * [55] [author] Lam-Weil, JosephJ., Laurent, BéatriceB. and Loubes, Jean-MichelJ.-M. (2022). Minimax optimal goodness-of-fit testing for densities and multinomials under a local differential privacy constraint. Bernoulli 28 579–600.
  * [56] [author] Lepskii, OVO. (1992). Asymptotically minimax adaptive estimation. i: Upper bounds. optimally adaptive estimates. Theory of Probability & Its Applications 36 682–697.
  * [57] [author] Levy, DanielD., Sun, ZitengZ., Amin, KareemK., Kale, SatyenS., Kulesza, AlexA., Mohri, MehryarM. and Suresh, Ananda TheerthaA. T. (2021). Learning with user-level privacy. Advances in Neural Information Processing Systems 34 12466–12479.
  * [58] [author] Li, MengchuM., Tian, YeY., Feng, YangY. and Yu, YiY. (2024). Federated Transfer Learning with Differential Privacy. arXiv preprint arXiv:2403.11343.
  * [59] [author] Li, TianT., Sahu, Anit KumarA. K., Talwalkar, AmeetA. and Smith, VirginiaV. (2020). Federated learning: Challenges, methods, and future directions. IEEE signal processing magazine 37 50–60.
  * [60] [author] Lieb, Elliott H.E. H. (1990). Gaussian kernels have only Gaussian maximizers. Inventiones Mathematicae 102 179–208. Publisher: Springer New York. 10.1007/BF01233426
  * [61] [author] Liu, JingboJ., Courtade, Thomas A.T. A., Cuff, PaulP. and Verdu, SergioS. (2016). Brascamp-Lieb inequality and its reverse: An information theoretic view. In 2016 IEEE International Symposium on Information Theory (ISIT) 1048–1052. IEEE, Barcelona, Spain. 10.1109/ISIT.2016.7541459
  * [62] [author] Liu, JingboJ., Courtade, Thomas A.T. A., Cuff, PaulP. and Verdu, SergioS. (2016). Smoothing Brascamp-Lieb Inequalities and Strong Converses for Common Randomness Generation. arXiv:1602.02216 [cs, math]. arXiv: 1602.02216.
  * [63] [author] Liu, YuhanY., Suresh, Ananda TheerthaA. T., Yu, Felix Xinnan XF. X. X., Kumar, SanjivS. and Riley, MichaelM. (2020). Learning discrete distributions: user vs item-level privacy. Advances in Neural Information Processing Systems 33 20965–20976.
  * [64] [author] McShane, Edward JamesE. J. (1934). Extension of range of functions.
  * [65] [author] Narayanan, ShyamS. (2022). Private high-dimensional hypothesis testing. In Conference on Learning Theory 3979–4027. PMLR.
  * [66] [author] Narayanan, ShyamS. (2022). Private High-Dimensional Hypothesis Testing. In Proceedings of Thirty Fifth Conference on Learning Theory (Po-LingP.-L. Loh and MaximM. Raginsky, eds.). Proceedings of Machine Learning Research 178 3979–4027. PMLR.
  * [67] [author] Narayanan, ShyamS., Mirrokni, VahabV. and Esfandiari, HosseinH. (2022). Tight and robust private mean estimation with few users. In International Conference on Machine Learning 16383–16412. PMLR.
  * [68] [author] Nguyen, AnhA., Do, TuongT., Tran, MinhM., Nguyen, Binh XB. X., Duong, ChienC., Phan, TuT., Tjiputra, ErmanE. and Tran, Quang DQ. D. (2022). Deep federated learning for autonomous driving. In 2022 IEEE Intelligent Vehicles Symposium (IV) 1824–1830. IEEE.
  * [69] [author] Petrov, Valentin VV. V. (2022). Sums of independent random variables. In Sums of Independent Random Variables De Gruyter.
  * [70] [author] Rodriguez, Ian MI. M., Sexton12, William NW. N., Singer, Phyllis EP. E. and Vilhuber, LarsL. The modernization of statistical disclosure limitation at the US Census Bureau.
  * [71] [author] Sart, MathieuM. (2023). Density estimation under local differential privacy and Hellinger loss. Bernoulli 29 2318 – 2341. 10.3150/22-BEJ1543
  * [72] [author] Sheffet, OrO. (2018). Locally private hypothesis testing. In International Conference on Machine Learning 4605–4614. PMLR.
  * [73] [author] Smirnov, N.N. (1948). Table for Estimating the Goodness of Fit of Empirical Distributions. The Annals of Mathematical Statistics 19 279 – 281. 10.1214/aoms/1177730256
  * [74] [author] Smith, AdamA. (2011). Privacy-preserving statistical estimation with optimal convergence rates. In Proceedings of the forty-third annual ACM symposium on Theory of computing 813–822.
  * [75] [author] Spokoiny, V. G.V. G. (1996). Adaptive hypothesis testing using wavelets. The Annals of Statistics 24\. 10.1214/aos/1032181163
  * [76] [author] Szabó, BotondB., Vuursteen, LasseL. and Van Zanten, HarryH. (2022). Optimal distributed composite testing in high-dimensional Gaussian models with 1-bit communication. IEEE Transactions on Information Theory 68 4070–4084.
  * [77] [author] Szabó, BotondB., Vuursteen, LasseL. and van Zanten, HarryH. (2023). Optimal high-dimensional and nonparametric distributed testing under communication constraints. The Annals of Statistics 51 909 – 934. 10.1214/23-AOS2269
  * [78] [author] Team, Apple Differential PrivacyA. D. P. (2017). Learning with Privacy at Scale.
  * [79] [author] Thorisson, H.H. (2000). Coupling, Stationarity, and Regeneration. Probability and Its Applications. Springer New York.
  * [80] [author] Triebel, H.H. (1992). Theory of Function Spaces II. Monographs in mathematics. Springer.
  * [81] [author] Tsybakov, Alexandre B.A. B. (2009). Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer.
  * [82] [author] Van Der Vaart, Aad WA. W. and Wellner, Jon AJ. A. (1996). Weak convergence. Springer.
  * [83] [author] Vershynin, RomanR. (2018). High-Dimensional Probability: An Introduction with Applications in Data Science, 1 ed. Cambridge University Press. 10.1017/9781108231596
  * [84] [author] Von Mises, RichardR. (1928). Statistik und wahrheit. Julius Springer 20\.
  * [85] [author] Ye, MinM. and Barg, AlexanderA. (2018). Optimal Schemes for Discrete Distribution Estimation Under Locally Differential Privacy. IEEE Transactions on Information Theory 64 5662-5676. 10.1109/TIT.2018.2809790

, and

##  A Proof of the lower bound Theorem 5

In this section, we provide a proof for Theorem 5. The proof is divided into
several steps, following the outline provided in Section 5.

It is convenient to introduce the following notation. In the notation that
follows, we shall consider a local randomness protocol to consist of a triplet

$(T,\\{\left({\mathbb{P}}^{Y^{(j)}|X^{(j)}=x,U=u}\right)_{x\in{\mathcal{X}}^{n},u\in{\mathcal{U}}}\\}_{j=1}^{m},({\mathcal{U}},\mathscr{U},{\mathbb{P}}^{U})),$

where the probability space $({\mathcal{U}},\mathscr{U},{\mathbb{P}}^{U})$ has
the trivial sigma-algebra; $\mathscr{U}=\\{\emptyset,{\mathcal{U}}\\}$. This
allows streamlining the argument for both lower bounds of Theorem 5 into a
single argument. Given an $(\epsilon,\delta)$-DP distributed protocol triplet

$(T,\\{\left({\mathbb{P}}^{Y^{(j)}|X^{(j)}=x,U=u}\right)_{x\in{\mathcal{X}}^{n},u\in{\mathcal{U}}}\\}_{j=1}^{m},({\mathcal{U}},\mathscr{U},{\mathbb{P}}^{U})),$

we shall use the notation $P_{f}={\mathbb{P}}_{f}^{X^{(j)}}$. For the Markov
kernel

$(A,(x,u))\mapsto{\mathbb{P}}^{Y^{(j)}|(X^{(j)},U)=(x,u)}(A),$

we shall use the shorthand $(A,(x,u))\mapsto K^{j}(A|(x,u))$. If the
transcript $Y^{(j)}$ is $(\epsilon,\delta)$-DP, the Markov kernel satisfies

$\displaystyle K^{j}(A$ $\displaystyle|x_{1},\dots,x_{i},\dots,x_{n},u)\leq
e^{\epsilon}K^{j}(A|x_{1},\dots,x_{i}^{\prime},\dots,x_{n},u)+\delta$
$\displaystyle\text{ for all
}A\in\mathscr{Y},\;x_{i}^{\prime},x_{1},\dots,x_{i},\dots,x_{n}\in{\mathcal{X}},\;i\in\\{1,\dots,n\\}.$

When the parameter underlying the true distribution of the data $F$ is drawn
from a prior distribution on $\ell_{2}({\mathbb{N}})$, we obtain that the
distributed testing protocol satisfies the Markov chain

${\quad
F}\qquad\begin{matrix}\put(-10.0,-4.0){\vector(3,1){20.0}}&\quad(X^{(1)},U)&\put(0.0,5.0){\vector(1,0){20.0}}&\qquad
Y^{(1)}\quad&\put(-10.0,4.0){\vector(3,-1){20.0}}\\\
\put(-10.0,3.0){\vector(1,0){20.0}}&\quad\vdots&\put(0.0,4.0){\vector(1,0){20.0}}&\qquad\vdots\quad&\put(-10.0,4.0){\vector(1,0){20.0}}\\\
\put(-10.0,12.0){\vector(3,-1){20.0}}&\quad(X^{(m)},U)&\put(0.0,5.0){\vector(1,0){20.0}}&\qquad
Y^{(m)}\quad&\put(-10.0,5.0){\vector(3,1){20.0}}\end{matrix}\qquad T,$ (S.1)

with ${\mathbb{P}}^{Y^{(j)}|U=u}_{f}=P_{f}K^{j}(\cdot|X^{(j)},u)$ for all
$j\in[m]$. Let $K_{u}=\bigotimes_{j=1}^{m}K^{j}(\cdot|\cdot,u)$ denote the
product conditional distribution with $U=u$, such that distribution of the
collection of transcripts conditionally on $U=u$ then satisfies
${\mathbb{P}}^{Y|U=u}_{f}=P^{m}_{f}K_{u}()$.

If the transcript $Y^{(j)}$ is $(\epsilon,\delta)$-DP and generated from
$K^{j}_{u},u\in{\mathcal{U}}$, this translates to

$\displaystyle K^{j}(A$ $\displaystyle|x_{1},\dots,x_{i},\dots,x_{n},u)\leq
e^{\epsilon}K^{j}(A|x_{1},\dots,x_{i}^{\prime},\dots,x_{n},u)+\delta$ (S.2)
$\displaystyle\text{ for all
}A\in\mathscr{Y},\;x_{i}^{\prime},x_{1},\dots,x_{i},\dots,x_{n}\in{\mathcal{X}},\;i\in\\{1,\dots,n\\}.$

###  A.1 Step 1: Lower bounding the testing risk by the Bayes risk

As a first step, we lower bound the testing risk by the Bayes risk. Following
the notation introduced above, let
$T\equiv(T,\\{{K}^{j}\\}_{j=1}^{m},({\mathcal{U}},\mathscr{U},{\mathbb{P}}^{U}))$
be an $(\epsilon,\delta)$-DP distributed testing protocol and let
${K}_{u}=\bigotimes_{j=1}^{m}{K}^{j}(\cdot|\cdot,u)$. The testing risk for $T$
can be written as

${\mathcal{R}}(H_{\rho}^{{s},R},T)=\int
P_{0}^{m}K_{u}Td{\mathbb{P}}^{U}(u)+\underset{f\in H_{\rho}^{s,R}}{\sup}\int
P_{f}^{m}K_{u}(1-T)d{\mathbb{P}}^{U}(u).$ (S.3)

Consider $L\in{\mathbb{N}}$, $d_{L}=\sum_{l=1}^{L}2^{l}$ and consider
$\pi=N(0,c_{\alpha}^{-1/2}d^{-1}_{L}\rho^{2}\bar{\Gamma})$ for a symmetric
idempotent matrix $\bar{\Gamma}\in{\mathbb{R}}^{d_{L}\times d_{L}}$. Consider
also the linear operator
$\Psi_{L}:{\mathbb{R}}^{d_{L}}\to\ell_{2}({\mathbb{N}})$ defined by
$\Psi_{L}\tilde{f}=f$ for

$f_{lk}=\begin{cases}\tilde{f}_{lk}&\text{if }l\leq L,\\\ 0&\text{if
}l>L,\end{cases}$ (S.4)

for
$\tilde{f}=(\tilde{f}_{11},\dots,\tilde{f}_{L2^{L}})\in{\mathbb{R}}^{d_{L}}$.
Since $\Psi_{L}$ is measurable, any probability distribution $\pi_{L}$ on
${\mathbb{R}}^{2^{L}}$, $\pi_{L}\circ\Psi^{-1}_{L}$ defines a probability
measure on the Borel sigma algebra of $\ell_{2}({\mathbb{N}})$.

Using that $0\leq T\leq 1$, the above testing risk is lower bounded by the
Bayes risk

$\int\left(P_{0}^{m}{K}_{u}T+\int
P_{f}^{m}{K}_{u}(1-T)d\pi\circ\Psi^{-1}_{L}(f)\right)d{\mathbb{P}}^{U}(u)-\pi\circ\Psi^{-1}_{L}\left((H_{\rho}^{s,R})^{c}\right).$
(S.5)

We highlight here that $\bar{\Gamma}$ can depend on $\\{{K}^{j}\\}_{j=1}^{m}$.

To lower bound the testing risk further, it suffices to show that the prior
$\pi$ has little mass outside of $H_{\rho}^{s,R}$. This follows by a standard
Gaussian concentration argument, provided in Lemma 5 below, from which it
follows that, for $c_{\alpha}>0$ small enough, it holds that
$\pi\circ\Psi^{-1}((H_{\rho}^{s,R})^{c})\leq\alpha/4$. This yields that (S.5)
is lower bounded by

$\int\left(P_{0}^{m}{K}_{u}T+\int
P_{f}^{m}{K}_{u}(1-T)d\pi\circ\Psi^{-1}_{L}(f)\right)d{\mathbb{P}}^{U}(u)-\alpha/4.$
(S.6)

######  Lemma 5.

Suppose $\rho\lesssim c_{\alpha}2^{-Ls}$. Then, for any $c_{\alpha}>0$ small
enough, it holds that $\pi\circ\Psi^{-1}_{L}((H_{\rho}^{s,R}))\leq\alpha/4$.

###### Proof.

Let $f\in\ell_{2}({\mathbb{N}})$. It holds that $f\in H_{\rho}^{s,R}$ if and
only if $\|f\|_{2}^{2}\geq\rho^{2}$ and $\|f\|_{{\mathcal{B}}^{s}_{p,q}}\leq
R$. For the first of these events, we have that

$\pi\circ\Psi^{-1}_{L}(f:\|f\|_{2}^{2}\geq\rho^{2})=\text{Pr}\left(Z^{\top}\bar{\Gamma}Z\geq\sqrt{c_{\alpha}}d_{L}\right),$
(S.7)

where $Z\sim N(0,I_{d_{L}})$. Using that $\bar{\Gamma}$ is idempotent, the
right-hand side of the above display can be made arbitrarily small for small
enough choice of $c_{\alpha}>0$, by Lemma 36.

To assure that $f\sim\pi\circ\Psi^{-1}_{L}$ concentrates on a Besov ball, we
recall the definition of the Besov norm as given in (5). We have that

$\displaystyle\pi\circ\Psi^{-1}_{L}(f:\|f\|_{{\mathcal{B}}^{s}_{p,q}}\leq R)$
$\displaystyle=\pi\circ\Psi^{-1}_{L}\left(2^{L({s}+1/2-1/p)}\left\|(f_{Lk})_{k=1}^{2^{l}}\right\|_{p}\leq
R\right)$ $\displaystyle=\text{Pr}\left(2^{-L/p}\left\|Z\right\|_{p}\leq
CR/c_{\alpha}^{3/4}\right)$

where $Z\sim N(0,I_{2^{L}})$ and $C>0$ a constant. The right-hand side of the
above display can be made arbitrarily small for small enough choice of
$c_{\alpha}>0$, following from the fact that $Z$ is a standard normal vector
${\mathbb{E}}\|Z\|_{p}^{p}\lesssim 2^{L}$, where the constant depends on $p$
(see e.g. Proposition 2.5.2 in [83]) and Markov’s inequality. ∎

The larger $L$, the larger the effective dimension of the signal under the
alternative hypothesis. Setting $L$ such that $2^{L}\asymp\rho^{-1/s}$ means
that the requirement of the above lemma are satisfied and consequently the
Gaussian prior most of it its mass in the alternative hypothesis. Recalling
that $d_{L}\asymp 2^{L}$, the condition (35) in the case of local randomness
protocols can be written as

$\rho^{2}\lesssim
c_{\alpha}\sigma^{2}\left(\frac{d_{L}^{3/2}}{mn(n\epsilon^{2}\wedge
d_{L})}\bigwedge\left(\frac{\sqrt{d_{L}}}{\sqrt{m}n\sqrt{n\epsilon^{2}\wedge
1}}\bigvee\frac{1}{mn^{2}\epsilon^{2}}\right)\right),$ (S.8)

and in the case of shared randomness protocols, (37) can be written as

$\rho^{2}\lesssim
c_{\alpha}\sigma^{2}\left(\frac{d_{L}}{mn\sqrt{n\epsilon^{2}\wedge
1}\sqrt{n\epsilon^{2}\wedge
d_{L}}}\bigwedge\left(\frac{\sqrt{d_{L}}}{\sqrt{m}n\sqrt{n\epsilon^{2}\wedge
1}}\bigvee\frac{1}{mn^{2}\epsilon^{2}}\right)\right).$ (S.9)

###  A.2 Step 2: Approximating the distribution of the transcripts

In Step 3, we aim to use the Brascamp-Lieb type inequality Lemma 10.1 of [77],
which we restate as Lemma 12 below. However, the _forward-backward channel_
corresponding to ${K}_{u}$, $(x_{1},x_{2})\mapsto{q}_{u}(x_{1},x_{2})$,
defined as

${q}_{u}(x_{1},x_{2}):=\int\frac{d{K}(\cdot|x_{1},u)}{d{\mathbb{P}}_{0}^{Y|U=u}}(y)\frac{d{K}(\cdot|x_{2},u)}{d{\mathbb{P}}_{0}^{Y|U=u}}(y)d{\mathbb{P}}^{Y|U=u}_{0}(y),$
(S.10)

is possibly unbounded when $\delta>0$. To overcome this, we use Lemma 6 below
to construct $(\epsilon,3\delta)$-DP Markov kernels
$\\{\tilde{K}^{j}\\}_{j=1}^{m}$ such that the corresponding forward-backward
channel $\tilde{q}_{u}(x_{1},x_{2})$ is bounded. The construction of
$\\{\tilde{K}^{j}\\}_{j=1}^{m}$ is such that the total variation distance
between $\tilde{K}^{j}$ and $\tilde{K}^{j}$ is small.

######  Lemma 6.

For any $\alpha\in(0,1)$ and $(\epsilon,\delta)$-DP collection of Markov
kernels $\\{K^{j}\\}_{j=1}^{m}$, there exists a collection of
$(\epsilon,3\delta)$-DP kernels $\\{\tilde{K}^{j}\\}_{j=1}^{m}$ such that for
some fixed constant $C>0$,

$\underset{x\in{\mathcal{X}}^{n}}{\sup}\;\frac{d\tilde{K}^{j}(\cdot|x)}{dP_{0}\tilde{K}^{j}(\cdot|X^{(j)})}(y)<C,\;P_{0}\tilde{K}^{j}(\cdot|X^{(j)})\text{-almost
surely},$ (S.11)

whilst

$\|P_{f}(K^{j}(\cdot|X^{(j)})-\tilde{K}^{j}(\cdot,X^{(j)}))\|_{\mathrm{TV}}\leq\frac{\alpha}{2m}.$

###### Proof.

For any $x\in{\mathcal{X}}^{n}$ and set $A\in\mathcal{\mathscr{Y}}^{(j)}$, we
have that

$K^{j}(A|x)=\int_{A}\frac{dK^{j}(\cdot|x)}{dP_{0}K^{j}(\cdot|X^{(j)})}(y)dP_{0}K^{j}(y|X^{(j)})\leq
1,$

where we note that by Lemma 39, the density of the integrand exists. So, by
Markov’s inequality, there exists a set
$A_{x}^{M}\in\mathcal{\mathscr{Y}}^{(j)}$ such that

$\frac{dK^{j}(\cdot|x)}{dP_{0}K^{j}(\cdot|X^{(j)})}(y)\leq M\;\text{ on
}A_{x}^{M},$

whilst

$K^{j}\left((A_{x}^{M})^{c}|x\right)\leq 1/M.$ (S.12)

Define for all $x\in{\mathcal{X}}$,

$\tilde{K}^{j}(B|x):=\frac{K^{j}(B\cap A_{x}^{M}|x)}{K^{j}(A_{x}^{M}|x)},$

which can be rewritten as

$K^{j}\left(B\cap
A_{x}^{M}|x\right)+K^{j}\left((A_{x}^{M})^{c}|x\right)\frac{K^{j}(B\cap
A_{x}^{M}|x)}{K^{j}(A_{x}^{M}|x)}.$ (S.13)

Then, $\tilde{K}^{j}$ is $(\epsilon,3\delta)$-DP whenever $M>4\delta^{-1}$;
for any $x,x^{\prime}\in{\mathcal{X}}^{n}$ that are Hamming distance $1$-apart
and $B\in\mathscr{Y}^{(j)}$,

$\displaystyle\tilde{K}^{j}(B|x)$ $\displaystyle\leq
K^{j}\left(B|x\right)+K^{j}\left((A_{x}^{M})^{c}|x\right)\frac{K^{j}\left(B\cap
A_{x}^{M}|x\right)}{K^{j}\left(A_{x}^{M}|x\right)}$
$\displaystyle=K^{j}\left(B\cap
A_{x^{\prime}}^{M}|x\right)+K^{j}\left(B\cap(A_{x^{\prime}}^{M})^{c}|x\right)+K^{j}\left((A_{x}^{M})^{c}|x\right)\frac{K^{j}\left(B\cap
A_{x}^{M}|x\right)}{K^{j}\left(A_{x}^{M}|x\right)}$ $\displaystyle\leq
e^{\epsilon}K^{j}\left(B\cap
A_{x^{\prime}}^{M}|x^{\prime}\right)+e^{\epsilon}K^{j}\left(B\cap(A_{x^{\prime}}^{M})^{c}|x^{\prime}\right)+2\delta+\frac{1}{M}$
$\displaystyle\leq
e^{\epsilon}\tilde{K}^{j}\left(B|x^{\prime}\right)+(1+e^{\epsilon})M^{-1}+2\delta,$

where the second to last inequality follows by (S.12) and the last inequality
follows by simply adding the nonnegative second term in (S.13). Furthermore,
its Radon-Nikodym derivative satisfies

$\displaystyle\frac{d\tilde{K}^{j}(\cdot|x)}{dP_{0}\tilde{K}^{j}(\cdot|X^{(j)})}(y)$
$\displaystyle\leq
2\text{1}_{A_{x}^{M}}\frac{dK^{j}(\cdot|x)}{dP_{0}{K}^{j}(\cdot|X^{(j)})}(y)\leq
2M$

$P_{0}\tilde{K}^{j}(\cdot|X^{(j)})$-almost surely. Moreover, it holds for any
$f\in\ell_{2}({\mathbb{N}})$ that

$\displaystyle\|P_{f}^{n}(K^{j}(\cdot|X^{(j)})-\tilde{K}^{j}(\cdot,X^{(j)}))\|_{\mathrm{TV}}$
$\displaystyle\leq\int\|K^{j}(\cdot|x)-\tilde{K}^{j}(\cdot|x)\|_{\mathrm{TV}}dP_{f}^{n}(x)$
$\displaystyle\leq
2\int|K^{j}\left((A_{x}^{M})^{c}|x\right)|dP_{f}^{n}(x)\leq\frac{2}{M}.$

Since a choice $M>\delta^{-1}\vee 2m/\alpha$ yields the bound uniformly in
$x\in{\mathcal{X}}^{n}$, the result follows. ∎

By standard arguments (see also Lemma 9), the first term in (S.6) can be lower
bounded as follows;

$\displaystyle P_{0}^{m}{K}_{u}T$
$\displaystyle=P_{0}^{m}\tilde{K}_{u}T+P_{0}^{m}{K}_{u}T-P_{0}^{m}\tilde{K}_{u}T$
$\displaystyle\geq
P_{0}^{m}\tilde{K}_{u}T-\sum_{j=1}^{m}\|P_{0}\tilde{K}^{j}(\cdot|X^{(j)})-P_{0}{K}^{j}(\cdot|X^{(j)})\|_{\mathrm{TV}}.$

The same argument on the second term yields that, we obtain that (S.6) is
lower bounded by

$\int\left(P_{0}^{m}\tilde{K}_{u}T+\int
P_{f}^{m}\tilde{K}_{u}(1-T)d\pi\circ\Psi^{-1}_{L}(f)\right)d{\mathbb{P}}^{U}(u)-3\alpha/8,$
(S.14)

for an $(\epsilon,3\delta)$-DP distributed testing protocol
$\tilde{T}=(T,\\{\tilde{K}^{j}\\}_{j=1}^{m},({\mathcal{U}},\mathscr{U},{\mathbb{P}}^{U}))$.

Another issue suffered by $(\epsilon,\delta)$-DP Markov kernels with
$\delta>0$, is that one has very poor control over the higher moments of the
local likelihoods

${{\mathcal{L}}}^{j}_{\pi,u}(y):=\frac{dP_{\pi}\tilde{K}^{j}(\cdot|X^{(j)},u)}{dP_{0}\tilde{K}^{j}(\cdot|X^{(j)},u)}(y),$

where $P_{\pi}(A):=\int P_{f}(A)d\pi\circ\Psi^{-1}_{L}(f)$, which are required
to sufficiently bound the corresponding quantity $\mathrm{B}_{u}$ defined in
(S.28) in Step 5. Using similar ideas as in the proof of Lemma 6, we can
construct approximating kernels $\\{\breve{K}^{j}\\}_{j=1}^{m}$ such that the
likelihoods ${\mathcal{L}}^{j}_{\pi,u}$ are bounded. This is the content of
the following lemma.

######  Lemma 7.

Let $\alpha\in(0,1)$,
$\pi=N(0,c_{\alpha}^{-1/2}d^{-1/2}_{L}\rho^{2}\bar{\Gamma})$ for an arbitrary
positive semidefinite $\bar{\Gamma}$ and let $\\{K^{j}\\}_{j=1}^{m}$
correspond to a $(\epsilon,\delta)$-DP distributed protocol $T$ (i.e. $K^{j}$
satisfies (S.2)). Furthermore, assume that $\epsilon\leq 1/\sqrt{n}$ and
define for $j=1,\dots,m$ the events

$A_{j,u}:=\left\\{y:|{\mathcal{L}}_{\pi,u}^{j}(y)-1|\leq\frac{4m^{1/2}}{{\alpha}}\right\\}$

and define

$\tilde{K}^{j}(B|x,u):=K^{j}(B\cap
A_{j,u}|x,u)+K^{j}(A_{j,u}^{c}|x,u)\frac{P_{0}K^{j}(B\cap
A_{j,u}|X^{(j)},u)}{P_{0}K^{j}(A_{j,u}|X^{(j)},u)}.$

Suppose in addition that $\delta\leq c_{\alpha}/m$. Then,

  1. (a)

The collection $\\{\tilde{K}^{j}\\}_{j=1}^{m}$ are $(\epsilon,2\delta)$-DP
Markov kernels.

  2. (b)

It holds $P_{0}\tilde{K}^{j}(\cdot|X^{(j)},u)$-a.s. that

$\tilde{{\mathcal{L}}}_{\pi,u}^{j}(y):=\int\frac{d\tilde{K}^{j}(y|x,u)}{dP_{0}\tilde{K}^{j}(y|X^{(j)},u)}dP_{\pi}^{n}(x)$

satisfies

$|\tilde{{\mathcal{L}}}_{\pi,u}^{j}(y)-1|\leq\frac{5m^{1/2}}{{\alpha}}.$
(S.15)

  3. (c)

If $\rho$ satisfies (35) or (37) with $c_{\alpha}>0$ small enough, it holds
that

$\displaystyle P_{0}^{m}KT+\int P_{f}^{m}K(1-T)d\pi\circ\Psi^{-1}_{L}(f)\geq
P_{0}^{m}\tilde{K}T+\int
P_{f}^{m}\tilde{K}(1-T)d\pi\circ\Psi^{-1}_{L}(f)-\alpha,$

where $\tilde{K}$ is the product kernel corresponding to
$\\{\tilde{K}^{j}\\}_{j=1}^{m}$.

  4. (d)

If $K^{j}$ satisfies (S.11), then $\tilde{K}^{j}$ satisfies the same bound for
some constant $C>0$.

We prove this lemma at the end of this section. The lemma above, in
combination with the same argument as before (e.g. Lemma 9) allows us to
replace the $(\epsilon,3\delta)$-DP Markov kernel $\tilde{K}^{j}$ of (S.14)
with an $(\epsilon,6\delta)$-DP Markov kernel $\breve{K}^{j}$, whose
transcripts have bounded likelihoods in the sense of (S.15). Furthermore, by
part _(c)_ of the lemma, the Bayes risk of (S.14) is further lower bounded by

$\int\left(P_{0}^{m}\breve{K}_{u}T+\int
P_{f}^{m}\breve{K}_{u}(1-T)d\pi\circ\Psi^{-1}_{L}(f)\right)d{\mathbb{P}}^{U}(u)-\alpha/2,$
(S.16)

where the $\breve{K}^{j}$’s satisfy (S.11).

####  A.2.1 Proof of Lemma 7

###### Proof.

The first statement follows by Lemma 8 below. For the second statement, we
first note that by Lemma 17 proven in Section A.5, it holds that

$\displaystyle\frac{c_{\alpha}^{1/4}}{m^{1/2}}+\delta+\frac{c_{\alpha}}{m^{3/2}}$
$\displaystyle\geq(P_{\pi}-P_{0})K^{j}\left(\\{|{\mathcal{L}}^{j}_{\pi,u}-1|\geq
4m^{1/2}/\alpha\\}|X^{(j)},u\right)$
$\displaystyle=P_{0}K^{j}\left(({\mathcal{L}}^{j}_{\pi,u}-1)\text{1}\\{|{\mathcal{L}}^{j}_{\pi,u}-1|\geq
4m^{1/2}/\alpha\\}|X^{(j)},u\right)$ $\displaystyle\geq
4\frac{m^{1/2}}{\alpha}P_{0}K^{j}\left(|{\mathcal{L}}^{j}_{\pi,u}-1|\geq
4m^{1/2}/\alpha|X^{(j)},u\right),$

where the second inequality follows from the fact that $m^{1/2}/\alpha\geq 1$
and ${\mathcal{L}}^{j}_{\pi,u}\geq 0$. Using that $\delta\leq c_{\alpha}/m$,
we obtain that

$P_{0}K^{j}(A_{j,u}^{c}|X^{(j)},u)\leq\frac{{\alpha(c_{\alpha}^{1/4}+c_{\alpha}(1+m^{-1}))}}{4{m}}:=\eta_{\alpha}.$
(S.17)

Since $K^{j}(B|x,u)\leq\tilde{K}^{j}(B|x,u)$ for all measurable $B\subset
A_{j,u}$ and $P_{0}\tilde{K}^{j}(\cdot|X^{(j)},u)$ has no support outside of
$A_{j,u}$, it holds that

$\frac{d{K}^{j}(\cdot|x,u)}{dP_{0}\tilde{K}^{j}(\cdot|X^{(j)},u)}(y)\leq\frac{d{K}^{j}(\cdot|x,u)}{dP_{0}{K}^{j}(\cdot|X^{(j)},u)}(y),$

for all $y\in A_{j,u}$ (and hence $P_{0}\tilde{K}^{j}(\cdot|X^{(j)},u)$-a.s.).
Similarly, we have for $P_{\pi}$-a.s. all $x$’s that

$\frac{K^{j}(A_{j,u}^{c}|x,u)}{P_{0}K^{j}(A_{j,u}|X^{(j)},u)}\frac{dP_{0}K^{j}(\cdot\cap
A_{j,u}|X^{(j)},u)}{dP_{0}\tilde{K}^{j}(\cdot|X^{(j)},u)}(y)\leq\frac{K^{j}(A_{j,u}^{c}|x,u)}{P_{0}K^{j}(A_{j,u}|X^{(j)},u)}\leq\frac{1}{1-\eta_{\alpha}},$

using that $K^{j}\leq 1$ and $P_{0}K^{j}(A_{j,u}|X^{(j)},u)\geq
1-\eta_{\alpha}$. By standard arguments and the above two statements, it
follows that

$\displaystyle\int\frac{d\tilde{K}^{j}(y|x,u)}{dP_{0}\tilde{K}^{j}(y|X^{(j)},u)}dP_{\pi}^{n}(x)$
$\displaystyle\leq\text{1}_{A_{j,u}}(y)\int\frac{d{K}^{j}(y|x,u)}{dP_{0}{K}^{j}(y|X^{(j)},u)}dP_{\pi}^{n}(x)+\frac{1}{1-\eta_{\alpha}}$
$\displaystyle=\text{1}_{A_{j,u}}(y){{\mathcal{L}}}_{\pi,u}^{j}(y)+\frac{1}{1-\eta_{\alpha}}.$

Applying the definition of the event $A_{j,u}$ and using that $\alpha\leq 1$,
we obtain that for $c_{\alpha}>0$ small enough

$\displaystyle\tilde{{\mathcal{L}}}_{\pi,u}^{j}-1\leq\frac{4m^{1/2}}{{\alpha}}+\frac{1}{1-\eta_{\alpha}}-1\leq\frac{5m^{1/2}}{{\alpha}}.$

Using that $\tilde{{\mathcal{L}}}_{\pi,u}^{j}-1\geq-1$, we obtain (S.15),
proving statement _(b)_.

For the third statement, we will aim to apply Lemma 9. By the construction of
$\tilde{K}^{j}$ and the triangle inequality,

$\displaystyle\|P_{0}K^{j}(\cdot|X^{(j)},u)-P_{0}\tilde{K}^{j}(\cdot|X^{(j)},u)\|_{\mathrm{TV}}$
$\displaystyle\leq 2\left\|P_{0}K^{j}(\cdot\cap
A_{j,u}^{c}|X^{(j)},u)\right\|_{\mathrm{TV}}.$

The latter is bounded by ${{\alpha}}/({2{m}})$ (see (S.17)). Similarly,

$\displaystyle\|P_{\pi}K^{j}(\cdot|X^{(j)},u)-P_{\pi}\tilde{K}^{j}(\cdot|X^{(j)})\|_{\mathrm{TV}}$
$\displaystyle\leq 2P_{\pi}K^{j}(A_{j,u}^{c}|X^{(j)},u).$

By Lemma 17,

$\displaystyle
P_{\pi}K^{j}(A_{j,u}^{c}|X^{(j)},u)\leq\left(1+c_{\alpha}^{1/4}m^{-1/2}\right)P_{0}K^{j}(A_{j}^{c}|X^{(j)},u)+\delta+\frac{c_{\alpha}}{m^{3/2}}.$

Again using (S.17) and the fact that $\delta\leq c_{\alpha}/m$ yield that the
latter is also bounded by $\alpha/4m$ for $c_{\alpha}>0$ small enough. The
condition and small enough choice of $c_{\alpha}>0$ yields that the conditions
of Lemma 9 and the conclusion of (c) follows. Finally, if $K^{j}$ satisfies
(S.11), the last statement follows directly by the construction of
$\tilde{K}^{j}$. ∎

We finish the section by providing the two technical lemmas mentioned in the
earlier proofs above. We omit the presence of the shared randomness $U$ in the