Metraipolis › archive › dc_145b405dfc62

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.38206
License (as archived)
CC0-1.0
Archived
2026-11-01T02:23:27.478Z
SHA-256 of the archived text
c7d941f3fee7333fd90fe4adb2b793e13c0c4c1eb69e9594d5088d3a838619da
Stable URL of this page
https://metraipolis.com/documento/dc_145b405dfc62

How to cite

Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part II: Langevin Dynamics — arXiv:2610.38206 — arXiv (en), https://arxiv.org/abs/2610.38206 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_145b405dfc62 (Metraipolis archive dc_145b405dfc62, sha256 c7d941f3fee7333fd90fe4adb2b793e13c0c4c1eb69e9594d5088d3a838619da)
BibTeX
@misc{dc145b405dfc62,
  title = {Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part II: Langevin Dynamics — arXiv:2610.38206},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.38206},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_145b405dfc62; sha256 c7d941f3fee7333fd90fe4adb2b793e13c0c4c1eb69e9594d5088d3a838619da},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.38206. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Data Structures and Algorithms (cs.DS); Probability (math.PR); Statistics Theory (math.ST).
Pagina del lavoro: https://arxiv.org/abs/2610.38206 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:12:44.109Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).