Algorithmic thresholds for tensor PCA

Abstract

We study the algorithmic thresholds for principal component analysis of Gaussian $k$-tensors with a planted rank-one spike, via Langevin dynamics and gradient descent. In order to efficiently recover the spike from natural initializations, the signal to noise ratio must diverge in the dimension. Our proof shows that the mechanism for the success/failure of recovery is the strength of the "curvature" of the spike on the maximum entropy region of the initial data. To demonstrate this, we study the dynamics on a generalized family of high-dimensional landscapes with planted signals, containing the spiked tensor models as specific instances. We identify thresholds of signal-to-noise ratios above which order 1 time recovery succeeds; in the case of the spiked tensor model these match the thresholds conjectured for algorithms such as Approximate Message Passing. Below these thresholds, where the curvature of the signal on the maximal entropy region is weak, we show that recovery from certain natural initializations takes at least stretched exponential time. Our approach combines global regularity estimates for spin glasses with point-wise estimates, to study the recovery problem by a perturbative approach.

arXiv comment34 pages. The manuscript has been updated to add a proof of what was Conjecture 1 in the first version

References in corpus (15)

• Statistical physics of inference: Thresholds and algorithms
• Optimal detection of sparse principal components in high dimension
• The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations
• Complexity of random smooth functions on the high-dimensional sphere
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
• A statistical model for tensor PCA
• Complex energy landscapes in spiked-tensor and simple glassy models: ruggedness, arrangements of local minima and phase transitions
• Tensor principal component analysis via sum-of-squares proofs
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Spectral gap estimates in mean field spin glasses
• On the Spectral Gap of Spherical Spin Glass Dynamics
• Bounding flows for spherical spin glass dynamics
• p>2 spin glasses with first order ferromagnetic transitions
• Phase transition in the spiked random tensor with Rademacher prior

Cited by in corpus (10)

• Computational Barriers to Estimation from Low-Degree Polynomials
• How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCA
• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
• Online stochastic gradient descent on non-convex losses from high-dimensional inference
• The Overlap Gap Property in Principal Submatrix Recovery
• Phase transition in random tensors with multiple independent spikes
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
• Landscape Complexity for the Empirical Risk of Generalized Linear Models
• Statistical Query Lower Bounds for Tensor PCA
• Who is Afraid of Big Bad Minima? Analysis of Gradient-Flow in a Spiked Matrix-Tensor Model