Gradient-descent-based algorithms and their stochastic versions have widespread applications in machine learning and statistical inference. In this work, we carry out an analytic study of the performance of the algorithm most commonly considered in physics, 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 mixed matrix-tensor model. The typical behavior of this algorithm is described by a system of integrodifferential 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 suboptimal with respect to the one given by AMP. This phenomenon is due to the residual glassiness present in that region of parameters. We also present a simple heuristic expression of the transition line, which appears to be in agreement with the numerical results.

Marvels and Pitfalls of the Langevin Algorithm in Noisy High-Dimensional Inference / Sarao Mannelli, S.; Biroli, G.; Cammarota, C.; Krzakala, F.; Urbani, P.; Zdeborova, L.. - In: PHYSICAL REVIEW. X. - ISSN 2160-3308. - 10:1(2020). [10.1103/PhysRevX.10.011057]

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

Cammarota C.;
2020

Abstract

Gradient-descent-based algorithms and their stochastic versions have widespread applications in machine learning and statistical inference. In this work, we carry out an analytic study of the performance of the algorithm most commonly considered in physics, 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 mixed matrix-tensor model. The typical behavior of this algorithm is described by a system of integrodifferential 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 suboptimal with respect to the one given by AMP. This phenomenon is due to the residual glassiness present in that region of parameters. We also present a simple heuristic expression of the transition line, which appears to be in agreement with the numerical results.
2020
inference, algorithms, risk landscape
01 Pubblicazione su rivista::01a Articolo in rivista
Marvels and Pitfalls of the Langevin Algorithm in Noisy High-Dimensional Inference / Sarao Mannelli, S.; Biroli, G.; Cammarota, C.; Krzakala, F.; Urbani, P.; Zdeborova, L.. - In: PHYSICAL REVIEW. X. - ISSN 2160-3308. - 10:1(2020). [10.1103/PhysRevX.10.011057]
File allegati a questo prodotto
File Dimensione Formato  
Sarao Mannelli_Marvels and Pitfalls_2020.pdf

solo gestori archivio

Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 2.05 MB
Formato Adobe PDF
2.05 MB Adobe PDF   Contatta l'autore
Sarao Mannelli_Marvels and Pitfalls of the Langevin_2020.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Creative commons
Dimensione 2.44 MB
Formato Adobe PDF
2.44 MB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1472273
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 27
  • ???jsp.display-item.citation.isi??? 19
social impact