AF:Small: Bayesian Estimation and Constraint Satisfaction

Consider a social network where individuals are nodes and connections between them represent relationships or interactions. A basic computational problem is to infer attributes of the nodes, such as subgroups among them, by only observing the connections between the nodes. The same problem arises in numerous contexts such as protein-protein interaction networks or gene regulatory networks in biology, disease spread models in epidemiology and fraud detection in financial networks. More generally, these computational problems are examples of "Bayesian estimation" which consists of determining hidden values from observations, that are often noisy and local. Greater the number of observations, it gets computationally easier to infer the hidden values. In other words, there is a tradeoff between data/observations collected vs computational resources needed. This project aims to pin-down the minimum number of observations needed to make the computational problem of inference feasible, for a large class of Bayesian inference problems. Concretely, a major theme in the project will be to precisely determine the minimum number of observations at which a powerful algorithmic technique called "sum-of-squares SDPs" can efficiently infer the hidden quantities. Bayesian estimation problems arise naturally in a vast variety of real-life applications, and the project's results will likely shed light on the computational limits for this entire class. Bayesian estimation is the problem of inferring the values of hidden variables from observed data. Formally, the problem is specified by a joint distribution over a set of hidden variables and observations. The algorithmic problem is to (even approximately) infer the hidden values given the observations, using the Bayes rule. The central focus of this project are a class of Bayesian estimation problems analogous to classical constraint satisfaction problems. Specifically, these are Bayesian estimation problems where the observations are local, in that each of them depend on a small number of hidden values, and are noisy. For brevity, we refer to these problems as ``Bayesian CSPs". They generalize a variety of models like planted CSPs, semi-random models, and stochastic block models. There is an emerging precise and comprehensive theory of computational complexity of random instances of Bayesian CSPs. Inspired by ideas from statistical physics, this theory predicts that Bayesian CSPs undergo a computational phase transition wherein they abruptly go from being computationally easy to intractable, as one increases the number of observations This project will pursue the following research directions. 1. (SoS lower bounds) Sum-of-squares SDPs are one of the most powerful and general algorithmic techniques known. The project will establish lower bounds for sum-of-squares SDPs as evidence towards computational hardness of random Bayesian CSPs upto the predicted computational phase transition. 2. (Reductions) Classical complexity theory compares computational difficulty of different problems by reducing problems to each other. This project aims to develop polynomial-time reductions between different Bayesian CSPs or the same Bayesian CSP in different parameter regimes. 3. (Beyond random instances) The project will transfer algorithmic insights developed in the context of random Bayesian CSPs, to worst-case settings. 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.