mlsanityData to 7 Oct 2026

Permutation recovery of spikes in noisy high-dimensional tensor estimation

arXiv 2412.14650 ↗First posted 19 Dec 2024math.PR cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the dynamics of gradient flow in high dimensions for the multi-spiked tensor problem, where the goal is to estimate r unknown signal vectors (spikes) from noisy Gaussian tensor observations. Specifically, we analyze the maximum likelihood estimation procedure, which involves optimizing a highly nonconvex random function. We determine the sample complexity required for gradient flow to efficiently recover all spikes, without imposing any assumptions on the separation of the signal-to-noise ratios (SNRs). More precisely, our results provide the sample complexity required to guarantee recovery of the spikes up to a permutation. Our work builds on our companion paper [Ben Arous, Gerbelot, Piccolo 2024], which studies Langevin dynamics and determines the sample complexity and separation conditions for the SNRs necessary for ensuring exact recovery of the spikes (where the recovered permutation matches the identity). During the recovery process, the correlations between the estimators and the hidden vectors increase in a sequential manner. The order in which these correlations become significant depends on their initial values and the corresponding SNRs, which ultimately determines the permutation of the recovered spikes.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 17 of its 39 references that are in the map. First posted on arXiv 19 Dec 2024.

Builds on

17 of 39 references.

References · 17

  1. 2020Prevalence of Neural Collapse during the terminal phase of deep learning trainingcited by 713
  2. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  3. 2014A statistical model for tensor PCAcited by 72
  4. 2022High-dimensional limit theorems for SGD: Effective dynamics and critical scalingcited by 69
  5. 2015Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectorscited by 38
  6. 2015Tensor principal component analysis via sum-of-squares proofscited by 35
  7. 2017The landscape of the spiked tensor modelcited by 34
  8. 2019Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrievalcited by 34
  9. 2018Optimality and Sub-optimality of PCA I: Spiked Random Matrix Modelscited by 33
  10. 2016Statistical limits of spiked tensor modelscited by 27
  11. 2018Complex energy landscapes in spiked-tensor and simple glassy models: ruggedness, arrangements of local minima and phase transitionscited by 23
  12. 2017Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squarescited by 17
5 more
  1. 2019The Kikuchi Hierarchy and Tensor PCAcited by 15
  2. 2021Long Random Matrices and Tensor Unfoldingcited by 10
  3. 2024Stochastic gradient descent in high dimensions for multi-spiked tensor PCAcited by 6
  4. 2024Sharp Analysis of Power Iteration for Tensor PCAcited by 2
  5. 2024Langevin dynamics for high-dimensional optimization: the case of multi-spiked tensor PCAcited by 2

Built on by

Not cited yet.