CAREER: The Nature of Average-Case Computation

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

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.