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

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.