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. 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.

arXiv comment10 pages, 3 figures

References in corpus (20)

• Message Passing Algorithms for Compressed Sensing
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Mean field theory of hard sphere glasses and jamming
• Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform so well over the BEC
• The structural glass transition and the entropy of the metastable states
• Spin-Glass Theory for Pedestrians
• Statistical physics of inference: Thresholds and algorithms
• Glass and Jamming Transitions: From Exact Results to Finite-Dimensional Descriptions
• Recipes for metastable states in Spin Glasses
• Statistical physics-based reconstruction in compressed sensing
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• A ferromagnet with a glass transition
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• Dynamical transition of glasses: from exact to approximate
• Finding One Community in a Sparse Graph
• Complexity in Mean-Field Spin-Glass Models: Ising $p$-spin

Cited by in corpus (12)

• Jamming in multilayer supervised learning models
• Mean-field inference methods for neural networks
• Marvels and Pitfalls of the Langevin Algorithm in Noisy High-dimensional Inference
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Finite size effects in the microscopic critical properties of jammed configurations: A comprehensive study of the effects of different types of disorder
• Good speciation and endogenous business cycles in a constraint satisfaction macroeconomic model
• Hard-Sphere Jamming through the Lens of Linear Optimization
• Thresholds of descending algorithms in inference problems
• Bayesian reconstruction of memories stored in neural networks from their connectivity
• Generalized Approximate Survey Propagation for High-Dimensional Estimation
• Efficient approximation of branching random walk Gibbs measures
• Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model