CAREER: Low-Degree Polynomial Perspectives on Complexity

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

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.