The landscape of the spiked tensor model

DOI10.1002/CPA.21861MaRDI QIDQ5204884zbMATH OpenOpenAlexFDO

Authors

Publication date 5 December 2019

Published in Communications on Pure and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.05424

zbMATH Keywords

machine learningglobal optimizationcritical pointsstatistical estimation

Mathematics Subject Classification ID

Characterization and structure theory for multivariate probability distributions; copulas (62H05) Estimation in multivariate analysis (62H12) Nonconvex programming, global optimization (90C26)

Abstract: We consider the problem of estimating a large rank-one tensor $$, $kge3$ in Gaussian noise. Earlier work characterized a critical signal-to-noise ratio $lambd{a}_{Bayes}=O(1)$ above which an ideal estimator achieves strictly positive correlation with the unknown vector of interest. Remarkably no polynomial-time algorithm is known that achieved this goal unless $lambdageC{n}^{(k-2)/4}$ and even powerful semidefinite programming relaxations appear to fail for $1lllambdall{n}^{(k-2)/4}$. In order to elucidate this behavior, we consider the maximum likelihood estimator, which requires maximizing a degree-$k$ homogeneous polynomial over the unit sphere in $n$ dimensions. We compute the expected number of critical points and local maxima of this objective function and show that it is exponential in the dimensions $n$, and give exact formulas for the exponential growth rate. We show that (for $lambda$ larger than a constant) critical points are either very close to the unknown vector $$, or are confined in a band of width $Theta(lambd{a}^{-1/(k-1)})$ around the maximum circle that is orthogonal to $$. For local maxima, this band shrinks to be of size $Theta(lambd{a}^{-1/(k-2)})$. These `uninformative' local maxima are likely to cause the failure of optimization algorithms.

Recommendations

• Statistical limits of spiked tensor models
• Algorithmic thresholds for tensor PCA
• Statistical thresholds for tensor PCA
• On the optimization landscape of tensor decompositions
• Sharp complexity asymptotics and topological trivialization for the (p, k) spiked tensor model

Cited in

(41)

• How to iron out rough landscapes and get optimal performances: averaged gradient descent and its application to tensor PCA
• When random tensors meet random matrices
• A spin glass model for the loss surfaces of generative adversarial networks
• Statistical limits of spiked tensor models
• The loss surfaces of neural networks with general activation functions
• Phase transition in the spiked random tensor with Rademacher prior
• Landscape complexity beyond invariance and the elastic manifold
• Statistical-computational trade-offs in tensor PCA and related problems via communication complexity
• Optimization landscape in the simplest constrained random least-square problem
• Large deviations for the largest eigenvalue of sub-Gaussian matrices
• Inference for low-rank tensors -- no need to debias
• Free energy subadditivity for symmetric random Hamiltonians
• Likelihood landscape and maximum likelihood estimation for the discrete orbit recovery model
• Sharp complexity asymptotics and topological trivialization for the (p, k) spiked tensor model
• Superposition of random plane waves in high spatial dimensions: Random matrix approach to landscape complexity
• scientific article; zbMATH DE number 7370623 (Why is no real title available?)
• Long random matrices and tensor unfolding
• Mean number and correlation function of critical points of isotropic Gaussian fields and some results on GOE random matrices
• Large deviations for the largest eigenvalue of matrices with variance profiles
• Local minima in disordered mean-field ferromagnets
• High‐dimensional limit theorems for SGD: Effective dynamics and critical scaling
• Sparse random tensors: concentration, regularization and applications
• Exponential growth of random determinants beyond invariance
• Marchenko–Pastur law with relaxed independence conditions
• Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization
• Phase transition in random tensors with multiple independent spikes
• Complexity of Gaussian random fields with isotropic increments
• Triviality of the geometry of mixed \(p\)-spin spherical Hamiltonians with external field
• Algorithmic thresholds for tensor PCA
• Counting equilibria in a random non-gradient dynamics with heterogeneous relaxation rates
• TAP free energy, spin glasses and variational inference
• Statistical query lower bounds for tensor PCA
• Community detection on mixture multilayer networks via regularized tensor decomposition
• Nature versus nurture: dynamical evolution in disordered Ising ferromagnets
• Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis
• Approximate ground states of hypercube spin glasses are near corners
• Sparse random hypergraphs: non-backtracking spectra and community detection
• Statistical thresholds for tensor PCA
• Community Detection in General Hypergraph Via Graph Embedding
• Rare events in random matrix theory
• Optimizing mean field spin glasses with external field

This page was built for publication: The landscape of the spiked tensor model

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