Multivariate Histograms and Inference with Finite Sample Guarantees

在现代大数据中，包含对每个主题的几种不同测量的数据很常见。为了将这些大数据存储在数据库中以及用于其他应用程序，必须以紧凑的形式总结这些大数据，而不丢失重要信息。由于一种被称为“维度诅咒”的现象，这是一个众所周知的难题。本研究将实施一个具体的计划，以克服这一绊脚石的一些重要的数据分析任务。重要的是，所得到的方法将为这些分析任务的准确性提供相关保证，并为其实现提供快速算法。该奖项将通过研究为研究生培训提供支持。由于“维数诅咒”的存在，基于多变量数据的密度估计一直是一个难题。但是在许多应用程序中，密度并不是推理的最终目标，而是通向其他目标的垫脚石。特别是，直方图表示数据的摘要，其主要目的是显示数据中的重要特征，例如模式，并用于估计总体子集的概率。这个建议将直接解决后一个问题，以便得到一个有用的多元直方图。该研究将开发具有有限样本保证的样本空间中某些数据相关子集的概率内容的同时置信界限。我们将证明这些边界具有一定的最优性，并且边界的宽度基本上只取决于集合的概率内容，而不取决于空间的维数，从而避免了维数的诅咒。该项目将开发快速算法来构建满足这些界限的直方图，从而继承这些属性。该研究将调查该直方图的性能，以及关于检测分布中的重要特征（如模式）的性能。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.