CAREER: Learning and property testing -- a complexity theoretic perspective

从基因组学到气象学，先进的技术导致了前所未有规模的数据收集。反过来，科学的未来前景在很大程度上取决于我们分析如此庞大而复杂的数据集的能力。为了获得更深入的见解，现代数据分析依赖于称为模型的数学抽象。特别是，机器学习的一个核心需求是找到适合给定数据集的简单模型。因此，理论计算机科学、机器学习和统计学在这方面已经开发了数学和算法框架。这个项目的目标是把这个议程下的计算复杂性理论的透镜。特别是，使用复杂性理论的工具和见解，研究人员将研究（i）机器学习和统计中出现的几个高维模型的有效学习算法，以及（ii）探索这些模型的鲁棒性，效率，数据大小和准确性之间的权衡。除了机器学习的数学基础之外，潜在的问题也出现在从进化生物学到信号处理的各种应用中。通过在复杂性理论，机器学习和统计学的交叉点引入新课程，以及研讨会和研讨会等其他活动，该项目将培养下一代研究生，他们将在所有这些领域实现流利，从而进一步交叉这些学科之间的思想。该项目还将支持旨在吸引本科生，特别是来自代表性不足群体的本科生进行理论计算机科学研究的活动。该项目有两个主要目标：（1）高维模型的噪声容忍学习算法：该项目将研究监督和无监督模型，如线性分离器，高斯混合模型和痕迹重建（这是进化生物学中祖先DNA重建问题的抽象）。对于这些模型，该项目将探索样本效率，计算效率和噪声容限之间的三方面权衡。(2)测试高维模型的稀疏表示的算法：此类模型的示例包括超立方体和高维矩阵上的布尔函数。这里的首要目标是设计算法，其复杂性与环境维度无关，从而避免众所周知的维数灾难。这一广泛议程的基础是布尔函数分析--一套在复杂性理论中开发的工具，它结合了组合学，调和分析和概率论是机器学习和统计学中学习和测试高维模型的有效算法工具。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值进行评估而被认为值得支持和更广泛的影响审查标准。

From genomics to meteorology, advanced technology has led to collection of data at an unprecedented scale. In turn, the future promise of science is crucially reliant on our ability to analyze such massive and complex datasets. To gain deeper insights here, modern data analysis relies on mathematical abstractions called models. In particular, a central desideratum of machine learning is to find simple models which fit a given dataset. Accordingly, theoretical computer science, machine learning and statistics have developed both mathematical and algorithmic frameworks in this pursuit. The goal of this project is to put this agenda under the lens of computational complexity theory. In particular, using tools and insights from complexity theory, the investigator will study (i) efficient learning algorithms for several high-dimensional models which appear in machine learning and statistics, and (ii) explore the tradeoffs between robustness, efficiency, data size and accuracy for these models. Besides the mathematical foundations of machine learning, the underlying questions also appear in a wide variety of applications ranging from evolutionary biology to signal processing. Through the introduction of new courses at the intersection of complexity theory, machine learning and statistics, as well as other activities such as workshops and seminars, the project will train the next generation of graduate students who will achieve fluency in all of these areas leading to a further cross-pollination of ideas between these disciplines. The project will also support activities aimed at attracting undergraduate students to research in theoretical computer science, especially those from underrepresented groups. The project has two principal thrusts: (1) Noise tolerant learning algorithms for high-dimensional models: The project will study both supervised and unsupervised models such as linear separators, Gaussian mixture models and trace reconstruction (which is an abstraction of the problem of ancestral DNA reconstruction from evolutionary biology). For these models, the project will explore the three-way tradeoff between sample efficiency, computational efficiency and noise tolerance. (2) Algorithms to test high dimensional models for sparse representations: Examples of such models include Boolean functions over the hypercube and high-dimensional matrices. The overarching goal here is to design algorithms whose complexity is independent of the ambient dimension, thus avoiding the proverbial curse of dimensionality. Underlying this broad agenda is the insight that Boolean function analysis -- a suite of tools developed in complexity theory which combines combinatorics, harmonic analysis and probability theory -- is an effective algorithmic tool for learning and testing high dimensional models in machine learning and statistics.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.