Decelle–Krzakala–Moore–Zdeborová parameter-estimation threshold conjecture

About 14 years old · traced to

Let G(n,a/n,b/n)\mathcal{G}(n,a/n,b/n) be the sparse planted partition model with two equal-sized clusters and parameters a>b>0a>b>0. A consistent estimator of aa and bb is an estimator whose estimates converge to the true parameters as n→∞n\to\infty. Decelle–Krzakala–Moore–Zdeborová's parameter-estimation conjecture. If

(a−b)2>2(a+b),(a-b)^2>2(a+b),

then there is a consistent estimator for aa and bb under G(n,a/n,b/n)\mathcal{G}(n,a/n,b/n); conversely, if

(a−b)2<2(a+b),(a-b)^2<2(a+b),

then there is no consistent estimator. This predicts that parameter estimation has the same phase transition as community recovery in the sparse two-block model. The source presents the claim as a conjectural extension of statistical work on parameter estimation and gives no proof of either direction.

References

Primary source

Elchanan Mossel, Joe Neeman and Allan Sly, “Stochastic Block Models and Reconstruction”, arXiv:1202.1499 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.