Name
Abstract | ||
|---|---|---|
We propose an efficient meta-algorithm for Bayesian estimation problems that is based on low-degree polynomials, semidefinite programming, and tensor decomposition. algorithm is inspired by recent lower bound constructions for sum-of-squares and related to the method of moments. 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. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Data Structures and Algorithms | Combinatorics,Exponential function,Polynomial,Upper and lower bounds,Stochastic block model,Posterior probability,Bayes estimator,Mathematics,Semidefinite programming,Method of moments (statistics) |
DocType | Volume | Citations |
Journal | abs/1710.00264 | 4 |
PageRank | References | Authors |
0.39 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samuel Hopkins | 1 | 88 | 9.47 |
| David Steurer | 2 | 934 | 44.91 |