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

职业：学习和属性测试——复杂性理论的视角

• 批准号: 2045128
• 负责人: Anindya De
• 金额: $ 42.1万
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-07-01 至 2026-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2045128&HistoricalAwards=false
• 关键词: CAREER; Learning; property; testing; complexity

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.

从基因组学到气象学，先进的技术已经以前所未有的规模收集了数据。反过来，科学的未来承诺至关重要，这是我们分析这种庞大和复杂数据集的能力。为了在这里获得更深入的见解，现代数据分析依赖于称为模型的数学抽象。特别是，机器学习的中央愿望是找到适合给定数据集的简单模型。因此，理论计算机科学，机器学习和统计数据在此追求中既开发了数学和算法框架。该项目的目的是将该议程置于计算复杂性理论的视角下。特别是，使用复杂性理论的工具和见解，研究者将研究（i）有效的多种高维模型的学习算法，这些模型出现在机器学习和统计中，以及（ii）探索这些模型的稳健性，效率，数据大小和准确性之间的权衡。除了机器学习的数学基础外，基本问题还出现在从进化生物学到信号处理的各种应用中。通过在复杂性理论，机器学习和统计数据以及研讨会和研讨会等其他活动的交集中引入新课程，该项目将培训下一代的研究生，这些研究生将在所有这些领域中获得流利性，从而实现这些学科之间的思想进一步交叉授粉。该项目还将支持旨在吸引本科生研究理论计算机科学研究的活动，尤其是来自代表性不足的小组的活动。该项目有两个主要的推力：（1）高维模型的噪声耐受性学习算法：该项目将研究监督和无监督的模型，例如线性分离器，高斯混合物模型和痕量重建（这是从进化生物学中祖先DNA重建问题的抽象）。对于这些模型，该项目将探索样本效率，计算效率和噪声耐受性之间的三路权衡。 （2）测试稀疏表示的高维模型的算法：此类模型的示例包括超立方体和高维矩阵上的布尔函数。这里的总体目标是设计复杂性独立于环境维度的算法，从而避免了维度的概念。基于这个广泛的议程是一个见解，即布尔功能分析（一组复杂性理论开发的工具，结合了组合主义，谐波分析和概率理论）是一种有效的算法工具，用于学习和测试机器学习和统计中高维模型的高维模型。该奖项反映了NSF的法定任务，并通过评估了构成的范围。

项目成果

Learning a mixture of two subspaces over finite fields

• 发表时间: 2020-10
• 期刊: ArXiv
• 作者: Aidao Chen;Anindya De;Aravindan Vijayaraghavan

Testing Convex Truncation

测试凸截断

• 发表时间: 2023
• 期刊: Proceedings of the 2023 {ACM-SIAM} Symposium on Discrete Algorithms
• 作者: De, Anindya;Nadimpali, Shivam;Servedio, Rocco A.
• 通讯作者: Servedio, Rocco A.

Approximate Trace Reconstruction from a Single Trace

从单个迹线进行近似迹线重建

• 发表时间: 2023
• 期刊: Proceedings of the annual ACMSIAM Symposium on Discrete Algorithms
• 作者: Chen, Xi;De, Anindya;Lee, Chin Ho;Sinha, Sandip;Servedio, Rocco A.
• 通讯作者: Servedio, Rocco A.

Detecting Low-Degree Truncation

检测低度截断

• 发表时间: 2024
• 期刊: Proceedings of the annual ACM Symposium on Theory of Computing
• 作者: De, Anindya;Li, Huan;Nadimpalli, Shivam;Servedio, Rocco A.
• 通讯作者: Servedio, Rocco A.

Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas

• DOI: 10.48550/arxiv.2309.12513
• 发表时间: 2023-09
• 期刊: ArXiv
• 作者: Xi Chen;Anindya De;Yuhao Li;Shivam Nadimpalli;R. Servedio