CAREER: Low-Degree Polynomial Perspectives on Complexity

在整个科学和工业中，海量数据集在现代世界无处不在，它们具有巨大的知识潜力。它们也提出了一个挑战：如何在随机噪声的压倒性存在中最好地提取我们想要的信息——无论是分子的结构、导致疾病的突变，还是网络中的社区结构，等等。获取数据是有成本的，所以我们希望数据分析的算法在统计上是高效的，也就是说，它们对数据的数量和质量有尽可能低的要求。我们也被限制使用计算效率高的算法，也就是说，即使对于非常大的问题，运行时也是实用的。然而，有时根本不可能同时实现这两个目标，本项目旨在了解可能的权衡以及如何实现它们。该项目的结果有望推进可用于设计算法的基础知识，并证明它们在各种情况下都是最佳的。这将加深我们对如何开发大规模统计推断的最佳方法的基本理解，同时考虑到统计和计算方面的考虑。作为该项目的教育计划的一部分，作为数学系成员的研究员将在他所在大学的数据科学专业的发展中发挥主导作用，该专业将吸引来自许多学科的学生。这项工作将包括开发本科阶段的课程材料，以帮助学生在数据科学方面打下坚实的基础。该项目还将包括指导研究生，以培养下一代数据科学家研究人员。具体来说，该项目旨在通过研究低次多项式（LDP）算法的能力和局限性来理解基本的统计计算权衡，这是一类易于分析但仍然非常强大的算法，为广泛的统计任务捕获最知名的算法。对于给定的统计任务，该框架允许我们系统地生成可证明成功且可证明最优的算法（在LDP类中）。该项目旨在通过以下方式扩大LDP框架的适用性：(1)开发工具来分析LDP算法在以前没有工具攻击的新型统计任务中的局限性；(2)了解什么时候代数结构可以通过研究轨道恢复问题来改进推理，这些问题既数学上丰富，又有实际应用，如低温电子显微镜；(3)在贝叶斯推理之外的环境中应用LDP框架，以便为鲁棒统计和近似算法等领域提供新的思路。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Throughout science and industry, massive datasets are ubiquitous in the modern world, and they hold great potential for knowledge. They also pose a challenge: how to best extract the information we desire — be it the structure of a molecule, the mutation responsible for a disease, the community structure in a network, etc. — in the overwhelming presence of random noise. There is a cost to acquiring data, so we desire algorithms for data analysis that are statistically efficient, that is, they have the minimum possible requirements on the quantity and quality of data. We are also constrained to use algorithms that are computationally efficient, that is, the runtime is practical, even for very large problem sizes. However, sometimes it is fundamentally impossible to achieve both these goals simultaneously, and this project aims to understand what tradeoffs are possible and how to achieve them. The results of this project are expected to advance foundational knowledge that can be used to design algorithms and prove they are optimal in a wide variety of settings. This will deepen our fundamental understanding of how to develop the best possible methods for large-scale statistical inference, taking both statistical and computational considerations into account. As part of the education plan for this project, the researcher, who is a member of the mathematics department, will take a leading role in the development of the data science major at his university, which will draw students from many disciplines. This effort will involve development of course materials at the undergraduate level to help students gain a strong foundation in data science. The project will also involve mentorship of graduate students to train the next generation of data scientist researchers.Specifically, this project aims to understand fundamental statistical-computational tradeoffs by studying the power and limitations of low-degree polynomial (LDP) algorithms, a class of algorithms that is tractable to analyze yet still very powerful, capturing the best known algorithms for a wide array of statistical tasks. For a given statistical task, this framework allows us to systematically produce algorithms that both provably succeed and are provably optimal (within the LDP class). This project aims to broaden the LDP framework’s applicability by (1) developing tools to analyze the limitations of LDP algorithms for new types of statistical tasks that previously had no tools to attack; (2) understanding when algebraic structure can be exploited for improved inference by studying orbit recovery problems, which are both mathematically rich and have real-world applications such as cryo-electron microscopy; and (3) applying the LDP framework in settings beyond Bayesian inference in order to shed new light on areas such as robust statistics and approximation algorithms.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.