Algorithmic thresholds for tensor PCA

DOI10.1214/19-AOP1415MaRDI QIDQ782415zbMATH OpenOpenAlexFDO

Authors Gerard Ben Arous, Reza Gheissari, Aukosh Jagannath

Publication date 27 July 2020

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.00921, https://projecteuclid.org/euclid.aop/1595232103

zbMATH Keywords

free energy wellsgradient descentLangevin dynamicsplanted signal recoveryspiked tensor modelspin glassestensor estimationtensor principal component analysis (PCA)

Mathematics Subject Classification ID

Applications of functional analysis in probability theory and statistics (46N30) Applications of stochastic analysis (to PDEs, etc.) (60H30) Point estimation (62F10) Parametric inference under constraints (62F30) Factor analysis and principal components; correspondence analysis (62H25) Markov processes: estimation; hidden Markov models (62M05) Monte Carlo methods (65C05) Dynamics of disordered systems (random Ising systems, etc.) in time-dependent statistical mechanics (82C44) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)

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.

Recommendations

• Statistical thresholds for tensor PCA
• The landscape of the spiked tensor model
• Statistical limits of spiked tensor models
• Phase transition in random tensors with multiple independent spikes
• Phase transition in the spiked random tensor with Rademacher prior

Cites work

• p> 2 spin glasses with first-order ferromagnetic transitions
• A nearly tight sum-of-squares lower bound for the planted clique problem
• Bounding flows for spherical spin glass dynamics
• Complexity of random smooth functions on the high-dimensional sphere
• Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• High-dimensional probability. An introduction with applications in data science
• scientific article; zbMATH DE number 5788282 (Why is no real title available?)
• scientific article; zbMATH DE number 3951715 (Why is no real title available?)
• Large deviations for the largest eigenvalue of rank one deformations of Gaussian ensembles
• Large deviations of the extreme eigenvalues of random deformations of matrices
• Most tensor problems are NP-hard
• On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank One Perturbations of Gaussian Tensors
• On the spectral gap of spherical spin glass dynamics
• Optimal detection of sparse principal components in high dimension
• Optimality and sub-optimality of PCA. I: Spiked random matrix models
• Phase transition in the spiked random tensor with Rademacher prior
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• Positive definite functions on spheres
• Proof of the achievability conjectures for the general stochastic block model
• Random matrices and complexity of spin glasses
• Spectral gap estimates in mean field spin glasses
• Statistical limits of spiked tensor models
• The complexity of spherical p-spin models: a second moment approach
• The landscape of the spiked tensor model
• The largest eigenvalue of small rank perturbations of Hermitian random matrices
• The largest eigenvalues of finite rank deformation of large Wigner matrices: Convergence and nonuniversality of the fluctuations

Cited in

(40)

• Diffusions interacting through a random matrix: universality via stochastic Taylor expansion
• The overlap gap property in principal submatrix recovery
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Optimal low-degree hardness of maximum independent set
• Computational barriers to estimation from low-degree polynomials
• Statistical limits of spiked tensor models
• Local minima in disordered mean-field ferromagnets
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models
• Phase transition in random tensors with multiple independent spikes
• Bounding flows for spherical spin glass dynamics
• Phase transition in the spiked random tensor with Rademacher prior
• Statistical thresholds for tensor PCA
• Online stochastic gradient descent on non-convex losses from high-dimensional inference
• How to iron out rough landscapes and get optimal performances: averaged gradient descent and its application to tensor PCA
• Dynamics of mean field spin glasses on short and long timescales
• The landscape of the spiked tensor model
• Free Energy Wells and Overlap Gap Property in Sparse PCA
• Algorithmic obstructions in the random number partitioning problem
• Random geometric graph: some recent developments and perspectives
• Statistical-computational trade-offs in tensor PCA and related problems via communication complexity
• Long random matrices and tensor unfolding
• Shattering versus metastability in spin glasses
• High‐dimensional limit theorems for SGD: Effective dynamics and critical scaling
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics
• Average-case complexity of tensor decomposition for low-degree polynomials
• High-dimensional asymptotics of Langevin dynamics in spiked matrix models
• Phase diagram of stochastic gradient descent in high-dimensional two-layer neural networks
• The landscape of the planted clique problem: dense subgraphs and the overlap gap property
• The threshold energy of low temperature Langevin dynamics for pure spherical spin glasses
• The Kikuchi hierarchy and tensor PCA
• Finding planted cliques using gradient descent
• A random matrix approach to low-multilinear-rank tensor approximation
• Almost-linear planted cliques elude the Metropolis process
• High-dimensional non-convex landscapes and gradient descent dynamics
• Learning from higher-order statistics, efficiently: hypothesis tests, random features, and neural networks
• Computational lower bounds for multi-frequency group synchronization
• On the MCMC performance in Bernoulli group testing and the random max-set cover problem
• Functional renormalisation for signal detection: dimensional analysis and dimensional phase transition for nearly continuous spectra effective field theory
• Stochastic gradient descent in high dimensions for multi-spiked tensor PCA
• An optimized Franz-Parisi criterion and its equivalence with SQ lower bounds

This page was built for publication: Algorithmic thresholds for tensor PCA

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q782415)