期刊
PHYSICAL REVIEW X
卷 9, 期 1, 页码 -出版社
AMER PHYSICAL SOC
DOI: 10.1103/PhysRevX.9.011020
关键词
Complex Systems; Interdisciplinary Physics; Statistical Physics
资金
- Investissements d'Avenir LabEx PALM [ANR-10-LABX-0039-PALM]
- ERC under the European Unions Horizon 2020 Research and Innovation Program [714608-SMiLe]
- Simons Foundation [454941]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据