Langevin dynamics for high-dimensional optimization: the case of multi-spiked tensor PCA
This work addresses nonconvex optimization challenges in high-dimensional tensor estimation, providing theoretical insights for machine learning and statistics, though it is incremental as it extends known methods to a multi-spike setting.
The paper tackles the multi-spiked tensor PCA problem by analyzing Langevin dynamics for high-dimensional optimization, showing that the sample complexity for recovering the largest SNR spike matches the single-spike threshold, but degrades when recovering all r spikes, with specific separation conditions on SNRs for exact recovery.
We study nonconvex optimization in high dimensions through Langevin dynamics, focusing on the multi-spiked tensor PCA problem. This tensor estimation problem involves recovering $r$ hidden signal vectors (spikes) from noisy Gaussian tensor observations using maximum likelihood estimation. We study the number of samples required for Langevin dynamics to efficiently recover the spikes and determine the necessary separation condition on the signal-to-noise ratios (SNRs) for exact recovery, distinguishing the cases $p \ge 3$ and $p=2$, where $p$ denotes the order of the tensor. In particular, we show that the sample complexity required for recovering the spike associated with the largest SNR matches the well-known algorithmic threshold for the single-spike case, while this threshold degrades when recovering all $r$ spikes. As a key step, we provide a detailed characterization of the trajectory and interactions of low-dimensional projections that capture the high-dimensional dynamics.