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的存在，显示统计到计算的差距，并确定它是先前模型中已排除的同类算法的障碍。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.