{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T16:37:25Z","timestamp":1791391045331,"version":"4.3.3"},"reference-count":71,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"name":"Australian Centre of Excellence for Mathematical and Statistical Frontiers"},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>Recently, there has been a surge of interest in designing variants of the classical Newton-CG in which the Hessian of a (strongly) convex function is replaced by suitable approximations. This is mainly motivated by large-scale finite-sum minimization problems that arise in many machine learning applications. Going beyond convexity, inexact Hessian information has also been recently considered in the context of algorithms such as trust-region or (adaptive) cubic regularization for general nonconvex problems. Here, we do that for Newton-MR, which extends the application range of the classical Newton-CG beyond convexity to invex problems. Unlike the convergence analysis of Newton-CG, which relies on spectrum preserving Hessian approximations in the sense of L\u00f6wner partial order, our work here draws from matrix perturbation theory to estimate the distance between the range spaces underlying the exact and approximate Hessian matrices. Numerical experiments demonstrate a great degree of resilience to such Hessian approximations, amounting to a highly efficient algorithm in large-scale problems.<\/jats:p>","DOI":"10.1137\/19m1302211","type":"journal-article","created":{"date-parts":[[2021,1,7]],"date-time":"2021-01-07T14:45:34Z","timestamp":1610030734000},"page":"59-90","source":"Crossref","is-referenced-by-count":13,"title":["Convergence of Newton-MR under Inexact Hessian Information"],"prefix":"10.1137","volume":"31","author":[{"given":"Yang","family":"Liu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fred","family":"Roosta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,1,7]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1039\/C7CP01108C"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/130915984"},{"key":"atypb3","first-page":"1","volume":"28","author":"Ben-Israel A.","year":"1986","journal-title":"ANZIAM J."},{"key":"atypb4","unstructured":"A. S. Berahas, R. Bollapragada, and J. Nocedal,\n                      An Investigation of Newton-Sketch and Subsampled Newton Methods\n                      , preprint,https:\/\/arxiv.org\/abs\/1705.06211, 2017."},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"D. S. Bernstein,\n                      Matrix Mathematics: Theory, Facts, and Formulas with Application to Linear Systems Theory\n                      , Princeton University Press, Princeton, NJ, 2009.","DOI":"10.1515\/9781400833344"},{"key":"atypb6","unstructured":"D. P. Bertsekas,\n                      Convex Optimization Algorithms\n                      , Athena Scientific, Belmont, MA, 2015."},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"J. Blanchet, C. Cartis, M. Menickelly, and K. Scheinberg,\n                      Convergence rate analysis of a stochastic trust region method via supermartingales\n                      , Informs J. Optim. (2019).","DOI":"10.1287\/ijoo.2019.0016"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/dry009"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe,\n                      Convex Optimization\n                      , Cambridge University Press, Cambridge, UK, 2004.","DOI":"10.1017\/CBO9780511804441"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/10079923X"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0572-5"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623493252985"},{"key":"atypb13","first-page":"385","author":"Calvetti D.","year":"2000","journal-title":"WA"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021918118380"},{"key":"atypb15","first-page":"654","author":"Carmon Y.","year":"2017","journal-title":"JMLR"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/17M1114296"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0286-5"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0337-y"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2011.06.001"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1141-8"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/100787921"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"P. Ciarlet,\n                      Linear and Nonlinear Functional Analysis with Applications\n                      , SIAM, Philadelphia, 2013.","DOI":"10.1137\/1.9781611972597"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01594934"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"A. R. Conn, N. I. M. Gould, and Ph. L. Toint,\n                      Trust Region Methods\n                      , MOS-SIAM Ser. Optim. 1, SIAM, Philadelphia, 2000.","DOI":"10.1137\/1.9780898719857"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.4134\/JKMS.2010.47.4.831"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"J. E. Dennis, Jr., and R. B. Schnabel,\n                      Numerical Methods for Unconstrained Optimization and Nonlinear Equations\n                      , Classics in Appl. Math. 16, SIAM, Philadelphia, 1996.","DOI":"10.1137\/1.9781611971200"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100263"},{"key":"atypb28","first-page":"2121","volume":"12","author":"Duchi J.","year":"2011","journal-title":"J. Mach. Learn. Res."},{"key":"atypb29","first-page":"3034","volume":"28","author":"Erdogdu M. A.","year":"2015","journal-title":"Advances in Neural Information Processing Systems"},{"key":"atypb30","doi-asserted-by":"crossref","first-page":"44","DOI":"10.24200\/squjs.vol17iss1pp44-62","volume":"17","author":"Fong D. C.-L.","year":"2012","journal-title":"Sultan Qaboos Univ. J. Sci."},{"key":"atypb31","unstructured":"C. G. Frye, N. S. Wadia, M. R. DeWeese, and K. E. Bouchard,\n                      Numerically Recovering the Critical Points of a Deep Linear Autoencoder\n                      , preprint,https:\/\/arxiv.org\/abs\/1901.10603, 2019."},{"key":"atypb32","unstructured":"G. Golub and C. Van Loan,\n                      Matrix Computations\n                      , 4th ed., Johns Hopkins Stud. Math. Sci., Johns Hopkins University Press, Baltimore, 2012."},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1145\/2950048"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/drx043"},{"key":"atypb35","first-page":"128","author":"Griewank A.","year":"1993","journal-title":"NJ"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"M. Hanke,\n                      Conjugate Gradient Type Methods for Ill-Posed Problems\n                      , Routledge, Abingdon, UK, 2017.","DOI":"10.1201\/9781315140193"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(81)90123-2"},{"key":"atypb38","unstructured":"J. H. Hubbard and B. B. Hubbard,\n                      Vector Calculus, Linear Algebra, and Differential Forms\n                      , 5th ed., Pearson, London, 2015."},{"key":"atypb39","unstructured":"D. Kingma and J. Ba,\n                      Adam: A Method for Stochastic Optimization\n                      , preprint,https:\/\/arxiv.org\/abs\/1412.6980, 2014."},{"key":"atypb40","first-page":"702","author":"Kylasa S.","year":"2019","journal-title":"SIAM"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-016-9827-z"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1090\/qam\/10666"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1137\/0111030"},{"key":"atypb44","unstructured":"S. Mei, Y. Bai, and A. Montanari,\n                      The Landscape of Empirical Risk for Non-Convex Losses\n                      , preprint,https:\/\/arxiv.org\/abs\/1607.06534, 2016."},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2009.10.009"},{"key":"atypb46","doi-asserted-by":"crossref","unstructured":"S. K. Mishra and G. Giorgi,\n                      Invexity and Optimization\n                      , Nonconvex Optim. Appl. 88, Springer, New York, 2008.","DOI":"10.1007\/978-3-540-78562-0"},{"key":"atypb47","doi-asserted-by":"crossref","unstructured":"Y. Nesterov,\n                      Introductory Lectures on Convex Optimization\n                      , Appl. Optim. 87, Springer, New York, 2004.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0706-8"},{"key":"atypb49","unstructured":"J. Nocedal and S. Wright,\n                      Numerical Optimization\n                      , Springer, New York, 2006."},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2017.11.014"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1137\/0712047"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1994.6.1.147"},{"key":"atypb53","unstructured":"M. Pilanci and M. J. Wainwright,\n                      Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence\n                      , preprint,https:\/\/arxiv.org\/abs\/1505.02250, 2015."},{"key":"atypb54","unstructured":"F. Roosta, Y. Liu, P. Xu, and M. W. Mahoney,\n                      Newton-MR: Newton's Method Without Smoothness or Convexity\n                      , preprint,https:\/\/arxiv.org\/abs\/1810.00303, 2018."},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1346-5"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1137\/130922756"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01362-7"},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1137\/17M1134329"},{"key":"atypb59","first-page":"1576","author":"Rudelson M.","year":"2010","journal-title":"NJ"},{"key":"atypb60","doi-asserted-by":"crossref","unstructured":"S. Shalev-Shwartz and S. Ben-David,\n                      Understanding Machine Learning: From Theory to Algorithms\n                      , Cambridge University Press, Cambridgs, UK, 2014.","DOI":"10.1017\/CBO9781107298019"},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.1137\/15M1042425"},{"key":"atypb62","doi-asserted-by":"publisher","DOI":"10.1137\/0905030"},{"key":"atypb63","unstructured":"G. Stewart and J. guang Sun,\n                      Matrix Perturbation Theory\n                      , Academic Press, New York, 1990."},{"key":"atypb64","first-page":"1139","author":"Sutskever I.","year":"2013","journal-title":"Proceedings of the International Conference on Machine Learning"},{"key":"atypb65","unstructured":"T. Tieleman and G. Hinton,\n                      Lecture 6.5-RMSProp: Divide the Gradient by a Running Average of Its Recent Magnitude\n                      , COURSERA: Neural Networks for Machine Learning, 4, 2012."},{"key":"atypb66","unstructured":"D. Wales,\n                      Energy Landscapes: Applications to Clusters, Biomolecules and Glasses\n                      , Cambridge University Press, Cambridge, UK, 2003."},{"key":"atypb67","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01405-z"},{"key":"atypb68","first-page":"199","author":"Xu P.","year":"2020","journal-title":"Philadelphia"},{"key":"atypb69","first-page":"3000","author":"Xu P.","year":"2016","journal-title":"Advances in Neural Information Processing Systems"},{"key":"atypb70","unstructured":"Z. Yao, P. Xu, F. Roosta, and M. W. Mahoney,\n                      Inexact Non-Convex Newton-Type Methods\n                      , preprint,https:\/\/arxiv.org\/abs\/1802.06925, 2018."},{"key":"atypb71","unstructured":"M. D. Zeiler,\n                      ADADELTA: An Adaptive Learning Rate Method\n                      , preprint,https:\/\/arxiv.org\/abs\/1212.5701, 2012."}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1302211","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:03:25Z","timestamp":1787339005000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1302211"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":71,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M1302211"],"URL":"https:\/\/doi.org\/10.1137\/19m1302211","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}