AF: Small: Low-Degree Methods for Optimization in Random Structures. Power and Limitations

AF：小：随机结构优化的低度方法。

• 批准号: 2233897
• 负责人: David Gamarnik
• 金额: $ 53.15万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-05-01 至 2026-04-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2233897&HistoricalAwards=false
• 关键词: AF; Small; Low; Degree; Methods

Optimization tasks for problems involving uncertainty and randomness arise in many areas of applications, including models of network structures and social networks, finance and economics, theoretical computer science, operations research and operations management, statistics and machine learning, statistical physics and material science. The nature and the sources of randomness underlying these optimization tasks vary and are mostly domain specific. Yet a remarkable and fairly generic theme has emerged recently across many of these application areas, dubbed the Statistics-to-Computation gap. This gap refers to the discovery that for many optimization problems the state-of-the-art tractable algorithms (those which can be run in a reasonable time) significantly underperform when compared to algorithms without any computational limits. How fundamental is this gap and what classes of algorithms achieve the best performance within reasonable computational time limits? These are two fundamental questions to be addressed in this project.Recent research activity in this area led to the discovery that tractable algorithms achieving state-of-the-art performance, while on surface are different and problem specific, can be coded as variants of the same algorithm, one based on computing low degree polynomials of the input data. We call this class of algorithms the Low Degree Method (LDM). The first research goal of this project is to investigate this discovery systematically. Specifically, the work will be conducted on (a) Verifying whether LDM-based methods achieve state-of-the-art performance for a broad spectrum of problems, beyond those already known, and identifying candidate problems for which LDM can in fact provide algorithms improving the state-of-the-art, (b) Identifying the potential computational advantage of the LDM based methods, including the speed and parallelism, and finally (c) Establishing the limits of what is achievable by the LDM, and specifically verifying that LDM-based methods provably cannot overcome the Statistics-to-Computation barrier. A concrete, but not exhaustive, class of problems to be considered within the goal (a) includes the problem of finding a largest clique in an Erdos-Renyi random graph, the sparse linear regression problem and the problem of finding a satisfying assignment of a random constraint satisfaction problem, known as random K-SAT problem. The goal (c) is also a segue into the second research goal of this project: establishing a barrier for the LDM-based methods for the problems of high dimensional statistical inference by means of the so-called Overlap Gap Property (OGP) methodology. OGP has been established already as an algorithmic barrier for a wide class of problems of optimization in random structures. Broad classes of algorithms have been ruled out by the OGP-based methods, including local algorithms, various iterative schemes, online algorithms and Boolean circuits. At the same time, OGP-based methodology does not extend to models involving noisy signal, which is unfortunate, since these models arise in a broad variety of important modern statistical and machine learning applications. The second goal of the project is establishing the presence of OGP in high dimensional statistical inference models exhibiting the Statistics-to-Computation gap and establishing that it is a barrier for the same classes of algorithms that have been ruled out in prior models.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.

在应用的许多领域，包括网络结构和社交网络，金融和经济学，理论计算机科学，运营研究与运营管理，统计和机器学习，统计物理学和材料科学的模型，涉及不确定性和随机性的问题的优化任务。这些优化任务的性质和随机性的性质和来源变化，并且主要是特定领域的。然而，最近在许多这样的应用领域中出现了一个了不起且相当普遍的主题，被称为统计数据到计算的差距。该差距是指以下发现：与算法相比，对于许多优化问题，最先进的可拖动算法（可以在合理的时间内运行的算法）明显不佳，而没有任何计算限制。这个差距有多基本，哪些类别的算法在合理的计算时间限制中实现了最佳性能？这是该项目要解决的两个基本问题。该领域的研究活动导致发现，可拖动算法实现最先进的性能，虽然表面上是不同的，并且可以具体地将其编码为同一算法的变体，一种基于计算输入数据低度的多项量的相同算法。我们称此类算法为低度方法（LDM）。该项目的第一个研究目标是系统地研究这一发现。具体而言，这项工作将进行（a）验证基于LDM的方法是否实现了广泛的问题的最先进性能，超出已知的问题，并确定LDM实际上可以为这些问题提供算法可以提供最先进的算法来改善最先进的算法，（b）确定基于LDM的方法的潜在计算优势，包括该方法的速度，并在包括ligs的范围内，以及（最终），并最终（最终）（最终）（最终）（最终）（最终是CC），并确定了速度的范围，并确定了基于ldm的速度。 LDM，特别是验证基于LDM的方法证明无法克服统计到计算障碍。在目标（a）中要考虑的具体但不详尽的问题包括在Erdos-Renyi随机图中找到最大的集团的问题，稀疏的线性回归问题以及找到满足随机约束满意度问题（称为随机K-SAT问题）的问题的问题。目标（c）也是该项目的第二个研究目标：建立基于LDM的方法，以通过所谓的重叠间隙属性（OGP）方法来解决高维统计推断问题的问题。 OGP已经被建立为在随机结构中优化的广泛优化问题的算法障碍。基于OGP的方法排除了广泛的算法类别，包括本地算法，各种迭代方案，在线算法和布尔电路。同时，基于OGP的方法不扩展到涉及嘈杂信号的模型，这是不幸的，因为这些模型出现在各种重要的现代统计和机器学习应用中。该项目的第二个目标是在高维统计推理模型中建立OGP的存在，该模型表现出统计学到计算的差距，并确定它是相同类别的算法的障碍，这些算法已在先前的模型中排除在外。该奖项反映了NSF的法定任务，反映了通过评估基金会和广泛的crtulial and Intfactial and toctial and toctial and tocriatial and tocriatial and tocriatial and tocriatial and Broadia and througial and tocriatial and tocria and tobleit and tocriatial and tobleit and tobrit。