Statistical physics of inference: Thresholds and algorithms
arXiv:1511.02476 · doi:10.1080/00018732.2016.1211393
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.
arXiv comment86 pages, 16 Figures. Review article based on HDR thesis of the first author and lecture notes of the second
References in corpus (124)
- Community structure in social and biological networks
- Modularity and community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Finding community structure in networks using the eigenvectors of matrices
- Cooperative Game Theory Approaches for Network Partitioning
- Message Passing Algorithms for Compressed Sensing
- Theoretical perspective on the glass transition and amorphous materials
- Statistical Mechanics of Community Detection
- Stochastic blockmodels and community structure in networks
- Measuring the Transmission Matrix in Optics : An Approach to the Study and Control of Light Propagation in Disordered Media
- Influence maximization in complex networks through optimal percolation
- Noise Dressing of Financial Correlation Matrices
- Analytical Solution of the Off-Equilibrium Dynamics of a Long Range Spin-Glass Model
- The Bethe lattice spin glass revisited
- The dynamics of message passing on dense graphs, with applications to compressed sensing
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral redemption: clustering sparse networks
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform so well over the BEC
- Phase transition in the detection of modules in sparse networks
- The Thermodynamic Limit in Mean Field Spin Glass Models
- Localization and centrality in networks
- Percolation on sparse networks
- A Bayesian Approach to Network Modularity
- Phase Transitions in the Coloring of Random Graphs
- Bilinear Generalized Approximate Message Passing
- 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
- Compressive Imaging using Approximate Message Passing and a Markov-Tree Prior
- Phase diagram of glassy systems in an external field
- Ising models on locally tree-like graphs
- Universality in polytope phase transitions and message passing algorithms
- Community Detection as an Inference Problem
- Ideal Glass Transitions by Random Pinning
- Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
- Coloring random graphs
- Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
- The Entropy of the K-Satisfiability Problem
- Sparse Principal Components Analysis
- A Landscape Analysis of Constraint Satisfaction Problems
- Adaptive Damping and Mean Removal for the Generalized Approximate Message Passing Algorithm
- Learning by message-passing in networks of discrete synapses
- A typical reconstruction limit of compressed sensing based on Lp-norm minimization
- Hiding Quiet Solutions in Random Constraint Satisfaction Problems
- A ferromagnet with a glass transition
- Simplest random K-satisfiability problem
- Hopping and the Stokes-Einstein relation breakdown in simple glass formers
- Computational barriers in minimax submatrix detection
- Statistical mechanics of image restoration and error-correcting codes
- The Nishimori line and Bayesian Statistics
- Non-backtracking random walks mix faster
- Approximate message-passing decoder and capacity-achieving sparse superposition codes
- Predicting percolation thresholds in networks
- Phase transitions and sample complexity in Bayes-optimal matrix factorization
- Mean-Field Equations for Spin Models with Orthogonal Interaction Matrices
- Model Selection for Degree-corrected Block Models
- Hiding solutions in random satisfiability problems: A statistical mechanics approach
- On the dynamics of the glass transition on Bethe lattices
- Percolation on dense graph sequences
- MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
- Temperature evolution and bifurcations of metastable states in mean-field spin glasses, with connections with structural glasses
- Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
- Analysis of CDMA systems that are characterized by eigenvalue spectrum
- Tractable approximations for probabilistic models: The adaptive TAP mean field approach
- Dynamical transition of glasses: from exact to approximate
- 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
- Out of equilibrium dynamics in spin-glasses and other glassy systems
- 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
- Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
- Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes
- 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
- Quiet Planting in the Locked Constraint Satisfaction Problems
- Equilibrium ultrastable glasses produced by random pinning
- Phase Diagram and Approximate Message Passing for Blind Calibration and Dictionary Learning
- Performance of simulated annealing in p-spin glasses
- Assessing node risk and vulnerability in epidemics on networks
- The hard-core model on random graphs revisited
- Spectral Clustering of Graphs with the Bethe Hessian
- Propagating beliefs in spin glass models
- Conjecture on the maximum cut and bisection width in random regular graphs
- Spin glass models with ferromagnetically biased couplings on the Bethe lattice: analytic solutions and numerical simulations
- Glassy dynamics as a melting process (On melting dynamics and the glass transition, Part II)
- Computational Lower Bounds for Community Detection on Random Graphs
- Perceptron capacity revisited: classification ability for correlated patterns
- Approximate Message Passing with Restricted Boltzmann Machine Priors
- A Spectral Approach to Analyzing Belief Propagation for 3-Coloring
- Counting good truth assignments of random k-SAT formulae
- Glassy aspects of melting dynamics (On melting dynamics and the glass transition, Part I)
- Near optimal configurations in mean field disordered systems
- Random matrices, non-backtracking walks, and orthogonal polynomials
- Belief Propagation Reconstruction for Discrete Tomography
- Comparative Study for Inference of Hidden Classes in Stochastic Block Models
- Binary Linear Classification and Feature Selection via Generalized Approximate Message Passing
- Dynamical critical exponents for the mean-field Potts glass
- Statistical Mechanics of Dictionary Learning
- Bayesian signal reconstruction for 1-bit compressed sensing
- Quasi-equilibrium in glassy dynamics: an algebraic view
- Estimation with Random Linear Mixing, Belief Propagation and Compressed Sensing
- Spectral density of the non-backtracking operator
- Alternative solutions to diluted p-spin models and XORSAT problems
- Compressed Sensing under Matrix Uncertainty: Optimum Thresholds and Robust Approximate Message Passing
- 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
- Calorimetric glass transition in a mean field theory approach
- Modern Coding Theory: The Statistical Mechanics and Computer Science Point of View
- Dynamics and termination cost of spatially coupled mean-field models
- Inference for Generalized Linear Models via Alternating Directions and Bethe Free Energy Minimization
- Matrix Completion from Fewer Entries: Spectral Detectability and Rank Estimation
- Properties of spatial coupling in compressed sensing
- Multiple Access Demodulation in the Lifted Signal Graph with Spatial Coupling
- Statistical Mechanical Analysis of Compressed Sensing Utilizing Correlated Compression Matrix
- The effect of quantum fluctuations on the coloring of random graphs
- Sample Complexity of Bayesian Optimal Dictionary Learning
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 -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 -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