# Improving Group Testing via Gradient Descent

Sundara Rajan Srinivasavaradhan1, Pavlos Nikolopoulos2, Christina Fragouli1,
Suhas Diggavi1  1University of California, Los Angeles, Electrical and
Computer Engineering,
{sundar, christina.fragouli<EMAIL_ADDRESS>2EPFL, Switzerland,
<EMAIL_ADDRESS>
###### Abstract

We study the problem of group testing with non-identical, independent priors.
So far, the pooling strategies that have been proposed in the literature take
the following approach: a hand-crafted test design along with a decoding
strategy is proposed, and guarantees are provided on how many tests are
sufficient in order to identify all infections in a population. In this paper,
we take a different, yet perhaps more practical, approach: we fix the decoder
and the number of tests, and we ask, given these, what is the best test design
one could use? We explore this question for the Definite Non-Defectives (DND)
decoder. We formulate a (non-convex) optimization problem, where the objective
function is the expected number of errors for a particular design. We find
approximate solutions via gradient descent, which we further optimize with
informed initialization. We illustrate through simulations that our method can
achieve significant performance improvement over traditional approaches.

##  I Introduction

Group testing has recently attracted significant attention in the context of
COVID ([1, 2, 3, 4, 5, 6]), and several countries (including India, Germany,
US, and China) have already deployed preliminary group-testing strategies ([7,
8]).

Group testing has a rich history in academia and a number of variations and
setups have been examined so far ([9, 10, 11, 12]). Simply stated, group
testing assumes a population of $N$ individuals out of which some are
infected, and the goal is to design testing strategies and corresponding
decoding algorithms to identify the infections from the test results. Most
works revolve around proposing a particular hand-crafted test design (e.g.
random Bernoulli design) coupled with a decoding strategy (e.g. Definite
Defectives, Definite Non-Defectives), and guarantees are provided on the
number of tests required to achieve vanishing probability of error.
Additionally, order-optimality results have been proved for the asymptotic
regime, where the population size tends to infinity.

To the best of our knowledge, the following complementary question remains
unexplored: Given a fixed decoding strategy and a given number of tests
$\mathit{T}$ (perhaps smaller than what is needed to achieve zero error), what
is the best test design one may use? We examine this question in the context
of nonadaptive group testing, and under the assumption of a Definite Non-
Defectives (DND) decoder, which eliminates false negatives by
construction.111Interestingly, a discussion of one of the authors with the
General Secretary of Public Health in an EU state has revealed that this
question is perhaps the most relevant in practice, as both private and public
lab facilities have limited testing capacity per day, and what actually
matters is how to use the available tests most efficiently.

In this paper, we show that the above problem can be formulated as a non-
convex continuous optimization problem. More specifically, the problem
requires finding a test-design matrix $G$ that minimizes the expected number
of erroneous identifications (i.e. false positives). This, however, presents
two challenges: (a) the analytical computation of the expected number of false
positives turns out to be computationally difficult; and (b) because
$G\in\\{0,1\\}^{\mathit{T}\times N}$, we are faced with a combinatorial
optimization problem.

To address these challenges, we proceed as follows: First, we provide a lower
bound on the expected number of errors, which we use as a proxy in the
optimization problem; that bound can be computed in $O(N^{2})$ runtime. We
then relax the combinatorial optimization problem based on an equivalence
result; the objective function in that relaxed formulation as well as its
gradient can be computed in $O(N^{2})$, thus enabling the use of Gradient
Descent (GD). To further improve the performance of our method, we propose two
approaches to GD: (i) an informed initialization with information from classic
test designs, such as the Constant Column Weight (CCW) design and the Coupon
Collector Algorithm (CCA); (ii) a stochastic re-initialization of the state of
the solution every few gradient iterations (e.g. 100 iterations), in a way
that allows GD to explore across various neighborhoods, while also ensuring
that the objective value does not increase by much with each re-
initialization.

Numerical evaluations show that the GD based approaches can significantly
outperform classical test designs, achieving up to $58\%$ fewer errors with
the DND decoder on simulated infection models. Rather surprisingly, GD based
designs also significantly outperform classical test designs when the decoder
is switched to definite defectives (DD), indicating transferability to other
decoders.

Related work: We here give a brief overview of group testing; the exact
problem we consider in this work will be detailed in Section II-A.

Three infection models are usually studied in the group testing literature:
(i) in the combinatorial priors model, a fixed number of individuals $k$
(selected uniformly at random), are infected; (ii) in i.i.d probabilistic
priors model, each individual is i.i.d infected with some probability $p$;
(iii) in the non-identical probabilistic priors model, each item $i$ is
infected independently of all others with prior probability $p_{i}$, so that
the expected number of infected members is $\bar{k}=\sum_{i=1}^{N}p_{i}$.
Infection models (i) and (ii) have received attention from researchers for the
most part (see for example, [13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23]).
Infection model (iii) is the most general, yet also the least studied one
[24]; we refer the reader to [10] for an excellent summary of existing work on
the above infection models. Our work assumes infection model (iii) with non-
identical probabilistic priors and accepts (ii) as a special case.

Tangentially, recent works have considered correlated infection models; see,
for example, [25, 26, 27, 28, 29, 30, 31].

##  II Preliminaries

In this section, we first precisely formulate the problem of interest, and
then state a simple lemma on combinatorial optimization that is used in our
work.

###  II-A Problem formulation

We consider the noiseless nonadaptive group testing problem with non-identical
priors. There are $N$ individuals in the population, where individual $i$ is
infected independently with probability $p_{i}$. We assume that the value of
$p_{i}$ is known apriori222This is a standard assumption in group testing.
Otherwise, epidemiological models for disease spread can be used to estimate
these probabilities ([32, 33, 34]).. Let $U_{i}$ be the infection status of
individual $i$: $U_{i}=\mathbbm{1}\\{\text{Individual }i\text{ is
infected}\\}$. As a result, $U_{i}\sim\text{Ber}(p_{i})$. We will denote by
$\mathbf{U}=(U_{1},U_{2},...,U_{N})$ the vector of infection statuses.

Testing matrix: A testing matrix $G\in\\{0,1\\}^{T\times N}$ is a $T\times N$
binary matrix. Row $t$ in the testing matrix represents the individuals
participating in test $t$, i.e., $G_{ti}=1$ represents individual $i$
participating in test $t$. The test results corresponding to a particular
realization of $\mathbf{U}=(U_{1},U_{2},...,U_{N})$ and $G$ is defined as the
vector $\mathbf{Y}=(Y_{1},Y_{2},...,Y_{T})$ where

$\displaystyle Y_{t}=1-\prod_{i=1}^{N}(1-G_{ti}U_{i}).$ (1)

In words, the test $t$ gives a positive result if any of the individuals
participating in the test are infected, otherwise it gives a negative
result333Most works in group testing express the right-hand side of (1) as a
Boolean expression. However, we use this particular form (similar expression
was given in [21]) as it easily admits continuous-valued relaxations of the
composing variables.. In (1) $Y_{t}=1$ if and only if there exists $i$ such
that both $G_{ti}=1$ and $U_{i}=1$ (individual $i$ is infected). In order to
infer $\mathbf{U}$ from $Y$, a decoding algorithm
$r:\\{0,1\\}^{T}\rightarrow\\{0,1\\}^{N}$ constructs an estimate
$\widehat{\mathbf{U}}$ of the infection statuses from the test results. In
this work, we fix the decoding algorithm, which we describe next.

DND decoder: The definite non-defective (DND) decoder is a well-known decoding
algorithm that forms an estimate of $\mathbf{U}$ by identifying those
individuals who have participated in at least one negative test as healthy and
labeling every other individual as infected – i.e., it operates under the
principle “every item is defective unless proved otherwise”. More precisely,
it outputs an estimate $\widehat{\mathbf{U}}$ where

$\displaystyle\widehat{U}_{i}=\prod_{t=1}^{T}Y_{t}^{G_{ti}}.$ (2)

$\widehat{\mathbf{U}}$ has zero false negatives by construction – it can be
seen that $\widehat{U}_{i}=1$ whenever $U_{i}=1$. The number of errors (false
positives) that the DND decoder makes for a particular realization
$\mathbf{U}$ is given by

$\displaystyle\sum_{i=1}^{N}\mathbbm{1}\\{\widehat{U}_{i}\neq
U_{i}\\}=\sum_{i=1}^{N}\mathbbm{1}\\{U_{i}=0\\}\mathbbm{1}\\{\widehat{U}_{i}=1|U_{i}=0\\},$

and as a result the expected number of errors $\mathcal{E}(G)$ under the DND
decoder for a given $G$ is

$\displaystyle\mathcal{E}(G)$
$\displaystyle\triangleq\mathbb{E}\left[\sum_{i=1}^{N}\mathbbm{1}\\{\widehat{U}_{i}\neq
U_{i}\\}\right]$
$\displaystyle=\sum_{i=1}^{N}\Pr(U_{i}=0)\Pr(\widehat{U}_{i}=1|U_{i}=0)$
$\displaystyle=\sum_{i=1}^{N}(1-p_{i})\mathbb{E}\left[\widehat{U}_{i}|U_{i}=0\right].$
(3)

Further, when $U_{i}$ is fixed to be 0, $\widehat{U}_{i}$ is a function of $G$
and $\mathbf{U}\setminus\\{i\\}$, where
$\mathbf{U}\setminus\\{i\\}\triangleq(U_{1},...,U_{i-1},U_{i+1},...,U_{N})$
denotes the vector $\mathbf{U}$ without its $i^{th}$ entry. Thus, fixing
$U_{i}=0$, and using (1) and (2) we have,

$\displaystyle\widehat{U}_{i}$
$\displaystyle=\prod_{t=1}^{T}\left(1-\prod_{\begin{subarray}{c}j=1:\\\ j\neq
i\end{subarray}}^{N}(1-G_{tj}U_{j})\right)^{G_{ti}}$
$\displaystyle\overset{(a)}{=}\prod_{t=1}^{T}\left(1-{G_{ti}}\prod_{\begin{subarray}{c}j=1:\\\
j\neq i\end{subarray}}^{N}(1-G_{tj}U_{j})\right),$

where $(a)$ follows because of the following fact: $(1-x)^{y}=1-xy$ if
$y\in\\{0,1\\}$. Now, denoting
$\gamma_{t,i}\triangleq\left(1-{G_{ti}}\prod_{\begin{subarray}{c}j=1:\\\ j\neq
i\end{subarray}}^{N}(1-G_{tj}U_{j})\right)$ in the above expression, we
rewrite (II-A) as:

$\displaystyle\mathcal{E}(G)$
$\displaystyle=\sum_{i=1}^{N}(1-p_{i})\mathbb{E}_{\mathbf{U}\setminus\\{i\\}}\prod_{t=1}^{T}\gamma_{t,i}.$
(4)

Our Goal: We want to minimize $\mathcal{E}(G)$ across all binary matrices $G$
of size $T\times N$, i.e., solve $\displaystyle
G_{opt}=\operatorname*{arg\,min}_{\begin{subarray}{c}G\in\\{0,1\\}^{T\times
N}\end{subarray}}\mathcal{E}(G).$ (5)

Discussion: We first observe that $\gamma_{t,i}$ is not independent of
$\gamma_{t^{\prime},i}$ for $t\neq t^{\prime}$ as they potentially share
common $U_{j}$ terms. As a result, the expectation of the product term in (4)
is not trivially the product of expectations, which makes the computation of
$\mathcal{E}(G)$ intractable in general (indeed one could estimate
$\mathcal{E}(G)$ using Monte-Carlo methods, belief propagation etc.). In
Section III we provide a lower bound for $\mathcal{E}(G)$ which can be
computed efficiently, and which we use as a proxy for $\mathcal{E}(G)$.

We also note that in principle, (5) could be formulated for any decoder, not
just the DND decoder. However, the particular nature of $\mathcal{E}(G)$ for
the DND decoder admits a nice form, for which we can propose an approximate
solution using lower bounding techniques (Section III). For decoders such as
the definite defective decoder or belief propagation based ones, we currently
do not have an approach to calculate a non-trivial lower bound; this remains a
challenging open problem.

###  II-B A combinatorial relaxation result

We now take a detour to prove a simple result that allows one to relax
combinatorial optimization problems that aim to optimize over the vertices of
an $n$-dimensional hypercube. One could extend this technique for optimization
over other finite sets as well.

######  Lemma 1.

In order to solve

$\displaystyle\operatorname*{arg\,min}_{\begin{subarray}{c}\mathbf{x}\in\\{0,1\\}^{n}\end{subarray}}\
g(\mathbf{x}),$ (6)

it is sufficient to solve

$\displaystyle\operatorname*{arg\,min}_{\begin{subarray}{c}\mathbf{q}\in[0,1]^{n}\end{subarray}}\
f(\mathbf{q}),$ (7) $\text{where
}f(\mathbf{q})\triangleq\mathbb{E}_{\mathbf{X}\sim\mathbf{q}}\ g(\mathbf{X})$

can be envisioned as a continuous extension of $g(\mathbf{x})$. The
expectation in the above expression is taken w.r.t the distribution where each
$X_{i}\sim\text{Ber}(q_{i})$, and the $X_{i}$s are independent of each other.

We refer the reader to Section -A for the proof.

Remark: There is a long history of using relaxation techniques to approximate
solutions of combinatorial optimization problems (see [35] for an overview).
Most of these focus on linear programming relaxation techniques. In Lemma 1,
there is no assumption on $g(\cdot)$ whatsoever and the resulting relaxation
may not be a linear program. Moreover, it may not be easy to compute
$f(\cdot)$ in all cases and it may also not be easy to compute the gradient
$\nabla f(\cdot)$ as well. In cases where exactly computing or approximating
the gradient is easy (as is indeed the case in this work), one can use first-
order optimization techniques such as GD.

##  III Main results

In this section, we delineate our approach to find an approximate solution to
(5). Following the discussion at the end of Section II-A, our approach is
three-fold: First, we lower bound $\mathcal{E}(G)$ by another function
$\mathcal{E}_{LB}(G)$, whose computation turns out to be tractable; we then
use $\mathcal{E}_{LB}(G)$ as a proxy for $\mathcal{E}(G)$. Next, we use Lemma
1 to show that it is sufficient to consider a continuous relaxation of the
resulting combinatorial optimization problem. Finally, we show that the
objective function in the continuous relaxation and its gradient can also be
computed efficiently, thus enabling gradient descent.

###  III-A A lower bound for $\mathcal{E}(G)$

As a first step, the following theorem states and proves a lower bound for
$\mathcal{E}(G)$.

######  Theorem 1.

Consider a random vector $\mathbf{U}=(U_{1},U_{2},...,U_{N})$ where
$U_{i}\sim\text{Ber}(p_{i})$. For a given testing matrix $G$, and under the
DND decoder, the expected number of errors (see (4)) satisfies

$\mathcal{E}(G)\geq\mathcal{E}_{LB}(G),$

where

$\mathcal{E}_{LB}(G)\triangleq\sum_{i=1}^{N}(1-p_{i})\prod_{t=1}^{T}\left(1-{G_{ti}}\prod_{\begin{subarray}{c}j=1:\\\
j\neq i\end{subarray}}^{N}(1-G_{tj}p_{j})\right).$

###### Proof.

First we recall the expression for $\mathcal{E}(G)$ in (4):

$\displaystyle\mathcal{E}(G)$
$\displaystyle=\sum_{i=1}^{N}(1-p_{i})\mathbb{E}_{\mathbf{U}\setminus\\{i\\}}\prod_{t=1}^{T}\gamma_{t,i}.$

Using the FKG inequality (see [36, 37, 38] or proof of Lemma 4 in [18]) one
could show that

$\mathbb{E}_{\mathbf{U}\setminus\\{i\\}}\prod_{t=1}^{T}\gamma_{t,i}\geq\prod_{t=1}^{T}\mathbb{E}_{\mathbf{U}\setminus\\{i\\}}\gamma_{t,i}.$

A rigorous proof of the above statement can be found in Appendix -B. The idea
is to show that $\gamma_{t,i}$ is an increasing function on $\mathbf{U}$
(assuming a partial ordering); using this observation, the result follows as
an application of the FKG inequality. Thus, we have

$\displaystyle\mathcal{E}(G)$
$\displaystyle\geq\sum_{i=1}^{N}(1-p_{i})\prod_{t=1}^{T}\mathbb{E}_{\mathbf{U}\setminus\\{i\\}}\gamma_{t,i}$
$\displaystyle=\sum_{i=1}^{N}(1-p_{i})\prod_{t=1}^{T}\left(1-{G_{ti}}\prod_{\begin{subarray}{c}j=1:\\\
j\neq i\end{subarray}}^{N}(1-G_{tj}p_{j})\right)$
$\displaystyle=\mathcal{E}_{LB}(G)$

∎

In all numerical evaluations we performed, $\mathcal{E}(G)$ and the lower
bound $\mathcal{E}_{LB}(G)$ were highly correlated – we provide example
scatter plots in Figure 2 in Section -C – which indicates that minimizing
$\mathcal{E}_{LB}(G)$ is a viable alternative to minimizing $\mathcal{E}(G)$.

###  III-B A continuous optimization formulation

Given the above discussion, we now propose using $\mathcal{E}_{LB}(G)$ as a
proxy for $\mathcal{E}(G)$ – more precisely we propose to solve the following
optimization problem:

$\operatorname*{arg\,min}_{\begin{subarray}{c}G\in\\{0,1\\}^{T\times
N}\end{subarray}}\mathcal{E}_{LB}(G).$ (8)

We next use Lemma 1 to argue that a continuous relaxation of (8) is equivalent
to (8). Before stating the main result, we give a definition: we say that the
matrix $G\sim Q$ (read as “$G$ is distributed according to the distribution
matrix $Q$”) if each $G_{ti}\sim\text{Ber}(Q_{ti})\ \forall\ t,i$ and the
$G_{ti}$ variables are independent of each other.

######  Corollary 1.

Suppose $U_{i}\sim\text{Ber}(p_{i})\ \forall\ i$. In order to solve the
optimization problem

$\displaystyle\operatorname*{arg\,min}_{\begin{subarray}{c}G\in\\{0,1\\}^{T\times
N}\end{subarray}}\mathcal{E}_{LB}(G),$ (9)

it is sufficient to solve

$\displaystyle\operatorname*{arg\,min}_{\begin{subarray}{c}Q\in[0,1]^{T\times
N}\end{subarray}}\mathbb{E}_{G\sim Q}\mathcal{E}_{LB}(G).$ (10)

This is a direct corollary of Lemma 1, where the objective function is
$\mathcal{E}_{LB}(G)$ and we associate a parameter $Q_{ti}$ corresponding to
each $G_{ti}$.

Thus, we now have the following approximate formulation for which the
objective function (and its gradient) can be computed in $O(N^{2})$ time
complexity (see Section III-C). The hope is that solving (11) gives
sufficiently good choices of $G\sim Q^{*}$; our experimental results in
Section V indicate that this is indeed the case.

Approximate formulation: Solve for $\displaystyle
Q^{*}=\operatorname*{arg\,min}_{\begin{subarray}{c}Q\in[0,1]^{T\times
N}\end{subarray}}f(Q),$ (11) where $f(Q)\triangleq\mathbb{E}_{G\sim
Q}\mathcal{E}_{LB}(G).$

Given the above formulation, we can now use techniques such as gradient
descent (GD) to select the testing matrix $G$. In essence, we are searching
over the continuous space of distribution matrices $Q$. If the gradient of
$f(Q)$ can be efficiently computed, one could use GD to converge to a local
minima $Q^{*}$ and pick a $G\sim Q^{*}$.

###  III-C Expression for $f(Q)$

We now give a closed-form expression for $f(Q)$ and briefly discuss the
computational complexity of computing $f(Q)$ and its gradient; the details are
deferred to Section -D, Section -E and Section -F. We have,

$\displaystyle f$ $\displaystyle(Q)\triangleq\mathbb{E}_{G\sim
Q}\mathcal{E}_{LB}(G)$ $\displaystyle=\mathbb{E}_{G\sim
Q}\sum_{i=1}^{N}(1-p_{i})\prod_{t=1}^{T}\left(1-{G_{ti}}\prod_{\begin{subarray}{c}j=1:\\\
j\neq i\end{subarray}}^{N}(1-G_{tj}p_{j})\right)$
$\displaystyle\overset{(a)}{=}\sum_{i=1}^{N}(1-p_{i})\prod_{t=1}^{T}\mathbb{E}_{G\sim
Q}\left(1-{G_{ti}}\prod_{\begin{subarray}{c}j=1:\\\ j\neq
i\end{subarray}}^{N}(1-G_{tj}p_{j})\right)$
$\displaystyle=\sum_{i=1}^{N}(1-p_{i})\prod_{t=1}^{T}\left(1-{Q_{ti}}\prod_{\begin{subarray}{c}j=1:\\\
j\neq i\end{subarray}}^{N}(1-Q_{tj}p_{j})\right),$ (12)

where in $(a)$ the expectation is pushed inside the product terms as
$\mathcal{E}_{LB}(G)$ is linear when viewed as a function of a single
$G_{ti}$. In Appendix -D we discuss an $O(N^{2})$ algorithm that simplifies
the computation of $f(Q)$ above. Given (12), one could derive an expression
for the gradient $\nabla f(Q)$ by calculating each partial derivative
$\partialderivative{f(Q)}{Q_{lm}}$. The details of the derivation can be found
in Appendix -E. Moreover, in Appendix -F, we discuss the computation of
$\nabla f(Q)$ in $O(N^{2})$ runtime.

$100$$200$$300$$400$$500$$600$$0$$0.2$$0.4$Number of tests used ($T$)FP
rateCCWCCAGD + 0initGD + CCWinitGD + CCAinitGD + sampling

(a) DND decoder.

$100$$200$$300$$400$$500$$600$$0$$0.5$$1$Number of tests used ($T$)FN
rateCCWCCAGD + 0initGD + CCWinitGD + CCAinitGD + sampling

(b) DD decoder.

Figure 1: Priors sampled from an exponential distribution with mean 0.05,
$N=1000$. We average over 10 such instances.

##  IV Algorithms

Leveraging the approximate formulation in (11), we here explore a GD approach
to find good choices of $G$. Our proposed approach uses informed
initialization with information provided by traditional group test designs.
Thus, it can be viewed as a way to refine and improve existing designs via
local search. Moreover, we propose a variation of GD that numerically seems to
converge to good choices of $G$ in many situations even without informed
initialization.

###  IV-A Baseline test designs

We use the following two group test design algorithms as baselines for
comparison:

$\bullet$ Constant column weight (CCW) design (see [39, 17]). This design was
introduced in the context of group testing for identical priors444Most of
these were proposed in the context of combinatorial priors. However, Theorem
1.7 and Theorem 1.8 from [10] imply that any algorithm that attains a
vanishing probability of error on the combinatorial priors, also attains a
vanishing probability of error on the corresponding i.i.d probabilistic
priors., but we adapt it to be applicable for non-identical priors as well, in
addition to identical priors. Here we construct a randomized $G$ assuming that
all individuals have the same prior probability of infection $p_{mean}$ (this
assumption is trivially true if the priors are identical), where $p_{mean}$ is
defined as the mean prior probability of infection
$\frac{1}{N}\sum_{i=1}^{N}p_{i}$. The testing matrix $G$ is constructed
column-by-column by placing each individual in a fixed number
($\frac{0.69T}{Np_{mean}}$) of tests, uniformly at random.

$\bullet$ Coupon Collector Algorithm (CCA) from [24]. The CCA algorithm was
introduced in [24] for the case of non-identical, independent priors. In
short, the CCA algorithm constructs a random non-adaptive test design $G$ by
sampling each row independently from a distribution (we refer the reader to
[24] for the exact description of this distribution). The idea is to place
objects which are less likely to be infected in more number of tests and vice-
versa.

###  IV-B Test designs based on gradient descent

We are now ready to describe the gradient descent (GD) approaches to search
for $G$. The high-level idea for our algorithms is as follows:

$\bullet$ We consider the approximate formulation in (11). Pick an initial
point $Q^{(0)}$.

$\bullet$ At each gradient iteration $l$, update $Q^{(l)}\leftarrow
Q^{(l-1)}-\epsilon\nabla_{Q}f(Q)$, where $\epsilon$ is the step size. Project
$Q^{(l)}$ onto $[0,1]^{T\times N}$ by resetting negative entries to 0 and
entries greater than 1 to 1.

$\bullet$ Stop based on some stopping criteria (e.g. limit number of gradient
steps or check for convergence).

$\bullet$ Let $Q^{*}$ be the resulting output. Sample a matrix $G^{*}$ where
$G^{*}\sim Q^{*}$ and return it.

As it turns out, in our experiments, the choice of initialization plays a
significant role in finding good choices of $G$. We propose the following
initializations.

$\bullet$ GD + CCW init. We first sample a testing matrix according to the CCW
testing matrix and set $Q^{(0)}$ as this matrix. The GD proceeds with this
initialization.

$\bullet$ GD + CCA init. We first sample a testing matrix according to the CCA
testing matrix and set $Q^{(0)}$ as this matrix. The GD proceeds with this
initialization.

Notably, any other state-of-the-art test design could have been used as
initialization. In principle, the above approach can be perceived as a way to
refine existing test designs via local search. Alternatively, we also propose
a modification to the GD approach called GD + sampling that helps avoid
getting stuck in a local minima by encouraging GD to explore multiple
neighborhoods. The idea is use stochastic re-initialization of the solution
state every few gradient iterations, while ensuring that the value of the
objective function is approximately preserved. First note that the objective
value $f(Q)$ is the mean of $f(G)$ with $G\sim Q$. Therefore, it is reasonable
to expect that typical realizations of $G$ will be such that $f(G)$ is close
to $f(Q)$. Given this idea, we propose the following: start from the all 0
initialization. However, every few gradient iterations, we replace the current
solution state $Q^{(l)}$ by $G^{s}$ where $G^{s}$ is sampled from the
distributed matrix $Q^{(l)}$, i.e., $G^{s}\sim Q^{(l)}$. This encourages GD to
explore different neighborhoods while (approximately) preserving the
monotonocity of GD.

##  V Numerical results

In this section, we show simulation results to demonstrate the improvement our
GD based approaches provides.

Test designs compared: We compare the testing matrices $G$ obtained via each
of the following methods: CCW, CCA, GD + CCW init., GD + CCA init., GD +
sampling. For completeness, we consider also the trivial all
$0$-initialization for GD (which we call GD + 0 init), where the initial point
$Q^{(0)}$ is set to all zeros.

Set-up: We first fix the prior probabilities of infection
$(p_{1},p_{2},...,p_{N})$ – each $p_{i}$ is sampled from an exponential
distribution with mean $0.05$; if $p_{i}>1$, we set it to 1. We repeat for 10
such prior distributions. For each design, we estimate $\mathcal{E}(G)$ via
Monte-Carlo simulations.

Metrics: We use the false positive (FP) rate (defined as the fraction of
uninfected individuals incorrectly determined to be infected) to measure the
performance w.r.t the DND decoder. Recall that the DND decoder results in 0
false negatives (FN) by construction.

Transferability to other decoders: As our GD methods aim for optimal designs
with the DND decoder, a natural follow-up question is how they perform with
other decoders. We compare the performance of each of the test designs w.r.t
the Definite Defective (DD) decoder. One could also consider other decoders,
such as ones based on belief propagation, but these result in both FP and FN,
and consequently the comparison between different methods is not trivial; it
requires weighing FP against FN, which can be application specific. We refer
the reader to Section 2.4 in [10] for a precise description of DD
decoder.Consequently, DD has 0 FP by construction. In this case, we use as
performance measure the false negative (FN) rate.

Observations: In Figure 1(a), we plot the FP rate for each test design w.r.t
DND decoder, as a function of $T$. We observe that the GD based methods
significantly outperform CCW and CCA555Interestingly, CCW outperforms CCA
here, despite using less information about the priors. We refer the reader to
Section -G for cases where CCA outperforms CCW.. Notably, the improvement of
our enhanced GD with informed initialization or sampling seems inversely
proportional to $\mathit{T}$, which is of practical importance.

Next, we plot the FN rate of each test design w.r.t the DD decoder, as a
function of $T$ in Figure 1(b). The performance trend here is similar to what
was observed with the DND decoder, which further supports the usefulness of
our GD based approach and its transferability to other decoders.

## References

  * [1] C. Gollier and O. Gossner, “Group testing against covid-19,” April 2020, see https://www.tse-fr.eu/publications/group-testing-against-covid-19.
  * [2] M. Broadfoot, “Coronavirus test shortages trigger a new strategy: Group screening,” May 2020, see https://www.scientificamerican.com/article/coronavirus-test-shortages-trigger-a-new-strategy-group-screening2/.
  * [3] J. Ellenberg, “Five people. one test. this is how you get there.” _NYtimes_ , May 2020.
  * [4] C. Verdun _et al._ , “Group testing for sars-cov-2 allows up to 10-fold efficiency increase across realistic scenarios and testing strategies,” _medRxiv_ , 2020.
  * [5] S. Ghosh _et al._ , “Tapestry: A single-round smart pooling technique for covid-19 testing,” _medRxiv_ , 2020.
  * [6] L. M. Kucirka, S. A. Lauer, O. Laeyendecker, D. Boon, and J. Lessler, “Variation in false-negative rate of reverse transcriptase polymerase chain reaction–based sars-cov-2 tests by time since exposure,” _Annals of Internal Medicine_ , vol. 173, pp. 262–267, Aug. 2020.
  * [7] S. Mallapaty. (2020) The mathematical strategy that could transform coronavirus testing. [Online]. Available: https://www.nature.com/articles/d41586-020-02053-6
  * [8] FDA. (2020) Pooled sample testing and screening testing for covid-19. [Online]. Available: https://www.fda.gov/medical-devices/coronavirus-covid-19-and-medical-devices/pooled-sample-testing-and-screening-testing-covid-19
  * [9] R. Dorfman, “The detection of defective members of large population,” _The Annals of Mathematical Statistics_ , vol. 14, pp. 436–440, 1943.
  * [10] M. Aldridge, O. Johnson, and J. Scarlett, “Group testing: an information theory perspective,” _CoRR_ , vol. abs/1902.06002, 2019.
  * [11] D.-Z. Du and F. Hwang, _Combinatorial Group Testing and Its Applications_. Series on Applied Mathematics, 1993.
  * [12] Y. Malinovsky and P. S. Albert, “Revisiting nested group testing procedures: new results, comparisons, and robustness,” _American Statistician_ , August 2016, see also https://arxiv.org/abs/1608.06330.
  * [13] G. K. Atia and V. Saligrama, “Boolean compressed sensing and noisy group testing,” _IEEE Transactions on Information Theory_ , vol. 58, no. 3, pp. 1880–1901, 2012.
  * [14] M. Aldridge, L. Baldassini, and O. Johnson, “Group testing algorithms: Bounds and simulations,” _IEEE Transactions on Information Theory_ , vol. 60, no. 6, pp. 3671–3687, 2014.
  * [15] C. L. Chan, S. Jaggi, V. Saligrama, and S. Agnihotri, “Non-adaptive group testing: Explicit bounds and novel algorithms,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 5, p. 3019–3035, 2014.
  * [16] J. Scarlett and V. Cevher, “Phase transitions in group testing,” in _Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016_. SIAM, 2016, pp. 40–53.
  * [17] O. Johnson, M. Aldridge, and J. Scarlett, “Performance of group testing algorithms with near-constant tests per item,” _IEEE Trans. Inf. Theory_ , vol. 65, no. 2, pp. 707–723, 2019.
  * [18] M. Aldridge, “Individual testing is optimal for nonadaptive group testing in the linear regime,” _IEEE Trans. Inf. Theory_ , vol. 65, no. 4, 2019.
  * [19] W. H. Bay, E. Price, and J. Scarlett, “Optimal non-adaptive probabilistic group testing requires $\theta(\min\\{k\log n,n\\})$ tests,” 2020.
  * [20] A. Coja-Oghlan, O. Gebhard, M. Hahn-Klimroth, and P. Loick, “Optimal group testing,” ser. Proceedings of Machine Learning Research, J. Abernethy and S. Agarwal, Eds., vol. 125, Jul. 2020, pp. 1374–1388.
  * [21] I. Armendáriz, P. A. Ferrari, D. Fraiman, J. M. Martínez, and S. P. Dawson, “Group testing with nested pools,” _arXiv preprint arXiv:2005.13650_ , 2020.
  * [22] E. Price and J. Scarlett, “A fast binary splitting approach to non-adaptive group testing,” _arXiv preprint arXiv:2006.10268_ , 2020.
  * [23] A. Coja-Oghlan, O. Gebhard, M. Hahn-Klimroth, and P. Loick, “Information-theoretic and algorithmic thresholds for group testing,” _IEEE Trans. Inf. Theory_ , 2020.
  * [24] T. Li, C. L. Chan, W. Huang, T. Kaced, and S. Jaggi, “Group testing with prior statistics,” in _2014 IEEE International Symposium on Information Theory_ , 2014, pp. 2346–2350.
  * [25] P. Nikolopoulos, T. Guo, C. Fragouli, and S. Diggavi, “Community aware group testing,” 2020, https://arxiv.org/abs/2007.08111.
  * [26] P. Nikolopoulos, S. Rajan Srinivasavaradhan, T. Guo, C. Fragouli, and S. Diggavi, “Group testing for connected communities,” in _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ , vol. 130. PMLR, 2021, pp. 2341–2349.
  * [27] P. Nikolopoulos, S. R. Srinivasavaradhan, T. Guo, C. Fragouli, and S. Diggavi, “Group testing for overlapping communities,” in _ICC 2021 - IEEE International Conference on Communications_ , 2021, pp. 1–7.
  * [28] J. Zhu, K. Rivera, and D. Baron, “Noisy pooled pcr for virus testing,” _arXiv preprint arXiv:2004.02689_ , 2020.
  * [29] R. Goenka, S.-J. Cao, C.-W. Wong, A. Rajwade, and D. Baron, “Contact tracing enhances the efficiency of covid-19 group testing,” _arXiv preprint arXiv:2011.14186_ , 2020.
  * [30] S. Ahn, W.-N. Chen, and A. Ozgur, “Adaptive group testing on networks with community structure,” _arXiv preprint arXiv:2101.02405_ , 2021.
  * [31] P. Bertolotti and A. Jadbabaie, “Network group testing,” _arXiv preprint arXiv:2012.02847_ , 2020.
  * [32] I. Kiss, J. Miller, and P. Simon, _Mathematics of Epidemics on Networks_ , 01 2017, vol. 46.
  * [33] S. R. Srinivasavaradhan, P. Nikolopoulos, C. Fragouli, and S. Diggavi, “Dynamic group testing to control and monitor disease progression in a population,” _arXiv preprint arXiv:2106.10765_ , 2021.
  * [34] ——, “An entropy reduction approach to continual testing,” in _2021 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2021, pp. 611–616.
  * [35] L. Trevisan, “Combinatorial optimization: exact and approximate algorithms,” _Stanford University_ , 2011.
  * [36] C. M. Fortuin, P. W. Kasteleyn, and J. Ginibre, “Correlation inequalities on some partially ordered sets,” _Communications in Mathematical Physics_ , vol. 22, no. 2, pp. 89–103, 1971.
  * [37] J. Kemperman, “On the fkg-inequality for measures on a partially ordered space,” in _Indagationes Mathematicae (Proceedings)_ , vol. 80, no. 4. North-Holland, 1977, pp. 313–331.
  * [38] P.C. Fishburn, _Encyclopedia of Mathematics_. European Mathematical Society, uRL: http://encyclopediaofmath.org/index.php?title=FKG_inequality&oldid=14368.
  * [39] M. Aldridge, O. Johnson, and J. Scarlett, “Improved group testing rates with constant column weight designs,” in _2016 IEEE International Symposium on Information Theory (ISIT)_. Ieee, 2016, pp. 1381–1385.

###  -A Proof of Lemma 1

###### Proof.

We first note that for any $\mathbf{q}\in[0,1]^{n}$ we have,

$\mathbb{E}_{\mathbf{X}\sim\mathbf{q}}g(\mathbf{X})\geq\min_{\begin{subarray}{c}\mathbf{x}\in\\{0,1\\}^{n}\end{subarray}}\
g(\mathbf{x}),$

since the expectation of a random variable is at least as large as its minimum
value over its support. Since the above holds for any $\mathbf{q}$, as a
result we have

$\min_{\begin{subarray}{c}\mathbf{q}\in[0,1]^{n}\end{subarray}}\
\mathbb{E}_{\mathbf{X}\sim\mathbf{q}}g(\mathbf{X})\geq\min_{\begin{subarray}{c}\mathbf{x}\in\\{0,1\\}^{n}\end{subarray}}\
g(\mathbf{x}).$ (13)

Let $\mathbf{x}^{*}$ be a minimizer of $g(\mathbf{x})$ in (6). The choice of
$\mathbf{q}^{*}=\mathbf{x}^{*}$ (i.e. $\mathbf{X}=\mathbf{x}^{*}$ with
probability 1) gives

$f(\mathbf{q}^{*})=\mathbb{E}_{\mathbf{X}\sim\mathbf{q}^{*}}g(\mathbf{X})=g(\mathbf{x}^{*})=\min_{\begin{subarray}{c}\mathbf{x}\in\\{0,1\\}^{n}\end{subarray}}\
g(\mathbf{x}).$ (14)

From (13) and (14) we conclude that

$\min_{\begin{subarray}{c}\mathbf{q}\in[0,1]^{n}\end{subarray}}\
\mathbb{E}_{\mathbf{X}\sim\mathbf{q}}g(\mathbf{X})=\min_{\begin{subarray}{c}\mathbf{x}\in\\{0,1\\}^{n}\end{subarray}}\
g(\mathbf{x}).$

In order to obtain a solution to (6), we obtain a solution $\mathbf{q}^{*}$ of
(7) and any $\mathbf{X}\sim\mathbf{q}^{*}$ (sample
$X_{i}\sim\text{Ber}(q_{i})$) is a solution to (6). ∎

###  -B Theorem 1 proof: filling in the gaps

In the proof of Theorem 1 we claimed the following:

$\mathbb{E}_{\mathbf{U}\setminus\\{i\\}}\prod_{t=1}^{T}\gamma_{t,i}\geq\prod_{t=1}^{T}\mathbb{E}_{\mathbf{U}\setminus\\{i\\}}\gamma_{t,i}.$

where $\gamma_{t,i}\triangleq\left(1-{G_{ti}}\prod_{\begin{subarray}{c}j=1:\\\
j\neq i\end{subarray}}^{N}(1-G_{tj}U_{j})\right)$. We prove this using the
Fortuin–Kasteleyn–Ginibre (FKG) inequality (see [36, 37, 38] or proof of Lemma
4 in [18]), restated here for convenience.

######  Lemma 2 (FKG inequality).

Consider a finite distributive lattice $\Gamma$ with partial ordering $\prec$
and meet ($\wedge$) and join operators ($\vee$). Consider a probability
measure $\mu$ on $\Gamma$ that is log-supermodular, i.e.,

$\mu(a)\mu(b)\leq\mu(a\wedge b)\mu(a\vee b)\ \forall\ a,b\in\Gamma.$

Then, any two functions $f$ and $g$ which are non-decreasing on $\Gamma$ are
positively correlated, i.e.,

$\mathbb{E}_{\mu}(fg)\geq\mathbb{E}_{\mu}(f)\mathbb{E}_{\mu}(g).$

Remark: Consider $\Gamma=\\{0,1\\}^{N}$ with partial ordering $\prec$, where
$a\prec b$ if every coordinate of $b$ is at least as large as $a$. When the
meet and join operators coincide with logical AND and logical OR respectively,
this is a distributive lattice. It can be verified that any product measure
$\mu$ on $\Gamma$ is log-supermodular. As a result, any two functions $f$ and
$g$ which are non-decreasing on $\Gamma$ are positively correlated, i.e.,
$\mathbb{E}_{\mu}(fg)\geq\mathbb{E}_{\mu}(f)\mathbb{E}_{\mu}(g).$
Consequently, given any $M$ non-negative, non-decreasing functions
$f_{1},f_{2},...,f_{M}$ one could inductively apply FKG inequality to obtain

$\mathbb{E}_{\mu}(\prod_{i=1}^{M}f_{i})\geq\prod_{i=1}^{M}\mathbb{E}_{\mu}f_{i}.$
(15)

Given (15) what remains to be shown is that each $\gamma_{t,i}(\mathbf{U})$ is
non-negative and non-decreasing as a function of $\mathbf{U}\in\\{0,1\\}^{N}$.
To see that it is non-negative is straight-forward – we have $G_{tj}U_{j}\geq
0$ and hence $(1-G_{tj}U_{j})\leq 1$. Therefore, the product
$\prod_{\begin{subarray}{c}j=1:\\\ j\neq
i\end{subarray}}^{N}(1-G_{tj}U_{j})\leq 1$ and the non-negativity follows. To
see that $\gamma_{t,i}(\mathbf{U})$ is non-decreasing, we first consider
$\mathbf{U}\prec\mathbf{U}^{\prime}$, i.e., $U_{j}\leq U_{j}^{\prime}\
\forall\ j$. Then we have $(1-G_{tj}U_{j})\geq(1-G_{tj}U^{\prime}_{j})\
\forall\ t,j$ and $\prod_{\begin{subarray}{c}j=1:\\\ j\neq
i\end{subarray}}^{N}(1-G_{tj}U_{j})\geq\prod_{\begin{subarray}{c}j=1:\\\ j\neq
i\end{subarray}}^{N}(1-G_{tj}U^{\prime}_{j})\ \forall\ t$. Thus,
$\gamma_{t,i}(\mathbf{U})\leq\gamma_{t,i}(\mathbf{U}^{\prime})$ and
$\gamma_{t,i}$ is non-decreasing. Applying (15), we have

$\mathbb{E}_{\mathbf{U}\setminus\\{i\\}}\prod_{t=1}^{T}\gamma_{t,i}\geq\prod_{t=1}^{T}\mathbb{E}_{\mathbf{U}\setminus\\{i\\}}\gamma_{t,i}.$

###  -C Quality of the lower bound approximation

$0$$0.5$$1$$0$$0.5$$1$

$0$$0.5$$1$$0$$0.5$$1$

Figure 2: Scatter plot of $\mathcal{E}(G)$ (on y-axis) vs.
$\mathcal{E}_{LB}(G)$ (on x-axis) normalized by the blocklength $N$.
$\mathcal{E}(G)$ is estimated via Monte-Carlo simulations while
$\mathcal{E}_{LB}(G)$ is computed exactly. For a fixed prior distribution, we
pick a variety of $G$ matrices and plot the two metrics – the left figure
plots for every $G\in\\{0,1\\}^{2\times 4}$ while the right figure plots for
1000 choices of $G$ sampled from $\\{0,1\\}^{300\times 500}$.

###  -D Computing the objective function $f(Q)$

Here we give a $O(N^{2})$ algorithm to compute the objective function $f(Q)$
in (11). We assume $T\leq N$ so $T=O(N)$ throughout. We first restate the
expression for $f(Q)$ in (12):

$f(Q)=\sum_{i=1}^{N}(1-p_{i})\prod_{t=1}^{T}(1-Q_{ti}\prod_{j=1,j\neq
i}^{N}(1-Q_{tj}p_{j})).$

Note that this can be rewritten as:

$f(Q)=\sum_{i=1}^{N}(1-p_{i})F[i],$

where the intermediate terms are defined as

$F[i]\triangleq\prod_{t=1}^{T}(1-Q_{ti}G[t,i])$

and

$G[t,i]\triangleq\prod_{j=1,j\neq i}^{N}(1-Q_{tj}p_{j})).$

Thus, we first compute and store $G[t,i]\ \forall\ t,i$, which is then used to
compute $F[i]\ \forall\ i$ in $O(N^{2})$ time (assuming $T=O(N)$).
Subsequently, $f(Q)$ can be computed from $F[i]$ in $O(N)$. Computing $G[t,i]$
takes $O(N^{2})$ as one can first compute
$H[t]\triangleq\prod_{j=1}^{N}(1-Q_{tj}p_{j}))\ \forall\ t$ in $O(N^{2})$ time
and obtain $G[t,i]=H[t]/(1-Q_{ti}p_{i})$ in $O(N^{2})$. The overall time
complexity of computing $f(Q)$ is $O(N^{2})$.

###  -E Expression for each partial derviative in $\nabla_{Q}f(Q)$

Here, we give an expression for the gradient $\nabla f(Q)$ by calculating each
partial derivative $\partialderivative{f(Q)}{Q_{lm}}$.

$\displaystyle\partialderivative{f(Q)}{Q_{lm}}$
$\displaystyle=\partialderivative{Q_{lm}}\sum_{i=1}^{N}(1-p_{i})\prod_{t=1}^{T}\left(1-{Q_{ti}}\prod_{\begin{subarray}{c}j=1:\\\
j\neq i\end{subarray}}^{N}(1-Q_{tj}p_{j})\right)$
$\displaystyle=\partialderivative{Q_{lm}}\sum_{i=1:i\neq
m}^{N}(1-p_{i})\prod_{t=1}^{T}\left(1-{Q_{ti}}\prod_{\begin{subarray}{c}j=1:\\\
j\neq i\end{subarray}}^{N}(1-Q_{tj}p_{j})\right)$ $\displaystyle\hskip
28.45274pt+(1-p_{m})\partialderivative{Q_{lm}}\prod_{t=1}^{T}\left(1-{Q_{tm}}\prod_{\begin{subarray}{c}j=1:\\\
j\neq m\end{subarray}}^{N}(1-Q_{tj}p_{j})\right)$
$\displaystyle\overset{(a)}{=}\sum_{i=1:i\neq
m}^{N}(1-p_{i})\partialderivative{Q_{lm}}\left(1-{Q_{li}}\prod_{\begin{subarray}{c}j=1:\\\
j\neq i\end{subarray}}^{N}(1-Q_{lj}p_{j})\right)\prod_{t=1:t\neq
l}^{T}\left(1-{Q_{ti}}\prod_{\begin{subarray}{c}j=1:\\\ j\neq
i\end{subarray}}^{N}(1-Q_{tj}p_{j})\right)$ $\displaystyle\hskip
28.45274pt+(1-p_{m})\partialderivative{Q_{lm}}\left(1-{Q_{lm}}\prod_{\begin{subarray}{c}j=1:\\\
j\neq m\end{subarray}}^{N}(1-Q_{lj}p_{j})\right)\prod_{t=1:t\neq
l}^{T}\left(1-{Q_{tm}}\prod_{\begin{subarray}{c}j=1:\\\ j\neq
m\end{subarray}}^{N}(1-Q_{tj}p_{j})\right)$
$\displaystyle\overset{(b)}{=}\sum_{i=1:i\neq
m}^{N}(1-p_{i})\left({Q_{li}}p_{m}\prod_{\begin{subarray}{c}j=1:\\\ j\neq
i,j\neq m\end{subarray}}^{N}(1-Q_{lj}p_{j})\right)\prod_{t=1:t\neq
l}^{T}\left(1-{Q_{ti}}\prod_{\begin{subarray}{c}j=1:\\\ j\neq
i\end{subarray}}^{N}(1-Q_{tj}p_{j})\right)$ $\displaystyle\hskip
28.45274pt+(1-p_{m})\left(-\prod_{\begin{subarray}{c}j=1:\\\ j\neq
m\end{subarray}}^{N}(1-Q_{lj}p_{j})\right)\prod_{t=1:t\neq
l}^{T}\left(1-{Q_{tm}}\prod_{\begin{subarray}{c}j=1:\\\ j\neq
m\end{subarray}}^{N}(1-Q_{tj}p_{j})\right),$ (16)

where in $(a)$ we separate out the term corresponding to $t=l$ from the
product term $\prod_{t=1}^{T}$ and apply the derivative in $(b)$.

###  -F Computing $\nabla_{Q}f(Q)$

The computation of gradient follows a similar approach as the computation of
the objective function $f(Q)$. We assume $T\leq N$ so $T=O(N)$ throughout. We
first restate the expression for the gradient in (16):

$\displaystyle\nabla_{Q_{lm}}f(Q)=\sum_{i=1:i\neq m}^{N}$
$\displaystyle(1-p_{i})\left({Q_{li}}p_{m}\prod_{\begin{subarray}{c}j=1:\\\
j\neq i,j\neq m\end{subarray}}^{N}(1-Q_{lj}p_{j})\right)\prod_{t=1:t\neq
l}^{T}\left(1-{Q_{ti}}\prod_{\begin{subarray}{c}j=1:\\\ j\neq
i\end{subarray}}^{N}(1-Q_{tj}p_{j})\right)$
$\displaystyle+(1-p_{m})\left(-\prod_{\begin{subarray}{c}j=1:\\\ j\neq
m\end{subarray}}^{N}(1-Q_{lj}p_{j})\right)\prod_{t=1:t\neq
l}^{T}\left(1-{Q_{tm}}\prod_{\begin{subarray}{c}j=1:\\\ j\neq
m\end{subarray}}^{N}(1-Q_{tj}p_{j})\right)$

As we did in the case of objective function computation, we first simplify and
rewrite this in terms of intermediate terms:

$\displaystyle\nabla_{Q_{lm}}f(Q)$ $\displaystyle=\sum_{i=1:i\neq
m}^{N}(1-p_{i})\left({Q_{li}}\frac{p_{m}}{1-Q_{lm}p_{m}}G[l,i]\right)\prod_{t=1:t\neq
l}^{T}\left(1-{Q_{ti}}G[t,i]\right)$ $\displaystyle\hskip
28.45274pt+(1-p_{m})\left(-G[l,m]\right)\prod_{t=1:t\neq
l}^{T}\left(1-{Q_{tm}}G[t,m]\right)$
$\displaystyle=\frac{p_{m}}{1-Q_{lm}p_{m}}\sum_{i=1:i\neq
m}^{N}(1-p_{i})\left({Q_{li}}G[l,i]\right)F[l,i]$ $\displaystyle\hskip
28.45274pt+(1-p_{m})\left(-G[l,m]\right)F[l,m]$
$\displaystyle=\frac{p_{m}}{1-Q_{lm}p_{m}}\left(\sum_{i=1}^{N}(1-p_{i}){Q_{li}}G[l,i]F[l,i]-(1-p_{m})Q_{lm}G[l,m]F[l,m]\right)$
$\displaystyle\hskip 28.45274pt+(1-p_{m})\left(-G[l,m]\right)F[l,m]$
$\displaystyle=\frac{p_{m}}{1-Q_{lm}p_{m}}\sum_{i=1}^{N}(1-p_{i}){Q_{li}}G[l,i]F[l,i]$
$\displaystyle\hskip
28.45274pt-(1-p_{m})G[l,m]F[l,m]\left(\frac{1}{1-Q_{lm}p_{m}}\right),$

where the intermediate terms are

$F[l,i]\triangleq\prod_{t=1:t\neq l}^{T}(1-Q_{ti}G[t,i])$

and

$G[t,i]=\prod_{j=1,j\neq i}^{N}(1-Q_{tj}p_{j}).$

As we showed earlier, computing $G[t,i]\ \forall\ t,i$ can be done in
$O(N^{2})$ runtime complexity, and $F[l,i]$ can be obtained as
$\frac{H[i]}{1-Q_{li}G[l,i]}$ where
$H[i]\triangleq\prod_{t=1}^{T}(1-Q_{ti}G[t,i])$. Clearly, $H[i]\ \forall\ i$
can be obtained once in $O(N^{2})$ and reused to compute $F[l,i]\ \forall\
l,i$ in $O(N^{2})$. Having computed $F$ and $G$ terms, one could again use a
similar trick to precompute
$J[l]\triangleq\sum_{i=1}(1-p_{i})Q_{li}G[l,i]F[l,i]\ \forall\ l$ in
$O(N^{2})$. With this, one could now compute each gradient term
$\nabla_{Q_{lm}}$ in $O(1)$ thus giving an overall time complexity $O(N^{2})$.

###  -G Additional numerical results

$100$$200$$300$$400$$500$$0$$0.2$$0.4$$0.6$Number of tests usedFP rateCCWCCAGD
+ 0initGD + CCWinitGD + CCAinitGD + sampling

(a) DND decoder.

$100$$200$$300$$400$$500$$0.2$$0.4$$0.6$$0.8$$1$Number of tests usedFP
rateCCWCCAGD + 0initGD + CCWinitGD + CCAinitGD + sampling

(b) DD decoder.

Figure 3: Priors sampled from a discrete bimodal distribution (priors take
value 0.02 or 0.3) with mean 0.1, $N=1000$. We average over 10 such instances.

$100$$200$$300$$400$$500$$0$$0.2$$0.4$$0.6$Number of tests usedFP rateCCWCCAGD
+ 0initGD + CCWinitGD + CCAinitGD + sampling

(a) DND decoder.

$100$$200$$300$$400$$500$$0.2$$0.4$$0.6$$0.8$$1$Number of tests usedFP
rateCCWCCAGD + 0initGD + CCWinitGD + CCAinitGD + sampling

(b) DD decoder.

Figure 4: Priors sampled from a discrete bimodal distribution (priors take
value 0.02 or 0.5) with mean 0.1, $N=1000$. We average over 10 such instances.