Multivariate Histograms and Inference with Finite Sample Guarantees

Stanford University, Stanford CA

Investigators

Abstract

Data that comprise several different measurements on each subject are common for modern big data. In order to store these big data in a database as well as for other applications, it is essential to summarize these big data in a compact form without losing important information. This is known to be a difficult problem due to a phenomenon called the `curse of dimensionality'. This research will implement a concrete plan to overcome this stumbling block for a number of important data analysis tasks. Importantly, the resulting methodology will provide relevant guarantees for the accuracy of these analysis tasks as well as fast algorithms for their implementation. The award will provide support of graduate training through research. Density estimation based on multivariate data is known to be a difficult problem due to the `curse of dimensionality'. But in many applications the density is not the final goal of the inference, rather it is a stepping stone to access other objectives. In particular, the histogram represents a summary of the data for the main purpose of showing important features in the data, such as modes, and for estimating probabilities of subsets of the population. This proposal will address the latter problem directly in order to derive a useful multivariate histogram. The research will develop simultaneous confidence bounds with finite sample guarantees for the probability contents of certain data-dependent subsets of the sample space. It will be shown that these bounds possess certain optimality properties and that the widths of the bounds depend essentially only on the probability content of the sets and not on the dimensionality of the space, thus avoiding the curse of dimensionality. The project will develop fast algorithms to construct a histogram that satisfies these bounds and which therefore inherits these properties. The research will investigate the performance of this histogram, also in regards to detecting important features in the distribution such as modes. 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.