Computation of confidence sets is central to data science and machine learning, serving as the workhorse of A/B testing and underpinning the operation and analysis of reinforcement learning algorithms [1]. This paper studies the geometry of the minimum-volume confidence sets for the multinomial parameter. When used in place of more standard confidence sets and intervals based on bounds and asymptotic approximation, learning algorithms can exhibit improved sample complexity. Prior work [2] showed the minimum-volume confidence sets are the level-sets of a discontinuous function defined by an exact p-value. While the confidence sets are optimal in that they have minimum average volume, computation of membership of a single point in the set is challenging for problems of modest size. Since the confidence sets are level-sets of discontinuous functions, little is apparent about their geometry. This paper studies the geometry of the minimum volume confidence sets by enumerating and covering the continuous regions of the exact p-value function. This addresses a fundamental question in A/B testing: given two multinomial outcomes, how can one determine if their corresponding minimum volume confidence sets are disjoint? We answer this question in a restricted setting.

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 over 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 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 if chosen at random, a relative risk ratio of 12.6). A cumulative exposure score is computed to account for exposure to multiple individuals that test positive. Over the duration of the study, the exposure score predicts positive cases with a true positive rate of 16.5% and missed detection rate of 79% at a specified operating point.

Construction of tight confidence sets and intervals is central to statistical inference and decision making. This paper develops new theory showing minimum average volume confidence sets for categorical data. More precisely, consider an empirical distribution$\widehat{p}$generated from$n$iid realizations of a random variable that takes one of$k$possible values according to an unknown distribution$p$. This is analogous to a single draw from a multinomial distribution. A confidence set is a subset of the probability simplex that depends on$\widehat{p}$and contains the unknown$p$with a specified confidence. This paper shows how one can construct minimum average volume confidence sets. The optimality of the sets translates to improved sample complexity for adaptive machine learning algorithms that rely on confidence sets, regions and intervals.

Datasets that organize and associate the many identifiers produced by PCs, smartphones, and tablets accessing the internet are referred to as internet device graphs . In this paper, we demonstrate how measurement, tracking, and other internet entities can associate multiple identifiers with a single device or user after coarse associations, e.g ., based on IP-colocation , are made. We employ a Bayesian similarity algorithm that relies on examples of pairs of identifiers and their associated telemetry, including user agent, screen size, and domains visited, to establish pair-wise scores. Community detection algorithms are applied to group identifiers that belong to the same device or user. We train and validate our methodology using a unique dataset collected from a client panel with full visibility, apply it to a dataset of 700 million device identifiers collected over the course of six weeks in the United States, and show that it outperforms several unsupervised learning approaches. Results show mean precision and recall exceeding 90% for association of identifiers at both the device and user levels.

Internet device graphs identify relationships between user-centric internet connected devices such as desktops, laptops, smartphones, tablets, gaming consoles, TV's, etc. The ability to create such graphs is compelling for online advertising, content customization, recommendation systems, security, and operations. We begin by describing an algorithm for generating a device graph based on IP-colocation, and then apply the algorithm to a corpus of over 2.5 trillion internet events collected over the period of six weeks in the United States. The resulting graph exhibits immense scale with greater than 7.3 billion edges (pair-wise relationships) between more than 1.2 billion nodes (devices), accounting for the vast majority of internet connected devices in the US. Next, we apply community detection algorithms to the graph resulting in a partitioning of internet devices into 100 million small communities representing physical households. We validate this partition with a unique ground truth dataset. We report on the characteristics of the graph and the communities. Lastly, we discuss the important issues of ethics and privacy that must be considered when creating and studying device graphs, and suggest further opportunities for device graph enrichment and application.

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(√log(p)/p), where p is the size of the empirical data set.

The paper proposes a novel upper confidence bound (UCB) procedure for identifying the arm with the largest mean in a multi-armed bandit game in the fixed confidence setting using a small number of total samples. The procedure cannot be improved in the sense that the number of samples required to identify the best arm is within a constant factor of a lower bound based on the law of the iterated logarithm (LIL). Inspired by the LIL, we construct our confidence bounds to explicitly account for the infinite time horizon of the algorithm. In addition, by using a novel stopping time for the algorithm we avoid a union bound over the arms that has been observed in other UCB-type algorithms. We prove that the algorithm is optimal up to constants and also show through simulations that it provides superior performance with respect to the state-of-the-art.

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 nonadaptive 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. The 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 with nonadaptive direct (uncompressed) sensing.

This paper studies sequential methods for recovery of sparse signals in high dimensions. When compared with 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(P0||P1), where s is the level of sparsity and D(P0||P1) is the Kullback-Leibler divergence between the underlying distributions. A series of sequential probability ratio tests, 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(P0||P1), achieving the lower bound. For comparison, we show any nonsequential procedure fails provided the number of measurements grows at a rate less than log(n)/D(P1||P0), where n is the total dimension of the problem.

This paper studies the sample complexity of searching over multiple populations. We consider a large number of populations, each corresponding to either distribution P0or P1. The goal of the search problem studied here is to find one population corresponding to distribution P1with 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: nonadaptive sampling methods, which sample each population a predetermined number of times until a population following P1is 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 nonadaptive scheme is presented.

This paper studies the problem of high-dimensional multiple testing and sparse recovery from the perspective of sequential analysis. In this setting, the probability of error is a function of the dimension of the problem. A simple sequential testing procedure is proposed. We derive necessary conditions for reliable recovery in the non-sequential setting and contrast them with sufficient conditions for reliable recovery using the proposed sequential testing procedure. Applications of the main results to several commonly encountered models show that sequential testing can be exponentially more sensitive to the difference between the null and alternative distributions (in terms of the dependence on dimension), implying that subtle cases can be much more reliably determined using sequential methods.