# A Fundamental Limit of Distributed Hypothesis Testing Under Memoryless
Quantization

Yunus İnan, , Mert Kayaalp, ,
Ali H. Sayed, , Emre Telatar The authors are with École Polytechnique Fédérale
de Lausanne (EPFL), 1015 Lausanne, Switzerland. Emails: {yunus.inan,
mert.kayaalp, ali.sayed<EMAIL_ADDRESS>
A short version of this work is presented at IEEE ICC 2022 [1].

###### Abstract

We study a distributed hypothesis testing setup where peripheral nodes send
quantized data to the fusion center in a memoryless fashion. The _expected_
number of bits sent by each node under the null hypothesis is kept limited. We
characterize the optimal decay rate of the mis-detection (type-II error)
probability provided that false alarms (type-I error) are rare, and study the
tradeoff between the communication rate and maximal type-II error decay rate.
We resort to rate-distortion methods to provide upper bounds to the tradeoff
curve and show that at high rates lattice quantization achieves near-optimal
performance. We also characterize the tradeoff for the case where nodes are
allowed to record and quantize a fixed number of samples. Moreover, under sum-
rate constraints, we show that an upper bound to the tradeoff curve is
obtained with a water-filling solution.

###### Index Terms:

distributed hypothesis testing, memoryless quantization, expected rate
constraints, type-II error exponent, rate-distortion methods, lattice
quantization

##  I Introduction

A present-day engineering challenge is to cope with amounts of data whose
processing requirements exceed the processing capabilities of a single device.
Therefore, many state-of-the-art designs share the workload (e.g., data
acquisition) among peripheral nodes (e.g., sensors). One particular challenge
is the distributed hypothesis testing problem. In this paradigm, peripheral
nodes acquire partially informative observations and transmit their
information to a fusion center. The center aims to infer the state-of-nature
by aggregating information from different nodes. If there were no
communication constraints, the fusion center would be able to observe the raw
data and perform an optimal test. However, in practice, there may exist
communication constraints due to channel imperfections or processing
capabilities of the nodes.

To illustrate this situation, consider a vehicle equipped with a collision
avoidance system that relies on vehicular communication. In such a
communication scheme, information can be received from other vehicles
(vehicle-to-vehicle, V2V) or from other objects such as mobile phones, base
stations etc. (vehicle-to-everything, V2X). The collision avoidance system is
activated upon detection of a possible collision — this risky state might be
associated with the alternative hypothesis in a binary hypothesis testing
setting. V2V and V2X communication protocols, e.g., IEEE 802.11p [2], limit
the data rate. Hence, the devices in proximity are required to compress or
quantize the data they possess before sending it to the vehicle.

The example above can be cast into a canonical distributed hypothesis testing
problem under communication constraints. Among many possible ways of
restricting communication, we choose to limit the _average_ number of bits
sent under riskless or ordinary state, which associates with the null
hypothesis; and we seek the fundamental limits of a distributed hypothesis
testing problem under such assumption. We focus on the case where nodes
compress their data with practically-appealing memoryless quantization
procedures. More precisely, under such setting, we initially focus on the
single-node case and when the average number of bits sent is at most $R$ under
the null hypothesis:

  * •

we characterize the optimal decay rate of the type-II error probability under
vanishing type-I error probability, given by $\theta^{*}(R)$, in Theorem 1 of
Section IV-A;

  * •

we obtain an upper bound to $\theta^{*}(R)$ via rate-distortion methods and
consequently characterize an unachievable region in Corollary 1 of Section
IV-B;

  * •

we show that with simple lattice-quantization, the upper bound can be
approached within $\frac{1}{2}\log_{2}(\frac{\pi e}{2})\approx 1.047$ bits in
Theorem 4 of Section V-A;

  * •

we provide the upper bound $\theta_{k}(R)$ for the $k$-dimensional vector
quantization case in Section V-B.

The results for the single-node case are then extended to multiple nodes in
Section VI, where the problem is formulated under individual communication
constraints at nodes, together with a sum-rate constrained formulation.

##  II Related Work

The present work contains flavors from both information theoretic and signal
processing approaches. We review the related work under these two approaches
respectively.

###  II-A Information Theoretic Approaches

Distributed hypothesis testing under communication constraints is a long-
standing problem studied by the information theory community. An early work by
Ahlswede and Csiszár [3] underlies most of the subsequent developments. It is
therefore instructive to review their problem setup for a better understanding
of the subsequent work. Their setup — henceforth referred to as the
Ahlswede–Csiszár setup — is as follows. A remote node possesses a sequence
$X^{n}$, while the decision maker possesses a $Y^{n}$. The pair
$(X^{n},Y^{n})$ is independent and identically distributed (i.i.d.) with
distribution $P$ under the null hypothesis ($\mathcal{H}_{0}$) and with
distribution $Q$ under the alternative hypothesis ($\mathcal{H}_{1}$). The
decision maker estimates the true hypothesis by using both $Y^{n}$ and an
$nR$-bit side information conveyed by the remote node. The communication
constraint is “hard” in the sense that $X^{n}$ is represented with exactly
$nR$ bits under both hypotheses. Their aim is to find the fastest exponential
decay rate of the type-II error given a prescribed type-I error probability,
say $0<\epsilon<1$. It turns out that the fastest decay rate does not depend
on $\epsilon$, and it is fully characterized for the special case of
dependence testing, i.e., when $Q_{XY}=P_{X}P_{Y}$ where $P_{X}$, $P_{Y}$ are
the marginals of $X$ and $Y$ under $\mathcal{H}_{0}$. The characterization of
the optimal decay rate for the general case turns out to be more involved and
it is still unknown although some upper and lower bounds exist.

The Ahlswede–Csiszár setup motivated various subsequent works on distributed
hypothesis testing. For instance, [4] presents tighter lower bounds on the
optimal decay rate for the Ahlswede–Csiszár setup and further extends the
formulation to include zero-rate compression (see also [5]), as well as to
include the compression of $Y^{n}$. The lower bound on the best possible decay
rate for the general case is improved in [6]. One may refer to [7] for a
comprehensive survey on the literature considering Ahlswede–Csiszár setup and
its variants. Subsequent works on communication-constrained hypothesis testing
include studies on tradeoffs between type-I and type-II error exponents [8,
9], performance under finite-blocklength regime [10], and under noisy
communication [11, 12, 13, 14]. Further extensions of this problem include
interactive protocols [15, 16, 17], privacy constraints [18, 19, 20, 21, 22,
23], the additional task of data reconstruction at the receiver [24]. For
dependence testing, [25] concludes that binning schemes are optimal; whereas
the recent work [26] shows that the performance can be improved with
sequential methods for the general case.

The works cited above elaborate on the “hard” communication constraints, as
Ahlswede and Csiszár did. A recent strand of works relax the “hard”
communication constraints and study the dependence testing problem by limiting
the _expected_ number of bits sent. A partial list of the studies adopting
this perspective is [27, 28, 29, 30, 31, 32]. The current study is also in
line with this perspective. We remark that for the special case of dependence
testing, since the $X$ marginals are the same under both hypotheses, the
expected number of bits conveyed does not depend on the true hypothesis. Our
work, on the other hand, focuses on the general case. Hence, given a strategy,
the expected number of bits sent might differ under the null and alternative
hypotheses; introducing an inherent asymmetry to the problem. We choose to
limit the _expected rate under the null hypothesis $\mathcal{H}_{0}$_. This
choice aligns with the view that $\mathcal{H}_{1}$ is a rare high-risk event
and necessary communication must take place to detect this event with high
probability. A more detailed discussion on such choice is given in Section
III.

Information theoretic approaches could be criticized because they use high-
dimensional vector quantization, i.e., the entire block $X^{n}$ should be
observed before being represented with $nR$ bits. A system designed as such
may not be desirable for timing-crucial applications, as the decision maker is
kept oblivious of the side information until time $n$. Furthermore, for large
$n$, such a system is not memory-efficient as the remote node records the
whole past and it might also be computationally expensive to compress $X^{n}$.
These observations suggest that low-dimensional quantization could be of
interest for low-latency and memory-efficient applications. Such quantization
procedures for distributed detection are often studied in the signal
processing literature.

###  II-B Signal Processing Approaches

As mentioned, signal processing approaches are usually centered around low-
dimensional quantizer designs. The scalar quantization procedures specialized
for the task of binary hypothesis testing aim to keep the dissimilarity
between the distributions of the quantizer output under $\mathcal{H}_{0}$ and
$\mathcal{H}_{1}$ as large as possible while representing the output only with
$R$ bits. Various methods for evaluating the dissimilarity include calculation
of the Kullback–Leibler divergence $D(\cdot||\cdot)$ — the optimal type-II
error rate under vanishing type-I error [33] or vice versa — or one may
consider the more general Ali–Silvey distances [34] (or equivalently
$f$-divergences [35]) which prove useful for a variety of signal detection
problems [36]. Notable early studies on quantization for binary hypothesis
testing include [37, 38, 39].

Finding the optimal quantizer is in general a daunting task and there is no
standard machinery to obtain such quantizers. However, there exists iterative
methods to find suboptimal quantizers as in [39], or studies on the high-rate
quantization regime [40, 41, 42]. Some extremal properties of likelihood-ratio
quantizers is given in [43]. Quantizer designs based on privacy and secrecy
constraints are studied in [44, 45]. Error resilient designs are studied in
[46, 47, 48], as well as Byzantine resilient designs in [49]. A recent work on
multilevel quantization is [50].

A similar trend to that in the information theoretic studies is also observed
in the signal processing literature — the works cited above rely on “hard”
communication constraints. Different from the existing signal processing
literature, we study the fundamental limits under memoryless (scalar)
quantization with _expected_ rate constraints under $\mathcal{H}_{0}$, and
provide impossibility results for the subject case. Namely, if the _expected_
rate under $\mathcal{H}_{0}$ is limited to $R$ bits, then the type-II error
rate cannot be greater than $\theta^{*}(R)$ — defined in Theorem 1 — under
vanishing type-I error probability.

Notation: Random variables are denoted with uppercase letters whereas their
realizations are written lowercase, e.g., $X_{n}$ and $x_{n}$.
$\mathcal{B}{(\mathbb{R})}$ denotes the Borel algebra of $\mathbb{R}$. For
probability measures $P$ and $Q$, $D(P||Q)$ denotes the Kullback–Leibler (KL)
divergence and $E_{P}[\cdot]$, $H_{P}(\cdot)$, $I_{P}(\cdot\,;\cdot)$ denote
the expectation, entropy, and mutual information under $P$ respectively. All
logarithms are taken with natural base unless explicitly stated.

##  III Problem Formulation

In this work, we study a canonical distributed hypothesis testing setup where
$m$ peripheral nodes communicate with a fusion center (Figure 1). At each time
instant $t$, the node $i$ observes data arising from distribution $P^{(i)}$
under the null hypothesis $\mathcal{H}_{0}$, and from distribution $Q^{(i)}$
under the alternative hypothesis $\mathcal{H}_{1}$. We assume that for all
$i$, $P^{(i)}$ is absolutely continuous with respect to $Q^{(i)}$. That is, if
$Q^{(i)}(B)=0$, then $P^{(i)}(B)=0$ for any $B\in\mathcal{B}(\mathbb{R})$. The
data is independent across nodes, and across time under both hypotheses.
Moreover, the data is identically distributed across time. Therefore, the
joint distribution of the network until time $t$ and under $\mathcal{H}_{0}$
can be characterized on rectangles in $\mathbb{R}^{tm}$ as follows:

$P(B^{t})=\prod_{\tau=1}^{t}\prod_{i=1}^{m}P^{(i)}([a_{\tau}^{(i)},b_{\tau}^{(i)}])$
(1)

where $B_{\tau}\mathrel{\mathop{\mathchar
58\relax}}=[a_{\tau}^{(1)},b_{\tau}^{(1)}]\times\dots\times[a_{\tau}^{(m)},b_{\tau}^{(m)}]$
and $B^{t}\mathrel{\mathop{\mathchar 58\relax}}=B_{1}\times\dots\times B_{t}$
are rectangles in $\mathbb{R}^{m}$ and $\mathbb{R}^{tm}$ respectively. By a
standard extension theorem, [51, Theorem 1.7], $P$ can be extended uniquely to
$\mathcal{B}(\mathbb{R}^{tm})$. Under $\mathcal{H}_{1}$, since the
independence assumptions are the same, the joint distribution of the network
is given exactly by (1), with $P$’s replaced by $Q$’s.

Figure 1: A representation of the setup studied in this work. The peripheral
nodes are drawn as blue circles, and the fusion center (FC) is drawn as the
red square. At each time instant $t$, node $i$ sends its compressed score
$f_{t}^{(i)}(L_{t}^{(i)})$, which is solely based on the fresh observation
$X_{t}^{(i)}$.

A key assumption in our setup is that _each node $i$ is only aware of
$P^{(i)}$ and $Q^{(i)}$, and the fusion center does not have any knowledge
about the statistics of the data observed at the nodes_. Such assumption
distinguishes our work from many information-theoretic approaches. For
instance, in the Ahlswede–Csiszár setup, both the remote observer and the
decision maker are aware of the joint distribution. By contrast, our oblivious
fusion center trusts the nodes blindly and sums the “scores” sent by them.
Knowing this behavior of the center, nodes prepare their scores accordingly.
An example of a score might be the log-likelihood ratio (LLR) of the data
observed at time $t$, i.e., node $i$ calculates the LLR $L_{t}^{(i)}$ based on
its freshly observed data $X_{t}^{(i)}$ as

$L_{t}^{(i)}\mathrel{\mathop{\mathchar
58\relax}}=\log\frac{dP}{dQ}(X_{t}^{(i)}),$ (2)

sets the score $S_{t}^{(i)}=L_{t}^{(i)}$, and passes it through the
communication link. Note that the above LLR is well-defined as a Radon–Nikodym
derivative due to the absolute continuity of $P^{(i)}$ with respect to
$Q^{(i)}$. Suppose each node behaves similarly, i.e., calculates and sends its
LLR. Since the data is independent across nodes and across time, under such a
strategy, the fusion center receives the sufficient statistic
$\sum_{\tau=1}^{t}\sum_{i=1}^{m}L_{\tau}^{(i)}$ and is able to perform an
optimal test, i.e., a Neyman–Pearson test. However, $P^{(i)}$ and $Q^{(i)}$
can be continuous in general and it is impossible to (i) calculate the LLR
with an arbitrarily high precision and (ii) represent the score losslessly
with a finite number of bits. Due to these restrictions, the nodes are
required to compress (quantize) the data they receive, and send their scores
with a finite number of bits at each time instant. The finite-bit score sent
by node $i$ at time $t$ is represented by $S_{t}^{(i)}$ and the fusion center
performs a threshold test based on the average score

$\bar{S}_{t}\mathrel{\mathop{\mathchar
58\relax}}=\frac{1}{t}\sum_{\tau=1}^{t}\sum_{i=1}^{m}S_{\tau}^{(i)},$ (3)

with the estimate being the result of the following test:

$\hat{\mathcal{H}}=\begin{cases}\mathcal{H}_{0},&\bar{S}_{t}\geq\eta_{t}\\\
\mathcal{H}_{1},&\text{else}\end{cases}$ (4)

where $\eta_{t}$ is a threshold that can depend on $t$. In addition to the
finite-bit constraint, the rate of communication between the nodes and the
center may be subject to limitations. As mentioned in the previous section, in
this work, we study the distributed hypothesis testing problem under the
following communication constraint: _The average number of bits sent under
$\mathcal{H}_{0}$ must be kept limited._

######  Remark 1.

The communication constraint is not symmetric, i.e., there is no constraint
under $\mathcal{H}_{1}$. This aligns well with many real-world scenarios when
$\mathcal{H}_{1}$ represents a high-risk situation in which the system is
allowed to violate communication constraints in order to identify the risk —
responding to an emergency takes priority over communication constraints —
recall the collision avoidance example at the beginning of this manuscript.
This view of $\mathcal{H}_{1}$ also implies that the type-II error must be
very rare. In fact, in many hypothesis testing problems, it is desired that
the type-II error decays exponentially. This is the approach we follow for the
rest of this work. ∎

###  III-A Memoryless Quantization and the Communication Constraint

For simplicity, we focus on a single node $i$ at the moment and omit the
symbol $(i)$ from the superscripts. In this section, we formally define the
memoryless quantization procedures that map the LLR $L_{t}$ to the score
$S_{t}$, and the communication constraints for such quantization procedures.
We first give the definition of a simple function.

######  Definition 1 (Simple function, [52]).

A function on $\mathbb{R}$ that takes finitely many values is called a simple
function. More precisely, let $\alpha_{1},\dots,\alpha_{n}$ be the distinct
values of a simple function $f$, then any such $f$ is represented as

$f(l)=\sum_{k=1}^{n}\alpha_{k}\mathbbm{1}\\{l\in B_{k}\\}$ (5)

where $B_{1},\dots,B_{k}\in\mathcal{B}({\mathbb{R}})$ form a partition of
$\mathbb{R}$. ∎

We let $S_{t}=f_{t}(L_{t})$ with a simple function $f_{t}$. Observe that such
procedures are _memoryless_ — quantization at time $t$ depends only on the
data arriving at time $t$, and does not depend on past. From Definition 1, it
is clear that $S_{t}$’s are discrete random variables. For example, if $f_{t}$
is set as in (5), then for $1\leq k\leq n$:

$P(S_{t}=\alpha_{k})=P(L_{t}\in B_{k})$ (6)

and the discrete entropy of $S_{t}$ under $\mathcal{H}_{0}$ is defined as

$H_{P}(S_{t})\mathrel{\mathop{\mathchar
58\relax}}=-\sum_{k=1}^{n}P(S_{t}=\alpha_{k})\log P(S_{t}=\alpha_{k})$ (7)

with $0\log 0\mathrel{\mathop{\mathchar 58\relax}}=0$. A discrete random
variable can be compressed _losslessly_ with a binary code whose expected
length is $\ell$, which is bounded as [53, 54]

$H_{P}(S_{t})\log_{2}e-\log_{2}(H_{P}(S_{t})\log_{2}e+1)-\log_{2}e\leq\ell\leq
H_{P}(S_{t})\log_{2}e.$ (8)

Therefore, the peripheral node can compress its LLR $L_{t}$ with a simple
function $f_{t}$, and can represent its score $S_{t}=f_{t}(L_{t})$ with an
average number of bits less than $H_{P}(S_{t})\log_{2}e$ under
$\mathcal{H}_{0}$. If we impose

$\frac{1}{t}\sum_{\tau=1}^{t}H_{P}(S_{\tau})\leq R/\log_{2}e,$ (9)

all scores until time $t$ can be represented with an expected number of bits
less than $Rt$ under $\mathcal{H}_{0}$; and the average number of bits sent
over the communication link is kept limited to at most $R$ bits. Constraints
formed as in (9) are then suitable candidates for being the communication
constraint in our distributed hypothesis testing setting.

######  Remark 2.

The memoryless quantization procedures we consider are practically appealing
since the peripheral devices can be designed in a memory-efficient manner.
Moreover, the assumption that each node only knows their own $P$’s and $Q$’s
allows independent design of the peripheral nodes, as opposed to the joint
design of all sensors which may be impractical. Note that without independence
across the nodes, joint design might be necessary. We assume that the network
subject to this study is designed such that the peripheral nodes have a
spatial configuration that yields, or at least approximates, independence
across nodes. ∎

###  III-B Performance Criteria under Memoryless Quantization

As mentioned earlier, the fusion center decides over the hypotheses based on
the threshold test given in (4). Under this test, the type-I and type-II error
probabilities are defined respectively as

$\begin{split}\alpha_{t}&\mathrel{\mathop{\mathchar
58\relax}}=P(\bar{S}_{t}<\eta_{t})\\\ \beta_{t}&\mathrel{\mathop{\mathchar
58\relax}}=Q(\bar{S}_{t}\geq\eta_{t})\end{split}.$ (10)

For an $\epsilon>0$, we assume that the fusion center sets the threshold to

$\eta_{t}=\frac{1}{t}\sum_{\tau=1}^{t}E_{P}[S_{t}]-\epsilon.$ (11)

Recalling that the fusion center is unaware of the statistics at the nodes,
one might argue that this choice of $\eta_{t}$ is not valid. However, such
adjustment is without loss of generality: If the nodes send the centered
version of the scores, i.e., $S_{t}-E_{P}[S_{t}]$, and if the fusion center
performs the test based on $\eta_{t}=-\epsilon$, the performance of the scheme
will be equivalent to the scheme where the threshold is chosen as in (11).
Note that setting $\eta_{t}=-\epsilon$ does not require any knowledge on $P$’s
and $Q$’s. Moreover, the discrete entropy $H_{P}(S_{t})$ does not change under
any shift and the communication constraints are not violated. It turns out
that the choice in (11) achieves the optimal curve $\theta^{*}(R)$ — to be
defined in Theorem 1 — and we keep this choice for the rest of the work.

##  IV Best Performance Under Memoryless Quantization

###  IV-A Boundary of the Achievable Region

In view of Remark 1, our aim is to drive the type-II error probability to zero
as fast as possible while ensuring the type-I error probability vanishes. In
particular, the type-II error probability must decay exponentially. A suitable
definition of an achievable region in line with this perspective is given as
follows.

######  Definition 2.

Given $P$ and $Q$, $(R,\theta)$ is an achievable pair if there exists a
sequence $\\{f_{t}\\}$ of simple functions and thresholds $\\{\eta_{t}\\}$
such that

  * (a)

$\frac{1}{t}\sum_{\tau=1}^{t}H_{P}(S_{\tau})\leq R$, for all $t$

  * (b)

$\lim_{t\to\infty}\alpha_{t}=0$

  * (c)

$\liminf_{t\to\infty}\frac{1}{t}\log\frac{1}{\beta_{t}}\geq\theta$

where $S_{t}=f_{t}(L_{t})$ is the quantized LLR, and $\alpha_{t}$, $\beta_{t}$
are the type-I and type-II errors defined in (10). ∎

Note that the communication constraint imposed in Definition 2(a) is in terms
of _nats_ for notational simplicity. The achievable region is then defined as
the set of the achievable pairs $(R,\theta)$. The theorem below characterizes
the boundary of this region in two parts.

######  Theorem 1.

Let $\theta^{*}(R)\mathrel{\mathop{\mathchar
58\relax}}=\sup\\{\theta\mathrel{\mathop{\mathchar 58\relax}}(R,\theta)\text{
achievable}\\}$ and define

$\displaystyle\theta_{t}(R)\mathrel{\mathop{\mathchar
58\relax}}=\sup_{\\{f_{1},\dots,f_{t}\\}\in\mathcal{F}_{t}(R)}\frac{1}{t}\sum_{\tau=1}^{t}\bigg{(}E_{P}[S_{\tau}]-\log
E_{P}[e^{S_{\tau}-L_{\tau}}]\bigg{)}$ (12)

where $\mathcal{F}_{t}(R)$ is the set of all simple real-valued functions
$f_{1},\dots,f_{t}$ on $(\mathbb{R},\mathcal{B}(\mathbb{R}))$ such that
$\frac{1}{t}\sum_{\tau=1}^{t}H_{P}(S_{\tau})\leq R$. Then, the following
statements hold.
(i) Let

$\theta_{1}(R)=\sup_{f_{1}\in\mathcal{F}_{1}(R)}E_{P}[S_{1}]-\log
E_{P}[e^{S_{1}-L_{1}}].$ (13)

Then $\lim_{t\to\infty}\theta_{t}(R)$ equals to the upper concave envelope
$\breve{\theta}_{1}(R)$ of $\theta_{1}(R)$.
(ii)

$\displaystyle\phantom{\mbox{(ii)}}\quad\theta^{*}(R)=\lim_{t\to\infty}\theta_{t}(R)=\breve{\theta}_{1}(R).$

###### Proof.

See Appendix -A. ∎

Theorem 1 provides the boundary of the achievable region in a variational form
that is reminiscent of a single-letter characterization. However, the
optimization problem (13) has a non-convex domain, which makes
$\mathcal{F}_{1}(R)$ a non-convex set. We will therefore consider a relaxed
version of the optimization problem (13) in the next section.

###  IV-B An Upper Bound on the Boundary of the Achievable Region

In order to relax the problem (13), we (i) allow randomized quantization, and
(ii) modify the communication constraint to $I_{P}(S_{1};L_{1})\leq R$, where
$I_{P}(S_{1};L_{1})$ is the mutual information between $S_{1}$ and $L_{1}$
under $\mathcal{H}_{0}$. Note that since $H_{P}(S_{1})\geq
I_{P}(S_{1};L_{1})$, $H_{P}(S_{1})\leq R$ implies $I_{P}(S_{1};L_{1})\leq R$,
hence the communication constraints indeed become less stringent. Moreover,
the randomized quantization procedures can be represented as channels
$p_{V|U}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{U}\times\mathbb{R}\to\mathbb{R}_{+}$ where for each $u$,
$p_{V|U}(v,u)$ is a probability mass function on the finite set
$\mathcal{U}\subset\mathbb{R}$. We further relax the problem by taking
$\mathcal{U}=\mathbb{R}$, hence the possible channels become
$p_{V|U}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{B}(\mathbb{R})\times\mathbb{R}\to\mathbb{R}_{+}$, where for
each $u$, $p_{V|U}(v,u)$ is a probability measure on $\mathbb{R}$. Adopting
the modifications we have just described, problem (13) then becomes

$\begin{split}\theta_{U}(R)\mathrel{\mathop{\mathchar
58\relax}}=\sup_{p_{V|U}}&\quad E_{P}[V]-\log E_{P}[\exp(V-U)]\\\
\text{s.t.}&\quad I_{P}(U;V)\leq R\end{split}$ (14)

where $U$ has the same distribution as the LLR $L_{1}$. Observe that as $R$
increases, the optimization domain is enlarged and thus $\theta_{U}(R)$ cannot
decrease; which shows that $\theta_{U}(R)$ is non-decreasing. Moreover,
$\theta_{U}(R)$ also captures the behavior at the extremes. Intuitively, if
$R\to\infty$, then $V$ can be set equal to $U$ and $\theta_{U}$ becomes

$E_{P}[U]=E_{P}\bigg{[}\log\frac{dP}{dQ}\bigg{]}=D(P||Q)$ (15)

which is known from Stein’s lemma [33] as the optimal type-II error exponent
under vanishing type-I error probability. This intuitive argument will be made
rigorous in Lemma 2. On the other extreme, if $R=0$, then the best possible
choice is to set $V$ equal to a constant $v$ and $\theta_{U}$ becomes

$v-\log E_{P}\bigg{[}\bigg{(}\frac{dP}{dQ}\bigg{)}^{-1}\bigg{]}-v=0,$ (16)

which is consistent with the fact that the center is not able to infer the
true hypothesis when there is no communication.

Another useful characterization of $\theta_{U}$ is given by the following
lemma.

######  Lemma 1.

Let

$\begin{split}\tilde{\theta}_{U}(R)\mathrel{\mathop{\mathchar
58\relax}}=\sup_{p_{V|U}}&\quad E_{P}[V]-E_{P}[\exp(V-U)]+1\\\
\text{s.t.}&\quad I_{P}(U;V)\leq R.\end{split}$ (17)

Then, $\theta_{U}(R)=\tilde{\theta}_{U}(R)$.

###### Proof.

See Appendix -B. ∎

Observe that $-\tilde{\theta}_{U}$ is given by

$\begin{split}-\tilde{\theta}_{U}(R)=\inf_{p_{V|U}}&\quad-
E_{P}[V]+E_{P}[\exp(V-U)]-1\\\ \text{s.t.}&\quad I_{P}(U;V)\leq R.\end{split}$
(18)

We highlight the equivalence between $-\tilde{\theta}_{U}(R)$ and the
distortion-rate function with the distortion function $d(u,v)=-v+e^{v-u}-1$.
Since it is known that this curve is convex, $-\tilde{\theta}_{U}(R)$ is also
convex and consequently, $\tilde{\theta}_{U}(R)$ is concave. We then make use
of the characterization in Lemma 1 and conclude that $\theta_{U}(R)$ is
concave as well.

We end this section with the following corollary, which states that
$\theta_{U}$ is a concave upper bound to the boundary of the achievable region
given by $\theta^{*}(R)$.

######  Corollary 1.

$\theta_{U}(R)\geq\breve{\theta}_{1}(R)=\theta^{*}(R)$.

###### Proof.

As (14) is a relaxation of (13), we know that
$\theta_{U}(R)\geq\theta_{1}(R)$. In addition, $\theta_{U}(R)$ is concave;
then it must also dominate the concave envelope $\breve{\theta}_{1}(R)$ of
$\theta_{1}(R)$. ∎

######  Remark 3.

As stated before, we have shown the equivalence of $\theta_{U}$ and
$\tilde{\theta}_{U}$ in Lemma 1. Although it might be tempting to work with
$\tilde{\theta}_{U}$, as it is the optimal value of an optimization problem
with a linear objective, (17) takes a smaller value than (14) if a generic
$p_{V|U}$ is substituted; thus leading to tighter bounds. This is due to the
inequality $\log x\leq x-1$. In view of this observation, we work with the
formulation (14) in the sequel. ∎

###  IV-C Calculating the Upper Bound $\theta_{U}$

In this section, and for the rest of the work, we assume all the expectations
(including the mutual information $I_{P}(\cdot\,;\cdot)$) are taken under $P$,
and we omit it from the subscripts for brevity. Applying Jensen’s inequality
to the objective function in (14), we have

$\begin{split}&E[V]-\log E[\exp(V-U)]\\\ &\leq
E[V]-E[V-U]=D(P||Q).\end{split}$ (19)

Thus, it is also convenient to study the gap to $D(P||Q)$. The gap function
$\delta_{U}(R)\mathrel{\mathop{\mathchar 58\relax}}=D(P||Q)-\theta_{U}(R)$ is
then straightforwardly given by

$\begin{split}\delta_{U}(R)=\inf_{p_{V|U}}&\quad\log E[\exp(V-U)]-E[V-U]\\\
\text{s.t.}&\quad I(U;V)\leq R.\end{split}$ (20)

Note that since $\theta_{U}$ is concave and non-decreasing, $\delta_{U}(R)$ is
convex and non-increasing by definition, and the following lemma explains the
limiting behavior as $R\to\infty$.

######  Lemma 2.

$\lim_{R\to\infty}\delta_{U}(R)=0$. Consequently, $\lim_{R\to\infty}$
$\theta_{U}(R)=D(P||Q)$.

###### Proof.

See Appendix -C. ∎

We highlight that Lemma 2 holds even if $P$ and $Q$ do not admit densities.
Now, we intend to derive an upper bound for $\delta_{U}$. Let
$Z\mathrel{\mathop{\mathchar 58\relax}}=V-U$. Then (20) is equivalent to

$\begin{split}\delta_{U}(R)=\inf_{p_{Z|U}}&\quad\log E[\exp(Z)]-E[Z]\\\
\text{s.t.}&\quad I(U;U+Z)\leq R.\end{split}$ (21)

A simple upper bound to $\delta_{U}(R)$ can be obtained by choosing $Z$ as a
Gaussian random variable independent of $U$. With such choice, we have

$\begin{split}I(U;U+Z)&=h(U+Z)-h(U+Z|U)\\\ &=h(U+Z)-h(Z|U)\\\ &=h(U+Z)-h(Z)\\\
&\leq\frac{1}{2}\log\bigg{(}1+\frac{\operatorname{\mathrm{Var}}(U)}{\operatorname{\mathrm{Var}}(Z)}\bigg{)}\end{split}$
(22)

where $h(\cdot)$ denotes the differential entropy. Observe that $U+Z$ always
admits a probability density; $U$ need not be continuous. However we assume
$U$ is square integrable such that $\operatorname{\mathrm{Var}}(U)$ exists.
Furthermore, for a Gaussian $Z$

$\begin{split}\log
E[\exp(Z)]-E[Z]&=E[Z]+\log(e^{\frac{1}{2}\operatorname{\mathrm{Var}}(Z)})-E[Z]\\\
&=\frac{1}{2}\operatorname{\mathrm{Var}}(Z).\end{split}$ (23)

Denoting the variance of $Z$ by $\sigma^{2}$, observe that the parametric
curve

$R=\frac{1}{2}\log\bigg{(}1+\frac{\operatorname{\mathrm{Var}}(U)}{\sigma^{2}}\bigg{)},\quad\delta=\frac{1}{2}\sigma^{2}$
(24)

lies above $\delta_{U}(R)$, and equivalently

$\delta_{U}(R)\leq\frac{\operatorname{\mathrm{Var}}(U)}{e^{2R}-1}=\mathrel{\mathop{\mathchar
58\relax}}g_{U}(R).$ (25)

The bound (25) is however not tight at low rates. Observe that as $R\to 0$,
the right-hand side of (25) tends to infinity although we know that the gap
$\delta$ can at most be $D(P||Q)$ — see (19). The bound can be strengthened as
follows: Since we know $\delta_{U}$ is convex with $\delta_{U}(0)=D(P||Q)$,
and $\delta_{U}(R)\leq g_{U}(R)$, any line segment connecting $(0,D(P||Q))$
with the curve $g_{U}(R)$ lies above $\delta_{U}(R)$. Among such line
segments, the one which is tangent to $g_{U}(R)$ gives the tightest bound.

After obtaining this simple upper bound, we direct our attention to the
calculation of $\delta_{U}(R)$. Note that the objective function in (21) is
concave. This is because $\log E[e^{Z}]$ is concave, and $E[Z]$ is linear in
$p_{Z|U}$. Hence, it is a concave minimization problem, and might a priori
require examining all extreme points of the feasible set. However, we now show
that the problem can be formulated as a convex minimization, circumventing the
combinatorial challenge. First, note that both the objective function and the
constraint in (21) remain unchanged if we add a constant to $Z$. Thus,
centering $Z$ does not change the feasible region in (21). Consequently, we
can add the constraint $E[Z]=0$ to our problem without changing its value,
which yields an equivalent formulation of (21):

$\begin{split}\delta_{U}(R)=\inf_{p_{Z|U}}&\quad\log E[\exp(Z)]\\\
\text{s.t.}&\quad I(U;U+Z)\leq R\\\ &\quad E[Z]=0\end{split}$ (26)

Any infimizer of the above problem also infimizes the optimization problem
with the objective function $E[\exp(Z)]$, and the optimal value of the former
problem is the logarithm of the optimal value of the latter. Further note that
the objective function becomes linear when changed to $E[\exp(Z)]$. The latter
problem is formulated as the convex program

$\begin{split}\Delta_{U}(R)\mathrel{\mathop{\mathchar
58\relax}}=\inf_{p_{Z|U}}&\quad E[\exp(Z)]\\\ \text{s.t.}&\quad I(U;U+Z)\leq
R\\\ &\quad E[Z]=0\end{split}$ (27)

with $\log\Delta_{U}(R)=\delta_{U}(R)$. Observe that $\Delta_{U}(R)$ is
convex, non-decreasing, and is finite at every $R\geq 0$ — check the feasible
choice $Z=-U+E[U]$ and observe $\Delta_{U}(R)\leq
E[e^{-U}]e^{E[U]}=e^{D(P||Q)}$. Therefore, $\Delta_{U}(R)$ can be expressed as

$\Delta_{U}(R)=\sup_{\lambda>0}\mathcal{L}(\lambda)-\lambda R$ (28)

where

$\begin{split}\mathcal{L}(\lambda)\mathrel{\mathop{\mathchar
58\relax}}=\inf_{p_{Z|U}}&\quad E[\exp(Z)]+\lambda I(U;U+Z)\\\
\text{s.t.}&\quad E[Z]=0.\end{split}$ (29)

Each $\lambda>0$ describes a straight line $\Delta+\lambda
R=\mathcal{L}(\lambda)$ in the $(R,\Delta)$ plane. $\Delta_{U}(R)$ is the
supremum in the $\Delta$ axis of these lines. The generalized inverse of
$\Delta_{U}(R)$, $R_{U}(\Delta)$, is then the supremum of these lines in the
$R$ axis,

$\begin{split}R_{U}(\Delta)&=\sup_{\lambda>0}\frac{1}{\lambda}\mathcal{L}(\lambda)-\frac{1}{\lambda}\Delta\\\
&=\sup_{\eta>0}\eta\mathcal{L}\bigg{(}\frac{1}{\eta}\bigg{)}-\eta\Delta\end{split}$
(30)

which is identical to the following convex problem for $\Delta>1$.

$\begin{split}R_{U}(\Delta)=\inf_{p_{Z|U}}&\quad I(U;U+Z)\\\ \text{s.t.}&\quad
E[\exp(Z)]\leq\Delta\\\ &\quad E[Z]=0.\end{split}$ (31)

An important direction is to obtain a closed-form lower bound for $R_{U}$,
which consequently gives a lower bound for $\delta_{U}$. Such a lower bound
characterizes an unachievable region as $\delta_{U}$ is a lower bound to the
boundary curve of the achievable region.

######  Assumption 1.

For the rest of the work, we assume that $U$ admits a probability density
$p_{U}$. Hence the differential entropy $h(U)$ is well-defined (but not
necessarily finite). ∎

Note that (31) is exactly the same as the rate-distortion formulation except
for the additional constraint $E[Z]=0$. This special structure allows us to
derive a lower bound based on maximum-entropy principles, which also led
Shannon to derive the well-known lower bound for the rate-distortion problem
under mean-square distortion [55]. We shall use the same machinery as well.
Note that

$\begin{split}I(U;U+Z)&=h(U)-h(U|U+Z)\\\ &=h(U)-h(Z|U+Z)\\\ &\geq
h(U)-h(Z)\end{split}$ (32)

where the last inequality is due to the property “conditioning reduces
entropy”. Hence, we obtain

$\begin{split}R_{U}(\Delta)\geq\inf_{p_{Z|U}}&\quad h(U)-h(Z)\\\
\text{s.t.}&\quad E[\exp(Z)]\leq\Delta\\\ &\quad E[Z]=0.\end{split}$ (33)

Since the new objective function depends only on the marginal of $Z$, the
problem above is equivalent to finding a maximum-entropy distribution $p_{Z}$
that satisfies the constraints $E[e^{Z}]\leq\Delta$ and $E[Z]=0$. The problem
can now be formulated as

$\sup_{p_{Z}}\ h(Z)\quad\text{s.t.}\quad E[e^{Z}]\leq\Delta,\quad E[Z]=0.$
(34)

The entropy maximizing distribution can be found with the methods in [56,
Chapter 12] and is given by

$f(z)=\frac{\beta^{\alpha}}{\Gamma(\alpha)}\exp(\alpha z-\beta
e^{z}),\quad\alpha,\beta>0.$ (35)

Observe that $f(z)$ is the distribution of the logarithm of a Gamma random
variable, i.e., $Z=\log G$ where $G\sim\text{Gamma}(\alpha,\beta)$. The
following entities have closed form expressions:

$\begin{split}E[e^{Z}]&=\frac{\alpha}{\beta}\\\
E[Z]&=\psi(\alpha)-\log\beta\\\
h(Z)&=\log\Gamma(\alpha)-\alpha\psi(\alpha)+\alpha\end{split}$ (36)

where $\Gamma(.)$ and $\psi(.)$ are gamma and digamma functions respectively.
Note that $\log E[e^{Z}]-E[Z]=\log\alpha-\psi(\alpha)$ and does not depend on
$\beta$. Substituting (36) into (33), we have just proved

######  Lemma 3.

Define the parametric curve

$\begin{split}\kern 1.00006pt\vbox{
\hbox{\kern-1.00006pt$R$\kern-1.00006pt}\kern 0.6458pt\hrule
height=0.4pt}\kern
1.00006pt_{U}(\alpha)&=h(U)-\log\Gamma(\alpha)+\alpha\psi(\alpha)-\alpha,\\\
\delta(\alpha)&=\log\alpha-\psi(\alpha),\quad\alpha>0,\end{split}$ (37)

where $\Gamma(.)$, $\psi(.)$ are gamma and digamma functions respectively.
Then $R$${}_{U}(\delta)\leq R_{U}(\delta)$. ∎

In comparison, the parametric curve in (24) gives the upper bound

$\kern 1.00006pt\vbox{\hrule height=0.4pt\kern
0.6458pt\hbox{\kern-1.00006pt$R$\kern-1.00006pt}}\kern
1.00006pt_{U}(\delta)=\frac{1}{2}\log\bigg{(}1+\frac{\operatorname{\mathrm{Var}}(U)}{2\delta}\bigg{)}.$
(38)

Both $\kern 1.00006pt\vbox{\hrule height=0.4pt\kern
0.6458pt\hbox{\kern-1.00006pt$R$\kern-1.00006pt}}\kern 1.00006pt_{U}$ and
$\kern 1.00006pt\vbox{ \hbox{\kern-1.00006pt$R$\kern-1.00006pt}\kern
0.6458pt\hrule height=0.4pt}\kern 1.00006pt_{U}$ are depicted in Figure 2 for
a Gaussian $U$. As discussed before, the upper bound $\kern
1.00006pt\vbox{\hrule height=0.4pt\kern
0.6458pt\hbox{\kern-1.00006pt$R$\kern-1.00006pt}}\kern 1.00006pt_{U}(\delta)$
is not tight at low rates since we know that $R_{U}(\delta)=0$ at
$\delta=D(P||Q)$, and the convexity of $R_{U}(\delta)$ enables tightening the
upper bound by drawing the tangent line from the point $(D(P||Q),0)$ to $\kern
1.00006pt\vbox{\hrule height=0.4pt\kern
0.6458pt\hbox{\kern-1.00006pt$R$\kern-1.00006pt}}\kern 1.00006pt_{U}$. This
straight line bound is denoted as SL in Figure 2.

Figure 2: Bounds for $R_{U}$ curve for the case where $X\sim\mathcal{N}(0,1)$
under $\mathcal{H}_{0}$ and $X\sim\mathcal{N}(\mu,1)$ under $\mathcal{H}_{1}$
for $\mu=\sqrt{20}$. $U$ has the same distribution as the LLR
$L\sim\mathcal{N}(10,20)$. The lower bound $\kern 1.00006pt\vbox{
\hbox{\kern-1.00006pt$R$\kern-1.00006pt}\kern 0.6458pt\hrule
height=0.4pt}\kern 1.00006pt_{U}$ is drawn with blue color and the shaded
region underneath is unachievable. The upper bound $\kern
1.00006pt\vbox{\hrule height=0.4pt\kern
0.6458pt\hbox{\kern-1.00006pt$R$\kern-1.00006pt}}\kern 1.00006pt_{U}$ is drawn
with red color, and its tightened version is drawn with a dashed line, denoted
as SL. The true $R_{U}$ curve lies between $\kern 1.00006pt\vbox{
\hbox{\kern-1.00006pt$R$\kern-1.00006pt}\kern 0.6458pt\hrule
height=0.4pt}\kern 1.00006pt_{U}$ and SL.

###  IV-D Asymptotic Behavior of $R_{U}(\delta)$

Although Figure 2 suggests that $\kern 1.00006pt\vbox{
\hbox{\kern-1.00006pt$R$\kern-1.00006pt}\kern 0.6458pt\hrule
height=0.4pt}\kern 1.00006pt_{U}$ and $\kern 1.00006pt\vbox{\hrule
height=0.4pt\kern 0.6458pt\hbox{\kern-1.00006pt$R$\kern-1.00006pt}}\kern
1.00006pt_{U}$ match closely at high rates, it is not evident if they tend to
infinity at the same rate. Therefore, the asymptotic behavior of the exact
$R_{U}$ is still unknown. We will characterize this behavior in this section.
We first derive another upper bound than $\kern 1.00006pt\vbox{\hrule
height=0.4pt\kern 0.6458pt\hbox{\kern-1.00006pt$R$\kern-1.00006pt}}\kern
1.00006pt_{U}$ and show that this new upper bound behaves the same as the
lower bound $\kern 1.00006pt\vbox{
\hbox{\kern-1.00006pt$R$\kern-1.00006pt}\kern 0.6458pt\hrule
height=0.4pt}\kern 1.00006pt_{U}$ asymptotically. Once again, refer to (22)
and observe for a Gaussian $Z$ with variance $v$ and independent of $U$,

$\begin{split}I(U;U+Z)=h(U+\sqrt{v}\tilde{Z})-h(\tilde{Z})-\frac{1}{2}\log{v},\end{split}$
(39)

where $\tilde{Z}$ is a standard Gaussian random variable. We obtain an upper
bound to $h(U+\sqrt{v}\tilde{Z})$ with a different method. Suppose $U$ has a
differentiable probability density $p_{U}$. We use De Brujin’s identity [56,
Chapter 17], which states

$\frac{\partial}{\partial
v}h(U+\sqrt{v}\tilde{Z})=\frac{1}{2}J(U+\sqrt{v}\tilde{Z}),$ (40)

where

$J(X)\mathrel{\mathop{\mathchar
58\relax}}=E\bigg{[}\Big{(}\frac{\partial}{\partial x}\log
p_{X}(x)\Big{)}^{2}\Big{|}_{x=X}\bigg{]}$ (41)

is the Fisher information of a random variable $X$ with differentiable density
$p_{X}$. We then resort to Taylor’s theorem which implies

$h(U+\sqrt{v}\tilde{Z})\leq h(U)+\frac{v}{2}\sup_{s\geq
0}J(U+\sqrt{s}\tilde{Z}).$ (42)

A well-known convolution inequality for Fisher information states [56, Chapter
17] for random variables $X$ and $Y$ with differentiable densities

$\frac{1}{J(X+Y)}\geq\frac{1}{J(X)}+\frac{1}{J(Y)}.$ (43)

Therefore,

$\begin{split}h(U+\sqrt{v}\tilde{Z})&\leq h(U)+\frac{v}{2}\sup_{s\geq
0}\frac{J(U)J(\sqrt{s}\tilde{Z})}{J(U)+J(\sqrt{s}\tilde{Z})}\\\
&\stackrel{{\scriptstyle(a)}}{{=}}h(U)+\frac{v}{2}\sup_{s\geq
0}\frac{J(U)}{sJ(U)+1}\\\
&\stackrel{{\scriptstyle(b)}}{{=}}h(U)+\frac{v}{2}J(U)\end{split}$ (44)

where (a) follows from $J(\sqrt{s}\tilde{Z})=\frac{1}{s}$, and (b) follows
from the fact that $J(U)$ is always non-negative. Substituting this upper
bound into (39), we obtain

$\begin{split}I(U;U+Z)&\leq
h(U)+\frac{v}{2}J(U)-h(\tilde{Z})-\frac{1}{2}\log{v}\\\
&=h(U)+\frac{v}{2}J(U)-\frac{1}{2}\log(2\pi ev).\end{split}$ (45)

Referring to (24), we have $v=2\delta$ and obtain another upper bound to
$R_{U}$ as

$R_{U}(\delta)\leq h(U)+\delta J(U)-\frac{1}{2}\log(4\pi e\delta).$ (46)

We intend to obtain a matching lower bound using $\kern 1.00006pt\vbox{
\hbox{\kern-1.00006pt$R$\kern-1.00006pt}\kern 0.6458pt\hrule
height=0.4pt}\kern 1.00006pt_{U}$. To this end, we use the following
inequalities valid for $\alpha>0$ [57, 5.11(ii)]:

$\begin{split}\log\Gamma(\alpha)\leq\alpha\log\alpha-\alpha-\frac{1}{2}\log\alpha+\frac{1}{2}\log(2\pi)+\frac{1}{12\alpha}\\\
\log\alpha-\frac{1}{2\alpha}-\frac{1}{12\alpha^{2}}\leq\psi(\alpha)\leq\log\alpha-\frac{1}{2\alpha}.\end{split}$
(47)

Using (47) we obtain from (37)

$\begin{split}\kern 1.00006pt\vbox{
\hbox{\kern-1.00006pt$R$\kern-1.00006pt}\kern 0.6458pt\hrule
height=0.4pt}\kern 1.00006pt_{U}(\alpha)\geq h(U)-\frac{1}{2}\log(2\pi
e\alpha^{-1})-\frac{1}{6\alpha},\quad\delta(\alpha)\geq\frac{1}{2\alpha}.\end{split}$
(48)

Thus,

$R_{U}(\delta)\geq\kern 1.00006pt\vbox{
\hbox{\kern-1.00006pt$R$\kern-1.00006pt}\kern 0.6458pt\hrule
height=0.4pt}\kern 1.00006pt_{U}(\delta)\geq h(U)-\frac{1}{2}\log(4\pi
e\delta)-\frac{\delta}{3}.$ (49)

Comparing (49) with (46), one can characterize the high-rate behavior of
$R_{U}$. We conclude this section with the following theorem that gives the
asymptotic behavior.

######  Theorem 2.

$\lim_{\delta\to 0}R_{U}(\delta)-h(U)+\frac{1}{2}\log(4\pi e\delta)=0.$ (50)

∎

##  V High-Rate Regime and Performance under Vector Quantization

###  V-A High-Rate Lattice Quantization

Until this point, we have investigated the behavior of $R_{U}$ and
characterized its exact asymptotic behavior. However, we have not yet proposed
a concrete quantization scheme that attains $(R,\delta)$ pairs comparable with
$R_{U}$. In this section, we will show that with simple quantization schemes,
$R_{U}$ can be closely approached at high rates. More specifically, we study
lattice quantization procedures — a detailed reference is [58]. As we focus on
scalar (memoryless) quantization in one dimension, the quantization procedures
we consider are simply described as

$q_{r}(U)\mathrel{\mathop{\mathchar
58\relax}}=2r\arg\min_{k\in\mathbb{Z}}|U-2kr|$ (51)

where $r$ is the covering radius. Consequently, $V=q_{r}(U)$ is a quantized
version of $U$ with $|V-U|\leq r$. A visual representation is given in Figure
3.

Figure 3: A visualization of $q_{r}(\cdot)$. The output is set to $2kr$ (drawn
as red dots) whenever the input falls into the bin (separated with vertical
lines) corresponding to $k$. Each bin is of radius $r$.

At this point, we would like to relate the radius $r$ to the gap $\delta$.
Referring to (20), under lattice quantization $q_{U}(r)$, the gap is given by

$\begin{split}\delta&=\log E[e^{V-U}]-E[V-U]\\\ &\leq E[e^{V-U}]-E[V-U]-1\\\
&=E[e^{Z}-Z-1]\end{split}$ (52)

and since $|Z|\leq r$ surely, $e^{Z}-Z-1\leq e^{r}-r-1$. Consequently,

$\delta\leq e^{r}-r-1,$ (53)

which suggests that in the small-$r$ regime, $\delta$ behaves quadratically.
In fact, if $r\leq D$ for a constant $D$, then

$\begin{split}\delta&\leq e^{r}-r-1=\sum_{k=2}^{\infty}\frac{r^{k}}{k!}\\\
&\leq\frac{r^{2}}{D^{2}}\sum_{k=2}^{\infty}\frac{D^{k}}{k!}=\frac{r^{2}}{D^{2}}(e^{D}-D-1).\end{split}$
(54)

The next step is to relate $r$ with $H(V)$, which is an upper bound to the
expected length of an optimal lossless code as discussed in (8). Under mild
regularity conditions on the distribution of $U$, the asymptotic behavior of
$H(V)$ when $r\to 0$ can be characterized.

######  Theorem 3 ([59]).

Suppose $H(\lfloor U\rfloor)<\infty$. Then,

$\lim_{r\to 0}H(V)+\log(2r)=h(U).$ (55)

∎

Using the above theorem, we have

$\begin{split}H(V)&\leq h(U)-\frac{1}{2}\log(4\pi e\delta)+\frac{1}{2}\log(\pi
e(e^{D}-D-1)D^{-2})+f(r)\end{split}$ (56)

where $f(r)$ is a function such that $\lim_{r\to 0}f(r)=0$. Comparing the
above with the asymptotic behavior of $R_{U}$ given in Theorem 2, we conclude
that with high-rate lattice quantization, one can approach the boundary of the
achievable region with at most $\frac{1}{2}\log_{2}(\pi e(e^{D}-D-1)D^{-2})$
bits of difference. As $D\to 0$, the difference term tends to
$\frac{1}{2}\log_{2}\big{(}\frac{\pi e}{2}\big{)}\approx 1.047$ bits.
Remembering that we work in the high-rate regime, i.e., we are allowed to send
a large number of bits, a $1.047$-bit gap from the optimal curve does not seem
to be significant. We summarize our results on the high-rate quantization as
follows.

######  Theorem 4.

Suppose $H(\lfloor U\rfloor)$ is finite. Then with one-dimensional lattice
quantization of sufficiently small radius, the lower bound to the optimal
curve $R_{U}$ can be approached within $\frac{1}{2}\log_{2}(\frac{\pi
e}{2})\approx 1.047$ bits. ∎

Although Theorem 4 quantifies the gap in the limit $r\to 0$, one may also be
interested to find an upper bound on $H(V)$ for strictly positive values of
$r$. To this end, one might need more stringent regularity conditions than
those of Theorem 3 and work with nicely-behaved distributions. For the moment,
consider $\tilde{V}=V+W$, where $W$ is independent of $V$ and uniformly
distributed in $[-r,r]$. Observe that the probability density of $\tilde{V}$
is a “quantized” version of the probability density of $U$. If $U$ has a
nicely-behaved distribution and if $r$ is small, then the distribution of
$\tilde{V}$ will not be very different from that of $U$; which is desirable
for the sake of analysis. The family of the aforementioned nicely-behaved
distributions are defined as follows.

######  Definition 3 ($v$-regular density, [60]).

Given $v\mathrel{\mathop{\mathchar 58\relax}}\mathbb{R}\to\mathbb{R}$, a
continuous and differentiable density function $p$ is called $v$-regular if
$\big{|}\frac{d}{du}p(u)\big{|}\leq v(u)p(u)$. ∎

In [60, Theorem 8], it has been proved that if $U$ has a $v$-regular density,
then

$H(V)\leq h(U)-\log 2r+2rC_{U}(r)$ (57)

where $C_{U}(r)$ is a function of $r$ depending on the density of $U$ and on
the function $v$. Furthermore, if $v$ is Lipschitz-continuous almost
everywhere and if $E[v(U)]$ is finite, then $C_{U}(r)$ can be shown to be
bounded for finite $r$ — see Appendix -D. In particular, if $v$ has Lipschitz
constant $L$,

$C_{U}(r)\leq\sqrt{J(U)}+2Lr.$ (58)

We then obtain the following parametric curve

$\begin{split}R^{(L)}_{U}(r)&\mathrel{\mathop{\mathchar 58\relax}}=h(U)-\log
2r+2r\sqrt{J(U)}+4Lr^{2}\\\ \delta(r)&\mathrel{\mathop{\mathchar
58\relax}}=e^{r}-r-1\end{split}$ (59)

which is an upper bound to the $(R,\delta)$ pairs achievable with lattice
quantization. Figure 4 illustrates the comparison of the lattice upper bound
$R_{U}^{(L)}$ and the lower bound $\kern 1.00006pt\vbox{
\hbox{\kern-1.00006pt$R$\kern-1.00006pt}\kern 0.6458pt\hrule
height=0.4pt}\kern 1.00006pt_{U}$ at high rates. The 1.047-bit gap in between
is clearly observed.

######  Remark 4.

As discussed in [60], the gap $\frac{1}{2}\log_{2}\big{(}\frac{\pi
e}{2}\big{)}\approx 1.047$ is due to the covering inefficiency of the one-
dimensional lattice. If we perform a similar analysis under the mean-square
distortion, the gap turns out to be exactly the same [60]. This is expected as
the gap $\delta=\log(E[e^{V-U}])-E[V-U]$ — despite not being a distortion
function — behaves like $r^{2}/2$ for small $r$. Observe that for sufficiently
smooth densities, the mean-square error under lattice quantization behaves
exactly the same for sufficiently small $r$. ∎

Figure 4: High-rate behaviors of the lower bound $\kern 1.00006pt\vbox{
\hbox{\kern-1.00006pt$R$\kern-1.00006pt}\kern 0.6458pt\hrule
height=0.4pt}\kern 1.00006pt_{U}$, and the curve $R_{U}^{(L)}$ achievable with
one-dimensional lattice quantization. Same hypothesis testing setup in Figure
2 is considered, where $U$ has a Gaussian distribution. It is not difficult to
see that a Gaussian distribution is $v$-regular. The 1.047-bit difference
between $R_{U}^{(L)}$ and $\kern 1.00006pt\vbox{
\hbox{\kern-1.00006pt$R$\kern-1.00006pt}\kern 0.6458pt\hrule
height=0.4pt}\kern 1.00006pt_{U}$, mentioned in Theorem 4, is visible.

In light of our results in this section, the remote node’s strategy in the
high-rate regime is apparent. At time $t$, the node (i) calculates its LLR
$L_{t}$, (ii) obtains the lattice-quantized score $S_{t}=q_{r}(L_{t})$, and
(iii) sends $S_{t}$ with an optimal variable-length lossless code designed for
$P$, i.e., for $\mathcal{H}_{0}$. This strategy ensures the approach to the
optimal curve within $1.047$ bits.

One might ask what is the expected number of bits sent under $\mathcal{H}_{1}$
although the code is designed for $\mathcal{H}_{0}$. It is known that if the
true distribution of the quantized score $S_{t}$ is given by $Q(S_{t})$, then
an optimal lossless code designed for $P(S_{t})$ yields the expected number of
bits at most

$\begin{split}H_{Q}(S_{t})\log_{2}e+D(Q(S_{t})||P(S_{t}))\log_{2}e\leq
H_{Q}(S_{t})\log_{2}e+D(Q||P)\log_{2}e,\end{split}$ (60)

where the inequality is due to the data processing inequality. Hence, if $Q$
is also absolutely continuous with respect to $P$, $D(Q||P)$ is finite, and
the expected number of bits sent under $\mathcal{H}_{1}$ is finite as well.

We end this section by raising the following question: “Is it possible to
eliminate the $\frac{1}{2}\log_{2}\big{(}\frac{\pi e}{2}\big{)}$ gap with more
efficient lattice coverings?” For high-dimensions, it is known that covering-
efficient lattices exist [60]. Hence, an obvious attempt would be to allow the
quantization of multiple samples, i.e., at time $tk$, the remote node records
$L_{(t-1)k+1},\dots,L_{tk}$ and sends the $k$-dimensional lattice-quantized
version. Although this approach might alleviate the covering inefficiency
problem, it is not certain that for such procedures the $R_{U}$ curve remains
the same. We shall study in the next section the behavior of $R_{U}$ when
vector quantization is allowed.

###  V-B Best Performance under Vector Quantization

This section addresses the problem of quantizing multiple samples instead of
one. We continue to study memoryless schemes, that is, at time $tk$, the
$k$-tuple of LLRs $(L_{(t-1)k+1},\dots,L_{tk})$ is quantized and sent. We
first highlight a key observation in the proof of Theorem 1 — given in
Appendix -A. Observe that for a choice of quantization function $f$, the
(optimal) Neyman–Pearson test pertaining to the quantized $S_{t}=f(L_{t})$
yields the type-II error rate $D(P(S)||Q(S))$ and the rate is optimized over
possible $f$’s to obtain $\theta(R)$. Adapting this observation to the vector
quantization case, we have the score $S_{t,k}=f(L_{(t-1)k+1},\dots,L_{tk})$,
where $f\mathrel{\mathop{\mathchar 58\relax}}\mathbb{R}^{k}\to\mathbb{R}$ is a
simple function, and we want to optimize $D(P(S)||Q(S))$ under the constraint
$I(L_{1},\dots,L_{k};S)\leq kR$ to obtain an upper bound. Using the
Donsker–Varadhan representation of $D(P(S)||Q(S))$ as we did in the proof of
Theorem 1, we therefore have the upper bound to the best achievable type-II
error exponent, analogous to (14):

$\begin{split}\tilde{\theta}_{L,k}(R)\mathrel{\mathop{\mathchar
58\relax}}=\frac{1}{k}\bigg{(}\sup_{p_{S|L_{1},\dots,L_{k}}}&E_{P}[S]-\log
E_{P}\Big{[}\exp\Big{(}S-L_{1,k}\Big{)}\Big{]}\bigg{)}\\\ \text{s.t.}&\quad
I_{P}(L_{1},\dots,L_{k};S)\leq kR.\end{split}$ (61)

Define $L_{1,k}\mathrel{\mathop{\mathchar 58\relax}}=L_{1}+\dots+L_{k}$ and
observe that $I_{P}(L_{1,k};S)\leq I_{P}(L_{1},\dots,L_{k};S)$. Hence,

$\begin{split}\theta_{L,k}(R)\mathrel{\mathop{\mathchar
58\relax}}=\frac{1}{k}\bigg{(}\sup_{p_{S|L_{1},\dots L_{k}}}&E_{P}[S]-\log
E_{P}\Big{[}\exp\Big{(}S-L_{1,k}\Big{)}\Big{]}\bigg{)}\\\ \text{s.t.}&\quad
I_{P}(L_{1,k};S)\leq kR\end{split}$ (62)

is an upper bound to $\tilde{\theta}_{L,k}(R)$ as the optimization domain is
enlarged (it is not difficult to show that $\theta_{L,k}$ is in fact equal to
$\tilde{\theta}_{L,k}$). Since both the objective and constraint functions in
(62) only depend on $L_{1,k}$, the feasible set can be reduced to the set of
channels from $L_{1,k}$ to $S$. Hence,

$\begin{split}\theta_{L,k}(R)=\frac{1}{k}\bigg{(}\sup_{p_{S|L_{1,k}}}&E_{P}[S]-\log
E_{P}\Big{[}\exp\Big{(}S-L_{1,k}\Big{)}\Big{]}\bigg{)}\\\ \text{s.t.}&\quad
I_{P}(L_{1,k};S)\leq kR.\end{split}$ (63)

Note the resemblance of (63) to (14). Consequently, all results for one-
dimensional quantization directly translate to the multi-dimensional case and
we obtain the following upper bound to the boundary of the achievable region:

$\begin{split}\theta_{U,k}(R)\mathrel{\mathop{\mathchar
58\relax}}=\frac{1}{k}\bigg{(}\sup_{p_{V|U}}&\quad E_{P}[V]-\log
E_{P}[\exp(V-U_{k})]\bigg{)}\\\ \text{s.t.}&\quad I_{P}(U_{k};V)\leq kR\\\
=\frac{1}{k}\theta_{U_{k}}(k&R)\end{split}$ (64)

where $U_{k}$ is the random variable that has the same distribution as
$L_{1,k}$. Following the same steps we have taken for the one-dimensional
case, we can also obtain the gap function and the rate-gap curve for the
$k$-dimensional case as

$\delta_{U,k}(R)=\frac{1}{k}\delta_{U_{k}}(kR),\quad
R_{U,k}(\delta)=\frac{1}{k}R_{U_{k}}(k\delta).$ (65)

The previously obtained upper and lower bounds for the one-dimensional case
are therefore valid for $k$-dimensional case as well:

$\kern 1.00006pt\vbox{ \hbox{\kern-1.00006pt$R$\kern-1.00006pt}\kern
0.6458pt\hrule height=0.4pt}\kern
1.00006pt_{U,k}(\delta)\mathrel{\mathop{\mathchar 58\relax}}=\frac{1}{k}\kern
1.00006pt\vbox{ \hbox{\kern-1.00006pt$R$\kern-1.00006pt}\kern 0.6458pt\hrule
height=0.4pt}\kern 1.00006pt_{U_{k}}(k\delta)\leq
R_{U,k}(\delta)\leq\frac{1}{k}\kern 1.00006pt\vbox{\hrule height=0.4pt\kern
0.6458pt\hbox{\kern-1.00006pt$R$\kern-1.00006pt}}\kern
1.00006pt_{U_{k}}(k\delta)=\mathrel{\mathop{\mathchar 58\relax}}\kern
1.00006pt\vbox{\hrule height=0.4pt\kern
0.6458pt\hbox{\kern-1.00006pt$R$\kern-1.00006pt}}\kern
1.00006pt_{U,k}(\delta).$ (66)

For various $k$ values, the lower bounds $\kern 1.00006pt\vbox{
\hbox{\kern-1.00006pt$R$\kern-1.00006pt}\kern 0.6458pt\hrule
height=0.4pt}\kern 1.00006pt_{U,k}(\delta)$ and upper bounds $\kern
1.00006pt\vbox{\hrule height=0.4pt\kern
0.6458pt\hbox{\kern-1.00006pt$R$\kern-1.00006pt}}\kern
1.00006pt_{U,k}(\delta)$ are drawn in Figure 5 for the same scenario in Figure
2.

Figure 5: Upper and lower bounds under $k$-dimensional vector quantization,
for $k=1,2,4$. Again, the same setup in Figure 2 is considered. The lower
bounds $\kern 1.00006pt\vbox{ \hbox{\kern-1.00006pt$R$\kern-1.00006pt}\kern
0.6458pt\hrule height=0.4pt}\kern 1.00006pt_{U,k}$ are drawn as solid curves
and the upper bounds $\kern 1.00006pt\vbox{\hrule height=0.4pt\kern
0.6458pt\hbox{\kern-1.00006pt$R$\kern-1.00006pt}}\kern 1.00006pt_{U,k}$ are
drawn as dashed curves. Although all upper and lower bounds are pointwise
decreasing with $k$, it is not certain that the true $R_{U,k}$ curves exhibit
the same behavior.

Observe that $R_{U,k}$’s obey the subadditive relation

$(k+l)R_{U,k+l}(\delta)\leq kR_{U,k}(\delta)+lR_{U,l}(\delta)$ (67)

as the admissible strategies for the quantization of $k+l$ samples include the
strategies that quantize $k$ samples and $l$ samples separately. However, note
that this does not imply $R_{U,k}(\delta)\leq R_{U,l}(\delta)$ for $k\geq l$.
Nevertheless, from a well-known result on subadditive sequences, e.g. [61], we
know

$\lim_{k\to\infty}R_{U,k}(\delta)=\inf_{k}R_{U,k}(\delta)$ (68)

and using the upper bound (38), we obtain for $\delta>0$,

$\begin{split}\lim_{k\to\infty}R_{U,k}(\delta)&\leq\lim_{k\to\infty}\frac{1}{2k}\log\bigg{(}1+\frac{\operatorname{\mathrm{Var}}(U_{k})}{2k\delta}\bigg{)}\\\
&=\lim_{k\to\infty}\frac{1}{2k}\log\bigg{(}1+\frac{\operatorname{\mathrm{Var}}(U_{1})}{2\delta}\bigg{)}\\\
&=0.\end{split}$ (69)

This is in contrast with the classical rate-distortion function as it is
already defined for $k\to\infty$.

Although (69) shows that the lower bound $R_{U,k}$ tends to zero, this is also
true for the true boundary curve. A simple achievability scheme at large $k$
is as follows: Since the remote node records the data until $k$, it can make
its own decision $\mathcal{H}_{0}$ or $\mathcal{H}_{1}$ and send the one-bit
result to the fusion center. The average number of bits sent is then kept
arbitrarily small and since the node makes the estimate of the true hypothesis
based on an optimal test, the type-II error rate will be close to $D(P||Q)$,
which is the best possible decay rate. Although such a design might seem
appealing in terms of the performance of type-II error rate, the peripheral
node needs to have sufficient computational power as a requirement of this
design. Also recall that in the end of Section V-A, we mentioned that the
covering efficiency of lattices may improve at high dimensions. However, (69)
and the strategy we have just described suggest that there is no need for
lattice quantization for high dimensions — the node only sends its one-bit
decision.

##  VI Multiple-Node Case

All the previous results obtained for the single-node case can be extended to
the multiple-node case. This is due to the fact that the data is _independent
across nodes_. To make this extension, we provide a modified definition of
achievable pairs. Recall that at time $t$, node $i$ observes data coming from
$P^{(i)}$ under $\mathcal{H}_{0}$, and from $Q^{(i)}$ under $\mathcal{H}_{1}$;
calculates the LLR $L_{t}^{(i)}$, and compresses it with a simple function
$S^{(i)}_{t}=f_{t}^{(i)}(L_{t}^{(i)})$. Furthermore, as discussed before, if

$\frac{1}{t}\sum_{\tau=1}^{t}H_{P}(S_{\tau}^{(i)})\leq R_{i}/\log_{2}e,$ (70)

then the compressed scores can be sent losslessly with an average number of
bits less than $R_{i}$. After recalling the system dynamics, we provide the
modified version of Definition 2.

######  Definition 4.

Given $\\{P^{(i)}\\}_{i=1}^{m}$ and $\\{Q^{(i)}\\}_{i=1}^{m}$,
$(R_{1},\dots,R_{m},\theta)$ is an achievable pair if there exists $m$
sequences $\\{f_{t}^{(1)}\\},\dots,\\{f_{t}^{(m)}\\}$ of simple functions and
a sequence of thresholds $\\{\eta_{t}\\}$ such that

  * (a)

$\frac{1}{t}\sum_{\tau=1}^{t}H_{P}(S_{\tau}^{(i)})\leq R_{i}$, for all $t$ and
for all $i$

  * (b)

$\lim_{t\to\infty}\alpha_{t}=0$

  * (c)

$\liminf_{t\to\infty}\frac{1}{t}\log\frac{1}{\beta_{t}}\geq\theta$

where $S_{t}^{(i)}=f_{t}^{(i)}(L_{t}^{(i)})$, and $\alpha_{t}$, $\beta_{t}$
are the type-I and type-II errors respectively, defined in (10). ∎

Let $\theta_{t}(R_{1},\dots,R_{m})\mathrel{\mathop{\mathchar
58\relax}}=\sum_{i=1}^{m}\theta_{t}^{(i)}(R_{i})$, where

$\begin{split}\theta^{(i)}_{t}(R_{i})\mathrel{\mathop{\mathchar
58\relax}}=\sup_{\begin{subarray}{c}\\{f^{(i)}_{1},\dots,f^{(i)}_{t}\\}\\\
\in\mathcal{F}_{t}(R_{i})\end{subarray}}\frac{1}{t}\sum_{\tau=1}^{t}\bigg{(}E_{P}[S^{(i)}_{\tau}]-\log
E_{P}[e^{S^{(i)}_{\tau}-L^{(i)}_{\tau}}]\bigg{)}\end{split}$ (71)

is defined as in Theorem 1. Observe that

$\begin{split}\theta_{t}(R_{1},\dots,R_{m})&=\sum_{i=1}^{m}\theta_{t}^{(i)}(R_{i})\\\
&=\sum_{i=1}^{m}\sup_{\begin{subarray}{c}\\{f^{(i)}_{1},\dots,f^{(i)}_{t}\\}\\\
\in\mathcal{F}_{t}(R_{i})\end{subarray}}\frac{1}{t}\sum_{\tau=1}^{t}\bigg{(}E_{P}[S^{(i)}_{\tau}]-\log
E_{P}[e^{S^{(i)}_{\tau}-L^{(i)}_{\tau}}]\bigg{)}\\\
&=\sup_{\begin{subarray}{c}\\{f^{(i)}_{1},\dots,f^{(i)}_{t}\\}\\\
\in\mathcal{F}_{t}(R_{i}),\ i\leq
m\end{subarray}}\frac{1}{t}\sum_{\tau=1}^{t}\sum_{i=1}^{m}\bigg{(}E_{P}[S^{(i)}_{\tau}]-\log
E_{P}[e^{S^{(i)}_{\tau}-L^{(i)}_{\tau}}]\bigg{)}\end{split}$ (72)

and

$\begin{split}\sum_{i=1}^{m}\log
E_{P}[e^{S^{(i)}_{\tau}-L^{(i)}_{\tau}}]&\stackrel{{\scriptstyle(a)}}{{=}}\log
E_{P}[e^{\sum_{i=1}^{m}(S^{(i)}_{\tau}-L^{(i)}_{\tau})}]\\\
&\stackrel{{\scriptstyle(b)}}{{=}}\log
E_{Q}[e^{\sum_{i=1}^{m}S^{(i)}_{\tau}}]\\\
&\stackrel{{\scriptstyle(c)}}{{=}}\sum_{i=1}^{m}\log
E_{Q}[e^{S^{(i)}_{\tau}}]\end{split}$ (73)

where $(a)$, $(c)$ are due to the independence assumption across nodes and
$(b)$ is because
$e^{-\sum_{i=1}^{m}L^{(i)}_{\tau}}=\prod_{i=1}^{m}\frac{dP^{(i)}}{dQ^{(i)}}=\frac{dP}{dQ}$
is the Radon–Nikodym derivative of $P$ with respect to $Q$. Therefore, we have

$\begin{split}\theta_{t}(R_{1},\dots,R_{m})=\sum_{i=1}^{m}\sup_{\begin{subarray}{c}\\{f^{(i)}_{1},\dots,f^{(i)}_{t}\\}\\\
\in\mathcal{F}_{t}(R_{i})\end{subarray}}\frac{1}{t}\sum_{\tau=1}^{t}\bigg{(}E_{P}[S^{(i)}_{\tau}]-\log
E_{Q}[e^{S^{(i)}_{\tau}}]\bigg{)}.\end{split}$ (74)

Comparing (74) with (12) and following exactly the same steps in the proof of
Theorem 1, we obtain the analogous version of Theorem 1 (ii):

$\begin{split}\theta^{*}(R_{1},\dots,R_{m})\mathrel{\mathop{\mathchar
58\relax}}=&\sup\\{\theta\mathrel{\mathop{\mathchar
58\relax}}(R_{1},\dots,R_{m},\theta)\text{ achievable}\\}\\\
=&\lim_{t\to\infty}\theta_{t}(R_{1},\dots,R_{m})\\\
=&\sum_{i=1}^{m}\lim_{t\to\infty}\theta_{t}^{(i)}(R_{i})\\\
=&\sum_{i=1}^{m}\breve{\theta}_{1}^{(i)}(R_{i}),\end{split}$ (75)

which characterizes the boundary of the optimal curve for rate constraints
$(R_{1},\dots,R_{m})$. We also know that $\breve{\theta}_{1}(R)$ is upper
bounded by $\theta_{U}(R)=D(P||Q)-\delta_{U}(R)$ from Corollary 1, hence

######  Corollary 2.

$\theta^{*}(R_{1},\dots,R_{m})\leq\sum_{i=1}^{m}\Big{[}D(P^{(i)}||Q^{(i)})-\delta_{U_{i}}^{(i)}(R_{i})\Big{]}$
(76)

where $U_{i}$ has the same distribution as $L_{1}^{(i)}$, LLR of node $i$. ∎

One might also consider an extension of the problem to sum-rate constraints.
Namely, the communication constraint is redefined as $R_{1}+\dots+R_{m}\leq
R_{\text{sum}}$. The characterization in (75) is readily adapted to sum-rate
constraint as

$\begin{split}\theta^{*}(R_{\text{sum}})\mathrel{\mathop{\mathchar
58\relax}}=\sup\\{&\theta\mathrel{\mathop{\mathchar
58\relax}}(R_{1},\dots,R_{m},\theta)\text{ achievable},\
R_{1}+\dots+R_{m}=R_{\text{sum}}\\}\\\
&\kern-33.0pt=\max_{R_{1}+\dots+R_{m}=R_{\text{sum}}}\sum_{i=1}^{m}\breve{\theta}_{1}^{(i)}(R_{i}),\end{split}$
(77)

and

$\theta^{*}(R_{\text{sum}})\leq\max_{R_{1}+\dots+R_{m}=R_{\text{sum}}}\sum_{i=1}^{m}\theta_{U_{i}}(R_{i}).$
(78)

The $(\theta,R)$ pairs that lie above the curve on right-hand side are
unachievable under the sum-rate constraint. Hence, one may be interested in
the optimal rate sharing that maximizes the right-hand side with an aim to
characterize an unachievable region. We first provide a simple property of a
possible optimal allocation: Intuitively, the optimal rate sharing must not
exclude the more informative nodes.

######  Definition 5 ([62]).

A node $j$ is said to be more informative111Although the definition of more
informativeness is different for $m$-ary hypothesis tests, it is shown in [62]
that for $m=2$, the definition given here is equivalent. than node $i$, and
denoted as $i\prec j$ if there exists a probability transition kernel
$w\mathrel{\mathop{\mathchar
58\relax}}\mathcal{B}(\mathbb{R})\times\mathbb{R}\to\mathbb{R}_{+}$ such that
for all $\mathcal{A}\in\mathcal{B}(\mathbb{R})$

$\int w(\mathcal{A},x)dP^{(j)}(x)=P^{(i)}(\mathcal{A})$ (79)

and

$\int w(\mathcal{A},x)dQ^{(j)}(x)=Q^{(i)}(\mathcal{A}).$ (80)

∎

With the above definition, we have

######  Theorem 5.

Let $\mathcal{R}^{*}\subset\mathbb{R}^{m}$ be the set of optimal allocations
in (78). If $i\prec j$ for some $j$, then $\mathcal{R}^{*}$ contains a
$(R_{1}^{*},\dots,R_{m}^{*})$ such that $R_{i}^{*}>0$ only if $R_{j}^{*}>0$.

###### Proof.

Recall the definition of $\theta_{U_{i}}(R_{i})$:

$\begin{split}\theta_{U_{j}}(R)&=\sup_{\begin{subarray}{c}p_{V|U_{j}}\\\
\text{s.t.}\ I(U_{j};V)\leq R\end{subarray}}\quad E_{P}[V]-\log
E_{P}[\exp(V-U_{j})]\\\
&\stackrel{{\scriptstyle(a)}}{{=}}\sup_{\begin{subarray}{c}p_{V|U_{j}}\\\
\text{s.t.}\ I(U_{j};V)\leq R\end{subarray}}\quad E_{P}[V]-\log
E_{Q}[\exp(V)]\\\
&\geq\sup_{\begin{subarray}{c}p_{V|U_{i}}\circ\,w_{U_{i}|U_{j}}\\\
\text{s.t.}\ I(U_{j};V)\leq R\end{subarray}}\quad E_{P}[V]-\log
E_{Q}[\exp(V)]\\\
&\stackrel{{\scriptstyle(b)}}{{\geq}}\sup_{\begin{subarray}{c}p_{V|U_{i}}\circ\,w_{U_{i}|U_{j}}\\\
\text{s.t.}\ I(U_{i};V)\leq R\end{subarray}}\quad E_{P}[V]-\log
E_{Q}[\exp(V)]\\\ &=\theta_{U_{i}}(R)\end{split}$ (81)

where $(a)$ is due to the measure change as $U_{j}$ is distributed as the
logarithm of the Radon–Nikodym derivative $\frac{dP^{(j)}}{dQ^{(j)}}$ and
$(b)$ is due to the data processing inequality $I(U_{j};V)\leq I(U_{i};V)$ for
the choice of $p_{V|U_{j}}=p_{V|U_{i}}\circ w_{U_{i}|U_{j}}$. Suppose
$R_{i}>0$ and $R_{j}=0$. Since $\theta_{U_{j}}(R)$ pointwise dominates
$\theta_{U_{i}}(R)$, one cannot do worse with the modification
$(R_{i},0)\to(0,R_{i})$. ∎

It might be tempting to think that the optimal allocation assigns
$R_{i}^{*}=0$ if $i\prec j$ for some $j$, as $\theta_{U_{j}}(R)$ dominates
$\theta_{U_{i}}(R)$ pointwise. This is not true in general. Suppose $P^{(i)}$
and $Q^{(i)}$ are obtained by passing $P^{(j)}$ and $Q^{(j)}$ through an
additive Gaussian channel with almost zero noise and suppose $R_{\text{sum}}$
is very large. Allocating all the rate to node $j$ will yield an exponent
close to $D(P^{(i)}||Q^{(i)})$ whereas an equal rate allocation gives an
exponent close to $D(P^{(i)}||Q^{(i)})+D(P^{(j)}||Q^{(j)})$. Therefore, if the
sum-rate constraint is large enough, it is preferred to observe two (almost
uncompressed) independent samples instead of one, which surely increases the
type-II decay rate.

Since $\theta_{U_{i}}$’s (or equivalently $\delta_{U_{i}}$’s) are difficult to
calculate in general, one may consider the optimal allocation based on the
$(R,\delta)$ pairs that lie on the $\kern 1.00006pt\vbox{
\hbox{\kern-1.00006pt$R$\kern-1.00006pt}\kern 0.6458pt\hrule
height=0.4pt}\kern 1.00006pt_{U_{i}}(\delta)$ curves given by the parametric
form (37). Observe that such pairs depend on $U_{i}$ only through shifts of a
parametric curve by its differential entropy $h_{i}\mathrel{\mathop{\mathchar
58\relax}}=h(U_{i})$. Denoting the inverse of $\kern 1.00006pt\vbox{
\hbox{\kern-1.00006pt$R$\kern-1.00006pt}\kern 0.6458pt\hrule
height=0.4pt}\kern 1.00006pt_{U_{i}}(\delta)$ by
$\underline{\delta}_{U_{i}}(R)$, we have thus the property

$\underline{\delta}_{U_{i}}(R)=\underline{\delta}(R-h_{i})$ (82)

where $\underline{\delta}(R)$ is given by the parametric form

$\begin{split}R(\alpha)&=-\log\Gamma(\alpha)+\alpha\psi(\alpha)-\alpha,\\\
\underline{\delta}(\alpha)&=\log\alpha-\psi(\alpha),\quad\alpha>0.\end{split}$
(83)

The sum-rate optimization is then formulated as

$\begin{split}\underline{\theta}^{*}(R_{\text{sum}})&\mathrel{\mathop{\mathchar
58\relax}}=\max_{\sum_{i=1}^{m}R_{i}=R_{\text{sum}}}\sum_{i=1}^{m}\big{[}D(P^{(i)}||Q^{(i)})-\underline{\delta}(R_{i}-h_{i})\big{]}\\\
&=\sum_{i=1}^{m}D(P^{(i)}||Q^{(i)})-\min_{\sum_{i=1}^{m}R_{i}=R_{\text{sum}}}\sum_{i=1}^{m}\underline{\delta}(R_{i}-h_{i}),\end{split}$
(84)

which can be shown to admit a water-filling solution.

######  Lemma 4.

The sum-rate constrained problem (84) has a solution given by

$R_{i}^{*}=(\mu+h_{i})^{+},$ (85)

where $(x)^{+}$ denotes the positive part of $x$; and $\mu$ is a constant
chosen to satisfy the sum-rate constraint
$\sum_{i=1}^{m}R^{*}_{i}=R_{\text{sum}}$.

###### Proof.

First, observe that $\underline{\delta}(R)$ is convex. This is a consequence
of its formulation in (34). As $\underline{\delta}(R)$ is convex, the
Karush–Kuhn–Tucker (KKT) conditions are necessary and sufficient to
characterize the solutions. For the sum-constraint
$\sum_{i=1}^{m}R_{i}=R_{\text{sum}}$, it is known that the KKT conditions are
given by [61]

$\begin{split}\underline{\delta}^{\prime}(R_{i}-h_{i})=\lambda,\quad
R_{i}>0\\\ \underline{\delta}^{\prime}(-h_{i})>\lambda,\quad
R_{i}=0\end{split}$ (86)

for some constant $\lambda$. Since $\underline{\delta}^{\prime}(R_{i}-h_{i})$
is non-decreasing due to the convexity of $\underline{\delta}(R)$, the KKT
conditions are also equivalent to

$\begin{split}R_{i}-h_{i}=\mu,\quad R_{i}>0\\\ -h_{i}>\mu,\quad
R_{i}=0\end{split}$ (87)

with $\mu=R(\alpha)|_{\alpha=1/\lambda}$, and they characterize the claimed
solution in (85). ∎

Although the sum-rate optimization in (84) does not give the exact boundary of
the achievable $(R_{1},\dots,R_{m},\theta)$ pairs,
$\underline{\theta}^{*}(R_{\text{sum}})$ is an upper bound to the boundary.
This implies that no $(R_{1},\dots,R_{m},\theta)$ pair lying above
$\underline{\theta}^{*}(R_{\text{sum}})$ is achievable. A numerical example is
illustrated in Figure 6.

Figure 6: A 3-node instance of the problem. Nodes observe zero-mean Gaussian
data under $\mathcal{H}_{0}$, and with a mean vector
$[\sqrt{0.2},\sqrt{0.4},\sqrt{0.6}]$ under $\mathcal{H}_{1}$. The data has
unit variance under both hypotheses. Then, the LLRs also have Gaussian
distributions with means $[0.1,0.2,0.3]$ and variances $[0.2,0.4,0.6]$ under
$\mathcal{H}_{0}$. The individual
$\underline{\theta}_{U_{i}}(R)\mathrel{\mathop{\mathchar
58\relax}}=D(P^{(i)}||Q^{(i)})-\underline{\delta}_{U_{i}}(R)$ curves are drawn
dashed, whereas the optimal sum-rate curve $\underline{\theta}^{*}(R)$ is
drawn solid. The shaded region is unachievable under sum-rate constraints.

We conclude this section by noting that when the data is not independent
across nodes, the question of how to combine the scores is highly non-trivial
even if there were no communication constraints. Under communication
constraints, the problem for this general case could be of formidable
complexity.

##  VII Discussion

In this work, we have studied a fundamental limit of a distributed hypothesis
testing problem when remote nodes compress their data in a memoryless fashion
and the expected number of bits sent under $\mathcal{H}_{0}$ should be kept
limited to a prescribed quantity $R$. This asymmetric communication constraint
is in line with the view that $\mathcal{H}_{1}$ is a rare high-risk event and
must be detected with high probability. Thus, nodes are allowed to send a
large number of bits under $\mathcal{H}_{1}$. With such a communication
constraint, we characterized the maximum attainable type-II error (i.e., mis-
detection of $\mathcal{H}_{1}$) exponent (Theorem 1) for vanishing type-I
error probability and derived a closed-form upper bound to this error exponent
(Lemma 3).

In the high-rate regime, we show that the upper bound is approached with
simple scalar lattice quantization within $\frac{1}{2}\log_{2}(\pi e/2)\approx
1.047$ bits. This gap is due to the covering inefficiency of the 1-dimensional
lattice and due to the fact that the gap to the optimal error rate $D(P||Q)$
behaves quadratically at high rates. Therefore, it is expected that the
results for the high-rate regime coincide with the results on the rate-
distortion problem for mean-square distortion. This is the reason that the
asymptotic behavior of the rate-gap curve (Theorem 2) is reminiscent of the
Shannon lower bound for the rate-distortion curve under mean-square
distortion. It is also because of this quadratic behavior that one can
approach the lower bound within $\frac{1}{2}\log_{2}(\pi e/2)$ bits under
scalar lattice quantization.

We have also obtained a simple upper bound for the vector quantization case
that can be expressed in terms of its scalar quantization analog (64)–(65).
Hence, the same upper and lower bounds for the scalar case are also valid for
the vector quantization case. We have also shown in (69) that as the dimension
tends to infinity, the rate-gap curve is identically equal to zero for
$\delta>0$. This is consistent with the following simple achievability scheme:
The remote node performs its own Neyman–Pearson test and sends its decision
with one bit. Hence, the fusion center is informed of the optimal decision,
and the average number of bits sent is arbitrarily small.

With an independence assumption across nodes, the results for the single-node
problem can be easily extended to the multiple-node problem, and a simple
upper bound to the optimal type-II error exponent can be obtained in terms of
the sum of individual upper bounds for each remote node. We formulated a sum-
rate constrained problem and studied some of its properties (Theorem 5 and
Lemma 4).

As a final remark, we note that the results for the vector quantization case
are also applicable to the multiple-node case. This implies that when the
dimension tends to infinity, the rate-gap curve will be again equal to zero
and is attained with a simple scheme that is similar to the single-node case:
Each node performs its optimal test and sends the 1-bit result to the fusion
center. The center decides $\mathcal{H}_{1}$ if at least one node decides
$\mathcal{H}_{1}$. This scheme ensures vanishing type-I error probability and
the type-II error exponent is equal to $\sum_{i}D(P^{(i)}||Q^{(i)})$. Hence
the center is able to attain the optimal rate with an arbitrarily low amount
of communication. However, this scheme allows each node to dictate a
$\mathcal{H}_{1}$ decision to the center. This results in a system that is
vulnerable to manipulation. By contrast, schemes with scalar quantization, or
with low-dimensional vector quantization, give the center the opportunity to
detect errors or manipulations and therefore these schemes could be of
interest when faulty or malicious nodes are present.

## References

  * [1] Y. Inan, M. Kayaalp, A. H. Sayed, and E. Telatar, “A fundamental limit of distributed hypothesis testing under memoryless quantization,” in _Proc. IEEE International Conference on Communications (ICC)_ , pp. 1–5, Seoul, May 2022.
  * [2] “IEEE standard for information technology–part 11: Wireless LAN medium access control (MAC) and physical layer (PHY) specifications,” _IEEE Std 802.11-2012_ , pp. 1–2793, 2012.
  * [3] R. Ahlswede and I. Csiszár, “Hypothesis testing with communication constraints,” _IEEE Transactions on Information Theory_ , vol. 32, no. 4, pp. 533–542, 1986.
  * [4] T. Han, “Hypothesis testing with multiterminal data compression,” _IEEE Transactions on Information Theory_ , vol. 33, no. 6, pp. 759–772, 1987.
  * [5] H. Shalaby and A. Papamarcou, “Multiterminal detection with zero-rate data compression,” _IEEE Transactions on Information Theory_ , vol. 38, no. 2, pp. 254–267, 1992.
  * [6] H. Shimokawa, T. S. Han, and S. Amari, “Error bound of hypothesis testing with data compression,” in _Proc. IEEE International Symposium on Information Theory_ , 1994, pp. 114–.
  * [7] T. S. Han and S. Amari, “Statistical inference under multiterminal data compression,” _IEEE Transactions on Information Theory_ , vol. 44, no. 6, pp. 2300–2324, 1998.
  * [8] T. Han and K. Kobayashi, “Exponential-type error probabilities for multiterminal hypothesis testing,” _IEEE Transactions on Information Theory_ , vol. 35, no. 1, pp. 2–14, 1989.
  * [9] N. Weinberger and Y. Kochman, “On the reliability function of distributed hypothesis testing under optimal detection,” _IEEE Transactions on Information Theory_ , vol. 65, no. 8, pp. 4940–4965, 2019.
  * [10] S. Watanabe, “Neyman-Pearson test for zero-rate multiterminal hypothesis testing,” in _Proc. IEEE International Symposium on Information Theory (ISIT)_ , 2017, pp. 116–120.
  * [11] E. Tuncel, “On error exponents in hypothesis testing,” _IEEE Transactions on Information Theory_ , vol. 51, no. 8, pp. 2945–2950, 2005.
  * [12] S. Sreekumar and D. Gündüz, “Distributed hypothesis testing over discrete memoryless channels,” _IEEE Transactions on Information Theory_ , vol. 66, no. 4, pp. 2044–2066, 2020.
  * [13] M. Wigger and R. Timo, “Testing against independence with multiple decision centers,” in _Proc. International Conference on Signal Processing and Communications (SPCOM)_ , 2016, pp. 1–5.
  * [14] S. Salehkalaibar and M. Wigger, “Distributed hypothesis testing over noisy broadcast channels,” _Information_ , vol. 12, no. 7, 2021. [Online]. Available: https://www.mdpi.com/2078-2489/12/7/268
  * [15] G. Katz, P. Piantanida, and M. Debbah, “Collaborative distributed hypothesis testing,” Jan. 2016, IEEE Trans. on Information Theory (submitted). [Online]. Available: https://hal.archives-ouvertes.fr/hal-01436767
  * [16] Y. Xiang and Y.-H. Kim, “Interactive hypothesis testing against independence,” in _Proc. IEEE International Symposium on Information Theory_ , 2013, pp. 2840–2844.
  * [17] P. Escamilla, M. Wigger, and A. Zaidi, “Distributed hypothesis testing: Cooperation and concurrent detection,” _IEEE Transactions on Information Theory_ , vol. 66, no. 12, pp. 7550–7564, 2020.
  * [18] M. Mhanna and P. Piantanida, “On secure distributed hypothesis testing,” in _Proc. IEEE International Symposium on Information Theory (ISIT)_ , 2015, pp. 1605–1609.
  * [19] S. Sreekumar, D. Gündüz, and A. Cohen, “Distributed hypothesis testing under privacy constraints,” in _Proc. IEEE Information Theory Workshop (ITW)_ , 2018, pp. 1–5.
  * [20] A. Gilani, S. Belhadj Amor, S. Salehkalaibar, and V. Y. F. Tan, “Distributed hypothesis testing with privacy constraints,” _Entropy_ , vol. 21, no. 5, 2019. [Online]. Available: https://www.mdpi.com/1099-4300/21/5/478
  * [21] J. Liao, L. Sankar, V. Y. F. Tan, and F. du Pin Calmon, “Hypothesis testing under mutual information privacy constraints in the high privacy regime,” _IEEE Transactions on Information Forensics and Security_ , vol. 13, no. 4, pp. 1058–1071, 2018.
  * [22] R. Abbasalipour and M. Mirmohseni, “Privacy-aware distributed hypothesis testing in Gray-Wyner network with side information,” _arXiv preprint arXiv:2202.02307_ , 2022.
  * [23] J. Liao, L. Sankar, F. P. Calmon, and V. Y. F. Tan, “Hypothesis testing under maximal leakage privacy constraints,” in _Proc. IEEE International Symposium on Information Theory (ISIT)_ , 2017, pp. 779–783.
  * [24] G. Katz, P. Piantanida, and M. Debbah, “Distributed binary detection with lossy data compression,” _IEEE Transactions on Information Theory_ , vol. 63, no. 8, pp. 5207–5227, 2017.
  * [25] M. S. Rahman and A. B. Wagner, “On the optimality of binning for distributed hypothesis testing,” _IEEE Transactions on Information Theory_ , vol. 58, no. 10, pp. 6282–6303, 2012.
  * [26] S. Watanabe, “On sub-optimality of random binning for distributed hypothesis testing,” 2022. [Online]. Available: https://arxiv.org/abs/2201.13005
  * [27] S. Salehkalaibar and M. Wigger, “Distributed hypothesis testing with variable-length coding,” in _Proc. International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT)_ , 2020, pp. 1–5.
  * [28] M. Hamad, M. Wigger, and M. Sarkiss, “Cooperative multi-sensor detection under variable-length coding,” in _Proc. IEEE Information Theory Workshop (ITW)_ , 2021, pp. 1–5.
  * [29] ——, “Two-hop network with multiple decision centers under expected-rate constraints,” in _Proc. IEEE Global Communications Conference_ , Madrid, Spain: IEEE, Dec. 2021, pp. 1–6. [Online]. Available: https://hal.archives-ouvertes.fr/hal-03349810
  * [30] ——, “Optimal exponents in cascaded hypothesis testing under expected rate constraints,” in _Proc. IEEE Information Theory Workshop (ITW)_ , 2021, pp. 1–6.
  * [31] ——, “Cooperative multi-sensor detection under variable-length coding,” in _ITW 2020: IEEE Information Theory Workshop_ , ser. 2020 IEEE Information Theory Workshop (ITW). Riva del Garda, Italy: IEEE, Apr. 2021, pp. 1–5. [Online]. Available: https://hal.archives-ouvertes.fr/hal-03349654
  * [32] M. Hamad, M. Sarkiss, and M. Wigger, “Benefits of rate-sharing for distributed hypothesis testing,” 2022. [Online]. Available: https://arxiv.org/abs/2202.02282
  * [33] H. Chernoff, “A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations,” _The Annals of Mathematical Statistics_ , vol. 23, no. 4, pp. 493 – 507, 1952. [Online]. Available: https://doi.org/10.1214/aoms/1177729330
  * [34] S. M. Ali and S. D. Silvey, “A general class of coefficients of divergence of one distribution from another,” _Journal of the Royal Statistical Society. Series B (Methodological)_ , vol. 28, no. 1, pp. 131–142, 1966.
  * [35] I. Csiszár and P. Shields, “Information theory and statistics: A tutorial,” _Foundations and Trends® in Communications and Information Theory_ , vol. 1, no. 4, pp. 417–528, 2004. [Online]. Available: http://dx.doi.org/10.1561/0100000004
  * [36] T. Kailath, “The divergence and Bhattacharyya distance measures in signal selection,” _IEEE Transactions on Communication Technology_ , vol. 15, no. 1, pp. 52–60, 1967.
  * [37] S. Kassam, “Optimum quantization for signal detection,” _IEEE Transactions on Communications_ , vol. 25, no. 5, pp. 479–484, 1977.
  * [38] H. Poor and J. Thomas, “Applications of Ali–Silvey distance measures in the design generalized quantizers for binary decision systems,” _IEEE Transactions on Communications_ , vol. 25, no. 9, pp. 893–900, 1977.
  * [39] M. Longo, T. Lookabaugh, and R. Gray, “Quantization for decentralized hypothesis testing under communication constraints,” _IEEE Transactions on Information Theory_ , vol. 36, no. 2, pp. 241–255, 1990.
  * [40] H. Poor, “Fine quantization in signal detection and estimation,” _IEEE Transactions on Information Theory_ , vol. 34, no. 5, pp. 960–972, 1988.
  * [41] R. Gupta and A. Hero, “High-rate vector quantization for detection,” _IEEE Transactions on Information Theory_ , vol. 49, no. 8, pp. 1951–1969, 2003.
  * [42] J. Villard and P. Bianchi, “High-rate vector quantization for the Neyman–Pearson detection of correlated processes,” _IEEE Transactions on Information Theory_ , vol. 57, no. 8, pp. 5387–5409, 2011.
  * [43] J. Tsitsiklis, “Extremal properties of likelihood-ratio quantizers,” _IEEE Transactions on Communications_ , vol. 41, no. 4, pp. 550–558, 1993\.
  * [44] V. S. S. Nadendla and P. K. Varshney, “Design of binary quantizers for distributed detection under secrecy constraints,” _IEEE Transactions on Signal Processing_ , vol. 64, no. 10, pp. 2636–2648, 2016.
  * [45] M. Mhanna, P. Duhamel, and P. Piantanida, “Quantization for distributed binary detection under secrecy constraints,” in _Proc. IEEE International Conference on Communications (ICC)_ , 2016, pp. 1–6.
  * [46] V. Saligrama, M. Alanyali, and O. Savas, “Distributed detection in sensor networks with packet losses and finite capacity links,” _IEEE Transactions on Signal Processing_ , vol. 54, no. 11, pp. 4118–4132, 2006.
  * [47] B. Liu and B. Chen, “Channel-optimized quantizers for decentralized detection in sensor networks,” _IEEE Transactions on Information Theory_ , vol. 52, no. 7, pp. 3349–3358, 2006.
  * [48] L. Cao and R. Viswanathan, “Divergence-based soft decision for error resilient decentralized signal detection,” _IEEE Transactions on Signal Processing_ , vol. 62, no. 19, pp. 5095–5106, 2014.
  * [49] S. Marano, V. Matta, and L. Tong, “Distributed detection in the presence of byzantine attacks,” _IEEE Transactions on Signal Processing_ , vol. 57, no. 1, pp. 16–29, 2009.
  * [50] G. Gül and M. Baßler, “Scalable multilevel quantization for distributed detection,” in _Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2021, pp. 5200–5204.
  * [51] D. Williams, _Probability with Martingales._ , ser. Cambridge mathematical textbooks. Cambridge University Press, 1991\.
  * [52] W. Rudin, _Real and Complex Analysis, 3rd Ed._ USA: McGraw-Hill, Inc., 1987.
  * [53] A. Wyner, “An upper bound on the entropy series,” _Information and Control_ , vol. 20, no. 2, pp. 176–181, 1972. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0019995872903658
  * [54] N. Alon and A. Orlitsky, “A lower bound on the expected length of one-to-one codes,” _IEEE Transactions on Information Theory_ , vol. 40, no. 5, pp. 1670–1672, 1994.
  * [55] C. E. Shannon, _Coding Theorems for a Discrete Source With a Fidelity CriterionInstitute of Radio Engineers, International Convention Record, vol. 7, 1959._ , 1993, pp. 325–350.
  * [56] T. M. Cover and J. A. Thomas, _Elements of Information Theory_. Wiley-Interscience, July 2006.
  * [57] “NIST Digital Library of Mathematical Functions,” http://dlmf.nist.gov/, Release 1.1.5 of 2022-03-15, f. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds. [Online]. Available: http://dlmf.nist.gov/
  * [58] J. Conway and N. Sloane, “Fast quantizing and decoding and algorithms for lattice quantizers and codes,” _IEEE Transactions on Information Theory_ , vol. 28, no. 2, pp. 227–232, 1982.
  * [59] I. Csiszár, “Generalized entropy and quantization problems,” _Trans. Sixth Prague Conference on Inform. Theory etc., Academia, Prague_ , pp. 159–174, 1971.
  * [60] V. Kostina, “Data compression with low distortion and finite blocklength,” in _Proc. Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , 2015, pp. 1127–1134.
  * [61] R. G. Gallager, _Information Theory and Reliable Communication_. USA: John Wiley & Sons, Inc., 1968.
  * [62] D. Blackwell, “Comparison of experiments,” _Berkeley Symposium on Mathematical Statistics and Probability_ , pp. 93–102, 1951.
  * [63] R. T. Rockafellar, _Convex analysis_ , ser. Princeton Mathematical Series. Princeton, N. J.: Princeton University Press, 1970.
  * [64] Y. Polyanskiy and Y. Wu, “Lecture notes on information theory,” _Lecture Notes for ECE563 (UIUC) and_ , vol. 6, no. 2012-2016, p. 7, 2014.

###  -A Proof of Theorem 1

####  -A1 Proof of (i)

Let $\breve{\theta}_{1}(R)$ be the concave envelope of $\theta_{1}(R)$. Recall
$S_{t}=f_{t}(L_{t})$ and since all the expectations are taken under $P$, we
omit $P$ from the subscripts. Also recall

$\theta_{t}(R)=\sup_{\\{f_{1},\dots,f_{t}\\}\in\mathcal{F}_{t}(R)}\frac{1}{t}\sum_{\tau=1}^{t}\bigg{(}E[S_{\tau}]-\log
E[e^{S_{\tau}-L_{\tau}}]\bigg{)}.$

We first show that $\breve{\theta}_{1}(R)\geq\theta_{t}(R)$ for all $t$. Let
us modify the definition of $\theta_{1}(R)$ as

$\begin{split}\theta_{1}(R)=\sup_{f\text{ simple}}&\quad E[S_{1}]\\\
\text{s.t.}&\quad E[e^{S_{1}-L_{1}}]=1\\\ &\quad H(S_{1})\leq R\end{split}$
(88)

since shifting $S_{1}$ does not change the entropy. The supremization is over
simple functions. Similarly, $\theta_{t}(R)$ can be defined as

$\begin{split}\theta_{t}(R)=\sup_{\begin{subarray}{c}f_{1},\dots,f_{t}\\\
\text{simple}\end{subarray}}&\quad\frac{1}{t}\sum_{i=1}^{t}E[S_{i}]\\\
\text{s.t.}&\quad E[e^{S_{i}-L_{i}}]=1,\forall i\leq t\\\
&\quad\frac{1}{t}\sum_{i=1}^{t}H(S_{i})\leq R.\end{split}$ (89)

For any $\\{f_{i}\\}$ in the feasible set of (89), there exists $\\{R_{i}\\}$
with $\frac{1}{t}\sum_{i=1}^{t}R_{i}\leq R$ and $H(S_{i})\leq R_{i}$ for all
$i\leq t$; and consequently $\frac{1}{t}\sum
E[S_{i}]\leq\frac{1}{t}\sum\theta_{1}(R_{i})\leq\breve{\theta}_{1}(R)$. Thus,
$\theta_{t}(R)\leq\breve{\theta}_{1}(R)$.

It remains to prove the reversed inequality for $t\to\infty$, i.e.,
$\theta_{t}(R)\geq\breve{\theta}_{1}(R)-\epsilon$ for large enough $t$, given
$\epsilon>0$. Suppose $\theta_{1}(R)$ is attained in the limit of the sequence
of simple functions $\\{f_{t}^{*}\\}$. This implies for all $\epsilon_{1}>0$,
there exists a simple function $f$ that maps $L_{1}\mapsto S_{1}$ such that
$E[S_{1}]\geq\theta_{1}(R)-\epsilon_{1}$, $E[e^{S_{1}-L_{1}}]=1$ and
$H(S_{1})\leq R$. Carathéodory’s theorem [63, Section 17] ensures that every
point on the concave envelope $\breve{\theta}_{1}(R)$ is achieved by a convex
combination of at most two points on $\theta_{1}(R)$. This implies the
existence of functions $f$, $\tilde{f}$, and $\lambda\in[0,1]$, such that
$\lambda
E[S_{1}]+(1-\lambda)E[\tilde{S}_{1}]\geq\breve{\theta}_{1}(R)-\epsilon_{2}$
for all $\epsilon_{2}>0$, and $\lambda
H(S_{1})+(1-\lambda)H(\tilde{S}_{1})\leq R$. Assume $H(\tilde{S}_{1})\leq R$
without loss of generality. Consider the sequence $\\{f_{t}\\}$ such that
$f_{i}=f$ for $i\leq\lceil\lambda t\rceil$ and $f_{i}=\tilde{f}$ otherwise.
Observe $\frac{1}{t}\sum H(S_{i})\leq R$ and thus
$\theta_{t}(R)\geq\frac{1}{t}\sum
E[S_{i}]\geq\breve{\theta}_{1}(R)-2\epsilon_{2}$ for $t$ large enough. The
proof of part (i) is complete.

In the achievability proof of part (ii), we have to show that the supremizers
of $\theta_{t}(R)$ have to drive $\alpha_{t}\to 0$. For completeness, we
provide the proof here. Take $\\{f_{t}\\}$ as above and use Chebyshev’s
inequality to bound the type-I error probability under the threshold test with
the threshold $\eta_{t}$ chosen as in (11):

$\alpha_{t}=P\bigg{(}\sum_{i=1}^{t}f_{i}(L_{i})<E_{P}[g_{i}(L_{i})]-\epsilon\bigg{)}\leq\frac{\sum_{i=1}^{t}\text{Var}\big{(}f_{i}(L_{i})\big{)}}{\epsilon^{2}t^{2}}$
(90)

Recall that $f_{i}$ is defined to be equal either to $f$ or $\tilde{f}$. As
$f$ and $\tilde{f}$ take finitely many values, the variances of $f(U)$,
$\tilde{f}(U)$ are bounded for any $U$. Therefore,

$\alpha_{t}\leq\frac{\max\Big{\\{}\text{Var}\big{(}f(L_{1})\big{)},\text{Var}\big{(}\tilde{f}(L_{1})\big{)}\Big{\\}}}{\epsilon^{2}t}\to
0,$ (91)

which shows that any sequence in the achievability part of (i) indeed
satisfies the property (b) in Definition 1.

####  -A2 Proof of (ii)

(Achievability) As mentioned, choose
$\eta_{t}=\frac{1}{t}\sum_{\tau=1}^{t}E_{P}[S_{t}]-\epsilon$ as in (11). We
upper bound the type-II error $\beta_{t}$ as

$\begin{split}Q\big{(}\bar{S}_{t}\geq\eta_{t}\big{)}&=Q\big{(}\exp(t\bar{S}_{t})\geq\exp\big{(}t\eta_{t}\big{)}\big{)}\\\
&\stackrel{{\scriptstyle(a)}}{{\leq}}E_{Q}\bigg{[}\exp\Big{(}\sum_{\tau=1}^{t}\big{(}S_{\tau}-E_{P}[S_{\tau}]+\epsilon\big{)}\Big{)}\bigg{]}\\\
&\stackrel{{\scriptstyle(b)}}{{=}}\prod_{\tau=1}^{t}E_{Q}[e^{S_{\tau}}]\exp(-E_{P}[S_{\tau}]+\epsilon)\\\
\end{split}$ (92)

where $(a)$ follows from Markov inequality and $(b)$ follows from independent
processing of LLRs. Therefore,

$\frac{1}{t}\log\frac{1}{\beta_{t}}\geq\frac{1}{t}\sum_{\tau=1}^{t}\big{(}E_{P}[S_{\tau}]-\log
E_{Q}[e^{S_{\tau}}]\big{)}-\epsilon.$ (93)

Optimizing the right-hand side with respect to the choice of $f_{t}$’s
satisfying the communication constraints we have

$\frac{1}{t}\log\frac{1}{\beta_{t}}\geq\sup_{\\{f_{1},\dots,f_{t}\\}\in\mathcal{F}_{t}(R)}\frac{1}{t}\sum_{\tau=1}^{t}E_{P}[S_{\tau}]-\log
E_{Q}[e^{S_{\tau}}]-\epsilon.$ (94)

Consider the transformation $\tilde{S}_{t}=\log\frac{P(S_{t})}{Q(S_{t})}$,
i.e., the LLR of $S_{t}$. Observe that the mapping $L_{t}\mapsto\tilde{S}_{t}$
is a simple function and since $S_{t}$ is discrete, $H(S_{t})\geq
H(\tilde{S}_{t})$ as the mapping $S_{t}\mapsto\tilde{S}_{t}$ is deterministic.
Therefore, communication constraints are still satisfied. Furthermore,
$\tilde{S}_{t}$ is a sufficient statistic and the fusion center is able to
deploy a Neyman–Pearson test based on $\tilde{S}_{t}$’s. It is known from
Donsker–Varadhan representation [64] of divergence that

$D(P||Q)=\sup_{g\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}\to\mathbb{R}}E_{P}[g(X)]-\log E_{Q}[e^{g(X)}]$ (95)

where the supremum is over the set of bounded measurable functions on
$\mathbb{R}$, and is attained at $g(X)=\log\frac{dP}{dQ}$, the logarithm of
the Radon–Nikodym derivative of $P$ with respect to $Q$. We combine (95) with
(94) to obtain

$\frac{1}{t}\log\frac{1}{\beta_{t}}\geq\sup_{\\{f_{1},\dots,f_{t}\\}\in\mathcal{F}_{t}(R)}\frac{1}{t}\sum_{\tau=1}^{t}D(P_{f_{\tau}}||Q_{f_{\tau}})-\epsilon,$
(96)

where $P_{f_{\tau}}\mathrel{\mathop{\mathchar 58\relax}}=P\circ f_{\tau}$ and
$Q_{f_{\tau}}\mathrel{\mathop{\mathchar 58\relax}}=Q\circ f_{\tau}$. It only
remains to show that the supremizers in (96) must drive $\alpha_{t}\to 0$,
which we have already proved at the end of part (i).

(Converse) Now, following similar steps to Stein’s lemma, we apply data
processing inequality twice to see that for any sequence of $f_{t}$’s:

$tD(P||Q)\geq\sum_{\tau=1}^{t}D(P_{f_{\tau}}||Q_{f_{\tau}})\geq
d(\alpha_{t}||1-\beta_{t})$ (97)

where $d(p||q)\mathrel{\mathop{\mathchar
58\relax}}=p\log\frac{p}{q}+\bar{p}\log\frac{\bar{p}}{\bar{q}}$ is the binary
divergence. Hence,

$\sum_{\tau=1}^{t}D(P_{f_{\tau}}||Q_{f_{\tau}})\geq-
h_{e}(\alpha_{t})-\alpha_{t}\log(1-\beta_{t})-(1-\alpha_{t})\log(\beta_{t}),$
(98)

with $h_{e}(p)\mathrel{\mathop{\mathchar 58\relax}}=-p\log p-(1-p)\log(1-p)$.
Suppose $\alpha_{t}\to 0$ and $\beta_{t}$ bounded away from 1. Then, it must
be true that

$\liminf_{t\to\infty}\sup_{\\{f_{1},\dots,f_{t}\\}\in\mathcal{F}_{t}(R)}\frac{1}{t}\sum_{\tau=1}^{t}D(P_{f_{\tau}}||Q_{f_{\tau}})\geq\liminf_{t\to\infty}\frac{1}{t}\log\frac{1}{\beta_{t}}.$
(99)

Taking $\liminf$ and $\epsilon\to 0$ in (96), combining with (99); we
therefore have

$\liminf_{t\to\infty}\sup_{\\{f_{1},\dots,f_{t}\\}\in\mathcal{F}_{t}(R)}\frac{1}{t}\sum_{\tau=1}^{t}\sup_{f_{\tau}}D(P_{f_{\tau}}||Q_{f_{\tau}})=\liminf_{t\to\infty}\frac{1}{t}\log\frac{1}{\beta_{t}}.$
(100)

In other words, $\beta_{t}$ decays with an exponent at least

$\liminf_{t\to\infty}\sup_{\\{f_{1},\dots,f_{t}\\}\in\mathcal{F}_{t}(R)}\frac{1}{t}\sum_{\tau=1}^{t}D(P_{f_{\tau}}||Q_{f_{\tau}}).$
(101)

Recall that the set $\mathcal{F}_{t}(R)$ also includes the supremal function
$g_{t}$’s in the Donsker–Varadhan formulation (95), thus we have

$\begin{split}&\liminf_{t\to\infty}\frac{1}{t}\log\frac{1}{\beta_{t}}\\\
&=\liminf_{t\to\infty}\sup_{\\{f_{1},\dots,f_{t}\\}\in\mathcal{F}_{t}(R)}\frac{1}{t}\sum_{\tau=1}^{t}E_{P}[S_{\tau}]-\log
E_{Q}[e^{S_{\tau}}]\\\
&=\liminf_{t\to\infty}\sup_{\\{f_{1},\dots,f_{t}\\}\in\mathcal{F}_{t}(R)}\frac{1}{t}\sum_{\tau=1}^{t}E_{P}[S_{\tau}]-\log
E_{P}[e^{S_{\tau}-L_{\tau}}]\\\ &=\lim_{t\to\infty}\theta_{t}(R).\end{split}$
(102)

###  -B Proof of Lemma 1

We consider the inequality (94) and obtain a more relaxed lower bound for it
using $\log x\leq x-1$ as

$\frac{1}{t}\log\frac{1}{\beta_{t}}\geq\frac{1}{t}\sum_{\tau=1}^{t}\sup_{f_{\tau}\in\mathcal{F}}E_{P}[S_{\tau}]-E_{Q}[e^{S_{\tau}}]+1-\epsilon.$
(103)

It is known that $D(P||Q)$ can also be represented as

$D(P||Q)=\sup_{g\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}\to\mathbb{R}}E_{P}[g(X)]-E_{Q}[e^{g(X)}]+1.$ (104)

Proceeding similarly to the proof of Theorem 1, we obtain
$\theta_{X}(R)=\tilde{\theta}_{X}(R)$.

###  -C Proof of Lemma 2

Consider the following quantization of $U$. Let
$\mathcal{I}_{n}\mathrel{\mathop{\mathchar 58\relax}}=[-n,n]$ and
$v_{n,k}\mathrel{\mathop{\mathchar 58\relax}}=-n+k2^{-n}$ for $1\leq k\leq
2^{n+1}n$. If $U\in\mathcal{I}_{n}$, then set $V$ as the closest $v_{n,k}$ to
$U$. Otherwise, set $V=0$. Then,

$E[e^{V-U}]\leq
e^{2^{-n}}P(U\in\mathcal{I}_{n})+E[e^{-U}\mathbbm{1}\\{U\notin\mathcal{I}_{n}\\}]$
(105)

and

$E[V-U]\geq-2^{-n}P(U\in\mathcal{I}_{n})-E[U\mathbbm{1}\\{U\notin\mathcal{I}_{n}\\}].$
(106)

Since $E[e^{-U}]=1$, $E[|U|]<\infty$ and $P(U\in\mathcal{I}_{n})\to 1$, the
rightmost terms above tend to zero and for large $n$,

$\log E[e^{V-U}]-E[V-U]$ (107)

is close to zero. The proof will be complete if $I(U;V)<\infty$ for finite
$n$. But since $V$ has finite cardinality, this is indeed the case.

###  -D Boundedness of $C_{U}(r)$

We give the definition of $C_{U}(r)$ suitable for our setting, adopted from
[60]. Recall that the output of the lattice quantization takes values in
$\\{2kr\\}_{k\in\mathbb{Z}}$. Let $I_{k}\mathrel{\mathop{\mathchar
58\relax}}=[(2k-1)r,(2k+1)r]$. Then $C_{U}(r)\mathrel{\mathop{\mathchar
58\relax}}=\sum_{k}P(I_{k})\max_{I_{k}}v(u)$.

Now, observe

$E[v(U)]=\sum_{k}\int_{I_{k}}p(u)v(u)du.$ (108)

Since both $p$ and $v$ are continuous, by the mean value theorem, for each $k$
there exists a $c_{k}$ such that

$\int_{I_{k}}p(u)v(u)du=v(c_{k})\int_{I_{k}}p(u)du.$ (109)

Suppose $v(u)$ is Lipschitz with constant $L$. Since
$a_{k}\mathrel{\mathop{\mathchar 58\relax}}=\arg\max_{u\in I_{k}}v(u)$ has
distance at most $2r$ to $c_{k}$, we have $|a_{k}-c_{k}|\leq 2r$ and
$v(a_{k})\leq 2Lr+v(c_{k})$. Then,

$C_{U}(r)\leq\sum_{k}(2Lr+v(c_{k}))P(I_{k})=2Lr+E[v(U)].$ (110)

Therefore, finiteness of $E[v(U)]$ guarantees the finiteness of $C_{U}$. Also
observe that if $v(u)=|\frac{d}{du}\log p(u)|$ is Lipschitz, and if
$J(U)<\infty$, then $C_{U}(r)$ is upper bounded as

$C_{U}(r)\leq\sqrt{J(U)}+2Lr$ (111)

and is guaranteed to be finite.

For the case when $v$ is not Lipschitz, but is differentiable and its
derivative is Lipschitz with constant $L$, $C_{U}(r)$ can be upper bounded as

$C_{U}(r)\leq E[v(U)]+2rE[|v^{\prime}(U)|]+4Lr^{2}$ (112)

and if $E[v(U)]$, $E[|v^{\prime}(U)|]$ are finite, $C_{U}(r)$ can be bounded
from above. Note that similar arguments generalize to higher order derivatives
of $v$.

As an example, suppose $U$ has a density given by $p(u)=K\exp(-|u|^{3})$, with
$K$ being the appropriate normalization constant. Then since $\frac{d}{du}\log
p(u)=3u^{2}$, one cannot find a Lipschitz $v$. Nevertheless, if one sets
$v(u)=3u^{2}$, $|v^{\prime}(u)|=6|u|$ is Lipschitz with constant $L=6$ and
since $E[U^{2}]$, $E[|U|]$ are finite, $C_{U}(r)$ is bounded according to
(112).