# Glassy nature of the hard phase in inference problems

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 May 2018.

## Built on by (most cited first, 9 of 9)

- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective](https://mlsanity.com/paper/2308.14085/) (2023)
- [The price of ignorance: how much does it cost to forget noise structure in low-rank matrix estimation?](https://mlsanity.com/paper/2205.10009/) (2022)
- [Dense Hopfield Networks in the Teacher-Student Setting](https://mlsanity.com/paper/2401.04191/) (2024)
- [On the phase diagram of extensive-rank symmetric matrix denoising beyond rotational invariance](https://mlsanity.com/paper/2411.01974/) (2024)
- [Bayesian reconstruction of memories stored in neural networks from their connectivity](https://mlsanity.com/paper/2105.07416/) (2021)
- [Generalization performance of narrow one-hidden layer networks in the teacher-student setting](https://mlsanity.com/paper/2507.00629/) (2025)
- [Mode connectivity in the loss landscape of parameterized quantum circuits](https://mlsanity.com/paper/2111.05311/) (2021)
- [On the Effect of Regularization on Nonparametric Mean-Variance Regression](https://mlsanity.com/paper/2511.22004/) (2025)

## Abstract (arXiv)

An algorithmically hard phase was described in a range of inference problems: even if the signal can be reconstructed with a small error from an information theoretic point of view, known algorithms fail unless the noise-to-signal ratio is sufficiently small. This hard phase is typically understood as a metastable branch of the dynamical evolution of message passing algorithms. In this work we study the metastable branch for a prototypical inference problem, the low-rank matrix factorization, that presents a hard phase. We show that for noise-to-signal ratios that are below the information theoretic threshold, the posterior measure is composed of an exponential number of metastable glassy states and we compute their entropy, called the complexity. We show that this glassiness extends even slightly below the algorithmic threshold below which the well-known approximate message passing (AMP) algorithm is able to closely reconstruct the signal. Counter-intuitively, we find that the performance of the AMP algorithm is not improved by taking into account the glassy nature of the hard phase. This result provides further evidence that the hard phase in inference problems is algorithmically impenetrable for some deep computational reasons that remain to be uncovered.