Skip to Main content Skip to Navigation
Journal articles

On the glassy nature of the hard phase in inference problems

Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [40 references]  Display  Hide  Download

https://hal-cea.archives-ouvertes.fr/cea-01930645
Contributor : Emmanuelle de Laborderie <>
Submitted on : Thursday, November 22, 2018 - 10:55:00 AM
Last modification on : Wednesday, September 16, 2020 - 4:05:54 PM
Long-term archiving on: : Saturday, February 23, 2019 - 1:27:46 PM

File

glassynature.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : cea-01930645, version 1
  • ARXIV : 1805.05857

Citation

Fabrizio Antenucci, Silvio Franz, Pierfrancesco Urbani, Lenka Zdeborová. On the glassy nature of the hard phase in inference problems. Physical Review X, American Physical Society, 2019, 9, pp.011020. ⟨cea-01930645⟩

Share

Metrics

Record views

117

Files downloads

188