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

涉及不确定性和随机性问题的优化任务出现在许多应用领域，包括网络结构和社交网络模型、金融和经济学、理论计算机科学、运筹学和运营管理、统计和机器学习、统计物理学和材料科学。这些优化任务背后的随机性的性质和来源各不相同，并且大多是特定于领域的。然而，最近在这些应用领域中出现了一个引人注目且相当通用的主题，称为统计到计算的差距。这个差距是指发现，对于许多优化问题，最先进的易处理算法（那些可以在合理的时间内运行）与没有任何计算限制的算法相比，显着表现不佳。这种差距有多重要？什么样的算法可以在合理的计算时间限制内实现最佳性能？这是本项目要解决的两个基本问题。最近在这一领域的研究活动导致了这样的发现，即实现最先进性能的易于处理的算法，虽然表面上是不同的和特定的问题，但可以被编码为同一算法的变体，一种是基于计算输入数据的低次多项式。我们称这类算法为低次方法（LDM）。本项目的第一个研究目标是系统地研究这一发现。具体而言，工作将在以下方面进行：（a）确定基于LDM的方法是否在已知问题之外的广泛问题上实现了最先进的性能，并确定LDM实际上可以提供改进最先进算法的候选问题，（B）确定基于LDM的方法的潜在计算优势，包括速度和并行性，最后（c）确定LDM可实现的极限，并具体验证基于LDM的方法可证明无法克服统计到计算的障碍。在目标（a）中要考虑的具体但不详尽的一类问题包括在Erdos-Renyi随机图中找到最大团的问题、稀疏线性回归问题和找到随机约束满足问题的满意分配的问题，称为随机K-SAT问题。目标（c）也是本项目的第二个研究目标的一个延续：通过所谓的重叠间隙属性（OGP）方法，为基于LDM的方法解决高维统计推断问题建立障碍。OGP已经被确立为一个算法的障碍，为广泛的一类问题的优化随机结构。基于OGP的方法已经排除了广泛的算法，包括局部算法，各种迭代方案，在线算法和布尔电路。同时，基于OGP的方法没有扩展到涉及噪声信号的模型，这是不幸的，因为这些模型出现在各种重要的现代统计和机器学习应用中。该项目的第二个目标是在高维统计推断模型中建立OGP的存在，展示统计到计算的差距，并建立它是在先前模型中被排除的同类算法的障碍。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。

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.