# Optimal distributed composite testing in high-dimensional Gaussian models
with 1-bit communication

Botond Szabó Department of Decision Sciences, Bocconi University, Bocconi
Institute for Data Science and Analytics (BIDSA<EMAIL_ADDRESS>Lasse Vuursteen Delft Institute of Applied Mathematics (DIAM), Delft
University of Technology<EMAIL_ADDRESS>and Harry van Zanten
Department of Mathematics, Vrije Universiteit Amsterdam<EMAIL_ADDRESS>
###### Abstract

In this paper we study the problem of signal detection in Gaussian noise in a
distributed setting where the local machines in the star topology can
communicate a single bit of information. We derive a lower bound on the
Euclidian norm that the signal needs to have in order to be detectable.
Moreover, we exhibit optimal distributed testing strategies that attain the
lower bound.

Index terms— Testing, distributed algorithms, hypothesis testing, federated
learning, minimax lower bounds, Gaussian noise.

##  1 Introduction

††2022 IEEE. Personal use of this material is permitted. Permission from IEEE
must be obtained for all other uses, in any current or future media, including
reprinting/republishing this material for advertising or promotional purposes,
creating new collective works, for resale or redistribution to servers or
lists, or reuse of any copyrighted component of this work in other works. DOI:
10.1109/TIT.2022.3150599

The rapidly increasing amount of available data in many fields of application
has triggered the development of distributed methods for data analysis.
Distributed methods, besides being able to speed up computations considerably,
can reduce local memory requirements and can also help in protecting privacy,
by refraining from storing a whole dataset in a single central location.
Moreover, distributed methods occur naturally when data is by construction
observed and processed at multiple locations, for instance in astronomy,
meteorology, seismology, military radar or air traffic control systems.

In the context of decentralized detection, the task of distinguishing between
different signals based on information provided from a network of sensors has
been investigated since the late seventies. Motivated by applications such as
surveillance systems and wireless communication, statistical hypothesis
testing with distributed sensors has received considerable attention over the
past few decades, e.g. [27, 28, 19, 25]. Most of this literature has been
concerned with distinguishing between finitely many signals, by combining the
decisions of sensors or machines receiving (noisy) data from the same
underlying signal [30, 10]. The statistical hypotheses considered at the time
where either simple, or reduce to a simple hypothesis. Under the name of
multiterminal data compression, hypothesis testing and estimation with
observations in fixed finite sample spaces (alphabets) was investigated [3,
16, 15, 4, 22, 31]. In this body of literature, each terminal observes a
stream of iid observations in some alphabet, where the different terminals
might receive observations from different distributions on different
alphabets. Each of the terminals compresses the iid observations into a
message that is sent to a central terminal, at which some inference goal is to
be achieved based on the messages. For an overview, see [26].

The information theoretic aspects of distributed statistical methods have only
been studied rigorously in terms of sample complexity relatively recently. The
problem of distributed testing with a composite alternative hypothesis about a
high-dimensional parameter with limited communication was first considered in
a few recent papers. In [2], theoretical guarantees are derived for
distributed uniformity testing of a discrete distribution in the case that a
collection of machines each receive one observation. Here, sample complexity
(in the sense of minimax convergence rate) is assessed in terms the
cardinality of the sample space, the number of bits available for
communication and the number of observations. In that paper, it is also shown
that in the distributed setting with many local machines, testing performance
can strictly improve when all machines have access to a shared source of
randomness, a so-called public coin. Distributed uniformity testing of a
discrete distribution when multiple observations per machine are available is
considered in [13, 14].

Most of the work, studying distributed inference in terms of sample
complexity, up until now has focused on distributed methods for estimating a
signal in the normal-means model under bandwidth, or communication
restrictions (see for instance [33, 8, 32, 6, 9]). The canonical normal-means
model postulates that we have an observation $X$ satisfying

$\displaystyle X=\mu+\frac{1}{\sqrt{n}}Z,$

where $\mu\in\mathbb{R}^{d}$ is the unknown signal, $Z\sim N_{d}(0,I_{d})$ is
an unobserved noise vector with a $d$-dimensional standard Gaussian
distribution, and $n$ is the signal-to-noise ratio. Note that this is
equivalent to observing $n$ independent copies of a $N_{d}(\mu,I_{d})$-vector.
In the distributed setting considered in the aforementioned articles, $n$ such
observations are distributed across $m$ machines, which then communicate a
transcript to a central machine. The central machine then forms an estimate of
$\mu$ on the basis of these transcripts. The sample complexity of such a
problem is expressed in $n$, $m$, the number of bits available for
communication of the transcripts and the properties of $\mu$ (e.g. Euclidian
norm). Related to this normal-means model, on deriving minimax lower bounds
and optimal distributed estimation strategies in the context of nonparametric
regression, density estimation and Gaussian signal-in-white-noise models (e.g.
[23, 34, 6, 17, 24]).

In this paper, we investigate the information theoretic properties of
distributed methods for testing for the presence of a signal in the normal-
means model. The theory on distributed testing in this setting is much less
developed than that for estimation. Testing for the presence of a signal in
the normal-means model translates to testing the null hypothesis $H_{0}:\mu=0$
that the sequence is identically equal to $0$. Rejecting this hypothesis means
declaring that there is a non-zero signal. A fundamental question is how large
the signal should be in order to be detectable. It is well known that in this
non-distributed model, the size of the signal (by which we mean the Euclidean
norm) has to be of order $d^{1/4}/\sqrt{n}$ in order for the signal to be
detectable (see e.g. [5]). An optimal test is for instance obtained by
rejecting the hypothesis $H_{0}$ if $\|X\|^{2}$ is above a specific threshold,
depending on $d$ and $n$ (see also Section 3.2).

The question we address in this paper is how this changes in the distributed
setting. In our analysis we consider the distributed version of the normal-
means model, where the data ($n$ independent draws from the
$N_{d}(\mu,I_{d})$-distribution) is divided over $m\leq n$ local machines, or
cores. Equivalently, we assume that at each local machine $j\in\\{1,...,m\\}$
we observe a vector $X^{(j)}$ which satisfies

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

where again $\mu\in\mathbb{R}^{d}$ and the $Z^{(j)}$ are independent
$N_{d}(0,I_{d})$-distributed vectors. Each machine carries out a test for the
hypothesis $H_{0}:\mu=0$ using its local data $X^{(j)}$, where we allow that
the machines use a public coin, i.e. a common random vector $U$ that is
available to all local machines. Subsequently, the outcomes of the $m$ local
tests (which are single bits) are sent to a central machine, where they are
combined into a single, overall test. We prove that in this distributed
setting, the size of the signal has to be of the order $(d(m\wedge
d))^{1/4}/\sqrt{n}$ in order for the signal to be detectable. Moreover, we
exhibit optimal distributed tests that achieve this detection bound.

The detection bound has a remarkable “regime change” or “elbow effect” at
$m=d$. As $m$ grows from $1$ to $d$ the testing problem becomes more
difficult, in the sense that the signal needs to be ever larger to be
detectable using an increasing number of machines. This is intuitively
understandable, since as $m$ grows, the local signal-to-noise ratio decreases,
so it is reasonable to expect that the signal needs to be larger to be able to
detect it. The detection bound stops increasing if $m$ grows above $d$
however. In that range, the decrease of the local signal-to-noise ratios is
apparently balanced by the increase of the number of bits that are transmitted
from the local machines to the central one.

The regime change is also reflected by the fact that we need different testing
strategies depending on how $m$ and $d$ are related. If $m$ is below some
threshold, and in particular it does not increase with $n$, then, not
surprisingly, we can simply use the classical non-distributed test mentioned
above at one of the local machines. If $m$ is larger than this threshold but
$m\leq d$, then it is still possible to construct an optimal test by combining
local tests that are based on the test statistics $\|X^{(j)}\|^{2}$, but the
test needs to be constructed more carefully. In the range $m\geq d$ this
strategy becomes sub-optimal and we have to adopt a different approach, using
the fact that we have a public coin at our disposal. For this case we
construct an optimal distributed test by appropriately combining local tests
that use local test statistics of the form $U^{\top}X^{(j)}$, where $U$ is a
public random vector.

The approach to finding the lower bound can be sumarized as follows. As a
first step, we lower bound the testing risk by a type of Bayes risk, where
$\mu$ is drawn from a prior such that it either belongs to the null hypothesis
of the alternative, as in for example [18]. This Bayes risk can be related to
the mutual information between the testing outcome and which hypothesis is
selected, akin to techniques common in tackling (distributed) estimation
problems through Fano-like inequalities in for example [33, 11]. In
particular, the tensorization property of the mutual information is used and
combined with a so called strong data processing inequality to quantify the
loss incurred in the distributed setup, similar to the approaches to
distributed estimation in [32, 8, 9].

Upon completion of this work, we came across the paper [1], which considers a
setting similar to ours and claims some partly overlapping results. There are
also important differences between the papers, however. Most importantly
perhaps, our proof strategy for the lower bound is rather different. As a
result our proof is arguably easier to verify and at least provides an
alternative to the approach proposed in [1]. Furthermore, the paper [1] does
not allow the number of machines (our $m$) to vary. Essentially, only the case
that $m=n$ is considered.

The remainder of the paper is organized as follows. In Section 2 we formally
describe the model and the distributed testing problem, and introduce
notations used throughout the paper. In Section 3 we present our main results.
We state the detection lower bound in Section 3.1, and we provide novel
distributed tests achieving the theoretical limits in Section 3.2. We provide
a short simulation study demonstrating the regime change observed in the
theoretical analysis in Section 4. The proofs for the distributed tests
achieving the minimax rate is given in Section 5, while the proofs of
corresponding (technical) lemmas are deferred to Sections 6-8.

##  2 Problem setting and notation

We assume we have $m$ local machines. For $j=1,\ldots,m$, we have an
observation $X^{(j)}$ at machine $j$, which satisfies

$X^{(j)}=\mu+\sqrt{\frac{m}{n}}Z^{(j)}.$

Here $\mu\in\mathbb{R}^{d}$ is the unknown signal of interest and
$Z^{(1)},\ldots,Z^{(m)}$ are independent, $N_{d}(0,I_{d})$-distributed
vectors. We allow both the dimension $d=d_{n}$ and the number of machines
$m=m_{n}$ to depend on the overal signal-to-noise ratio, or “sample size” $n$.
In fact, the interesting cases (from an asymptotic perspective) are the ones
where both $d$ and $m$ are tending to infinity with $n$. Nevertheless, we do
not restrict ourselves to this asymptotic regime and cover the finite $m$ and
$d$ cases as well.

We are interested in distributed tests for the hypotheses

$H_{0}:\mu=0,\qquad\text{against}\qquad H_{\rho}:\|\mu\|\geq\rho,$ (2)

for $\rho>0$. We consider public coin protocols, where each machine has access
to a shared random vector $U$, which is independent of the observations
$X^{(1)},\ldots,X^{(m)}$. Each local machine $j$ carries out a local test.
Using the local data $X^{(j)}$ and the public coin $U$ it produces a binary,
$\\{0,1\\}$-valued outcome $T^{(j)}$. The outcomes $T^{(1)},\ldots,T^{(m)}$ of
the local tests are transmitted to a central machine where they are aggregated
into a global test, described by a $\\{0,1\\}$-valued variable $T_{dist}$.
Schematically, a distributed test looks as follows:

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

We denote the collection of all distributed tests of this form by
$\mathcal{T}_{dist}$.

The testing error, or risk of a distributed test $T_{dist}$, is defined as
usual by

$\mathcal{R}(H_{\rho},T_{dist})=P_{0}\left(T_{dist}=1\right)+\underset{\|\mu\|\geq\rho}{\sup}P_{\mu}\left(T_{dist}=0\right),$
(4)

i.e. as the sum of the type one and type two errors of the test. (Here, and
elsewhere, we denote by $P_{\mu}$ the underlying distribution assuming that
$\mu$ is the true signal.) Uniform lower bounds for this risk express the
impossibility of detecting a signal of size $\rho$. Indeed, fix a level
$\alpha\in(0,1)$. If $\rho>0$ is such that
$\mathcal{R}(H_{\rho},T_{dist})>\alpha$ for all
$T_{dist}\in\mathcal{T}_{dist}$, then it means that there exists no consistent
level-$\alpha$ test for testing $H_{0}$ against $H_{\rho}$. In other words, no
distributed test of level $\alpha$ is able to detect all signals that are
larger than $\rho$ in Euclidean norm.

Our aim is to find the detection threshold, i.e. the cut-off $\rho_{dist}$
such that no consistent level-$\alpha$ test exists if $\rho<\rho_{dist}$ and
at least one consistent level-$\alpha$ test exists if $\rho\geq\rho_{dist}$.
We will show that, up to constants depending on the chosen level $\alpha$, the
detection threshold is given by

$\rho^{2}_{dist}\asymp\min\Big{\\{}\frac{\sqrt{dm}}{n},\frac{d}{{n}}\Big{\\}}.$

Moreover, we exhibit optimal tests for the case $\rho\geq\rho_{dist}$.

###  2.1 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. The Euclidean norm of a
vector $v\in\mathbb{R}^{d}$ is denoted by $\|\cdot\|$. For absolutely
continuous probability measures $P\ll Q$, we denote by
$D_{KL}(P\|Q)=\int\log\frac{dP}{dQ}dP$ their Kullback-Leibler divergence.

##  3 Main results

###  3.1 Lower bound for the detection threshold

The following theorem establishes the detection threshold. Its proof is
described in the remainder of the subsection.

######  Theorem 1.

Fix $\alpha\in(0,1)$ and suppose that

$\rho^{2}<c_{\alpha}\frac{\sqrt{d(m\wedge d)}}{n}$ (5)

for ${c_{\alpha}\leq({1-\alpha})^{2}/384}$. Then,

$\underset{T\in\mathcal{T}_{dist}}{\inf}\;\mathcal{R}(H_{\rho},T)>\alpha,$

where infimum is over all distributed tests $T\in\mathcal{T}_{dist}$ given in
(3).

The result tells us that if (5) holds, there does not exist a consistent test
in $\mathcal{T}_{dist}$ of level $\alpha\in(0,1)$ for the hypotheses (2). In
other words, no distributed test can detect all signals of size $\rho$. It
should be noted that we did not optimize for the value of the constant
$c_{\alpha}$ and the statement is likely to be still true for larger values of
$c_{\alpha}$.

The proof of the theorem relies on three key lemmas, which we state below
after introducing some necessary notations. As a first step, we use the basic
fact that the supremum of the probability of a type two error of a test can be
lower bounded by a Bayesian type two error, i.e. for any prior distribution
$\Pi$ supported on $H_{\rho}$

$\underset{\mu\in
H_{\rho}}{\sup}P_{\mu}\left(T=0\right)\geq\int_{H_{\rho}}P_{\mu}\left(T=0\right)\,d\Pi(\mu).$

To further lower bound the risk we construct an appropriate Markov chain and
relate the testing problem to an information transfer problem through the
chain. Consider $V\sim\text{Ber}(1/2)$, i.e. a $V$ is $0$ or $1$, each with
probability $1/2$, independent of the public coin random vector $U$, such that
the random vectors $X^{(j)}|(V=0)$, $j=1,\dots,m$ follow (1) with $\mu=0$ and
$X^{(j)}|(V=1)$ follows a Gaussian mixture $P_{\Pi}$ defined as
$P_{\Pi}(A)=\int P_{\mu}(A)\,d\Pi(\mu)$ for all Borel sets
$A\subset\mathbb{R}^{d}$. Let us denote by ${\mathbb{P}}$ the joint
probability measure describing the corresponding Markov dynamics

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

We then have that for any distributed test $T$,

$\mathcal{R}(H_{\rho},T)\geq{\mathbb{P}}(T=1|V=0)+{\mathbb{P}}(T=0|V=1)=2{\mathbb{P}}(T\neq
V).$ (7)

The right hand side of (7) can be further bounded from below using the _mutual
information_ between $T$ and $V$ in the chain (6), defined by

$I_{\Pi}(V,T)=D_{KL}\left({\mathbb{P}}^{V\times
T}\,\|\;{\mathbb{P}}^{V}\times{\mathbb{P}}^{T}\right),$

where ${\mathbb{P}}^{V}$, ${\mathbb{P}}^{T}$ and ${\mathbb{P}}^{V\times T}$
denote marginal- and joint distributions of $V$ and $T$, and the subscript
$\Pi$ is used to indicate the dependence on the prior $\Pi$. Informally, the
mutual information measures how much knowing $T$ reduces uncertainty about $V$
and vice versa. The lower bound based on the mutual information is given in
the following lemma. The proof of the lemma is deferred to Section 7.1.

######  Lemma 1.

Let $\Pi$ be a prior on $H_{\rho}$ and consider the dynamics (6). We have

$\underset{T\in\mathcal{T}_{dist}}{\inf}\;\mathcal{R}(H_{\rho},T)\geq
1-\sqrt{2I_{\Pi}(V,T)}.$

In view of the usual data processing inequality we have $I_{\Pi}(V,T)\leq
I_{\Pi}(V,(T^{(1)},\dots,T^{(m)}))$. The following lemma asserts that, up to
an additional term, this further tensorizes conditional on the public coin
randomness.

######  Lemma 2.

Consider the dynamics (6). We have

$I_{\Pi}(V,(T^{(1)},\dots,T^{(m)}))\leq\underset{j=1}{\overset{m}{\sum}}I_{\Pi}(V,T^{(j)}|U)+{\underset{j=1}{\overset{m}{\sum}}I_{\Pi}(\mu,T^{(j)}|U,V)}.$
(8)

The proof of this lemma is given in Section 7.2. This bound, combined with
Lemma 1, allows us to break down the difficulty of the ’global’ testing
problem in terms of the difficult of the $m$ ’local’ testing problems,
captured by the quantities $I_{\Pi}(V,T^{(j)}|U)$. These conditional local
mutual informations quantify the capacity of the local tests to distinguish a
signal drawn from the prior $\Pi$ from the zero signal. The second sum in the
display of the lemma captures dependency between the transcripts and the prior
draw $\mu\sim\Pi$. Essentially, it captures how well the signal can be
_estimated_ by the local tests.

We now discuss the choice of prior distribution $\Pi$. Let us set
$\epsilon=\rho/\sqrt{d}$, let $R$ be a $d$-dimensional vector of independent
Rademacher random variables, and define the prior $\Pi$ as the distribution of
$\epsilon R$. Note that $\Pi$ has support contained in $H_{\rho}$. (Such
choices are typically considered as least favorable priors supported on
signals that are difficult to detect, see for instance Section 3.2 of [18].)

Since $V$, $\mu$ and $X^{(j)}$ are independent of $U$, conditioning on $U$
does not distrupt the Markov chain property: we have the chain $V|U\to\mu|U\to
X^{(j)}|U\to T^{(j)}|U$. Consequently, the “estimation term”
$I_{\Pi}(\mu,T^{(j)}|U,V)$ can be handled using strong data processing
techniques employed in distributed estimation, see for example Lemma 11 in
[9]. For completeness, we adopted the aforementioned lemma for the above
choice of prior distribution in the form of Lemma 9 in the appendix, which
yields that $I_{\Pi}(\mu,T^{(j)}|U,V)\leq
128\frac{n\rho^{2}}{dm}I_{\Pi}(X^{(j)},T^{(j)}|U,V=1)$. Using that $T^{(j)}$
is binary valued, we obtain that the second term in (8) is bounded above by
$128\frac{n\rho^{2}}{d}$.

The loss of information about $V$ resulting from the compression of
$X^{(j)}|U$ into $T^{(j)}|U$ in this Markov chain is quantified by Lemma 3
below. The lemma comes in the form of a strong data processing inequality for
the testing problem and forms the crux of the proof of the lower bound. It
captures the difficulty of the local testing problem in terms of $n$, $m$, $d$
and $\rho$.

######  Lemma 3 (Public Coin Strong Data Processing Inequality).

With $\Pi$ as defined above we have

$I_{\Pi}(V,T^{(j)}|U)\leq(48\beta\wedge 1)I_{\Pi}(X^{(j)},T^{(j)}|U),$

where

$\beta=\begin{cases}\frac{n^{2}\rho^{4}}{dm^{2}}\;\;\;\text{ if
}\frac{m}{n\rho^{2}}<1/2,\\\ \frac{2n\rho^{2}}{dm}\;\;\;\text{ if
}\frac{m}{n\rho^{2}}\geq 1/2.\end{cases}$ (9)

We give the proof of the lemma in Section 7.3. By combining the information
theoretic inequalities above with the fact that $I(X^{(j)},T^{(j)}|U)\leq
H(T^{(j)}|U)\leq 1$, which is true because $T^{(j)}$ is a binary variable, we
get that

$I_{\Pi}(V,T)\leq\sum_{j=1}^{m}I_{\Pi}(V,T^{(j)}|U)+{\underset{j=1}{\overset{m}{\sum}}I_{\Pi}(\mu,T^{(j)}|U,V)\leq
48\beta m+128\frac{n\rho^{2}}{d}}.$

Therefore, in view of Lemma 1,

$\mathcal{R}(H_{\rho},T)\geq
1-4\sqrt{6\frac{n\rho^{2}}{d}{\left(\max\left\\{\frac{n\rho^{2}}{m},2\right\\}+8/3\right)}}.$

For $\rho$ satisfying (5), the right-hand side is bounded from below by
$\alpha$ for an arbitrary distributed test $T\in\mathcal{T}_{dist}$.

###  3.2 Optimal tests attaining the lower bound

In this section, we exhibit a distributed testing procedure that is optimal in
the sense that it attains the lower bound of Theorem 1. More precisely, we
show that if $\rho^{2}$ is larger than a multiple of the right-hand side of
(5), there exists a distributed test for $H_{0}$ against $H_{\rho}$ with risk
bounded by a chosen level $\alpha\in(0,1)$. Summarising, we have the following
theorem, complementing the lower bound of Theorem 1.

######  Theorem 2.

Fix $\alpha\in(0,1)$ and suppose that

$\rho^{2}\geq C_{\alpha}\frac{\sqrt{d(m\wedge d)}}{n}$ (10)

for $C_{\alpha}>0$ a constant depending only on $\alpha$ as given in (15).
Then there exists a test $T\in\mathcal{T}_{dist}$ such that
$\mathcal{R}(H_{\rho},T)\leq\alpha$.

We prove the theorem by constructing three concrete distributed tests, for
three different ranges of $m$. We outline the construction of these tests in
this section. The detailed verification that they are consistent at the level
$\alpha$ for testing $H_{0}$ against $H_{\rho}$ in their respective ranges is
deferred to Section 5.

First assume that the number of machines is large enough, but does not exceed
the dimension $d$, i.e. $M_{\alpha}\leq m\leq d$, for a large enough constant
$M_{\alpha}>0$ given in (15). In this case, Theorem 1 asserts that the
detection lower bound for $\rho$ is a multiple of $(dm)^{1/4}/n^{1/2}$. We
propose the following distributed test that is able to detect signals with
Euclidian norm of that order if $M_{\alpha}\leq m\leq d$. In this case no
public coin is needed. In this setting we first compute the local test
statistic $S_{m\leq d}^{(j)}=(n/m)\|X^{(j)}\|^{2}$ at every machine $j$. Under
the null hypothesis, $S_{m\leq d}^{(j)}$ follows a chi-square distribution
with $d$ degrees of freedom, i.e. $S_{m\leq d}^{(j)}\sim\chi^{2}_{d}$. Then
for every $j$ we consider the randomized test $T_{m\leq d}^{(j)}$ using
Bernoulli random variables

$T_{m\leq d}^{(j)}|S_{m\leq
d}^{(j)}\sim\text{Ber}\left(F_{\chi^{2}_{d}}\left(S_{m\leq
d}^{(j)}\right)\right),$

where $F_{\chi^{2}_{d}}$ denotes the distribution function of $\chi^{2}_{d}$.
Under the null hypothesis the $T_{m\leq d}^{(j)}$ are independent and
$\text{Ber}(1/2)$. At the central machines we combine the local test in a
global test $T_{m\leq d}\in\mathcal{T}_{dist}$ by setting

$T_{m\leq d}=\text{1}\left\\{\left|\underset{j=1}{\overset{m}{\sum}}(T_{m\leq
d}^{(j)}-1/2)\right|\geq\sqrt{m}\bar{\kappa}_{\alpha}\right\\},$ (11)

with $\bar{\kappa}_{\alpha}^{2}=3\log\left(4/\alpha\right)$. By a standard
Chernoff bound, the type one error of this test is bounded by $\alpha/2$ for
$m$ large enough. In Section 5.1, we prove that the same is true for the type
two error if $\|\rho\|^{2}\geq C_{\alpha}\sqrt{dm}/n$. as posed by Theorem

Next we assume that $m\geq d\vee M_{\alpha}$, in which case the detection
lower bound for $\rho$ is a multiple of $\sqrt{d/n}$. When $m/d\to\infty$,
tests based on the statistics $S_{m\leq d}^{(j)}$ cannot reach the detection
lower bound anymore as can be observed by inspection of the variance of (18),
or through Theorem 16 in [1]. We propose a novel distributed test using a
public coin. Specifically, we assume all machine have access to a vector
$U=(U_{1},\ldots,U_{d})$ of independent standard normal random variables. For
$j=1,\ldots,m$ we compute the local test statistics $S_{m\geq
d}^{(j)}=\sqrt{\frac{n}{md}}U^{T}X^{(j)}$ and the corresponding local tests

$T_{m\geq d}^{(j)}=\text{1}\left\\{S_{m\geq d}^{(j)}\geq 0\right\\}.$

Then we aggregate these local tests in the central machine to a distributed
test $T_{m\geq d}\in\mathcal{T}_{dist}$ by defining

$T_{m\geq d}=\text{1}\left\\{\left|\underset{j=1}{\overset{m}{\sum}}(T_{m\geq
d}^{(j)}-1/2)\right|\geq\sqrt{m}\tilde{\kappa}_{\alpha}\right\\},$ (12)

with $\tilde{\kappa}_{\alpha}^{2}=(1/3)\log\left(16/\alpha\right)$. In Section
5.2 we prove that this test satisfies the required error bound if
$\rho^{2}\geq C_{\alpha}d/n$.

Finally, we consider the case $m\leq M_{\alpha}$ for completeness. We have to
treat it separately for technical reasons, although in practice we would
probably simply use the first test above for all cases $m\leq d$. To achieve
optimality in this case we can simply choose a single machine and conduct the
hypothesis test we would use in the classical, non-distributed setting.
Specifically, we can for instance use as global test $T_{m\asymp
1}\in\mathcal{T}_{dist}$ the test given by

$T_{m\asymp
1}=\text{1}\left\\{\frac{n}{\sqrt{d}m}\|X^{(1)}\|^{2}-\sqrt{d}\geq\kappa_{\alpha}\right\\},$
(13)

with $\kappa_{\alpha}=2/\sqrt{\alpha}$. See Section 5.3 for details.

##  4 Simulation experiments

In this section we investigate the performance of the tests $T_{m\leq d}$ and
$T_{m\geq d}$ that were proposed in the preceding section, in particular with
regards to the “elbow effect” when $m\simeq d$ that we observed in our
theoretical results. We visualize the performance using two different
simulation experiments.

In the first experiment we consider two fixed choices of $m,n$ and $d$, one
with $m<d$ and one with $m>d$. We simulate data with a signal with increasing
strength $\rho$ and then assess the performance of the tests by computing the
“true positive rate” (TPR), i.e. the fraction of the simulations in which they
correctly detect the signal.

For the second experiment we also consider two scenarios, one with $m\lesssim
d$ and one with $m\gtrsim d$. But now we fix the signal strength $\rho$ a
little above the detection limit in both cases and investigate how the
performance of the tests depends on the total signal-to-noise ratio, or sample
size $n$.

###  4.1 First experiment

Figure 4.1: The horizontal axes correspond to the Euclidian norm
$\|\mu\|=\rho$ of the signal (14) used in the simulations. In the plot on the
left we have $m=50$ and $d=500$, on the right we have $m=5000$ and $d=5$. For
each $\rho$ in a grid between $0$ and $1$, $100$ datasets were simulated. The
solid lines give the TPR, i.e. the fraction of the $100$ runs in which the
tests correctly detected the signal. The red lines correspond to $T_{m\leq
d}$, the blue lines to $T_{m\geq d}$.

In the first simulation we consider fixed values for $n$, $m$ and $d$ and we
simulate data in which we let the strength $\|\mu\|$ of the unobserved signal
vary between $0$ and $1$. We investigate how well each of the distributed
tests manages to correctly reject the null hypothesis, i.e. detect the signal.

In Figure 4.1, we consider two different scenarios. In both scenarios we
choose $n=10^{4}$ and we have specified the rejection criterion for both tests
such that they have a type one error probability of less than $\alpha=0.05$.
The signal $\mu$ is drawn according to

$\mu=\frac{\rho}{\sqrt{d}}R,$ (14)

where $R$ is a vector of independent Rademacher random variables, and we let
the signal strength $\rho=\|\mu\|$ vary from $0$ to $1$.

In the $m<d$ scenario corresponding to the plot on the left-hand side in
Figure 4.1, we see that the test $T_{m\leq d}$ outperforms the public coin
test $T_{m\geq d}$, in accordance with our theoretical results. In the $m>d$
scenario on the right-hand side we see that the test $T_{m\geq d}$ detects the
presence of the signal much earlier than the test $T_{m\leq d}$.

###  4.2 Second experiment

Figure 4.2: The horizontal axes corresponds to the total sample size $n$. In
the plot on the left we have $d=n^{{2}/{3}}$, $m=500$, and
$\rho={\log(d)(dm)^{1/4}}/{\sqrt{n}}$. On the right, $m=n/10$, $d=5$ and
$\rho=2\log(m)\sqrt{{d}/{n}}$. For every $n$ in a grid ranging from $1$ to
$3\cdot 10^{4}$, $100$ datasets were simulated. The solid lines give the TPR,
i.e. the fraction of the $100$ runs in which the tests correctly detected the
signal. The red lines correspond to $T_{m\leq d}$, the blue lines to $T_{m\geq
d}$.

In the second experiment we also consider two scenarios.

The first scenario corresponds to a situation in which a fixed number of
machines $m$ receive more observations as $n$ increases, but the dimension of
the signal increases as well. Specifically, we take $d=n^{\frac{2}{3}}$ and
$m=500$. We set the signal strength slightly above the detection limit for
this case, namely $\rho=\log(d)(dm)^{1/4}/\sqrt{n}$. Note that $\rho\to 0$ as
$n\to\infty$. In view of the theory we expect that the test $T_{m\leq d}$
detects the signal consistently, whereas the public coin test $T_{m\geq d}$
should have a worse performance, since it requires that
$\rho\gtrsim\sqrt{d/n}$.

In the second scenario we take $m=n/10$ and $d=5$ and set
$\rho=2\log(m)\sqrt{d/n}$, which is again slightly above the detecting limit.
This corresponds to the situation in which for each $10$ additional
observations a new machine is added, whilst the dimension of the signal
remains fixed. In this case we also have $\rho\to 0$ as $n\to\infty$. We
expect that for large $n$ the test $T_{m\leq d}$ will fail to consistently
detect the signal, as it requires $\rho\gtrsim{(md)^{1/4}}/{\sqrt{n}}$ to do
so.

The resulting plots can be found in Figure 4.2. The results are again in
accordance with our theoretical findings. We note in particular that the
public coin test $T_{m\geq d}$ is a suitable choice in the realistic scenario
where the number of machines $m$ scales with $n$, so batches of additional
observations are distributed over additional machines, while the dimension of
the signal remains fixed or at least relatively small compared to the number
of observations.

##  5 Proof of Theorem 2

Let $\alpha\in(0,1)$ be given, recall that
$\bar{\kappa}_{\alpha}^{2}=3\log\left(4/\alpha\right)$,
$\tilde{\kappa}_{\alpha}^{2}=(1/3)\log\left(16/\alpha\right)$,
$\kappa_{\alpha}^{2}=4/\alpha$, and set

$\displaystyle M_{\alpha}$
$\displaystyle:=\max\left\\{(2^{5}5\bar{\kappa}_{\alpha})^{2},\bar{D},36\tilde{\kappa}_{\alpha}^{2},4e^{2}\pi\tilde{\kappa}_{\alpha}^{2}\alpha^{1/2}\right\\},$
$\displaystyle C_{\alpha}$
$\displaystyle:=\max\left\\{2^{4}M_{\alpha}^{2}\kappa_{\alpha}^{2},2(1+\sqrt{2})\kappa_{\alpha}M_{\alpha},80\bar{\kappa}_{\alpha},2^{12}e^{2}\tilde{\kappa}_{\alpha}^{2}\alpha^{-5/2}\right\\},$
(15)

where $\bar{D}$ is defined in Lemma 4. Then we show below that for all
$d,m,n\in{\mathbb{N}}$ at least one of the three distributed tests $T_{m\leq
d},T_{m\geq d},T_{m\asymp 1},$ given in (13)-(12), achieves uniform
consistency at level $\alpha$, i.e.

$\mathcal{R}(H_{\rho},T)\leq\alpha,$ (16)

for some $T\in\\{T_{m\asymp 1},T_{m\leq d},T_{m\geq d}\\}$.

We distinguish three regimes in view of the interplay of $m$ and $d$, and show
in the following subsections that the corresponding tests reach uniform
consistency:

  * •

Case 1: $M_{\alpha}<m\leq d$.

  * •

Case 2: $M_{\alpha}\vee d<m$.

  * •

Case 3: $m\leq M_{\alpha}$.

with corresponding tests $T_{m\leq d},T_{m\geq d},T_{m\asymp 1}$,
respectively.

###  5.1 Case 1: $M_{\alpha}<m\leq d$

In view of Chernoff’s bound, see Lemma 6, for $m>4\bar{\kappa}_{\alpha}^{2}$,

$\displaystyle P_{0}\left(T_{m\leq d}=1\right)$
$\displaystyle=P_{0}\left(\sum_{j=1}^{m}(T_{m\leq
d}^{(j)}-1/2)\geq\bar{\kappa}_{\alpha}/\sqrt{m}\right)$ $\displaystyle\leq
2\exp\left(-2\bar{\kappa}_{\alpha}^{2}/3\right)<\alpha/2.$ (17)

We now turn to bounding the type II error probability. For arbitrary
$\mu=(\mu_{1},\dots,\mu_{d})\in H_{\rho}$,

$S^{(j)}_{m\leq
d}=\underset{i=1}{\overset{d}{\sum}}\left(\sqrt{\frac{n}{m}}\mu_{i}+Z_{i}^{(j)}\right)^{2}$
(18)

with $Z_{i}^{(j)}\stackrel{{\scriptstyle iid}}{{\sim}}N(0,1)$, follows a
noncentral chi-square distribution with $d$ degrees of freedom and
noncentrality parameter $\delta:=(n/m)\|\mu\|_{2}^{2}$, i.e. $S^{(j)}_{m\leq
d}\stackrel{{\scriptstyle ind}}{{\sim}}\chi_{d}^{2}(\delta)$.

Let us take independent random variables
$V_{d}^{\delta}\sim\chi_{d}^{2}(\delta)$ and $U_{d}\sim\chi_{d}^{2}(0)$ . Then
in view of Lemma 4, for $c>1/40$ and for all $d\geq\bar{D}$,

$\displaystyle E_{\mu}(F_{\chi^{2}_{d}}(S^{(j)}_{m\leq
d}))=\text{Pr}\left(V^{\delta}_{d}\geq
U_{d}\right)\geq\frac{1}{2}+c\left(\frac{\delta}{\sqrt{d}}\wedge\frac{1}{2}\right),$

where $E_{\mu}$ is the expectation corresponding to $P_{\mu}$. This further
yields

$\displaystyle P_{\mu}$
$\displaystyle\left(\left|\underset{j=1}{\overset{m}{\sum}}\left[T^{(j)}_{m\leq
d}-\frac{1}{2}\right]\right|\leq\sqrt{m}\bar{\kappa}_{\alpha}\right)$
$\displaystyle\leq
P_{\mu}\left(\underset{j=1}{\overset{m}{\sum}}\left[T^{(j)}_{m\leq
d}-E_{\mu}(F_{\chi^{2}_{d}}(S^{(j)}_{m\leq
d}))\right]\leq\sqrt{m}\bar{\kappa}_{\alpha}\left(1-\frac{c\sqrt{m}}{\bar{\kappa}_{\alpha}}\left(\frac{\delta}{\sqrt{d}}\wedge\frac{1}{2}\right)\right)\right).$

In view of Chernoff’s bound and the inequality
$E_{\mu}(F_{\chi^{2}_{d}}(T^{(j)}_{m\leq d}))\leq 1$, this is further bounded
by $2\exp(-\bar{\kappa}_{\alpha}^{2}/3)=\alpha/2$, given that

$\frac{c\sqrt{m}}{\bar{\kappa}_{\alpha}}\left(\frac{\delta}{\sqrt{d}}\wedge\frac{1}{2}\right)\geq
2.$ (19)

This last inequality follows from the assumption (10)

$\displaystyle\sqrt{\frac{m}{d}}\delta=\frac{n\|\mu\|_{2}^{2}}{\sqrt{dm}}\geq
C_{\alpha}\geq 2\bar{\kappa}_{\alpha}/c\quad\text{and}\quad
m>16\bar{\kappa}_{\alpha}^{2}/c^{2}.$

###  5.2 Case 2: $M_{\alpha}\vee d<m$

For the choice and $m>4\tilde{\kappa}_{\alpha}^{2}$ the same bound as in (17)
holds for $P_{0}\left(T_{m\geq d}=1\right)$.

For the type II error, consider $\mu=(\mu_{1},\dots,\mu_{d})\in H_{\rho}$.
Define for $\eta>0$, $\nu>0$ the events
$D_{\eta}:=\\{\|U\|_{2}/\sqrt{d}\leq\eta\\}$ and

$A_{\nu,\eta}:=\left\\{\frac{\sqrt{n}}{\sqrt{d}}\underset{i=1}{\overset{d}{\sum}}\mu_{i}U_{i}>\nu\right\\}\cap
D_{\eta},\;B_{\nu,\eta}:=\left\\{\frac{\sqrt{n}}{\sqrt{d}}\underset{i=1}{\overset{d}{\sum}}\mu_{i}U_{i}<-\nu\right\\}\cap
D_{\eta},$

where $U=(U_{1},\dots,U_{d})\sim N(0,I_{d})$ is the public coin random vector,
whose probability distribution we shall denote by $Q$. We set

$\displaystyle\eta=4\alpha^{-1/2}\quad\text{and}\quad\nu=4e\sqrt{2\pi}\tilde{\kappa}_{\alpha}\sqrt{\eta},$
(20)

and note that $C_{\alpha}\geq 2^{7}\nu^{2}/(\pi\alpha^{2})$.

Then the type II error is bounded from above as

$\displaystyle E_{Q}P_{\mu}\left(T_{m\geq d}=0|U=u\right)$
$\displaystyle\leq\int_{A_{\nu,\eta}}P_{\mu}\left(\underset{j=1}{\overset{m}{\sum}}(T^{(j)}_{m\geq
d}-1/2)\leq\sqrt{m}\tilde{\kappa}_{\alpha}\bigg{|}U=u\right)dQ(u)$
$\displaystyle+\int_{B_{\nu,\eta}}P_{\mu}\left(\underset{j=1}{\overset{m}{\sum}}(T^{(j)}_{m\geq
d}-1/2)\geq-\sqrt{m}\tilde{\kappa}_{\alpha}\bigg{|}U=u\right)dQ(u)$
$\displaystyle\qquad+Q(A^{c}_{\nu,\eta}\cap B_{\nu,\eta}^{c}).$ (21)

We show below that each of the first two terms on the right hand side are
bounded by $\alpha/8$ and the third term by $\alpha/4$, resulting our
statement.

First we deal with the third term in (21). Since

$\frac{\sqrt{n}}{\sqrt{d}}\underset{i=1}{\overset{d}{\sum}}\mu_{i}U_{i}\sim\mathcal{N}(0,\frac{n}{d}\|\mu\|_{2}^{2}),$

the set $(A_{\nu,\eta}\cup B_{\nu,\eta})^{c}=A_{\nu,\eta}^{c}\cap
B_{\nu,\eta}^{c}$, in view of Chebyshev’s inequality, assumption (10), and
definitions (20), satisfies that

$\displaystyle Q(A_{\nu,\eta}^{c}\cap B_{\nu,\eta}^{c})$
$\displaystyle\leq\text{Pr}\left(\sqrt{\frac{n}{d}}\|\mu\|_{2}|Z|\leq\nu\right)+Q(D_{\eta}^{c})\leq\frac{2\nu}{\sqrt{2\pi
C_{\alpha}}}+\frac{2}{\eta^{2}}\leq\alpha/4.$

where $Z\sim N(0,1)$.

Next we deal with the first term on the right hand side of (21). For $u\in
A_{\nu,\eta}$, we have $\|u\|_{2}/\sqrt{d}\leq\eta$, hence for
$m\geq\nu^{2}/(2\eta^{2})$,

$\displaystyle\text{Pr}\left(-\frac{\nu}{\sqrt{m}}<\frac{1}{\sqrt{d}}\underset{i=1}{\overset{d}{\sum}}u_{i}Z_{i}\leq
0\right)$ $\displaystyle\geq\text{Pr}\left(-\frac{\nu}{\sqrt{m}\eta}<Z\leq
0\right)$
$\displaystyle\geq\frac{e^{-\frac{\nu^{2}}{2m\eta^{2}}}}{\sqrt{2\pi}}\frac{\nu}{\sqrt{m}\eta}\geq
c^{\prime}\frac{\nu}{\sqrt{m}\eta},$

where $Z,Z_{1},\dots,Z_{d}\stackrel{{\scriptstyle iid}}{{\sim}}N(0,1)$ and
$c^{\prime}=(e\sqrt{2\pi})^{-1}$. Therefore,

$\displaystyle P_{\mu}\left(S_{m\geq d}^{(j)}\geq 0\bigg{|}U=u\right)$
$\displaystyle=\text{Pr}\left(\frac{\sqrt{n}}{\sqrt{dm}}\underset{i=1}{\overset{d}{\sum}}\mu_{i}u_{i}+\frac{1}{\sqrt{d}}\underset{i=1}{\overset{d}{\sum}}u_{i}Z_{i}\geq
0\right)$
$\displaystyle\geq\text{Pr}\left(\frac{\nu}{\sqrt{m}}+\frac{1}{\sqrt{d}}\underset{i=1}{\overset{d}{\sum}}u_{i}Z_{i}\geq
0\right)$
$\displaystyle=\frac{1}{2}+\text{Pr}\left(-\frac{\nu}{\sqrt{m}}<\frac{1}{\sqrt{d}}\underset{i=1}{\overset{d}{\sum}}u_{i}Z_{i}\leq
0\right)$ $\displaystyle\geq\frac{1}{2}+c^{\prime}\frac{\nu}{\sqrt{\eta m}}.$

Then in view of Chernoff’s bound

$\displaystyle\int_{A_{\nu}}$ $\displaystyle
P_{\mu}\left(\underset{j=1}{\overset{m}{\sum}}(T^{(j)}_{m\geq
d}-1/2)\leq\sqrt{m}\tilde{\kappa}_{\alpha}\bigg{|}U=u\right)dQ(u)$
$\displaystyle\leq\int_{A_{\nu}}P_{\mu}\left(\underset{j=1}{\overset{m}{\sum}}\left[T^{(j)}_{m\geq
d}-E_{\mu}(T^{(j)}_{m\geq
d}|U=u)\right]\leq\sqrt{m}\big{(}\tilde{\kappa}_{\alpha}-\frac{c^{\prime}\nu}{\sqrt{\eta}}\big{)}\bigg{|}U=u\right)dQ(u).$

Since by definition (20)
$\tilde{\kappa}_{\alpha}-c^{\prime}\nu/\sqrt{\eta}=-3\tilde{\kappa}_{\alpha}$,
in view of Chernoff’s bound (Lemma 6), for $36\tilde{\kappa}_{\alpha}^{2}<m$
the preceding display is further bounded by
$2e^{-3\tilde{\kappa}_{\alpha}^{2}}=\alpha/8$.

We can deal with the second term on the right hand side of (21) similarly.
First, we obtain for $u\in B_{\nu,\eta}$ that

$P_{\mu}\left(S_{m\geq d}^{(j)}\geq 0\bigg{|}U=u\right)\leq
1/2-c^{\prime}\frac{\nu}{\sqrt{\eta m}}.$

And then we can derive as above that

$E_{Q}\text{1}_{B_{\nu}}P_{\mu}\left(\underset{j=1}{\overset{m}{\sum}}\left[T^{(j)}_{m\geq
d}-\frac{1}{2}\right]\geq-\sqrt{m}\tilde{\kappa}_{\alpha}\right)\leq\alpha/8,$

concluding the proof of case 2.

###  5.3 Case 3: $m\leq M_{\alpha}$

Finally, for completeness, we deal with the case when the number of machines
is limited and we are back bascially to the single server, centralized case
from a minimax rate point of view.

Under the null hypothesis, $(n/m)\|X^{(1)}\|_{2}^{2}$ follows a chi-square
distribution with $d$ degrees of freedom, so by Chebyshev’s inequality

$P_{0}\left(T_{m\asymp 1}=1\right)\leq 2/\kappa_{\alpha}^{2}=\alpha/2.$

For any $\mu\in H_{\rho}$, it holds that

$\displaystyle P_{\mu}\big{(}\frac{n}{\sqrt{d}m}$
$\displaystyle\|X^{(1)}\|_{2}^{2}-\sqrt{d}\leq\kappa_{\alpha}\big{)}$
$\displaystyle=\text{Pr}\left(\left|\frac{n}{\sqrt{d}m}\|\mu\|_{2}^{2}+2d^{-1/2}\underset{i=1}{\overset{d}{\sum}}\mu_{i}Z_{i}+d^{-1/2}\underset{i=1}{\overset{d}{\sum}}(Z_{i}^{2}-1)\right|\leq\kappa_{\alpha}\right)$

where $Z_{i}\stackrel{{\scriptstyle iid}}{{\sim}}N(0,1)$, $i=1,...,d$. By the
reverse triangle inequality, we can bound the previous probability with

$\displaystyle\text{Pr}\left(\left|2d^{-1/2}\underset{i=1}{\overset{d}{\sum}}\mu_{i}Z_{i}\right|\geq\frac{n\|\mu\|_{2}^{2}}{2\sqrt{d}m}\right)+\text{Pr}\left(\left|d^{-1/2}\underset{i=1}{\overset{d}{\sum}}(Z_{i}^{2}-1)\right|\geq\frac{n\|\mu\|_{2}^{2}}{2\sqrt{d}m}-\kappa_{\alpha}\right).$

In view of Chebyshev’s inequality and $\|\mu\|_{2}^{2}\geq\rho^{2}\geq
C_{\alpha}\sqrt{d}/n$,

$\text{Pr}\left(\left|2d^{-1/2}\underset{i=1}{\overset{d}{\sum}}\mu_{i}Z_{i}\right|\geq\frac{n\|\mu\|_{2}^{2}}{2\sqrt{d}m}\right)\leq\frac{16m^{2}}{n^{2}\|\mu\|_{2}^{2}}\leq\frac{16m^{2}}{C_{\alpha}}\leq\frac{\alpha}{4}$

for $C_{\alpha}\geq 2^{6}M_{\alpha}^{2}/\alpha$. Likewise, for
$C_{\alpha}\geq{2(1+\sqrt{2})\kappa_{\alpha}M_{\alpha}}$

$\frac{n\|\mu\|_{2}^{2}}{2\sqrt{d}m}-\kappa_{\alpha}\geq\sqrt{2}\kappa_{\alpha}$

and consequently, by applying again Chebyshev’s inequality, the second term is
bounded by

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

Hence we can conclude that for
$C_{\alpha}\geq\max\\{2^{6}M_{\alpha}^{2}/\alpha,{2(1+\sqrt{2})\kappa_{\alpha}M_{\alpha}}\\}$,

$P_{\mu}\big{(}T_{m\asymp 1}=0\big{)}\leq\alpha/2,$

concluding the proof of the theorem.

##  6 Lemmas for Theorem 2

In this section we collect the proofs of the lemmas used to derive the minimax
testing upper bound.

######  Lemma 4.

Let $U_{d}$ and $V_{d}^{\delta_{d}}$ be independent chi-square distributed
random variables with $d$ degree of freedom and non-centrality parameters zero
and $\delta_{d}>0$, respectively. Then for a universal $\bar{D}\in\mathbb{N}$,
not depending on $\delta_{d}$, we have for all $d\geq\bar{D}$ that

$\text{Pr}\left(V_{d}^{\delta_{d}}-U_{d}\geq
0\right)\geq\frac{1}{2}+\frac{1}{40}(\frac{{\delta_{d}}}{\sqrt{d}}\wedge\frac{1}{2}).$
(22)

###### Proof.

First note that the function
$\delta\mapsto\text{Pr}\left(V_{d}^{\delta}-U_{d}\geq 0\right)$ is monotone
increasing. Then

$\text{Pr}\left(V_{d}^{\delta_{d}}-U_{d}\geq
0\right)\geq\text{Pr}\left(V_{d}^{\delta_{d}\wedge\sqrt{d}/2}-U_{d}\geq
0\right),$

so without loss of generality we can assume that $\delta_{d}\leq\sqrt{d}/2$.

The density of $V_{d}^{\delta_{d}}$ is

$\underset{k=0}{\overset{\infty}{\sum}}\frac{e^{-{\delta_{d}}/2}\left({\delta_{d}}/2\right)^{k}}{k!}p_{d+2k},$

where $p_{k}$ denotes the $\chi^{2}_{k}$-density. By the independence of
$U_{d}$ and $V_{d}^{\delta_{d}}$,

$\displaystyle\text{Pr}\left(V_{d}^{\delta_{d}}-U_{d}\leq 0\right)$
$\displaystyle=\underset{k=0}{\overset{\infty}{\sum}}\frac{e^{-{\delta_{d}}/2}\left({\delta_{d}}/2\right)^{k}}{k!}\int_{\\{v-u\geq
0\\}}p_{d+2k}(v)p_{d}(u)d(v,u).$

Let $U_{d}^{\prime}\sim\chi^{2}_{d}$ and
$U_{2k}^{\prime\prime}\sim\chi^{2}_{2k}$ be independent from each other and
$U_{d}$. For any given $k\in{\mathbb{N}}$, we have

$\displaystyle\int_{\\{v-u\geq
0\\}}p_{d+2k}(v)p_{d}(u)d(v,u)=\text{Pr}\left(U_{d}-U_{d}^{\prime}\leq
U_{2k}^{\prime\prime}\right).$

For convenience let us introduce the notation
$W_{d}=(U_{d}-U_{d}^{\prime})/(2\sqrt{d})$. Conditioning and using
independence once more, the latter equals

$\int\text{Pr}\left(W_{d}\leq\frac{u}{2\sqrt{d}}\right)d{\mathbb{P}}_{U_{2k}^{\prime\prime}}(u)=\frac{1}{2}+\int\text{Pr}\left(0\leq
W_{d}\leq\frac{u}{2\sqrt{d}}\right)d{\mathbb{P}}_{U_{2k}^{\prime\prime}}(u).$

Since $U_{2k}^{\prime\prime}$ has a median larger than $2k/3$ and the map
$u\mapsto\text{Pr}\left(0\leq W_{d}\leq\frac{u}{2\sqrt{d}}\right)$ is
increasing, we have that the second term in the last display satisfies

$\displaystyle\int\text{Pr}\left(0\leq
W_{d}\leq\frac{u}{2\sqrt{d}}\right)p_{{2k}}(u)du$
$\displaystyle\geq\text{Pr}\left(0\leq
W_{d}\leq\frac{k}{3\sqrt{d}}\right)\int_{[\frac{2k}{3},\infty)}p_{{2k}}(u)du$
$\displaystyle\geq\frac{1}{2}\text{Pr}\left(0\leq
W_{d}\leq\frac{k}{3\sqrt{d}}\right).$

By combining the above inequalities we obtain that

$\text{Pr}\left(V_{d}^{\delta_{d}}-U_{d}\leq
0\right)\geq\frac{1}{2}+\frac{1}{2}\underset{k=0}{\overset{\infty}{\sum}}\frac{e^{-{\delta_{d}}/2}\left({\delta_{d}}/2\right)^{k}}{k!}\text{Pr}\left(0\leq
W_{d}\leq\frac{k}{3\sqrt{d}}\right).$ (23)

Assume now that $\delta_{d}\gtrsim 1$. Let $k_{d}$ be the largest integer such
that $k_{d}\leq 3\sqrt{d}$. We divide the sum on the right hand of the
preceding display to two parts, i.e. $k<k_{d}$ and $k\geq k_{d}$. By applying
Lemma 5 with $\varepsilon_{d}=k$, it holds that for $c_{0}=e^{-9/8}/6$,

$\displaystyle\underset{k=0}{\overset{k_{d}}{\sum}}\frac{e^{-{\delta_{d}}/2}\left({\delta_{d}}/2\right)^{k}}{k!}\text{Pr}\left(0\leq
W_{d}\leq\frac{k}{3\sqrt{d}}\right)$
$\displaystyle\geq\frac{c_{0}}{\sqrt{d}}\underset{k=1}{\overset{k_{d}}{\sum}}\frac{e^{-{\delta_{d}}/2}\left({\delta_{d}}/2\right)^{k}}{(k-1)!}$
$\displaystyle\geq\frac{c_{0}{\delta_{d}}}{2\sqrt{d}}\underset{k=0}{\overset{k_{d}-1}{\sum}}\frac{e^{-{\delta_{d}}/2}\left({\delta_{d}}/2\right)^{k}}{k!}.$

We have $\text{Pr}\left(0\leq W_{d}\leq 1\right)\stackrel{{\scriptstyle
d}}{{\to}}\text{Pr}\left(0\leq Z\leq 1\right)>1/3$, hence there exists a
$D_{1}\in\mathbb{N}$, such that for all $d\geq D_{1}$ we have
$\text{Pr}\left(0\leq W_{d}\leq 1\right)>1/3$. For $k>k_{d}$ we have
$k>3\sqrt{d}$, hence for all $d\geq D_{1}$,

$\displaystyle\underset{k>k_{d}}{\overset{\infty}{\sum}}\frac{e^{-{\delta_{d}}/2}\left({\delta_{d}}/2\right)^{k}}{k!}\text{Pr}\left(0\leq
W_{d}\leq\frac{k}{3\sqrt{d}}\right)$
$\displaystyle\geq\frac{c_{0}}{2}\underset{k>k_{d}}{\overset{\infty}{\sum}}\frac{e^{-{\delta_{d}}/2}\left({\delta_{d}}/2\right)^{k}}{k!}.$

Since ${\delta_{d}}/\sqrt{d}\leq 1/2$, we have for $d\geq D_{1}$,

$\displaystyle\frac{1}{2}\underset{k=0}{\overset{\infty}{\sum}}\frac{e^{-{\delta_{d}}/2}\left({\delta_{d}}/2\right)^{k}}{k!}\text{Pr}\left(0\leq
W_{d}\leq\frac{k}{3\sqrt{d}}\right)\geq\frac{c_{0}{\delta_{d}}}{2\sqrt{d}}(1-\frac{e^{-{\delta_{d}}/2}\left({\delta_{d}}/2\right)^{k_{d}}}{k_{d}!}).$

The proof is finished by showing that for large enough $d$ we have
$c_{0}/2-1/40>({\delta_{d}}/2)^{k_{d}}/k_{d}!>0$. Recalling that
$2\sqrt{d}\leq 3\sqrt{d}-1\leq k_{d}\leq 3\sqrt{d}$ and hence
$\delta_{d}\leq\sqrt{d}/2\leq\sqrt{d}/4$ we get in view of Stirling’s
inequality, that for some universal constant $C>0$

$\displaystyle\frac{\left({\delta_{d}}/2\right)^{k_{d}}}{k_{d}!}\leq\frac{\left(k_{d}/4\right)^{k_{d}}}{k_{d}!}\lesssim
e^{k_{d}(1-\log 4)}k_{d}^{-1/2},$

which is bounded from above by $c_{0}/2-1/40$ for $d\geq D_{1}$, for some
sufficiently large $D_{1}>0$.

∎

######  Lemma 5.

Let $U_{d},U_{d}^{\prime}\stackrel{{\scriptstyle iid}}{{\sim}}\chi^{2}_{d}$,
and $0<\varepsilon_{d}\leq C\sqrt{d}$. Then there exists a large enough
$D_{0}\in\mathbb{N}$, such that for all $d\geq D_{0}$

$\text{Pr}\left(0\leq\frac{U_{d}-U_{d}^{\prime}}{2\sqrt{d}}\leq\frac{\varepsilon_{d}}{\sqrt{d}}\right)\geq\frac{e^{-C^{2}/8}}{6}\frac{\varepsilon_{d}}{\sqrt{d}}.$

###### Proof.

The characteristic function of the random variable
$W_{d}:=(U_{d}-U_{d}^{\prime})/(2\sqrt{d})$ is

$\displaystyle\phi_{d}(t)$
$\displaystyle={\mathbb{E}}e^{itW_{d}}={\mathbb{E}}e^{i\frac{t}{2\sqrt{d}}U_{d}}{\mathbb{E}}e^{-i\frac{t}{2\sqrt{d}}U_{d}^{\prime}}$
$\displaystyle=(1+it/\sqrt{d})^{-d/2}(1-it/\sqrt{d})^{-d/2}$
$\displaystyle=(1+t^{2}/d)^{-d/2}\stackrel{{\scriptstyle
d\rightarrow\infty}}{{\longrightarrow}}e^{-t^{2}/2}.$

Using the Fourier inversion formula, the density $f_{W_{d}}$ of $W_{d}$
satisfies

$\displaystyle f_{W_{d}}(v)$
$\displaystyle=\frac{1}{2\pi}\int_{\mathbb{R}}e^{itv}\phi_{d}(t)dt=\frac{1}{2\pi}\int_{\mathbb{R}}\cos(tv)\phi_{d}(t)dt,$

where the second equality follows from the symmetry of $\phi_{d}$. Let

$\displaystyle g(v)$
$\displaystyle:=\frac{1}{2\pi}\int_{\mathbb{R}}\cos(tv)e^{-t^{2}/2}dt=\frac{1}{\sqrt{2\pi}}e^{-v^{2}/2},$

where the last equation follows for instance by contour integration. Then by
the dominated convergence theorem

$\displaystyle|f_{W_{d}}(v)-g(v)|$
$\displaystyle\leq\frac{1}{2\pi}\int_{\mathbb{R}}|e^{-t^{2}/2}-\phi_{d}(t)|dt\stackrel{{\scriptstyle
d\to\infty}}{{\longrightarrow}}0.$

By the earlier established uniform convergence we have that for every $d\geq
D_{0}$, for some large enough $D_{0}$,

$\int_{0}^{\frac{\varepsilon_{d}}{2\sqrt{d}}}f_{W_{d}}(v)dv\geq\frac{1}{3}e^{-\varepsilon_{d}^{2}/(8d)}\frac{\varepsilon_{d}}{2\sqrt{d}}=\frac{e^{-C^{2}/8}}{6}\frac{\varepsilon_{d}}{\sqrt{d}},$

where the constant $1/3$ is arbitrary and could be taken anything smaller than
$1/\sqrt{2\pi}$. ∎

######  Lemma 6 (Chernoff’s bound).

Let $B_{i}\stackrel{{\scriptstyle ind}}{{\sim}}\text{Ber}(p_{i})$,
$i=1,...,k$, and $0<\delta<1$. Then

$\text{Pr}\left(\left|\underset{i=1}{\overset{k}{\sum}}(B_{i}-{\mathbb{E}}B_{i})\right|\geq\delta\underset{i=1}{\overset{k}{\sum}}p_{i}\right)\leq
2e^{-(\delta^{2}/3)\sum_{i=1}^{k}p_{i}}.$ (24)

##  7 Lemmas for Theorem 1

In this section we collect the proofs of the lemmas used to derive the minimax
testing lower bound.

###  7.1 Proof of Lemma 1

In view of (7) we have

$\displaystyle\mathcal{R}(H_{\rho},T)$ $\displaystyle\geq
1-\left({\mathbb{P}}(T=0|V=0)-{\mathbb{P}}(T=0|V=1)\right)$ $\displaystyle\geq
1-\left|{\mathbb{P}}^{T|V=0}-{\mathbb{P}}^{T|V=1}\right|(T=0)$
$\displaystyle\geq 1-\|{\mathbb{P}}^{T|V=0}-{\mathbb{P}}^{T|V=1}\|_{TV}.$

By the triangle inequality,

$\|{\mathbb{P}}^{T|V=0}-{\mathbb{P}}^{T|V=1}\|_{TV}\leq\|{\mathbb{P}}^{T|V=0}-{\mathbb{P}}^{T}\|_{TV}+\|{\mathbb{P}}^{T}-{\mathbb{P}}^{T|V=1}\|_{TV}.$

Applying the second Pinsker bound to the two terms on the RHS and using that
$2ab\leq a^{2}+b^{2}$,

$\displaystyle\|{\mathbb{P}}^{T|V=0}-{\mathbb{P}}^{T|V=1}\|_{TV}^{2}$
$\displaystyle\leq
D_{KL}({\mathbb{P}}^{T|V=0}\|{\mathbb{P}}^{T})+D_{KL}({\mathbb{P}}^{T|V=1}\|{\mathbb{P}}^{T})$
$\displaystyle=2I_{\Pi}(V,T),$

which completes the proof of the lemma.

###  7.2 Proof of Lemma 2

We prove a more general lemma, but before stating it we recall some
information theoretic definitions and identities, see [12, 20].

For discrete random variables $X$ and arbitrary random variable $Y$, define
the _entropy of_ $X$ as

$H(X)=-\underset{x}{\overset{}{\sum}}{\mathbb{P}}(X=x)\log{\mathbb{P}}(X=x)$

and the _conditional entropy of $X$ given $Y$_,

$H(X|Y)=E_{Y}H(X|Y=y)=-E_{Y}\underset{x}{\overset{}{\sum}}{\mathbb{P}}(X=x|Y=y)\log{\mathbb{P}}(X=x|Y=y).$

We also recall that conditioning reduced entropy $H(X)\geq H(X|Y)$. Following
from this conditioning, on an arbitrary random vector $Z$, also reduces
conditional entropy

$H(X|Y)=\int H(X|Y=y)dP_{Y}(y)\geq\int H(X|Y=y,Z)dP_{Y}(y)=H(X|Y,Z).$

For random variables $X,Y,Z$ we define the mutual information between $X$ and
$Y$ and conditional mutual information between $X$ and $Y$ given $Z$ as

$\displaystyle I(X;Y)$ $\displaystyle=D_{KL}(P_{(X,Y)}\|P_{X}\times P_{Y}),$
$\displaystyle I(X;Y|Z=z)$
$\displaystyle=D_{KL}(P_{(X,Y)|Z=z}\|P_{X|Z=z}\times P_{Y|Z=z}),$
$\displaystyle I(X;Y|Z)$ $\displaystyle=\int I(X;Y|Z=z)dP_{Z}(z).$

Next we recall some conditions of the mutual information. First we note that
$I(X,Y)=0$ if and only if $X$ is independent from $Y$. The chain rule for the
mutual information between the random vector $Y=(Y^{(1)},...,Y^{(m)})$ and $V$
is

$\displaystyle I(V;Y)=\sum_{j=1}^{m}I(V;Y^{(j)}|Y^{(1)},...,Y^{(j-1)}).$ (25)

For discrete random variable $X$ and arbitrary random variable $Y$

$\displaystyle I(X;Y)$
$\displaystyle=E_{(X,Y)}\log\frac{dP_{(XY)}}{dP_{X}dP_{Y}}$ (26)
$\displaystyle=E_{(X,Y)}\log\frac{1}{dP_{X}}-E_{(X,Y)}\log\frac{1}{dP_{(X|Y=y)}}$
(27) $\displaystyle=H(X)-H(X|Y).$ (28)

In addition, by similar arguments, for arbitrary random variable $Z$ we have

$\displaystyle I(X;Y|Z)=H(X|Z)-H(X|Y,Z).$ (29)

######  Lemma 7.

Let us assume that the discrete random variable $V$ and the discrete random
vector $F$ are such that the pair $(V,F)$ is independent from the random
variable $U$ and the discrete random vector $Y=(Y_{1},...,Y_{m})$ satisfies
that $Y_{j}$ is conditionally independent from
$Y_{1:j-1}:=(Y_{1},...,Y_{j-1})$ given $U$ and $(V,F)$, then

$I(V;Y)\leq\underset{j=1}{\overset{m}{\sum}}I(V;Y_{j}|U){+\underset{j=1}{\overset{m}{\sum}}I(F;Y_{j}|U,V)}.$

###### Proof.

A non-public coin version of the lemma is given for instance in [21].

First note that in view of (28) and since conditioning reduces entropy

$\displaystyle I\big{(}(Y,U);V\big{)}=H(V)-H(V|Y,U)\geq H(V)-H(V|Y)=I(Y;V).$

Furthermore, by the chain rule (25) and the independence of $U$ and $V$,

$\displaystyle I\big{(}(Y,U);V\big{)}=I\big{(}Y;V|U\big{)}+I(U;V)=I(Y;V|U).$

Similarly, by the chain rule and nonnegativity of mutual information,

$I\big{(}V;Y|U\big{)}=I\big{(}(V,F);Y|U\big{)}-I\big{(}F;Y|U,V\big{)}\leq
I\big{(}(V,F);Y|U\big{)}.$

By the identity (29) and the chain rule (25),

$\displaystyle I\big{(}(V,F);Y|U\big{)}$ $\displaystyle=H(Y|U)-H(Y|V,F,U)$
$\displaystyle=\underset{j=1}{\overset{m}{\sum}}H(Y_{j}|Y_{1:j-1},U)-H(Y_{j}|V,F,Y_{1:j-1},U).$

Since conditioning reduces entropy we have $H(Y_{j}|Y_{1:j-1},U)\leq
H(Y_{j}|U)$. Furthermore, by the conditional independence of $Y_{1:j-1}$ and
$Y_{j}$ given $(U,V,F)$ results in $H(Y_{j}|V,F,Y_{1:j-1},U)=H(Y_{j}|V,F,U)$.
Using these two facts, we obtain that

$\displaystyle I\big{(}(V,F);Y|U\big{)}$
$\displaystyle\leq\underset{j=1}{\overset{m}{\sum}}H(Y_{j}|,U)-H(Y_{j}|V,F,U)$
$\displaystyle=\underset{j=1}{\overset{m}{\sum}}I\big{(}(V,F);Y_{j}|U\big{)}.$

Combining the above displays and again applying the chain rule we now obtain
that

$I(Y;V)\leq\underset{j=1}{\overset{m}{\sum}}I\big{(}(V,F);Y_{j}|U\big{)}=\underset{j=1}{\overset{m}{\sum}}\left[I\big{(}V;Y_{j}|U\big{)}+I\big{(}F;Y_{j}|U,V\big{)}\right].$

∎

###  7.3 Proof of Lemma 3

Using the sub-Gaussianity of the likelihood $P_{\Pi}=\int P_{\mu}d\Pi(\mu)$
verified in Lemma 8, we adapt the proof of Theorem 3.7 in [21] to the present
continuous setting with public coin protocol.

###### Proof.

We start by noting that if $48\beta\geq 1$, the result follows immediately
from the regular data processing inequality for mutual information.

In view of the definition of the conditional mutual information and noting
that ${\mathbb{P}}^{V|U=u}(v)={\mathbb{P}}^{V}(v)=1/2$ by independence of $U$
and $V$,

$\displaystyle
I(V,{T}^{(j)}|U)=\frac{1}{2}\int\sum_{v\in\\{0,1\\}}D_{KL}\left({\mathbb{P}}^{{T}^{(j)}|(V,U)=(v,u)};{\mathbb{P}}^{{T}^{(j)}|U=u}\right)d{\mathbb{P}}^{U}(u).$
(30)

By Lemma 13 below,

$D_{KL}\left({\mathbb{P}}^{{T}^{(j)}|(V,U)=(v,u)}\|{\mathbb{P}}^{{T}^{(j)}|U=u}\right)\leq\underset{{t}\in{{\\{0,1\\}}}}{\overset{}{\sum}}{\mathbb{P}}^{{T}^{(j)}|U=u}({t})\left(\frac{{\mathbb{P}}^{{T}^{(j)}|(V,U)=(v,u)}({t})}{{\mathbb{P}}^{{T}^{(j)}|U=u}({t})}-1\right)^{2}$
(31)

${\mathbb{P}}^{U}$-almost surely. Furthermore, by Bayes rule,

$\frac{{\mathbb{P}}^{{T}^{(j)}|(U,X^{(j)})=(u,x)}({t})}{{\mathbb{P}}^{{T}^{(j)}|U=u}({t})}=\frac{d{\mathbb{P}}^{X^{(j)}|(U,{T}^{(j)})=(u,{t})}}{d{\mathbb{P}}^{X^{(j)}|U=u}}(x)=:g_{{t},u}(x),$
(32)

where the equality holds in an $L_{1}\left({\mathbb{P}}^{X^{(j)}}\right)$
sense ${\mathbb{P}}^{U}$-almost surely.

For $v\in\\{0,1\\}$, define

$\mathscr{L}_{v}(X^{(j)}):=\frac{d{\mathbb{P}}^{X^{(j)}|V=v}}{d{\mathbb{P}}^{X^{(j)}}}(X^{(j)}).$

Since $V\to(X^{(j)},U)\to{T}^{(j)}$ forms a Markov chain, we can write

$\displaystyle\frac{{\mathbb{P}}^{{T}^{(j)}|(V,U)=(v,u)}({t})}{{\mathbb{P}}^{Y^{(j)}|U=u}({t})}$
$\displaystyle=\int\frac{{\mathbb{P}}^{{T}^{(j)}|(U,X^{(j)})=(u,x)}({t})}{{\mathbb{P}}^{{T}^{(j)}|U=u}({t})}d{\mathbb{P}}^{X^{(j)}|V=v}(x)$
$\displaystyle={\mathbb{E}}_{X^{(j)}}\left[g_{{t},u}(X^{(j)})\mathscr{L}_{v}(X^{(j)})\right].$

Then in view of
${\mathbb{E}}_{X^{(j)}}\mathscr{L}_{v}(X^{(j)})=1={\mathbb{E}}_{X^{(j)}}g_{y,u}(X^{(j)})$,
${\mathbb{P}}^{U}$-a.s., the right hand side of (31) equals

$\underset{{t}\in{\\{0,1\\}}}{\overset{}{\sum}}{\mathbb{P}}^{{T}^{(j)}|U=u}({t})\text{Cov}\left(\mathscr{L}_{v}(X^{(j)}),g_{{t},u}(X^{(j)})\right)^{2},\;\;\;{\mathbb{P}}^{U}\text{-a.s.}$

By Theorem 4.13 in [7], we have that

${\mathbb{E}}GH\leq{\mathbb{E}}H\log H+\log{\mathbb{E}}e^{G}$

for any random variables $G,H$ with ${\mathbb{E}}H=1$ and
${\mathbb{E}}e^{G}<\infty$. Applying this to
$G=s(\mathscr{L}_{v}(X^{(j)})-1)$, $H=g_{{t},u}(X^{(j)})$ we obtain

$\displaystyle
s\text{Cov}\left(\mathscr{L}_{v}(X^{(j)}),g_{{t},u}(X^{(j)})\right)\leq\log$
$\displaystyle\,{\mathbb{E}}_{X^{(j)}}\left[e^{s(\mathscr{L}_{v}(X^{{(j)}})-1)}\right]$
$\displaystyle+{\mathbb{E}}_{X^{(j)}}\left[g_{{t},u}(X^{(j)})\log
g_{{t},u}(X^{(j)})\right].$

By display (32) and the independence of $X^{(j)}$ and $U$,

${\mathbb{E}}_{X^{(j)}}\left[g_{{t},u}(X^{(j)})\log
g_{{t},u}(X^{(j)})\right]=D_{KL}({\mathbb{P}}^{X^{(j)}|(U,{T}^{(j)})=(u,{t})}\|{\mathbb{P}}^{X^{(j)}|U=u}).$

Furthermore, in view of Lemma 8, $\mathscr{L}_{v}(X^{(j)})$ is
$\sqrt{24\beta}$-sub-Gaussian, hence

$\log{\mathbb{E}}_{X^{(j)}}\left[e^{s(\mathscr{L}_{v}(X^{(j)})-1)}\right]\leq
24\beta s^{2}/2.$

Taking
$s=(24\beta)^{-1}\text{Cov}\left(\mathscr{L}_{v}(X^{(j)}),g_{{t},u}(X^{(j)})\right)$
and combining the above displays we obtain

$\displaystyle\text{Cov}\left(\mathscr{L}_{v}(X^{(j)}),g_{{t},u}(X^{(j)})\right)^{2}\leq\frac{1}{2}$
$\displaystyle\text{Cov}\left(\mathscr{L}_{v}(X^{(j)}),g_{{t},u}(X^{(j)})\right)^{2}$
$\displaystyle+24\beta
D_{KL}({\mathbb{P}}^{X^{(j)}|(U,{T}^{(j)})=(u,{t})}\|{\mathbb{P}}^{X^{(j)}|U=u}),$

which holds ${\mathbb{P}}^{U}$-almost surely. We now have shown that

$\displaystyle\int
D_{KL}\left({\mathbb{P}}^{{T}^{(j)}|(V,U)=(v,u)}\|{\mathbb{P}}^{{T}^{(j)}|U=u}\right)d{\mathbb{P}}^{U}(u)$
$\displaystyle\qquad\qquad\leq
48\beta\int\underset{{t}\in{\\{0,1\\}}}{\overset{}{\sum}}{\mathbb{P}}^{{T}^{(j)}|U=u}({t})D_{KL}({\mathbb{P}}^{X^{(j)}|(U,{T}^{(j)})=(u,{t})}\|{\mathbb{P}}^{X^{(j)}|U=u})d{\mathbb{P}}^{U}(u)$
$\displaystyle\qquad\qquad=48\beta I(X^{(j)},{T}^{(j)}|U),$

which in view of (30) concludes the proof. ∎

###  7.4 Sub-Gaussianity lemma

First we recall some notations from Section 3.1. Let us denote by $\Pi$ the
distribution of the random vector $\epsilon R$, where $R=(R_{1},\dots,R_{d})$
has independent Rademacher marginals and $\epsilon>0$ is small (it is taken to
be $\epsilon=\rho/\sqrt{d}$). We take $V\sim Ber(1/2)$ and set $X|(V=0)\sim
N(0,\sigma^{2}I_{d})$ and $X|(V=1)\sim P_{\Pi}$, where $P_{\Pi}=\int
P_{\mu}d\Pi(\mu)$ and $P_{\mu}$ is a multivariate Gaussian distribution with
mean $\mu$ and $\sigma^{2}$ times the identity variance. Let
${\mathbb{P}}^{X}$ and ${\mathbb{P}}^{X|V}$ denote the corresponding
distributions of $X$ and $X|V$.

######  Definition 1.

A random variable $X$ is called $\beta$_-sub-Gaussian_ if for all
$s\in{\mathbb{R}}$,

${\mathbb{E}}e^{s(X-{\mathbb{E}}X)}\leq e^{\beta^{2}s^{2}/2}.$

The lemma below shows that the likelihood ratios
$\frac{d{\mathbb{P}}^{X|V=0}}{d{\mathbb{P}}^{X}}(X)$ and
$\frac{d{\mathbb{P}}^{X|V=1}}{d{\mathbb{P}}^{X}}(X)$ are sub-Gaussian.

######  Lemma 8.

The likelihood ratios

$\frac{d{\mathbb{P}}^{X|V=0}}{d{\mathbb{P}}^{X}}(X)\;\;\text{ and
}\;\;\frac{d{\mathbb{P}}^{X|V=1}}{d{\mathbb{P}}^{X}}(X)$

are $\sqrt{24\beta}$-sub-Gaussian with

$\beta=\begin{cases}d\epsilon^{4}/\sigma^{4},\;\;\;\text{ if
}\sigma^{2}/\epsilon^{2}<d/2,\\\ 2\epsilon^{2}/\sigma^{2},\;\;\;\text{ if
}\sigma^{2}/\epsilon^{2}\geq d/2.\end{cases}$ (33)

###### Proof.

Using the notation

$\mathscr{L}_{v}(X):=\frac{d{\mathbb{P}}^{X|V=v}}{d{\mathbb{P}}^{X}}(X),\quad
v\in\\{0,1\\},$

we show below that for all $t\in{\mathbb{R}}$,

${\mathbb{E}}_{X}e^{t(\mathscr{L}_{v}(X)-{\mathbb{E}}_{X}\mathscr{L}_{v}(X))}\leq
e^{24\beta t^{2}/2}.$

This is implied by

${\mathbb{P}}^{X}\left(|\mathscr{L}_{v}-{\mathbb{E}}_{X}\mathscr{L}_{v}|\geq
s\right)\leq 12\exp\left(-\frac{s^{2}}{2\beta}\right)\,\,\,\text{ for all
}s>0,$ (34)

where the equivalence is well known, but a proof can be found in Lemma 11.
Since
$|\mathscr{L}_{v}(X)-{\mathbb{E}}_{X}\mathscr{L}_{v}(X)|=|\mathscr{L}_{v}(X)-1|\leq
1$, it is enough to consider $0<s<1$.

To prove (34), let us first introduce the notation
$L:=\frac{dP_{\pi}}{dP_{0}}$, and note that

$\mathscr{L}_{0}=\frac{2}{1+L}\quad\text{and}\quad\mathscr{L}_{1}=\frac{2}{1+L^{-1}}.$

Then for $x\in\\{\mathscr{L}_{0}-1\geq s\\}$ we have

$\frac{2}{1+L}(x)=\mathscr{L}_{0}(x)\geq s+1\quad\text{ and }\quad
0\leq\frac{2L}{1+L}(x)=1-\frac{1-L}{1+L}(x)\leq 1-s,$

where the last inequality follows from $\mathscr{L}_{0}-1=\frac{1-L}{1+L}$.
Consequently, $L^{-1}(x)\geq\frac{s+1}{1-s}$. Similarly, for
$x\in\\{\mathscr{L}_{0}-1\leq-s\\}$,

$0\leq\frac{2}{1+L}(x)\leq 1-s\text{ and }\frac{2L}{1+L}(x)\geq 1+s$

and thus $L(x)\geq\frac{s+1}{1-s}$. Combining the above bounds results in for
$x\in\\{|\mathscr{L}_{0}-1|\geq s\\}$ that

$|\log L(x)|\geq\log\left(\frac{1+s}{1-s}\right)\geq\frac{2s}{1+s}\geq s,$

where the last two inequalities follow from $\log x\geq 1-\frac{1}{x}$ and
$0<s<1$.

Through the same computation, the above display is also true for
$x\in\\{|\mathscr{L}_{1}-1|\geq s\\}$. Consequently, for $v=0,1$,

$\displaystyle{\mathbb{P}}^{X}\left(|\mathscr{L}_{v}-{\mathbb{E}}\mathscr{L}_{v}|\geq
s\right)$ $\displaystyle\leq{\mathbb{P}}^{X}\left(|\log L|\geq s\right)$
$\displaystyle=\frac{1}{2}P_{0}\left(|\log(L)|\geq
s\right)+\frac{1}{2}P_{\pi}\left(|\log(L)|\geq s\right).$

Using Markov’s inequality the terms on the right hand side can be further
bounded as

$\displaystyle P_{0}\left(|\nu\log(L)|\geq\nu s\right)$ $\displaystyle\leq
e^{-\nu
s}({\mathbb{E}}_{X|V=0}L^{\nu}+{\mathbb{E}}_{X|V=0}L^{-\nu})\;\;\;\;\;\;\;\;\;\;\,\text{
for }\nu>0,$ (35) $\displaystyle P_{\pi}\left(|\lambda\log(L)|\geq\lambda
s\right)$ $\displaystyle\leq
e^{-\lambda_{1}s}{\mathbb{E}}_{X|V=1}L^{\lambda_{1}}+e^{-\lambda_{2}s}{\mathbb{E}}_{X|V=1}L^{-\lambda_{2}}\;\text{
for }\lambda_{1},\lambda_{2}>0.$ (36)

Note that ${\mathbb{E}}_{X|V=1}L^{\lambda}={\mathbb{E}}_{X|V=0}L^{\lambda+1}$,
hence choosing $\lambda_{1}=\nu-1$ and $\lambda_{2}=\nu+1$ in display (36), we
get by combining the above two displays that for $v\in\\{0,1\\}$,

${\mathbb{P}}^{X}\left(|\mathscr{L}_{v}-{\mathbb{E}}\mathscr{L}_{v}|\geq
s\right)\leq\frac{1}{2}\left[1+e^{-s}+e^{s}\right]e^{-\nu
s}({\mathbb{E}}_{X|V=0}L^{\nu}+{\mathbb{E}}_{X|V=0}L^{-\nu}).$ (37)

We proceed by bounding the expectations in the above display after which
minimizing in $\nu$ gives us the result of the lemma. Recall that
$X|(V=0)\sim\mathcal{N}(0,\sigma^{2}I_{d})$ and
$X_{i}|(V=1)\stackrel{{\scriptstyle
iid}}{{\sim}}\frac{1}{2}\mathcal{N}(\epsilon,\sigma^{2})+\frac{1}{2}\mathcal{N}(-\epsilon,\sigma^{2})$,
$i=1,...,d$. Consequently,

$\displaystyle L(X)$
$\displaystyle=\underset{i=1}{\overset{d}{\Pi}}\left[\frac{\exp\big{(}-\frac{1}{2\sigma^{2}}(X_{i}-\epsilon)^{2}\big{)}+\exp\big{(}-\frac{1}{2\sigma^{2}}(X_{i}+\epsilon)^{2}\big{)}}{2\exp(-\frac{1}{2\sigma^{2}}X_{i}^{2})}\right]$
$\displaystyle=\underset{i=1}{\overset{d}{\Pi}}\exp(-\frac{1}{2}\epsilon^{2}/\sigma^{2})\cosh(X_{i}\epsilon/\sigma^{2}).$
(38)

Then by independence of $X_{j}$, $j=1,...,d$

$\displaystyle{\mathbb{E}}_{X|V=0}L^{\nu}$
$\displaystyle=\left(e^{-\frac{\nu}{2}\epsilon^{2}/\sigma^{2}}{\mathbb{E}}\cosh^{\nu}\left(\frac{\epsilon}{\sigma}Z\right)\right)^{d},$

where $Z\sim N(0,1)$.

Next we distinguish two cases. Suppose first that
$2/d\leq\epsilon^{2}/\sigma^{2}$. Let us take
$\nu=s\sigma^{4}/(d\epsilon^{4})$. Then $\nu\epsilon^{2}/\sigma^{2}<1/2$, as
$0<s<1$, and hence in view of Lemma 10

$\displaystyle e^{-s\nu}({\mathbb{E}}_{0}L^{\nu}+{\mathbb{E}}_{0}L^{-\nu})$
$\displaystyle\leq\exp\left(\nu^{2}\frac{d\epsilon^{4}}{2\sigma^{4}}-s\nu\right)\left(1+e^{(3/2)\nu
d\epsilon^{4}/\sigma^{4}}\right)$
$\displaystyle\leq\exp\left(-\frac{s^{2}}{2}\frac{\sigma^{4}}{d\epsilon^{4}}\right)\left(1+e^{(3/2)s}\right).$

The remaining case is when $2/d>\epsilon^{2}/\sigma^{2}$. Choosing
$\nu=s\sigma^{2}/(2\epsilon^{2})$ results in $\nu\epsilon^{2}/\sigma^{2}<1/2$,
hence again in view of Lemma 10

$\displaystyle e^{-s\nu}({\mathbb{E}}_{0}L^{\nu}+{\mathbb{E}}_{0}L^{-\nu})$
$\displaystyle\leq\left(\nu^{2}\frac{d\epsilon^{4}}{2\sigma^{4}}-s\nu\right)\left(1+e^{(3/2)\nu
d\epsilon^{4}/\sigma^{4}}\right)$
$\displaystyle\leq\exp\left(-\frac{s^{2}}{2}\frac{\sigma^{2}}{2\epsilon^{2}}\right)\left(1+e^{(3/2)s}\right).$

Hence, by plugging in the last two displays into (37), and noting that for
$0<s<1$

$\frac{1}{2}\left(1+e^{(3/2)s}\right)\left[1+e^{-s}+e^{s}\right]\leq 12,$

we arrive at (34), for $\beta$ given in (33), concluding the proof of the
lemma. ∎

##  8 Additional technical lemmas

In this subsection, we collect technical lemmas and their proofs.

The following lemma is essentially Lemma 11 in [9] adopted the setting in this
article.

######  Lemma 9 (Multivariate Gaussian estimation SPDI).

Let $R$ a $d$-dimensional vector of independent Rademacher variables, $V$ be
an independent $\text{Ber}(1/2)$ random variable and let $\Pi$ denote the
distribution of $\mu=\epsilon VR$ where $\epsilon>0$ is a constant. Suppose
that the random vector $X=(X_{1},\dots,X_{d})$ satisfies $X|\mu\sim
N(\mu,\sigma^{2}I_{d})$ and that $T$ is a discrete random variable such that
$V\to\mu\to X\to Y$ forms a Markov chain. Then,

$I(\mu;T|V)\leq 128\left(\frac{\epsilon}{\sigma}\right)^{2}I(X;T|V=1).$

###### Proof.

Write $R_{1},\dots,R_{d}$ for the coordinates of $R$ and write for $k\leq d$,
$R_{1:k}:=(R_{1},\dots,R_{k})$ and $X_{1:k}=(X_{1},\dots,X_{k})$.
Conditionally on $V=0$, $\mu=0$ with probability $1$, so $I(\mu;T|V=0)=0$.
Conditionally on $V=1$, $\mu=\epsilon R$. Combining these facts with the chain
rule for mutual information,

$\displaystyle I(\mu;T|V)=\frac{1}{2}I(\epsilon R;T|V=1)$
$\displaystyle=\frac{1}{2}\underset{k=1}{\overset{d}{\sum}}I(\epsilon
R_{k};T|V=1,R_{1:k-1})$
$\displaystyle=\frac{1}{2}\underset{k=1}{\overset{d}{\sum}}I(\epsilon
R_{k};T|V=1),$

where the last equality follows from the fact that the coordinates of $R$ are
independent, so $R_{k+1}$ is independent of $R_{1:k}$. Furthermore,
$R_{k}|V=1\to X_{k}|V=1\to T|V=1$ forms a Markov chain with
$(X_{k}|R_{k},V=1)\sim N(\epsilon R_{k},\sigma^{2})$. Consequently, by
applying Lemma 14 in [9],

$I(\epsilon R_{k};T|V=1)\leq
64\left(\frac{2\epsilon}{\sigma}\right)^{2}I(X_{k};T|V=1).$

The proof is now finished by observing that $X_{k+1}|V=1$ is independent of
$X_{1:k}|V=1$, so combining the above inequality with the chain rule of mutual
information, we obtain

$I(\mu;T|V)\leq
128\left(\frac{\epsilon}{\sigma}\right)^{2}\underset{k=1}{\overset{d}{\sum}}I(X_{k};T|V=1,X_{1:k-1})=128\left(\frac{\epsilon}{\sigma}\right)^{2}I(X;T|V=1).$

∎

######  Lemma 10.

Let $Z\sim N(0,1)$ and let $\nu\in{\mathbb{R}}$ such that
$|\nu|\epsilon^{2}/\sigma^{2}<1/2$. It holds that

${\mathbb{E}}\cosh^{\nu}\left(\frac{\epsilon}{\sigma}Z\right)\leq\exp\left({\nu\frac{\epsilon^{2}}{2\sigma^{2}}+\nu^{2}\frac{3\epsilon^{4}}{2\sigma^{4}}}-\text{1}_{\\{\nu<0\\}}\frac{3}{2}\nu\frac{\epsilon^{4}}{\sigma^{4}}\right).$
(39)

###### Proof.

First assume that $\nu\geq 0$. Using $\cosh(x)\leq e^{x^{2}/2}$ we find

${\mathbb{E}}\cosh^{\nu}\left(\frac{\epsilon}{\sigma}Z\right)\leq{\mathbb{E}}e^{\nu\frac{\epsilon^{2}}{2\sigma^{2}}Z^{2}}.$

In view of Lemma 12,

${\mathbb{E}}e^{\lambda(Z^{2}-1)}\leq e^{2\lambda^{2}}\text{ for all
}0\leq\lambda\leq 1/4.$

Applying this to the second last display yields (39).

Consider now the case that $\nu<0$. We have

$\displaystyle\frac{d}{dx}\cosh^{\nu}\left(\frac{\epsilon}{\sigma}x\right)$
$\displaystyle=\nu\frac{\epsilon}{\sigma}\cosh^{\nu}\left(\frac{\epsilon}{\sigma}x\right)\tanh\left(\frac{\epsilon}{\sigma}x\right),$
$\displaystyle\frac{d^{2}}{dx^{2}}\cosh^{\nu}\left(\frac{\epsilon}{\sigma}x\right)$
$\displaystyle=\nu\frac{\epsilon^{2}}{\sigma^{2}}\cosh^{\nu}\left(\frac{\epsilon}{\sigma}x\right)\left[(\nu-1)\tanh^{2}\left(\frac{\epsilon}{\sigma}x\right)+1\right]=:\tau(x)$

Since $\cosh(0)=1$ and $\tanh(0)=0$, a second order Taylor expansion of
$x\mapsto\cosh^{\nu}\left(\frac{\epsilon}{\sigma}x\right)$ about $0$ yields

$\displaystyle{\mathbb{E}}\cosh^{\nu}\left(\frac{\epsilon}{\sigma}Z\right)$
$\displaystyle={\mathbb{E}}\left[1+\frac{Z^{2}}{2!}\tau(r_{Z}Z)\right],\text{
for some}\quad r_{Z}\in[0,1].$

Since $\tanh^{2}(x)\leq x^{2}$ and $\cosh(x)\geq 1$ for all
$x\in{\mathbb{R}}$,

$\displaystyle{\mathbb{E}}\frac{Z^{2}}{2!}\tau(r_{Z}Z)\leq\nu\frac{\epsilon^{2}}{2\sigma^{2}}\bigg{[}(\nu-1)\frac{\epsilon^{2}}{\sigma^{2}}{\mathbb{E}}r_{Z}^{2}Z^{4}+1\bigg{]}\leq\nu\frac{\epsilon^{2}}{2\sigma^{2}}\bigg{[}(\nu-1)\frac{3\epsilon^{2}}{\sigma^{2}}+1\bigg{]}.$

Then by combining the above two displays

${\mathbb{E}}\cosh^{\nu}\left(\frac{\epsilon}{\sigma}Z\right)\leq\exp\left({\nu\frac{\epsilon^{2}}{2\sigma^{2}}+\nu^{2}\frac{3\epsilon^{4}}{2\sigma^{4}}}-\frac{3}{2}\nu\frac{\epsilon^{4}}{\sigma^{4}}\right),$

∎

The next lemma gives a well-known sufficient (and necessary) condition for the
sub-Gaussian distribution. In the literature we did not find the present,
required form of the lemma, hence for completeness we also provide its proof.

######  Lemma 11.

Let $X$ a mean-zero random variable satisfying

${\mathbb{P}}\left(|X|\geq s\right)\leq
C\exp\left(-\frac{s^{2}}{2\beta}\right)$

for some $C\geq 2$, $\beta>0$ and for all $s\in[0,\infty)$. Then,

${\mathbb{E}}e^{sX}\leq e^{2\beta Cs^{2}/2}.$

###### Proof.

For $k\in{\mathbb{N}}$, we have

$\displaystyle{\mathbb{E}}|X|^{k}=\int_{0}^{\infty}{\mathbb{P}}\left(|X|^{k}>t\right)dt\leq
C\int_{0}^{\infty}\exp\left(-\frac{t^{2/k}}{2\beta}\right)dt.$

Changing coordinates to $u=t^{2/k}/(2\beta)$ yields that the right hand side
display equals

$\displaystyle\frac{C}{2}(2\beta)^{k/2}k\int_{0}^{\infty}e^{-u}u^{k/2-1}du$
$\displaystyle=\frac{C}{2}(2\beta)^{k/2}k\Gamma(k/2).$

By the dominated convergence theorem, ${\mathbb{E}}X=0$, and $C\geq 2$,

$\displaystyle{\mathbb{E}}e^{sX}$
$\displaystyle=1+\underset{k=2}{\overset{\infty}{\sum}}\frac{s^{k}{\mathbb{E}}X^{k}}{k!}\leq
1+\frac{C}{2}\underset{k=2}{\overset{\infty}{\sum}}\frac{(2\beta
s^{2})^{k/2}\Gamma(k/2)}{(k-1)!}$ $\displaystyle\leq
1+\underset{k=1}{\overset{\infty}{\sum}}\left[\frac{(C\beta
s^{2})^{k}\Gamma(k)}{(2k-1)!}+\frac{(C\beta
s^{2})^{k+1/2}\Gamma(k+1/2)}{(2k)!}\right].$

Since $\Gamma(k+1/2)\leq\Gamma(k+1)=k\Gamma(k)=k!$ and $(2k)!\geq
2^{k}(k!)^{2}$, the latter is further bounded by

$\displaystyle 1+\left(1+\sqrt{{C}\beta
s^{2}}\right)\underset{k=1}{\overset{\infty}{\sum}}\frac{(C\beta
s^{2}/2)^{k}}{k!}=e^{{C\beta s^{2}/2}}+{\sqrt{C\beta s^{2}}}(e^{{\beta
Cs^{2}/2}}-1).$

Since $(e^{x}-1)(e^{x}-\sqrt{x})\geq 0$, we obtain that

${\mathbb{E}}e^{sX}\leq e^{\frac{2C\beta s^{2}}{2}}.$

∎

The following lemma is a well known result and follows from standard calculus,
but we included it as we did not find a stand-alone proof.

######  Lemma 12.

Let $Z$ be $N(0,1)$, $0\leq\lambda\leq 1/4$. Then,

${\mathbb{E}}e^{\lambda(Z^{2}-1)}\leq e^{2\lambda^{2}}.$

###### Proof.

Using the change of variables $u=z\sqrt{1-2\lambda}$,

$\displaystyle{\mathbb{E}}e^{\lambda(Z^{2}-1)}$
$\displaystyle=\frac{1}{\sqrt{2\pi}}\int
e^{\lambda(z^{2}-1)}e^{-\frac{1}{2}z^{2}}dz$
$\displaystyle=\frac{e^{-\lambda}}{\sqrt{2\pi(1-2\lambda)}}\int
e^{-\frac{1}{2}z^{2}}dz=\frac{e^{-\lambda}}{\sqrt{(1-2\lambda)}}.$

The MacLaurin series of $-\frac{1}{2}\log(1-2\lambda)$ reads

$\frac{1}{2}\underset{k=1}{\overset{\infty}{\sum}}\frac{(2\lambda)^{k}}{k},$

which yields that the second last display equals

$\exp\left(\frac{3}{2}\lambda^{2}+\frac{1}{2}\underset{k=3}{\overset{\infty}{\sum}}\frac{(2\lambda)^{k}}{k}\right).$

If $\lambda\leq 1/4$,

$\underset{k=3}{\overset{\infty}{\sum}}\frac{(2\lambda)^{k}}{k}\leq\frac{(2\lambda)^{3}}{1-2\lambda}\leq\lambda^{2},$

from which the result follows. ∎

The next lemma is a standard bound for the KL-divergence, see for instance
Lemma 2.7 of [29].

######  Lemma 13.

Let $P,Q$ probability measures on some measure space such that $Q\ll P$. Then,

$D_{KL}(P\|Q)\leq\int\left(\frac{dP}{dQ}-1\right)^{2}dQ.$

## References

  * [1] Acharya, J., Canonne, C. L., and Tyagi, H. Distributed signal detection under communication constraints.  In Proceedings of Thirty Third Conference on Learning Theory (09–12 Jul 2020), J. Abernethy and S. Agarwal, Eds., vol. 125 of Proceedings of Machine Learning Research, PMLR, pp. 41–63.
  * [2] Acharya, J., Canonne, C. L., and Tyagi, H. Inference under information constraints i: Lower bounds from chi-square contraction.  IEEE Transactions on Information Theory 66, 12 (2020), 7835–7855.
  * [3] Ahlswede, R., and Csiszar, I. Hypothesis testing with communication constraints.  IEEE Transactions on Information Theory 32, 4 (July 1986), 533–542.  Number: 4.
  * [4] Amari, S.-i. Fisher information under restriction of Shannon information in multi-terminal situations.  Annals of the Institute of Statistical Mathematics 41, 4 (Dec. 1989), 623–648.
  * [5] Baraud, Y. Non-asymptotic minimax rates of testing in signal detection.  Bernoulli 8, 5 (Oct. 2002), 577–606.  Publisher: Bernoulli Society for Mathematical Statistics and Probability.
  * [6] Barnes, L. P., Han, Y., and Ozgur, A. Lower bounds for learning distributions under communication constraints via fisher information.  Journal of Machine Learning Research 21, 236 (2020), 1–30.
  * [7] Boucheron, S., Lugosi, G., and Massart, P. Concentration inequalities: a nonasymptotic theory of independence, 1st ed ed.  Oxford University Press, Oxford, 2013.  OCLC: ocn818449985.
  * [8] Braverman, M., Garg, A., Ma, T., Nguyen, H. L., and Woodruff, D. P. 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 (2016), pp. 1011–1020.
  * [9] Cai, T. T., and Wei, H. Distributed Gaussian Mean Estimation under Communication Constraints: Optimal Rates and Communication-Efficient Algorithms.  arXiv:2001.08877 [cs, math, stat] (Jan. 2020).  arXiv: 2001.08877.
  * [10] Chamberland, J.-F., and Veeravalli, V. Wireless Sensors in Distributed Detection Applications.  IEEE Signal Processing Magazine 24, 3 (May 2007), 16–25.
  * [11] Chen, X., Guntuboyina, A., and Zhang, Y. On bayes risk lower bounds.  J. Mach. Learn. Res. 17, 1 (Jan. 2016), 7687–7744.
  * [12] Cover, T. M., and Thomas, J. A. Elements of information theory.  John Wiley & Sons, 2012.
  * [13] Diakonikolas, I., Gouleakis, T., Kane, D. M., and Rao, S. Communication and memory efficient testing of discrete distributions.  In Proceedings of the Thirty-Second Conference on Learning Theory (Phoenix, USA, 25–28 Jun 2019), A. Beygelzimer and D. Hsu, Eds., vol. 99 of Proceedings of Machine Learning Research, PMLR, pp. 1070–1106.
  * [14] Fischer, O., Meir, U., and Oshman, R. Distributed uniformity testing.  In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (New York, NY, USA, 2018), PODC ’18, Association for Computing Machinery, p. 455–464.
  * [15] Han, T., and Kobayashi, K. Exponential-type error probabilities for multiterminal hypothesis testing.  IEEE Transactions on Information Theory 35, 1 (Jan. 1989), 2–14.
  * [16] Han, T. S. Hypothesis Testing with Multiterminal Data Compression.  DATA COMPRESSION, 6 (1987), 14.
  * [17] Han, Y., Özgür, A., and Weissman, T. Geometric lower bounds for distributed parameter estimation under communication constraints.  In Conference On Learning Theory (2018), PMLR, pp. 3163–3188.
  * [18] Ingster, Y. I., and Suslina, I. A. Nonparametric goodness-of-fit testing under Gaussian models.  No. 169 in Lectures notes in statistics. Springer, New York, 2002.
  * [19] Kreidl, O. P., Tsitsiklis, J. N., and Zoumpoulis, S. I. On Decentralized Detection With Partial Information Sharing Among Sensors.  IEEE Transactions on Signal Processing 59, 4 (Apr. 2011), 1759–1765.
  * [20] Polyanskiy, Y., and Wu, Y. Lecture notes on information theory.  Lecture Notes for ECE563 (UIUC) and 6, 2012-2016 (2014), 7.
  * [21] Raginsky, M. Strong Data Processing Inequalities and $\Phi $ -Sobolev Inequalities for Discrete Channels.  IEEE Transactions on Information Theory 62, 6 (June 2016), 3355–3389.  Conference Name: IEEE Transactions on Information Theory.
  * [22] Shalaby, H., and Papamarcou, A. Multiterminal detection with zero-rate data compression.  IEEE Transactions on Information Theory 38, 2 (Mar. 1992), 254–267.
  * [23] Szabo, B., and van Zanten, H. Adaptive distributed methods under communication constraints.  Annals of Statistics 48, 4 (2020), 2347–2380.
  * [24] Szabo, B., and van Zanten, H. Distributed function estimation: adaptation using minimal communication.  arXiv preprint arXiv:2003.12838 (2020).
  * [25] Tarighati, A., Gross, J., and Jalden, J. Decentralized Hypothesis Testing in Energy Harvesting Wireless Sensor Networks.  IEEE Transactions on Signal Processing 65, 18 (Sept. 2017), 4862–4873.
  * [26] Te Sun Han, and Amari, S. Statistical inference under multiterminal data compression.  IEEE Transactions on Information Theory 44, 6 (Oct. 1998), 2300–2324.  Number: 6.
  * [27] Tenney, R. R., and Sandell, N. R. Detection with Distributed Sensors.  IEEE Transactions on Aerospace and Electronic Systems AES-17, 4 (July 1981), 501–510.  Number: 4.
  * [28] Tsitsiklis, J. N. Decentralized detection by a large number of sensors.  Mathematics of Control, Signals, and Systems 1, 2 (June 1988), 167–182.  Number: 2.
  * [29] Tsybakov, A. B. Introduction to nonparametric estimation.  Springer, New York, 2009.
  * [30] Varshney, P. K. Distributed Detection and Data Fusion.  Springer New York, New York, NY, 1997.  OCLC: 853259779.
  * [31] Watanabe, S. Neyman–Pearson Test for Zero-Rate Multiterminal Hypothesis Testing.  IEEE Transactions on Information Theory 64, 7 (July 2018), 4923–4939.
  * [32] Xu, A., and Raginsky, M. Information-Theoretic Lower Bounds on Bayes Risk in Decentralized Estimation.  IEEE Transactions on Information Theory 63, 3 (Mar. 2017), 1580–1600.
  * [33] Zhang, Y., Duchi, J., Jordan, M. I., and Wainwright, M. J. Information-theoretic lower bounds for distributed statistical estimation with communication constraints.  In Advances in Neural Information Processing Systems (2013), pp. 2328–2336.
  * [34] Zhu, Y., and Lafferty, J. Distributed nonparametric regression under communication constraints.  In International Conference on Machine Learning (2018), pp. 6004–6012.