Stochastic Gradient Descent outperforms Gradient Descent in recovering a high-dimensional signal in a glassy energy landscape
arXiv:2309.04788
Abstract
Stochastic Gradient Descent (SGD) is an out-of-equilibrium algorithm used extensively to train artificial neural networks. However very little is known on to what extent SGD is crucial for to the success of this technology and, in particular, how much it is effective in optimizing high-dimensional non-convex cost functions as compared to other optimization algorithms such as Gradient Descent (GD). In this work we leverage dynamical mean field theory to benchmark its performances in the high-dimensional limit. To do that, we consider the problem of recovering a hidden high-dimensional non-linearly encrypted signal, a prototype high-dimensional non-convex hard optimization problem. We compare the performances of SGD to GD and we show that SGD largely outperforms GD for sufficiently small batch sizes. In particular, a power law fit of the relaxation time of these algorithms shows that the recovery threshold for SGD with small batch size is smaller than the corresponding one of GD.
arXiv comment5 pages + appendix. 3 figures
References in corpus (16)
- Spin-Glass Theory for Pedestrians
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- Essentially No Barriers in Neural Network Energy Landscape
- In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning
- Phase Retrieval: From Computational Imaging to Machine Learning
- Dynamics of glassy systems
- Stochastic gradient descent introduces an effective landscape-dependent regularization favoring flat solutions
- Bad Global Minima Exist and SGD Can Reach Them
- Dynamics of Learning with Restricted Training Sets I: General Theory
- Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
- Complex Dynamics in Simple Neural Networks: Understanding Gradient Flow in Phase Retrieval
- A continuous constraint satisfaction problem for the rigidity transition in confluent tissues
- Phase diagram of Stochastic Gradient Descent in high-dimensional two-layer neural networks
- Dynamical mean field theory for models of confluent tissues and beyond
- A Modern Look at the Relationship between Sharpness and Generalization
- Solving systems of Random Equations via First and Second-Order Optimization Algorithms