Sample-optimal inference, computational thresholds, and the methods of moments

 Abstract: 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).

 Biography:  David Steurer is an Assistant Professor in the department of computer science at Cornell University and a Visiting Assistant Professor at the Institute for Advanced Study in Princeton. His research interests are in the theory of algorithms, complexity, and machine learning. Steurer received his PhD from Princeton University advised by Sanjeev Arora and was a postdoctoral researcher at Microsoft Research for two years before joining Cornell University. For his work, he received an ACM Doctoral Dissertation Award Honorable Mention, an NSF CAREER Award, and an Alfred P. Sloan Research Fellowship, a Microsoft Research Faculty Fellowship, and best paper awards at STOC and FOCS.