On the All-Or-Nothing Behavior
of Bernoulli Group Testing

We consider a population of $p$ items indexed as $\{1,\dotsc,p\}$, and we let $k$ denote the number of defective items. The set of defective items is denoted by $S$, and is assumed to be uniform over the ${p\choose k}$ possibilities.

A group testing procedure performs a sequence of $n$ tests, with $X^{(i)}\in\{0,1\}^{p}$ indicating which item is in the $i$-th test. The resulting outcomes are $Y^{(i)}=\bigvee_{j\in S}X_{j}^{(i)}$ for $i=1,\dotsc,n$, where $n$ is the number of tests. That is, the test outcome is $1$ if there is any defective item in the test, and $0$ otherwise. The tests can be represented by a matrix $\mathbf{X}\in\{0,1\}^{n\times p}$, whose $i$-th row is $X^{(i)}$. Similarly, the outcomes can be represented by a vector $\mathbf{Y}\in\{0,1\}^{n}$, whose $i$-th entry is $Y^{(i)}$.

In general, group testing procedures may be adaptive (i.e., $X^{(i)}$ may be chosen as a function of the previous outcomes) or non-adaptive (i.e., all $X^{(i)}$ must be selected prior to observing any outcomes). We focus on the non-adaptive setting, which is often preferable in practice due to permitting highly parallelized tests. In particular, except where stated otherwise, we consider the widely-adopted (i.i.d.) Bernoulli random test design [1, Sec. 2.1], in which every item is independently placed in each test with probability $\frac{\nu}{k}$ for some $\nu>0$, and we choose $\nu$ to be such that

This choice ensures that the probability of a positive test is exactly $\frac{1}{2}$, which maximizes the entropy of each test outcome. More importantly, this choice of $\nu$ leads to a provably optimal number of tests in broad scaling regimes, as we survey in Section I-B. A simple asymptotic analysis gives $\nu=(\log 2)(1+o(1))$ as $k\to\infty$, which behaves similarly to the choice $\nu=\log 2$, but the exact choice described by (1) will be more convenient to work with.

There have recently been numerous developments on theory and algorithms for probabilistic group testing [14, 15, 16, 17, 13, 18, 19, 20] (see [1] for a survey); here we focus only on those most relevant to the present paper.

The most relevant works to us are those attaining upper and/or lower bounds on the number of tests of the form $\big{(}k\log_{2}\frac{p}{k}\big{)}(1+o(1))$. The most straightforward way that this quantity arises is that with $p\choose k$ possible defective sets and $2^{n}$ possible sequences of outcomes, we require $n\geq\log_{2}{p\choose k}$ for each defective set to produce different outcomes. In the sublinear regime $k=o(p)$, this simplifies to $n\geq\big{(}k\log_{2}\frac{p}{k}\big{)}(1+o(1))$. Building on this intuition, Fano’s inequality was used in [4, 21] to show that $n\geq(1-\delta)\log_{2}{p\choose k}$ is required to attain an error probability of at most $\delta$, and a refined bound $n\geq\log_{2}\big{(}{p\choose k}(1-\delta)\big{)}$ was established in [22].

More recently, various results showed that $\big{(}k\log_{2}\frac{p}{k}\big{)}(1+o(1))$ tests are sufficient for certain recovery guarantees under broad scaling regimes on $k$ as a function of $p$. In [13], high-probability exact recovery was shown to be possible under Bernoulli random testing when $k=O(p^{1/3})$ and $n=\big{(}k\log_{2}\frac{p}{k}\big{)}(1+o(1))$, and in addition, this result was extended to all $k=o(p)$ when the exact recovery criterion is replaced by the following approximate recovery criterion (see also [11]): Output a set $\widehat{S}\subseteq\{1,\dotsc,p\}$ of cardinality $k$ such that

for some $\alpha\in(0,1)$. The above-mentioned result holds for arbitrarily small $\alpha>0$, as long as it is bounded away from zero as $p\to\infty$.

On the other hand, the lower bounds for approximate recovery in [13, 11] only state that in order to attain (2) for fixed $\alpha\in(0,1)$, it is necessary that $n\geq(1-\alpha)\big{(}k\log_{2}\frac{p}{k}\big{)}(1+o(1))$. This suggests that as $\alpha$ increases, the constant factor in the number of tests could be reduced. We will show that the preceding lower bound can in fact be matched with an upper bound using a suitably-chosen non-Bernoulli design, whereas Bernoulli designs can fail even for $\alpha$ close to one when $n$ is slightly smaller than $k\log_{2}\frac{p}{k}$.

While our discussion thus far focuses on Bernoulli designs, in the case of exact recovery, improved bounds have been shown for a different random test design based on near-constant tests-per-item [23, 19, 20], in particular permitting $n=\big{(}k\log_{2}\frac{p}{k}\big{)}(1+o(1))$ for all $k=O(p^{0.409})$ (improving on $O(p^{1/3})$). However, upon moving to approximate recovery with parameter $\alpha$, both designs attain the threshold $n=\big{(}k\log_{2}\frac{p}{k}\big{)}(1+o(1))$ in the limit as $\alpha\to 0$ [11, 24], suggesting that there is less to be gained via the near-constant tests-per-item design under relaxed recovery criteria. Nevertheless, extending our results to this design may be an interesting direction for future work.

Our work is inspired by recent studies of the all-or-nothing behavior of sparse linear regression under i.i.d. Gaussian measurements; see [25] for a study of the maximum-likelihood estimator, and [26, 27] for general estimators. While group testing can be viewed as a non-linear Boolean counterpart to sparse linear regression [28, 29], and our work will adopt the same high-level approach as [26], the details will be very different.

As hinted above, in this paper, our main goal is to investigate the question of when the following mild recovery requirement is possible:

• •

  (Weak recovery) Can we find a set $\hat{S}$ of size $k$ such that $|S\cap\hat{S}|\geq\delta k$ for small $\delta>0$ with some non-zero constant probability?

The study of this goal essentially asks whether we can learn even a small amount of information from the test outcomes. As a result, any hardness result (lower bound on the number of tests) under this criterion serves as a much stronger claim compared to a hardness result for exact recovery.

While our main focus is on weak recovery, we will additionally address the following two recovery goals that are also much milder than exact recovery:

• •

  (Weak detection) Can we perform a hypothesis test on $(\mathbf{X},\mathbf{Y})$ to distinguish between the above group testing model and the “null model” in which $\mathbf{Y}$ is independent of $\mathbf{X}$?

• •

  (Identify a definite defective) Can we identify just a single defective item, i.e., output a single index $\mathcal{I}\in\{1,\dotsc,p\}$ with certainty that $\mathcal{I}\in S$? (Here we also allow “detected errors”, in which the decoder declares that it is uncertain.)

We show in Section II that these goals can be achieved with very few tests using suitably-chosen non-Bernoulli test designs. On the other hand, for Bernoulli designs (studied in Section III), we will see that in sufficiently sparse regimes, these criteria all require essentially the same number of tests as exact recovery.

The main reason that we consider weak detection is that is serves as a useful stepping stone to establishing our negative result for weak recovery under Bernoulli designs. Identifying a definite defective is also not our central focus, but its negative result comes almost for free via our analysis.

Before proceeding, we briefly pause to discuss our emphasis on Bernoulli designs, despite our results demonstrating that they can be inferior to alternative designs under the relaxed recovery criteria. The justification for doing so is that Bernoulli designs (and other related unstructured random designs) are widespread and extensively studied in the literature [1], and thus serve as a standard “go-to” design. As a result, it is essential to not only identify the cases that they succeed, but also understand their limitations.

As discussed in Section I-B, the lower bounds for approximate recovery in [13, 11] state that in order to attain

for fixed $\alpha\in(0,1)$, it is necessary that $n\geq(1-\alpha)(k\log_{2}\frac{p}{k})(1-o(1))$. The following result shows that one can in fact attain a matching upper bound for general test designs.

By letting $\alpha$ be arbitrarily close to one, this result establishes the following corollary.

To prove Theorem 1, we will use the previous best-known positive result on approximate recovery as a stepping stone. This is stated in the following lemma, whose main statement comes from [13, 11], with the second part regarding approximately-known $k$ instead coming from [30, App. B].

Theorem 1 reduces the number of tests in Lemma 1 by a multiplicative factor of $1-\alpha$, and provides an asymptotically optimal result (including the constant). In addition, this result demonstrates that weak recovery is possible whenever $n=\Omega\big{(}k\log_{2}\frac{p}{k}\big{)}$ with an arbitrarily small implied constant. In contrast, we will show in Theorem 6 below that Bernoulli testing requires the implied constant to be one, and hence, the two differ by an arbitrarily large constant factor.

We note that while the preceding analysis still uses Bernoulli testing as a subroutine via Lemma 1, the full $n\times p$ test matrix is not i.i.d. Bernoulli, as a fraction $\alpha^{\prime}$ of its columns are set to zero. Hence, we still consider this to be a non-Bernoulli test design.

Discussion. Since the proof of Theorem 1 is based on ignoring a fraction of the items, it amounts to a technique that immediately gives up on exact recovery, or “cuts its losses” from an early stage. This raises the interesting question as to whether such an approach is actually necessary to obtain the bound in Theorem 1.

To appreciate this distinction, note that Hwang’s adaptive generalized binary splitting algorithm [32] works by repeatedly identifying a single defective using at most $\big{(}\log_{2}\frac{p}{k}\big{)}(1+o(1))$ tests, and then removing it from further consideration. Hence, exact recovery is guaranteed with $n=\big{(}k\log_{2}\frac{p}{k}\big{)}(1+o(1))$, but even if the procedure is stopped after $(1-\alpha)\big{(}k\log_{2}\frac{p}{k}\big{)}(1+o(1))$ tests, one will have already identified $(1-\alpha)k$ defective items. In this sense, Hwang’s adaptive algorithm is universally optimal with respect to the approximate recovery parameter $\alpha$,²²2Note that the lower bound stated following (3) also holds for adaptive algorithms. and the algorithm degrades gracefully as the number of tests decreases below the exact recovery threshold.

In contrast, the non-adaptive designs that we have considered do not enjoy such universality. Under a Bernoulli design with $k=o(p)$, we can achieve approximate recovery with arbitrarily small $\alpha$ when $n=\big{(}k\log_{2}\frac{p}{k}\big{)}(1+o(1))$ (Lemma 1), or even exact recovery if $k=O(p^{1/3})$ [13], but we are prone to complete failure for smaller $n$, at least in sufficiently sparse regimes (see Theorem 6 below). Alternatively, ignoring roughly a fraction $\alpha$ of the items leads to $\alpha$-approximate recovery when $n=(1-\alpha)\big{(}k\log_{2}\frac{p}{k}\big{)}(1+o(1))$, but one retains this guarantee and no better regardless of how much $n$ is increased. Hence, it remains an interesting question for future work as to whether there exists a gracefully degrading (and ideally universally optimal) test matrix design in the non-adaptive setting.

We first describe the weak detection problem in more detail. The goal is to distinguish between two joint distributions on the pair $(\mathbf{X},\mathbf{Y})$ for some specified distribution $P(\mathbf{X})$:

• •

  Under distribution $P$, the X-marginal is $P(\mathbf{X})$, and the joint distribution $P(\mathbf{X},\mathbf{Y})$ is deduced by deterministically computing $\mathbf{Y}$ from $\mathbf{X}$ via the group testing model.

• •

  Under distribution $Q$, the $\mathbf{X}$ and $\mathbf{Y}$ marginals match those of $P$, but $\mathbf{X}$ and $\mathbf{Y}$ are independent, i.e., $Q(\mathbf{X},\mathbf{Y})=P(\mathbf{X})P(\mathbf{Y})$.

This is a binary hypothesis testing problem. The distribution $Q$ corresponds to “completely uninformative outcomes”, so intuitively, if we cannot reliably distinguish between $P$ and $Q$, then we can view the group tests (under the distribution $P$) as being highly uninformative.

As hinted above, for Bernoulli designs, the main reason that we consider weak detection is as a stepping stone to providing a negative result for weak recovery (see Section III). It turns out that if we consider weak detection as a standalone problem with general designs, then a trivial strategy succeeds with very few tests. Formally, we have the following.

This result suggests that weak detection is of limited interest as a standalone recovery criterion in general. Nevertheless, this finding arguably strengthens our subsequent negative results for Bernoulli designs (Section III), in the sense of showing that weak detection is not attained despite being an “extremely easy” goal.

Our negative results for Bernoulli testing in Section III will demonstrate failure in sufficiently sparse regimes (e.g., $k={\rm poly}(\log p)$) when the number of tests is slightly below $\log_{2}{p\choose k}$. On the other hand, fairly simple detection strategy can be used to attain the following positive result under Bernoulli testing when $k\gg p^{1/3}$ and $k=o(p)$.

We first describe the problem of identifying a definite defective in more detail. We suppose that the decoder either outputs a single index $\mathcal{I}\in\{1,\dotsc,p\}$ believed to be defective, or declares “I don’t know” by outputting $\mathcal{I}=0$. In the former scenario, we insist that $\mathcal{I}$ must be defective (i.e., $\mathcal{I}\in S$) with probability one, meaning that the only errors allowed are detected errors corresponding to $\mathcal{I}=0$. This setup is partly motivated by the definite defectives algorithm for recovering the defective set [17, 23], as well as the notion of zero undetected error capacity in information theory [33].

The following result shows that under a suitably-chosen non-Bernoulli test design, a single definitely-defective item can be reliably identified using only $O(\log\frac{p}{k})$ tests, representing a reduction by a factor of $k$ compared to the usual $O(k\log\frac{p}{k})$ scaling.

We briefly mention that the $O\big{(}\log\frac{p}{k}\big{)}$ scaling in Theorem 3 cannot be improved further. To see this, suppose by contradiction that a definite defective could be found with constant (non-zero) probability using $o\big{(}\log\frac{p}{k}\big{)}$ tests. By repeating this procedure with uniformly random shuffling of the items, ignoring any $\mathcal{I}=0$ outcomes and removing any defectives identified, an adaptive group testing algorithm could recover the full defective set using $o\big{(}k\log\frac{p}{k}\big{)}$ tests on average. However, this would violate the standard $\Omega\big{(}k\log\frac{p}{k}\big{)}$ lower bound [1, Sec 1.4], which holds even in the adaptive setting.

Recall from Section II-C that the goal of weak detection is to distinguish $P(\mathbf{X},\mathbf{Y})$ (defined according to the group testing model) from $Q(\mathbf{X},\mathbf{Y}):=P(\mathbf{X})P(\mathbf{Y})$, with $P(\mathbf{X})$ being the i.i.d. Bernoulli distribution using the choice of $\nu$ in (1), and $P(\mathbf{Y})=2^{-n}$.

For concreteness, we consider the Bayesian setting, where the observed pair $(\mathbf{X},\mathbf{Y})$ is drawn from $P$ or $Q$ with probability $\frac{1}{2}$ each. The resulting error probability of the hypothesis test is denoted by $\mathsf{P}_{\mathrm{e}}$. Trivially, choosing the hypothesis via a random guess gives $\mathsf{P}_{\mathrm{e}}=\frac{1}{2}$. It is a standard result in binary hypothesis testing that if $d_{\rm{TV}}(P,Q)\to 0$ as $p\to\infty$, then one cannot do better than random guessing asymptotically, i.e., it is impossible do better than $\mathsf{P}_{\mathrm{e}}=\frac{1}{2}+o(1)$ (e.g., see [35, Sec. 2.3.1]).

Let $D(P\|Q)$ denote the KL divergence between $P$ and $Q$. By Pinsker’s inequality, $D(P\|Q)\to 0$ implies $d_{\rm{TV}}(P,Q)\to 0$, and in addition, $D(P\|Q)\leq\chi^{2}(P\|Q)$ [36], where we define the $\chi^{2}$ divergence

Hence, to prove a hardness result for distinguishing $P$ from $Q$, it suffices to show that $\chi^{2}(P\|Q)\to 0$ as $p\to\infty$. The following theorem gives conditions under which this is the case.

The condition $k=o(p^{\frac{\eta}{1+\eta}})$ holds when $k$ grows sufficiently slowly with respect to $p$, e.g., it holds for arbitrarily small $\eta$ when $k={\rm poly}(\log p)$. On the other hand, it remains open as to whether a similar hardness result can be proved when $k$ grows faster than $\Theta(p^{\frac{\eta}{1+\eta}})$. To address this question, we note the following:

• •

  Theorem 2 above shows that $P$ and $Q$ can be reliably distinguished when $n\geq(1-\eta)\log_{2}{p\choose k}$ and $k=p^{\frac{1+\eta}{3+\eta}+\Omega(1)}$, which essentially reduces to $k\gg p^{1/3}$ for small $\eta$. Thus, $\log_{2}{p\choose k}$ no longer serves as an all-or-nothing threshold in this denser regime. This provides an interesting point of contrast with the analogous sparse linear regression problem [26], where the analogous hardness result to Theorem 4 holds for all $k=O(\sqrt{p})$. In addition, [26, App. C] provides a positive result showing that this threshold is tight.

• •

  Theorem 5 below shows that the above $\chi^{2}$-divergence does not approach zero when $n\geq(1-\eta)\log_{2}{p\choose k}$ and $k=\Omega\big{(}p^{\frac{\eta}{1+\eta}}\big{)}$. Note that $\chi^{2}$-divergence approaching zero is sufficient, but not necessary, for establishing the hardness of distinguishing $P$ from $Q$. Hence, this result does not establish such hardness, but it does show that any proof establishing hardness must move beyond the approach of bounding $\chi^{2}(P\|Q)$.

  In the sparse linear regression problem, a similar limitation regarding the $\chi^{2}$ divergence is overcome by conditioning out certain “catastrophic” low-probability events [26] that blow up the divergence. Unfortunately, it appears to be difficult to identify an analogous event in the group testing problem.

Formally, the second of these is stated as follows.

We are now ready to present our main negative result concerning the weak recovery criterion under Bernoulli testing, and establishing an all-or-nothing threshold at $n\sim k\log_{2}\frac{p}{k}$.

Hence, when $k$ is sufficiently sparse so that $k=o(p^{\frac{\eta}{1+\eta}})$ holds for any $\eta>0$ (e.g., $k={\rm poly}(\log p)$), the threshold $n^{*}=k\log_{2}\frac{p}{k}$ serves as an exact threshold between complete success and complete failure. We note that in previous works, phase transitions were proved in [13, 19, 20] regarding the error probability of recovering the exact defective set, whereas Theorem 6 gives the much stronger statement that one cannot even identify a small fraction of the defective set.

The following negative result for identifying a definite defective (see Section II-D) follows in a straightforward manner from our negative result for weak detection (Theorem 4).

We wrap up this section and Section II by highlighting that for all three of the recovery criteria considered, Bernoulli designs can be highly suboptimal compared to general designs:

• •

  Weak recovery is possible (for general test designs) when $n=\Omega\big{(}k\log\frac{n}{k}\big{)}$ with an arbitrarily small implied constant, whereas Bernoulli testing requires $n=(1+o(1))k\log\frac{n}{k}$ in sufficiently sparse regimes;

• •

  A trivial strategy exists for weak detection with only $O(1)$ tests (for constant error probability), whereas Bernoulli testing requires $n=(1+o(1))k\log\frac{n}{k}$ in sufficiently sparse regimes;

• •

  Identifying a definite defective is possible with $O(\log n)$ tests, whereas Bernoulli testing requires $n=(1+o(1))k\log\frac{n}{k}$ in sufficiently sparse regimes.

Since Bernoulli designs are a prototypical example of an unstructured random design, these results indicate that despite their strong theoretical guarantees (e.g., as established in [13]), significant care should be taken in adopting them when too few tests are available, or when relaxed recovery criteria are considered to be acceptable. Essentially, in such cases, it is much better to “cut one’s losses” early on via a hand-crafted design that targets the less stringent recovery criterion under consideration.