{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T13:29:11Z","timestamp":1790774951715,"version":"4.1.0"},"reference-count":44,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"name":"PACCAR INC 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"}]},{"DOI":"10.13039\/100005492","name":"Stanford University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005492","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004362","name":"Toyota USA","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004362","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We present an accelerated gradient method for nonconvex optimization problems with Lipschitz continuous first and second derivatives. In a time $O(\\epsilon^{-7\/4} \\log(1\/ \\epsilon) )$, the method finds an $\\epsilon$-stationary point, meaning a point $x$ such that $\\|\\nabla f(x)\\| \\le \\epsilon$. The method improves upon the $O(\\epsilon^{-2} )$ complexity of gradient descent and provides the additional second-order guarantee that $\\lambda_{\\min}(\\nabla^2 f(x)) \\gtrsim -\\epsilon^{1\/2}$ for the computed $x$. Furthermore, our method is Hessian free, i.e., it only requires gradient computations, and is therefore suitable for large-scale applications.<\/jats:p>","DOI":"10.1137\/17m1114296","type":"journal-article","created":{"date-parts":[[2018,6,14]],"date-time":"2018-06-14T12:29:58Z","timestamp":1528979398000},"page":"1751-1772","source":"Crossref","is-referenced-by-count":125,"title":["Accelerated Methods for NonConvex Optimization"],"prefix":"10.1137","volume":"28","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"}]},{"given":"Oliver","family":"Hinder","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aaron","family":"Sidford","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,6,14]]},"reference":[{"key":"atypb1","unstructured":"R. J. Adler and J. E. Taylor,\n                      Random Fields and Geometry\n                      , Springer Monogr. Math., Springer, New York, 2007."},{"key":"atypb2","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                      , preprint, arXiv:1611.01146, 2016.","DOI":"10.1145\/3055399.3055464"},{"key":"atypb3","unstructured":"Z. Allen-Zhu and E. Hazan,\n                      Variance Reduction for Faster Non-Convex Optimization\n                      , preprint, arXiv:1603.05643, 2016."},{"key":"atypb4","unstructured":"Z. Allen-Zhu and L. Orecchia,\n                      Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent\n                      , preprint, arXiv:1407.1537, 2014."},{"key":"atypb5","unstructured":"A. Anandkumar and R. Ge,\n                      Efficient Approaches for Escaping Higher Order Saddle Points in Non-Convex Optimization\n                      , preprint, arXiv:1602.05908, 2016."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-014-9672-x"},{"key":"atypb7","unstructured":"E. G. Birgin, J. L. Gardenghi, J. M. Marti\u0300nez, S. A. Santos, and Ph. L. Toint,\n                      Worst-Case Evaluation Complexity for Unconstrained Nonlinear Optimization Using High-Order Regularized Models\n                      , Technical report, naXys-05-2015, University of Namur, Namur, 2015."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-09-05048-X"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe,\n                      Convex Optimization\n                      , Cambridge University Press, Cambridge, 2004.","DOI":"10.1017\/CBO9780511804441"},{"key":"atypb10","unstructured":"S. Bubeck, Y. T. Lee, and M. Singh,\n                      A Geometric Alternative to Nesterov's Accelerated Gradient Descent\n                      , preprint, arXiv:1506.08187, 2015."},{"key":"atypb11","unstructured":"Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford,\n                      Accelerated Methods for Non-Convex Optimization\n                      , preprint, arXiv:1611.00756 [math.OC], 2016."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0286-5"},{"key":"atypb13","first-page":"1646","author":"Defazio A.","year":"2014","journal-title":"NY"},{"key":"atypb14","first-page":"2540","volume":"37","author":"Frostig R.","year":"2015","journal-title":"Proc. Mach. Learn. Res."},{"key":"atypb15","unstructured":"D. Garber, E. Hazan, C. Jin, S. M. Kakade, C. Musco, P. Netrapalli, and A. Sidford,\n                      Faster Eigenvector Computation via Shift-and-Invert Preconditioning\n                      , preprint, arXiv:1605.08754, 2016."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0470-2"},{"key":"atypb17","first-page":"797","volume":"40","author":"Ge R.","year":"2015","journal-title":"Proc. Mach. Learn. Res."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/120880811"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0871-8"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0933-y"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/16M1065197"},{"key":"atypb22","first-page":"315","author":"Johnson R.","year":"2013","journal-title":"NY"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/0613066"},{"key":"atypb24","first-page":"1246","volume":"49","author":"Lee J. D.","year":"2016","journal-title":"Proc. Mach. Learn. Res."},{"key":"atypb25","first-page":"379","author":"Li H.","year":"2015","journal-title":"NY"},{"key":"atypb26","first-page":"3384","author":"Lin H.","year":"2015","journal-title":"NY"},{"key":"atypb27","first-page":"559","volume":"16","author":"Loh P.-L.","year":"2015","journal-title":"J. Mach. Learn. Res."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592948"},{"key":"atypb29","unstructured":"A. Nemirovski and D. Yudin,\n                      Problem Complexity and Method Efficiency in Optimization\n                      , Wiley Ser. Discrete Math. Optim., Wiley, Hoboken, NJ, 1983."},{"key":"atypb30","first-page":"372","volume":"27","author":"Nesterov Y.","year":"1983","journal-title":"Soviet Math. Dokl."},{"key":"atypb31","first-page":"405","author":"Nesterov Y.","year":"2000","journal-title":"New York"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"Y. Nesterov,\n                      Introductory Lectures on Convex Optimization: A Basic Course\n                      , Kluwer Academic Publishers, Boston, MA, 2004.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"atypb33","first-page":"10","volume":"88","author":"Nesterov Y.","year":"2012","journal-title":"Optima"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0706-8"},{"key":"atypb35","first-page":"1141","author":"Orecchia L.","year":"2012","journal-title":"New York"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1561\/2400000003"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1994.6.1.147"},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"S. J. Reddi, A. Hefny, S. Sra, B. Po\u0301czo\u0301s, and A. Smola,\n                      Stochastic Variance Reduction for Nonconvex Optimization\n                      , preprint, arXiv:1603.06160, 2016.","DOI":"10.1109\/ALLERTON.2016.7852377"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"R. T. Rockafellar and R. J. B. Wets,\n                      Variational Analysis\n                      , Grundlehren Math. Wiss. 317, Springer, New York, 1998.","DOI":"10.1007\/978-3-642-02431-3"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1162\/08997660260028683"},{"key":"atypb41","first-page":"64","volume":"32","author":"Shalev-Shwartz S.","year":"2014","journal-title":"Proc. Mach. Learn. Res."},{"key":"atypb42","unstructured":"J. Sun, Q. Qu, and J. Wright,\n                      When are Nonconvex Problems Not Scary?\n                      , preprint, arXiv:1510.06096 [math.OC], 2015."},{"key":"atypb43","doi-asserted-by":"crossref","unstructured":"J. Sun, Q. Qu, and J. Wright,\n                      A geometric analysis of phase retrieval\n                      , J. Found. Comput. Math. (2017),https:\/\/doi.org\/10.1007\/s10208-017-9365-9.","DOI":"10.1007\/s10208-017-9365-9"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581726"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1114296","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:03:54Z","timestamp":1787339034000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1114296"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1114296"],"URL":"https:\/\/doi.org\/10.1137\/17m1114296","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}