Marvels and Pitfalls of the Langevin Algorithm in Noisy High-dimensional Inference

Abstract

Gradient-descent-based algorithms and their stochastic versions have widespread applications in machine learning and statistical inference. In this work we perform an analytic study of the performances of one of them, the Langevin algorithm, in the context of noisy high-dimensional inference. We employ the Langevin algorithm to sample the posterior probability measure for the spiked matrix-tensor model. The typical behaviour of this algorithm is described by a system of integro-differential equations that we call the Langevin state evolution, whose solution is compared with the one of the state evolution of approximate message passing (AMP). Our results show that, remarkably, the algorithmic threshold of the Langevin algorithm is sub-optimal with respect to the one given by AMP. We conjecture this phenomenon to be due to the residual glassiness present in that region of parameters. Finally we show how a landscape-annealing protocol, that uses the Langevin algorithm but violate the Bayes-optimality condition, can approach the performance of AMP.

11 pages and 5 figures + appendix

References in corpus (11)

• Spontaneous and induced dynamic fluctuations in glass-formers I: General results and dependence on ensemble and dynamics
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Spontaneous and induced dynamic correlations in glass-formers II: Model calculations and comparison to numerical simulations
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• Complex energy landscapes in spiked-tensor and simple glassy models: ruggedness, arrangements of local minima and phase transitions
• Out-of-equilibrium dynamical mean-field equations for the perceptron model
• Typology of phase transitions in Bayesian inference problems
• Glassy nature of the hard phase in inference problems
• On the TAP free energy in the mixed $p$-spin models
• Exactly solvable spin-glass models with ferromagnetic couplings: the spherical multi-$p$-spin model in a self-induced field

Cited by in corpus (16)

• Disordered Systems Insights on Computational Hardness
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Dynamical Instantons and Activated Processes in Mean-Field Glass Models
• Path Integral Approach Unveils the Role of Complex Energy Landscape for Activated Dynamics of Glassy Systems
• Dynamical Mean-Field Theory and Aging Dynamics
• Incorporating Heterogeneous Interactions for Ecological Biodiversity
• Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classification
• Sharp complexity asymptotics and topological trivialization for the (p, k) spiked tensor model
• The Copycat Perceptron: Smashing Barriers Through Collective Learning
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Numerical renormalization of glassy dynamics
• Some observations on the ambivalent role of symmetries in Bayesian inference problems
• Strong ergodicity breaking in dynamical mean-field equations for mixed p-spin glasses
• Planted matching problems on random hypergraphs
• Optimal thresholds and algorithms for a model of multi-modal learning in high dimensions
• Gradient descent dynamics and the jamming transition in infinite dimensions