Statistical physics of inference: thresholds and algorithms

Abstract

Many questions of fundamental interest in today's science can be formulated as inference problems: some partial, or noisy, observations are performed over a set of variables and the goal is to recover, or infer, the values of the variables based on the indirect information contained in the measurements. For such problems, the central scientific questions are: Under what conditions is the information contained in the measurements sufficient for a satisfactory inference to be possible? What are the most efficient algorithms for this task? A growing body of work has shown that often we can understand and locate these fundamental barriers by thinking of them as phase transitions in the sense of statistical physics. Moreover, it turned out that we can use the gained physical insight to develop new promising algorithms. The connection between inference and statistical physics is currently witnessing an impressive renaissance and we review here the current state-of-the-art, with a pedagogical focus on the Ising model which, formulated as an inference problem, we call the planted spin glass. In terms of applications we review two classes of problems: (i) inference of clusters on graphs and networks, with community detection as a special case and (ii) estimating a signal from its noisy linear measurements, with compressed sensing as a case of sparse estimation. Our goal is to provide a pedagogical review for researchers in physics and other fields interested in this fascinating topic.

PACS:

• 89.70.Eg interdisciplinary: computational complexity
• 75.50.Lk magneticproperties of materials: spin glasses and other random magnets
• 64.60.aq networks
• 89.75.-k complex systems

Keywords:

• Bayesian inference
• spin glass theory
• compressed sensing
• stochastic block model
• belief propagation
• phase transitions in computer science

Acknowledgments

We would like to express our gratitude to all our colleagues with whom many of the results presented here have been obtained. In particular, we wish to thank Maria-Chiara Angelini, Jean Barbier, Francesco Caltagirone, T. Castellani, Michael Chertkov, Andrea Crisanti, Leticia F. Cugliandolo, Laurent Daudet, Aurelien Decelle, Angelique Drémeau, Laura Foini, Silvio Franz, Sylvain Gigan, Emmanuelle Gouillart, Jacob E. Jensen, Yoshyiuki Kabashima, Brian Karrer, Lukas Kroc, Srinivas Kudekar, Jorge Kurchan, Marc Lelarge, Antoine Liutkus, Thibault Lesieur, Luca Leuzzi, André Manoel, David Martina, Marc Mézard, Andrea Montanari, Cristopher Moore, Richard G. Morris, Elchanan Mossel, Joe Neeman, Mark Newman, Hidetoshi Nishimori, Boshra Rajaei, Sundeep Rangan, Joerg Reichardt, Federico Ricci-Tersenghi, Alaa Saade, David Saad, Ayaka Sakata, Fran cois Sausset, Christian Schmidt, Christophe Schülke, Guilhem Semerjian, Cosma R. Shalizi, David Sherrington, Alan Sly, Phil Schniter, Eric W. Tramel, Rudiger Urbanke, Massimo Vergassola, Jeremy Vila, Xiaoran Yan, Sun Yifan, Francesco Zamponi, Riccardo Zecchina and Pan Zhang.

A part of this manuscript has been written during a visit to UC Berkeley as part of the semester long program on “Counting complexity and phase transitions”, at the Simons Institute for the Theory of Computing, which we thank for the kind hospitality.

Finally, we also wish to thank Alena and Julie for their continuous support and for letting us work, if only from time to time, on this review.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

Part of the research leading to the presented results has received funding from the European Research Council under the European Union's 7th Framework Programme (FP/2007-2013/ERC Grant Agreement 307087-SPARCS).