2017 · 98 citations · 25 references
Natural SciencesComputer ScienceMathematicsAlgorithmsProbability TheoryStochastic ProcessesApproximation AlgorithmsBayesian InferenceBayesian StatisticsCommunity DetectionCommunity StructureStatistical InferenceBayesian EstimationEfficient EstimationPosterior Distribution ApproximationPosterior Distribution EstimationPosterior MomentsSample ComplexitySample Complexity AnalysisSemidefinite Programming
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.
25
Noga Alon, Raphael Yuster, Uri Zwick · Journal of the ACM · 1995 · 1K citations · Full text
Mixed membership stochastic blockmodels
Edoardo M. Airoldi, David M. Blei, Stephen E. Fienberg et al. · arXiv (Cornell University) · 2007 · 800 citations · Full text
Community detection thresholds and the weak Ramanujan property
Laurent Massoulié · 2014 · 338 citations · Full text