Local search can match global methods on a noisy signal task
A proof showed that random search with cooling and averaging could recover a hidden vector above the same signal threshold as established global methods.
Edited by Boris Djordjevic · Paperfoot
The researchers proved that spherical Langevin dynamics, a random local search constrained to a sphere, achieved strong recovery in tensor principal components analysis when combined with annealing, or cooling, and time averaging. The task was to recover a hidden vector—a list of numbers—from noisy products formed from a fixed number of copies of that vector, at least three.
The method began at a uniformly random point, with no information about the hidden vector. Above the known signal-to-noise threshold for global methods, its estimates became increasingly accurate as the problem grew. Its running time was polynomial, meaning it grew no faster than a fixed power of the problem size. Earlier guarantees for local methods required a polynomially higher signal-to-noise ratio.
Why it matters
The proof showed that local search need not require a stronger signal than global methods for this mathematical recovery problem, even from an uninformed starting point.
Caveats
The guarantee concerns a mathematical model; lower bounds at the threshold cover restricted kinds of algorithms, not all possible methods. The work is a preprint and has not been peer-reviewed.
In this paper
tensor principal components analysis on the sphere
- Methods
- spherical Langevin dynamics (this paper)averaged gradient descent (baseline)
What it shows
- Spherical Langevin dynamics with annealing and ergodic averaging achieves polynomial-time strong recovery above the algorithmic threshold from a uniformly random initialization for tensor PCA on the sphere.
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.
Abstract
- Local Markov chains can succeed down to the algorithmic threshold from an uninformative cold start for tensor PCA.
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.
Abstract
- Normalized average spherical gradient is a sufficiently good warm start for escaping the equator exactly when signal-to-noise ratio is at least the algorithmic threshold.
In particular, if \lambda\leqslant N^{\tfrac{k-1}{4}}, then {\lambda m(\widehat{u}_{H})^{k-2}\asymp_{k}(\lambda N^{-\tfrac{k-2}{4}})^{k-1}}, and hence \widehat{u}_{H} is a sufficiently good warm start for escaping the equator exactly when \lambda\gtrsim\lambda_{\mathrm{ALG}}.
2.2 Warm Start via the Average Spherical Gradient
- After correlation exceeds a constant multiple of critical correlation, spherical Langevin dynamics achieves strong recovery within O(1) additional time and retains it over polynomial time horizons.
Consequently, once the correlation m_{t} exceeds a large constant multiple of the critical correlation r_{N}\doteq\lambda^{-1/(k-1)}, the signal drift dominates both the entropic and disorder drifts, even in the worst case, until m_{t} approaches one.
2.4 Controlling the Disorder via Reverse Planting
- The top eigenvector computation on the ergodic second moment is agnostic to the parity of the tensor order k.
Thus, the same top eigenvector computation yields a sufficiently good warm start for either parity, and is agnostic to the parity of k.
2.5 Strong Recovery for Any Tensor Order
Quoted word for word from the full text on arXiv.
The paper
arXiv, Oct 28, 2026, Open access, CC BY, Preprint, not peer-reviewed
doi.org/10.48550/arxiv.2610.38206
arXiv:2610.38206v1 in cs.LG, also cs.DS, math.PR, math.ST, stat.TH
Comments: Companion paper to arXiv:2610.16705 (Part I). 71 pages, 1 figure
Cite as BibTeX
@misc{das2026averaged,
title = {Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part II: Langevin Dynamics},
author = {Das, Aniket and Schramm, Tselil},
year = {2026},
eprint = {2610.38206},
archivePrefix = {arXiv},
primaryClass = {cs.LG},
doi = {10.48550/arxiv.2610.38206},
url = {https://arxiv.org/abs/2610.38206}
}