# Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem arXiv: https://arxiv.org/abs/2103.04902 ยท HTML: https://mlsanity.com/paper/2103.04902/ ## Key facts - Cited by 23 papers in the map (data through 14 Oct 2026). - Builds on 20 of its 43 references that are in the map. - First posted on arXiv 8 Mar 2021. ## Builds on (most cited first, 20 of 20) - [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016) - [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019) - [Three Factors Influencing Minima in SGD](https://mlsanity.com/paper/1711.04623/) (2017) - [A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks](https://mlsanity.com/paper/1901.06053/) (2019) - [Stochastic modified equations and adaptive stochastic gradient algorithms](https://mlsanity.com/paper/1511.06251/) (2015) - [Generalisation error in learning with random features and the hidden manifold model](https://mlsanity.com/paper/2002.09339/) (2020) - [Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/1708.03395/) (2017) - [Shape Matters: Understanding the Implicit Bias of the Noise Covariance](https://mlsanity.com/paper/2006.08680/) (2020) - [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018) - [Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classification](https://mlsanity.com/paper/2006.06098/) (2020) - [Optimization and Generalization of Shallow Neural Networks with Quadratic Activation Functions](https://mlsanity.com/paper/2006.15459/) (2020) - [Bad Global Minima Exist and SGD Can Reach Them](https://mlsanity.com/paper/1906.02613/) (2019) - [Fundamental Limits of Weak Recovery with Applications to Phase Retrieval](https://mlsanity.com/paper/1708.05932/) (2017) - [Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval](https://mlsanity.com/paper/1910.12837/) (2019) - [Poly-time universality and limitations of deep learning](https://mlsanity.com/paper/2001.02992/) (2020) - [Complex Dynamics in Simple Neural Networks: Understanding Gradient Flow in Phase Retrieval](https://mlsanity.com/paper/2006.06997/) (2020) - [Landscape Complexity for the Empirical Risk of Generalized Linear Models](https://mlsanity.com/paper/1912.02143/) (2019) - [Optimal Combination of Linear and Spectral Estimators for Generalized Linear Models](https://mlsanity.com/paper/2008.03326/) (2020) - [Solving phase retrieval with random initial guess is nearly as good as by spectral initialization](https://mlsanity.com/paper/2101.03540/) (2021) - [Spectral Method for Multiplexed Phase Retrieval and Application in Optical Imaging in Complex Media](https://mlsanity.com/paper/1810.13038/) (2018) ## Built on by (most cited first, 23 of 23) - [Grokking as the Transition from Lazy to Rich Training Dynamics](https://mlsanity.com/paper/2310.06110/) (2023) - [Self-Consistent Dynamical Field Theory of Kernel Evolution in Wide Neural Networks](https://mlsanity.com/paper/2205.09653/) (2022) - [The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents](https://mlsanity.com/paper/2402.03220/) (2024) - [The effective noise of Stochastic Gradient Descent](https://mlsanity.com/paper/2112.10852/) (2021) - [Bayes-optimal learning of an extensive-width neural network from quadratically many samples](https://mlsanity.com/paper/2408.03733/) (2024) - [On the Cryptographic Hardness of Learning Single Periodic Neurons](https://mlsanity.com/paper/2106.10744/) (2021) - [The Limiting Dynamics of SGD: Modified Loss, Phase Space Oscillations, and Anomalous Diffusion](https://mlsanity.com/paper/2107.09133/) (2021) - [Model, sample, and epoch-wise descents: exact solution of gradient flow in the random feature model](https://mlsanity.com/paper/2110.11805/) (2021) - [Escaping mediocrity: how two-layer networks learn hard generalized linear models with SGD](https://mlsanity.com/paper/2305.18502/) (2023) - [High-dimensional learning of narrow neural networks](https://mlsanity.com/paper/2409.13904/) (2024) - [Catapult Dynamics and Phase Transitions in Quadratic Nets](https://mlsanity.com/paper/2301.07737/) (2023) - [The Role of the Time-Dependent Hessian in High-Dimensional Optimization](https://mlsanity.com/paper/2403.02418/) (2024) - [Gradient flow in the gaussian covariate model: exact solution of learning curves and multiple descent structures](https://mlsanity.com/paper/2212.06757/) (2022) - [Stochastic Gradient Descent outperforms Gradient Descent in recovering a high-dimensional signal in a glassy energy landscape](https://mlsanity.com/paper/2309.04788/) (2023) - [Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problems](https://mlsanity.com/paper/2309.05337/) (2023) - [Asymptotic Dynamics of Alternating Minimization for Bilinear Regression](https://mlsanity.com/paper/2402.04751/) (2024) - [Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokens](https://mlsanity.com/paper/2410.18858/) (2024) - [Learning Curves for SGD on Structured Features](https://mlsanity.com/paper/2106.02713/) (2021) - [The Local Landscape of Phase Retrieval Under Limited Samples](https://mlsanity.com/paper/2311.15221/) (2023) - [Stochastic Gradient Flow Dynamics of Test Risk and its Exact Solution for Weak Features](https://mlsanity.com/paper/2402.07626/) (2024) - [Phase retrieval with rank d measurements -- descending algorithms phase transitions](https://mlsanity.com/paper/2506.18282/) (2025) - [Detecting Metastable Basins in High Dimensions via Marginal Trajectory Distribution Discrimination](https://mlsanity.com/paper/2605.24136/) (2026) - [Theory of learning of high-dimensional controlled non-linear dynamical systems (I): models and methods](https://mlsanity.com/paper/2606.07247/) (2026) ## Abstract (arXiv) 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.