Statistical physics of inference: Thresholds and algorithms

2015/11/30 by Lenka Zdeborová, Florent Krzakala, Florent Krząkała · 429 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Artificial intelligence #Complex Network Analysis Techniques #Computer science #Data science #Focus (optics) #Inference #Ising model #Machine learning #Markov Chains and Monte Carlo Methods #Mathematics #Physics #Set (abstract data type) #Statistical inference #Statistical physics #Theoretical and Computational Physics #Theoretical computer science #cond-mat.stat-mech #cs.DS #stat.ML

paper · pdf · doi:10.1080/00018732.2016.1211393

published in Advances In Physics 65(5), 453-552 (Taylor & Francis) · 86 pages, 16 Figures. Review article based on HDR thesis of the first author and lecture notes of the second

openalex publication_date 2016/08/19 · arxiv created 2018/01/22 · arxiv updated 2018/01/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

Many questions of fundamental interest in todays 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. 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.

Citations

• Monte Carlo sampling methods using Markov chains and their applications

Cited by

• Statistical Physics of Deep Learning: Optimal Learning of a Multilayer Perceptron near Interpolation
• There Will Be a Scientific Theory of Deep Learning
• Graphs are maximally expressive for higher-order interactions
• Learning to erase quantum states: thermodynamic implications of quantum learning theory
• Dilution of Ferromagnets via a Random Graph-based Strategy
• Critical properties of disordered XY model on sparse random graphs
• Optimizing information transmission in the canonical Wnt pathway
• Universality of the fluctuations of the free energy in generalized Sherrington-Kirkpatrick models and the log likelihood ratio in spiked Wigner models
• Replica Analysis for Generalized Linear Regression with IID Row Prior
• Statistical and computational challenges in ranking
• Learning transitions of topological surface codes
• Perfect reconstruction of sparse signals using nonconvexity control and one-step RSB message passing
• On the Effect of Regularization on Nonparametric Mean-Variance Regression
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Empirical universality and non-universality of local dynamics in the Sherrington-Kirkpatrick model
• Machine learning and the physical sciences
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
• Revisiting Nishimori multicriticality through the lens of information measures
• Bulk-boundary decomposition of neural networks
• Statistical Query Lower Bounds for Tensor PCA
• Plug and play methods for magnetic resonance imaging (long version)
• Thermodynamics of the Minimum Description Length on Community Detection
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust\n Estimation and Semirandom Adversaries
• Graphical model for tensor factorization by sparse sampling
• Belief propagation for finite networks using a symmetry-breaking source node
• A high-bias, low-variance introduction to Machine Learning for physicists
• Structure of solutions to continuous constraint satisfaction problems through the statistics of wedged and inscribed spheres
• Phase transitions in spiked matrix estimation: information-theoretic analysis
• Precise Dynamics of Diagonal Linear Networks: A Unifying Analysis by Dynamical Mean-Field Theory
• Spin glasses and the Parisi formula
• On the accuracy of message-passing approaches to percolation in complex networks
• On Quantification of Borrowing of Information in Hierarchical Bayesian Models
• Macroscopic Analysis of Vector Approximate Message Passing in a Model Mismatch Setting
• The rank of random matrices over finite fields
• Nonlocal Monte Carlo via Reinforcement Learning
• Statistical physics of linear and bilinear inference problems
• A Spin Glass Characterization of Neural Networks
• Intuition emerges in Maximum Caliber models at criticality
• Topological Phase Transitions in a Constrained Two-Qubit Quantum Control Landscape
• Diverging conditional correlation lengths in the approach to high temperature
• Post-mortem on a deep learning contest: a Simpson's paradox and the complementary roles of scale metrics versus shape metrics
• Illuminating the Three Dogmas of Reinforcement Learning under Evolutionary Light
• Shannon entropy of the measurement record at measurement-dominated criticality and RG flow: A c-theorem for effective central charge and a g-theorem for effective boundary entropy
• Hessian Eigenspectra of More Realistic Nonlinear Models
• Temperature chaos as a logical consequence of the reentrant transition in spin glasses
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties
• An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
• Overlap Gap and Computational Thresholds in the Square Wave Perceptron
• Bayes optimal learning of attention-indexed models
• A Theoretical Connection Between Statistical Physics and Reinforcement Learning
• Bayesian Inference with Structured Signal: Static Replica Symmetry Breaking on the Nishimori Line in the Planted Spin Glass
• Covariance Density Neural Networks
• Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don't
• Guerra interpolation for inverse freezing
• Minimax entropy: The statistical physics of optimal models
• Near optimal sparsity-constrained group testing: improved bounds and algorithms
• Phase diagram of matrix compressed sensing
• Information-theoretic thresholds from the cavity method
• Comparing Dynamics: Deep Neural Networks versus Glassy Systems
• A Model Zoo on Phase Transitions in Neural Networks
• Improved belief propagation algorithm finds many Bethe states in the random-field Ising model on random graphs
• Frozen 1-RSB structure of the symmetric Ising perceptron
• Summary statistics of learning link changing neural representations to behavior
• Annealed averages in spin and matrix models
• Spectral Entropies as Information-Theoretic Tools for Complex Network Comparison
• Towards data analysis with diagrammatics
• Solving statistical mechanics on sparse graphs with feedback-set variational autoregressive networks
• High-dimensional inference: a statistical mechanics perspective
• Large Deviations of Semi-supervised Learning in the Stochastic Block Model
• Marvels and Pitfalls of the Langevin Algorithm in Noisy High-Dimensional Inference
• Learning transitions in classical Ising models and deformed toric codes
• Emergence of Computational Structure in a Neural Network Physics Simulator
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• A computational transition for detecting multivariate shuffled linear regression by low-degree polynomials
• Statistical Physics for Medical Diagnostics: Learning, Inference, and Optimization Algorithms. [europepmc]
• Boltzmann Machines as Generalized Hopfield Networks: A Review of Recent Results and Outlooks. [europepmc]
• Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setup. [europepmc]
• Inverse problems for structured datasets using parallel TAP equations and restricted Boltzmann machines. [europepmc]
• Bayesian inference of ion velocity distribution function from laser-induced fluorescence spectra. [europepmc]
• Inferring a Property of a Large System from a Small Number of Samples. [europepmc]
• Thermodynamics of the Ising Model Encoded in Restricted Boltzmann Machines. [europepmc]
• Bayesian reconstruction of memories stored in neural networks from their connectivity. [europepmc]
• Fundamental limits to learning closed-form mathematical models from data. [europepmc]
• An analytical theory of curriculum learning in teacher-student networks. [europepmc]
• Neural Activity in Quarks Language: Lattice Field Theory for a Network of Real Neurons. [europepmc]
• Summary statistics of learning link changing neural representations to behavior. [europepmc]

Related

• Statistical physics of linear and bilinear inference problems
• The mighty force: statistical inference and high-dimensional statistics
• Statistical physics of complex systems: glasses, spin glasses, continuous constraint satisfaction problems, high-dimensional inference and neural networks
• Hidden Clique Inference in Random Ising Model II: the planted Sherrington-Kirkpatrick model
• Statistical Problems with Planted Structures: Information-Theoretical and Computational Limits