CAREER: The Nature of Average-Case Computation

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

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.