Statistical and Computational Phase Transitions in Group Testing
- URL: http://arxiv.org/abs/2206.07640v1
- Date: Wed, 15 Jun 2022 16:38:50 GMT
- Title: Statistical and Computational Phase Transitions in Group Testing
- Authors: Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Alexander S.
Wein, Ilias Zadik
- Abstract summary: We study the group testing problem where the goal is to identify a set of k infected individuals carrying a rare disease.
We consider two different simple random procedures for assigning individuals tests.
- Score: 73.55361918807883
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the group testing problem where the goal is to identify a set of k
infected individuals carrying a rare disease within a population of size n,
based on the outcomes of pooled tests which return positive whenever there is
at least one infected individual in the tested group. We consider two different
simple random procedures for assigning individuals to tests: the
constant-column design and Bernoulli design. Our first set of results concerns
the fundamental statistical limits. For the constant-column design, we give a
new information-theoretic lower bound which implies that the proportion of
correctly identifiable infected individuals undergoes a sharp "all-or-nothing"
phase transition when the number of tests crosses a particular threshold. For
the Bernoulli design, we determine the precise number of tests required to
solve the associated detection problem (where the goal is to distinguish
between a group testing instance and pure noise), improving both the upper and
lower bounds of Truong, Aldridge, and Scarlett (2020). For both group testing
models, we also study the power of computationally efficient (polynomial-time)
inference procedures. We determine the precise number of tests required for the
class of low-degree polynomial algorithms to solve the detection problem. This
provides evidence for an inherent computational-statistical gap in both the
detection and recovery problems at small sparsity levels. Notably, our evidence
is contrary to that of Iliopoulos and Zadik (2021), who predicted the absence
of a computational-statistical gap in the Bernoulli design.
Related papers
- Precise Error Rates for Computationally Efficient Testing [75.63895690909241]
We revisit the question of simple-versus-simple hypothesis testing with an eye towards computational complexity.
An existing test based on linear spectral statistics achieves the best possible tradeoff curve between type I and type II error rates.
arXiv Detail & Related papers (2023-11-01T04:41:16Z) - Statistical Performance Guarantee for Subgroup Identification with
Generic Machine Learning [1.0878040851638]
We develop uniform confidence bands for estimation of the group average treatment effect sorted by generic ML algorithm (GATES)
We analyze a clinical trial of late-stage prostate cancer and find a relatively large proportion of exceptional responders.
arXiv Detail & Related papers (2023-10-12T01:41:47Z) - Group Testing with Non-identical Infection Probabilities [59.96266198512243]
We develop an adaptive group testing algorithm using the set formation method.
We show that our algorithm outperforms the state of the art, and performs close to the entropy lower bound.
arXiv Detail & Related papers (2021-08-27T17:53:25Z) - Deep Learning in current Neuroimaging: a multivariate approach with
power and type I error control but arguable generalization ability [0.158310730488265]
A non-parametric framework is proposed that estimates the statistical significance of classifications using deep learning architectures.
A label permutation test is proposed in both studies using cross-validation (CV) and resubstitution with upper bound correction (RUB) as validation methods.
We found in the permutation test that CV and RUB methods offer a false positive rate close to the significance level and an acceptable statistical power.
arXiv Detail & Related papers (2021-03-30T21:15:39Z) - Group Testing with a Graph Infection Spread Model [61.48558770435175]
Infection spreads via connections between individuals and this results in a probabilistic cluster formation structure as well as a non-i.i.d. infection status for individuals.
We propose a class of two-step sampled group testing algorithms where we exploit the known probabilistic infection spread model.
Our results imply that, by exploiting information on the connections of individuals, group testing can be used to reduce the number of required tests significantly even when infection rate is high.
arXiv Detail & Related papers (2021-01-14T18:51:32Z) - Tracking disease outbreaks from sparse data with Bayesian inference [55.82986443159948]
The COVID-19 pandemic provides new motivation for estimating the empirical rate of transmission during an outbreak.
Standard methods struggle to accommodate the partial observability and sparse data common at finer scales.
We propose a Bayesian framework which accommodates partial observability in a principled manner.
arXiv Detail & Related papers (2020-09-12T20:37:33Z) - Active pooling design in group testing based on Bayesian posterior
prediction [0.0]
In identifying infected patients in a population, group testing is an effective method to reduce the number of tests and correct the test errors.
In this paper, an adaptive design method of pools based on the predictive distribution is proposed in the framework of Bayesian inference.
arXiv Detail & Related papers (2020-07-27T06:50:24Z) - Noisy Adaptive Group Testing using Bayesian Sequential Experimental
Design [63.48989885374238]
When the infection prevalence of a disease is low, Dorfman showed 80 years ago that testing groups of people can prove more efficient than testing people individually.
Our goal in this paper is to propose new group testing algorithms that can operate in a noisy setting.
arXiv Detail & Related papers (2020-04-26T23:41:33Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.