CAREER: Efficient Algorithms for Learning and Testing Structured Probabilistic Models

近年来，科技领域的可用数据量呈爆炸式增长，目前正以前所未有的速度扩张。在大型和复杂的数据集上做出准确推断的一般任务已经成为跨越各个学科的主要瓶颈。这种推理任务的自然形式化包括将数据视为从概率模型中提取的随机样本--我们认为该模型描述了生成数据的过程。这个项目的首要目标是从统计和计算的角度对这些推理任务有一个更好的理解。本项目涉及的问题源于现代数据分析面临的紧迫挑战。该项目的一个重要组成部分涉及促进不同社区之间的合作。此外，PI将指导高中生和本科生，并在本科和研究生层面设计几个新的理论课程，整合研究和教学。PI将研究非监督学习和测试中的几个基本算法问题，这些问题在我们目前的理解中存在着令人震惊的差距。这些措施包括设计有效的算法，在与假设模型存在偏差的情况下保持稳定，绕过分布学习中的维度诅咒，以及测试高维概率模型。这一系列方向可能会导致新的算法和概率技术，并为非监督估计中结构和效率之间的相互作用提供见解。这项研究涉及到更广泛的工作，涉及计算机科学、概率论、统计学和信息论。

In recent years, the amount of available data in science and technology has exploded and is currently expanding at an unprecedented rate. The general task of making accurate inferences on large and complex datasets has become a major bottleneck across various disciplines. A natural formalization of such inference tasks involves viewing the data as random samples drawn from a probabilistic model -- a model that we believe describes the process generating the data. The overarching goal of this project is to obtain a refined understanding of these inference tasks from both statistical and computational perspectives. The questions addressed in this project arise from pressing challenges faced in modern data analysis. A crucial component of the project involves fostering collaboration between different communities. Furthermore, the PI will mentor high-school and undergraduate students, and design several new theory courses integrating research and teaching at the undergraduate and graduate levels.The PI will investigate several fundamental algorithmic questions in unsupervised learning and testing for which there is an alarming gap in our current understanding. These include designing efficient algorithms that are stable in the presence of deviations from the assumed model, circumventing the curse of dimensionality in distribution learning, and testing high-dimensional probabilistic models. This set of directions could lead to new algorithmic and probabilistic techniques, and offer insights into the interplay between structure and efficiency in unsupervised estimation. This research ties into a broader range of work across computer science, probability, statistics, and information theory.