CAREER: Low-Degree Polynomial Perspectives on Complexity

职业：复杂性的低次多项式视角

• 批准号: 2338091
• 负责人: Alexander Wein
• 金额: $ 63.28万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-02-01 至 2029-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2338091&HistoricalAwards=false
• 关键词: CAREER; Low; Degree; Polynomial; Perspectives

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.

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