Improving Group Testing via Gradient Descent. Srinivasavaradhan, S. R., Nikolopoulos, P., Fragouli, C., & Diggavi, S. IEEE International Symposium on Information theory, 2022.
Improving Group Testing via Gradient Descent [link]Arxiv  abstract   bibtex   11 downloads  
We study the problem of group testing with non-identical, independent priors. So far, the pooling strategies that have been proposed in the literature take the following approach: a hand-crafted test design along with a decoding strategy is proposed, and guarantees are provided on how many tests are sufficient in order to identify all infections in a population. In this paper, we take a different, yet perhaps more practical, approach: we fix the decoder and the number of tests, and we ask, given these, what is the best test design one could use? We explore this question for the Definite Non-Defectives (DND) decoder. We formulate a (non-convex) optimization problem, where the objective function is the expected number of errors for a particular design. We find approximate solutions via gradient descent, which we further optimize with informed initialization. We illustrate through simulations that our method can achieve significant performance improvement over traditional approaches.
@article{srinivasavaradhan2022improving,
  title={Improving Group Testing via Gradient Descent},
  author={Srinivasavaradhan, Sundara Rajan and Nikolopoulos, Pavlos and Fragouli, Christina and Diggavi, Suhas},
  journal={IEEE International Symposium on Information theory},
  year={2022},
  type={1},
  tags={conf,PET},
  pages={2243-2248},
  url_arxiv={https://arxiv.org/abs/2201.12325},
  abstract={We study the problem of group testing with non-identical, independent priors. So far, the pooling strategies that have been proposed in the literature take the following approach: a hand-crafted test design along with a decoding strategy is proposed, and guarantees are provided on how many tests are sufficient in order to identify all infections in a population. In this paper, we take a different, yet perhaps more practical, approach: we fix the decoder and the number of tests, and we ask, given these, what is the best test design one could use? We explore this question for the Definite Non-Defectives (DND) decoder. We formulate a (non-convex) optimization problem, where the objective function is the expected number of errors for a particular design. We find approximate solutions via gradient descent, which we further optimize with informed initialization. We illustrate through simulations that our method can achieve significant performance improvement over traditional approaches.},
}

Downloads: 11