Complex Dynamics in Simple Neural Networks: Understanding Gradient Flow in Phase Retrieval
arXiv:2006.06997
Abstract
Despite the widespread use of gradient-based algorithms for optimizing high-dimensional non-convex functions, understanding their ability of finding good minima instead of being trapped in spurious ones remains to a large extent an open problem. Here we focus on gradient flow dynamics for phase retrieval from random measurements. When the ratio of the number of measurements over the input dimension is small the dynamics remains trapped in spurious minima with large basins of attraction. We find analytically that above a critical ratio those critical points become unstable developing a negative direction toward the signal. By numerical experiments we show that in this regime the gradient flow algorithm is not trapped; it drifts away from the spurious critical points along the unstable direction and succeeds in finding the global minimum. Using tools from statistical physics we characterize this phenomenon, which is related to a BBP-type transition in the Hessian of the spurious minima.
arXiv comment9 pages, 5 figures + appendix
Cited by in corpus (10)
- Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem
- Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
- Fundamental problems in statistical physics XIV: Lecture on Machine Learning
- Optimization and Generalization of Shallow Neural Networks with Quadratic Activation Functions
- An Analytical Theory of Curriculum Learning in Teacher-Student Networks
- When you can't count, sample! Computable entropies beyond equilibrium from basin volumes
- Stochastic Gradient Descent outperforms Gradient Descent in recovering a high-dimensional signal in a glassy energy landscape
- Analytical Study of Momentum-Based Acceleration Methods in Paradigmatic High-Dimensional Non-Convex Problems
- Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization
- Catapult Dynamics and Phase Transitions in Quadratic Nets