{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T09:10:31Z","timestamp":1778231431072,"version":"3.51.4"},"reference-count":34,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematics of OR"],"published-print":{"date-parts":[[2026,5]]},"abstract":"<jats:p>In this paper, we consider a nonconvex unconstrained optimization problem minimizing a twice differentiable objective function with H\u00f6lder continuous Hessian. Specifically, we first propose a Newton-conjugate gradient (Newton-CG) method for finding an approximate first- and second-order stationary point of this problem, assuming the associated H\u00f6lder parameters are explicitly known. Then, we develop a parameter-free Newton-CG method without requiring any prior knowledge of these parameters. To the best of our knowledge, this method is the first parameter-free second-order method achieving the best-known iteration and operation complexity for finding an approximate first- and second-order stationary point of this problem. Finally, we present preliminary numerical results to demonstrate the superior practical performance of our parameter-free Newton-CG method over a well-known regularized Newton method.<\/jats:p>\n                  <jats:p>Funding: C. He was partially financially supported by the Wallenberg AI, Autonomous Systems and Software Program funded by the Knut and Alice Wallenberg Foundation. H. Huang was partially financially supported by the National Science Foundation [Award IIS-2347592]. Z. Lu was partially financially supported by the National Science Foundation [Award IIS-2211491], the Office of Naval Research [Award N00014-24-1-2702], and the Air Force Office of Scientific Research [Award FA9550-24-1-0343].<\/jats:p>","DOI":"10.1287\/moor.2023.0356","type":"journal-article","created":{"date-parts":[[2025,5,19]],"date-time":"2025-05-19T11:41:30Z","timestamp":1747654890000},"page":"1284-1311","source":"Crossref","is-referenced-by-count":0,"title":["Newton-CG Methods for Nonconvex Unconstrained Optimization with H\u00f6lder Continuous Hessian"],"prefix":"10.1287","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2402-3437","authenticated-orcid":false,"given":"Chuan","family":"He","sequence":"first","affiliation":[{"name":"Department of Mathematics, Link\u00f6ping University, SE-581 83 Linkping, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3483-8333","authenticated-orcid":false,"given":"Heng","family":"Huang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Maryland, College Park, Maryland 20742"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3277-7853","authenticated-orcid":false,"given":"Zhaosong","family":"Lu","sequence":"additional","affiliation":[{"name":"Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"crossref","unstructured":"Agarwal N, Allen-Zhu Z, Bullins B, Hazan E, Ma T (2017) Finding approximate local minima faster than gradient descent.\n                      STOC 2017 Proc. 49th Annu. ACM SIGACT Sympos. Theory Comput.\n                      (Association for Computing Machinery, New York), 1195\u20131199.","DOI":"10.1145\/3055399.3055464"},{"key":"B2","unstructured":"Allen-Zhu Z, Li Y (2018) Neon2: Finding local minima via first-order oracles.\n                      Adv. Neural Inform. Processing Systems\n                      , vol. 31 (ACM, New York), 3720\u20133730."},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1080\/00401706.1974.10489171"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1137\/16M110280X"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1137\/080738222"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1137\/17M1113898"},{"key":"B7","unstructured":"Carmon Y, Duchi JC, Hinder O, Sidford A (2017) \u201cConvex until proven guilty\u201d: Dimension-free acceleration of gradient descent on non-convex functions.\n                      Internat. Conf. Machine Learn.\n                      (PMLR, New York), 654\u2013663."},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1137\/17M1114296"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01406-y"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0286-5"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0337-y"},{"key":"B12","unstructured":"Cartis C, Gould NI, Toint PL (2011) Optimal Newton-type methods for nonconvex smooth optimization problems. Preprint, submitted June 22, https:\/\/optimization-online.org\/2011\/06\/3070\/."},{"key":"B13","first-page":"3711","volume-title":"Proc. Internat. Congress Mathematicians Rio de Janeiro 2018","author":"Cartis C","year":"2018"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1137\/16M1106316"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1137\/17M1144854"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1026-2"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/dry022"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1137\/19M130563X"},{"key":"B19","unstructured":"Dvurechensky P (2017) Gradient method with inexact oracle for composite non-convex optimization. Preprint, submitted March 27, https:\/\/arxiv.org\/abs\/1703.09180."},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1137\/16M1087801"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1137\/22M1489824"},{"key":"B22","first-page":"1","volume":"24","author":"Ito M","year":"2023","journal-title":"J. Machine Learn. Res."},{"key":"B23","unstructured":"Jin C, Netrapalli P, Jordan MI (2018) Accelerated gradient descent escapes saddle points faster than gradient descent.\n                      Conf. Learn. Theory\n                      (PMLR, New York), 1042\u20131085."},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1137\/0613066"},{"key":"B25","unstructured":"Li H, Lin Z (2022) Restarted nonconvex accelerated gradient descent: No more polylogarithmic factor in the O(\u03f5\u22127\/4) complexity.\n                      Internat. Conf. Machine Learn.\n                      (PMLR, New York), 12901\u201312916."},{"key":"B26","unstructured":"Li B, Tang S, Yu H (2019) Better approximations of high dimensional smooth functions by deep neural networks with rectified power units. Preprint, submitted November 3, https:\/\/arxiv.org\/abs\/1903.05858."},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-016-0475-8"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1137\/22M1540934"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0790-0"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0706-8"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1137\/17M1134329"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01362-7"},{"key":"B33","unstructured":"Xu Y, Jin R, Yang T (2017) NEON+: Accelerated gradient methods for extracting negative curvature for non-convex optimization. Preprint, submitted December 4, https:\/\/arxiv.org\/abs\/1712.01033v1."},{"key":"B34","unstructured":"Zhang C, Jiang R (2023) Riemannian adaptive regularized Newton methods with H\u00f6lder continuous Hessians. Preprint, submitted September 8, https:\/\/arxiv.org\/abs\/2309.04052v1."}],"container-title":["Mathematics of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/moor.2023.0356","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T08:24:23Z","timestamp":1778228663000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/moor.2023.0356"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["10.1287\/moor.2023.0356"],"URL":"https:\/\/doi.org\/10.1287\/moor.2023.0356","relation":{},"ISSN":["0364-765X","1526-5471"],"issn-type":[{"value":"0364-765X","type":"print"},{"value":"1526-5471","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5]]}}}