Group testing and local search: is there a computational-statistical gap?

Abstract

In this work we study the fundamental limits of approximate recovery in the context of group testing. One of the most well-known, theoretically optimal, and easy to implement testing procedures is the non-adaptive Bernoulli group testing problem, where all tests are conducted in parallel, and each item is chosen to be part of any certain test independently with some fixed probability. In this setting, there is an observed gap between the number of tests above which recovery is information theoretically (IT) possible, and the number of tests required by the currently best known efficient algorithms to succeed. Often times such gaps are explained by a phase transition in the landscape of the solution space of the problem (an Overlap Gap Property phase transition). In this paper we seek to understand whether such a phenomenon takes place for Bernoulli group testing as well. Our main contributions are the following: (1) We provide first moment evidence that, perhaps surprisingly, such a phase transition does not take place throughout the regime for which recovery is IT possible. This fact suggests that the model is in fact amenable to local search algorithms ; (2) we prove the complete absence of "bad" local minima for a part of the "hard" regime, a fact which implies an improvement over known theoretical results on the performance of efficient algorithms for approximate recovery without false-negatives, and finally (3) we present extensive simulations that strongly suggest that a very simple local algorithm known as Glauber Dynamics does indeed succeed, and can be used to efficiently implement the well-known (theoretically optimal) Smallest Satisfying Set (SSS) estimator.

arXiv commentAccepted for publication in COLT 2021. Various minor mistakes are corrected

References in corpus (13)

• Clustering of solutions in the random satisfiability problem
• Group Testing: An Information Theory Perspective
• Evolution of scaling emergence in large-scale spatial epidemic spreading
• A statistical model for tensor PCA
• On independent sets in random graphs
• Computational Barriers to Estimation from Low-Degree Polynomials
• Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure
• Near-Optimal Noisy Group Testing via Separate Decoding of Items
• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
• Sparse High-Dimensional Linear Regression. Algorithmic Barriers and a Local Search Algorithm
• Free Energy Wells and Overlap Gap Property in Sparse PCA
• On Accelerated Testing for COVID-19 Using Group Testing
• On the All-Or-Nothing Behavior of Bernoulli Group Testing