CAREER: The Nature of Average-Case Computation

职业：平均情况计算的本质

• 批准号: 2422342
• 负责人: Pravesh Kothari
• 金额: $ 59.96万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-04-01 至 2026-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2422342&HistoricalAwards=false
• 关键词: CAREER; Nature; Average; Case; Computation

The recent surge in the applications of machine learning is powered by algorithms that learn hidden patterns in large volumes of data. Designing faster and more reliable data analysis algorithms is a key challenge in broadening the scope of such applications. However, researchers have realized that the classical framework of algorithm design is inadequate for this task. This is because large data in almost every application is modeled using statistical models as opposed to the standard worst-case model used in algorithm design. Consequently, central challenges that involve an interplay between algorithms and statistically generated data remain widely unresolved not just in machine learning but also in statistical physics and cryptography. This project will address this critical deficiency by building a principled theory of algorithm design for statistical (aka average-case) data. The new paradigms explored in this work will unify the currently fragmented set of approaches for studying average-case computation. The curriculum development plan outlined in this project will train the next generation of scientists in the algorithmic methods tailor-made for problems in large scale statistical data analysis and disseminate the modern paradigms for understanding computation to both graduate and undergraduate students.Average-case complexity is a central thrust in the theory of computation with a direct impact on potential technological advances in machine learning and cryptography as well as basic questions in statistical physics. Examples include training expressive statistical models such as Gaussian mixture models and Sparse PCA to find patterns in large data in machine learning, ascertaining the security of pseudo-random generators in cryptography, and finding the lowest-energy states of spin-glass systems in statistical physics. Our current understanding of such problems is based on fragmented, domain-specific algorithmic schemes such as statistical query methods and method of moments (in machine learning), belief propagation (in statistical physics), and semidefinite programming hierarchies (in computational complexity). This project is devoted to building a unified theory of average-case computation that offers new tools to design better algorithms, prove sharp lower-bounds, and allow rigorously transferring insights between different specific frameworks. This investigation will build new bridges between theoretical computer science and several adjacent areas including machine learning, statistical physics, algebraic geometry, and probability. In addition, it will further develop the burgeoning understanding of the sum-of-squares semidefinite programming hierarchy, mixture models, and use of solution-space geometry in solving random constraint satisfaction problems.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.

机器学习应用的最新激增是由学习大量数据中隐藏模式的算法提供的。设计更快，更可靠的数据分析算法是扩大此类应用程序范围的关键挑战。但是，研究人员已经意识到，算法设计的经典框架对于此任务不足。这是因为几乎每个应用程序中的大数据都是使用统计模型建模的，而不是算法设计中使用的标准最差模型。因此，涉及算法与统计生成数据之间相互作用的核心挑战不仅在机器学习中，而且在统计物理学和密码学方面都无法解决。该项目将通过建立统计算法设计理论（又称平均案例）数据来解决这一严重缺陷。这项工作中探索的新范例将统一目前的研究平均计算方法。该项目中概述的课程发展计划将以算法方法培训下一代科学家，以量身定制大规模统计数据分析中的问题，并传播现代范式，以了解研究生和本科生的计算，以直接对统计和机器的统计学范围进行统计学上的问题，在统计学方面的范围内，对研究生和本科生进行了研究，这是一个中心势头。示例包括培训表达性统计模型，例如高斯混合模型和稀疏的PCA，以在机器学习中找到大型数据中的模式，确定伪随机发电机在密码学中的安全性，并在统计物理学中找到旋转玻璃系统的最低能量状态。我们目前对此类问题的理解是基于分散的，域特异性的算法方案，例如统计查询方法和矩（机器学习），信念传播（在统计物理学）和半决赛编程层次结构（计算复杂性中）。该项目致力于建立一个平均计算的统一理论，该理论提供了新的工具来设计更好的算法，证明是急剧的下限，并允许在不同的特定框架之间进行严格的转移见解。这项调查将在理论计算机科学与几个相邻领域之间建立新的桥梁，包括机器学习，统计物理学，代数几何和概率。此外，它将进一步发展对方格总和半决赛编程层次结构，混合模型以及解决方案空间几何的使用来解决随机约束满意度问题的新兴理解。该奖项反映了NSF的法定任务，并被认为是通过基金会的知识优点和广泛的影响来评估的支持，并被认为是值得通过评估的支持。