{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T18:06:23Z","timestamp":1791223583424,"version":"4.1.0"},"reference-count":51,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"name":"Stanford Graduate Fellowship"},{"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"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-19-2288"],"award-info":[{"award-number":["N00014-19-2288"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"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 Rev."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>We consider minimization of indefinite quadratics with either trust-region (norm) constraints or cubic regularization. Despite the nonconvexity of these problems we prove that, under mild assumptions, gradient descent converges to their global solutions and give a nonasymptotic rate of convergence for the cubic variant. We also consider Krylov subspace solutions and establish sharp convergence guarantees to the solutions of both trust-region and cubic-regularized problems. Our rates mirror the behavior of these methods on convex quadratics and eigenvector problems, highlighting their scalability. When we use Krylov subspace solutions to approximate the cubic-regularized Newton step, our results recover the strongest known convergence guarantees to approximate second-order stationary points of general smooth nonconvex functions.<\/jats:p>","DOI":"10.1137\/20m1321759","type":"journal-article","created":{"date-parts":[[2020,5,6]],"date-time":"2020-05-06T13:08:17Z","timestamp":1588770497000},"page":"395-436","source":"Crossref","is-referenced-by-count":23,"title":["First-Order Methods for Nonconvex Quadratic Minimization"],"prefix":"10.1137","volume":"62","author":[{"given":"Yair","family":"Carmon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John C.","family":"Duchi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,5,7]]},"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 Theory of Computing, 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","unstructured":"Y. Carmon and J. C. Duchi,\n                      Analysis of Krylov subspace solutions of regularized nonconvex quadratic problems\n                      , in Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018, pp. 10728-10738."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/17M1113898"},{"key":"atypb7","first-page":"654","author":"Carmon Y.","year":"2017","journal-title":"Dimension-free acceleration of gradient descent on non-convex functions, in Proceedings of the 34th International Conference on Machine Learning"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/17M1114296"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford,\n                      Lower bounds for finding stationary points\n                      I, Math. Program. Ser. A,https:\/\/doi.org\/10.1007\/s10107-019-01406-y.","DOI":"10.1007\/s10107-019-01406-y"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0337-y"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0286-5"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2012.06.003"},{"key":"atypb13","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. 1, SIAM, 2000,https:\/\/doi.org\/10.1137\/1.9780898719857.","DOI":"10.1137\/1.9780898719857"},{"key":"atypb14","first-page":"505","author":"Cullum J.","year":"1974","journal-title":"IEEE"},{"key":"atypb15","first-page":"797","volume":"40","author":"Ge R.","year":"2015","journal-title":"Proc. Mach. Learn. Res."},{"key":"atypb16","unstructured":"R. Ge, J. D. Lee, and T. Ma,\n                      Matrix completion has no spurious local minimum\n                      , in Proceedings of the 30th International Conference on Neural Information Processing Systems, 2016, pp. 2981-2989."},{"key":"atypb17","unstructured":"R. Ge, C. Jin, and Y. Zheng,\n                      No spurious local minima in nonconvex low rank problems: A unified geometric analysis\n                      , in Proceedings of the 34th International Conference on Machine Learning, pp. 1233-1242."},{"key":"atypb18","unstructured":"G. Golub and C. V. Loan,\n                      Matrix Computations\n                      , 2nd ed., Johns Hopkins University Press, 1989."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-587260-7.50018-2"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497322735"},{"key":"atypb21","unstructured":"A. Griewank,\n                      The Modification of Newton's Method for Unconstrained Optimization by Bounding Cubic Terms\n                      , Technical report NA\/12, 1981,https:\/\/doi.org\/10.13140\/RG.2.1.4097.2960."},{"key":"atypb22","first-page":"1025","volume":"19","author":"Hardt M.","year":"2018","journal-title":"J. Mach. Learn. Res."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0933-y"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.6028\/jres.049.044"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/16M1065197"},{"key":"atypb26","unstructured":"J. M. Kohler and A. Lucchi,\n                      Sub-sampled cubic regularization for non-convex optimization\n                      , in Proceedings of the 34th International Conference on Machine Learning, 2017, pp. 1895-1904."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/0613066"},{"key":"atypb28","first-page":"597","volume":"30","author":"Li Y.","year":"2017","journal-title":"Advances in Neural Information Processing Systems"},{"key":"atypb30","unstructured":"J. Martens and R. Grosse,\n                      Optimizing neural networks with Kronecker-factored approximate curvature\n                      , in Proceedings of the 32nd International Conference on Machine Learning, 2015, pp. 2408-2417."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/0804009"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592948"},{"key":"atypb33","unstructured":"A. Nemirovski,\n                      Efficient Methods in Convex Programming\n                      , Technion, 1994."},{"key":"atypb34","unstructured":"A. Nemirovski and D. Yudin,\n                      Problem Complexity and Method Efficiency in Optimization\n                      , Wiley, 1983."},{"key":"atypb35","first-page":"372","volume":"27","author":"Nesterov Y.","year":"1983","journal-title":"Soviet Math. Dokl."},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"Y. Nesterov,\n                      Introductory Lectures on Convex Optimization\n                      , Kluwer Academic, 2004.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0706-8"},{"key":"atypb38","unstructured":"J. Nocedal and S. J. Wright,\n                      Numerical Optimization\n                      , Springer, 2006."},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1994.6.1.147"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1137\/17M1134329"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01362-7"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1162\/08997660260028683"},{"key":"atypb43","first-page":"1249","author":"Simchowitz M.","year":"2018","journal-title":"Proceedings of the Fiftieth Annual ACM Symposium on Theory of Computing"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1137\/0720042"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-017-9365-9"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623494274313"},{"key":"atypb47","doi-asserted-by":"crossref","unstructured":"L. N. Trefethen and D. Bau III,\n                      Numerical Linear Algebra\n                      , SIAM, 1997.","DOI":"10.1137\/1.9780898719574"},{"key":"atypb48","unstructured":"N. Tripuraneni, M. Stern, C. Jin, J. Regier, and M. I. Jordan,\n                      Stochastic cubic regularization for fast nonconvex optimization\n                      , in Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018, pp. 2904-2913."},{"key":"atypb49","unstructured":"P. Tseng,\n                      On accelerated proximal gradient methods for convex-concave optimization\n                      , 2008,http:\/\/www.mit.edu\/~dimitrib\/PTseng\/papers\/apgm.pdf."},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1080\/10556780600605129"},{"key":"atypb51","doi-asserted-by":"crossref","unstructured":"P. Xu, F. Roosta, and M. W. Mahoney,\n                      Newton-type methods for non-convex optimization under inexact Hessian information\n                      , Math. Program. Ser. A,https:\/\/doi.org\/10.1007\/s10107-019-01405-z.","DOI":"10.1007\/s10107-019-01405-z"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1137\/16M1095056"}],"container-title":["SIAM Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1321759","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T14:13:53Z","timestamp":1787235233000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1321759"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/20M1321759"],"URL":"https:\/\/doi.org\/10.1137\/20m1321759","relation":{},"ISSN":["0036-1445","1095-7200"],"issn-type":[{"value":"0036-1445","type":"print"},{"value":"1095-7200","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}