mlsanityData to 7 Oct 2026

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

arXiv 2103.04902 ↗First posted 8 Mar 2021cond-mat.dis-nn cs.LG math.STcited by 23

Not on the map. Why?

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.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). Builds on 20 of its 43 references that are in the map. First posted on arXiv 8 Mar 2021.

Builds on

20 of 43 references.

References · 20

  1. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,337
  2. 2019Deep Double Descent: Where Bigger Models and More Data Hurtcited by 667
  3. 2017Three Factors Influencing Minima in SGDcited by 270
  4. 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 213
  5. 2015Stochastic modified equations and adaptive stochastic gradient algorithmscited by 141
  6. 2020Generalisation error in learning with random features and the hidden manifold modelcited by 126
  7. 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 115
  8. 2020Shape Matters: Understanding the Implicit Bias of the Noise Covariancecited by 88
  9. 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
  10. 2020Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classificationcited by 60
  11. 2020Optimization and Generalization of Shallow Neural Networks with Quadratic Activation Functionscited by 50
  12. 2019Bad Global Minima Exist and SGD Can Reach Themcited by 49
8 more
  1. 2017Fundamental Limits of Weak Recovery with Applications to Phase Retrievalcited by 39
  2. 2019Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrievalcited by 34
  3. 2020Poly-time universality and limitations of deep learningcited by 23
  4. 2020Complex Dynamics in Simple Neural Networks: Understanding Gradient Flow in Phase Retrievalcited by 18
  5. 2019Landscape Complexity for the Empirical Risk of Generalized Linear Modelscited by 15
  6. 2020Optimal Combination of Linear and Spectral Estimators for Generalized Linear Modelscited by 15
  7. 2021Solving phase retrieval with random initial guess is nearly as good as by spectral initializationcited by 9
  8. 2018Spectral Method for Multiplexed Phase Retrieval and Application in Optical Imaging in Complex Mediacited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 2; 2023: 6; 2024: 7; 2025: 1; 2026: 2.

23 papers.

Sort:

  1. 2022Self-Consistent Dynamical Field Theory of Kernel Evolution in Wide Neural Networkscited by 104
  2. 2023Grokking as the Transition from Lazy to Rich Training Dynamicscited by 102
  3. 2024The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponentscited by 50
  4. 2021The effective noise of Stochastic Gradient Descentcited by 25
  5. 2024Bayes-optimal learning of an extensive-width neural network from quadratically many samplescited by 23
  6. 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
  7. 2021The Limiting Dynamics of SGD: Modified Loss, Phase Space Oscillations, and Anomalous Diffusioncited by 19
  8. 2021Model, sample, and epoch-wise descents: exact solution of gradient flow in the random feature modelcited by 17
  9. 2023Escaping mediocrity: how two-layer networks learn hard generalized linear models with SGDcited by 14
  10. 2024High-dimensional learning of narrow neural networkscited by 12
  11. 2023Catapult Dynamics and Phase Transitions in Quadratic Netscited by 8
  12. 2024The Role of the Time-Dependent Hessian in High-Dimensional Optimizationcited by 7
11 more
  1. 2022Gradient flow in the gaussian covariate model: exact solution of learning curves and multiple descent structurescited by 5
  2. 2023Stochastic Gradient Descent outperforms Gradient Descent in recovering a high-dimensional signal in a glassy energy landscapecited by 3
  3. 2023Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problemscited by 3
  4. 2024Asymptotic Dynamics of Alternating Minimization for Bilinear Regressioncited by 3
  5. 2024Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokenscited by 3
  6. 2023The Local Landscape of Phase Retrieval Under Limited Samplescited by 1
  7. 2024Stochastic Gradient Flow Dynamics of Test Risk and its Exact Solution for Weak Featurescited by 1
  8. 2021Learning Curves for SGD on Structured Featurescited by 0
  9. 2025Phase retrieval with rank d measurements -- descending algorithms phase transitionscited by 0
  10. 2026Detecting Metastable Basins in High Dimensions via Marginal Trajectory Distribution Discriminationcited by 0
  11. 2026Theory of learning of high-dimensional controlled non-linear dynamical systems (I): models and methodscited by 0