# Passed & Spurious: Descent Algorithms and Local Minima in Spiked Matrix-Tensor Models

arXiv: https://arxiv.org/abs/1902.00139 · HTML: https://mlsanity.com/paper/1902.00139/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Feb 2019.

## Built on by (most cited first, 28 of 28)

- [A Dynamical Model of Neural Scaling Laws](https://mlsanity.com/paper/2402.01092/) (2024)
- [Self-Consistent Dynamical Field Theory of Kernel Evolution in Wide Neural Networks](https://mlsanity.com/paper/2205.09653/) (2022)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [How Feature Learning Can Improve Neural Scaling Laws](https://mlsanity.com/paper/2409.17858/) (2024)
- [The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents](https://mlsanity.com/paper/2402.03220/) (2024)
- [Infinite Limits of Multi-head Transformer Dynamics](https://mlsanity.com/paper/2405.15712/) (2024)
- [An Analytical Theory of Curriculum Learning in Teacher-Student Networks](https://mlsanity.com/paper/2106.08068/) (2021)
- [Deep Linear Network Training Dynamics from Random Initialization: Data, Width, Depth, and Hyperparameter Transfer](https://mlsanity.com/paper/2502.02531/) (2025)
- [Sliding down the stairs: how correlated latent variables accelerate learning with neural networks](https://mlsanity.com/paper/2404.08602/) (2024)
- [Statistical limits of dictionary learning: random matrix theory and the spectral replica method](https://mlsanity.com/paper/2109.06610/) (2021)
- [Sudakov-Fernique post-AMP, and a new proof of the local convexity of the TAP free energy](https://mlsanity.com/paper/2208.09550/) (2022)
- [The Role of the Time-Dependent Hessian in High-Dimensional Optimization](https://mlsanity.com/paper/2403.02418/) (2024)
- [On free energy barriers in Gaussian priors and failure of cold start MCMC for high-dimensional unimodal distributions](https://mlsanity.com/paper/2209.02001/) (2022)
- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [Computational Thresholds in Multi-Modal Learning via the Spiked Matrix-Tensor Model](https://mlsanity.com/paper/2506.02664/) (2025)
- [Analytical Study of Momentum-Based Acceleration Methods in Paradigmatic High-Dimensional Non-Convex Problems](https://mlsanity.com/paper/2102.11755/) (2021)
- [Rank-one matrix estimation: analytic time evolution of gradient descent dynamics](https://mlsanity.com/paper/2105.12257/) (2021)
- [A spin-glass model for the loss surfaces of generative adversarial networks](https://mlsanity.com/paper/2101.02524/) (2021)
- [Stochastic Gradient Descent outperforms Gradient Descent in recovering a high-dimensional signal in a glassy energy landscape](https://mlsanity.com/paper/2309.04788/) (2023)
- [Asymptotic Dynamics of Alternating Minimization for Bilinear Regression](https://mlsanity.com/paper/2402.04751/) (2024)
- [High-dimensional Asymptotics of Langevin Dynamics in Spiked Matrix Models](https://mlsanity.com/paper/2204.04476/) (2022)
- [Overparametrization bends the landscape: BBP transitions at initialization in simple Neural Networks](https://mlsanity.com/paper/2510.18435/) (2025)
- [Sharp description of local minima in the loss landscape of high-dimensional two-layer ReLU neural networks](https://mlsanity.com/paper/2604.09412/) (2026)
- [Gradient flow on extensive-rank positive semi-definite matrix denoising](https://mlsanity.com/paper/2303.09474/) (2023)
- [Topological Exploration of High-Dimensional Empirical Risk Landscapes: general approach, and applications to phase retrieval](https://mlsanity.com/paper/2602.17779/) (2026)
- [Selective Multiple Power Iteration: from Tensor PCA to gradient-based exploration of landscapes](https://mlsanity.com/paper/2112.12306/) (2021)
- [Topological complexity of spiked random polynomials and finite-rank spherical integrals](https://mlsanity.com/paper/2312.12323/) (2023)
- [Theory of learning of high-dimensional controlled non-linear dynamical systems (I): models and methods](https://mlsanity.com/paper/2606.07247/) (2026)

## Abstract (arXiv)

In this work we analyse quantitatively the interplay between the loss landscape and performance of descent algorithms in a prototypical inference problem, the spiked matrix-tensor model. We study a loss function that is the negative log-likelihood of the model. We analyse the number of local minima at a fixed distance from the signal/spike with the Kac-Rice formula, and locate trivialization of the landscape at large signal-to-noise ratios. We evaluate in a closed form the performance of a gradient flow algorithm using integro-differential PDEs as developed in physics of disordered systems for the Langevin dynamics. We analyze the performance of an approximate message passing algorithm estimating the maximum likelihood configuration via its state evolution. We conclude by comparing the above results: while we observe a drastic slow down of the gradient flow dynamics even in the region where the landscape is trivial, both the analyzed algorithms are shown to perform well even in the part of the region of parameters where spurious local minima are present.