# Optimal high-dimensional and nonparametric distributed testing under
communication constraints

Botond<EMAIL_ADDRESS>[ Lasse Vuursteenlabel=e2]
<EMAIL_ADDRESS>[ Harry van<EMAIL_ADDRESS>[
Department of Decision Sciences, Bocconi University,
Bocconi Institute for Data Science and Analytics (BIDSA),  Delft Institute of
Applied Mathematics (DIAM), Delft University of Technology  Department of
Mathematics, Vrije Universiteit Amsterdam  Botond
<EMAIL_ADDRESS>[ Lasse Vuursteenlabel=e2]
<EMAIL_ADDRESS>[ Harry van<EMAIL_ADDRESS>[
Department of Decision Sciences, Bocconi University,
Bocconi Institute for Data Science and Analytics (BIDSA),  Delft Institute of
Applied Mathematics (DIAM), Delft University of Technology  Department of
Mathematics, Vrije Universiteit Amsterdam

# Supplementary Material to “Optimal high-dimensional and nonparametric
distributed testing under communication constraints”

Botond<EMAIL_ADDRESS>[ Lasse Vuursteenlabel=e2]
<EMAIL_ADDRESS>[ Harry van<EMAIL_ADDRESS>[
Department of Decision Sciences, Bocconi University,
Bocconi Institute for Data Science and Analytics (BIDSA),  Delft Institute of
Applied Mathematics (DIAM), Delft University of Technology  Department of
Mathematics, Vrije Universiteit Amsterdam  Botond
<EMAIL_ADDRESS>[ Lasse Vuursteenlabel=e2]
<EMAIL_ADDRESS>[ Harry van<EMAIL_ADDRESS>[
Department of Decision Sciences, Bocconi University,
Bocconi Institute for Data Science and Analytics (BIDSA),  Delft Institute of
Applied Mathematics (DIAM), Delft University of Technology  Department of
Mathematics, Vrije Universiteit Amsterdam

###### Abstract

We derive minimax testing errors in a distributed framework where the data is
split over multiple machines and their communication to a central machine is
limited to $b$ bits. We investigate both the $d$\- and infinite-dimensional
signal detection problem under Gaussian white noise. We also derive
distributed testing algorithms reaching the theoretical lower bounds.

Our results show that distributed testing is subject to fundamentally
different phenomena that are not observed in distributed estimation. Among our
findings, we show that testing protocols that have access to shared randomness
can perform strictly better in some regimes than those that do not. We also
observe that consistent nonparametric distributed testing is always possible,
even with as little as $1$-bit of communication and the corresponding test
outperforms the best local test using only the information available at a
single local machine. Furthermore, we also derive adaptive nonparametric
distributed testing strategies and the corresponding theoretical lower bounds.

###### Abstract

In this supplement, we present the detailed proofs for the main theorems in
the paper “Optimal high-dimensional and nonparametric distributed testing
under communication constraints”.

62G10,

62F30,

62F03,

Distributed methods,

Nonparametric,

Hypothesis testing,

Minimax optimal,

62G10,

62F30,

62F03,

Distributed methods,

Nonparametric,

Hypothesis testing,

Minimax optimal,

###### keywords:

[class=MSC2020]

###### keywords:

###### keywords:

[class=MSC2020]

###### keywords:

, and

##  1 Introduction

Distributed methods are concerned with inference in a framework where the data
resides at multiple machines. Such settings occur naturally when data is
observed and processed locally, at multiple locations, before sent to a
central location where they are aggregated to obtain a final result. By
working with smaller sample sizes locally distributed methods can
substantially speed up the computation compared to centralized, classical
methods. Furthermore, they reduce memory requirements and help protecting
privacy by not storing all the information at a single location. For these
reasons, the study of distributed methods has attracted significant attention
in recent years.

In our analysis we first consider the many normal means model, which is often
used as a platform to investigate more complex statistical problems. In the
classical version of the model one obtains an observation $X$ subject to the
dynamics $X=f+n^{-1/2}Z$, where $f\in{\mathbb{R}}^{d}$ is an unknown signal,
and $Z$ an unobserved, $d$-dimensional standard normal noise vector. This is
equivalent to observing $n$ independent copies of a $N_{d}(f,I_{d})$ vector.
Our focus is on testing the absence or presence of the signal component $f$ in
the model. Rejecting the null hypothesis $H_{0}:\,f=0$ means declaring that
there is a non-zero signal underlying the observation $X$. The difficulty of
distinguishing between the two hypotheses depends on signal strength, the
noise ratio $n$ and dimension $d$. It is well known that the signal strength
in terms of the Euclidean norm of $f$ needs to be at least of the order
$d^{1/4}/\sqrt{n}$ for the hypotheses to be distinguishable, see e.g. [6].

We study this signal detection problem in a distributed setting. In the
distributed version of the above normal-means model, the $n$ observations are
divided over $m$ machines (assuming without loss of generality that $n$ is a
multiple of $m$). Equivalently, each local machine $j\in\\{1,\dots,m\\}$
observes

$X^{j}=f+\sqrt{\frac{m}{n}}Z^{j},$ (1)

where $f\in{\mathbb{R}}^{d}$ and the noise vectors $Z^{j}$ are independent
$d$-dimensional standard normal random vectors. Each machine $j$ transmits a
$b$-bit transcript $Y^{j}$ to a central machine. By aggregating these $m$
local transcripts, the central machine computes a test for the hypothesis
$H_{0}:f=0$. We derive, for this distributed setting, the order of the minimal
signal strength $\rho$ for which the null hypothesis can be distinguished from
the alternative $H_{1}:\|f\|_{2}\geq\rho$. In the distributed setting, $\rho$
is considered as a function of the number of machines $m$ and the
communication budget $b$, in addition to the dimension $d$ and noise level
$n$. We allow all the parameters $b,m$ and $d$ to depend on $n$.

The transcripts generated by the machines may be either deterministic or
randomized. When randomizing the transcript, we consider two different
possibilities for the source of randomness. In the _private coin_ setup, the
machines may only use their own local (independent) source of randomness. In
the _public coin_ setup, the machines have access to a shared source of
randomness in addition to their own independent source. This is akin to a
situation in which the machines have access to the same random seed. We show
that depending on the size of the communication budget, having access to a
public coin strictly improves the distinguishability of the null- and
alternative hypothesis.

Our results indicate that, in the case where $b$ and $m$ are small relative to
the dimension $d$ in an appropriate sense, the one-bit protocols have similar
properties, in terms of separation rate, as multi-bits protocols, i.e. one can
achieve the minimax optimal $b$-bit testing rates with taking the majority
vote of appropriately chosen local (one-bit) test outcomes. This is a striking
difference with estimation, where for small values of $b$, increases in the
communication budget result in (sometimes exponential) improvements in
convergence rate. We find that, as $m$ increases, the local testing problems
become more difficult as the local sample size deceases, but at a certain
threshold, this effect is compensated for by the increase in total
communication budget $bm$. This threshold occurs when $bm$ exceeds the
dimension. At this point, we find that public coin protocols start to strictly
outperform private coin protocols, in the sense that smaller signals can be
detected with the same amount of transmitted bits $b$. This is also a
dissimilarity with estimation, where having access to public randomness offers
no benefit, as we show it in our paper. When the communication budget $b$ per
machine exceeds that of the dimension $d$ of the problem, the minimax rates of
the classical, non-distributed setting can be attained.

We then extend our results for the $d$-dimensional Gaussian model to the
nonparametric signal in white noise setting. This latter model is of interest
as it serves as benchmark and starting point to investigate more complicated
nonparametric models. Here, the local observations for $j=1,\dots,m$
constitute $\int_{0}^{\cdot}f(s)ds+\sqrt{\frac{m}{n}}W^{j}_{\cdot}$ where the
$W^{j}$’s are independent Brownian motions and $f\in L_{2}[0,1]$ the unknown
functional parameter of interest. Our results for the infinite dimensional
model comes in the form of minimax rates for distributed protocols in terms of
the strength of the signal in $L_{2}$-norm, the smoothness $s$ of the signal,
the amount of bits $b$ allowed to be communicated by each machine, the signal
to noise ratio $n$ and the number of machines $m$. In contrast to
nonparametric distributed estimation, we show that consistent distributed
testing is always possible, even when $m$ and $b$ are small. Having a shared
source of randomness results in better rates in certain regimes in the
nonparametric setting, whilst we show that this is never the case for
distributed estimation. Finally, we consider the more realistic, adaptive
setting where the regularity $s$ is considered to be unknown. We show that in
contrast to the non-distributed setting where the cost for adaptation is a
multiplicative $\log\log n$ factor, in the distributed case a more severe
$\log n$ penalty is necessary. We also propose a nonparametric distributed
testing procedure based on Bonferroni’s correction reaching the theoretical
limits (up to a $\log\log n$ factor) and observe additional, unexpected phase
transitions compared to the non-adaptive setting.

###  1.1 Related literature

Starting a few decades ago, earlier investigations into similar topics
originate in the electrical engineering community, under the names
“decentralized decision theory / the CEO problem” e.g. [38, 4, 39, 9, 25, 37]
or “inference under multiterminal compression” (see [21] for an overview).
Motivated by applications such as surveillance systems and wireless
communication, the inference problems are approached from a “rate-distortion”
angle in this body of literature. However, these results typically consider
fixed, finite sample spaces and a fixed number of machines $m$ and investigate
asymptotics only in the sample size $n$.

Understanding the fundamental statistical performance of distributed methods
in context of non-discrete, higher-dimensional sample spaces has been
considered only recently. Most of the literature focused on estimating the
parameter/signal of the model in a distributed framework. Minimax lower and
(up to a possible logarithmic factor) matching upper bounds were derived for
the minimax risk in terms of communication constraints in context of the many
normal means and simple parametric problems, see [43, 19, 30, 11, 41, 22, 13,
12]. These results were extended to nonparametric models, including Gaussian
white noise [44], nonparametric regression [32], density estimation [7] and
general, abstract settings [36]. Distributed techniques for adapting to the
unknown regularity of the functional parameter of interest were derived in
[32, 33, 14].

For distributed testing, much less is known. In [1], the authors consider a
setting in which each machine obtains a single observation from a distribution
on a finite sample space and derive lower bounds for testing uniformity of
this distribution. Similar distributed uniformity testing is considered in
[2], where matching upper bounds are exhibited for this setting. In [34], the
authors derive matching upper and lower bounds for the distributed version of
the classical many normal means model (see (1) above) for the case that only
the outcome of local tests can be communicated (e.g. $1$-bit of
communication). In [3] less stringent communication requirements are
considered, in the special case of the model in (1) above with $m=n$.
Questions regarding nonparametric models and adaptation in the setting of
distributed testing have remained completely open thus far.

To summarize the state of the art, the lower bounds derived in the literature
so far are only optimal in case of constant communication budget in the public
coin setting, i.e. $b=O(1)$. So far no lower bound results are available in
the public coin setting if $b$ can tend to infinity as $n$ increases.
Furthermore, there is a lack of any lower bound result in the private coin
setup. The traditional methods based on mutual information and Taylor
expansion as considered in [34] and [3], respectively, do not extend to the
setting of multiple bits or private coin protocols. In this article we fill
this gap and derive the first rigorous minimax lower bounds for distributed
testing procedures in the normal means model for arbitrary communication
budget $b$ both for private and public coin settings. In order to prove the
lower bounds, we provide a novel Bayesian testing argument based on a
Brascamp-Lieb type inequality with distributed version of testing lower
bounding techniques.

The upper bounds derived in [3] are more complete for both the private and
public coin settings and go beyond the above described restrictive setting in
which the lower bounds were derived, but do not cover all possible cases. For
instance, in [3] it is assumed that the separation distance between the null
and alternative hypotheses is bounded from above by one, which does not cover
the case $\sqrt{dm}\gg n$. Also, only the $m=n$ case was considered in the
preceding paper. Therefore, in certain regimes new testing procedures and
proof techniques had to be derived for full treatment of the problem (e.g. our
novel test $T_{\text{III}}$ in the high-budget private coin case, see Section
4.3).

The literature on distributed testing has so far solely focused on finite
dimensional models. We provide the first results for distributed testing in
nonparametric models. Besides deriving lower and matching upper bounds we also
derive an adaptive testing procedure, not depending on the typically unknown
regularity of the underlying functional parameter of interest.

###  1.2 Overview of our results and organization

For a quick overview, the main contributions of this article are:

  * •

Sharp minimax upper- and lower bounds for all values of $n,m,d,b$ for the
$d$-dimensional distributed-signal-in-white-noise model, for both private and
public coin settings (Section 3), with accompanying methods achieving these
rates (Theorem 3.1 and Theorem 3.2).

  * •

We extend the $d$-dimensional distributed-signal-in-white-noise model to the
nonparametric setting where the signal is a Sobolev regular functional
parameter of known regularity and establish the minimax rates within this
setting for all values of $n,m,b$ for both the private and public coin
settings (Theorem 6.1).

  * •

We consider the nonparametric setting in which the regularity of underlying
signal is unknown and derive adaptive private and public coin procedures.
Furthermore, we establish private and public coin lower bounds for the
adaptive setting that are tight up to a $\log\log n$ factor for all values of
$n,m,b$ (Theorem 7.1 and Theorem 7.2).

The remainder of the paper is organized as follows. In Section 2 we describe
the distributed-signal-in-white-noise model with $d$-dimensional signal
$f\in\mathbb{R}^{d}$ and formalize the distributed testing problem both for
private and public coin protocols. In Section 3 we provide the minimax lower
and matching upper bounds for both testing protocols. Section 5 gives a sketch
of the proof of the lower bound. We exhibit constructive algorithms that
achieve matching upper bounds in Section 4. We extend our results to the
nonparametric distributed-signal-in-white-noise model with Sobolev regular
functional parameter in Section 6. Here, we also compare distributed testing
and estimation rates and highlight the similarities and differences between
them both in the private and public coin settings. In Section 7, we consider
adaptation to the unknown regularity level in the nonparametric setting and
present theoretical lower and matching upper bounds. In Section 8, we derive
constructive algorithms achieving these upper bounds. The detailed proof of
the lower bound for the $d$-dimensional signal is deferred to Section 9 and a
key technical lemma described in Section 10. Detailed proofs for this lemma,
as well as some of the technical details of the other main results and various
auxilliary results, have been deferred to the Supplementary Material [35] to
this manuscript. Results, equations and sections in the Supplementary Material
are indexed by capital letters as opposed to numerals, as is used in the
article.

###  1.3 Notation

We write $a\wedge b=\min\\{a,b\\}$ and $a\vee b=\max\\{a,b\\}$. For two
positive sequences $a_{n},b_{n}$ we use the notation $a_{n}\lesssim b_{n}$ if
there exists a universal positive constant $C$ such that $a_{n}\leq Cb_{n}$.
We write $a_{n}\asymp b_{n}$ which holds if $a_{n}\lesssim b_{n}$ and
$b_{n}\lesssim a_{n}$ are satisfied simultaneously. We shall use $a_{n}\gg
b_{n}$ to denote $b_{n}/a_{n}\to 0$. The Euclidean norm of a vector
$v\in\mathbb{R}^{d}$ is denoted by $\|\cdot\|_{2}$. For absolutely continuous
probability measures $P\ll Q$, we denote by
$D_{KL}(P\|Q)=\int\log\frac{dP}{dQ}dP$ and
$D_{\chi^{2}}(P\|Q)=\int(\frac{dP}{dQ}-1)^{2}dP$ their Kullback-Leibler and
Chi-square divergences, respectively. Throughout the whole text we use for
convenience the abbreviation rhs and lhs for right-hand-side and left-hand-
side, respectively, and cdf for the cumulative distribution function.

##  2 Problem formulation and setting

We consider testing in the distributed-signal-in-white-noise model. In this
section, we provide the formulation of the distributed setup for data coming
from the finite dimensional model. Except for obvious modifications to the
sample space, the same setup is considered when the local data is from the
infinite dimensional distributed-signal-in-white-noise model, which is
formulated in Section 6. For $j=1,\dots,m$ machines, the local observations
constitute $X^{j}$ taking values in ${\mathcal{X}}\subset{\mathbb{R}}^{d}$,
subject to dynamics (1) under $P_{f}$. Each machine $j$ communicates a $b$-bit
transcript $Y^{j}$ to a central machine. That is, the transcript $Y^{j}$ takes
values in some space ${\mathcal{Y}}^{j}$ with $|{\mathcal{Y}}^{j}|\leq 2^{b}$
for $b\in{\mathbb{N}}$. Let $Y=\left(Y^{1},\dots,Y^{m}\right)$ denote the
aggregated data in the central machine. The central machine computes a test
$T(Y)$, where $T$ is a map from
${\mathcal{Y}}:=\bigotimes_{j=1}^{m}{\mathcal{Y}}^{j}$ to $\\{0,1\\}$ that has
to distinguish between the null hypothesis $f=0$ and the alternative
hypothesis. As alternative hypothesis, we consider whether

$f\in H_{\rho}:=\left\\{f\in{\mathbb{R}}^{d}:\|f\|_{2}\geq\rho\right\\},$

for some appropriately chosen $\rho=\rho_{m,n,d,b}$.

We distinguish two mechanisms through which the local machines $j=1,\dots,m$
can generate their transcripts $Y^{j}$. In the first setup, machines can use
only their local observation $X^{j}$ when generating $Y^{j}$, possibly in
combination with a local source of randomness. In the second setup, we allow
the machines to access a common source of randomness $U$, which is independent
of the data $X:=(X^{1},\ldots,X^{m})$. In the latter setup, which we call the
public coin setting, the machines may use both local randomness, the observed
draw of $U$ and their local observation $X^{j}$ when generating their
transcript $Y^{j}$. The setup where only local randomness is available shall
be referred to as the private coin setting. A formal definition of these two
setups is as follows.

  * •

A _private coin distributed testing protocol_ consists of a map
$T:{\mathcal{Y}}\to\\{0,1\\}$ and a collection of Markov kernels
$K^{j}:2^{{\mathcal{Y}}^{j}}\times{\mathcal{X}}^{j}\to[0,1]$, $j=1,\dots,m$,
and the transcript satisfies $Y^{j}|X^{j}\sim K^{j}(\cdot|X^{j})$.

  * •

A _public coin distributed testing protocol_ consists of a map
$T:{\mathcal{Y}}\to\\{0,1\\}$, a random variable $U$ taking values in a
probability space $({\mathcal{U}},\mathscr{U},{\mathbb{P}}^{U})$ and a
collection of Markov kernels
$K^{j}:2^{{\mathcal{Y}}^{j}}\times{\mathcal{X}}^{j}\times{\mathcal{U}}\to[0,1]$,
$j=1,\dots,m$, such that $Y^{j}|(X^{j},U)\sim K^{j}(\cdot|X^{j},U)$.

The choices for the kernels induce the conditional distribution of
$Y=(Y^{1},\dots,Y^{m})$, which we will denote
$K:={\bigotimes}^{m}_{j=1}K^{j}$. For the joint distribution of $X$, $Y$ and
$U$ we shall write ${\mathbb{P}}_{f,K}\equiv{\mathbb{P}}_{f}$, where the $f$
subscript indicates the dynamics underlying $X$ and the subscript $K$ is used
to stress that the conditional distribution of $Y$ induced by the choice of
kernels. Furthermore, we denote by $\mathbb{P}_{f}^{X}$ the corresponding
marginal distribution of X, i.e. $\mathbb{P}_{f}^{X}=P_{f}$. Our distributed
architecture in the public coin case then follows the following Markov chain
structure at each local machine $j=1,...,m$

$\begin{matrix}&\qquad&\qquad
U&\qquad\put(0.0,3.0){\vector(3,-1){20.0}}\qquad&\\\
&\qquad&\qquad&\qquad&\quad Y^{j}.\\\
f&\qquad\put(0.0,3.0){\vector(1,0){20.0}}&\qquad
X^{j}&\qquad\put(0.0,3.0){\vector(3,1){20.0}}\qquad&\end{matrix}$ (2)

Note that any private coin testing protocol can effectively be considered a
public coin testing protocol for which $U$ has degenerate distribution, i.e.
$U=u\in{\mathcal{U}}$ almost surely. In our proofs below, for the sake of
compactness, we consider without loss of generality that the private coin
setting implies $U$ has a degenerate distribution. When no confusion can
arise, we will refer to a distributed testing protocol as “distributed test”,
and we will refer to the tuple $(T,\\{K^{1},\dots,K^{m}\\},{\mathbb{P}}^{U})$
by $T$ for ease of notation. We use ${\mathcal{T}}_{priv}(b)$ and
${\mathcal{T}}_{pub}(b)$ to denote the classes of all private and public coin
distributed tests, respectively, each with communication budget $b$ per
machine.

We define the testing risk of a distributed test
$T\equiv(T,K,{\mathbb{P}}^{U})$ for the alternative hypothesis $H_{\rho}$ as
the sum of the Type I and Type II errors, i.e.

${\mathcal{R}}(H_{\rho},T):={\mathbb{P}}_{0}\left(T(Y)=1\right)+\underset{f\in
H_{\rho}}{\sup}\;{\mathbb{P}}_{f}\left(T(Y)=0\right).$ (3)

##  3 Minimax upper and lower bounds in the normal means model

Our main results come in the form of two theorems. The first establishes the
lower bounds for the detection threshold for both the public- and private coin
distributed tests. We provide the proof of this theorem in Section 9. The
second theorem establishes the optimality of the lower bound posed in the
first theorem by providing distributed tests in both the public and private
coin cases which attain the respective rates posed by the lower bounds. These
optimal distributed testing procedures are described in Section 4. We note
that our results are not asymptotic in nature as they hold for every
combination of $b,n,m$ and $d$, hence going beyond the classical parametric
framework.

######  Theorem 3.1.

[Distributed testing lower bound] For each $\alpha\in(0,1)$ there exists a
constant $c_{\alpha}>0$ (depending only on $\alpha$) such that if

$\rho^{2}<c_{\alpha}\frac{\sqrt{d}}{n}\left(\sqrt{\frac{d}{b\wedge
d}}\bigwedge\sqrt{m}\right),$ (4)

then in the public coin protocol case

$\underset{T\in{\mathcal{T}}_{pub}(b)}{\inf}\;\;{\mathcal{R}}(H_{\rho},T)>\alpha\;\text{
for all }\;n,m,d,b\in{\mathbb{N}}.$

Similarly, for

$\rho^{2}<c_{\alpha}\frac{\sqrt{d}}{n}\left(\frac{d}{b\wedge
d}\bigwedge\sqrt{m}\right),$ (5)

we have under the private coin protocol that

$\underset{T\in{\mathcal{T}}_{priv}(b)}{\inf}\;\;{\mathcal{R}}(H_{\rho},T)>\alpha\;\text{
for all }\;n,m,d,b\in{\mathbb{N}}.$

The approach to proving the lower bound theorem can be summarized as follows.
We start out by lower bounding the testing risk by a type of Bayes risk, where
the parameter $f$ is drawn from an adversarial prior distribution $\pi$. By
taking $\pi$ to be Gaussian, we can exploit the conjugacy of the model in
order to show that optimal transcripts are either invariant to the prior or
“Gaussian” in an appropriate sense. After this, the results follow by data
processing arguments that are geometric in nature. We defer a more elaborate
sketch of the proof to Section 5 and the detailed proof to Section 9. The
techniques used in this work are novel and drastically different than those
used in [3, 34], which provide tight bounds only in the $1$-bit case.

The above theorem implies that if (4) holds, no consistent public coin
distributed testing protocol with communication budget $b$ bits per machine
exists for the hypotheses $H_{0}:f=0$ versus the alternative
$H_{1}:\|f\|_{2}\geq\rho$. In other words, no public coin distributed test
manages to consistently distinguish all signals from $0$ if the signals are
smaller than the rhs of (4). When considering only private coin distributed
testing protocols, the detection threshold (5) is more stringent than the
public coin threshold (4) for certain values of $d$, $m$ and $b$. Theorem 3.2
below affirms that, in these cases, the best private coin protocol have a
strictly worse performance compared to the best public coin protocol.

######  Theorem 3.2.

For each $\alpha\in(0,1)$ there exists a constant $C_{\alpha}>0$ (depending
only on $\alpha$) such that if

$\rho^{2}\geq C_{\alpha}\frac{\sqrt{d}}{n}\left(\sqrt{\frac{d}{b\wedge
d}}\bigwedge\sqrt{m}\right),$

there exists $T\in{\mathcal{T}}_{pub}(b)$ such that

${\mathcal{R}}(H_{\rho},T)\leq\alpha\;\text{ for all
}\;n,m,d,b\in{\mathbb{N}}.$

Similarly, for

$\rho^{2}\geq C_{\alpha}\frac{\sqrt{d}}{n}\left(\frac{d}{b\wedge
d}\bigwedge\sqrt{m}\right)$

there exists $T\in{\mathcal{T}}_{priv}(b)$ such that

${\mathcal{R}}(H_{\rho},T)\leq\alpha\;\text{ for all
}\;n,m,d,b\in{\mathbb{N}}.$

The achievability of arbitrarily small testing risk is shown using a
constructive proof, see Section 4. That is, we derive distributed testing
protocols that distinguish the null hypothesis from any $f\in{\mathbb{R}}^{d}$
in the alternative class.

Theorem 3.1 together with Theorem 3.2 establish the minimax distributed
testing rate for public and private coin protocols. As a sanity check, note
that when $m=1$, we obtain the non-distributed minimax testing rate
$\rho^{2}=\sqrt{d}/n$. Furthermore, when $b\gtrsim d$, enough information
about the coefficients can be communicated to obtain the non-distributed
minimax rate also, for both the public coin and private coin distributed
protocols. When the communication budget is smaller than the dimension
($b=o(d)$), the class of public coin protocols starts to exhibit strictly
better performance than the private coin ones in scenarios as long as
$d=o(mb)$. That is, as long as the total communication budget $mb$ of the
system exceeds the dimension $d$ of the parameter, public coin protocols
achieve a strictly better rate than private coin ones. This remarkable
phenomenon disappears when the dimension is larger than the total
communication budget (i.e. $mb=o(d)$), at which point there exists a one-bit
private coin protocol achieving the optimal rate of
$\rho^{2}\asymp\frac{\sqrt{md}}{n}$ in both cases. Consistent distributed
testing turns out to be possible even for small values of $b$ and $m$, as long
as $n$ is large enough compared to $d$. This stands in contrast to estimation
in the $d$-dimensional Gaussian mean model, where consistent estimation is not
possible when $mb=o(d)$, regardless of sample size $n$ (see e.g. [13]).
Furthermore, as long as $mb=o(d)$ in the public coin case or $mb^{2}=o(d^{2})$
in the private coin case, an increase in communication budget does not lead to
a better rate. This stands in stark contrast to estimation, where for small
budgets an increase can lead to an exponential improvement in convergence
rate.

##  4 Distributed testing protocols achieving the lower bound in the many
normal means model

In this section, we exhibit three distributed testing procedures achieving the
rates posed by the lower bound. The first distributed testing procedure
$T_{\text{I}}$ communicates only a single bit per machine and can detect
signals with a squared Euclidean norm of larger or equal order than
$\frac{\sqrt{dm}}{n}$ and does not need a public coin. As a second procedure,
we consider a test satisfying the public coin protocol $T_{\text{II}}$ that
achieves the rate $\frac{d}{n\sqrt{b\wedge d}}$. The third procedure satisfies
the private coin protocol and achieves the corresponding slower rate
$\frac{d}{n(b\wedge d)}$. Note that, depending on the values of $n,m,d$ and
$b$, the existence of such distributed testing protocols proves Theorem 3.2
and implies that the lower bounds in Theorem 3.1 are in fact tight.

A common denominator in the construction of the three protocols is that the
transcripts $Y^{j}$ are generated as vector of $p_{f}^{j}$-Bernoulli random
variables taking values in $\\{0,1\\}^{b}$ where $p_{f}^{j}\in[0,1]^{b}$
depends on the underlying signal $f$, with $p_{f}^{j}=(1/2,\dots,1/2)$ under
the null hypothesis ($f=0$). The concentration inequality for groups of
Bernoulli random variables given in Lemma 4.1 provides a recipe for the
construction of a central test for each of the three regimes. The Type I error
can be controlled since the distribution under the null hypothesis is known.
The Type II error is small whenever the vectors of probabilities
$p_{f}^{1},\dots,p_{f}^{m}$ are sufficiently separated from $(1/2,\dots,1/2)$
in Euclidean norm.

######  Lemma 4.1.

Consider for $k,l\in{\mathbb{N}}$, $l\geq 2$, independent random variables
$\\{B^{j}_{i}:i=1,\dots,k,\;j=1,\dots,l\\}$ with
$B^{j}_{i}\sim\text{Ber}(p_{i})$. If $p_{i}=1/2$ for $i=1,\dots,k$, it holds
that for all $\alpha\in(0,1)$ there exists $\kappa_{\alpha}>0$ such that

$T:=\text{1}\left\\{\bigg{|}\frac{1}{\sqrt{k}l}\underset{i=1}{\overset{k}{\sum}}\left(\underset{j=1}{\overset{l}{\sum}}(B_{i}^{j}-\frac{1}{2})\right)^{2}-\sqrt{k}/4\bigg{|}\geq\kappa_{\alpha}\right\\}$

satisfies ${\mathbb{E}}T\leq\alpha/2$. On the otherhand, if

$\eta_{p,l,k}:=\frac{l-1}{2\sqrt{k}}\underset{i=1}{\overset{k}{\sum}}\left(p_{i}-\frac{1}{2}\right)^{2}\geq\kappa_{\alpha},$
(6)

it holds that

${\mathbb{E}}(1-T)\leq\frac{1/2+16\eta_{p,l,k}/\sqrt{k}}{\eta_{p,l,k}^{2}}.$
(7)

The proof of the lemma can be found in Section A.2 of the Supplementary
Material where it is restated as Lemma A.4. We also provide a version of this
lemma (Lemma A.5 in the Supplement) used in the high-budget private coin
protocol case.

###  4.1 Low communication budget: construction of $T_{\text{I}}$

The protocol presented here is similar to the one given in [34], with some
adjustment allowing the application of Lemma 4.1 for a simpler proof.

We first compute the local test statistic
$S_{\text{I}}^{j}=(n/m)\|X^{j}\|_{2}^{2}$ at every machine $j=1,...,m$. Under
the null hypothesis, $S_{\text{I}}^{j}$ follows a chi-square distribution with
$d$ degrees of freedom, i.e. $S_{\text{I}}^{j}\sim\chi^{2}_{d}$. Letting
$F_{\chi^{2}_{d}}$ denote $\chi^{2}_{d}$-cdf, the quantity
$F_{\chi^{2}_{d}}\left(S_{\text{I}}^{j}\right)$ can be seen as the p-value for
the local test statistic $S_{\text{I}}^{j}$. Based on these “local p-values”,
we then generate the randomized transcript $Y_{\text{I}}^{j}$ for every $j$
using Bernoulli random variables:

$Y_{\text{I}}^{j}|S_{\text{I}}^{j}\sim\text{Ber}\left(F_{\chi^{2}_{d}}\left(S_{\text{I}}^{j}\right)\right).$

For a given $\alpha\in(0,1)$, we can construct the test

$T_{\text{I}}=\text{1}\Big{\\{}\Big{|}\frac{1}{m}\Big{(}\underset{j=1}{\overset{m}{\sum}}(Y_{\text{I}}^{j}-1/2)\Big{)}^{2}-{1/4}\Big{|}\geq{\kappa}_{\alpha}\Big{\\}}$
(8)

at the central machine. In applications, one could set for instance
$\kappa_{\alpha}$ such that ${\mathbb{P}}_{0}T_{\text{I}}\approx\alpha$ by
considering that $\sum_{j=1}^{m}Y_{I}^{j}$ is $(m,1/2)$-binomially distributed
under the null. Lemma A.6 in the Supplementary Material yields that for each
$\alpha\in(0,1)$, there exist constants
$\kappa_{\alpha},C_{\alpha},M_{\alpha},D_{0}>0$ such that for $m\geq
M_{\alpha}$ and $d\geq D_{0}$ it holds that
${\mathcal{R}}(H_{\rho},T_{\text{I}})\leq\alpha$, whenever $\rho^{2}\geq
C_{\alpha}\frac{\sqrt{md}}{n}$.

The case $m\leq M_{\alpha}$ corresponds essentially to the non-distributed
setting and is treated separately for technical reasons. In practice, one
would simply use the test given in (8) also for $m\leq M_{\alpha}$.
Furthermore, if one allows for a slightly larger amount of bits (e.g.
$\log_{2}(n)$ bits), one could opt to transmit an (approximation of) the test
statistics $S_{\text{I}}^{j}$ themselves, see e.g. Lemma 2.3 in [33], for
which it is easy to prove that the rate of $\frac{\sqrt{md}}{n}$ is achieved
without requiring any assumptions on $m$. For the sake completeness: by
considering $\rho^{2}\geq C_{\alpha}\sqrt{M_{\alpha}}\frac{\sqrt{d}}{n}$, we
see that the optimal rate of $\frac{\sqrt{md}}{n}$ can be achieved in the
$m\leq M_{\alpha}$ case by simply taking

$T_{\text{I}}^{\prime}:={Y_{\text{I}}^{1}}:={\text{1}\left\\{\frac{1}{\sqrt{d}}\left(S_{\text{I}}^{1}-d\right)\geq\kappa_{\alpha}\right\\}}$
(9)

for an appropriately large choice of the constant $\kappa_{\alpha}$.
Similarly, the requirement that $d$ is larger than some constant $D_{0}$
(which is independent of $\alpha$) appears for technical reasons. The case
where $d\leq D_{0}$ is covered by the private coin protocol $T_{\text{III}}$
in Section 4.3.

###  4.2 Public coin, high communication budget: construction of
$T_{\text{II}}$

We now switch our attention to exhibiting a testing procedure that is optimal
when $bm\gtrsim d$ in the public coin case. That a shared source of randomness
in distributed settings can be strictly better than private ones in terms of
_communication complexity_ , is an idea that goes back to [42]. Essentially,
the use of shared randomness allows for the machines coordinate their efforts
in “covering” each of the $d$ dimensions of the data even though all
communication happens in just one round. See also e.g. Chapter 3 in [29] for
an extensive treatment of this phenomenon. We adopt ideas proposed by [3], who
consider the setting where $m=n$ with asymptotics in $m$. We exhibit this
testing protocol below and provide a full proof covering also the case where
$m\neq n$. To that extend, let $U$ be a random rotation, i.e. $U$ is drawn
from the Haar measure (see e.g. Theorem F.13 in [5]) on the set of orthonormal
matrices in ${\mathbb{R}}^{d\times d}$. At each machine, for $b\leq d$, we can
compute the $b$-bit transcript $Y^{j}_{\text{II}}\in\\{0,1\\}^{b}$
conditionally on the shared public coin draw $U$, where each of the $1\leq
i\leq b$ components is defined through

$(Y^{j}_{\text{II}})_{i}|U,X^{j}=\text{1}\left\\{\left(\sqrt{n/m}UX^{j}\right)_{i}>0\right\\},$

where $\left(v\right)_{i}$ denotes the projection onto the $i$-th coordinate
of the vector $v\in{\mathbb{R}}^{d}$. The random rotation fulfills a similar
purpose as the random reweighting algorithm proposed in [34], but leads to an
easier proof in the $d$-dimensional case because of rotational invariance of
the Gaussian distribution.

Centrally, after transmitting $(Y^{1},\dots,Y^{m})$, we compute the aggregated
test statistics $S_{\text{II}}=\sum_{j=1}^{m}Y^{j}_{\text{II}}$ and define the
corresponding test as

$T_{\text{II}}=\text{1}\Big{\\{}\Big{|}\frac{1}{\sqrt{b}m}\underset{i=1}{\overset{b}{\sum}}\Big{(}(S_{\text{II}})_{i}-\frac{m}{2}\Big{)}^{2}-\sqrt{b}/4\Big{|}>\kappa_{\alpha}\Big{\\}}.$
(10)

Lemma A.7 in the Supplementary Material shows that this test achieves the
public coin lower bound when $mb\gtrsim d$ and $m\geq M_{\alpha}$.

###  4.3 Private coin, high total communication budget: constructing
$T_{\text{III}}$

Finally, we consider the case of not having access to a public coin, but
having a relatively large communication budget ($b^{2}m\gtrsim d^{2}$). Note
that we can assume without loss of generality that $m\geq
M_{\alpha}{d^{2}}/{b^{2}}$ for a constant $M_{\alpha}>0$, as otherwise the
optimal rate is $\sqrt{md}/n$, obtained by the $1$-bit private coin test
described by (8) (see Section 4.1). This case is the most involved one and we
construct a test consisting two sub-tests optimal in different sub-regimes.

The most obvious approach in this case is to divide the communication budget
of each machine over the $d$ coordinates as uniformly as possible. That is to
say, to partition the coordinates $\\{1,\ldots,d\\}$ into approximately $d/b$
sets of size $b$ (we assume without loss of generality that $b\leq d$, as we
can always throw away excess budget and $b=d$ bits suffices for achieving the
minimax rate). The machines are then equally divided over each of these
partitions and communicate the coefficients corresponding to their partition.
More formally, such a strategy entails taking sets
${\mathcal{I}}_{i}\subset\\{1,\dots,m\\}$ such that
$|{\mathcal{I}}_{i}|=\lfloor\frac{mb}{d}\rfloor$ and each
$j\in\\{1,\dots,m\\}$ is in ${\mathcal{I}}_{i}$ for $b$ different indexes
$i\in\\{1,\dots,d\\}$. For $i=1,\dots,d$ and $j\in{\mathcal{I}}_{i}$, generate
the transcripts according to

$Y^{j}_{i}|X_{i}^{j}=\text{1}\\{X_{i}^{j}>0\\}.$ (11)

Centrally, a natural test based on these transcripts is

$T_{\text{III}}^{1}:=\text{1}\Big{\\{}\Big{|}\frac{1}{{|{\mathcal{I}}_{1}|}\sqrt{d}}\underset{i=1}{\overset{d}{\sum}}\Big{(}\underset{j\in{\mathcal{I}}_{i}}{\overset{}{\sum}}(Y_{i}^{j}-1/2)\Big{)}^{2}-\sqrt{d}/4\Big{|}>\kappa_{\alpha}\Big{\\}}.$
(12)

It turns out that such a test does not cover all regimes where
$m\gtrsim{d^{2}}/{b^{2}}$, because, there is a certain amount of information
loss due to the nonlinearity of the quantization step (11), i.e. the test
induces soft thresholding for the signal components which is sub-optimal for
(relatively) large signal components. For the exact statement on the testing
error of this test, see Lemma A.9 below.

For detecting signals including large coordinates we propose an adaptation of
test $T_{\text{III}}^{1}$. We start by assuming that $b\geq 2\log(d+1)$
otherwise we do not construct the test. Then for $i=1,...,d$ and $j=1,...,m$,
let us generate

$B^{j}_{li}\stackrel{{\scriptstyle
iid}}{{\sim}}\text{Ber}\Big{(}F_{\chi^{2}_{1}}\Big{(}\big{(}\sqrt{n/m}X_{i}^{j}\big{)}^{2}\Big{)}\Big{)},\qquad
l\in\\{1,\dots,C_{b,d}=\lfloor 2^{b}/(d+1)\rfloor\\}.$

Note that $C_{b,d}\geq 1$ by assumption. Then machine $j$ communicate the
transcripts

$N^{j}=\sum_{l=1}^{C_{b,d}}\underset{i=1}{\overset{d}{\sum}}B^{j}_{li}\in\\{0,1,\dots,C_{b,d}d\\},$
(13)

which can be done using $\log_{2}(C_{b,d}d+1)\leq b$ bits in total. Based on
these transcripts, we compute the test

$T_{\text{III}}^{2}=\text{1}\left\\{\bigg{|}\frac{1}{dmC_{b,d}}\left(\underset{j=1}{\overset{m}{\sum}}(N^{j}-Ld/2)\right)^{2}-\frac{1}{4}\bigg{|}\geq\kappa_{\alpha}\right\\}$

centrally. The testing risk bound for the above test is given in Lemma A.10
below.

Finally, we construct our test by combining the above ones. We construct both
partial tests $T_{\text{III}}^{1}$ and $T_{\text{III}}^{2}$ if $b\geq
2\log(d+1)$ by transmitting $b^{\prime}=\lfloor b/2\rfloor$ bits per machine
for each, otherwise we just construct $T_{\text{III}}^{1}$. Then we merge them
by taking

$T_{\text{III}}=T_{\text{III}}^{1}\vee T_{\text{III}}^{2}\text{1}_{\\{b\geq
2\log(d+1)\\}},$ (14)

where the indicator should be understood to rule out cases in which the
transcripts for $T_{\text{III}}^{2}$ cannot necessarily be communicated. This
case, as shown below, is covered by the first test $T_{\text{III}}^{1}$. Lemma
A.8 in the Supplementary Material shows that $T_{\text{III}}$ has sufficiently
small testing risk in all cases where $m\geq M_{\alpha}d^{2}/b^{2}$.

##  5 A sketch of proof for the testing lower bound (Theorem 3.1)

In this section, we provide a sketch of proof of Theorem 3.1, of which the
full details are given in Section 9. The proof starts out the same way for
both the private and public coin cases, but bifurcates later on. We consider
for the time being a generic collection of $b$-bit distributed testing
protocols ${\mathcal{T}}(b)$.

As a first step, we introduce a prior distribution $\pi$ on ${\mathbb{R}}^{d}$
and lower bound the testing risk by a type of Bayes risk and the mass of $\pi$
that resides outside of the alternative hypothesis $H_{\rho}$, akin to e.g.
[24]. Recall that ${\mathbb{P}}_{f}$ denotes the joint distribution of $Y$,
$U$ and $X$ where $X^{j}$ follows (1) and
$Y\sim{\mathbb{E}}_{f}^{X,U}K(\cdot|X,U)=:{\mathbb{P}}_{f,K}^{Y}={\mathbb{P}}_{f}^{Y}$.
For $\pi$ a given a distribution on ${\mathbb{R}}^{d}$, define the mixture
distribution ${\mathbb{P}}_{\pi}^{X}=P_{\pi}$ on ${\mathbb{R}}^{md}$ by
$P_{\pi}(A)=\int P_{f}(A)d\pi(f)$, where we recall the notational convention
$\mathbb{P}_{f}^{X}=P_{f}$ from Section 2.

Through the Markov chain relation $f\to X\to Y$ this defines a distribution
${\mathbb{P}}^{Y}_{\pi}={\mathbb{P}}^{Y}_{\pi,K}$ on ${\mathcal{Y}}$ and let
us denote by ${\mathbb{E}}^{Y}_{\pi}$ the corresponding expectation. Lemma A.1
in the Supplementary Material lower bounds the infimum testing risk
$\inf_{T\in{\mathcal{T}}}\mathcal{R}(H_{\rho},T)$ using a version of Le Cam’s
lemma adapted to the distributed setting. The lemma yields that, for any
distribution on $U$,

$\underset{T\in{\mathcal{T}}}{\inf}\Big{(}{\mathbb{E}}_{0}^{Y}T(Y)+\underset{f\in
H_{\rho}}{\sup}\,{\mathbb{E}}_{f}^{Y}(1-T(Y))\Big{)}\geq\underset{K}{\inf}\,\underset{\pi}{\sup}\Big{(}1-\|{\mathbb{P}}_{0,K}^{Y}-{\mathbb{P}}_{\pi,K}^{Y}\|_{TV}-\pi(H_{\rho}^{c})\Big{)},$

where the infimum on the rhs is over all kernels on ${\mathcal{Y}}$.

Using that the measure $d{\mathbb{P}}_{f}^{Y}$ disintegrates as
$d{\mathbb{P}}_{f}^{Y|U=u}d{\mathbb{P}}^{U}_{f}(u)$, and the fact that $U$ is
independent of the prior $\pi$, we find by Jensen’s inequality that

$\|{\mathbb{P}}_{0,K}^{Y}-{\mathbb{P}}_{\pi,K}^{Y}\|_{TV}\leq\int\|{\mathbb{P}}_{0,K}^{Y|U=u}-{\mathbb{P}}_{\pi,K}^{Y|U=u}\|_{TV}d{\mathbb{P}}^{U}(u).$

By Pinsker’s second inequality and the fact that $\log(x)\leq x-1$, we obtain
that

$\underset{T\in{\mathcal{T}}(b)}{\inf}{\mathcal{R}}(H_{\rho},T)\geq
1-\sup_{K}\inf_{\pi}\Big{(}\int\sqrt{2D_{\chi^{2}}({\mathbb{P}}^{Y|U=u}_{0,K};{\mathbb{P}}^{Y|U=u}_{\pi,K})}d{\mathbb{P}}^{U}(u)+\pi(H_{\rho}^{c})\Big{)},$
(15)

where

$D_{\chi^{2}}({\mathbb{P}}^{Y|U=u}_{0,K};{\mathbb{P}}^{Y|U=u}_{\pi,K})={\mathbb{E}}_{0,K}^{Y|U=u}\left(\frac{{\mathbb{P}}_{\pi,K}^{Y|U=u}}{{\mathbb{P}}_{0,K}^{Y|U=u}}(Y)\right)^{2}-1.$
(16)

From hereon, the proof can be broken down into two steps. We provide the
skeleton of the proof here and defer the full details to Section 9.

  1. 1.

The first term on the rhs of (16) can be expressed in terms of a conditional
expectation of the likelihood of $X$:

${\mathbb{E}}_{0}^{Y|U=u}\left({\mathbb{E}}_{0}\left[\int\underset{j=1}{\overset{m}{\Pi}}\frac{d{\mathbb{P}}^{X^{j}}_{f}}{d{\mathbb{P}}^{X^{j}}_{0}}(X^{j})d\pi(f)\bigg{|}Y,U=u\right]^{2}\right),$
(17)

which we compare to the quantity

$\underset{j=1}{\overset{m}{\Pi}}{\mathbb{E}}_{0}^{Y^{j}|U=u}\left({\mathbb{E}}_{0}\left[\int\frac{d{\mathbb{P}}^{X^{j}}_{f}}{d{\mathbb{P}}^{X^{j}}_{0}}(X^{j})d\pi(f)\bigg{|}Y^{j},U=u\right]^{2}\right),$
(18)

which corresponds to the product of the first terms of the local chi-square
divergences. In particular, we compare the ratio of the expressions in the
above two displays and show that when $\pi$ is taken to be centered Gaussian,
this ratio is maximized when the protocol’s kernel $K:L_{2}({\mathcal{Y}})\to
L_{2}({\mathcal{X}})$ with Hilbert space adjoint $K^{*}$ satisfies that
$K^{*}K:L_{2}({\mathcal{X}})\to L_{2}({\mathcal{X}})$ is Gaussian in an
appropriate sense. This is the content of Lemma 10.1, which forms the crux of
our proof. This lemma, on which we expound in Section 10, exploits the
conjugacy between the prior and the model which enables the use of techniques
applied in [26]. Consequently, we obtain that the first term on the rhs of
(16) is bounded from above by a multiple of

$\underset{j=1}{\overset{m}{\Pi}}{\mathbb{E}}_{0}\left[\mathscr{L}_{\pi}\left({X}^{j}\right)^{2}\right]\int\exp\left(f^{\top}\Xi_{u}g\right)d(\pi\times\pi)(f,g)d{\mathbb{P}}^{U}(u),$
(19)

where

$\Xi_{u}:=\underset{j=1}{\overset{m}{\sum}}{\mathbb{E}}_{0}^{Y^{j}|U=u}{\mathbb{E}}_{0}\left[{X}^{j}\bigg{|}Y^{j},U=u\right]{\mathbb{E}}_{0}\left[{X}^{j}\bigg{|}Y^{j},U=u\right]^{\top}.$
(20)

  2. 2.

The final step combines data processing techniques with what is essentially a
geometric argument. The first term in (19) is handled using classical, non-
distributed techniques, i.e. decoupling argument of the measure and the moment
generating function of the Gaussian chaos, see e.g. [40]. In the second term
in (19) the $d\times d$ matrix $\Xi_{u}$ geometrically captures how well $Y$
allows to “reconstruct” the compressed sample $X$. The information lost by
compressing a $d$ dimensional observation $X^{j}$ into a $b$-bit transcript
$Y^{j}$ is captured in a data processing inequality for the matrix $\Xi_{u}$
and its trace, which comes in the form of Lemma A.2 and Lemma A.3. From hereon
out, the proof of the private and the public coin cases separate. Recalling
the order of the supremum, infimum and expectation with respect to the public
coin in (15), we see that in the private coin case, $\pi$ can be chosen with
knowledge of $\Xi_{u}$, as $U$ is degenerate in this case. To obtain the
stricter lower bound in the private coin case, we choose $\pi$’s covariance in
order to exploit the “weakest directions” of the protocol $Y$ and the proof is
finished by matrix algebra arguments.

##  6 Nonparametric testing with known regularity

A natural extension of the above finite dimensional signal in Gaussian noise
setting is the infinite dimensional signal in white noise model. Here, the
$j=1,\dots,m$ machines observe iid $X^{j}$ taking values in
${\mathcal{X}}\subset L_{2}[0,1]$ and subject to the stochastic differential
equation

$dX^{j}_{t}=f(t)dt+\sqrt{\frac{m}{n}}dW_{t}^{j}$ (21)

under $P_{f}$, with $W^{1},\dots,W^{m}$ iid Brownian motions and $f\in
L_{2}[0,1]$. Besides the difference in the local observations, the distributed
setup considered for this model remains exactly the same. The results derived
for the alternatives $H_{\rho}$ in the finite dimensional model translate to
testing in the infinite dimensional model against the alternative hypotheses

$f\in
H_{\rho}^{s,R}:=\\{f\in{\mathcal{H}}^{s,R}[0,1]:\|f\|_{L_{2}}\geq\rho\text{
and }\|f\|_{{\mathcal{H}}^{s}}\leq R\\}.$

Here, ${\mathcal{H}}^{s,R}={\mathcal{H}}^{s,R}([0,1])$ denotes the Sobolev
ball of radius $R$ in the space of $s$-smooth Sobolev functions and
$\|\cdot\|_{{\mathcal{H}}^{s}}$ the Sobolev norm, see Section G for recalling
the definitions. The smoothness parameter $s>0$ determines the difficulty of
the classical (non-distributed, $m=1$) nonparametric testing problem as
considered in e.g. [24]. The asymptotic minimax rate for the non-distributed
case is $\rho^{2}\asymp n^{-\frac{2s}{2s+1/2}}$ for the $s$-smooth Sobolev
alternative class.

We allow for asymptotics in $b$ and $m$ in the sense that they can depend on
$n$. Consequently, we consider the separation rate $\rho$ in the nonparametric
problem to be a sequence of positive numbers in both $n$, $m$ and the budget
$b$. A distributed test $T$ in the nonparametric setting is called
$\alpha$-consistent for $\alpha\in(0,1)$ if
${\mathcal{R}}(H_{\rho}^{s,R},T)\leq\alpha$ for all $n$ large enough.

The distributed setting for the nonparametric model remains unchanged in
comparison with the finite dimensional model introduced in Section 2, except
of course for the sample space in which the observations $X^{j}$ take values.
This becomes $L_{2}[0,1]$ instead of ${\mathbb{R}}^{d}$. The following theorem
describes the minimax rate for the nonparametric distributed problem.

######  Theorem 6.1 (Nonparametric signal in white noise minimax rate).

Take $f\in H^{s,R}$ for some $s,R>0$ and let $b\equiv b_{n}$ and $m\equiv
m_{n}$ be sequences of natural numbers and take $\rho\equiv\rho_{n,b,m,s}$ be
a sequence of positive numbers satisfying

$\rho^{2}\asymp\begin{cases}n^{-\frac{2s}{2s+1/2}},&\text{ if }b\geq
n^{\frac{1}{2s+1/2}},\\\ \left({\sqrt{b}n}\right)^{-\frac{2s}{2s+1}},&\text{
if }n^{\frac{1}{2s+1/2}}/m^{\frac{2s+1}{2s+1/2}}\leq
b<n^{\frac{1}{2s+1/2}},\\\ (n/\sqrt{m})^{-\frac{2s}{2s+1/2}},&\text{ if
}b<n^{\frac{1}{2s+1/2}}/m^{\frac{2s+1}{2s+1/2}}.\end{cases}$ (22)

In the public coin protocol case the minimax testing rate is $\rho^{2}$ given
in (22), i.e. for all $\alpha\in(0,1)$ there exist constants
$C_{\alpha},c_{\alpha}>0$ depending only on $\alpha$, $s$ and $R$ such that
for all $n$ large enough,

$\underset{T\in{\mathcal{T}}_{pub}(b)}{\inf}\;\;{\mathcal{R}}(H_{c_{\alpha}\rho}^{s,R},T)>1-\alpha\;\;\text{
and
}\;\;\underset{T\in{\mathcal{T}}_{pub}(b)}{\inf}\;\;{\mathcal{R}}(H_{C_{\alpha}\rho}^{s,R},T)\leq\alpha.$

Similarly, in the private coin protocol case $\rho\equiv\rho_{n,b,m}$ given
below

$\rho^{2}\asymp\begin{cases}n^{-\frac{2s}{2s+1/2}}&\text{ if }b\geq
n^{\frac{1}{2s+1/2}},\\\ \left({bn}\right)^{-\frac{2s}{2s+3/2}}&\text{ if
}n^{\frac{1}{2s+1/2}}/m^{\frac{s+3/4}{2s+1/2}}\leq b<n^{\frac{1}{2s+1/2}},\\\
(n/\sqrt{m})^{-\frac{2s}{2s+1/2}}&\text{ if
}b<n^{\frac{1}{2s+1/2}}/m^{\frac{s+3/4}{2s+1/2}},\end{cases}$ (23)

provides the minimal testing rate, i.e. for all $\alpha\in(0,1)$ there exist
constants $C_{\alpha},c_{\alpha}>0$ depending only on $\alpha$ and $R$ such
that for all $n$ large enough,

$\underset{T\in{\mathcal{T}}_{priv}(b)}{\inf}\;\;{\mathcal{R}}(H_{c_{\alpha}\rho}^{s,R},T)>1-\alpha\;\;\text{
and
}\;\;\underset{T\in{\mathcal{T}}_{priv}(b)}{\inf}\;\;{\mathcal{R}}(H_{C_{\alpha}\rho}^{s,R},T)\leq\alpha.$

The proof of the theorem is given in Section B. The theorem reveals the
relationship between the signal-to-noise-ratio $n$, communication budget per
machine $b$, the number of machines $m$ and the smoothness of the signal $s$.
Before providing the proof we briefly discuss the connection with distributed
minimax estimation rates.

The distributed minimax estimation rates under private coin protocol were
established in Corollary 2.2 of [32] or Theorem 3.1 in [44]. A slight
reformulation of the latter yields that

$\underset{(\hat{f},{\mathcal{L}}(Y))\in{\mathcal{E}}_{priv}(b)}{\inf}\;\underset{f\in{\mathcal{H}}^{s,R}}{\sup}{\mathbb{E}}_{f}^{Y}\|\hat{f}(Y)-f\|^{2}_{L_{2}}\asymp\begin{cases}n^{-\frac{2s}{2s+1}},&\text{
if }b\geq n^{\frac{1}{2s+1}},\\\ {(bn)}^{-\frac{2s}{2s+2}},&\text{ if
}(n/m^{2+2s})^{\frac{1}{2s+1}}\leq b\leq n^{\frac{1}{2s+1}},\\\
\left(bm\right)^{-2s},&\text{ if
}b\leq(n/m^{2+2s})^{\frac{1}{2s+1}},\end{cases}$ (24)

where ${\mathcal{E}}_{priv}(b)$ is the class of all distributed estimators
based on $b$-bit transcripts $Y=\left(Y^{1},\dots,Y^{m}\right)$.

A first observation is that consistent testing is possible in any regime of
$b\geq 1$ and $m$, whereas this is not the case in estimation. Consider for
instance the regime where $m$ and $b$ are fixed. In nonparametric distributed
estimation, the $L_{2}$-risk does not improve once the sample size is large
enough. In fact, even when allowing for asymptotics in $b$ and $m$ (but
assuming that $(n/m^{2+2s})^{\frac{1}{2s+1}}{\geq b}$) one is better off
performing the estimation locally using just one of the machines with local
signal-to-noise-ratio $n/m$, attaining the locally optimal rate
$(n/m)^{-\frac{2s}{2s+1}}$.

In the case of nonparametric testing, not only can we consistently test for
any fixed $m$ and $b$, the distributed testing rate is bounded from above by
$(n/\sqrt{m})^{-2s/(2s+1/2)}$ (regardless of the communication budget $b$),
which is significantly smaller (for large $m$) than the minimax testing rate
based on the local signal-to-noise-ratio $(n/m)^{-2s/(2s+1/2)}$, which can be
achieved by using only a single local machine. One possible explanation for
this discrepancy is that in nonparametric estimation, the output of the
inference is a high-dimensional object, which requires a large total
communication budget to be reconstructed with sufficient granularity. In
testing, the output of our inference is binary.

A perhaps less surprising difference is that a larger budget is needed for
testing at the non-distributed minimax testing rate compared to estimation.
That is, in order to obtain the non-distributed minimax rate of
$\rho^{2}\asymp n^{-\frac{2s}{2s+1/2}}$, the communication budget needs to
satisfy $b\gtrsim n^{\frac{1}{2s+1/2}}$. On the other hand, the non-
distributed minimax estimation rate $n^{-\frac{2s}{2s+1}}$ requires only
$b\gtrsim n^{\frac{1}{2s+1}}$. This follows from the fact that the $L_{2}$
testing rate is faster than the estimation rate and hence to achieve this
faster rate one has to collect information about the signal at higher
frequency level as well (up to the $O(n^{\frac{1}{2s+1/2}})$ coefficients in
the spectral decomposition).

Increasing $m$ decreases the local signal-to-noise-ratio. When the total
budget $bm$ grows at a similar or faster rate than the “effective dimension”
of the model, the rate that can be achieved no longer depends on $m$ in both
estimation and testing settings. In this regime, this effect is offset by the
total number of bits being received by the central machine. What is different
in testing problem, however, is that having access to shared randomness
strictly improves the performance (until the local communication budget $b$
reaches the effective dimension $n^{\frac{1}{2s+1/2}}$ as after that both
method reaches the minimax non-distributed testing rate
$n^{-\frac{2s}{2s+1/2}}$). One might wonder whether having access to a public
coin improves the rate in the estimation setting also. It turns out that this
is not the case. We show in Theorem C.1 in the Supplementary Material that
under the public coin protocol the distributed minimax estimation rate does
not improve compared to the private coin protocol.

##  7 Adaptation in nonparametrics

In the previous section we have derived minimax lower and matching upper
bounds for the nonparametric distributed testing problem in context of the
Gaussian white noise model. The proposed tests, however, depend on the
regularity hyper-parameter $s$ of the functional parameter of interest $f$.
Typically, the regularity of the function is not known in practice and one has
to use data driven methods to find the best testing strategies. In this
section we derive distributed tests adapting to this unknown regularity. We
derive both lower and upper bounds and observe surprising, additional phase
transition in the small budget regime which was not present in the non-
adaptive setting.

First, we note that even in the non-distributed setting, we have to pay an
additional $\log\log n$ factor as a price for adaptation (see e.g. Theorem 2.3
in [31] or Section 7 in [24]). More concretely, if $\rho_{s}\asymp
n^{-s/(2s+1/2)}$, it holds that for any $s_{\min}<s_{\max}$,

$\underset{s\in[s_{min},s_{max}]}{\sup}{\mathcal{R}}(H^{s,R}_{c_{n}M_{n,s}\rho_{s}},T)\to
1,$

for all tests $T$, ${M_{n,s}}=(\log\log n)^{\frac{s/4}{2s+1/2}}$ and any
$c_{n}=o(1)$ whilst there exists a test $T$ satisfying

$\underset{s\in[s_{min},s_{max}]}{\sup}{\mathcal{R}}(H^{s,R}_{CM_{n,s}\rho_{s}},T)\to
0.$

for large enough constant $C>0$.

The distributed testing problem is more complicated as we have to consider
different regimes based on the number of transmitted bits, see Theorem 6.1.
These regimes, however, depend on the unknown regularity hyper-parameter and
require different testing procedures to achieve consistent testing. The
transcripts transmitted require a larger communication budget to attain the
same performance as in Theorem 6.1. Theorem 7.1 and 7.2 below capture this
increased difficulty in terms of lower- and upper bounds on the detection rate
(tight up to a log-log factor). In the proof of the theorem, we derive such an
adaptive distributed testing method which adapts to the smoothness. These
methods are in principle based on taking a $1/\log n$ grid of the regularity
interval $[s_{\min},s_{\max}]$, constructing optimal tests for each of the
grid points and combining them using Bonferroni’s correction. This results in
loosing a logarithmic factor in the intermediate case as the budget has to be
divided over $O(\log n)$ tests, each capturing a different possible level of
smoothness.

This additional incurred cost in the distributed setting due to additional
communication budget required is fundamental, as our accompanying lower bound
shows. This additional difficulty translates to a $\sqrt{\log(n)}$ and
$\log(n)$ factor more observations required in the intermediate budget regimes
for the public and private coin settings, respectively. In the small budget
regime, such a loss is incurred when the local communication budget $b$ is of
smaller order than $\log(n)$. When $b\gtrsim\log(n)$ in the small budget
regime, the same rate as in Theorem 6.1 can be obtained, up to the
$\log\log(n)$ factor incurred by the Bonferroni correction.

The above described results are split over two theorems. The first, Theorem
7.1, concerns the case where $b\gtrsim\log(n)$. In the second, Theorem 7.2,
the case where $b\lesssim\log(n)$ (both theorems coincide when
$b\asymp\log(n)$). The case where $b=O(1)$ is of special interest, as $b=1$
means each machine’s local transcript forms a test itself and the global test
can be seen as a “meta-analysis” on the basis of these $m$ tests. The proofs
of the upper bounds in both theorems are given in Section 8, while the proofs
of the lower bound are deferred to Section D in the supplement.

######  Theorem 7.1.

Let us consider some $0<s_{\min}<s_{\max}<\infty$, $R>0$, let $b\equiv b_{n}$
such that $b\gg\log n$ and $m\equiv m_{n}$ be sequences of natural numbers and
take a sequence of positive numbers $\rho_{s}\equiv\rho_{n,b,m,s}$ satisfying

$\rho^{2}_{s}\asymp\begin{cases}n^{-\frac{2s}{2s+1/2}},&\text{ if
}\;b\geq{{\log(n)}n^{\frac{1}{2s+1/2}}},\\\
\left(\frac{\sqrt{b}n}{\sqrt{\log(n)}}\right)^{-\frac{2s}{2s+1}},&\text{ if
}\;{\log(n)}\left(\frac{n^{\frac{1}{2s+1/2}}}{m^{\frac{2s+1}{2s+1/2}}}\bigvee
1\right)\leq b<{{\log(n)}n^{\frac{1}{2s+1/2}}},\\\
\left(\frac{n}{\sqrt{m}}\right)^{-\frac{2s}{2s+1/2}},&\text{ if }\;\log(n)\leq
b<{\log(n)}\left(\frac{n^{\frac{1}{2s+1/2}}}{m^{\frac{2s+1}{2s+1/2}}}\bigvee
1\right).\end{cases}$ (25)

in the public coin case, and

$\rho^{2}_{s}\asymp\begin{cases}n^{-\frac{2s}{2s+1/2}}&\text{ if
}\;b\geq{{\log(n)}n^{\frac{1}{2s+1/2}}},\\\
\left(\frac{bn}{\log(n)}\right)^{-\frac{2s}{2s+3/2}}&\text{ if
}\;\log(n)\left(\frac{n^{\frac{1}{2s+1/2}}}{m^{\frac{s+3/4}{2s+1/2}}}\bigvee
1\right)\leq b<{{\log(n)}n^{\frac{1}{2s+1/2}}},\\\
\left(\frac{n}{\sqrt{m}}\right)^{-\frac{2s}{2s+1/2}}&\text{ if }\;\log(n)\leq
b<\log(n)\left(\frac{n^{\frac{1}{2s+1/2}}}{m^{\frac{s+3/4}{2s+1/2}}}\bigvee
1\right).\end{cases}$ (26)

in the case of a private coin. Then, there exits a sequence of distributed
testing procedures in the respective setups such that

$\underset{s\in[s_{\min},s_{\max}]}{\sup}{\mathcal{R}}(H_{M_{n}\rho_{s}}^{s,R},T)\to
0,$

for arbitrary $M_{n}\gg\big{(}\log\log(n)\big{)}^{1/4}$. Similarly, for all
distributed testing procedures in the respective setups, we have that for all
$\alpha\in(0,1)$ there exists $c_{\alpha}>0$ such that

$\underset{s\in[s_{\min},s_{\max}]}{\sup}{\mathcal{R}}(H_{c_{\alpha}\rho_{s}}^{s,R},T)>\alpha.$

The above theorem recovers (up to log-factors) the three rates corresponding
to the three regimes also found in Theorem 6.1, the different regimes
corresponding to different testing strategies. Since the true smoothness is
unknown, these different distributed testing strategies are to be conducted
simultaneously.

We note that for $m\geq n^{\frac{1}{2s_{\min}+1}}$ or $m\geq
n^{\frac{1}{s_{\min}+3/4}}$ in the public and private coin cases,
respectively, the small budget regime no longer occurs. The reason for this is
that, even though $b$ could be relatively small, the total communication
budget $bm$ is large enough to warrant the strategy for the intermediate and
high budget regimes. Furthermore, whenever
$b>{{\log(n)}n^{\frac{1}{2s+1/2}}}$, the budget is large enough to recover the
non-distributed regime rate.

For $b\lesssim\log(n)$ the separation rate is different from the non-adaptive
low budget regime. Depending on the interplay between $n$ and $m$ either the
minimax rate corresponding to the intermediate case applies or an additional
$(\log(n)/b)^{\delta}$ factor is present compared to the non-adaptive low
budget regime, both in the private and public coin settings. This results in
an additional phase transition at $b=\log n$. The reason for this, is that in
order to cover approximately $\log(n)$ different levels of smoothness using
less than $\log(n)$ bits, each of the machines can no longer send an adequate
amount of information on all of the relevant smoothness levels. Instead, an
optimal strategy is to divide the different machines over each of the
smoothness levels, where each machines foregoes sending information regarding
certain smoothness levels all together.

######  Theorem 7.2.

Assume the conditions of Theorem 7.1 with $b\lesssim\log(n)$ and assume
$bm\gg\log(n)$. Let us consider

$\rho^{2}_{s}\asymp\begin{cases}\left(\frac{\sqrt{b}n}{\sqrt{\log(n)}}\right)^{-\frac{2s}{2s+1}},&\text{
if }\;m\geq n^{\frac{1}{2s+1}},\\\
\left(\frac{\sqrt{b}n}{\sqrt{m\log(n)}}\right)^{-\frac{2s}{2s+1/2}},&\text{ if
}\;m<n^{\frac{1}{2s+1}},\end{cases}$ (27)

in the public coin case and

$\rho^{2}_{s}\asymp\begin{cases}\left(\frac{bn}{\log(n)}\right)^{-\frac{2s}{2s+3/2}}&{if}\;m\geq
n^{\frac{2}{2s+3/2}}\left(\frac{b}{\log(n)}\right)^{\frac{s-1/4}{2s+3/2}},\\\
\left(\frac{n\sqrt{b}}{\sqrt{m\log(n)}}\right)^{-\frac{2s}{2s+1/2}}&\text{ if
}\;\;m<n^{\frac{2}{2s+3/2}}\left(\frac{b}{\log(n)}\right)^{\frac{s-1/4}{2s+3/2}}.\end{cases}$
(28)

in the private coin case. Then, there exits a sequence of distributed testing
procedures in the respective setups such that

$\underset{s\in[s_{\min},s_{\max}]}{\sup}{\mathcal{R}}(H_{M_{n}\rho_{s}}^{s,R},T)\to
0,$

for arbitrary $M_{n}\gg\big{(}\log\log(n)\big{)}^{1/4}$. Similarly, for all
distributed testing procedures in the respective setups, we have that for all
$\alpha\in(0,1)$ there exists $c_{\alpha}>0$ such that

$\underset{s\in[s_{\min},s_{\max}]}{\sup}{\mathcal{R}}(H_{c_{\alpha}\rho_{s}}^{s,R},T)>\alpha.$

######  Remark 7.3.

Both theorems together cover all cases where $mb\gg\log(n)$. The cases where
$mb\lesssim\log(n)$ are excluded for technical reasons, as well as the fact
that when $mb\lesssim\log(n)$, the optimal rate in (27)-(28) (up to at most a
$\sqrt{\log\log(n)}$ factor) is attained by using a standard non-distributed
method using just the data of one machine (see e.g. [31]). Similarly, in order
to contain the level of technicality, we have foregone the
$(\log\log(n))^{1/4}$ additional factor in the lower bound which we esteem
also to be present in the distributed setting. We refer the reader to the
argument of Theorem 2.3 in [31] for how to obtain the $(\log\log(n))^{1/4}$
factor in the lower bound in addition to the $\sqrt{\log(n)}$ and ${\log(n)}$
factors in the public and private coin cases respectively.

##  8 Adaptive tests attaining the adaptation bounds in Theorem 7.1 and 7.2

Let us consider the smooth orthonormal wavelet basis
$\\{\psi_{li}\,:l\in{\mathbb{N}}_{0},\,i=0,1,\dots,2^{l}-1\\}$. See Section G
for a brief introduction of wavelets and collection of properties used in this
proof. For $L=L\in{\mathbb{N}}$, let $V_{L}=\\{\psi_{li}:l\leq
L,\;i=0,1,\dots,2^{l}-1\\}$. For $f\in L_{2}[0,1]$, let $f^{L}$ denote the
projection of $f$ onto $V_{L}$, i.e.

$f^{L}=\underset{l=0}{\overset{L}{\sum}}\underset{i=0}{\overset{2^{l}-1}{\sum}}\tilde{f}_{li}\psi_{li}$
(29)

with $\tilde{f}_{li}:=\int f\psi_{li}$. We denote the wavelet coefficients of
$X^{j}$ by $\tilde{X}_{li}^{j}:=\int_{0}^{1}\psi_{li}dX_{t}^{j}$. For the
coefficients at resolution level $L$, write
$\tilde{X}_{L}^{j}=(\tilde{X}_{L0}^{j},\dots,\tilde{X}_{L(2^{L}-1)}^{j})\in{\mathbb{R}}^{2^{L}}$
and let $\tilde{X}_{L^{\prime}:L}^{j}$ denote the concatenated coefficients
from resolution level $L^{\prime}<L$ up to resolution level $L$, i.e.
$\tilde{X}_{L^{\prime}:L}^{j}=(\tilde{X}_{L^{\prime}}^{j},\dots,\tilde{X}_{L}^{j})\in{\mathbb{R}}^{2^{L+1}-2^{L^{\prime}+1}}$.
The vector
$\tilde{X}^{j}_{0:L}:=(\tilde{X}_{0}^{j},\tilde{X}_{1}^{j},\dots,\tilde{X}_{L}^{j})$
follows the dynamics

$\tilde{X}^{j}_{0:L}=\tilde{f}^{L}+\sqrt{\frac{m}{n}}Z^{j},$ (30)

where $Z^{j}\sim^{iid}N(0,I_{2^{L+1}-1})$, $j=1,\dots,m$, and
$\tilde{f^{L}}:=(\tilde{f}_{li})_{l=0,...,L;\,i=0,...,2^{l}-1}$.

Let $\nu_{L}=2^{L+1}-1$ and let us introduce the notations ${L_{s}}=\lfloor
s^{-1}\log(1/\rho_{s})\rfloor\vee 1$, and for shorthand write
$L_{\min}=L_{s_{\max}}$ and $L_{\max}=L_{s_{\min}}$ and note that
$L_{s}\in\mathcal{C}:=\\{L_{\min},...,L_{\max}\\}$ for all
$s\in[s_{\min},s_{\max}]$. Note that $|\mathcal{C}|\leq\log n$.

For each regularity hyper-parameter $s$, we distinguish low-budget
($2^{L_{s}}\gtrsim mb$ in the public coin, and $2^{\frac{3}{2}L_{s}}\gtrsim
mb$ in the private coin setting) and high-budget (corresponding to
$2^{L_{s}}\lesssim mb$ in the public coin and $2^{\frac{3}{2}L_{s}}\lesssim
mb$ in the private coin setting) cases. Since $m$ and $b$ are known for any
given regularity $s$ we know which regime it falls and is sufficient to
construct that test. For notational convenience, without loss of generality,
for each $s$ we construct both the high-budget and the low-budget optimal
tests using all the $m$ machines (and do not split them between these two
cases).

###  8.1 Proof of the upper bound in the low-budget regime

First we deal with the low-budget case (where the total budget is small
compared to the effective dimension), which coincides in both setups. For each
$L\in\mathcal{C}$ we take a subset of machines $M_{L}\subset\\{1,...,m\\}$
such that $|M_{L}|=m^{\prime}:=\frac{m(\log(n)\wedge b)}{\log(n)}$ and each
machine appears in at most $b$ such subsets. We note that this is possible
since $m^{\prime}|\mathcal{C}|\leq mb$. Then for each $j\in M_{L}$,
$L\in\mathcal{C}$ we communicate

$Y_{I}^{j}(L)|X^{j}\sim\text{Ber}\left(\chi^{2}_{\nu_{L}}\left(\sqrt{n/m}\|\tilde{X}_{0:L}^{j}\|_{2}^{2}\right)\right)$
(31)

and at the central machine, we can compute

$S_{I}(L)=\frac{1}{\sqrt{m^{\prime}}}\underset{j\in
M_{L}}{\sum}(2Y_{I}^{j}(L)-1).$

Then we consider the following adaptive test based on Bonferroni’s correction

$T_{I}^{adapt}=\text{1}\Big{\\{}\underset{L\in\mathcal{C}}{\max}S_{I}(L)\geq
2\sqrt{\log\log n}\Big{\\}}.$

Since for $L\in\mathcal{C}$, it holds that $L\asymp\log(n)$, the above
$\sqrt{\log\log n}$ blow up suffices to guarantee that the test has
asymptotically vanishing Type I error control, i.e.
${\mathbb{E}}_{0}T_{I}^{adapt}=o(1)$ by Lemma E.1 in the Supplementary
Material (as the random variables $2Y_{I}^{j}(L)-1$ are iid Rademacher under
$\mathbb{P}_{0}$).

For the Type II error note that

${\mathbb{E}}_{f}(1-T_{I}^{adapt})\leq{\mathbb{P}}_{f}\Big{(}S_{I}(L_{s})<2\sqrt{\log\log
n}\Big{)}$

and aim to apply Lemma A.4. In view of Lemma A.6, (with $\|f\|_{2}$ replaced
by $\|\tilde{f}^{L_{s}}\|_{2}$ and $d=\nu_{L_{s}}$), noting that by triangle
inequality
$\|\tilde{f}^{L_{s}}\|_{2}^{2}\geq\|f\|_{2}^{2}/2-2^{-2L_{s}s}R^{2}$ (see also
Section B in the Supplementary Material), we get for $\|f\|_{2}^{2}\geq
C_{0}^{2}\sqrt{\log\log(n)}\rho_{s}^{2}\geq
C_{0}^{2}\sqrt{\log\log(n)}{\frac{\sqrt{2^{L_{s}}m\log(n)}}{n\sqrt{b\wedge\log(n)}}}$,
that for $m$ large enough

$\displaystyle\eta_{p,m^{\prime},1}\gtrsim(m^{\prime}-1)\Big{(}\frac{n\|\tilde{f}^{L_{s}}\|_{2}^{2}}{m2^{L_{s}/2}}\wedge\frac{1}{2}\Big{)}^{2}\gtrsim
m^{\prime}\Big{(}(\tilde{C}\frac{\log\log n}{m^{\prime}})\wedge(1/4)\Big{)},$

with $\tilde{C}=C_{0}^{2}/2-R^{2}$. By the assumption that $bm\gg\log(n)$,
$m^{\prime}$ can be taken larger than arbitrary constant $M_{0}>0$. This means
that, in view of Lemma A.4 with $c_{\alpha,n}=4\log\log n$ and large enough
constant $C_{0}$ (depending on $R$), the Type II error is bounded by $\alpha$.

###  8.2 Proof of the upper bound in the public coin, high budget regime

We use similar arguments as before, applying a Bonferroni-type of correction.
First let us consider the public coin setting and take a one-to-one mapping
$\xi_{L}$ from $\\{1,\dots,\nu_{L}\\}$ to
$\\{(l,i):l=0,\dots,L,\;i=0,1,\dots,2^{l}-1\\}$. Let us define the test

$(Y_{\text{II}}^{j}(L))_{i}|U_{L}=\text{1}\left\\{\left(\sqrt{n/m}U_{L}\tilde{X}_{\xi_{L}(i)}^{j}\right)_{i}>0\right\\},$
(32)

where the random variable $U_{L}\in{\mathbb{R}}^{\nu_{L}\times\nu_{L}}$ is
drawn from the Haar measure on the rotation group on ${\mathbb{R}}^{\nu_{L}}$.
Similarly to before for each $L$ we take a subset of machines
$M_{L}\subseteq\\{1,...,m\\}$ such that
$|M_{L}|=m^{\prime}:=\frac{m(b\wedge\log(n))}{\log(n)}$, and each machine
appears at most in $b$ such sets.

Then machine $j\in M_{L}$, $L\in\mathcal{C}$, transmits the bits
$(Y_{\text{II}}^{j}(L))_{i}$,
$i=1,...,b^{\prime}:=\frac{mb}{m^{\prime}|\mathcal{C}|}\wedge\nu_{L}$ to the
central machine, where these local test statistics are aggregated, similarly
to (10), as

$S_{\text{II}}(L)=\frac{1}{\sqrt{b^{\prime}}m^{\prime}}\underset{i=1}{\overset{b^{\prime}}{\sum}}\left[\left(\underset{j\in
M_{L}}{\sum}\left[(Y_{\text{II}}^{j}(L))_{i}-1/2\right]\right)^{2}-\frac{m^{\prime}}{4}\right].$
(33)

In view of Lemma E.1 the Type I error of the test

$T_{\text{II}}^{pub,adapt}:=\text{1}\Big{\\{}\underset{L\in\mathcal{C}}{\max}S_{\text{II}}(L)\geq
2\sqrt{\log\log n}\Big{\\}}$

is $o(1)$. For the Type II error note that

${\mathbb{E}}_{f}(1-T_{\text{II}}^{pub,adapt})\leq{\mathbb{E}}_{f}\text{1}\left\\{S_{\text{II}}(L_{s})<2\sqrt{\log\log
n}\right\\}.$

By Lemma E.2, the above display is $o(1)$ whenever $\rho^{2}\gtrsim
M_{n}{\frac{2^{L_{s}}}{n\sqrt{\frac{b}{\log(n)}\wedge 2^{L_{s}}}}}$, which,
for the choice of $L_{s}{=\lfloor s^{-1}\log(1/\rho_{s})\rfloor\vee 1}$ yields
the rates of Theorem 7.1 and 7.2.

###  8.3 Proof of the upper bound in the private coin, high-budget regime

We proceed by adapting the test $T_{\text{III}}$ provided in Section 4.3 to
the nonparametric setting with unknown regularity using again a Bonferroni
type correction to achieve adaptation. For simplicity we again apply the map
$\xi_{L}$ introduced previously to move between the single and double index
notations of the sequence model.

For all $L\in\mathcal{C}$, similarly to the previous cases we consider a
collection of machines $M_{L}$ with
$|M_{L}|=m^{\prime}=\frac{m(b\wedge\log(n))}{\log(n)}$ and similarly to
Section 4.3 let us use the notation ${\mathcal{I}}_{i}(L)\subset M_{L}$ for
the collection of machines corresponding the $i$th coordinate. We note that
without loss of generality we can assume that $m^{\prime}\geq
M_{\alpha}\sqrt{\log\log n}2^{2L_{s}}/(b^{\prime})^{2}$, for some large enough
constant $M_{\alpha}$, otherwise the test $T_{I}^{adapt}$ above covers the
corresponding range. Then we modify the test given in (12) by increasing the
threshold with the Bonferroni correction, i.e.

$\displaystyle T_{\text{III}}^{priv,adapt,1}$
$\displaystyle=\text{1}\Big{\\{}\underset{L\in\mathcal{C}}{\max}S^{\text{III},1}(L)\geq
2\sqrt{\log\log n}\Big{\\}},\quad\text{where}$ $\displaystyle
S^{\text{III},1}(L)$
$\displaystyle=\Big{|}\frac{1}{{|{\mathcal{I}}_{1}(L)|}2^{L/2}}\underset{i=1}{\overset{\nu_{L}}{\sum}}\Big{(}\underset{j\in{\mathcal{I}}_{i}(L)}{\overset{}{\sum}}(Y_{i}^{j}-1/2)\Big{)}^{2}-2^{L/2}/4\Big{|},\quad
Y_{i}^{j}|\tilde{X}_{\xi_{L}(i)}^{j}=\text{1}_{\tilde{X}_{\xi_{L}(i)}^{j}>0}.$

To deal with large signal components, similarly to (12) (with $d=\nu_{L}$ and
including the Bonferroni correction in the threshold), we propose the test,

$\displaystyle T_{\text{III}}^{priv,adapt,2}$
$\displaystyle=\text{1}\Big{\\{}\underset{L\in\mathcal{C},2\log(L)\leq
b}{\max}S^{\text{III},2}(L)\geq\kappa_{\alpha}\sqrt{\log\log
n}\Big{\\}},\quad\text{where}$ $\displaystyle S^{\text{III},2}(L)$
$\displaystyle=\bigg{|}\frac{1}{dm^{\prime}C_{b,L}}\left(\underset{j=1}{\overset{m^{\prime}}{\sum}}(N^{j}-C_{b,L}2^{L-1})\right)^{2}-\frac{1}{4}\bigg{|},$

with $C_{b,L}=2^{b-L}$ and $N^{j}$ given in (13). Finally, we aggregate these
tests by taking

$T_{\text{III}}^{priv,adapt}=T_{\text{III}}^{priv,adapt,1}\vee
T_{\text{III}}^{priv,adapt,2}.$

In view of the law of Lemma E.1 the Type I error tends to zero for both tests.
Therefore it remained to show that the Type II error is bounded by $\alpha$.
Similarly to the previous cases, note that

$E_{f}(1-T_{\text{III}}^{priv,adapt})\leq{\mathbb{E}}_{f}\Big{(}\text{1}\left\\{S^{\text{III},1}(L_{s})<2\sqrt{\log\log
n}\right\\}\wedge\text{1}\left\\{S^{\text{III},2}(L_{s})<2\sqrt{\log\log
n}\right\\}\Big{)}.$

Following the proofs of Lemmas A.8, A.9 and A.10 (with $d=\nu_{L_{s}}$, $f$
taken to be the $\nu_{L_{s}}$ dimensional vector $\tilde{f}^{L_{s}}$, $b$
replaced by $b^{\prime}$, and $M_{\alpha}$ replaced by $M_{0}\sqrt{\log\log
n}$, for some large enough $M_{0}>0$), noting that for $C_{0}^{2}>4R^{2}$

$\displaystyle\|\tilde{f}^{L_{s}}\|_{2}^{2}$
$\displaystyle\geq\|f\|_{2}^{2}/2-R^{2}2^{-2L_{s}s}\gtrsim
C_{0}\sqrt{\log\log(n)}\rho_{s}^{2}$
$\displaystyle=\frac{C_{0}2^{3L_{s}/2}\sqrt{\log\log
n}}{2n(\frac{b}{\log(n)}\wedge
2^{L_{s}})}\gtrsim\frac{C_{0}2^{L_{s}}\sqrt{\log\log
n}}{nb^{\prime}\frac{m^{\prime}}{m}},$

and applying Lemmas A.11 and A.4 with $c_{n,\alpha}=2\sqrt{\log\log n}$, we
get that the Type II error of $T_{\text{III}}^{priv,adapt}$ is bounded from
above by $\alpha/2$.

Finally, we combine the above tests by taking

$\displaystyle T^{priv,adapt}=T_{\text{III}}^{priv,adapt}\vee
T_{\text{I}}^{priv,adapt}\quad\text{and}\quad
T^{pub,adapt}=T_{\text{II}}^{pub,adapt}\vee T_{\text{I}}^{pub,adapt}.$

Note that both of the above tests still have vanishing Type I error, while the
Type II errors are bounded by the prescribed level $\alpha$ in view of taking
the union of the above optimal tests.

##  9 Proof of the testing lower bound

We provide the details for Steps 1 and 2 as outlined in Section 5. We shall
write $\mathscr{L}_{\pi}(x)=\int\mathscr{L}_{f}(x)d\pi(f)$ with
$\mathscr{L}_{f}(x):=\frac{dP_{f}}{dP_{0}}(x)$ and
$P_{f}={\mathbb{P}}_{f}^{X}$.

_Step 1._ In view of the Markov chain structure given in (2), the probability
measure $d{\mathbb{P}}_{\pi}(x,u,y)$ disintegrates as
$d{\mathbb{P}}_{K}^{Y|(X,U)=(x,u)}d{\mathbb{P}}^{X}_{f}(x)d{\mathbb{P}}^{U}(u)d\pi(f)$.
Using the Markov chain structure, the first term on the rhs of (16) can be
seen to equal

$\underset{y\in\mathcal{Y}}{\overset{}{\sum}}{\mathbb{P}}^{Y|U=u}_{0}(y)\left(\int\mathscr{L}_{\pi}(x)\frac{K(y|x,u)}{{\mathbb{P}}^{Y|U=u}_{0}(y)}dP_{0}(x)\right)^{2}={\mathbb{E}}_{0}^{Y|U=u}{\mathbb{E}}_{0}\left[\mathscr{L}_{\pi}(x)\bigg{|}Y,U=u\right]^{2}.$
(34)

Decoupling the square in $X$ and using Fubini’s theorem we can write the above
display as

$\int\mathscr{L}_{\pi}(x_{1})\mathscr{L}_{\pi}(x_{2})q_{u}(x_{1},x_{2})d(P_{0}\times
P_{0})(x_{1},x_{2}),$ (35)

where by independence between the transcripts,

$q_{u}(x_{1},x_{2}):=\underset{y\in\mathcal{Y}}{\overset{}{\sum}}\frac{K(y|x_{1},u)K(y|x_{2},u)}{{\mathbb{P}}_{0}^{Y|U=u}(y)}=\underset{j=1}{\overset{m}{\Pi}}\left(\underset{y^{j}\in\mathcal{Y}^{j}}{\overset{}{\sum}}\frac{K^{j}(y^{j}|x_{1}^{j},u)K^{j}(y^{j}|x_{2}^{j},u)}{{\mathbb{P}}_{0}^{Y^{j}|U=u}(y^{j})}\right).$

Note that in the above display, $x_{i}^{j}$ and $y^{j}$ denote the projection
of $x_{i}$ and $y$ on the coordinates indexed by $\\{(j-1)d+1,\dots,jd\\}$,
respectively. In addition, let us denote by
$\prod_{j=1}^{m}q_{u}^{j}(x_{1}^{j},x_{2}^{j})$ the rhs of the preceding
display. Since $K$ is a Markov kernel, the function $q_{u}\in
L_{2}({\mathbb{R}}^{2dm},P_{0}\times P_{0})$ is bounded and nonnegative.
Furthermore,

$\displaystyle\int
q_{u}(x_{1},x_{2})\;dP_{0}(x_{1})=\underset{y\in\mathcal{Y}}{\overset{}{\sum}}\frac{K(y|x_{2},u)}{{\mathbb{P}}_{0}^{Y|U=u}(y)}\int
K(y|x_{1},u)\;dP_{0}(x_{1})=\underset{y\in\mathcal{Y}}{\overset{}{\sum}}K(y|x_{2},u)=1,$

similarly $\int q_{u}(x_{1},x_{2})\;dP_{0}(x_{2})=1$,

$\int x_{i}q_{u}(x_{1},x_{2})d(P_{0}\times P_{0})(x_{1},x_{2})=\int
x_{i}dP_{0}(x_{i})=0\in{\mathbb{R}}^{md}$ (36)

for $i=1,2$, and

$\int\left(\begin{matrix}x_{1}\\\
x_{2}\end{matrix}\right)\left(\begin{matrix}x_{1}^{\top}&x_{2}^{\top}\end{matrix}\right)q_{u}(x_{1},x_{2})d(P_{0}\times
P_{0})(x_{1},x_{2})=:\Sigma\in{\mathbb{R}}^{2md\times 2md},$ (37)

where the former display can be seen to follow by the law of total
expectation,
$\Sigma=\text{Diag}\left(\Sigma^{1},\dots,\Sigma^{m}\right)\in{\mathbb{R}}^{2md}$
for

$\Sigma^{j}:=\left(\begin{matrix}\frac{m}{n}I_{d}&\Xi_{u}^{j}\\\
\Xi_{u}^{j}&\frac{m}{n}I_{d},\end{matrix}\right)$

with

$\Xi_{u}^{j}:={\mathbb{E}}_{0}^{Y^{j}|U=u}{\mathbb{E}}_{0}\left[{X}^{j}\bigg{|}Y,U=u\right]{\mathbb{E}}_{0}\left[{X}^{j}\bigg{|}Y^{j},U=u\right]^{\top}.$

Writing
$\mathscr{L}^{j}_{\pi}:=\int\frac{d{\mathbb{P}}^{X^{j}}_{f}}{d{\mathbb{P}}^{X^{j}}_{0}}d\pi(f)$,
(18) can be seen to equal

$\underset{j=1}{\overset{m}{\Pi}}\int\mathscr{L}^{j}_{\pi}(x_{1}^{j})\mathscr{L}^{j}_{\pi}(x_{2}^{j})q_{u}^{j}(x_{1}^{j},x_{2}^{j})d(P_{0}\times
P_{0})(x_{1}^{j},x_{2}^{j}),$ (38)

Lemma 10.1 below applies to the ratio between (35) and (38) whenever $\pi$ is
chosen to be centered Gaussian. The lemma yields that the aforementioned ratio
is maximized when $q_{u}(x_{1},x_{2})d(P_{0}\times P_{0})(x_{1},x_{2})$ is a
Gaussian distribution on ${\mathbb{R}}^{2md}$ with covariance $\Sigma$, where
the maximization is among all choices of $q_{u}$ such that $q_{u}$ is
nonnegative, bounded and satisfying (36)-(37). Deliberation and proof of the
lemma is deferred to Section 10 and the Supplementary Material to the article.
For $\pi$ a centered Gaussian distribution on ${\mathbb{R}}^{d}$, the above
lemma applies with $k=2d$, $\sigma^{2}=m/n$, we obtain that the ratio between
(35) and (38) is bounded above by

$\frac{\int\mathscr{L}_{\pi}(x_{1})\mathscr{L}_{\pi}(x_{2})dN(0,\Sigma)(x_{1},x_{2})}{\underset{j=1}{\overset{m}{\Pi}}\int\mathscr{L}^{j}_{\pi}(x_{1}^{j})\mathscr{L}^{j}_{\pi}(x_{2}^{j})dN(0,\Sigma^{j})(x_{1}^{j},x_{2}^{j})}.$
(39)

Combining the result of the lemma with the bound

$\underset{j=1}{\overset{m}{\Pi}}{\mathbb{E}}_{0}^{Y^{j}|U=u}{\mathbb{E}}_{0}\left[\mathscr{L}_{\pi}\left({X}^{j}\right)\bigg{|}Y^{j},U=u\right]^{2}\leq\underset{j=1}{\overset{m}{\Pi}}{\mathbb{E}}_{0}^{X^{j}|U=u}\left[\mathscr{L}_{\pi}\left({X}^{j}\right)^{2}\right]$
(40)

following from Jensen’s inequality, we obtain that

$\displaystyle{\mathbb{E}}_{0}^{Y|U=u}\left(\frac{{\mathbb{P}}_{\pi}^{Y|U=u}}{{\mathbb{P}}_{0}^{Y|U=u}}(Y)\right)^{2}$
$\displaystyle\leq\frac{\int\mathscr{L}_{\pi}(x_{1})\mathscr{L}_{\pi}(x_{2})dN(0,\Sigma)(x_{1},x_{2})}{\underset{j=1}{\overset{m}{\Pi}}\int\mathscr{L}^{j}_{\pi}(x_{1}^{j})\mathscr{L}^{j}_{\pi}(x_{2}^{j})dN(0,\Sigma)(x_{1},x_{2})}$
$\displaystyle\qquad\qquad\times\underset{j=1}{\overset{m}{\Pi}}{\mathbb{E}}_{0}^{X^{j}|U=u}\left[\mathscr{L}_{\pi}\left({X}^{j}\right)^{2}\right].$
(41)

By the block diagonal matrix structure of $\Sigma$, the denominator in the
first factor of the rhs of (41) satisfies

$\displaystyle\underset{j=1}{\overset{m}{\Pi}}\int\mathscr{L}^{j}_{\pi}(x_{1}^{j})\mathscr{L}^{j}_{\pi}(x_{2}^{j})dN(0,\Sigma)(x_{1},x_{2})$
$\displaystyle=\underset{j=1}{\overset{m}{\Pi}}\int
e^{\frac{n}{2m}\left(\frac{n}{m}\|\sqrt{\Sigma^{j}}\left({f},{g}\right)\|_{2}^{2}-\|\left({f},{g}\right)\|_{2}^{2}\right)}d(\pi\times\pi)\left({f},{g}\right)$
$\displaystyle=\underset{j=1}{\overset{m}{\Pi}}\int
e^{\frac{n^{2}}{m^{2}}f^{\top}\Xi^{j}_{u}g}d(\pi\times\pi)(f,g)$
$\displaystyle\geq\underset{j=1}{\overset{m}{\Pi}}e^{\frac{n^{2}}{m^{2}}\int
f^{\top}\Xi^{j}_{u}g\,d(\pi\times\pi)(f,g)}=1.$

Similarly, the numerator is equal to

$\int\mathscr{L}_{\pi}(x_{1})\mathscr{L}_{\pi}(x_{2})dN(0,\Sigma)(x_{1},x_{2})=\int
e^{\frac{n^{2}}{m^{2}}f^{\top}\sum_{j=1}^{m}\Xi^{j}_{u}g}d(\pi\times\pi)(f,g).$

Combining the above displays (i.e. (16) and the last three displays), we
obtain that

$D_{\chi^{2}}({\mathbb{P}}^{Y|U=u}_{0,K};{\mathbb{P}}^{Y|U=u}_{\pi,K})\leq\underset{j=1}{\overset{m}{\Pi}}{\mathbb{E}}_{0}^{X^{j}|U=u}\left[\mathscr{L}_{\pi}\left({X}^{j}\right)^{2}\right]\cdot\int
e^{\frac{n^{2}}{m^{2}}f^{\top}\sum_{j=1}^{m}\Xi^{j}_{u}g}d(\pi\times\pi)(f,g)-1.$
(42)

_Step 2._ What is left to show in this step, is that for $\pi=N(0,\Gamma)$,
$\Gamma\in{\mathbb{R}}^{d\times d}$ can be chosen such that the rhs of the
previous display is small enough whilst also ensuring that $\pi(H_{\rho}^{c})$
is controlled whenever $\rho^{2}$ satisfies (4)-(5) for $c_{\alpha}$ depending
only on $\alpha\in(0,1)$.

For a given $c_{\alpha}>0$, set
$\epsilon:=\frac{\rho}{c_{\alpha}^{1/4}d^{1/2}}$ and
$\Gamma:=\epsilon^{2}\bar{\Gamma}$ for some
$\bar{\Gamma}\in\mathbb{R}^{d\times d}$ to be specified later, separately for
the private and public coin protocols. The remaining mass $\pi(H_{\rho})$ can
now be seen to equal

$\pi(f:\|f\|_{2}^{2}\leq\rho^{2})=\text{Pr}\left(Z^{\top}\bar{\Gamma}Z\leq\sqrt{c_{\alpha}}d\right),$

where $Z$ is a $d$-dimensional standard normal vector. If $\bar{\Gamma}$ is
symmetric, idempotent and has rank (proportional to) $d$, the concentration
inequality in Lemma A.13 yields that the probability on the rhs of the above
display can be made arbitrarily small for small enough choice of
$c_{\alpha}>0$.

We now proceed to bound the first factor in the product on the rhs of (42),
which for a positive semi-definite choice of $\bar{\Gamma}$ equals

$\underset{j=1}{\overset{m}{\Pi}}\int{\mathbb{E}}_{0}^{X^{j}|U=u}\exp\left(\frac{n}{m}(\sqrt{\bar{\Gamma}}(f+g))^{\top}{X}^{j}-\frac{n}{2m}\|\sqrt{\bar{\Gamma}}f\|_{2}^{2}-\frac{n}{2m}\|\sqrt{\bar{\Gamma}}g\|_{2}^{2}\right)dN(0,{\epsilon^{2}}I_{2d})(f,g).$

By direct computation, the latter display equals

$\underset{j=1}{\overset{m}{\Pi}}\int\exp\left(\frac{n\epsilon^{2}}{m}z^{\top}\bar{\Gamma}z^{\prime}\right)dN(0,I_{2d})(z,z^{\prime}).$

By applying the moment generating function of the Gaussian chaos, e.g. Lemma
6.2.2 in [40] to the above display and using that $\rho^{2}$ satisfies (4) or
(5), we obtain that for
$\frac{n\epsilon^{2}}{m}\|\bar{\Gamma}\|\lesssim\frac{n\rho^{2}}{c_{\alpha}^{1/2}m\sqrt{d}}\leq\sqrt{c_{\alpha}/m}\leq\sqrt{c_{\alpha}}$
small enough, where $\|\cdot\|$ denotes the spectral norm of a matrix, there
exists a constant $C\geq\|\bar{\Gamma}\|^{2}/d$ such that

$\underset{j=1}{\overset{m}{\Pi}}{\mathbb{E}}_{0}^{X^{j}|U=u}\left[\mathscr{L}_{\pi}\left({X}^{j}\right)^{2}\right]\leq\exp\left(Cc_{\alpha}^{-1}\frac{n^{2}\rho^{4}}{md}\right)\leq\exp(Cc_{\alpha}).$
(43)

The exponent can be made arbitrarily close to zero per choice of
$c_{\alpha}>0$.

We switch our attention now to the second factor in the product on the rhs of
(42), which we bound by applying Lemma 6.2.2 in [40] once more,

$\int
e^{\frac{n^{2}}{m^{2}}(\sqrt{\Gamma}f)^{\top}\sum_{j=1}^{m}\Xi^{j}_{u}(\sqrt{\Gamma}g)}dN(0,\epsilon^{2}I_{2d})(f,g)\leq
e^{C\frac{n^{4}\epsilon^{4}}{m^{4}}\text{Tr}\left((\sqrt{\bar{\Gamma}}^{\top}\Xi_{u}\sqrt{\bar{\Gamma}})^{2}\right)},$
(44)

whenever

$\frac{n^{2}\epsilon^{2}}{m^{2}}\|\sqrt{\bar{\Gamma}}^{\top}\Xi_{u}\sqrt{\bar{\Gamma}}\|$
(45)

is small enough.

It remains to choose a symmetric, idempotent positive semi-definite
$\bar{\Gamma}$ that sufficiently bounds (45) and to combine the above displays
providing the stated lower bound for the testing risk. For the exact choice of
$\bar{\Gamma}$, we distinguish between the public coin and private coin cases.
In both cases, we employ the data processing inequalities of Lemma A.3 and
Lemma A.2, which yield that

$\text{Tr}(\Xi_{u})=\underset{j=1}{\overset{m}{\sum}}\text{Tr}(\Xi^{j}_{u})\leq\min\\{2\log
2\cdot\frac{b}{d},1\\}\frac{m^{2}d}{n}.$ (46)

_The public coin case:_ In this case, it suffices to take
$\bar{\Gamma}=I_{d}$, which is trivially symmetric, idempotent and positive
semi-definite. By Lemma A.2, $\frac{n}{m}\Xi_{u}^{j}\leq I_{d}$, so (45) holds
as well for this choice of $\bar{\Gamma}$:

$\frac{n^{2}\epsilon^{2}}{m^{2}}\|\Xi_{u}\|\leq
n\epsilon^{2}\leq\frac{n\rho^{2}}{\sqrt{c_{\alpha}}d}\leq\sqrt{c_{\alpha}},$

where the second to last inequality holds for $\rho^{2}$ satisfying (4).

It remains to combine our results and provide a lower bound for the testing
risk. Note that

$\displaystyle\text{Tr}(\Xi^{2}_{u})=\|\Xi_{u}\|\,\text{Tr}(\Xi_{u})\leq\frac{m^{2}}{n}\text{Tr}(\Xi_{u})\lesssim\frac{(b\wedge
d)m^{4}}{n^{2}},$

where the last inequality follows from (46). Combining the above bound with
assertions (44), (43), (42), (16), and (15),
$\epsilon^{4}=c_{\alpha}^{-1}d^{-2}\rho^{4}$ and the fact that
$\pi(H_{\rho})\leq\alpha/2$, we obtain that

$\displaystyle\underset{T\in{\mathcal{T}}_{pub}(b)}{\inf}{\mathcal{R}}(H_{\rho},T)$
$\displaystyle\geq
1-\sqrt{2(e^{C(\frac{n^{2}\rho^{4}}{c_{\alpha}md}+\frac{n^{2}\rho^{4}(b\wedge
d)}{c_{\alpha}d^{2}})}-1)}-\pi(H_{\rho}^{c})$ $\displaystyle\geq
1-\sqrt{2(e^{2Cc_{\alpha}}-1)}-\alpha/2>1-\alpha,$

whenever $\rho^{2}$ satisfies (4) for $c_{\alpha}>0$ small enough. This
finishes the proof for the public coin case.

_The private coin case:_ Since without loss of generality we can assume that
$U$ is degenerate in the private coin case, $\Xi_{u}=\Xi$ for
${\mathbb{P}}^{U}$-almost every $u$. The matrix $\Xi$ is positive definite and
symmetric, therefore it possesses a spectral decomposition
$V^{\top}\text{Diag}(\xi_{1},\dots,\xi_{d})V$. Without loss of generality,
assume that $\xi_{1}\geq\xi_{2}\geq\ldots\geq\xi_{d}$ with corresponding
eigenvectors $V=\left(\begin{matrix}v_{1}&\dots&v_{d}\end{matrix}\right)$. Let
$\check{V}$ denote the $d\times\lceil d/2\rceil$ matrix
$\left(\begin{matrix}v_{\lfloor d/2\rfloor+1}&\dots&v_{d}\end{matrix}\right)$.
The choice of prior may depend on $\Xi$, to see this, note the order of the
supremum and infimum in (15) and the fact that $\Xi$ soley depends on the
choice of kernel. To that extent, set
$\bar{\Gamma}=\check{V}\check{V}^{\top}$. It holds that

$\displaystyle\text{Tr}(\check{V}\check{V}^{\top})$
$\displaystyle=\underset{i=1}{\overset{d}{\sum}}\underset{k=\lfloor
d/2\rfloor+1}{\overset{d}{\sum}}(v_{k})_{i}^{2}=\lceil d/2\rceil.$

The choice $\Gamma=\epsilon^{2}\bar{\Gamma}$ is thus seen to satisfy the
conditions of symmetry and positive definiteness and is idempotent with rank
$\lceil d/2\rceil$.

Since the eigenvalues are decreasingly ordered,

$\xi_{\lfloor d/2\rfloor}\leq\frac{2}{d}\underset{i=1}{\overset{\lfloor
d/2\rfloor}{\sum}}\xi_{i}\leq\frac{2}{d}\text{Tr}(\Xi).$

By orthogonality of the columns of $V$,
$\check{V}^{\top}\Xi\check{V}=\text{Diag}(\xi_{\lfloor
d/2\rfloor+1},\dots,\xi_{d})$. Combining this inequality with the last display
and assertion (46) we get that for $\rho^{2}$ satisfying (5) the term (45) can
be made arbitrarily small for small enough choice of $c_{\alpha}$, i.e.

$\displaystyle\frac{n^{2}\epsilon^{2}}{m^{2}}\|\sqrt{\bar{\Gamma}}^{\top}\Xi_{u}\sqrt{\bar{\Gamma}}\|$
$\displaystyle\leq\frac{n^{2}\epsilon^{2}}{m^{2}}\xi_{\lfloor d/2\rfloor}\leq
2\frac{n^{2}\rho^{2}}{\sqrt{c_{\alpha}}d^{2}m^{2}}\text{Tr}(\Xi)$
$\displaystyle\leq(4\log 2)\frac{n\rho^{2}(b\wedge
d)}{\sqrt{c_{\alpha}}d^{2}}\leq(4\log 2)\sqrt{c_{\alpha}/d}.$

Finally, a similar argument will be used to bound the right hand side of (44)
and finally to provide a lower bound for the testing risk. Note that

$\displaystyle\text{Tr}\big{(}(\sqrt{\bar{\Gamma}}^{\top}\Xi_{u}\sqrt{\bar{\Gamma}})^{2}\big{)}=\text{Tr}\left((\check{V}^{\top}\Xi\check{V})^{2}\right)=\underset{i=\lfloor
d/2\rfloor+1}{\overset{d}{\sum}}\xi_{i}^{2}\leq d\xi_{\lfloor
d/2\rfloor}^{2}\leq\frac{4}{d}\text{Tr}(\Xi)^{2},$

which implies in turn that

$\frac{n^{4}\epsilon^{4}}{m^{4}}\text{Tr}\left((\check{V}^{\top}\Xi\check{V})^{2}\right)\leq
4\frac{n^{4}\rho^{4}}{c_{\alpha}m^{4}d^{3}}\text{Tr}(\Xi)^{2}\leq
4\frac{n^{2}\rho^{4}(b\wedge d)^{2}}{c_{\alpha}d^{3}},$

where the last inequality follows from (46). Consequently, we have obtained
that

$\displaystyle\underset{T\in{\mathcal{T}}_{priv}(b)}{\inf}{\mathcal{R}}(H_{\rho},T)$
$\displaystyle\geq
1-\sqrt{2(e^{C(\frac{n^{2}\rho^{4}}{c_{\alpha}md}+\frac{n^{2}\rho^{4}(b\wedge
d)^{2}}{c_{\alpha}d^{3}})}-1)}-\pi(H_{\rho}^{c})$ $\displaystyle\geq
1-\sqrt{2(e^{2Cc_{\alpha}}-1)}-\alpha/2>1-\alpha,$

for $\rho^{2}$ satisfying (5) and $c_{\alpha}>0$ small enough.

##  10 Lemma 10.1: Gaussian maximization

Before giving the detailed statement of the lemma below, we briefly
contemplate on its aim and proof. The lemma bears a close connection to
Brascamp-Lieb inequalities [10, 26, 8]. Brascamp-Lieb type inequalities have
appeared in context of information theory in the literature before, see e.g.
[16, 27], where Gaussian extremality is established for certain information
theoretic optimization problems. Instead of the information theoretic entropy
based route, we rely on the technique of [26]. The resulting lemma allows us
to bound the ratio between (35) and (38), i.e.

$\frac{\int\mathscr{L}_{\pi}(x_{1})\mathscr{L}_{\pi}(x_{2})q_{u}(x_{1},x_{2})d(P_{0}\times
P_{0})(x_{1},x_{2})}{\underset{j=1}{\overset{m}{\Pi}}\int\mathscr{L}^{j}_{\pi}(x_{1}^{j})\mathscr{L}^{j}_{\pi}(x_{2}^{j})q_{u}^{j}(x_{1}^{j},x_{2}^{j})d(P_{0}\times
P_{0})(x_{1}^{j},x_{2}^{j})},$ (47)

by (39), i.e. a Gaussian distribution with matching mean and covariance.
Consequently, we obtain a quadratic form in the covariance that we would
otherwise obtain via a Taylor expansion. That such a quadratic form does not
follow through more standard means such as Taylor expansion is described in
[3], Section 4.

The proof of the lemma exploits the conjugacy between likelihood of the
observation $X$ and the Gaussian prior on the parameter to obtain that a
Gaussian distribution is in fact an extremal case. For reasons of space, we
defer the proof to Section F of the Supplementary Material.

######  Lemma 10.1.

For $x\in{\mathbb{R}}^{mk}$, let $x^{j}\in{\mathbb{R}}^{k}$, $j=1,...,m$,
denote the projection of $x$ on the coordinates $\\{(j-1)k+1,\dots,jk\\}$. Let
$\Lambda\in\mathbb{R}^{k\times k}$ a positive definite symmetric matrix and
$\Lambda^{\otimes m}=\text{Diag}(\Lambda,....,\Lambda)\in\mathbb{R}^{mk\times
mk}$. For $h\in{\mathbb{R}}^{k}$, let $p_{h}$ denote the density of a
$N(h,\Lambda)$ distribution with respect to the Lebesgue measure on
${\mathbb{R}}^{k}$ and let $p^{m}_{h}(x):=\Pi_{j=1}^{m}p_{h}(x^{j})$. Consider
for some $M>0$, ${\mathcal{Q}}\equiv{\mathcal{Q}}(M,\Sigma)$ the class of all
nonnegative functions $q\in L_{\infty}({\mathbb{R}}^{mk})$ satisfying
$\frac{q(x)}{\int q(x)p_{0}^{m}(x)dx}\leq M$ $P_{0}^{m}$-a.e., $\int
x\,q(x)p_{0}^{m}(x)dx=0$ and $\int xx^{\top}\,q(x)p^{m}_{0}(x)dx=\Sigma$.
Furthermore, let $H$ a $N(0,\Upsilon)$-distributed random vector in
${\mathbb{R}}^{k}$. Then

$\underset{q\in{\mathcal{Q}}}{\sup}\;\frac{\int{\mathbb{E}}^{H}\Pi_{j=1}^{m}\frac{p_{H}}{p_{0}}\left(x^{j}\right)\,q(x)p_{0}^{m}(x)dx}{\int\Pi_{j=1}^{m}{\mathbb{E}}^{H}\frac{p_{H}}{p_{0}}\left(x^{j}\right)\,q(x)p_{0}^{m}(x)dx}\leq\frac{\int{\mathbb{E}}^{H}\Pi_{j=1}^{m}\frac{p_{H}}{p_{0}}\left(x^{j}\right)dN(0,\Sigma)(x)}{\int\Pi_{j=1}^{m}{\mathbb{E}}^{H}\frac{p_{H}}{p_{0}}\left(x^{j}\right)dN(0,\Sigma)(x)}.$

Acknowledgements:  We would like to thank Elliot H. Lieb for a helpful comment
regarding the proof of Lemma 10.1. This project has received funding from the
European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme (grant agreement No. 101041064).

Supplementary Material to Optimal high-dimensional and nonparametric
distributed testing under communication constraints In the supplement to this
paper [35], we present the detailed proofs for the main theorems in the paper
“Optimal high-dimensional and nonparametric distributed testing under
communication constraints”.

## References

  * [1] [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
  * [2] [author] Acharya, JayadevJ., Canonne, Clément L.C. L. and Tyagi, HimanshuH. (2020). Inference Under Information Constraints II: Communication Constraints and Shared Randomness. IEEE Transactions on Information Theory 66 7856-7877. 10.1109/TIT.2020.3028439
  * [3] [author] Acharya, JayadevJ., Canonne, Clément LC. L. and Tyagi, HimanshuH. (2020). Distributed Signal Detection under Communication Constraints. In Proceedings of Thirty Third Conference on Learning Theory (JacobJ. Abernethy and ShivaniS. Agarwal, eds.). Proceedings of Machine Learning Research 125 41–63. PMLR.
  * [4] [author] Ahlswede, R.R. and Csiszar, I.I. (1986). Hypothesis testing with communication constraints. IEEE Transactions on Information Theory 32 533–542. Number: 4. 10.1109/TIT.1986.1057194
  * [5] [author] Anderson, Greg W.G. W., Guionnet, AliceA. and Zeitouni, OferO. (2009). An Introduction to Random Matrices. Cambridge Studies in Advanced Mathematics. Cambridge University Press. 10.1017/CBO9780511801334
  * [6] [author] Balakrishnan, SivaramanS. and Wasserman, LarryL. (2019). Hypothesis testing for densities and high-dimensional multinomials: Sharp local minimax rates. The Annals of Statistics 47 1893–1927. 10.1214/18-AOS1729
  * [7] [author] Barnes, Leighton PateL. P., Han, YanjunY. and Ozgur, AyferA. (2020). Lower bounds for learning distributions under communication constraints via Fisher information. Journal of Machine Learning Research 21 1–30.
  * [8] [author] Bennett, JonathanJ., Carbery, AnthonyA., Christ, MichaelM. and Tao, TerenceT. (2008). The Brascamp–Lieb inequalities: finiteness, structure and extremals. Geometric and Functional Analysis 17 1343–1415.
  * [9] [author] Berger, T.T. and Zhang, ZhenZ. (1994). On the CEO problem. In Proceedings of 1994 IEEE International Symposium on Information Theory 201-. 10.1109/ISIT.1994.394767
  * [10] [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.
  * [11] [author] Braverman, MarkM., Garg, AnkitA., Ma, TengyuT., Nguyen, Huy LH. L. and Woodruff, David PD. P. (2016). Communication lower bounds for statistical estimation problems via a distributed data processing inequality. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing 1011–1020.
  * [12] [author] Cai, T TonyT. T. and Wei, HongjiH. Distributed adaptive Gaussian mean estimation with unknown variance: interactive protocol helps adaptation. arXiv preprint arXiv:2001.08877.
  * [13] [author] Cai, T. TonyT. T. and Wei, HongjiH. (2020). Distributed Gaussian Mean Estimation under Communication Constraints: Optimal Rates and Communication-Efficient Algorithms. arXiv:2001.08877 [cs, math, stat]. arXiv: 2001.08877.
  * [14] [author] Cai, T TonyT. T. and Wei, HongjiH. (2022). Distributed nonparametric function estimation: Optimal rate of convergence and cost of adaptation. The Annals of Statistics 50 698–725.
  * [15] [author] Carlen, Eric AE. A. (1991). Superadditivity of Fisher’s information and logarithmic Sobolev inequalities. Journal of Functional Analysis 101 194–211. 10.1016/0022-1236(91)90155-X
  * [16] [author] Carlen, Eric AE. A. and Cordero-Erausquin, DarioD. (2009). Subadditivity of the entropy and its relation to Brascamp–Lieb type inequalities. Geometric and Functional Analysis 19 373–405.
  * [17] [author] Cohen, AlbertA., Daubechies, IngridI. and Vial, PierreP. (1993). Wavelets on the Interval and Fast Wavelet Transforms. Applied and Computational Harmonic Analysis 1 54 - 81. https://doi.org/10.1006/acha.1993.1005
  * [18] [author] Daubechies, I.I. (1992). Ten Lectures on Wavelets. Society for Industrial and Applied Mathematics. 10.1137/1.9781611970104
  * [19] [author] Duchi, John C.J. C., Jordan, Michael I.M. I., Wainwright, Martin J.M. J. and Zhang, YuchenY. (2014). Optimality guarantees for distributed statistical estimation. arXiv:1405.0782 [cs, math, stat]. arXiv: 1405.0782.
  * [20] [author] Giné, EvaristE. and Nickl, RichardR. (2016). Mathematical foundations of infinite-dimensional statistical models. Cambridge series in statistical and probabilistic mathematics.
  * [21] [author] Te Sun Han and Amari, S.S. (1998). Statistical inference under multiterminal data compression. IEEE Transactions on Information Theory 44 2300–2324. Number: 6. 10.1109/18.720540
  * [22] [author] Han, YanjunY., Özgür, AyferA. and Weissman, TsachyT. (2018). Geometric lower bounds for distributed parameter estimation under communication constraints. In Conference On Learning Theory 3163–3188. PMLR.
  * [23] [author] Härdle, W.W., Kerkyacharian, G.G., Picard, D.D. and Tsybakov, A.A. (2012). Wavelets, Approximation, and Statistical Applications. Lecture Notes in Statistics. Springer New York.
  * [24] [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
  * [25] [author] Kreidl, O. PatrickO. P., Tsitsiklis, John N.J. N. and Zoumpoulis, Spyros I.S. I. (2011). On Decentralized Detection With Partial Information Sharing Among Sensors. IEEE Transactions on Signal Processing 59 1759–1765. Number: 4. 10.1109/TSP.2010.2099223
  * [26] [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
  * [27] [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
  * [28] [author] Petrov, Valentin VV. V. (2022). Sums of independent random variables. In Sums of Independent Random Variables De Gruyter.
  * [29] [author] Rao, A.A. and Yehudayoff, A.A. (2020). Communication Complexity: and Applications. Cambridge University Press.
  * [30] [author] Shamir, OhadO. (2014). Fundamental limits of online and distributed algorithms for statistical learning and estimation. Advances in Neural Information Processing Systems 27 163–171.
  * [31] [author] Spokoiny, V. G.V. G. (1996). Adaptive hypothesis testing using wavelets. The Annals of Statistics 24\. 10.1214/aos/1032181163
  * [32] [author] Szabo, BotondB. and van Zanten, HarryH. (2020). Adaptive distributed methods under communication constraints. The Annals of Statistics 48 2347–2380.
  * [33] [author] Szabo, BotondB. and van Zanten, HarryH. (2020). Distributed function estimation: adaptation using minimal communication. arXiv preprint arXiv:2003.12838.
  * [34] [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.
  * [35] [author] Szabó, BotondB., Vuursteen, LasseL. and Van Zanten, HarryH. (2022). Supplement to “Optimal high-dimensional and nonparametric distributed testing under communication constraints”.
  * [36] [author] Szabo, BotondB. and Zaman, AzeemA. (2022). Distributed Nonparametric Estimation under Communication Constraints. preprint.
  * [37] [author] Tarighati, AllaA., Gross, JamesJ. and Jalden, JoakimJ. (2017). Decentralized Hypothesis Testing in Energy Harvesting Wireless Sensor Networks. IEEE Transactions on Signal Processing 65 4862–4873. 10.1109/TSP.2017.2716909
  * [38] [author] Tenney, R. R.R. R. and Sandell, N. R.N. R. (1981). Detection with Distributed Sensors. IEEE Transactions on Aerospace and Electronic Systems AES-17 501–510. Number: 4. 10.1109/TAES.1981.309178
  * [39] [author] Tsitsiklis, John N.J. N. (1988). Decentralized detection by a large number of sensors. Mathematics of Control, Signals, and Systems 1 167–182. Number: 2. 10.1007/BF02551407
  * [40] [author] Vershynin, RomanR. (2018). High-Dimensional Probability: An Introduction with Applications in Data Science, 1 ed. Cambridge University Press. 10.1017/9781108231596
  * [41] [author] Xu, AolinA. and Raginsky, MaximM. (2016). Information-Theoretic Lower Bounds on Bayes Risk in Decentralized Estimation. arXiv:1607.00550 [cs, math, stat]. arXiv: 1607.00550.
  * [42] [author] Yao, Andrew Chi-ChihA. C.-C. (1979). Some Complexity Questions Related to Distributive Computing(Preliminary Report). In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing. STOC ’79 209–213. Association for Computing Machinery, New York, NY, USA. 10.1145/800135.804414
  * [43] [author] Zhang, YuchenY., Duchi, John CJ. C., Jordan, Michael IM. I. and Wainwright, Martin JM. J. (2013). Information-theoretic lower bounds for distributed statistical estimation with communication constraints. In NIPS 2328–2336. Citeseer.
  * [44] [author] Zhu, YuanchengY. and Lafferty, JohnJ. (2018). Distributed Nonparametric Regression under Communication Constraints. In Proceedings of the 35th International Conference on Machine Learning (JenniferJ. Dy and AndreasA. Krause, eds.). Proceedings of Machine Learning Research 80 6009–6017. PMLR.

, and

##  A Auxilliary lemmas for finite dimensional Gaussian mean testing

###  A.1 Lemmas related to the lower bound (Theorem 3.1)

Following the notation of Section 2 in the article, let
${\mathbb{P}}_{f}\equiv{\mathbb{P}}_{f,K}$ denote the joint distribution of
$Y$, $U$ and $X$ where $X^{j}$ follows $N(f,\frac{{m}}{{n}}I_{d})$ and
$Y\sim{\mathbb{E}}_{f}^{X,U}K(\cdot|X,U)=:{\mathbb{P}}_{f,K}^{Y}$ for
$f\in{\mathbb{R}}^{d}$. Let $\pi$ be a probability distribution on
$\mathbb{R}^{d}$ and define the mixture distribution $P_{\pi}$ by

$P_{\pi}(A)=\int P_{f}(A)d\pi(f),$

where $P_{f}={\mathbb{P}}_{f}^{X}$.

######  Lemma A.1.

[Le Cam bound] For any distribution on $U$, it holds that

$\underset{\varphi,K}{\inf}\left({\mathbb{E}}_{0,K}^{Y}\varphi+\underset{f\in
H_{\rho}}{\sup}\,{\mathbb{E}}_{f,K}^{Y}(1-\varphi)\right)\geq\underset{K}{\inf}\left(\underset{\pi}{\sup}(1-\|{\mathbb{P}}_{0,K}^{Y}-{\mathbb{P}}_{\pi,K}^{Y}\|_{TV})-\pi(H_{\rho}^{c})\right),$

where

  * •

the infimum on the lhs is taken over all Markov kernels
$K:\,2^{{\mathcal{Y}}}\times{\mathcal{X}}\times{\mathcal{U}}\to[0,1]$ in a
suitable way and maps $\varphi:{\mathcal{Y}}\to\\{0,1\\}$,

  * •

the infimum on the rhs is over the same class od Markov kernels ,

  * •

the supremum on the rhs is over all prior distributions $\pi$ on
$\mathbb{R}^{d}$.

###### Proof.

It trivially holds that for any
$\varphi^{\prime}:\,{\mathcal{Y}}\mapsto\\{0,1\\}$,

$\left({\mathbb{E}}_{0,K}^{Y}\varphi^{\prime}(Y)+\underset{f\in
H_{\rho}}{\sup}{\mathbb{E}}_{f,K}^{Y}(1-\varphi^{\prime}(Y))\right)\geq\underset{\varphi}{\inf}\left({\mathbb{E}}_{0,K}^{Y}\varphi(Y)+\underset{f\in
H_{\rho}}{\sup}{\mathbb{E}}_{f,K}^{Y}(1-\varphi(Y))\right),$

where the infimum is over all $\varphi:{\mathcal{Y}}\mapsto\\{0,1\\}$.
Furthermore, for any prior distribution $\pi$ on $\mathbb{R}^{d}$ it holds
that

$\displaystyle\underset{f\in
H_{\rho}}{\sup}\,{\mathbb{E}}_{f,K}^{Y}(1-\varphi(Y))$
$\displaystyle\geq\int_{\\{f\in
H_{\rho}\\}}{\mathbb{E}}_{f,K}^{Y}(1-\varphi(Y))d\pi(f)$
$\displaystyle\geq\int{\mathbb{E}}_{f,K}^{Y}(1-\varphi(Y))d\pi(f)-\pi(H_{\rho}^{c}).$
(S.1)

Hence the rhs of the second last display is further bounded from below by

$\inf_{\varphi}\big{(}{\mathbb{E}}_{0,K}^{Y}\varphi(Y)+{\mathbb{E}}_{\pi,K}^{Y}(1-\varphi(Y))-\pi(H_{\rho}^{c})\big{)}$

for all prior distributions $\pi$ on $\mathbb{R}^{d}$. For any $\varphi$,
write $A_{\varphi}=\varphi^{-1}(\\{0\\})$ and note that

$\displaystyle{\mathbb{P}}_{0,K}^{Y}\varphi(Y)+{\mathbb{P}}_{\pi,K}^{Y}(1-\varphi(Y))$
$\displaystyle=1-\big{(}{\mathbb{P}}_{0,K}^{Y}(Y\in
A_{\varphi})-{\mathbb{P}}_{\pi,K}^{Y}(Y\in A_{\varphi})\big{)}.$

By combining the above two displays we get that

$\displaystyle\underset{\varphi}{\inf}\left({\mathbb{E}}_{0,K}^{Y}\varphi(Y)+\underset{f\in
H_{\rho}}{\sup}\,{\mathbb{E}}_{f,K}^{Y}(1-\varphi(Y))\right)$
$\displaystyle\geq
1-\underset{A}{\sup}|{\mathbb{P}}_{0,K}^{Y}(A)-{\mathbb{P}}_{\pi,K}^{Y}(A)|-\pi(H_{\rho}^{c}).$

Since the above is true for any distribution $\pi$ on $\mathbb{R}^{d}$, the
statement is true after taking the supremum over $\pi$ also. Since the above
holds for an arbitrary Markov kernel
$K:\,2^{{\mathcal{Y}}}\times{\mathcal{X}}\times{\mathcal{U}}\to[0,1]$, the
proof is concluded. ∎

######  Lemma A.2.

Let $\Xi_{u}^{j}$ denote the matrix

$\displaystyle\Xi_{u}^{j}={\mathbb{E}}_{0}^{Y^{j}}{\mathbb{E}}_{0}^{Y^{j}|U=u}\left[{X}^{j}\bigg{|}Y^{j},U=u\right]{\mathbb{E}}_{0}^{Y^{j}|U=u}\left[{X}^{j}\bigg{|}Y^{j},U=u\right]^{\top}.$

It holds that $\Xi_{u}^{j}\leq\frac{m}{n}I_{d}$.

###### Proof.

Let $v\in{\mathbb{R}}^{d}$, then

$\displaystyle v^{\top}\Xi_{u}^{j}v$
$\displaystyle={\mathbb{E}}_{0}^{Y^{j}}{\mathbb{E}}_{0}^{Y|U=u}\left[v^{\top}{X}^{j}\bigg{|}Y^{j},U=u\right]{\mathbb{E}}_{0}^{Y|U=u}\left[({X}^{j})^{\top}v\bigg{|}Y^{j},U=u\right]$
$\displaystyle={\mathbb{E}}_{0}^{Y^{j}}{\mathbb{E}}_{0}^{Y|U=u}\left[v^{\top}{X}^{j}\bigg{|}Y^{j},U=u\right]^{2}.$

Since the conditional expectation contracts the $L_{2}$-norm, we obtain that
the latter is bounded by

${\mathbb{E}}_{0}v^{\top}{X}^{j}({X}^{j})^{\top}v=\frac{m}{n}\|v\|_{2}^{2},$

which completes the proof. ∎

The previous lemma is in some sense a data processing inequality: the
covariance matrix of $X|Y$ is strictly dominated by the covariance of the
original process $X$. The following lemma extends this and shows that the
trace of the covariance satisfies a different data processing inequality,
where the loss of information due to $Y^{j}$ having only $b^{j}$ bits
available is captured. When $b^{j}\ll d$, the latter data processing
inequality is stronger than the one implied by Lemma A.2. The lemma below is
essentially Theorem 2 of [7] adapted to our setting, for which we provide a
different proof that results in a smaller constant.

######  Lemma A.3.

Consider the matrix $\Xi_{u}^{j}$ given in Lemma A.2, then

$\text{Tr}(\Xi_{u}^{j})\leq 2\log(2)\frac{m}{n}(\log_{2}|{\mathcal{Y}}^{j}|).$
(S.2)

In particular, for $\log_{2}|{\mathcal{Y}}^{j}|=b^{j}$,

$\text{Tr}(\Xi_{u}^{j})\leq\left(2\log(2)\frac{b^{j}}{d}\bigwedge
1\right)\frac{md}{n}.$ (S.3)

###### Proof.

We start by noting that under ${\mathbb{P}}_{0}$, ${X}^{j}$ follows a
$N(0,\frac{m}{n}I_{d})$ distribution. For any unit vector
$v\in{\mathbb{R}}^{d}$ and $s\in{\mathbb{R}}$ this means that

${\mathbb{E}}_{0}e^{s\langle{X}^{j},v\rangle}\leq e^{\frac{s^{2}m}{2n}}.$

Furthermore, for arbitary $y\in{\mathcal{Y}}$,

$\displaystyle\underset{y}{\overset{}{\sum}}{\mathbb{P}}^{Y^{j}|U=u}(y){\mathbb{E}}_{0}\left[e^{s\langle{X}^{j},v\rangle}\big{|}Y^{j}=y,U=u\right]$
$\displaystyle\geq{\mathbb{P}}^{Y^{j}|U=u}(y){\mathbb{E}}_{0}\left[e^{s\langle{X}^{j},v\rangle}\big{|}Y^{j}=y,U=u\right]$
$\displaystyle\geq{\mathbb{P}}^{Y^{j}|U=u}(y)e^{s{\mathbb{E}}_{0}\left[\langle{X}^{j},v\rangle\big{|}Y^{j}=y,U=u\right]},$

where the last line follows by Jensen’s inequality. By combining the above
displays we obtain that

$s{\mathbb{E}}_{0}\left[\langle{X}^{j},v\rangle\big{|}Y^{j}=y,U=u\right]\leq\frac{s^{2}m}{2n}-\log{\mathbb{P}}^{Y^{j}|U=u}(y)$

for all $s\in{\mathbb{R}}$. Choosing
$s=\frac{n}{m}{\mathbb{E}}_{0}\left[\langle{X}^{j},v\rangle\big{|}Y^{j}=y,U=u\right]$,
we have for any unit vector $v\in{\mathbb{R}}^{d}$,

${\mathbb{E}}_{0}\left[\langle{X}^{j},v\rangle\big{|}Y^{j}=y,U=u\right]^{2}\leq-2\frac{m}{n}\log{\mathbb{P}}^{Y^{j}|U=u}(y).$

Next define for $y\in\mathcal{Y}^{j}$

$w_{1,y}=\frac{1}{\|{\mathbb{E}}_{0}({X}^{j}|Y^{j}=y,U=u)\|_{2}}{\mathbb{E}}_{0}\left[{X}^{j}|Y^{j}=y,U=u\right].$
(S.4)

Choose now $w_{2,y},\dots,w_{d,y}$ such that together with $w_{1,y}$ the
vectors form an orthonormal basis for ${\mathbb{R}}^{d}$. We then have

$\displaystyle\text{Tr}(\Xi^{j}_{u})$
$\displaystyle=\underset{y\in{\mathcal{Y}}^{j}}{\overset{}{\sum}}{\mathbb{P}}^{Y^{j}|U=u}(y)\underset{i=1}{\overset{d}{\sum}}{\mathbb{E}}_{0}\left[\langle
w_{i,y},X^{j}\rangle|Y^{j}=y,U=u\right]^{2}$
$\displaystyle=\underset{y\in{\mathcal{Y}}^{j}}{\overset{}{\sum}}{\mathbb{P}}^{Y^{j}|U=u}(y){\mathbb{E}}_{0}\left[\langle
w_{1,y},X^{j}\rangle|Y^{j}=y,U=u\right]^{2}$
$\displaystyle\leq-2\frac{m}{n}\underset{y\in{\mathcal{Y}}^{j}}{\overset{}{\sum}}{\mathbb{P}}^{Y^{j}|U=u}(y)\log{\mathbb{P}}^{Y^{j}|U=u}(y)\leq
2\frac{m}{n}\log|{\mathcal{Y}}^{j}|,$

where the last inequality follows from the fact that uniform distribution on
${\mathcal{Y}}^{j}$ maximizes the entropy on the lhs. For the second statement
note that by construction $\log|{\mathcal{Y}}^{j}|\leq b^{j}\log 2$.
Furthermore in view of of Lemma A.2, $\log|{\mathcal{Y}}^{j}|\leq dm/n$. Then
the statement follows by combining the above upper bounds for
$\log|{\mathcal{Y}}^{j}|$ with the preceding display. ∎

###  A.2 Lemmas for the upper bound theorems in the finite dimensional
Gaussian mean model

We state a slightly extended version of Lemma 4.1.

######  Lemma A.4.

Consider for $k,l\in{\mathbb{N}}$, $l\geq 2$, independent random variables
$\\{B^{j}_{i}:i=1,\dots,k,\;j=1,\dots,l\\}$ with
$B^{j}_{i}\sim\text{Ber}(p_{i})$. If $p_{i}=1/2$ for $i=1,\dots,k$, for each
$\alpha\in(0,1)$ there exists $\kappa_{\alpha}>0$ such that

$\text{Pr}\left(\bigg{|}\frac{1}{\sqrt{k}l}\underset{i=1}{\overset{k}{\sum}}\left(\underset{j=1}{\overset{l}{\sum}}(B_{i}^{j}-\frac{1}{2})\right)^{2}-\sqrt{k}/4\bigg{|}\geq\kappa_{\alpha}\right)\leq\alpha.$

On the other hand, for arbitrary $c_{\alpha,n}>0$,

$\eta_{p,l,k}:=\frac{l-1}{2\sqrt{k}}\underset{i=1}{\overset{k}{\sum}}\left(p_{i}-\frac{1}{2}\right)^{2}\geq
c_{\alpha,n},$ (S.5)

it holds that

$\text{Pr}\left(\bigg{|}\frac{1}{\sqrt{k}l}\underset{i=1}{\overset{k}{\sum}}\left(\underset{j=1}{\overset{l}{\sum}}(B_{i}^{j}-\frac{1}{2})\right)^{2}-\sqrt{k}/4\bigg{|}\leq
c_{\alpha,n}\right)\leq\frac{1/2+16\eta_{p,l,k}/\sqrt{k}}{\eta_{p,l,k}^{2}}.$
(S.6)

###### Proof.

The LHS in the event having bounded variance: a straightforward computation
(using that for $B_{i}^{j}\sim\text{Bern}(p_{i})$, the central fourth moment
is $E(B_{i}^{j}-p_{i})^{4}=p_{i}(1-p_{i})(1-3p_{i}(1-p_{i}))\leq 1/16$ and
$\text{Var}(X)\leq EX^{2}$) yields

$\displaystyle{\mathbb{E}}\Big{[}\frac{1}{\sqrt{k}l}\underset{i=1}{\overset{k}{\sum}}$
$\displaystyle\Big{(}\underset{j=1}{\overset{l}{\sum}}(B_{i}^{j}-\frac{1}{2})\Big{)}^{2}-\frac{\sqrt{k}}{4}\Big{]}^{2}=\frac{1}{kl^{2}}\underset{i=1}{\overset{k}{\sum}}\text{Var}\Big{[}\Big{(}\underset{j=1}{\overset{l}{\sum}}(B_{i}^{j}-1/2)\Big{)}^{2}\Big{]}$
$\displaystyle\leq\frac{1}{l^{2}}\sum_{j=1}^{l}{\mathbb{E}}(B_{i}^{j}-1/2)^{4}+\frac{1}{l^{2}}\sum_{j=1}^{l}\big{(}{\mathbb{E}}(B_{i}^{j}-1/2)^{2}\big{)}^{2}\leq
1/8,$ (S.7)

after which Chebyshev’s inequality yields the first statement.

We turn to the second statement. Adding and subtracting $p_{i}$ and expanding
the square, the lhs of the display in the lemma can be written as

$\displaystyle\text{Pr}\left(\bigg{|}\frac{1}{\sqrt{k}l}\underset{i=1}{\overset{k}{\sum}}\left(\underset{j=1}{\overset{l}{\sum}}B^{j}_{i}-lp_{i}\right)^{2}-\mu_{p}+\frac{l-1}{\sqrt{k}}\underset{i=1}{\overset{k}{\sum}}\left(p_{i}-\frac{1}{2}\right)^{2}+\zeta\bigg{|}\leq
c_{\alpha,n}\right)$ (S.8)

where

$\mu_{p}:=\frac{1}{\sqrt{k}}\underset{i=1}{\overset{k}{\sum}}p_{i}(1-p_{i})\;\;\text{
and
}\;\;\zeta:=\frac{2}{\sqrt{k}}\underset{i=1}{\overset{k}{\sum}}\left(p_{i}-\frac{1}{2}\right)\left(\underset{j=1}{\overset{l}{\sum}}B^{j}_{i}-lp_{i}\right).$

The first term in the event of (S.8) has mean $\mu_{p}$ and variance (by the
same computations as in (S.7))

$\displaystyle\text{Var}\Big{[}\frac{1}{\sqrt{k}l}\underset{i=1}{\overset{k}{\sum}}\Big{(}\underset{j=1}{\overset{l}{\sum}}B^{j}_{i}-lp_{i}\Big{)}^{2}\Big{]}$
$\displaystyle=\frac{1}{kl^{2}}\sum_{i=1}^{k}\text{Var}\Big{[}\Big{(}\sum_{j=1}^{l}B_{i}^{j}-lp_{i}\Big{)}^{2}\Big{]}\leq
1/8.$

The term $\zeta$ has mean $0$ and

$\displaystyle\text{Var}(\zeta)=\frac{4l}{k}\underset{i=1}{\overset{k}{\sum}}(p_{i}-\frac{1}{2})^{2}p_{i}(1-p_{i})\leq\frac{l}{k}\underset{i=1}{\overset{k}{\sum}}\left(p_{i}-\frac{1}{2}\right)^{2}.$

Applying the reverse triangle inequality and condition (S.5), the probability
in (S.8) is bounded from above by

$\displaystyle\text{Pr}\Big{[}\Big{|}\frac{1}{\sqrt{k}l}\underset{i=1}{\overset{k}{\sum}}\Big{(}\underset{j=1}{\overset{l}{\sum}}B^{j}_{i}-lp_{i}\Big{)}^{2}-\mu_{p}\Big{|}+|\zeta|\geq\frac{l-1}{2\sqrt{k}}\underset{i=1}{\overset{k}{\sum}}\Big{(}p_{i}-\frac{1}{2}\Big{)}^{2}\Big{]}$
$\displaystyle\qquad\qquad\leq\text{Pr}\Big{[}\Big{|}\frac{1}{\sqrt{k}l}\underset{i=1}{\overset{k}{\sum}}\Big{(}\underset{j=1}{\overset{l}{\sum}}B^{j}_{i}-lp_{i}\Big{)}^{2}-\mu_{p}\Big{|}\geq\eta_{p,l,k}/2\Big{]}+\text{Pr}\Big{[}|\zeta|\geq\eta_{p,l,k}/2\Big{]}$
$\displaystyle\qquad\qquad\leq\frac{1/8}{(\eta_{p,l,k}/2)^{2}}+\frac{2lk^{-1/2}\eta_{p,l,k}/(l-1)}{(\eta_{p,l,k}/2)^{2}}\leq\frac{1/2+16\eta_{p,l,k}/\sqrt{k}}{\eta_{p,l,k}^{2}},$

where the last line follows by Chebyshev’s inequality.

∎

Next we provide another version of the above lemma, with the sum over the
index $i$ moved inside of the square.

######  Lemma A.5.

Consider for $k,l\in{\mathbb{N}}$, $l\geq 2$, independent random variables
$\\{B^{j}_{i}:i=1,\dots,k;\,j=1,\dots,l\\}$ with
$B^{j}_{i}\sim\text{Ber}(p_{i})$. If $p_{i}=1/2$ for $i=1,\dots,k$, for each
$\alpha\in(0,1)$ there exists $\kappa_{\alpha}>0$ such that

$\text{Pr}\left(\bigg{|}\frac{1}{lk}\left(\underset{i=1}{\overset{k}{\sum}}\underset{j=1}{\overset{l}{\sum}}(B_{i}^{j}-\frac{1}{2})\right)^{2}-1/4\bigg{|}\geq\kappa_{\alpha}\right)\leq\alpha.$

On the other hand, if $p_{i}\geq 1/2$ for all $i=1,...,k$ and for arbitrary
$c_{\alpha,n}>0$

$\eta_{p,l,k}^{\prime}:=\frac{l-1}{2k}\left(\underset{i=1}{\overset{k}{\sum}}(p_{i}-\frac{1}{2})\right)^{2}\geq
c_{\alpha,n}$ (S.9)

it holds that

$\text{Pr}\left(\bigg{|}\frac{1}{kl}\left(\underset{i=1}{\overset{k}{\sum}}\underset{j=1}{\overset{l}{\sum}}(B_{i}^{j}-\frac{1}{2})\right)^{2}-1/4\bigg{|}\leq
c_{\alpha,n}\right)\leq\frac{1/2+16\eta_{p,l,k}^{\prime}/k}{(\eta_{p,l,k}^{\prime})^{2}}.$

###### Proof.

The lhs in the event having bounded variance: by the same arguments as in
(S.7) we have

$\displaystyle{\mathbb{E}}\Big{[}\frac{1}{lk}\Big{(}\underset{i=1}{\overset{k}{\sum}}\underset{j=1}{\overset{l}{\sum}}(B_{i}^{j}-\frac{1}{2})\Big{)}^{2}-\frac{1}{4}\Big{]}^{2}\leq
1/8,$

after which Chebyshev’s inequality yields the first statement.

We turn to the second statement. Adding and subtracting $p_{i}$ and expanding
the square, the lhs of the display in the lemma can be written as

$\displaystyle\text{Pr}\left(\bigg{|}\frac{1}{lk}\left(\underset{i=1}{\overset{k}{\sum}}\underset{j=1}{\overset{l}{\sum}}(B^{j}_{i}-p_{i})\right)^{2}-\mu_{p}^{\prime}+\frac{l-1}{k}\left(\underset{i=1}{\overset{k}{\sum}}(p_{i}-\frac{1}{2})\right)^{2}+\zeta\bigg{|}\leq
c_{\alpha,n}\right),$ (S.10)

where

$\mu_{p}^{\prime}:=1/4-\frac{1}{k}\Big{(}\underset{i=1}{\overset{k}{\sum}}(p_{i}-\frac{1}{2})\Big{)}^{2}\;\;\text{
and
}\;\;\zeta:=\frac{2}{k}\left(\underset{i=1}{\overset{k}{\sum}}(p_{i}-\frac{1}{2})\right)\left(\underset{i=1}{\overset{k}{\sum}}\underset{j=1}{\overset{l}{\sum}}(B^{j}_{i}-p_{i})\right).$

Next we note that in view of the assumption $p_{i}\geq 1/2$ we have that

$\displaystyle\mu_{p}^{\prime}\leq
1/4-\frac{1}{k}\underset{i=1}{\overset{k}{\sum}}(p_{i}-\frac{1}{2})^{2}=\frac{1}{k}\underset{i=1}{\overset{k}{\sum}}p_{i}(1-p_{i})=:\mu_{p}.$

The first term in the event of (S.10) has mean $\mu_{p}$ and variance (by the
same computations as in (S.7))

$\displaystyle\text{Var}\Big{[}\frac{1}{lk}\Big{(}\underset{i=1}{\overset{k}{\sum}}\underset{j=1}{\overset{l}{\sum}}(B^{j}_{i}-p_{i})\Big{)}^{2}\Big{]}$
$\displaystyle=\frac{1}{l^{2}k^{2}}\text{Var}\Big{[}\Big{(}\sum_{j=1}^{l}\sum_{i=1}^{k}(B_{i}^{j}-p_{i})\Big{)}^{2}\Big{]}\leq
1/8.$

The term $\zeta$ has mean $0$ and

$\displaystyle\text{Var}(\zeta)=\frac{4l}{k^{2}}\left(\underset{i=1}{\overset{k}{\sum}}(p_{i}-\frac{1}{2})\right)^{2}\underset{i=1}{\overset{k}{\sum}}p_{i}(1-p_{i})\leq\frac{l}{k^{2}}\left(\underset{i=1}{\overset{k}{\sum}}(p_{i}-\frac{1}{2})\right)^{2}.$

Applying the reverse triangle inequality, condition (S.9) and the inequality
$\mu_{p}\geq\mu_{p}^{\prime}$, the probability in (S.10) is bounded from above
by

$\displaystyle\text{Pr}\Big{[}\Big{|}\frac{1}{kl}\Big{(}\underset{i=1}{\overset{k}{\sum}}\underset{j=1}{\overset{l}{\sum}}(B^{j}_{i}-p_{i})\Big{)}^{2}-\mu_{p}\Big{|}+|\zeta|\geq\frac{l-1}{2}\Big{(}\underset{i=1}{\overset{k}{\sum}}p_{i}-\frac{1}{2}\Big{)}^{2}\Big{]}$
$\displaystyle\qquad\qquad\leq\text{Pr}\Big{[}\Big{|}\frac{1}{kl}\Big{(}\underset{i=1}{\overset{k}{\sum}}\underset{j=1}{\overset{l}{\sum}}(B^{j}_{i}-p_{i})\Big{)}^{2}-\mu_{p}\Big{|}\geq\eta_{p,l,k}^{\prime}/2\Big{]}+\text{Pr}\Big{[}|\zeta|\geq\eta_{p,l,k}^{\prime}/2\Big{]}$
$\displaystyle\qquad\qquad\leq\frac{1/8}{(\eta_{p,l,k}^{\prime}/2)^{2}}+\frac{2lk^{-1}\eta_{p,l,k}^{\prime}/(l-1)}{(\eta_{p,l,k}^{\prime}/2)^{2}}\leq\frac{1/2+16\eta_{p,l,k}^{\prime}/k}{\eta_{p,l,k}^{\prime
2}},$

where the last line follows by Chebyshev’s inequality.

∎

Next we provide the lemmas used in Section 4, providing guarantees for the
testing procedures $T_{\text{I}}$, $T_{\text{II}}$ and $T_{\text{III}}$,
proposed in subsections 4.1, 4.2 and 4.3, respectively.

######  Lemma A.6.

For each $\alpha\in(0,1)$, there exist constants
$\kappa_{\alpha},C_{\alpha},M_{\alpha},D_{0}>0$ such that for $m\geq
M_{\alpha}$ and $d\geq D_{0}$ it holds that

${\mathcal{R}}(H_{\rho},T_{\text{I}})\leq\alpha,$

whenever $\rho^{2}\geq C_{\alpha}\frac{\sqrt{md}}{n}$.

###### Proof of Lemma A.6.

Under the null hypothesis the random variables
$Y_{\text{I}}^{j}\sim^{iid}\text{Bern}(1/2)$. Next we shall apply Lemma 4.1
with $k=1$, and $l=m$. By the first statement of the lemma, we obtain that
there exists ${\kappa}_{\alpha}>0$ such that
${\mathbb{P}}_{0}T_{\text{I}}\leq\alpha/2$.

We give an upper bound for the Type II error by using the second statement of
the lemma, but before that we show that condition (6) holds. Note that the law
of total expectation yields

${\mathbb{E}}_{f}Y_{I}^{j}={\mathbb{E}}_{f}{\mathbb{E}}_{f}\left[Y_{I}^{j}\big{|}S_{\text{I}}^{j}\right]={\mathbb{E}}_{f}F_{\chi^{2}_{d}}\left(S_{\text{I}}^{j}\right)=\text{Pr}(S_{\text{I}}^{j}\geq
W_{d}),$

where $S_{\text{I}}^{j}$ is noncentral Chi-square distributed under
${\mathbb{P}}_{f}$ with $d$-degrees of freedom and noncentrality parameter
$\frac{n}{m}\|f\|_{2}^{2}$ and $W_{d}$ is an independent chi-square
distributed random variable with $d$-degrees of freedom. Then Lemma 4 in [34]
yields that

$\eta_{p,m,1}=\frac{m-1}{2}\left({\mathbb{E}}_{f}Y_{I}^{j}-\frac{1}{2}\right)^{2}\geq\frac{m-1}{3200}\left(\frac{n\|f\|_{2}^{2}}{m\sqrt{d}}\bigwedge\frac{1}{2}\right)^{2}.$
(S.11)

whenever $d\geq D_{0}$ for some universal constant $D_{0}>0$. Consequently, as
$\|f\|_{2}^{2}\geq\rho^{2}\geq C_{\alpha}\frac{\sqrt{md}}{n}$, we obtain that
condition (6) is satisfied whenever $m\geq M_{\alpha}$ for some large enough
$C_{\alpha}>0$ and $M_{\alpha}>0$. Therefore the Type II error is bounded by
the rhs of (7), which is monotone decreasing in $\eta_{p,m,1}$ hence also in
$C_{\alpha}$. Therefore by large enough choice of $C_{\alpha}$ the Type II
error is bounded from above by $\alpha/2$. ∎

######  Lemma A.7.

For each $\alpha\in(0,1)$, there exist constants
$\kappa_{\alpha},C_{\alpha},M_{\alpha}>0$ such that for $m\geq M_{\alpha}$

${\mathcal{R}}(H_{\rho},T_{\text{II}})\leq\alpha,$

whenever $\rho^{2}\geq C_{\alpha}\frac{d}{n\sqrt{d\wedge b}}$.

###### Proof of Lemma A.7.

First note that it is sufficient to consider the case $b\leq d$ as one can
simply take $b=b\wedge d$. Then note that under ${\mathbb{P}}_{f}$,
$\sqrt{n/m}UX^{j}|U\sim N_{d}(\sqrt{n/m}Uf,I_{d})$ by the rotational
invariance of the Gaussian distribution. By linearity of the coordinate
projection, conditionally on $U$,

$\text{1}\left\\{\left(\sqrt{n/m}UX^{j}\right)_{i}>0\right\\}\overset{d}{=}\text{1}\left\\{\sqrt{n/m}(Uf)_{i}+Z>0\right\\},$

where $Z\sim N(0,1)$. As a consequence, the vector $S_{\text{II}}$ is
conditionally on $U$ coordinate wise independent binomially distributed with
parameters $m$ and $p_{f,U}\in[0,1]^{b}$ under ${\mathbb{P}}_{f}^{Y|U}$, where

$(p_{f,U})_{i}=\Phi(\sqrt{n/m}(Uf)_{i}),$

with $\Phi$ the standard normal cdf. Under the null hypothesis,
$(S_{\text{II}})_{i}$ is $\text{Bin}(m,1/2)$ distributed since
$p_{0,U}=(1/2,\dots,1/2)\in[0,1]^{b}$. Next we apply Lemma 4.1 with $k=b$ and
$l=m$. By the first statement of the lemma, it follows that for
$\kappa_{\alpha}$ large enough, ${\mathbb{P}}_{0}T_{\text{II}}\leq\alpha/2$.

In order apply the second statement of the lemma, which yields that the Type
II error is bounded by $\alpha/2$, it suffices to show that the event

$A=\Big{\\{}\frac{m-1}{2\sqrt{b}}\underset{i=1}{\overset{b}{\sum}}\Big{(}(p_{f,U})_{i}-\frac{1}{2}\Big{)}^{2}\geq
N_{\alpha}\Big{\\}},$

where $N_{\alpha}:=\kappa_{\alpha}\vee\frac{16}{\alpha}$, occurs with
${\mathbb{P}}^{U}$-probability greater than $1-\alpha/4$. Note that for this
choice of $N_{\alpha}$, (6) is satisfied on the event $A$ and the rhs of (7)
is smaller than $\alpha/4$. The Type II error is then bound by
${\mathbb{P}}_{f}T_{\text{II}}\leq{\mathbb{P}}_{f}T_{\text{II}}\text{1}_{A}+{\mathbb{P}}_{f}\text{1}_{A^{c}}\leq\alpha/2$.

We proceed to show that ${\mathbb{P}}_{f}\text{1}_{A^{c}}\leq\alpha/4$. By a
standard bound on the Gaussian error function $x\mapsto 2\Phi(x)-1$ (see Lemma
A.11),

$\left(\Phi(\sqrt{n/m}(Uf)_{i})-\frac{1}{2}\right)^{2}\geq\frac{1}{12}\min\left\\{\frac{n}{m}(Uf)_{i}^{2},1\right\\},$

which in turn implies that

$\displaystyle{\mathbb{P}}^{U}\left(\frac{m-1}{2\sqrt{b}}\underset{i=1}{\overset{b}{\sum}}\left((p_{f,U})_{i}-\frac{1}{2}\right)^{2}\leq
N_{\alpha}\right)$
$\displaystyle\leq{\mathbb{P}}^{U}\left(\frac{m-1}{24\sqrt{b}}\underset{i=1}{\overset{b}{\sum}}\min\left\\{\frac{n}{m}(Uf)_{i}^{2},1\right\\}\leq
N_{\alpha}\right).$

Note that $Uf\overset{d}{=}\|f\|_{2}(Z_{1},\dots,Z_{d})/\|Z\|_{2}$, where
$Z=(Z_{1},\dots,Z_{d})\sim N(0,I_{d})$ (see e.g. Section 3.4 of [40]). Using
that $\|f\|_{2}\geq\rho$ and $\rho^{2}\geq C_{\alpha}\frac{d}{n\sqrt{b}}$, the
previous display is further bounded by

$\text{Pr}\left(\frac{m-1}{24\sqrt{b}}\underset{i=1}{\overset{b}{\sum}}\min\left\\{C_{\alpha}\frac{dZ_{i}^{2}}{m\sqrt{b}\|Z\|_{2}^{2}},1\right\\}\leq
N_{\alpha}\right).$

Considering the intersection with the event $\\{\|Z\|_{2}^{2}\leq kd\\}$ for
some $k>0$, the above display can be bounded by

$\text{Pr}\left(\underset{i=1}{\overset{b}{\sum}}\min\\{Z_{i}^{2},C_{\alpha}^{-1}{m\sqrt{b}k}\\}\leq\frac{24{b}mk}{C_{\alpha}(m-1)}N_{\alpha}\right)+\text{Pr}\left(\|Z\|_{2}^{2}\geq
kd\right).$

For $k$ large enough (independent of $d$), the second term is less than
$\alpha/8$. By Lemma A.12,

$\text{Pr}\left(\underset{1\leq i\leq b}{\max}Z_{i}^{2}\geq
C_{\alpha}^{-1}{m\sqrt{b}k}\right)\leq\frac{2b}{e^{C_{\alpha}^{-1}m\sqrt{b}k/4}}.$

For large enough $M_{\alpha}\geq C_{\alpha}$, the condition $m\geq M_{\alpha}$
implies that the right hand side is less than $\alpha/8$. The first term in
the second to last display is consequently bounded by

$\displaystyle\text{Pr}\Big{(}\underset{i=1}{\overset{b}{\sum}}Z_{i}^{2}$
$\displaystyle\leq\frac{24{b}mk}{C_{\alpha}(m-1)}N_{\alpha}\Big{)}+\text{Pr}\left(\underset{1\leq
i\leq b}{\max}Z_{i}^{2}\geq C_{\alpha}^{-1}{m\sqrt{b}k}\right)$
$\displaystyle\qquad\leq\text{Pr}\left(\underset{i=1}{\overset{b}{\sum}}Z_{i}^{2}\leq\frac{24{b}mk}{C_{\alpha}(m-1)}N_{\alpha}\right)+\alpha/8.$

For $m\geq M_{\alpha}\geq 25$ and by choosing $C_{\alpha}$ large enough such
that the Chernoff-Hoeffding bound on the left tail of the chi-square
distribution (see Lemma A.13) can be applied to the first term of the
preceding display we get that

$\text{Pr}\left(\underset{i=1}{\overset{b}{\sum}}Z_{i}^{2}\leq\frac{25kN_{\alpha}}{C_{\alpha}}b\right)\leq\exp\left(-b\frac{\frac{25kN_{\alpha}}{C_{\alpha}}-1-\log\left(\frac{25kN_{\alpha}}{C_{\alpha}}\right)}{2}\right)\leq\alpha/8,$
(S.12)

finishing the proof of the lemma. ∎

######  Lemma A.8.

For $\alpha\in(0,1)$, there exist constants $M_{\alpha},C_{\alpha}>0$ such
that when $m\geq M_{\alpha}d^{2}/b^{2}$, the $b$-bit distributed private
testing protocol $T_{\text{III}}$ given in (14) satisfies

${\mathcal{R}}(H_{\rho},T_{\text{III}})\leq\alpha,$

whenever $\rho^{2}\geq C_{\alpha}\frac{d\sqrt{d}}{nb}$.

###### Proof.

Fix an arbitrary $f\in H_{\rho}$ and define

${\mathcal{J}}=\\{i:\;1\leq i\leq d,\;\frac{n}{m}f_{i}^{2}\geq 1\\}.$ (S.13)

By Lemma A.9 below, the test $T_{\text{III}}^{1}$ given in (12) with
$\kappa_{\alpha},C_{\alpha},M_{\alpha}>0$ large enough satisfies

${\mathbb{E}}_{0}T_{\text{III}}^{1}\leq\alpha/6,\quad\text{and}\quad{\mathbb{E}}_{f}(1-T_{\text{III}}^{1})\leq\alpha/6,$

whenever

$\underset{i\notin{\mathcal{J}}}{\overset{}{\sum}}f_{i}^{2}\geq\rho^{2}/2\;\text{
or }\;\frac{mb}{d\sqrt{d}}>M_{\alpha}.$ (S.14)

Next we consider the case where (S.14) does not hold. Then
$M_{\alpha}\geq\frac{mb}{d\sqrt{d}}\geq M_{\alpha}\frac{\sqrt{d}}{b}$, where
the second inequality follows from the assumption of the lemma. This implies
that $b\geq\sqrt{d}$. Since $\frac{mb}{d\sqrt{d}}\leq M_{\alpha}$ and $m$ can
be taken to be larger than arbitrary constant (otherwise we are in the non-
distributed regime in which the minimax rate can be achieved locally), we can
without loss of generality assume $d$ is larger than an arbitrary constant
(depending only on $\alpha$), hence $b\geq\sqrt{d}\geq 2\log(d+1)$ and the
test $T_{\text{III}}^{2}$ and the corresponding transcripts can be
constructed. Furthermore, $\sum_{i\in{\mathcal{J}}^{c}}f_{i}^{2}<\rho^{2}/2$
implies ${\mathcal{J}}\neq\emptyset$ in view of
$\sum_{i}f_{i}^{2}\geq\rho^{2}$. Consequently, the conditions of Lemma A.10
are satisfied, yielding that there exists a test $T_{\text{III}}^{2}$ such
that ${\mathbb{E}}_{0}T_{\text{III}}^{2}\leq\alpha/6$ and
${\mathbb{E}}_{f}(1-T_{\text{III}}^{2})\leq\alpha/6$. We note that in case
$\frac{mb}{d\sqrt{d}}>M_{\alpha}$, the test $T_{\text{III}}^{2}$ cannot
necessarily be computed (not enough communication budget), but this is not
required as this case is covered by $T_{\text{III}}^{1}$.

We now have that for any $f\in H_{\rho}$, whenever $\frac{mb}{d\sqrt{d}}\leq
M_{\alpha}$, the test $T_{\text{III}}$ can be computed and using that for
nonnegative $x,y\geq 0$, $x\vee y\leq x+y$ and $x\vee y\geq x$, we obtain that

$\displaystyle{\mathcal{R}}(H_{\rho},T_{\text{III}})$
$\displaystyle\leq{\mathbb{E}}_{0}T_{\text{III}}^{1}+{\mathbb{E}}_{0}T_{\text{III}}^{2}\text{1}_{\\{b\geq
2\log(d+1)\\}}$ $\displaystyle\quad+\sup_{f\in
H_{\rho}}\min\big{\\{}{\mathbb{E}}_{f}(1-T_{\text{III}}^{1}),{\mathbb{E}}_{f}(1-T_{\text{III}}^{2}\text{1}_{\\{b\geq
2\log(d+1)\\}})\big{\\}}$ $\displaystyle\leq 2\alpha/6+\alpha/6=\alpha/2.$

∎

Next we provide the risk bounds for the partial tests $T_{\text{III}}^{1}$ and
$T_{\text{III}}^{2}$, used in the previous lemma.

######  Lemma A.9.

For any $\alpha\in(0,1)$ there exist constants
$\kappa_{\alpha},M_{\alpha},C_{\alpha}>0$ such that
${\mathbb{E}}_{0}T_{\text{III}}^{1}\leq\alpha/2.$ Furthermore, for $f\in
H_{\rho}$ if $\rho^{2}\geq C_{\alpha}\frac{d\sqrt{d}}{n(d\wedge b)}$ and
either $\frac{mb}{d\sqrt{d}}\geq M_{\alpha}$ or