{"id":"arxiv/2610.38206","url":"https://arxiv.org/abs/2610.38206","tags":["cs.LG","cs.DS","math.PR","math.ST"],"score":0,"title":"Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part II: Langevin Dynamics","domain":"cs.LG","source":"arxiv","authors":["Aniket Das","Tselil Schramm"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-28","reactions":{}}