{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T12:39:49Z","timestamp":1790685589545,"version":"4.1.0"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100015707","name":"SAIL-Toyota Center for AI Research","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100015707","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Stanford Graduate Fellowship"},{"name":"Numerical Technologies Fellowship"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["NSF-CAREER-1553086"],"award-info":[{"award-number":["NSF-CAREER-1553086"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>We consider the minimization of a nonconvex quadratic form regularized by a cubic term, which may exhibit saddle points and a suboptimal local minimum. Nonetheless, we prove that, under mild assumptions, gradient descent approximates the global minimum to within $\\varepsilon$ accuracy in $O(\\varepsilon^{-1}\\log(1\/\\varepsilon))$ steps for large $\\varepsilon$ and $O(\\log(1\/\\varepsilon))$ steps for small $\\varepsilon$ (compared to a condition number we define), with at most logarithmic dependence on the problem dimension. When we use gradient descent to approximate the cubic-regularized Newton step, our result implies a rate of convergence to second-order stationary points of general smooth nonconvex functions.<\/jats:p>","DOI":"10.1137\/17m1113898","type":"journal-article","created":{"date-parts":[[2019,9,5]],"date-time":"2019-09-05T11:02:28Z","timestamp":1567681348000},"page":"2146-2178","source":"Crossref","is-referenced-by-count":38,"title":["Gradient Descent Finds the Cubic-Regularized Nonconvex Newton Step"],"prefix":"10.1137","volume":"29","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5731-8640","authenticated-orcid":true,"given":"Yair","family":"Carmon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Duchi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,9,5]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"N. Agarwal, Z. Allen-Zhu, B. Bullins, E. Hazan, and T. Ma,\n                      Finding approximate local minima faster than gradient descent\n                      , in Proceedings of the Forty-Ninth Annual ACM Symposium on the Theory of Computing, Association for Computing Machinery, New York, NY, 2017.","DOI":"10.1145\/3055399.3055464"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1150281"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-014-9672-x"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/16M1080173"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/17M1114296"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0286-5"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0337-y"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2011.06.001"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"A. R. Conn, N. I. M. Gould, and P. L. Toint,\n                      Trust Region Methods\n                      , MPS-SIAM Ser. Optim., SIAM, Philadelphia, PA, 2000.","DOI":"10.1137\/1.9780898719857"},{"key":"atypb10","first-page":"99","author":"Duchi J. C.","year":"2018","journal-title":"RI"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/08072440X"},{"key":"atypb12","first-page":"797","volume":"40","author":"Ge R.","year":"2015","journal-title":"Proc. Mach. Learn. Res."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497322735"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-010-0011-7"},{"key":"atypb15","unstructured":"A. Griewank,\n                      The Modification of Newton's Method for Unconstrained Optimization by Bounding Cubic Terms\n                      , Technical report NA\/12, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, 1981."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0933-y"},{"key":"atypb17","unstructured":"N. Ho-Nguyen and F. K\\il\\in\u00e7-Karzan,\n                      A Second-Order Cone Based Approach for Solving the Trust-Region Subproblem and Its Variants\n                      , preprint,https:\/\/arxiv.org\/abs\/1603.03366, 2016."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/0613066"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1038\/nature14539"},{"key":"atypb20","first-page":"1246","volume":"49","author":"Lee J. D.","year":"2016","journal-title":"Proc. Mach. Learn. Res."},{"key":"atypb21","unstructured":"K. Y. Levy,\n                      The Power of Normalization: Faster Evasion of Saddle Points\n                      , preprint,https:\/\/arxiv.org\/abs\/1611.04831, 2016."},{"key":"atypb22","first-page":"1396","author":"Musco C.","year":"2015","journal-title":"NY"},{"key":"atypb23","first-page":"372","volume":"27","author":"Nesterov Y.","year":"1983","journal-title":"Sov. Math. Dokl."},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"Y. Nesterov,\n                      Introductory Lectures on Convex Optimization\n                      , Kluwer Academic, Norwell, MA, 2004.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"atypb25","unstructured":"Y. Nesterov,\n                      Gradient Methods for Minimizing Composite Objective Function\n                      , Technical Report 76, Center for Operations Research and Econometrics (CORE), Catholic University of Louvain, 2007."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0706-8"},{"key":"atypb27","unstructured":"J. Nocedal and S. J. Wright,\n                      Numerical Optimization\n                      , 2nd ed., Springer Ser. Oper. Res. Financ. Eng., Springer, New York, NY, 2006."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1994.6.1.147"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(64)90137-5"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1162\/08997660260028683"},{"key":"atypb31","first-page":"1249","author":"Simchowitz M.","year":"2018","journal-title":"NY"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623494274313"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"L. N. Trefethen and D. Bau, III,\n                      Numerical Linear Algebra\n                      , SIAM, Philadelphia, PA, 1997.","DOI":"10.1137\/1.9780898719574"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1080\/10556780600605129"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1137\/16M1095056"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1113898","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:20:09Z","timestamp":1787336409000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1113898"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/17M1113898"],"URL":"https:\/\/doi.org\/10.1137\/17m1113898","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}