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）算法的能力和局限性，该算法的一类算法，可用于统计算法，但要符合统计的算法，该算法仍是最众所周知的Alg，该算法是一个非常强大的任务。对于给定的统计任务，此框架使我们能够系统地生成可能成功并且是适当最佳（在LDP类中）的算法。该项目旨在通过（1）开发工具来分析新兴算法的局限性，以扩大新民党框架的适用性，以分析以前没有攻击工具的新型统计任务的局限性； （2）理解何时可以通过研究轨道恢复问题来探索代数结构以改善推断，这些轨道恢复问题在数学上既丰富又具有现实世界中的应用，例如冷冻电子显微镜； （3）在贝叶斯推理以外的设置中应用LDP框架，以便对诸如稳健统计和近似算法等领域进行新的启示。该奖项反映了NSF的法定任务，并通过使用基金会的知识分子优点和更广泛的影响审查标准来通过评估来诚实地支持。