AF:Small:Managing Correlation in Selection and Sampling Problems

University Of Southern California, Los Angeles CA

Investigators

Abstract

Algorithms are being increasingly tasked with the analysis and synthesis of data, and randomness in this data plays a central role in the design of these algorithms. This project is concerned with how correlation in the data, whether naturally present in input data or undesirable in output data, must influence the design of these algorithms. There are two thrusts to this project, which share common technical challenges. The first thrust will examine how correlation in input data must factor into algorithmic decision making in the presence of uncertainty. With algorithms tasked with the allocation of resources in commerce, healthcare, industry, and government, often in view of present and future uncertainty, it is crucial to understand how correlation between present and future events impacts the quality of these decisions. Such understanding will enable the automated and efficient allocation of resources in such domains. The second thrust of this project will examine how algorithms which make randomized decisions can minimize correlations in their decisions. This is motivated in large part by applications to national security. In particular, algorithms are already tasked with the allocation of security resources for the protection of vital national assets, and the decisions made by these algorithms are often deliberately randomized in order to make them less predictable to an adversary. Whereas some correlation in these decisions is often unavoidable due to logistical constraints, too much correlation renders these algorithms vulnerable to information leakage through surveillance. Algorithms which minimize this correlation are less vulnerable to information leakage, and hence ultimately less predictable and more effective. The first thrust of this project is primarily concerned with stochastic selection problems, which capture a myriad of applications in the aforementioned domains. Here, a stochastic set of "requests" is presented to the algorithm, and the algorithm must decide which of the requests to grant, subject to constraints, with the goal of optimizing some domain-specific objective. Most prior work has assumed that requests are stochastically independent, and this assumption was crucial in enabling algorithms for near-optimal selection. Much less is understood when the requests are correlated, and in particular positively correlated, despite such correlation arising naturally in many of the intended applications. Recent work by the primary investigator initiates the systematic study of correlation in stochastic selection problems, and this project follows up on this agenda. In particular, this thrust of the project will characterize "benign" correlation permitting approximately-optimal selection, and design efficient and near-optimal algorithms for such scenarios. The second thrust of this project is primarily concerned with sampling a random subset of a given set of objects, subject to constraints on the set as well as on the probability of including each element in the sample. This task forms a crucial subroutine in a variety of applications, including the aforementioned security scenarios. The goal is to minimize correlation between different objects to the extent permitted by the imposed constraints. The basic models for limited-correlation samplings were introduced in joint work by the primary investigator, and heuristic algorithms applying that work to security settings have already been delivered to governmental security agencies. This thrust of the project will put that line of work on firm theoretical ground by formally characterizing the constraints which permit sampling with limited correlation, and designing efficient algorithms for such sampling with provable guarantees. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.