English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Many inference problems, notably the stochastic block model (SBM) thatgenerates a random graph with a hidden community structure, undergo phasetransitions as a function of the signal-to-noise ratio, and can exhibit hardphases in which optimal inference is information-theoretically possible butcomputationally challenging. In this paper we refine this description byemphasizing the existence of more generic phase diagrams with a hybrid-hardphase in which it is computationally easy to reach a non-trivial inferenceaccuracy, but computationally hard to match the information theoreticallyoptimal one. We support this discussion by quantitative expansions of thefunctional cavity equations that describe inference problems on sparse graphs.These expansions shed light on the existence of hybrid-hard phases, for a largeclass of planted constraint satisfaction problems, and on the question of thetightness of the Kesten-Stigum (KS) bound for the associated treereconstruction problem. Our results show that the instability of the trivialfixed point is not a generic evidence for the Bayes-optimality of the messagepassing algorithms. We clarify in particular the status of the symmetric SBMwith 4 communities and of the tree reconstruction of the associated Pottsmodel: in the assortative (ferromagnetic) case the KS bound is always tight,whereas in the disassortative (antiferromagnetic) case we exhibit an explicitcriterion involving the degree distribution that separates a large degreeregime where the KS bound is tight and a low degree regime where it is not. Wealso investigate the SBM with 2 communities of different sizes, a.k.a. theasymmetric Ising model, and describe quantitatively its computational gap as afunction of its asymmetry, and a version of the SBM with 2 groups ofcommunities. We complement this study with numerical simulations of the BeliefPropagation algorithm.

Typology of phase transitions in Bayesian inference problems