Langevin dynamics for high-dimensional optimization: the case of multi-spiked tensor PCA

We study nonconvex optimization in high dimensions through Langevin dynamics, focusing on the multi-spiked tensor PCA problem. In this tensor estimation model, the goal is to recover a finite number of hidden signal vectors, or spikes, from noisy Gaussian tensor observations using maximum likelihood estimation. We characterize the number of samples required for Langevin dynamics to efficiently recover the spikes and identify the separation conditions on the signal-to-noise ratios (SNRs) needed for exact recovery. In particular, we show that the sample complexity required to recover the spike associated with the largest SNR matches the well-known algorithmic threshold for the single-spike case, whereas the threshold degrades when recovering all spikes. A key ingredient is a precise low-dimensional description of the Langevin trajectory through its correlations with the spikes, which captures both the high-dimensional dynamics and the interactions among competing signal directions.