AF:Small: Bayesian Estimation and Constraint Satisfaction

考虑一个社会网络，其中个人是节点，它们之间的连接代表关系或交互。一个基本的计算问题是仅通过观察节点之间的连接来推断节点的属性，例如其中的子组。同样的问题出现在许多环境中，如生物学中的蛋白质-蛋白质相互作用网络或基因调控网络，流行病学中的疾病传播模型和金融网络中的欺诈检测。更一般地说，这些计算问题是“贝叶斯估计”的例子，它包括从观察中确定隐藏值，这些值通常是嘈杂的和局部的。观察值越多，在计算上推断隐藏值就越容易。换句话说，收集的数据/观察值与所需的计算资源之间存在权衡。该项目旨在确定使推理计算问题可行所需的最小观测数，用于大型贝叶斯推理问题。具体地说，该项目的一个主要主题将是精确地确定最小观测次数，在这种情况下，一种称为“平方和sdp”的强大算法技术可以有效地推断隐藏量。贝叶斯估计问题自然出现在各种各样的实际应用中，项目的结果可能会揭示整个课程的计算极限。贝叶斯估计是从观测数据中推断隐变量值的问题。形式上，这个问题是由一组隐变量和观测值的联合分布来指定的。算法问题是（甚至近似地）推断出给定观察值的隐藏值，使用贝叶斯规则。本课题的中心焦点是一类类似于经典约束满足问题的贝叶斯估计问题。具体来说，这些是贝叶斯估计问题，其中观测值是局部的，因为每个观测值都依赖于少量隐藏值，并且有噪声。为简洁起见，我们将这些问题称为“贝叶斯csp”。他们推广了各种模型，如种植csp，半随机模型和随机块模型。关于贝叶斯csp随机实例的计算复杂度，出现了一种精确而全面的理论。受统计物理学思想的启发，该理论预测贝叶斯csp会经历一个计算相变，随着观测数量的增加，它们会突然从计算上容易变为难以处理。（SoS下界）平方和sdp是已知的最强大和通用的算法技术之一。该项目将建立平方和sdp的下界，作为随机贝叶斯csp计算硬度的证据，直至预测的计算相变2。（约简）经典复杂性理论通过将不同问题相互约简来比较不同问题的计算难度。本项目旨在开发不同贝叶斯CSP之间或相同贝叶斯CSP在不同参数体系中的多项式时间缩减。3. （超越随机实例）该项目将把在随机贝叶斯csp背景下开发的算法见解转移到最坏情况下。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.