Skip to Main content Skip to Navigation
Journal articles

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

Cited literature [69 references]  Display  Hide  Download

https://hal-cea.archives-ouvertes.fr/cea-02009687
Contributor : Emmanuelle de Laborderie Connect in order to contact the contributor
Submitted on : Wednesday, February 6, 2019 - 3:04:44 PM
Last modification on : Wednesday, October 27, 2021 - 5:16:49 AM
Long-term archiving on: : Tuesday, May 7, 2019 - 1:53:55 PM

File

marvels.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : cea-02009687, version 1
  • ARXIV : 1812.09066
`

Citation

Stefano Mannelli, Giulio Biroli, Chiara Cammarota, Florent Krzakala, Pierfrancesco Urbani, et al.. Marvels and Pitfalls of the Langevin Algorithm in Noisy High-dimensional Inference. Physical Review X, American Physical Society, 2020, 10 (011057). ⟨cea-02009687⟩

Share

Metrics

Record views

181

Files downloads

244