Description:

Title: Statistical-Computational Tradeoffs in Random Optimization Problems

Abstract: Optimization problems with random objective functions are central in computer science, probability, and modern data science. Despite their ubiquity, finding efficient algorithms for solving these problems remains a major challenge. Interestingly, many random optimization problems share a common feature, dubbed as a statistical-computational gap: while the optimal value can be pinpointed non-constructively (through, e.g., probabilistic/information-theoretic tools), all known polynomial-time algorithms find strictly sub-optimal solutions. That is, an optimal solution can only be found through brute force search which is computationally expensive. 

In this talk, I will discuss an emerging theoretical framework for understanding the fundamental computational limits of random optimization problems, based on the Overlap Gap Property (OGP). This is an intricate geometrical property that achieves sharp algorithmic lower bounds against the best known polynomial-time algorithms for a wide range of random optimization problems. I will focus on two models to demonstrate the power of the OGP framework: (a) the symmetric binary perceptron, a random constraint satisfaction problem and a simple neural network classifying/storing random patterns, widely studied in computer science, probability, and statistics communities, and (b) the random number partitioning problem as well as its planted counterpart, a classical worst-case NP-hard problem whose average-case variant is closely related to the design of randomized controlled trials. In addition to yielding sharp algorithmic lower bounds, our techniques also give rise to new toolkits for the study of statistical-computational tradeoffs in other models, including the online setting.