{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T05:24:06Z","timestamp":1770960246251,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T00:00:00Z","timestamp":1756512000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T00:00:00Z","timestamp":1756512000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2023239"],"award-info":[{"award-number":["DMS-2023239"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006224","name":"Argonne National Laboratory","doi-asserted-by":"publisher","award":["8F-30039"],"award-info":[{"award-number":["8F-30039"]}],"id":[{"id":"10.13039\/100006224","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006224","name":"Argonne National Laboratory","doi-asserted-by":"publisher","award":["CCF-2224213"],"award-info":[{"award-number":["CCF-2224213"]}],"id":[{"id":"10.13039\/100006224","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-21-1-0084"],"award-info":[{"award-number":["FA9550-21-1-0084"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2023239"],"award-info":[{"award-number":["DMS-2023239"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["FA9550-21-1-0084"],"award-info":[{"award-number":["FA9550-21-1-0084"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We consider minimization of a smooth nonconvex function with inexact oracle access to gradient and Hessian (without assuming access to the function value) to achieve approximate second-order optimality. A novel feature of our method is that if an approximate direction of negative curvature is chosen as the step, we choose its sign to be positive or negative with equal probability. We allow gradients to be inexact (with a bound on their error relative to the size of the true quantity) and relax the coupling between inexactness thresholds for the first- and second-order optimality conditions. Our convergence analysis includes both an expectation bound based on martingale analysis and a high-probability bound based on concentration inequalities. We apply our algorithm to empirical risk minimization problems and obtain improved gradient sample complexity over existing works.<\/jats:p>","DOI":"10.1007\/s10957-025-02817-y","type":"journal-article","created":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T18:07:29Z","timestamp":1756577249000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Randomized Algorithm for Nonconvex Minimization With Inexact Evaluations and Complexity Guarantees"],"prefix":"10.1007","volume":"207","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-0170-1018","authenticated-orcid":false,"given":"Shuyao","family":"Li","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6815-7379","authenticated-orcid":false,"given":"Stephen J.","family":"Wright","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,30]]},"reference":[{"key":"2817_CR1","doi-asserted-by":"publisher","unstructured":"Agarwal, N., Allen-Zhu, Z., Bullins, B., Hazan, E., Ma, T.: Finding approximate local minima faster than gradient descent. In: STOC\u201917\u2014Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1195\u20131199. ACM, New York (2017). https:\/\/doi.org\/10.1145\/3055399.3055464","DOI":"10.1145\/3055399.3055464"},{"key":"2817_CR2","unstructured":"Allen-Zhu, Z.: Natasha 2: Faster non-convex optimization than sgd. In: Advances in Neural Information Processing Systems, vol.\u00a031. Curran Associates, Inc. (2018)"},{"key":"2817_CR3","unstructured":"Arjevani, Y., Carmon, Y., Duchi, J.C., Foster, D.J., Sekhari, A., Sridharan, K.: Second-order information in non-convex stochastic optimization: power and limitations. In: Proceedings of Thirty Third Conference on Learning Theory, Proceedings of Machine Learning Research, 125, 242\u2013299. PMLR (2020)"},{"key":"2817_CR4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejco.2022.100043","volume":"10","author":"S Bellavia","year":"2022","unstructured":"Bellavia, S., Gurioli, G., Morini, B., Toint, P.L.: Trust-region algorithms: probabilistic complexity and intrinsic noise with applications to subsampling techniques. EURO J. Comput. Optim. 10, 100,043 (2022)","journal-title":"EURO J. Comput. Optim."},{"issue":"2","key":"2817_CR5","doi-asserted-by":"publisher","first-page":"1489","DOI":"10.1137\/19M1291832","volume":"31","author":"AS Berahas","year":"2021","unstructured":"Berahas, A.S., Cao, L., Scheinberg, K.: Global convergence rate analysis of a generic line search algorithm with noise. SIAM J. Optim. 31(2), 1489\u20131518 (2021)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"2817_CR6","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1287\/ijoo.2022.0072","volume":"4","author":"EH Bergou","year":"2022","unstructured":"Bergou, E.H., Diouane, Y., Kunc, V., Kungurtsev, V., Royer, C.W.: A subsampling line-search method with second-order results. INFORMS J. Optim. 4(4), 403\u2013425 (2022). https:\/\/doi.org\/10.1287\/ijoo.2022.0072","journal-title":"INFORMS J. Optim."},{"issue":"2","key":"2817_CR7","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1287\/ijoo.2019.0016","volume":"1","author":"J Blanchet","year":"2019","unstructured":"Blanchet, J., Cartis, C., Menickelly, M., Scheinberg, K.: Convergence rate analysis of a stochastic trust-region method via supermartingales. INFORMS J. Optim. 1(2), 92\u2013119 (2019)","journal-title":"INFORMS J. Optim."},{"issue":"1","key":"2817_CR8","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s10107-012-0572-5","volume":"134","author":"RH Byrd","year":"2012","unstructured":"Byrd, R.H., Chin, G.M., Nocedal, J., Wu, Y.: Sample size selection in optimization methods for machine learning. Math. Program. 134(1), 127\u2013155 (2012)","journal-title":"Math. Program."},{"key":"2817_CR9","doi-asserted-by":"publisher","first-page":"1751","DOI":"10.1137\/17M1114296","volume":"28","author":"Y Carmon","year":"2018","unstructured":"Carmon, Y., Duchi, J.C., Hinder, O., Sidford, A.: Accelerated methods for non-convex optimization. SIAM J. Optim. 28, 1751\u20131772 (2018)","journal-title":"SIAM J. Optim."},{"key":"2817_CR10","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.jco.2011.06.001","volume":"28","author":"C Cartis","year":"2012","unstructured":"Cartis, C., Gould, N., Toint, P.: Complexity bounds for second-order optimality in unconstrained optimization. J. Complex. 28, 93\u2013108 (2012). https:\/\/doi.org\/10.1016\/j.jco.2011.06.001","journal-title":"J. Complex."},{"issue":"2","key":"2817_CR11","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s10107-009-0337-y","volume":"130","author":"C Cartis","year":"2011","unstructured":"Cartis, C., Gould, N.I.M., Toint, P.L.: Adaptive cubic regularisation methods for unconstrained optimization. part ii: worst-case function- and derivative-evaluation complexity. Math. Program. 130(2), 295\u2013319 (2011). https:\/\/doi.org\/10.1007\/s10107-009-0337-y","journal-title":"Math. Program."},{"issue":"2, Ser. A","key":"2817_CR12","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s10107-017-1137-4","volume":"169","author":"C Cartis","year":"2018","unstructured":"Cartis, C., Scheinberg, K.: Global convergence rate analysis of unconstrained optimization methods based on probabilistic models. Math. Program. 169(2, Ser. A), 337\u2013375 (2018). https:\/\/doi.org\/10.1007\/s10107-017-1137-4","journal-title":"Math. Program."},{"key":"2817_CR13","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/s10107-017-1141-8","volume":"169","author":"R Chen","year":"2018","unstructured":"Chen, R., Menickelly, M., Scheinberg, K.: Stochastic optimization using a trust-region method and random models. Math. Program. 169, 447\u2013487 (2018)","journal-title":"Math. Program."},{"key":"2817_CR14","doi-asserted-by":"publisher","first-page":"518","DOI":"10.1137\/19M130563X","volume":"31","author":"FE Curtis","year":"2021","unstructured":"Curtis, F.E., Robinson, D.P., Royer, C.W., Wright, S.J.: Trust-region Newton-CG with strong second-order complexity guarantees for nonconvex optimization. SIAM J. Optim. 31, 518\u2013544 (2021)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"2817_CR15","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1287\/ijoo.2018.0010","volume":"1","author":"FE Curtis","year":"2019","unstructured":"Curtis, F.E., Scheinberg, K., Shi, R.: A stochastic trust region algorithm based on careful step normalization. Informs J. Optim. 1(3), 200\u2013220 (2019)","journal-title":"Informs J. Optim."},{"key":"2817_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/9781108591034","volume-title":"Probability\u2013theory and examples, Cambridge Series in Statistical and Probabilistic Mathematics","author":"R Durrett","year":"2019","unstructured":"Durrett, R.: Probability\u2013theory and examples, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 49. Cambridge University Press, Cambridge (2019). https:\/\/doi.org\/10.1017\/9781108591034"},{"key":"2817_CR17","unstructured":"Ge, R., Huang, F., Jin, C., Yuan, Y.: Escaping from saddle points\u2014online stochastic gradient for tensor decomposition. In: Conference on Learning Theory, pp. 797\u2013842 (2015)"},{"key":"2817_CR18","unstructured":"Ge, R., Jin, C., Zheng, Y.: No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In: Proceedings of the 34th International Conference on Machine Learning, Proceedings of Machine Learning Research, 70, 1233\u20131242. PMLR (2017)"},{"issue":"3","key":"2817_CR19","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1080\/10556788.2015.1130129","volume":"31","author":"GN Grapiglia","year":"2016","unstructured":"Grapiglia, G.N., Yuan, J., Yuan, Y.: On the worst-case complexity of nonlinear stepsize control algorithms for convex unconstrained optimization. Optim. Methods Softw. 31(3), 591\u2013604 (2016)","journal-title":"Optim. Methods Softw."},{"issue":"3","key":"2817_CR20","doi-asserted-by":"publisher","first-page":"1621","DOI":"10.1137\/22M1499522","volume":"33","author":"S Gratton","year":"2023","unstructured":"Gratton, S., Jerad, S., Toint, P.L.: Convergence properties of an objective-function-free optimization regularization algorithm, including an $$\\cal{O} (\\epsilon ^{-3\/2})$$ complexity bound. SIAM J. Optim. 33(3), 1621\u20131646 (2023). https:\/\/doi.org\/10.1137\/22M1499522","journal-title":"SIAM J. Optim."},{"key":"2817_CR21","unstructured":"Jin, B., Scheinberg, K., Xie, M.: Sample complexity analysis for adaptive optimization algorithms with stochastic oracles. arXiv preprint arXiv:2303.06838 (2023)"},{"key":"2817_CR22","unstructured":"Jin, C., Ge, R., Netrapalli, P., Kakade, S.M., Jordan, M.I.: How to escape saddle points efficiently. In: Proceedings of the 34th International Conference on Machine Learning, Proceedings of Machine Learning Research, 70, 1724\u20131732. PMLR (2017)"},{"issue":"2","key":"2817_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3418526","volume":"68","author":"C Jin","year":"2021","unstructured":"Jin, C., Netrapalli, P., Ge, R., Kakade, S.M., Jordan, M.I.: On nonconvex optimization for machine learning: gradients, stochasticity, and saddle points. J. ACM 68(2), 1\u201329 (2021). https:\/\/doi.org\/10.1145\/3418526","journal-title":"J. ACM"},{"key":"2817_CR24","unstructured":"Li, S., Cheng, Y., Diakonikolas, I., Diakonikolas, J., Ge, R., Wright, S.: Robust second-order nonconvex optimization and its application to low rank matrix sensing. In: Advances in Neural Information Processing Systems, 36, 54,386\u201354,398. Curran Associates, Inc. (2023)"},{"key":"2817_CR25","unstructured":"Liu, L., Liu, X., Hsieh, C.J., Tao, D.: Stochastic optimization for nonconvex problem with inexact hessian matrix, gradient, and function. IEEE Transactions on Neural Networks and Learning Systems pp. 1\u201313 (2023)"},{"key":"2817_CR26","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s10107-006-0706-8","volume":"108","author":"Y Nesterov","year":"2006","unstructured":"Nesterov, Y., Polyak, B.T.: Cubic regularization of Newton method and its global performance. Math. Program. Ser. A. 108, 177\u2013205 (2006)","journal-title":"Math. Program. Ser. A."},{"issue":"1","key":"2817_CR27","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1137\/18M1216250","volume":"30","author":"C Paquette","year":"2020","unstructured":"Paquette, C., Scheinberg, K.: A stochastic line search method with expected complexity analysis. SIAM J. Optim. 30(1), 349\u2013376 (2020). https:\/\/doi.org\/10.1137\/18M1216250","journal-title":"SIAM J. Optim."},{"issue":"1\u20132, Ser. A","key":"2817_CR28","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s10107-019-01362-7","volume":"180","author":"CW Royer","year":"2020","unstructured":"Royer, C.W., O\u2019Neill, M., Wright, S.J.: A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization. Math. Program. 180(1\u20132, Ser. A), 451\u2013488 (2020). https:\/\/doi.org\/10.1007\/s10107-019-01362-7","journal-title":"Math. Program."},{"key":"2817_CR29","doi-asserted-by":"publisher","first-page":"1448","DOI":"10.1137\/17M1134329","volume":"28","author":"CW Royer","year":"2018","unstructured":"Royer, C.W., Wright, S.J.: Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization. SIAM J. Optim. 28, 1448\u20131477 (2018)","journal-title":"SIAM J. Optim."},{"key":"2817_CR30","doi-asserted-by":"crossref","unstructured":"Sun, J., Qu, Q., Wright, J.: A geometric analysis of phase retrieval. In: Information Theory (ISIT), 2016 IEEE International Symposium on, pp. 2379\u20132383. IEEE (2016)","DOI":"10.1109\/ISIT.2016.7541725"},{"issue":"2","key":"2817_CR31","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1109\/TIT.2016.2632162","volume":"63","author":"J Sun","year":"2017","unstructured":"Sun, J., Qu, Q., Wright, J.: Complete dictionary recovery over the sphere i: overview and the geometric picture. IEEE Trans. Inf. Theor. 63(2), 853\u2013884 (2017). https:\/\/doi.org\/10.1109\/TIT.2016.2632162","journal-title":"IEEE Trans. Inf. Theor."},{"key":"2817_CR32","unstructured":"Tripuraneni, N., Stern, M., Jin, C., Regier, J., Jordan, M.I.: Stochastic cubic regularization for fast nonconvex optimization. In: Advances in Neural Information Processing Systems, vol.\u00a031. Curran Associates, Inc. (2018)"},{"key":"2817_CR33","doi-asserted-by":"publisher","DOI":"10.1017\/9781009004282","volume-title":"Optimization for Data Analysis","author":"SJ Wright","year":"2022","unstructured":"Wright, S.J., Recht, B.: Optimization for Data Analysis. Cambridge University Press, Cambridge (2022). https:\/\/doi.org\/10.1017\/9781009004282"},{"issue":"1\u20132","key":"2817_CR34","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s10107-019-01405-z","volume":"184","author":"P Xu","year":"2020","unstructured":"Xu, P., Roosta, F., Mahoney, M.W.: Newton-type methods for non-convex optimization under inexact hessian information. Math. Program. 184(1\u20132), 35\u201370 (2020). https:\/\/doi.org\/10.1007\/s10107-019-01405-z","journal-title":"Math. Program."},{"key":"2817_CR35","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/drac043","author":"Z Yao","year":"2022","unstructured":"Yao, Z., Xu, P., Roosta, F., Wright, S.J., Mahoney, M.W.: Inexact Newton-CG algorithms with complexity guarantees. IMA J. Numer. Anal. (2022). https:\/\/doi.org\/10.1093\/imanum\/drac043","journal-title":"IMA J. Numer. Anal."},{"key":"2817_CR36","unstructured":"Zhang, Y., Qu, Q., Wright, J.: From symmetry to geometry: Tractable nonconvex problems. arXiv preprint arXiv:2007.06753 (2020)"}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-025-02817-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-025-02817-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-025-02817-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,16]],"date-time":"2025-09-16T07:44:49Z","timestamp":1758008689000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-025-02817-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,30]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["2817"],"URL":"https:\/\/doi.org\/10.1007\/s10957-025-02817-y","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"value":"0022-3239","type":"print"},{"value":"1573-2878","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,30]]},"assertion":[{"value":"2 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 August 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 August 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"66"}}