{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T05:30:15Z","timestamp":1782279015830,"version":"3.54.5"},"reference-count":55,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,2,18]],"date-time":"2019-02-18T00:00:00Z","timestamp":1550448000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2019,7]]},"DOI":"10.1007\/s10107-019-01374-3","type":"journal-article","created":{"date-parts":[[2019,2,18]],"date-time":"2019-02-18T15:00:54Z","timestamp":1550502054000},"page":"311-337","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":91,"title":["First-order methods almost always avoid strict saddle points"],"prefix":"10.1007","volume":"176","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0064-7800","authenticated-orcid":false,"given":"Jason D.","family":"Lee","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ioannis","family":"Panageas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Georgios","family":"Piliouras","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Max","family":"Simchowitz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael I.","family":"Jordan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benjamin","family":"Recht","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,2,18]]},"reference":[{"issue":"2","key":"1374_CR1","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1137\/040605266","volume":"16","author":"PA Absil","year":"2005","unstructured":"Absil, P.A., Mahony, R., Andrews, B.: Convergence of the iterates of descent methods for analytic cost functions. SIAM J. Optim. 16(2), 531\u2013547 (2005)","journal-title":"SIAM J. Optim."},{"key":"1374_CR2","volume-title":"Optimization Algorithms on Matrix Manifolds","author":"PA Absil","year":"2009","unstructured":"Absil, P.A., Mahony, R., Sepulchre, R.: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton (2009)"},{"key":"1374_CR3","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/978-3-642-40020-9_39","volume-title":"Geometric Science of Information","author":"PA Absil","year":"2013","unstructured":"Absil, P.A., Mahony, R., Trumpf, J.: An extrinsic look at the Riemannian Hessian. In: Nielsen, F., Barbaresco, F. (eds.) Geometric Science of Information, pp. 361\u2013368. Springer, Berlin (2013)"},{"issue":"1","key":"1374_CR4","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/100802529","volume":"22","author":"PA Absil","year":"2012","unstructured":"Absil, P.A., Malick, J.: Projection-like retractions on matrix manifolds. SIAM J. Optim. 22(1), 135\u2013158 (2012)","journal-title":"SIAM J. Optim."},{"key":"1374_CR5","volume-title":"Random Fields and Geometry","author":"RJ Adler","year":"2009","unstructured":"Adler, R.J., Taylor, J.E.: Random Fields and Geometry. Springer, Berlin (2009)"},{"key":"1374_CR6","unstructured":"Arora, S., Ge, R., Ma, T., Moitra, A.: Simple, efficient, and neural algorithms for sparse coding. In: Proceedings of The 28th Conference on Learning Theory, pp. 113\u2013149 (2015)"},{"issue":"2","key":"1374_CR7","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1287\/moor.1100.0449","volume":"35","author":"H Attouch","year":"2010","unstructured":"Attouch, H., Bolte, J., Redont, P., Soubeyran, A.: Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka\u2013Lojasiewicz inequality. Math. Oper. Res. 35(2), 438\u2013457 (2010)","journal-title":"Math. Oper. Res."},{"issue":"1\u20132","key":"1374_CR8","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s10107-011-0484-9","volume":"137","author":"H Attouch","year":"2013","unstructured":"Attouch, H., Bolte, J., Svaiter, B.F.: Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward\u2013backward splitting, and regularized Gauss\u2013Seidel methods. Math. Program. 137(1\u20132), 91\u2013129 (2013)","journal-title":"Math. Program."},{"issue":"2","key":"1374_CR9","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1002\/cpa.21422","volume":"66","author":"A Auffinger","year":"2013","unstructured":"Auffinger, A., Arous, G.B., \u010cern\u1ef3, J.: Random matrices and complexity of spin glasses. Commun. Pure Appl. Math. 66(2), 165\u2013201 (2013)","journal-title":"Commun. Pure Appl. Math."},{"key":"1374_CR10","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974997","volume-title":"First-Order Methods in Optimization","author":"A Beck","year":"2017","unstructured":"Beck, A.: First-Order Methods in Optimization, vol. 25. SIAM, New Delhi (2017)"},{"key":"1374_CR11","unstructured":"Belkin, M., Rademacher, L., Voss, J.: Basis learning as an algorithmic primitive. In: Conference on Learning Theory, pp. 446\u2013487 (2016)"},{"key":"1374_CR12","unstructured":"Bhojanapalli, S., Neyshabur, B., Srebro, N.: Global optimality of local search for low rank matrix recovery. In: Advances in Neural Information Processing Systems, pp. 3873\u20133881 (2016)"},{"issue":"6","key":"1374_CR13","doi-asserted-by":"publisher","first-page":"3319","DOI":"10.1090\/S0002-9947-09-05048-X","volume":"362","author":"J Bolte","year":"2010","unstructured":"Bolte, J., Daniilidis, A., Ley, O., Mazet, L., et al.: Characterizations of Lojasiewicz inequalities: subgradient flows, talweg, convexity. Trans. Am. Math. Soc 362(6), 3319\u20133363 (2010)","journal-title":"Trans. Am. Math. Soc"},{"issue":"1\u20132","key":"1374_CR14","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/s10107-013-0701-9","volume":"146","author":"J Bolte","year":"2014","unstructured":"Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization or nonconvex and nonsmooth problems. Math. Program. 146(1\u20132), 459\u2013494 (2014)","journal-title":"Math. Program."},{"issue":"3","key":"1374_CR15","doi-asserted-by":"publisher","first-page":"2131","DOI":"10.1137\/17M1138558","volume":"28","author":"J Bolte","year":"2018","unstructured":"Bolte, J., Sabach, S., Teboulle, M., Vaisbourd, Y.: First order methods beyond convexity and lipschitz gradient continuity with applications to quadratic inverse problems. SIAM J. Optim. 28(3), 2131\u20132151 (2018)","journal-title":"SIAM J. Optim."},{"key":"1374_CR16","unstructured":"Brutzkus, A., Globerson, A.: Globally optimal gradient descent for a convnet with Gaussian inputs. arXiv preprint arXiv:1702.07966 (2017)"},{"issue":"5","key":"1374_CR17","doi-asserted-by":"publisher","first-page":"2221","DOI":"10.1214\/16-AOS1443","volume":"44","author":"TT Cai","year":"2016","unstructured":"Cai, T.T., Li, X., Ma, Z., et al.: Optimal rates of convergence for noisy sparse phase retrieval via thresholded wirtinger flow. Ann. Stat. 44(5), 2221\u20132251 (2016)","journal-title":"Ann. Stat."},{"issue":"4","key":"1374_CR18","doi-asserted-by":"publisher","first-page":"1985","DOI":"10.1109\/TIT.2015.2399924","volume":"61","author":"EJ Candes","year":"2015","unstructured":"Candes, E.J., Li, X., Soltanolkotabi, M.: Phase retrieval via Wirtinger flow: theory and algorithms. IEEE Trans. Inf. Theory 61(4), 1985\u20132007 (2015)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1374_CR19","unstructured":"Choromanska, A., Henaff, M., Mathieu, M., Arous, G.B., LeCun, Y.: The loss surfaces of multilayer networks. In: Artificial Intelligence and Statistics, pp. 192\u2013204 (2015)"},{"key":"1374_CR20","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719857","volume-title":"Trust Region Methods","author":"AR Conn","year":"2000","unstructured":"Conn, A.R., Gould, N.I., Toint, P.L.: Trust Region Methods, vol. 1. SIAM, New Delhi (2000)"},{"key":"1374_CR21","unstructured":"Dauphin, Y.N., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., Bengio, Y.: Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. In: Advances in Neural Information Processing Systems, pp. 2933\u20132941 (2014)"},{"key":"1374_CR22","unstructured":"Du, S.S., Jin, C., Lee, J.D., Jordan, M.I., Poczos, B., Singh, A.: Gradient descent can take exponential time to escape saddle points. arXiv preprint arXiv:1705.10412 (2017)"},{"key":"1374_CR23","unstructured":"Du, S.S., Lee, J.D., Tian, Y.: When is a convolutional filter easy to learn? arXiv preprint arXiv:1709.06129 (2017)"},{"key":"1374_CR24","unstructured":"Ge, R., Huang, F., Jin, C., Yuan, Y.: Escaping from saddle points online stochastic gradient for tensor decomposition. In: Conference on Learning Theory, pp. 797\u2013842 (2015)"},{"key":"1374_CR25","unstructured":"Ge, R., Jin, C., Zheng, Y.: No spurious local minima in nonconvex low rank problems: a unified geometric analysis. arXiv preprint arXiv:1704.00708 (2017)"},{"key":"1374_CR26","unstructured":"Ge, R., Lee, J.D., Ma, T.: Matrix completion has no spurious local minimum. In: Advances in Neural Information Processing Systems, pp. 2973\u20132981 (2016)"},{"issue":"1","key":"1374_CR27","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/BF01585529","volume":"7","author":"PE Gill","year":"1974","unstructured":"Gill, P.E., Murray, W.: Newton-type methods for unconstrained and linearly constrained optimization. Math. Program. 7(1), 311\u2013350 (1974)","journal-title":"Math. Program."},{"key":"1374_CR28","unstructured":"Jin, C., Ge, R., Netrapalli, P., Kakade, S.M., Jordan, M.I.: How to escape saddle points efficiently. arXiv preprint arXiv:1703.00887 (2017)"},{"issue":"6","key":"1374_CR29","doi-asserted-by":"publisher","first-page":"2980","DOI":"10.1109\/TIT.2010.2046205","volume":"56","author":"RH Keshavan","year":"2009","unstructured":"Keshavan, R.H., Montanari, A., Oh, S.: Matrix completion from a few entries. IEEE Trans. Inf. Theory 56(6), 2980\u20132998 (2009)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1374_CR30","doi-asserted-by":"crossref","unstructured":"Kleinberg, R., Piliouras, G., Tardos, E.: Multiplicative updates outperform generic no-regret learning in congestion games. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pp. 533\u2013542. ACM (2009)","DOI":"10.1145\/1536414.1536487"},{"key":"1374_CR31","doi-asserted-by":"crossref","unstructured":"Lange, K.: Optimization, vol. 95. Springer (2013)","DOI":"10.1007\/978-1-4614-5838-8"},{"key":"1374_CR32","unstructured":"Lee, J.D., Simchowitz, M., Jordan, M.I., Recht, B.: Gradient descent only converges to minimizers. In: Conference on Learning Theory, pp. 1246\u20131257 (2016)"},{"issue":"1","key":"1374_CR33","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1287\/moor.1070.0291","volume":"33","author":"AS Lewis","year":"2008","unstructured":"Lewis, A.S., Malick, J.: Alternating projections on manifolds. Math. Oper. Res. 33(1), 216\u2013234 (2008)","journal-title":"Math. Oper. Res."},{"key":"1374_CR34","unstructured":"Liu, M., Yang, T.: On noisy negative curvature descent: competing with gradient descent for faster non-convex optimization. arXiv preprint arXiv:1709.08571 (2017)"},{"key":"1374_CR35","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF00305762","volume":"17","author":"V Losert","year":"1983","unstructured":"Losert, V., Akin, E.: Dynamics of games and genes: discrete versus continuous time. J. Math. Biol. 17, 241\u2013251 (1983)","journal-title":"J. Math. Biol."},{"key":"1374_CR36","volume-title":"An Introduction to Multivariable Analysis From Vector to Manifold","author":"P Mikusinski","year":"2012","unstructured":"Mikusinski, P., Taylor, M.: An Introduction to Multivariable Analysis From Vector to Manifold. Springer, Berlin (2012)"},{"issue":"1","key":"1374_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01582091","volume":"16","author":"JJ Mor\u00e9","year":"1979","unstructured":"Mor\u00e9, J.J., Sorensen, D.C.: On the use of directions of negative curvature in a modified Newton method. Math. Program. 16(1), 1\u201320 (1979)","journal-title":"Math. Program."},{"issue":"2","key":"1374_CR38","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BF02592948","volume":"39","author":"KG Murty","year":"1987","unstructured":"Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39(2), 117\u2013129 (1987)","journal-title":"Math. Program."},{"key":"1374_CR39","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9","volume-title":"Introductory Lectures on Convex Optimization","author":"Y Nesterov","year":"2004","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization, vol. 87. Springer, Berlin (2004)"},{"issue":"1","key":"1374_CR40","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s10107-006-0706-8","volume":"108","author":"Y Nesterov","year":"2006","unstructured":"Nesterov, Y., Polyak, B.T.: Cubic regularization of Newton method and its global performance. Math. Program. 108(1), 177\u2013205 (2006)","journal-title":"Math. Program."},{"key":"1374_CR41","unstructured":"ONeill, M., Wright, S.: Behavior of accelerated gradient methods near critical points of nonconvex problems. arXiv preprint arXiv:1706.07993 (2017)"},{"key":"1374_CR42","unstructured":"Panageas, I., Piliouras, G.: Gradient descent only converges to minimizers: non-isolated critical points and invariant regions. In: Innovations of Theoretical Computer Science (ITCS) (2017)"},{"key":"1374_CR43","unstructured":"Pascanu, R., Dauphin, Y.N., Ganguli, S., Bengio, Y.: On the saddle point problem for non-convex optimization. arXiv:1405.4604 (2014)"},{"key":"1374_CR44","doi-asserted-by":"publisher","first-page":"698","DOI":"10.1214\/aop\/1176990853","volume":"18","author":"R Pemantle","year":"1990","unstructured":"Pemantle, R.: Nonconvergence to unstable points in urn models and stochastic approximations. Ann. Probab. 18, 698\u2013712 (1990)","journal-title":"Ann. Probab."},{"key":"1374_CR45","unstructured":"Reddi, S.J., Zaheer, M., Sra, S., Poczos, B., Bach, F., Salakhutdinov, R., Smola, A.J.: A generic approach for escaping saddle points. arXiv preprint arXiv:1709.01434 (2017)"},{"key":"1374_CR46","doi-asserted-by":"crossref","unstructured":"Richt\u00e1rik, P., Tak\u00e1\u010d, M.: Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. arXiv preprint arXiv:1107.2848 (2011)","DOI":"10.1007\/s10107-012-0614-z"},{"key":"1374_CR47","doi-asserted-by":"crossref","unstructured":"Royer, C.W., Wright, S.J.: Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization. arXiv preprint arXiv:1706.03131 (2017)","DOI":"10.1137\/17M1134329"},{"key":"1374_CR48","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-1947-5","volume-title":"Global Stability of Dynamical Systems","author":"M Shub","year":"1987","unstructured":"Shub, M.: Global Stability of Dynamical Systems. Springer, Berlin (1987)"},{"key":"1374_CR49","unstructured":"Soltanolkotabi, M., Javanmard, A., Lee, J.D.: Theoretical insights into the optimization landscape of over-parameterized shallow neural networks. arXiv preprint arXiv:1707.04926 (2017)"},{"key":"1374_CR50","unstructured":"Sun, J., Qu, Q., Wright, J.: When are nonconvex problems not scary? arXiv preprint arXiv:1510.06096 (2015)"},{"key":"1374_CR51","doi-asserted-by":"crossref","unstructured":"Sun, J., Qu, Q., Wright, J.: A geometric analysis of phase retrieval. In: 2016 IEEE International Symposium on Information Theory (ISIT), pp. 2379\u20132383. IEEE (2016)","DOI":"10.1109\/ISIT.2016.7541725"},{"issue":"2","key":"1374_CR52","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1109\/TIT.2016.2632162","volume":"63","author":"J Sun","year":"2017","unstructured":"Sun, J., Qu, Q., Wright, J.: Complete dictionary recovery over the sphere I: overview and the geometric picture. IEEE Trans. Inf. Theory 63(2), 853\u2013884 (2017)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"1374_CR53","doi-asserted-by":"publisher","first-page":"885","DOI":"10.1109\/TIT.2016.2632149","volume":"63","author":"J Sun","year":"2017","unstructured":"Sun, J., Qu, Q., Wright, J.: Complete dictionary recovery over the sphere II: recovery by Riemannian trust-region method. IEEE Tran. Inf. Theory 63(2), 885\u2013914 (2017)","journal-title":"IEEE Tran. Inf. Theory"},{"key":"1374_CR54","unstructured":"Zhang, Y., Chen, X., Zhou, D., Jordan, M.I.: Spectral methods meet EM: a provably optimal algorithm for crowdsourcing. In: Advances in Neural Information Processing Systems, pp. 1260\u20131268 (2014)"},{"key":"1374_CR55","unstructured":"Zhao, T., Wang, Z., Liu, H.: Nonconvex low rank matrix factorization via inexact first order oracle. Adv. Neural Inf. Process. Syst. 559\u2013567 (2015)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-019-01374-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01374-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01374-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,12]],"date-time":"2022-09-12T01:34:09Z","timestamp":1662946449000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-019-01374-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,18]]},"references-count":55,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["1374"],"URL":"https:\/\/doi.org\/10.1007\/s10107-019-01374-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,18]]},"assertion":[{"value":"19 October 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 February 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 February 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}