Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem

Abstract

In this paper we investigate how gradient-based algorithms such as gradient descent, (multi-pass) stochastic gradient descent, its persistent variant, and the Langevin algorithm navigate non-convex loss-landscapes and which of them is able to reach the best generalization error at limited sample complexity. We consider the loss landscape of the high-dimensional phase retrieval problem as a prototypical highly non-convex example. We observe that for phase retrieval the stochastic variants of gradient descent are able to reach perfect generalization for regions of control parameters where the gradient descent algorithm is not. We apply dynamical mean-field theory from statistical physics to characterize analytically the full trajectories of these algorithms in their continuous-time limit, with a warm start, and for large system sizes. We further unveil several intriguing properties of the landscape and the algorithms such as that the gradient descent can obtain better generalization properties from less informed initializations.

28 pages, 11 figures

References in corpus (3)

• A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance
• Poly-time universality and limitations of deep learning

Cited by in corpus (9)

• Phase Retrieval: From Computational Imaging to Machine Learning
• The effective noise of Stochastic Gradient Descent
• Single-step transmission matrix retrieval for fast imaging through multi-mode fibers
• Rigorous dynamical mean field theory for stochastic gradient descent methods
• The Limiting Dynamics of SGD: Modified Loss, Phase Space Oscillations, and Anomalous Diffusion
• Analytical Study of Momentum-Based Acceleration Methods in Paradigmatic High-Dimensional Non-Convex Problems
• Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
• Gradient descent dynamics and the jamming transition in infinite dimensions
• Catapult Dynamics and Phase Transitions in Quadratic Nets