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.