CAREER: Algorithms for understanding data

给出一些未知分布的样本，人们可以从潜在的分布中推断出什么，以及做出这些推断的效率有多高？在许多最基本的环境中，我们对计算和信息理论的可能性和障碍的理解仍然令人震惊地糟糕。这个项目涉及两个广泛的研究目标：开发用于探测数据的高效算法，以及了解如何有效地估计分布的性质。研究的第一条线试图理解关于数据集的哪些问题可以非常有效地得到回答，这需要计算资源(时间或内存)，这些资源与数据集或分布的大小是次线性的。第二个研究目标是了解高概率地确定分布或数据集是否具有给定属性所需的最少信息量。在统计属性估计的背景下，这个问题询问需要多少样本才能以高概率将所述属性估计到所需的精度。这项研究既追求新的估计算法，也追求新的信息论工具和下限。随着从遗传学、生物和医学数据库到记录我们的经济和社会行为的数据库等多个学科涌现出大量重要的数据集，如何理解它们的挑战具有特别直接的相关性，并迅速成为科学理解的瓶颈。这个项目中调查的具体问题出现在对这些数据集的分析中；这些问题的算法进步有可能很快被采用，并改变正在进行的数据分析工作。除了对数据科学的直接影响外，这些问题都是极其基础和基础性的。因此，从他们的研究中收集到的新技术、新观点和新见解可能会对整个计算机科学、统计学、信息论和数据科学的其他问题产生广泛的影响。

Given samples from some unknown distribution, what can one infer about the underlying distribution, and how efficiently can these inferences be made?  In many of the most fundamental settings, our understanding of the computational and information theoretic possibilities and barriers is still startlingly poor.  This project tackles two broad research objectives: developing efficient algorithms for probing data, and understanding how to efficiently estimate properties of distributions.  The first line of research seeks to understand which questions about a dataset can be answered extremely efficiently, requiring computational resources (time, or memory) that are sublinear in the size of the dataset or distribution.  The second research objective is to understand the minimal amount of information necessary to ascertain, with high probability, whether or not a distribution or dataset possesses a given property.  In the context of statistical property estimation, this problem asks how few samples are needed to estimate the property in question to a desired accuracy, with high probability.  This research pursues both new estimation algorithms, and new information theoretic tools and lower bounds.With vast and important datasets emerging across many disciplines, from genetic, biological, and medical databases, to databases documenting our economic and social behaviors, the challenge of how to make sense of them has particular immediate relevance and has rapidly become the bottleneck in scientific understanding.   The specific problems investigated in this project arise in the analysis of these datasets; algorithmic advances on these problems have the potential to very quickly be adopted and transform ongoing data analysis efforts.   Beyond the immediate implications for the data sciences, these questions are extremely basic and foundational. As such, new techniques, perspectives, and insights gleaned from their study are likely to have broad implications for other problems throughout computer science, statistics, information theory, and the data sciences.