Phase Transitions in the Pooled Data Problem
In this paper, we study the pooled data problem of identifying the labels associated with a large collection of items, based on a sequence of pooled tests revealing the counts of each label within the pool. In the noiseless setting, we identify an exact asymptotic threshold on the required number of tests with optimal decoding, and prove a phase transition between complete success and complete failure. In addition, we present a novel noisy variation of the problem, and provide an information-theoretic framework for characterizing the required number of tests for general random noise models. Our results reveal that noise can make the problem considerably more difficult, with strict increases in the scaling laws even at low noise levels. Finally, we demonstrate similar behavior in an approximate recovery setting, where a given number of errors is allowed in the decoded labels.
In the pooled data problem there are p items, each of which is assigned 1 of d possible labels. The goal is to recover the vector of labels from n "pooled tests." In each of these tests, a "pool" (subset of the items) is chosen and we observe how many items in the pool have each label (but not which items have which). A random prior on the label vector is used: the proportion with which each label occurs in the population is fixed, and the true labelling is chosen independently among all labellings that exactly obey these proportions. This paper considers the non-adaptive case where all the pools (subsets) must be chosen in advance. The focus is mainly on the case of Bernoulli random pools: the incidence matrix of pools versus items has iid Bernoulli(q) entries for some fixed 0 < q < 1. The objective is exact recovery of the label vector, although extensions to approximate recovery are considered in the appendix.
This paper proves information-theoretic lower bounds for the pooled data problem, both in the noiseless setting described above and in a very general noisy model.
In the noiseless setting with Bernoulli random pools, they prove the following sharp phase transition. The regime is where the number of samples is n = c*p/log(p) for a constant c, with p tending to infinity. They find the exact constant C such that if c > C then exact recovery is possible with success probability tending to 1, and if c < C then any procedure will fail with probability tending to 1. The constant C depends on the number of labels and the proportions of each label (but not on the constant q which determines the pool sizes). The upper bound was known previously; this paper proves the tight lower bound (i.e. the impossibility result), improving upon a loose bound in prior work.
The sharp information-theoretic threshold above is not known to be achieved by any efficient (i.e. polynomial time) algorithm. Prior work (citation [4] in the paper) suggests that efficient algorithms require a different threshold (in which n scales proportionally to p).
The key technical insight used in this paper to prove the sharp lower bound is the following "genie argument." Let G be some subset of {1,..,d} (the label values), and imagine revealing the labels of all the items that have labels not in G. Now apply a more standard lower bound to this setting, and optimize G in order to get the strongest possible bound.
The other contribution of this paper is to the noisy setting, which has not previously been studied. This paper defines a very general noise model where each observation is corrupted via an arbitrary noisy channel. They give a lower bound for exact recovery in this setting, and specialize it to certain concrete cases (e.g. Gaussian noise). The proof of the lower bound is based on a variant of the above genie argument, combined with standard lower bounds based on Fano's inequality.
Unfortunately there are no existing upper bounds for the noisy setting, so it is hard to judge the strength of this lower bound. The authors do, however, argue for its efficacy in a few different ways. First, it recovers the sharp results for the noiseless case and also recovers known bounds for the "group testing" problem, which is essentially the special case of 2 labels: "defective" and "non-defective" (and you want to identify the defective items). Furthermore, the lower bound for Gaussian noise is strong enough to show an asymptotic separation between the noiseless and noisy cases: while in the noiseless case it is necessary and sufficient for n to be of order p/log(p), the noisy case requires n to be at least p*log(p).
In the conclusion, the authors pose the open question of finding upper bounds for the noisy setting and provide some justification as to why this seem difficult using existing techniques.
I think this is a good paper and I recommend its acceptance. The exposition is good. The sharp lower bound for the noiseless case is a very nice result, and the proof technique seems to be novel. The lower bound for the noisy case is also a nice contribution; although it is hard to judge whether or not it should be tight (since no upper bound is given), it is certainly nontrivial, using the genie argument to surpass standard methods.
Specific comment:
- I think there is a typo in Table 2: the heading "exact recovery" should be "noiseless." (If I understand correctly, the entire table pertains to exact recovery.)