Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part II: Langevin Dynamics

Aniket Das, Tselil SchrammarXiv 2026 · arXiv

TL;DR

This paper proves that local Markov chains—specifically spherical Langevin dynamics—can solve the Tensor PCA problem all the way down to the "algorithmic threshold," matching the performance of much more complex global algorithms like Sum-of-Squares. By combining high-temperature annealing with ergodic averaging, the authors show that these simple, local processes can escape uninformative "cold starts" and achieve strong signal recovery in polynomial time.

What Problem Does This Paper Address?

Tensor Principal Component Analysis (Tensor PCA) is a fundamental problem in high-dimensional statistics and average-case complexity. The goal is to recover a hidden signal vector $x^*$ from a noisy observation of its $k$-th tensor power.

The problem is famous for its statistical-computational gap. While it is information-theoretically possible to recover the signal at a low signal-to-noise ratio (SNR), efficient "global" algorithms (like spectral methods or the Sum-of-Squares hierarchy) only work when the SNR $\lambda$ is above a much higher threshold: $\lambda_{ALG} \approx N^{(k-2)/4}$.

Previously, "local" algorithms—those that move iteratively based on local gradients, like Markov chains or power iteration—were believed to be strictly inferior, requiring an even higher SNR ($\lambda \approx N^{(k-2)/2}$) to succeed from a random starting point. This paper challenges that belief, asking if local Markov chains can be as powerful as global methods.

Figure 1: Phase diagram for the recovery problem in tensor PCA in terms of λ.

Methods

The authors introduce a two-phase algorithm based on Spherical Langevin Dynamics, which is essentially a gradient descent process on a sphere with added Gaussian noise (diffusion).

  1. Phase 1: High-Temperature Ergodic Averaging. The algorithm starts at a very high "temperature" (high noise level) from a random point. Instead of looking for the signal directly, it computes the ergodic average (the average of all states visited during the trajectory).
  2. The "Aha!" Moment: At high temperatures, the dynamics are dominated by noise, but the signal exerts a tiny "linear response" bias. By averaging the trajectory over a long time, this tiny bias accumulates into a "warm start" vector that correlates with the hidden signal.
  3. Phase 2: Low-Temperature "Climbing." The algorithm takes the normalized average from Phase 1 as a starting point and runs Langevin dynamics at a much lower temperature. Because it now has a "warm start," it can successfully climb the "rugged landscape" of the tensor Hamiltonian to achieve strong recovery without getting trapped in local minima.

For cases where the tensor order $k$ is even (where symmetry makes the simple average zero), the authors use an augmented ergodic second moment (Algorithm 2), taking the top eigenvector of the covariance of the trajectory to find the signal direction.

Datasets

This is a theoretical paper in mathematical statistics; it does not use real-world datasets. Evaluations and proofs are conducted using the standard Spiked Tensor Model, where the observation is a planted signal tensor plus i.i.d. Gaussian noise.

Key Insights and Ideas

  • Local is as good as Global: The most significant insight is that the perceived weakness of local algorithms was not inherent to the algorithms themselves, but rather to how they were initialized and analyzed.
  • The Power of Averaging: Most local methods fail because they get stuck in the "equator" (states orthogonal to the signal). Ergodic averaging acts as a noise-reduction filter that extracts a signal-aligned direction from what looks like pure noise.
  • The Reverse Planting Trick: To prove the algorithm works, the authors use a novel "reverse planting" argument. They compare the dynamics of the true model to a "null" model (pure noise) and use Girsanov’s theorem (a tool from stochastic calculus) to show that the noise is unlikely to overpower the signal drift before the algorithm reaches a critical correlation level.
  • Universality: The approach is agnostic to the specific form of the Hamiltonian, suggesting that "averaging + annealing" might be a general recipe for making local Markov chains reach algorithmic thresholds in other planted problems.

Key Results

  • Threshold Matching: The proposed algorithms achieve strong recovery (correlation $\approx 1$) at the same SNR threshold ($\lambda \gtrsim N^{(k-2)/4}$) as global algorithms.
  • Polynomial Time: The recovery happens in polynomial time, specifically requiring an averaging time $T_{av} \approx N^{2k-2}$.
  • High Probability: The results hold with very high probability ($1 - \exp(-N^{1/2-o(1)})$).
  • Parity Agnostic: While simple averaging works for odd $k$, the second-moment approach (Algorithm 2) works for all $k \ge 3$, regardless of parity.

Limitations and Future Work

  • Averaging Time: While the algorithm is polynomial-time, the exponent ($2k-2$) is quite high. Future work could investigate if more efficient local methods (like those using momentum or adaptive step sizes) can reduce this.
  • Beyond the Sphere: The current work is specifically for spherical constraints. Extending these results to other geometries (like discrete hypercubes or more complex manifolds) is a natural next step.
  • General Planted Problems: The authors suggest their framework might apply to other "rugged landscape" problems in statistical physics and machine learning, which remains to be proven for specific cases.

Summary updated

Abstract

We consider the tensor principal components analysis (tensor PCA) problem on the sphere, in which we are asked to recover an unknown vector in $\mathcal{S}_N=\{x\in\mathbb{R}^N:\lVert x\rVert^2=N\}$ from a noisy observation of its $k$-th tensor power, for a fixed $k\ge3$. Tensor PCA exhibits a well-studied information-computation gap: global algorithms such as spectral methods and sum-of-squares work above an algorithmic threshold, below which we know matching lower bounds (against these and some other restricted models of computation). In contrast, local algorithms such as Markov chains were only known to succeed from a random initialization at a polynomially larger signal-to-noise ratio, and were believed to be inferior to global algorithms for tensor PCA. Continuing the program initiated in Part I [arXiv:2610.16705], we show that spherical Langevin dynamics, when supplemented with annealing and ergodic averaging, achieves polynomial-time strong recovery above the algorithmic threshold from a uniformly random initialization. Together with Part I, our results demonstrate that local Markov chains can succeed all the way down to the algorithmic threshold from an uninformative cold start.
BibTeX
@misc{das2026averaged,
  author = {Aniket Das and Tselil Schramm},
  title = {{Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part II: Langevin Dynamics}},
  year = {2026},
  eprint = {2610.38206},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.38206},
}

Loading related content...

Figure