Source author record

Matthew L. Malloy

Matthew L. Malloy appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Information Theory math.IT Machine Learning math.OC math.ST Networking and Internet Architecture Social and Information Networks Statistics Theory

Catalog footprint

What is connected

7works

8topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Network-Side Digital Contact Tracing on a Large University Campus

We describe a study conducted at a large public university campus in the United States which shows the efficacy of network log information for digital contact tracing and prediction of COVID-19 cases. Over the period of January 18, 2021 to May 7, 2021, more than 216 million client-access-point associations were logged across more than 11,000 wireless access points (APs). The association information was used to find potential contacts for approximately 30,000 individuals. Contacts are determined using an AP colocation algorithm, which supposes contact when two individuals connect to the same WiFi AP at approximately the same time. The approach was validated with a truth set of 350 positive COVID-19 cases inferred from the network log data by observing associations with APs in isolation residence halls reserved for individuals with a confirmed (clinical) positive COVID-19 test result. The network log data and AP-colocation have a predictive value of greater than 10%; more precisely, the contacts of an individual with a confirmed positive COVID-19 test have greater than a 10\% chance of testing positive in the following 7 days (compared with a 0.79% chance when chosen at random, a relative risk ratio of 12.6). Moreover, a cumulative exposure score is computed to account for exposure to multiple individuals that test positive. Over the duration of the study, the cumulative exposure score predicts positive cases with a true positive rate of 16.5% and missed detection rate of 79% at a specified operating point.

preprint2021arXiv

Optimal Confidence Regions for the Multinomial Parameter

Construction of tight confidence regions and intervals is central to statistical inference and decision making. This paper develops new theory showing minimum average volume confidence regions for categorical data. More precisely, consider an empirical distribution $\widehat{\boldsymbol{p}}$ generated from $n$ iid realizations of a random variable that takes one of $k$ possible values according to an unknown distribution $\boldsymbol{p}$. This is analogous to a single draw from a multinomial distribution. A confidence region is a subset of the probability simplex that depends on $\widehat{\boldsymbol{p}}$ and contains the unknown $\boldsymbol{p}$ with a specified confidence. This paper shows how one can construct minimum average volume confidence regions, answering a long standing question. We also show the optimality of the regions directly translates to optimal confidence intervals of linear functionals such as the mean, implying sample complexity and regret improvements for adaptive machine learning algorithms.

preprint2015arXiv

Contamination Estimation via Convex Relaxations

Identifying anomalies and contamination in datasets is important in a wide variety of settings. In this paper, we describe a new technique for estimating contamination in large, discrete valued datasets. Our approach considers the normal condition of the data to be specified by a model consisting of a set of distributions. Our key contribution is in our approach to contamination estimation. Specifically, we develop a technique that identifies the minimum number of data points that must be discarded (i.e., the level of contamination) from an empirical data set in order to match the model to within a specified goodness-of-fit, controlled by a p-value. Appealing to results from large deviations theory, we show a lower bound on the level of contamination is obtained by solving a series of convex programs. Theoretical results guarantee the bound converges at a rate of $O(\sqrt{\log(p)/p})$, where p is the size of the empirical data set.

preprint2014arXiv

Near-Optimal Adaptive Compressed Sensing

This paper proposes a simple adaptive sensing and group testing algorithm for sparse signal recovery. The algorithm, termed Compressive Adaptive Sense and Search (CASS), is shown to be near-optimal in that it succeeds at the lowest possible signal-to-noise-ratio (SNR) levels, improving on previous work in adaptive compressed sensing. Like traditional compressed sensing based on random non-adaptive design matrices, the CASS algorithm requires only k log n measurements to recover a k-sparse signal of dimension n. However, CASS succeeds at SNR levels that are a factor log n less than required by standard compressed sensing. From the point of view of constructing and implementing the sensing operation as well as computing the reconstruction, the proposed algorithm is substantially less computationally intensive than standard compressed sensing. CASS is also demonstrated to perform considerably better in practice through simulation. To the best of our knowledge, this is the first demonstration of an adaptive compressed sensing algorithm with near-optimal theoretical guarantees and excellent practical performance. This paper also shows that methods like compressed sensing, group testing, and pooling have an advantage beyond simply reducing the number of measurements or tests -- adaptive versions of such methods can also improve detection and estimation performance when compared to non-adaptive direct (uncompressed) sensing.

preprint2014arXiv

Sequential Testing for Sparse Recovery

This paper studies sequential methods for recovery of sparse signals in high dimensions. When compared to fixed sample size procedures, in the sparse setting, sequential methods can result in a large reduction in the number of samples needed for reliable signal support recovery. Starting with a lower bound, we show any coordinate-wise sequential sampling procedure fails in the high dimensional limit provided the average number of measurements per dimension is less then log s/D(P_0||P_1) where s is the level of sparsity and D(P_0||P_1) the Kullback-Leibler divergence between the underlying distributions. A series of Sequential Probability Ratio Tests (SPRT) which require complete knowledge of the underlying distributions is shown to achieve this bound. Motivated by real world experiments and recent work in adaptive sensing, we introduce a simple procedure termed Sequential Thresholding which can be implemented when the underlying testing problem satisfies a monotone likelihood ratio assumption. Sequential Thresholding guarantees exact support recovery provided the average number of measurements per dimension grows faster than log s/ D(P_0||P_1), achieving the lower bound. For comparison, we show any non-sequential procedure fails provided the number of measurements grows at a rate less than log n/D(P_1||P_0), where n is the total dimension of the problem.

preprint2013arXiv

The Sample Complexity of Search over Multiple Populations

This paper studies the sample complexity of searching over multiple populations. We consider a large number of populations, each corresponding to either distribution P0 or P1. The goal of the search problem studied here is to find one population corresponding to distribution P1 with as few samples as possible. The main contribution is to quantify the number of samples needed to correctly find one such population. We consider two general approaches: non-adaptive sampling methods, which sample each population a predetermined number of times until a population following P1 is found, and adaptive sampling methods, which employ sequential sampling schemes for each population. We first derive a lower bound on the number of samples required by any sampling scheme. We then consider an adaptive procedure consisting of a series of sequential probability ratio tests, and show it comes within a constant factor of the lower bound. We give explicit expressions for this constant when samples of the populations follow Gaussian and Bernoulli distributions. An alternative adaptive scheme is discussed which does not require full knowledge of P1, and comes within a constant factor of the optimal scheme. For comparison, a lower bound on the sampling requirements of any non-adaptive scheme is presented.

preprint2012arXiv

Near-Optimal Compressive Binary Search

We propose a simple modification to the recently proposed compressive binary search. The modification removes an unnecessary and suboptimal factor of log log n from the SNR requirement, making the procedure optimal (up to a small constant). Simulations show that the new procedure performs significantly better in practice as well. We also contrast this problem with the more well known problem of noisy binary search.