AF: Large: Collaborative Research: Algebraic Proof Systems, Convexity, and Algorithms

这个项目通过“平方和”算法框架的镜头，解决了算法、优化和机器学习理论中的一些核心问题。特别是，它将使我们了解哪些函数类可以有效地最小化，以及这样做需要什么计算资源。如果成功，这将极大地促进我们在所有这些关键领域的理解，产生新的实用算法方法，并与其他领域建立新的联系，包括量子信息理论、统计物理、极值图论等。这项合作拨款将促进迄今为止互动相对较少的知识界之间的新互动，私人投资机构将组织研讨会、课程和其他活动，将这些社区聚集在一起。受训的学生和博士后将对这些地区的景观有一个独特的广泛看法。PI提出了一种统一的方法来开发和分析凸证明系统，其中包括并推广了“平方和”(SOS)方法。尽管最近取得了相当大的进步，但对于大多数当前的技术来说，理解SOS？S的表现似乎是遥不可及的。这一领域的重大进展需要综合不同领域的思想和技术，包括理论计算机科学、优化、代数几何、量子信息理论和机器学习。研究计划包括理论构建和问题解决两个方面，最终目标是完全理解SOS方法和相关的证明系统，以及它们的算法含义。研究工作将沿着几个方向进行：唯一博弈和相关问题(小集合扩展、最大割、稀疏割)、平均情况问题的分析(例如，种植集团)、机器学习的应用(稀疏PCA、字典学习)、SOS的算法加速以及与数学和物理的联系(例如，量子纠缠、p自旋眼镜、极图理论和代数几何)。虽然主要关注的是理论方面，但这个项目也关注有效的计算方法，结果可能会产生新的实用技术，用于机器学习和优化。该提案的其他关键特征包括与课程开发、本科生研究项目的紧密结合，以及培训下一波研究生和博士后，并为他们配备必要的工具，以在这些领域开展工作。

This project tackles some of the central questions in algorithms, optimization, and the theory of machine learning, through the lens of the "Sum of Squares" algorithmic framework. In particular, it will allow us to understand what classes of functions can be efficiently minimized, and what computational resources are needed to do so. If successful, this will significantly advance our understanding in all these key areas, produce new practical algorithmic methodologies, as well as build new connections with other fields, including quantum information theory, statistical physics, extremal graph theory and more.This collaborative grant will foster new interactions between intellectual communities that have had relatively little interaction so far, and the PIs will organize workshops, courses, and other events that bring these communities together. The students and postdocs trained will gain a uniquely broad view of the landscape of these areas.The PIs propose a unified approach to the development and analysis of convex proof systems that include and generalize the "Sum of Squares" (SoS) method. Despite considerable recent progress, understanding SoS?s performance seems to be out-of-reach for most current techniques. Significant progress in this area requires the synthesis of ideas and techniques from different domains, including theoretical computer science, optimization, algebraic geometry, quantum information theory and machine learning. The research plans include both theory-building and problem-solving aspects, with the ultimate goal of obtaining a complete understanding of the SoS method and related proof systems, as well as their algorithmic implications.Research efforts will be directed along several thrusts: Unique Games and related problems (Small Set Expansion, Max Cut, Sparsest Cut), analysis of average-case problems (e.g., Planted Clique), applications to Machine Learning (sparse PCA, dictionary learning), algorithmic speedups of SoS, and connections to math and physics (e.g., quantum entanglement, p-spin glasses, extremal graph theory and algebraic geometry). While the main focus is on theoretical aspects, this project is also concerned with effective computational methods, and the outcomes may yield novel practical techniques for machine learning and optimization.Other key features of this proposal include its strong integration with curriculum development, undergraduate research projects, and training the next wave of graduate students and postdocs and equipping them with the necessary tools to work across these areas.