{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T19:19:05Z","timestamp":1790709545951,"version":"4.1.0"},"reference-count":42,"publisher":"IOP Publishing","issue":"3","license":[{"start":{"date-parts":[[2021,7,13]],"date-time":"2021-07-13T00:00:00Z","timestamp":1626134400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,13]],"date-time":"2021-07-13T00:00:00Z","timestamp":1626134400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/iopscience.iop.org\/info\/page\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Research and Innovation Programme Grant","award":["714608-SMiLe"],"award-info":[{"award-number":["714608-SMiLe"]}]},{"name":"ERC"}],"content-domain":{"domain":["iopscience.iop.org"],"crossmark-restriction":false},"short-container-title":["Mach. Learn.: Sci. Technol."],"published-print":{"date-parts":[[2021,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>In this paper we investigate how gradient-based algorithms such as gradient descent (GD), (multi-pass) stochastic GD, 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 GD are able to reach perfect generalization for regions of control parameters where the GD 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 GD can obtain better generalization properties from less informed initializations.<\/jats:p>","DOI":"10.1088\/2632-2153\/ac0615","type":"journal-article","created":{"date-parts":[[2021,5,27]],"date-time":"2021-05-27T19:21:19Z","timestamp":1622143279000},"page":"035029","update-policy":"https:\/\/doi.org\/10.1088\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem"],"prefix":"10.1088","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9944-2498","authenticated-orcid":false,"given":"Francesca","family":"Mignacco","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4722-6811","authenticated-orcid":false,"given":"Pierfrancesco","family":"Urbani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lenka","family":"Zdeborov\u00e1","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"266","published-online":{"date-parts":[[2021,7,13]]},"reference":[{"key":"mlstac0615bib1","article-title":"Bad global minima exist and SGD can reach them","author":"Liu","year":"2019"},{"key":"mlstac0615bib2","article-title":"Poly-time universality and limitations of deep learning","author":"Abbe","year":"2020"},{"key":"mlstac0615bib3","article-title":"Shape matters: understanding the implicit bias of the noise covariance","author":"HaoChen","year":"2020"},{"key":"mlstac0615bib4","first-page":"pp 1810","article-title":"Stochastic gradient and Langevin processes","author":"Cheng","year":"2020"},{"key":"mlstac0615bib5","first-page":"pp 2101","article-title":"Stochastic modified equations and adaptive stochastic gradient algorithms","author":"Li","year":"2017"},{"key":"mlstac0615bib6","article-title":"Three factors influencing minima in SGD","author":"Jastrzebski","year":"2017"},{"key":"mlstac0615bib7","doi-asserted-by":"publisher","first-page":"3","DOI":"10.4310\/AMSA.2019.v4.n1.a1","article-title":"On the diffusion approximation of nonconvex stochastic gradient descent","volume":"4","author":"Hu","year":"2019","journal-title":"Ann. Math. Sci. Appl."},{"key":"mlstac0615bib8","first-page":"pp 5827","article-title":"A tail-index analysis of stochastic gradient noise in deep neural networks","author":"Simsekli","year":"2019"},{"key":"mlstac0615bib9","article-title":"Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classification","author":"Mignacco","year":"2020"},{"key":"mlstac0615bib10","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1080\/713817747","article-title":"The question of phase retrieval in optics","volume":"10","author":"Walther","year":"1963","journal-title":"Opt. Acta: Int. J. Opt."},{"key":"mlstac0615bib11","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1364\/JOSAA.7.000394","article-title":"Phase retrieval in crystallography and optics","volume":"7","author":"Millane","year":"1990","journal-title":"J. Opt. Soc. Am. A"},{"key":"mlstac0615bib12","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/j.acha.2005.07.001","article-title":"On signal reconstruction without phase","volume":"20","author":"Balan","year":"2006","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"mlstac0615bib13","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S0034-4877(06)80008-X","article-title":"The Pauli problem, state reconstruction and quantum-real numbers","volume":"57","author":"Corbett","year":"2006","journal-title":"Rep. Math. Phys."},{"key":"mlstac0615bib14","first-page":"pp 287","article-title":"Landscape complexity for the empirical risk of generalized linear models","author":"Maillard","year":"2020"},{"key":"mlstac0615bib15","doi-asserted-by":"publisher","first-page":"5451","DOI":"10.1073\/pnas.1802705116","article-title":"Optimal errors and phase transitions in high-dimensional generalized linear models","volume":"116","author":"Barbier","year":"2019","journal-title":"Proc. Natl Acad. Sci."},{"key":"mlstac0615bib16","first-page":"pp 1445","article-title":"Fundamental limits of weak recovery with applications to phase retrieval","author":"Mondelli","year":"2018"},{"key":"mlstac0615bib17","doi-asserted-by":"publisher","first-page":"3600","DOI":"10.1109\/TIT.2019.2893254","article-title":"Optimization-based amp for phase retrieval: the impact of initialization and l2 regularization","volume":"65","author":"Ma","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"mlstac0615bib18","first-page":"pp 4963","article-title":"Spectral method for multiplexed phase retrieval and application in optical imaging in complex media","author":"Dong","year":"2019"},{"key":"mlstac0615bib19","doi-asserted-by":"publisher","first-page":"2347","DOI":"10.1109\/TSP.2019.2904918","article-title":"Optimal spectral initialization for signal recovery with applications to phase retrieval","volume":"67","author":"Luo","year":"2019","journal-title":"IEEE Trans. Signal Process."},{"key":"mlstac0615bib20","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s10107-019-01363-6","article-title":"Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval","volume":"176","author":"Chen","year":"2019","journal-title":"Math. Program."},{"key":"mlstac0615bib21","article-title":"Complex dynamics in simple neural networks: understanding gradient flow in phase retrieval","author":"Mannelli","year":"2020a"},{"key":"mlstac0615bib22","first-page":"pp 3452","article-title":"Generalisation error in learning with random features and the hidden manifold model","author":"Gerace","year":"2020"},{"key":"mlstac0615bib23","article-title":"Solving phase retrieval with random initial guess is nearly as good as by spectral initialization","author":"Cai","year":"2021"},{"key":"mlstac0615bib24","article-title":"Optimization and generalization of shallow neural networks with quadratic activation functions","author":"Mannelli","year":"2020b"},{"key":"mlstac0615bib25","first-page":"pp 3345","article-title":"Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval and matrix completion","author":"Ma","year":"2018"},{"key":"mlstac0615bib26","article-title":"Online stochastic gradient descent with arbitrary initialization solves non-smooth, non-convex phase retrieval","author":"Tan","year":"2019"},{"key":"mlstac0615bib27","article-title":"Optimal combination of linear and spectral estimators for generalized linear models","author":"Mondelli","year":"2020"},{"key":"mlstac0615bib28","first-page":"2003","article-title":"A classification for the performance of online SGD for high-dimensional inference","author":"Ben Arous","year":"2020"},{"key":"mlstac0615bib29","doi-asserted-by":"publisher","first-page":"p 476","DOI":"10.1142\/0271","author":"M\u00e9zard","year":"1986"},{"key":"mlstac0615bib30","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1103\/RevModPhys.68.13","article-title":"Dynamical mean-field theory of strongly correlated fermion systems and the limit of infinite dimensions","volume":"68","author":"Georges","year":"1996","journal-title":"Rev. Mod. Phys."},{"key":"mlstac0615bib31","author":"Parisi","year":"2020"},{"key":"mlstac0615bib32","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1103\/PhysRevLett.47.359","article-title":"Dynamic theory of the spin-glass phase","volume":"47","author":"Sompolinsky","year":"1981","journal-title":"Phys. Rev. Lett."},{"key":"mlstac0615bib33","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1103\/PhysRevLett.71.173","article-title":"Analytical solution of the off-equilibrium dynamics of a long-range spin-glass model","volume":"71","author":"Cugliandolo","year":"1993","journal-title":"Phys. Rev. Lett."},{"key":"mlstac0615bib34","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1103\/PhysRevLett.61.259","article-title":"Chaos in random neural networks","volume":"61","author":"Sompolinsky","year":"1988","journal-title":"Phys. Rev. Lett."},{"key":"mlstac0615bib35","first-page":"1367","article-title":"Symmetric Langevin spin glass dynamics","volume":"25","author":"Arous","year":"1997","journal-title":"Ann. Probab."},{"key":"mlstac0615bib36","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8121\/aaa68d","article-title":"Out-of-equilibrium dynamical mean-field equations for the perceptron model","volume":"51","author":"Agoritsas","year":"2018","journal-title":"J. Phys. A: Math. Theor."},{"key":"mlstac0615bib37","doi-asserted-by":"publisher","first-page":"2094","DOI":"10.1103\/PhysRevLett.68.2094","article-title":"New method for studying the dynamics of disordered spin systems without finite-size effects","volume":"68","author":"Eissfeller","year":"1992","journal-title":"Phys. Rev. Lett."},{"key":"mlstac0615bib38","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1103\/PhysRevE.50.709","article-title":"Carlo approach to the Sherrington-Kirkpatrick model with asymmetric couplings","volume":"50","author":"Eissfeller","year":"1994","journal-title":"Phys. Rev. E"},{"key":"mlstac0615bib39","article-title":"The anisotropic noise in stochastic gradient descent: its behavior of escaping from sharp minima and regularization effects","author":"Zhu","year":"2019"},{"key":"mlstac0615bib40","article-title":"On large-batch training for deep learning: generalization gap and sharp minima","author":"Keskar","year":"2017"},{"key":"mlstac0615bib41","author":"Zinn-Justin","year":"1996"},{"key":"mlstac0615bib42","article-title":"Deep double descent: where bigger models and more data hurt","author":"Nakkiran","year":"2020"}],"container-title":["Machine Learning: Science and Technology"],"original-title":[],"link":[{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-2153\/ac0615","content-type":"text\/html","content-version":"am","intended-application":"text-mining"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-2153\/ac0615\/pdf","content-type":"application\/pdf","content-version":"am","intended-application":"text-mining"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-2153\/ac0615","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-2153\/ac0615\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-2153\/ac0615\/pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-2153\/ac0615\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-2153\/ac0615\/pdf","content-type":"application\/pdf","content-version":"am","intended-application":"similarity-checking"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-2153\/ac0615\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,13]],"date-time":"2021-12-13T11:18:18Z","timestamp":1639394298000},"score":1,"resource":{"primary":{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/2632-2153\/ac0615"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,13]]},"references-count":42,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2021,7,13]]},"published-print":{"date-parts":[[2021,9,1]]}},"URL":"https:\/\/doi.org\/10.1088\/2632-2153\/ac0615","relation":{},"ISSN":["2632-2153"],"issn-type":[{"value":"2632-2153","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,13]]},"assertion":[{"value":"Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem","name":"article_title","label":"Article Title"},{"value":"Machine Learning: Science and Technology","name":"journal_title","label":"Journal Title"},{"value":"paper","name":"article_type","label":"Article Type"},{"value":"\u00a9 2021 The Author(s). Published by IOP Publishing Ltd","name":"copyright_information","label":"Copyright Information"},{"value":"2021-04-14","name":"date_received","label":"Date Received","group":{"name":"publication_dates","label":"Publication dates"}},{"value":"2021-05-27","name":"date_accepted","label":"Date Accepted","group":{"name":"publication_dates","label":"Publication dates"}},{"value":"2021-07-13","name":"date_epub","label":"Online publication date","group":{"name":"publication_dates","label":"Publication dates"}}]}}