{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T12:40:56Z","timestamp":1790685656523,"version":"4.1.0"},"reference-count":19,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-13-1-0138"],"award-info":[{"award-number":["FA9550-13-1-0138"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006224","name":"Argonne National Laboratory","doi-asserted-by":"publisher","award":["3F-30222"],"award-info":[{"award-number":["3F-30222"]}],"id":[{"id":"10.13039\/100006224","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1447449"],"award-info":[{"award-number":["IIS-1447449"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1628384"],"award-info":[{"award-number":["1628384"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1634597"],"award-info":[{"award-number":["1634597"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1740707"],"award-info":[{"award-number":["1740707"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1740425"],"award-info":[{"award-number":["CCF-1740425"]}],"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":[[2018,1]]},"abstract":"<jats:p>There has been much recent interest in finding unconstrained local minima of smooth functions, due in part to the prevalence of such problems in machine learning and robust statistics. A particular focus is algorithms with good complexity guarantees. Second-order Newton-type methods that make use of regularization and trust regions have been analyzed from such a perspective. More recent proposals, based chiefly on first-order methodology, have also been shown to enjoy optimal iteration complexity rates, while providing additional guarantees on computational cost. In this paper, we present an algorithm with favorable complexity properties that differs in two significant ways from other recently proposed methods. First, it is based on line searches only: Each step involves computation of a search direction, followed by a backtracking line search along that direction. Second, its analysis is rather straightforward, relying for the most part on the standard technique for demonstrating sufficient decrease in the objective from backtracking. In the latter part of the paper, we consider inexact computation of the search directions, using iterative methods in linear algebra: the conjugate gradient and Lanczos methods. We derive modified convergence and complexity results for these more practical methods.<\/jats:p>","DOI":"10.1137\/17m1134329","type":"journal-article","created":{"date-parts":[[2018,5,8]],"date-time":"2018-05-08T11:53:02Z","timestamp":1525780382000},"page":"1448-1477","source":"Crossref","is-referenced-by-count":54,"title":["Complexity Analysis of Second-Order Line-Search Algorithms for Smooth Nonconvex Optimization"],"prefix":"10.1137","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2452-2172","authenticated-orcid":true,"given":"Cl\u00e9ment W.","family":"Royer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6815-7379","authenticated-orcid":true,"given":"Stephen J.","family":"Wright","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,5,8]]},"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 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Association for Computing Machinery (ACM), New York, 2017, pp. 1195-1199.","DOI":"10.1145\/3055399.3055464"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/16M110280X"},{"key":"atypb3","unstructured":"Y. Carmon and J. C. Duchi,\n                      Gradient Descent Efficiently Finds the Cubic-Regularized Non-Convex Newton Step\n                      , preprint, arXiv:1612.00547v2, 2017."},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford,\n                      Accelerated Methods for Non-Convex Optimization\n                      , preprint, arXiv:1611.00756v2, 2017.","DOI":"10.1137\/17M1114296"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/090774100"},{"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","unstructured":"C. Cartis, N. I. M. Gould, and P. L. Toint,\n                      Optimal Newton-Type Methods for Nonconvex Optimization\n                      , Technical report naXys-17-2011, Department of Mathematics, University of Namur, Belgium, 2011."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2011.06.001"},{"key":"atypb10","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, 2000.","DOI":"10.1137\/1.9780898719857"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1026-2"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-016-1007-x"},{"key":"atypb13","unstructured":"S. Gratton, C. W. Royer, and L. N. Vicente,\n                      A Decoupled First\/Second-Order Steps Technique for Nonconvex Nonlinear Unconstrained Optimization with Improved Complexity Bounds\n                      , Technical report 17-21, Department of Mathematics, University of Coimbra, Portugal, 2017."},{"key":"atypb14","first-page":"1724","author":"Jin C.","year":"2017","journal-title":"PMLR"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/0613066"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-016-0475-8"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0706-8"},{"key":"atypb18","unstructured":"J. Nocedal and S. J. Wright,\n                      Numerical Optimization\n                      , 2nd ed., Springer Ser. Oper. Res. Financ. Eng., Springer, New York, 2006."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/0720042"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1134329","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:03:28Z","timestamp":1787339008000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1134329"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1134329"],"URL":"https:\/\/doi.org\/10.1137\/17m1134329","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}