Glassy Nature of the Hard Phase in Inference Problems
An algorithmically hard phase is 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 a...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2019-01-01
|
| Series: | Physical Review X |
| Online Access: | http://doi.org/10.1103/PhysRevX.9.011020 |
| _version_ | 1830189894376357888 |
|---|---|
| author | Fabrizio Antenucci Silvio Franz Pierfrancesco Urbani Lenka Zdeborová |
| author_facet | Fabrizio Antenucci Silvio Franz Pierfrancesco Urbani Lenka Zdeborová |
| author_sort | Fabrizio Antenucci |
| collection | DOAJ |
| description | An algorithmically hard phase is 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. Counterintuitively, 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. |
| first_indexed | 2024-12-17T23:12:15Z |
| format | Article |
| id | doaj.art-31c6a61f0b4a45fa90a1ea8691e55b9d |
| institution | Directory Open Access Journal |
| issn | 2160-3308 |
| language | English |
| last_indexed | 2024-12-17T23:12:15Z |
| publishDate | 2019-01-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | Physical Review X |
| spelling | doaj.art-31c6a61f0b4a45fa90a1ea8691e55b9d2022-12-21T21:29:06ZengAmerican Physical SocietyPhysical Review X2160-33082019-01-019101102010.1103/PhysRevX.9.011020Glassy Nature of the Hard Phase in Inference ProblemsFabrizio AntenucciSilvio FranzPierfrancesco UrbaniLenka ZdeborováAn algorithmically hard phase is 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. Counterintuitively, 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.http://doi.org/10.1103/PhysRevX.9.011020 |
| spellingShingle | Fabrizio Antenucci Silvio Franz Pierfrancesco Urbani Lenka Zdeborová Glassy Nature of the Hard Phase in Inference Problems Physical Review X |
| title | Glassy Nature of the Hard Phase in Inference Problems |
| title_full | Glassy Nature of the Hard Phase in Inference Problems |
| title_fullStr | Glassy Nature of the Hard Phase in Inference Problems |
| title_full_unstemmed | Glassy Nature of the Hard Phase in Inference Problems |
| title_short | Glassy Nature of the Hard Phase in Inference Problems |
| title_sort | glassy nature of the hard phase in inference problems |
| url | http://doi.org/10.1103/PhysRevX.9.011020 |
| work_keys_str_mv | AT fabrizioantenucci glassynatureofthehardphaseininferenceproblems AT silviofranz glassynatureofthehardphaseininferenceproblems AT pierfrancescourbani glassynatureofthehardphaseininferenceproblems AT lenkazdeborova glassynatureofthehardphaseininferenceproblems |