Data-driven Adaptive Network Models: Quantitative Group Testing
The quantitative group testing (QGT) problem aims at learning an underlying binary vector x of length n with a sparsity parameter k. The information acquisition process about x involves conducting pooled measurements, also known as group tests, where the outcome reveals the number of ones within the pool. This setup is often regarded as a collection of items, with those corresponding to 1 being labeled as defective and the task can be interpreted as identifying presence or absence of defective items at each location with the minimum number of tests.
The applications of this problem extends to a wide variety of domains including that of network traffic control, and resource allocation in random access channels. Strategies addressing the QGT problem can be categorized based on how information is acquired in the testing procedure. In a non-adaptive scenario, all tests must be pre-designed and can potentially be executed in parallel. This implies no feedback from test outcomes that could be utilized to design more effective tests. A precise information-theoretic threshold for non-adaptive schemes has been established in prior works, indicating that for any δ > 0, no algorithm using (1 - δ)m0 tests, where m0 = 2(1-α)/αk, can recover 𝐛 with non-vanishing probability. Conversely, a (randomized) scheme exists that can recover 𝐛 using (1 - δ)m0 tests with high probability. Several non-adaptive algorithms have been proposed in prior works. However, theoretically optimal or near-optimal solutions are often impractical, requiring excessively large parameters for significant improvements compared to more practical alternatives with sub-optimal asymptotic performance. Therefore, our focus lies in assessing the performance of our results compared to practical schemes, which offer efficient decoding methods and demonstrate improvements over general convex relaxation approaches within a moderate range of problem parameters.
Our work on non-adaptive algorithms (Soleymani & Javidi, COLT 2024) introduces a concatenated construction method aimed at reducing the gap between theoretical lower bounds and computational complexity. By leveraging insights from the “balls into bins” problem and conducting meticulous analysis of decoding failure probabilities, we achieve an almost linear decoding complexity for certain regimes of the parameters. This advancement significantly narrows the gap in required tests from log k to loglog k, showcasing practical applicability particularly for moderately large k values.
Soleymani & Javidi (ISIT 2024) proposes an efficient adaptive testing algorithm, implemented in stages, where each stage adapts non-adaptive measurements from previous stages. The number of stages can range from 2 to log(n/k) for a fully adaptive scheme. In the sublinear regime, our algorithm matches state-of-the-art adaptive algorithms with fewer stages, reducing the number of tests by (1-α). Moreover, our approach minimizes the number of stages while maintaining adaptivity, resulting in significant test reduction. With just two stages, our method achieves a 47% reduction in tests compared to efficient non-adaptive strategies, showcasing substantial adaptivity gain.