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; 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.

考虑一个社交网络，其中个人是节点，它们之间的联系代表关系或互动。 一个基本的计算问题是通过仅观察节点之间的连接来推断节点的属性，例如其中的子组。 在许多情况下，例如蛋白质 - 蛋白质相互作用网络或生物学中的基因调节网络，流行病学中的疾病传播模型和金融网络中的欺诈检测。 更一般而言，这些计算问题是“贝叶斯估计”的示例，其中包括从观察值中确定隐藏的值，这些值通常是嘈杂的和局部的。 更大的观测数量，计算上更容易推断隐藏的值。 换句话说，收集到的数据/观测值与所需的计算资源之间存在权衡。 该项目的目的是限制大量贝叶斯推理问题所需的最小观测值来使推理可行的计算问题。 具体而言，项目中的一个主要主题是精确确定一种强大的算法技术称为“ Suger-Squares SDPS”可以有效地推断出隐藏数量的最小观测值。 贝叶斯估计问题自然出现在各种各样的现实应用中，该项目的结果可能会阐明整个类别的计算限制。bayesian估计是从观察到的数据中推断隐藏变量值的问题。 正式地，该问题是通过一组隐藏变量和观测值的联合分布来指定的。 算法问题是（甚至大致）使用贝叶斯规则（即使）在观察值中推断出隐藏的值。 该项目的主要重点是类似于经典约束满意度问题的贝叶斯估计问题类别。 具体而言，这些是观测值是局部观测的贝叶斯估计问题，因为它们每个都取决于少量的隐藏值，并且是嘈杂的。 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一项易于训练的计算，随着一个项目的数量，该项目将追求以下研究方向。1（SOS下限）SDPS。经典复杂性理论通过减少彼此的问题来比较不同问题的计算难度。 该项目旨在在不同的参数方面开发不同贝叶斯CSP或相同的贝叶斯CSP之间的多项式时间减少。 3。（超出随机实例）该项目将转移在随机贝叶斯CSP的背景下开发的算法洞察力，以转移到最坏的情况下。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛的影响审查标准通过评估来进行评估的。