- This event has passed.
Sample-optimal inference, computational thresholds, and the methods of moments
April 7 @ 11:00 am
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. Our algorithm also captures smooth trade-offs between sample and computational complexity, for example, for tensor principal component analysis. In contrast, we show that our algorithm exhibits a sharp computational threshold for 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.
Joint work with Samuel B. Hopkins (Cornell).