Who is Afraid of Big Bad Minima? Analysis of Gradient-Flow in a Spiked Matrix-Tensor Model

Abstract

Gradient-based algorithms are effective for many machine learning tasks, but despite ample recent effort and some progress, it often remains unclear why they work in practice in optimising high-dimensional non-convex functions and why they find good minima instead of being trapped in spurious ones. Here we present a quantitative theory explaining this behaviour in a spiked matrix-tensor model. Our framework is based on the Kac-Rice analysis of stationary points and a closed-form analysis of gradient-flow originating from statistical physics. We show that there is a well defined region of parameters where the gradient-flow algorithm finds a good global minimum despite the presence of exponentially many spurious local minima. We show that this is achieved by surfing on saddles that have strong negative direction towards the global minima, a phenomenon that is connected to a BBP-type threshold in the Hessian describing the critical points of the landscapes.

arXiv comment9 pages, 4 figures + appendix. Appears in Proceedings of the Advances in Neural Information Processing Systems 2019 (NeurIPS 2019)

References in corpus (14)

• Analytical Solution of the Off-Equilibrium Dynamics of a Long Range Spin-Glass Model
• Spin-Glass Theory for Pedestrians
• Global Optimality of Local Search for Low Rank Matrix Recovery
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Phase space geometry and slow dynamics
• Weak-ergodicity breaking in mean-field spin-glass models
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• The spherical $2+p$ spin glass model: an exactly solvable model for glass to spin-glass transition
• Depth Creates No Bad Local Minima
• Algorithmic thresholds for tensor PCA
• Performance of simulated annealing in p-spin glasses
• Topology and Geometry of Half-Rectified Network Optimization
• The p-spin spherical spin glass model
• Limiting Dynamics for Spherical Models of Spin Glasses with Magnetic Field

Cited by in corpus (1)

• Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model