# Statistical physics of inference: Thresholds and algorithms

arXiv: https://arxiv.org/abs/1511.02476 · HTML: https://mlsanity.com/paper/1511.02476/

## Key facts

- Cited by 128 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2015.

## Built on by (most cited first, 30 of 128)

- [Beyond neural scaling laws: beating power law scaling via data pruning](https://mlsanity.com/paper/2206.14486/) (2022)
- [Learning curves of generic features maps for realistic datasets with a teacher-student model](https://mlsanity.com/paper/2102.08127/) (2021)
- [Continual Learning in the Teacher-Student Setup: Impact of Task Similarity](https://mlsanity.com/paper/2107.04384/) (2021)
- [How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Model](https://mlsanity.com/paper/2307.02129/) (2023)
- [Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions](https://mlsanity.com/paper/2106.03791/) (2021)
- [Instance-Optimal Compressed Sensing via Posterior Sampling](https://mlsanity.com/paper/2106.11438/) (2021)
- [Bayes-optimal Learning of Deep Random Networks of Extensive-width](https://mlsanity.com/paper/2302.00375/) (2023)
- [Benign, Tempered, or Catastrophic: A Taxonomy of Overfitting](https://mlsanity.com/paper/2207.06569/) (2022)
- [Graph-based Approximate Message Passing Iterations](https://mlsanity.com/paper/2109.11905/) (2021)
- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [A phase transition between positional and semantic learning in a solvable model of dot-product attention](https://mlsanity.com/paper/2402.03902/) (2024)
- [There Will Be a Scientific Theory of Deep Learning](https://mlsanity.com/paper/2604.21691/) (2026)
- [An Analytical Theory of Curriculum Learning in Teacher-Student Networks](https://mlsanity.com/paper/2106.08068/) (2021)
- [Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective](https://mlsanity.com/paper/2308.14085/) (2023)
- [Bayes-optimal learning of an extensive-width neural network from quadratically many samples](https://mlsanity.com/paper/2408.03733/) (2024)
- [The emergence of a concept in shallow neural networks](https://mlsanity.com/paper/2109.00454/) (2021)
- [Post-mortem on a deep learning contest: a Simpson's paradox and the complementary roles of scale metrics versus shape metrics](https://mlsanity.com/paper/2106.00734/) (2021)
- [Fluctuations, Bias, Variance & Ensemble of Learners: Exact Asymptotics for Convex Losses in High-Dimension](https://mlsanity.com/paper/2201.13383/) (2022)
- [High-dimensional Asymptotics of Denoising Autoencoders](https://mlsanity.com/paper/2305.11041/) (2023)
- [Fundamental computational limits of weak learnability in high-dimensional multi-index models](https://mlsanity.com/paper/2405.15480/) (2024)
- [Disentangling and Mitigating the Impact of Task Similarity for Continual Learning](https://mlsanity.com/paper/2405.20236/) (2024)
- [Theoretical characterization of uncertainty in high-dimensional linear classification](https://mlsanity.com/paper/2202.03295/) (2022)
- [Learning curves for the multi-class teacher-student perceptron](https://mlsanity.com/paper/2203.12094/) (2022)
- [Quantum field-theoretic machine learning](https://mlsanity.com/paper/2102.09449/) (2021)
- [On double-descent in uncertainty quantification in overparametrized models](https://mlsanity.com/paper/2210.12760/) (2022)
- [A solvable model of learning generative diffusion: theory and insights](https://mlsanity.com/paper/2501.03937/) (2025)
- [Optimal Task Order for Continual Learning of Multiple Tasks](https://mlsanity.com/paper/2502.03350/) (2025)
- [Asymptotics of Non-Convex Generalized Linear Models in High-Dimensions: A proof of the replica formula](https://mlsanity.com/paper/2502.20003/) (2025)
- [Empirical Risk Minimization with Relative Entropy Regularization](https://mlsanity.com/paper/2211.06617/) (2022)
- [Forward Learning with Top-Down Feedback: Empirical and Analytical Characterization](https://mlsanity.com/paper/2302.05440/) (2023)

## Abstract (arXiv)

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.