Statistical physics of inference: Thresholds and algorithms

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.

86 pages, 16 Figures. Review article based on HDR thesis of the first author and lecture notes of the second

References in corpus (58)

• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Theoretical perspective on the glass transition and amorphous materials
• Statistical Mechanics of Community Detection
• Stochastic blockmodels and community structure in networks
• Influence maximization in complex networks through optimal percolation
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase transition in the detection of modules in sparse networks
• A Bayesian Approach to Network Modularity
• Percolation on sparse networks
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• Reference-less measurement of the transmission matrix of a highly scattering material using a DMD and phase retrieval techniques
• Community Detection as an Inference Problem
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Sparse Principal Components Analysis
• A Landscape Analysis of Constraint Satisfaction Problems
• Adaptive Damping and Mean Removal for the Generalized Approximate Message Passing Algorithm
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Hopping and the Stokes-Einstein relation breakdown in simple glass formers
• Approximate message-passing decoder and capacity-achieving sparse superposition codes
• Predicting percolation thresholds in networks
• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• Analysis of CDMA systems that are characterized by eigenvalue spectrum
• Cavity approach to the spectral density of non-Hermitian sparse matrices
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• A statistical model for tensor PCA
• Community Detection in the Labelled Stochastic Block Model
• A Theory of Solving TAP Equations for Ising Models with General Invariant Random Matrices
• Tight lower bound for percolation threshold on a quasi-regular graph
• Numerical detection of the Gardner transition in a mean-field glass former
• Phase transitions in semisupervised clustering of sparse networks
• The cavity method at zero temperature
• Community detection in networks with unequal groups
• Replica Analysis and Approximate Message Passing Decoder for Superposition Codes
• Equilibrium ultrastable glasses produced by random pinning
• Assessing node risk and vulnerability in epidemics on networks
• Spectral Clustering of Graphs with the Bethe Hessian
• Glassy dynamics as a melting process (On melting dynamics and the glass transition, Part II)
• Computational Lower Bounds for Community Detection on Random Graphs
• Approximate Message Passing with Restricted Boltzmann Machine Priors
• Counting good truth assignments of random k-SAT formulae
• Near optimal configurations in mean field disordered systems
• Random matrices, non-backtracking walks, and orthogonal polynomials
• Glassy aspects of melting dynamics (On melting dynamics and the glass transition, Part I)
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models
• Spectral density of the non-backtracking operator
• Alternative solutions to diluted p-spin models and XORSAT problems
• Approximate Message Passing with Consistent Parameter Estimation and Applications to Sparse Learning
• Improvement of BP-Based CDMA Multiuser Detection by Spatial Coupling
• Following states in temperature in the spherical s+p-spin glass model
• Modern Coding Theory: The Statistical Mechanics and Computer Science Point of View
• Calorimetric glass transition in a mean field theory approach
• Inference for Generalized Linear Models via Alternating Directions and Bethe Free Energy Minimization
• Matrix Completion from Fewer Entries: Spectral Detectability and Rank Estimation
• The effect of quantum fluctuations on the coloring of random graphs

Cited by in corpus (203)

• Machine learning and the physical sciences
• A high-bias, low-variance introduction to Machine Learning for physicists
• Inverse statistical problems: from the inverse Ising problem to data science
• Plug and play methods for magnetic resonance imaging (long version)
• Solving Statistical Mechanics Using Variational Autoregressive Networks
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Extreme value statistics of correlated random variables: a pedagogical review
• Spectral entropies as information-theoretic tools for complex network comparison
• Quantum Machine Learning for Chemistry and Physics
• Entropy and mutual information in models of deep neural networks
• Approximate message-passing decoder and capacity-achieving sparse superposition codes
• Bayesian stochastic blockmodeling
• Modelling the influence of data structure on learning in neural networks: the hidden manifold model
• Mean-field message-passing equations in the Hopfield model and its generalizations
• Information-theoretic thresholds from the cavity method
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• Low rattling: A predictive principle for self-organization in active collectives
• Generalisation error in learning with random features and the hidden manifold model
• Mutual Information in Rank-One Matrix Estimation
• Coherent Ising machines -- Quantum optics and neural network perspectives
• Complex energy landscapes in spiked-tensor and simple glassy models: ruggedness, arrangements of local minima and phase transitions
• Algorithmic thresholds for tensor PCA
• Phase transitions in Restricted Boltzmann Machines with generic priors
• Phase transition in protocols minimizing work fluctuations
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Learning curves of generic features maps for realistic datasets with a teacher-student model
• Statistical and computational phase transitions in spiked tensor estimation
• Thermodynamics of Restricted Boltzmann Machines and related learning dynamics
• Out-of-equilibrium dynamical mean-field equations for the perceptron model
• Double Trouble in Double Descent : Bias and Variance(s) in the Lazy Regime
• Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don't
• Jamming in multilayer supervised learning models
• The Gaussian equivalence of generative models for learning with shallow neural networks
• Comparing Dynamics: Deep Neural Networks versus Glassy Systems
• Spectral Dynamics of Learning Restricted Boltzmann Machines
• Typology of phase transitions in Bayesian inference problems
• The Mutual Information in Random Linear Estimation Beyond i.i.d. Matrices
• Is stochastic thermodynamics the key to understanding the energy costs of computation?
• High-temperature Expansions and Message Passing Algorithms
• Quantum field-theoretic machine learning
• Disordered Systems Insights on Computational Hardness
• Mean-field inference methods for neural networks
• Charting the replica symmetric phase
• Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setup
• Marvels and Pitfalls of the Langevin Algorithm in Noisy High-dimensional Inference
• Asymptotic Errors for Teacher-Student Convex Generalized Linear Models (or : How to Prove Kabashima's Replica Formula)
• Information-theoretic and algorithmic thresholds for group testing
• Fundamental limits to learning closed-form mathematical models from data
• Linear stability analysis for large dynamical systems on directed random graphs
• Statistical mechanics of unsupervised feature learning in a restricted Boltzmann machine with binary synapses
• The committee machine: Computational to statistical gaps in learning a two-layers neural network
• Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems
• Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising
• Glassy nature of the hard phase in inference problems
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Dynamical Instantons and Activated Processes in Mean-Field Glass Models
• Rethinking generalization requires revisiting old ideas: statistical mechanics approaches and complex learning behavior
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
• Evaluating Ising Processing Units with Integer Programming
• Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
• Dynamical phase transitions in the nonreciprocal Ising model
• Bypassing sluggishness: SWAP algorithm and glassiness in high dimensions
• Quantifying Relevance in Learning and Inference
• On the correspondence between thermodynamics and inference
• Phase retrieval in high dimensions: Statistical and computational phase transitions
• Approximate Survey Propagation for Statistical Inference
• Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Model
• Optimal group testing
• Disorder-free spin glass transitions and jamming in exactly solvable mean-field models
• Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs
• Message-Passing Methods for Complex Contagions
• Asymptotic errors for convex penalized linear regression beyond Gaussian matrices
• Algorithmic detectability threshold of the stochastic block model
• Learning curves for the multi-class teacher-student perceptron
• Fundamental problems in statistical physics XIV: Lecture on Machine Learning
• Neural activity in quarks language: Lattice Field Theory for a network of real neurons
• Decoding from Pooled Data: Phase Transitions of Message Passing
• Solving Statistical Mechanics on Sparse Graphs with Feedback Set Variational Autoregressive Networks
• Micro, Meso, Macro: the effect of triangles on communities in networks
• Revisiting the Bethe-Hessian: Improved Community Detection in Sparse Heterogeneous Graphs
• Empirical Risk Minimization with Relative Entropy Regularization
• Deep learning via message passing algorithms based on belief propagation
• Aligning random graphs with a sub-tree similarity message-passing algorithm
• Statistical mechanics of low-rank tensor decomposition
• Spin systems on Bethe lattices
• Introduction to the dynamics of disordered systems: equilibrium and gradient descent
• From complex to simple : hierarchical free-energy landscape renormalized in deep neural networks
• The replica symmetric phase of random constraint satisfaction problems
• Phase transitions in the mini-batch size for sparse and dense two-layer neural networks
• Matrix denoising: Bayes-optimal estimators via low-degree polynomials
• Estimating rank-one matrices with mismatched prior and noise: universality and large deviations
• Macroscopic Analysis of Vector Approximate Message Passing in a Model Mismatch Setting
• Near-Optimal Coding for Many-user Multiple Access Channels
• Perturbative stability and error correction thresholds of quantum codes
• The autoregressive neural network architecture of the Boltzmann distribution of pairwise interacting spins systems
• Phase diagram of matrix compressed sensing
• Dense Hopfield Networks in the Teacher-Student Setting
• Toward a Theory of Phase Transitions in Quantum Control Landscapes
• Statistical Query Lower Bounds for Tensor PCA
• Creating equilibrium glassy states via random particle bonding
• Exploring the diluted ferromagnetic p-spin model with a Cavity Master Equation
• Anomalous distribution of magnetization in an Ising spin glass with correlated disorder
• An Analytical Theory of Curriculum Learning in Teacher-Student Networks
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
• Bayes-Optimal Estimation in Generalized Linear Models via Spatial Coupling
• Thresholds of descending algorithms in inference problems
• An Evolutionary Strategy based on Partial Imitation for Solving Optimization Problems
• Thermodynamic efficiency of learning a rule in neural networks
• An improved Belief Propagation algorithm finds many Bethe states in the random field Ising model on random graphs
• Spatially heterogeneous learning by a deep student machine
• Bayes-optimal inference for spreading processes on random networks
• Generalisation dynamics of online learning in over-parameterised neural networks
• Theoretical characterization of uncertainty in high-dimensional linear classification
• A random energy approach to deep learning
• Prediction Errors for Penalized Regressions based on Generalized Approximate Message Passing
• Sparse Autoregressive Neural Networks for Classical Spin Systems
• Streaming Bayesian inference: theoretical limits and mini-batch approximate message-passing
• The Copycat Perceptron: Smashing Barriers Through Collective Learning
• Hessian Eigenspectra of More Realistic Nonlinear Models
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
• Gibbs Sampling the Posterior of Neural Networks
• Statistical Mechanics of Inference in Epidemic Spreading
• Revisiting the replica trick: Competition between spin glass and conventional order
• Analyticity of the energy in an Ising spin glass with correlated disorder
• Annealed averages in spin and matrix models
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Exact results on high-dimensional linear regression via statistical physics
• Large deviations of extreme eigenvalues of generalized sample covariance matrices
• Thermodynamics of the Ising model encoded in restricted Boltzmann machines
• Inference and mutual information on random factor graphs
• Analytical solution to Heisenberg spin glass models on sparse random graphs and their de Almeida-Thouless line
• Self-planting: digging holes in rough landscapes
• Equivalence between algorithmic instability and transition to replica symmetry breaking in perceptron learning systems
• On the TAP equations via the cavity approach in the generic mixed $p$-spin models
• Inferring Hidden Symmetries of Exotic Magnets from Detecting Explicit Order Parameters
• Near optimal sparsity-constrained group testing: improved bounds and algorithms
• A residual-based message passing algorithm for constraint satisfaction problems
• Statistical Mechanics of Dynamical System Identification
• A Theoretical Connection Between Statistical Physics and Reinforcement Learning
• Posiform Planting: Generating QUBO Instances for Benchmarking
• Bayesian inference of ion velocity distribution function from laser-induced fluorescence spectra
• The solution space structure of planted constraint satisfaction problems with growing domains
• Mapping State Transition Susceptibility in Quantum Annealing
• Statistical physics of linear and bilinear inference problems
• Noisy group testing via spatial coupling
• Multilayer Modularity Belief Propagation To Assess Detectability Of Community Structure
• Critical properties of disordered XY model on sparse random graphs
• Neural-prior stochastic block model
• Bayesian reconstruction of memories stored in neural networks from their connectivity
• Circumventing spin glass traps by microcanonical spontaneous symmetry breaking
• Post-mortem on a deep learning contest: a Simpson's paradox and the complementary roles of scale metrics versus shape metrics
• The rank of random matrices over finite fields
• Temperature chaos as a logical consequence of the reentrant transition in spin glasses
• The planted directed polymer: inferring a random walk from noisy images
• Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation
• Evidence of Replica Symmetry Breaking under the Nishimori conditions in epidemic inference on graphs
• Intrinsic regularization effect in Bayesian nonlinear regression scaled by observed data
• Dense Limit of the Dawid-Skene Model for Crowdsourcing and Regions of Sub-optimality of Message Passing Algorithms
• Revisiting Nishimori multicriticality through the lens of information measures
• Classes of non-Gaussian random matrices: long-range eigenvalue correlations and non-ergodic extended eigenvectors
• Inferring a property of a large system from a small number of samples
• Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions
• Large Deviations of Semi-supervised Learning in the Stochastic Block Model
• The planted XY model: thermodynamics and inference
• Topological Phase Transitions in a Constrained Two-Qubit Quantum Control Landscape
• On the accuracy of message-passing approaches to percolation in complex networks
• Some observations on the ambivalent role of symmetries in Bayesian inference problems
• Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokens
• Top eigenpair statistics of diluted Wishart matrices
• Blind calibration for compressed sensing: State evolution and an online algorithm
• Replica Analysis for Ensemble Techniques in Variable Selection
• Appearance of Random Matrix Theory in Deep Learning
• Summary statistics of learning link changing neural representations to behavior
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• Optimizing information transmission in optogenetic Wnt signaling
• Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
• Thermodynamics of the Minimum Description Length on Community Detection
• A spectral approach to Hebbian-like neural networks
• High-dimensional inference: a statistical mechanics perspective
• Frozen $1$-RSB structure of the symmetric Ising perceptron
• The Limiting Poisson Law of Massive MIMO Detection with Box Relaxation
• Faster algorithms for the alignment of sparse correlated Erdös-Rényi random graphs
• Planted matching problems on random hypergraphs
• Integer Traffic Assignment Problem: Algorithms and Insights on Random Graphs
• Rényi complexity in mean-field disordered systems
• Renormalization group for spectral collapse in random matrices with power-law variance profiles
• Speech perception: a model of word recognition
• Statistical physics of deep learning: Optimal learning of a multi-layer perceptron near interpolation
• Inference in Spreading Processes with Neural-Network Priors
• Saddle Hierarchy in Dense Associative Memory
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties
• Dilution of Ferromagnets via a Random Graph-based Strategy
• Statistical mechanics of extensive-width Bayesian neural networks near interpolation
• Diagrammatics of free energies with fixed variance for high-dimensional data
• Optimal thresholds and algorithms for a model of multi-modal learning in high dimensions
• Landscape Complexity for the Empirical Risk of Generalized Linear Models: Discrimination between Structured Data
• Optimizing collective fieldtaxis of swarming agents through reinforcement learning
• Replica Analysis for Generalized Linear Regression with IID Row Prior
• Construction of simplicial complexes with prescribed degree-size sequences
• Matrix approach to generalized ensemble theory for nonequilibrium discrete systems
• Optimal generalisation and learning transition in extensive-width shallow neural networks near interpolation