Search

This paper considers the problem of adaptive group testing for isolating up to $k$ defective items from a population of size $n$. There exist restrictions or preferences which determine how the items can be pooled for testing. A graphical model formalizes the pooling restrictions and preferences. Such graph-constrained group testing is investigated in three settings: populations with defectives, populations facing the potential presence of inhibitors, and populations with community structures. Adaptive group testing frameworks are provided for each setting. In populations without inhibitors, existing non adaptive frameworks can isolate the defective items perfectly with $\Theta(k \log n/k)$ number of tests, where is the $\beta$ -mixing time of a random walk over the underlying graph. This paper provides a two-stage framework that can perfectly isolate up to $k$ defective items for a regular graph using $\Theta(k2 \log n k + k)$ number of tests, thus achieving an approximate gain of a factor of $k$ over the non-adaptive frameworks. This twostage framework's principles are extended to community-structured graphs and graphs with up to $r$ inhibitor items. In particular, when inhibitors are present in the graph, a four-stage group testing framework is proposed. The results show that in the regime $r= O(k)$ for a fully connected graph, $\Theta ((k+r)\log n/(k+r) + r\log n)$ tests are sufficient for isolating the defective items. This matches the corresponding necessary condition on tests which scales $(k+r)\log n$. The adaptive graphconstrained group testing framework is also empirically evaluated. [ABSTRACT FROM AUTHOR]

Stochastic gradient descent (SGD) has become the method of choice for training highly complex and nonconvex models since it can not only recover good solutions to minimize training errors but also generalize well. Computational and statistical properties are separately studied to understand the behavior of SGD in the literature. However, there is a lacking study to jointly consider the computational and statistical properties in a nonconvex learning setting. In this paper, we develop novel learning rates of SGD for nonconvex learning by presenting high-probability bounds for both computational and statistical errors. We show that the complexity of SGD iterates grows in a controllable manner with respect to the iteration number, which sheds insights on how an implicit regularization can be achieved by tuning the number of passes to balance the computational and statistical errors. As a byproduct, we also slightly refine the existing studies on the uniform convergence of gradients by showing its connection to Rademacher chaos complexities. [ABSTRACT FROM AUTHOR]

Group testing refers to the process of testing pooled samples to reduce the total number of tests. Given the current pandemic, and the shortage of test supplies for COVID-19, group testing can play a critical role in time and cost efficient diagnostics. In many scenarios, samples collected from users are also accompanied with auxiliary information (such as demographics, history of exposure, onset of symptoms). Such auxiliary information may differ across patients, and is typically not considered while designing group testing algorithms. In this paper, we abstract such heterogeneity using a model where the population can be categorized into clusters with different prevalence rates. The main result of this work is to show that exploiting knowledge heterogeneity can further improve the efficiency of group testing. Motivated by the practical constraints and diagnostic considerations, we focus on two-stage group testing algorithms, where in the first stage, the goal is to detect as many negative samples by pooling, whereas the second stage involves individual testing to detect any remaining samples. For this class of algorithms, we prove that the gain in efficiency is related to the concavity of the number of tests as a function of the prevalence. We also show how one can choose the optimal pooling parameters for one of the algorithms in this class, namely, doubly constant pooling. We present lower bounds on the average number of tests as a function of the population heterogeneity profile, and also provide numerical results and comparisons. [ABSTRACT FROM AUTHOR]

The basic goal of threshold group testing is to identify up to $d$ defective items among a population of $n$ items, where $d$ is usually much smaller than $n$. The outcome of a test on a subset of items is positive if the subset has at least $u$ defective items, negative if it has up to $\ell $ defective items, where $0 \leq \ell < u$ , and arbitrary otherwise. This is called threshold group testing. The parameter $g = u - \ell - 1$ is called the gap. In this paper, we focus on the case $g > 0$ , i.e., threshold group testing with a gap. Note that the results presented here are also applicable to the case $g = 0$ ; however, the results are not as efficient as those in related work. Currently, a few reported studies have investigated test designs and decoding algorithms for identifying defective items. Most of the previous studies have not been feasible because there are numerous constraints on their problem settings or the decoding complexities of their proposed schemes are relatively large. Therefore, it is compulsory to reduce the number of tests as well as the decoding complexity, i.e., the time for identifying the defective items, for achieving practical schemes. The work presented here makes five contributions. The first is a more accurate theorem for a non-adaptive algorithm for threshold group testing proposed by Chen and Fu. The second is an improvement in the construction of disjunct matrices, which are the main tools for tackling (threshold) group testing and other tasks such as constructing cover-free families or learning hidden graphs. Specifically, we present a better exact upper bound on the number of tests for disjunct matrices compared with that in related work. The third and fourth contributions are a reduced exact upper bound on the number of tests and a reduced asymptotic bound on the decoding time for identifying defective items in a noisy setting on test outcomes. The fifth contribution is a simulation on the number of tests of the resulting improvements for previous work and the proposed theorems. [ABSTRACT FROM AUTHOR]

This paper studies the problem of developing an efficient signal sampling framework for distributed blind spectrum sensing, together with the corresponding local cognitive radio (CR) decision and fusion rules. A novel collaborative sampling and binary output (CSBO) generating scheme is proposed to overcome the disadvantage of traditional energy detectors for blind spectrum sensing, in which the signal-to-noise ratio (SNR) and level of noise power at the CRs are unknown and thus the decision threshold of local energy detectors cannot be specified. In designing the fusion rule in conjunction with the proposed CSBO scheme, both fixed-sample-size tests and sequential tests are considered. It is theoretically shown that the proposed CSBO scheme outperforms traditional blind cooperative energy detectors with uniform sampling schemes in terms of its ability to increase the amount of information acquired under a given number of samples. Simulation results confirm the theoretical analyses, and demonstrate that, compared with the fixed-sample-size test, the sequential test requires fewer observations on average to achieve comparable detection performance. The reduction in the expected sample size needed in the sequential CSBO test when compared to the fixed-sample-size CSBO can reach 50% when primary signal is present. [ABSTRACT FROM AUTHOR]