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.