Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems

We propose an efficient meta-algorithm for Bayesian inference problems 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 partial recovery in the stochastic block model, a widely-studied class of inference problems for community detection in graphs. We obtain the first partial recovery guarantees for the mixed-membership stochastic block model (Airoldi et el.) for constant average degree-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.

Authors

• Samuel B. Hopkins 0001
• David Steurer

Keywords

• Stochastic processes
• Algorithm design and analysis
• Complexity theory
• Correlation
• Estimation
• Inference algorithms
• Prediction algorithms
• Bayesian Estimation
• Community Detection
• Posterior Probability
• Conjecture
• Stochastic Model
• Inference Problem
• Semidefinite Programming
• Tensor Decomposition
• Stochastic Block Model
• Phase Transition
• Efficient Algorithm
• Independent Component Analysis
• Estimation Problem
• Second Moment
• Constant Factor
• Observable Variables
• Color Code
• Probability Vector
• Polynomial-time Algorithm
• Random Graph
• Previous Algorithms
• Belief Propagation
• Moment Tensor
• Left-hand Side Of Eq
• Hidden Variables
• Indicator Vector
• Right-hand Side Of Eq
• Dirichlet Distribution
• Statistical Physics
• Constant Degree
• Bayesian inference
• stochastic blockmodel
• low-degree polynomials
• sum of squares algorithms
• average-case hardness
• phase transitions