Multivariate Histograms and Inference with Finite Sample Guarantees

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

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.