# Stochastic Gradient Descent outperforms Gradient Descent in recovering a high-dimensional signal in a glassy energy landscape

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 40 references that are in the map.
- First posted on arXiv 9 Sep 2023.

## Builds on (most cited first, 19 of 19)

- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Essentially No Barriers in Neural Network Energy Landscape](https://mlsanity.com/paper/1803.00885/) (2018)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Online stochastic gradient descent on non-convex losses from high-dimensional inference](https://mlsanity.com/paper/2003.10409/) (2020)
- [A Modern Look at the Relationship between Sharpness and Generalization](https://mlsanity.com/paper/2302.07011/) (2023)
- [High-dimensional limit theorems for SGD: Effective dynamics and critical scaling](https://mlsanity.com/paper/2206.04030/) (2022)
- [Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classification](https://mlsanity.com/paper/2006.06098/) (2020)
- [Phase diagram of Stochastic Gradient Descent in high-dimensional two-layer neural networks](https://mlsanity.com/paper/2202.00293/) (2022)
- [Bad Global Minima Exist and SGD Can Reach Them](https://mlsanity.com/paper/1906.02613/) (2019)
- [Taxonomizing local versus global structure in neural network loss landscapes](https://mlsanity.com/paper/2107.11228/) (2021)
- [Passed & Spurious: Descent Algorithms and Local Minima in Spiked Matrix-Tensor Models](https://mlsanity.com/paper/1902.00139/) (2019)
- [The effective noise of Stochastic Gradient Descent](https://mlsanity.com/paper/2112.10852/) (2021)
- [Marvels and Pitfalls of the Langevin Algorithm in Noisy High-dimensional Inference](https://mlsanity.com/paper/1812.09066/) (2018)
- [Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem](https://mlsanity.com/paper/2103.04902/) (2021)
- [Stochastic gradient descent introduces an effective landscape-dependent regularization favoring flat solutions](https://mlsanity.com/paper/2206.01246/) (2022)
- [Complex Dynamics in Simple Neural Networks: Understanding Gradient Flow in Phase Retrieval](https://mlsanity.com/paper/2006.06997/) (2020)
- [Analytical Study of Momentum-Based Acceleration Methods in Paradigmatic High-Dimensional Non-Convex Problems](https://mlsanity.com/paper/2102.11755/) (2021)

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

- [Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problems](https://mlsanity.com/paper/2309.05337/) (2023)
- [Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokens](https://mlsanity.com/paper/2410.18858/) (2024)
- [Theory of learning of high-dimensional controlled non-linear dynamical systems (I): models and methods](https://mlsanity.com/paper/2606.07247/) (2026)

## Abstract (arXiv)

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.