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 会经历计算相变，随着数量的增加，它们会突然从计算容易变得难以处理。观察结果 该项目将追求以下研究方向：1.（SoS 下界）平方和 SDP 是已知的最强大和通用的算法技术之一。该项目将建立平方和 SDP 的下界：随机贝叶斯 CSP 的计算难度与预测的计算相变的证据。2.（简化）经典复杂性理论通过相互简化问题来比较不同问题的计算难度。 该项目旨在开发不同贝叶斯 CSP 之间或不同参数状态下相同贝叶斯 CSP 之间的多项式时间缩减。 3.（超越随机实例）该项目将把在随机贝叶斯 CSP 背景下开发的算法见解转移到最坏的情况设置。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优点和更广泛的评估进行评估，被认为值得支持影响审查标准。