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

arXiv: https://arxiv.org/abs/1812.09066 · HTML: https://mlsanity.com/paper/1812.09066/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Dec 2018.

## Built on by (most cited first, 24 of 24)

- [Self-Consistent Dynamical Field Theory of Kernel Evolution in Wide Neural Networks](https://mlsanity.com/paper/2205.09653/) (2022)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [High-dimensional limit theorems for SGD: Effective dynamics and critical scaling](https://mlsanity.com/paper/2206.04030/) (2022)
- [The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents](https://mlsanity.com/paper/2402.03220/) (2024)
- [Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective](https://mlsanity.com/paper/2308.14085/) (2023)
- [On the Cryptographic Hardness of Learning Single Periodic Neurons](https://mlsanity.com/paper/2106.10744/) (2021)
- [Sliding down the stairs: how correlated latent variables accelerate learning with neural networks](https://mlsanity.com/paper/2404.08602/) (2024)
- [Origami in N dimensions: How feed-forward networks manufacture linear separability](https://mlsanity.com/paper/2203.11355/) (2022)
- [Sudakov-Fernique post-AMP, and a new proof of the local convexity of the TAP free energy](https://mlsanity.com/paper/2208.09550/) (2022)
- [Computational Thresholds in Multi-Modal Learning via the Spiked Matrix-Tensor Model](https://mlsanity.com/paper/2506.02664/) (2025)
- [Analytical Study of Momentum-Based Acceleration Methods in Paradigmatic High-Dimensional Non-Convex Problems](https://mlsanity.com/paper/2102.11755/) (2021)
- [Rank-one matrix estimation: analytic time evolution of gradient descent dynamics](https://mlsanity.com/paper/2105.12257/) (2021)
- [Optimal learning rate schedules in high-dimensional non-convex optimization problems](https://mlsanity.com/paper/2202.04509/) (2022)
- [Optimal thresholds and algorithms for a model of multi-modal learning in high dimensions](https://mlsanity.com/paper/2407.03522/) (2024)
- [Stochastic Gradient Descent outperforms Gradient Descent in recovering a high-dimensional signal in a glassy energy landscape](https://mlsanity.com/paper/2309.04788/) (2023)
- [Asymptotic Dynamics of Alternating Minimization for Bilinear Regression](https://mlsanity.com/paper/2402.04751/) (2024)
- [Transfer Learning in Infinite Width Feature Learning Networks](https://mlsanity.com/paper/2507.04448/) (2025)
- [High-dimensional Asymptotics of Langevin Dynamics in Spiked Matrix Models](https://mlsanity.com/paper/2204.04476/) (2022)
- [Precise Dynamics of Diagonal Linear Networks: A Unifying Analysis by Dynamical Mean-Field Theory](https://mlsanity.com/paper/2510.01930/) (2025)
- [Sharp description of local minima in the loss landscape of high-dimensional two-layer ReLU neural networks](https://mlsanity.com/paper/2604.09412/) (2026)
- [Topological Exploration of High-Dimensional Empirical Risk Landscapes: general approach, and applications to phase retrieval](https://mlsanity.com/paper/2602.17779/) (2026)
- [Selective Multiple Power Iteration: from Tensor PCA to gradient-based exploration of landscapes](https://mlsanity.com/paper/2112.12306/) (2021)
- [Large-N dynamics of the spiked tensor model with random initial conditions](https://mlsanity.com/paper/2208.12586/) (2022)
- [Theory of learning of high-dimensional controlled non-linear dynamical systems (I): models and methods](https://mlsanity.com/paper/2606.07247/) (2026)

## Abstract (arXiv)

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.