We propose an efficient meta-algorithm for Bayesian estimation problems that is based on low-degree polynomials, semidefinite programming, and tensor decomposition. The algorithm is inspired by recent lower bound constructions for sum-of-squares and related to the method of moments. Our focus is on sample complexity bounds that are as tight as possible (up to additive lower-order terms) and often achieve statistical thresholds or conjectured computational thresholds. Our algorithm recovers the best known bounds for community detection in the sparse stochastic block model, a widely-studied class of estimation problems for community detection in graphs. We obtain the first recovery guarantees for the mixed-membership stochastic block model (Airoldi et el.) in constant average degree graphs---up to what we conjecture to be the computational threshold for this model. We show that our algorithm exhibits a sharp computational threshold for the stochastic block model with multiple communities beyond the Kesten--Stigum bound---giving evidence that this task may require exponential time. The basic strategy of our algorithm is strikingly simple: we compute the best-possible low-degree approximation for the moments of the posterior distribution of the parameters and use a robust tensor decomposition algorithm to recover the parameters from these approximate posterior moments.

提出了一种基于低阶多项式、半定规划和张量分解的高效贝叶斯估计问题的元算法，该算法的重点在于尽量紧密（达到添加低阶项的下限），并且通常可以达到统计阈值或猜测的计算阈值。在样本复杂度方面改善了社交网络检测和混合式社交网络模型的恢复保证，并且表明该任务可能需要指数时间。算法的基本策略是计算参数的后验分布的最佳低阶逼近，然后使用一个健壮的张量分解算法从这些近似的后验时刻中恢复参数。

来自少样本的贝叶斯估计：社群检测及相关问题