The landscape of the spiked tensor model

DOI10.1002/CPA.21861zbMATH Open1434.62078arXiv1711.05424OpenAlexW2968353065MaRDI QIDQ5204884FDOQ5204884

Authors:

Publication date: 5 December 2019

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

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.

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

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

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)

Cited In (41)

• 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
• Free energy subadditivity for symmetric random Hamiltonians
• Inference for low-rank tensors -- no need to debias
• 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
• Title not available (Why is that?)
• 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
• High‐dimensional limit theorems for SGD: Effective dynamics and critical scaling
• Local minima in disordered mean-field ferromagnets
• Exponential growth of random determinants beyond invariance
• Sparse random tensors: concentration, regularization and applications
• Marchenko–Pastur law with relaxed independence conditions
• Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization
• Complexity of Gaussian random fields with isotropic increments
• Phase transition in random tensors with multiple independent spikes
• Triviality of the geometry of mixed \(p\)-spin spherical Hamiltonians with external field
• Counting equilibria in a random non-gradient dynamics with heterogeneous relaxation rates
• Algorithmic thresholds for tensor PCA
• Statistical query lower bounds for tensor PCA
• TAP free energy, spin glasses and variational inference
• Community detection on mixture multilayer networks via regularized tensor decomposition
• Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis
• Nature versus nurture: dynamical evolution in disordered Ising ferromagnets
• Sparse random hypergraphs: non-backtracking spectra and community detection
• Approximate ground states of hypercube spin glasses are near corners
• 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
• 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

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)