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

AF：大型：协作研究：代数证明系统、凸性和算法

• 批准号: 1565264
• 负责人: Boaz Barak
• 金额: $ 86.5万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-05-01 至 2022-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1565264&HistoricalAwards=false
• 关键词: AF; Large; Collaborative; Research; Algebraic

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.

这个项目通过“平方和”算法框架的透镜来解决算法、优化和机器学习理论中的一些核心问题。特别是，它将使我们能够理解哪些类的函数可以有效地最小化，以及需要什么计算资源来做到这一点。如果成功的话，这将大大推进我们在所有这些关键领域的理解，产生新的实用算法方法，以及与其他领域建立新的联系，包括量子信息理论，统计物理，极值图论等。这项合作资助将促进迄今为止互动相对较少的知识社区之间的新互动，PI将组织研讨会，课程，以及其他将这些社区聚集在一起的活动。经过培训的学生和博士后将获得这些领域独特的广阔视野。PI提出了一种统一的方法来开发和分析凸证明系统，其中包括并推广了“平方和”（SoS）方法。尽管最近取得了相当大的进展，但了解SoS？的性能似乎是目前大多数技术所无法企及的。这一领域的重大进展需要综合来自不同领域的思想和技术，包括理论计算机科学、优化、代数几何、量子信息理论和机器学习。研究计划包括理论构建和问题解决两个方面，最终目标是获得对SoS方法和相关证明系统的完整理解，以及它们的算法含义。研究工作将沿着几个方向进行：独特的游戏和相关问题（小集扩展，最大割，稀疏割），平均情况问题的分析（例如，Planted Clique）、机器学习的应用（稀疏PCA、字典学习）、SoS的算法加速以及与数学和物理的联系（例如，量子纠缠，p-自旋玻璃，极值图论和代数几何）。虽然主要关注的是理论方面，但该项目也关注有效的计算方法，其结果可能会产生机器学习和优化的新实用技术。该提案的其他主要特点包括与课程开发，本科生研究项目，培训下一批研究生和博士后，并为他们提供必要的工具，使他们能够在这些领域工作。