AF:Small: Bayesian Estimation and Constraint Satisfaction

AF:Small：贝叶斯估计和约束满足

• 批准号: 2342192
• 负责人: Prasad Raghavendra
• 金额: $ 59.93万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-03-15 至 2027-02-28
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2342192&HistoricalAwards=false
• 关键词: AF; Small; Bayesian; Estimation; Constraint

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.

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