BIGDATA: F: Testing High Dimensional Distributions without the Curse of Dimensionality

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

Scientists develop descriptions of models that explain their observations. But how many observations are needed to verify the validity of a model? When the model is probabilistic, the resulting question is this: How many samples from a distribution are needed to test whether it has a certain property? Arguably this problem lies at the foundations of scientific thought, and recent years have seen a tremendous body of work in the Computer Science literature trying to close in on the precise sample and time complexity needed to test distribution properties. Often data is high dimensional -- for example, medical records for patients have many entries. However, high dimensional distribution data is notoriously hard to deal with. This project will find new ways of overcoming the difficulties of dealing with high dimensional data, by isolating properties of data occurring in practice that aid in simplifying the distribution testing problems. The broader impact of this project includes advancing the interface of Computer Science, Statistics and Learning. Our methods will be tested on a healthcare dataset, including over 3.7 million patients, and will test the accuracy of common models used to improve healthcare outcomes. Broader impact of this project also includes engagement in Computer Science activities for elementary school children, MIT PRIMES mathematical research with high school students, and participation in activities for promoting women in research. Current work on distribution property testing has focused on properties of single-dimensional distributions such as uniformity, monotonicity, log-concavity, and others, with only a few results on testing properties of high-dimensional distributions. Unfortunately, testing properties of high-dimensional distributions quickly runs into exponential sample complexity lower bounds. The goal of the project is to develop new analysis frameworks for overcoming these lower bounds. Typically the lower bounds construct highly-complex distributions that do not possess a property but are really hard to distinguish from those that do. Our thesis is that such rich structure may not be present in many practical settings of interest. The overarching question of our research then is this: are there reasonable assumptions that one could make about the unknown distribution under which high-dimensional testing problems are more tractable? This research will (1) explore how the expressive language of graphical models can be used to restrict the correlation structure of high-dimensional distributions in ways that can be leveraged for faster testing; and (2) develop analysis frameworks that allow testing generating models of combinatorial structures, such as social networks, from a single or a constant number of samples; this sounds like an oxymoron but it will be made possible with adequate assumptions about the model generating the combinatorial structure. (1) will reveal important connections to Bayesian networks and their use in healthcare decision making, as well as to computational biology and phylogenetics, while (2) will have connections to social network modeling.