Crackovid: Optimizing Group Testing

• URL: http://arxiv.org/abs/2005.06413v1
• Date: Wed, 13 May 2020 16:40:09 GMT
• Title: Crackovid: Optimizing Group Testing
• Authors: Louis Abraham, Gary B\'ecigneul, Bernhard Sch\"olkopf
• Abstract summary: Given $n$ samples taken from patients, how should we select mixtures of samples to be tested? We consider both adaptive and non-adaptive strategies, and take a Bayesian approach with a prior both for infection of patients and test errors.
• Score: 7.895866278697778
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem usually referred to as group testing in the context of COVID-19. Given $n$ samples taken from patients, how should we select mixtures of samples to be tested, so as to maximize information and minimize the number of tests? We consider both adaptive and non-adaptive strategies, and take a Bayesian approach with a prior both for infection of patients and test errors. We start by proposing a mathematically principled objective, grounded in information theory. We then optimize non-adaptive optimization strategies using genetic algorithms, and leverage the mathematical framework of adaptive sub-modularity to obtain theoretical guarantees for the greedy-adaptive method.

Related papers

• Globally-Optimal Greedy Experiment Selection for Active Sequential Estimation [1.1530723302736279]
  We study the problem of active sequential estimation, which involves adaptively selecting experiments for sequentially collected data. The goal is to design experiment selection rules for more accurate model estimation. We propose a class of greedy experiment selection methods and provide statistical analysis for the maximum likelihood.
  arXiv  Detail & Related papers  (2024-02-13T17:09:29Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions. We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• 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)
• Local policy search with Bayesian optimization [73.0364959221845]
  Reinforcement learning aims to find an optimal policy by interaction with an environment. Policy gradients for local search are often obtained from random perturbations. We develop an algorithm utilizing a probabilistic model of the objective function and its gradient.
  arXiv  Detail & Related papers  (2021-06-22T16:07:02Z)
• Adaptive Sampling for Minimax Fair Classification [40.936345085421955]
  We propose an adaptive sampling algorithm based on the principle of optimism, and derive theoretical bounds on its performance. By deriving algorithm independent lower-bounds for a specific class of problems, we show that the performance achieved by our adaptive scheme cannot be improved in general.
  arXiv  Detail & Related papers  (2021-03-01T04:58:27Z)
• Adaptive Sampling of Pareto Frontiers with Binary Constraints Using Regression and Classification [0.0]
  We present a novel adaptive optimization algorithm for black-box multi-objective optimization problems with binary constraints. Our method is based on probabilistic regression and classification models, which act as a surrogate for the optimization goals. We also present a novel ellipsoid truncation method to speed up the expected hypervolume calculation.
  arXiv  Detail & Related papers  (2020-08-27T09:15:02Z)
• Bloom Origami Assays: Practical Group Testing [90.2899558237778]
  Group testing is a well-studied problem with several appealing solutions. Recent biological studies impose practical constraints for COVID-19 that are incompatible with traditional methods. We develop a new method combining Bloom filters with belief propagation to scale to larger values of n (more than 100) with good empirical results.
  arXiv  Detail & Related papers  (2020-07-21T19:31:41Z)
• Robust Sampling in Deep Learning [62.997667081978825]
  Deep learning requires regularization mechanisms to reduce overfitting and improve generalization. We address this problem by a new regularization method based on distributional robust optimization. During the training, the selection of samples is done according to their accuracy in such a way that the worst performed samples are the ones that contribute the most in the optimization.
  arXiv  Detail & Related papers  (2020-06-04T09:46:52Z)
• 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.