A Probably Approximately Correct Analysis of Group Testing Algorithms

We consider the problem of identifying the defectives from a population of items via a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">non-adaptive group testing</i> framework with a random pooling-matrix design. We analyze the sufficient number of tests needed for <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">approximate set identification</i>, i.e., for identifying <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">almost</i> all the defective and non-defective items with high <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">confidence</i>. To this end, we view the group testing problem as a function learning problem in the probably approximately correct (PAC) framework. We derive sufficiency bounds on the number of tests for popular binary group testing recovery algorithms, namely, combinatorial orthogonal matching pursuit under Bernoulli and near-constant row-weight test designs, and definite defectives under a Bernoulli test design. We compare the derived bounds with the existing ones in the literature for exact recovery both theoretically and using simulations. Finally, we contrast the three cases under consideration in terms of the sufficient testing rate <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">surface</i> and the sufficient number of tests <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">contours</i> across the range of the approximation and confidence levels.