{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T05:45:24Z","timestamp":1776836724098,"version":"3.51.2"},"reference-count":39,"publisher":"American Mathematical Society (AMS)","issue":"341","license":[{"start":{"date-parts":[[2023,12,2]],"date-time":"2023-12-02T00:00:00Z","timestamp":1701475200000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/501100009448","name":"Universit\u00e0 degli Studi della Campania Luigi Vanvitelli","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100009448","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006601","name":"Ministero degli Affari Esteri e della Cooperazione Internazionale","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006601","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>We develop a line-search second-order algorithmic framework for minimizing finite sums. We do not make any convexity assumptions, but require the terms of the sum to be continuously differentiable and have Lipschitz-continuous gradients. The methods fitting into this framework combine line searches and suitably decaying step lengths. A key issue is a two-step sampling at each iteration, which allows us to control the error present in the line-search procedure. Stationarity of limit points is proved in the almost-sure sense, while almost-sure convergence of the sequence of approximations to the solution holds with the additional hypothesis that the functions are strongly convex. Numerical experiments, including comparisons with state-of-the art stochastic optimization methods, show the efficiency of our approach.<\/p>","DOI":"10.1090\/mcom\/3802","type":"journal-article","created":{"date-parts":[[2022,11,30]],"date-time":"2022-11-30T10:19:07Z","timestamp":1669803547000},"page":"1273-1299","source":"Crossref","is-referenced-by-count":11,"title":["LSOS: Line-search second-order stochastic optimization methods for nonconvex finite sums"],"prefix":"10.1090","volume":"92","author":[{"given":"Daniela","family":"di Serafino","sequence":"first","affiliation":[]},{"given":"Nata\u0161a","family":"Kreji\u0107","sequence":"additional","affiliation":[]},{"given":"Nata\u0161a","family":"Krklec Jerinki\u0107","sequence":"additional","affiliation":[]},{"given":"Marco","family":"Viola","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2022,12,2]]},"reference":[{"issue":"1","key":"1","doi-asserted-by":"publisher","first-page":"764","DOI":"10.1093\/imanum\/drz076","article-title":"Adaptive cubic regularization methods with dynamic inexact Hessian information and applications to finite-sum minimization","volume":"41","author":"Bellavia, Stefania","year":"2021","journal-title":"IMA J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0272-4979","issn-type":"print"},{"issue":"4","key":"2","doi-asserted-by":"publisher","first-page":"2309","DOI":"10.1093\/imanum\/drz027","article-title":"Subsampled inexact Newton methods for minimizing large sums of convex functions","volume":"40","author":"Bellavia, Stefania","year":"2020","journal-title":"IMA J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0272-4979","issn-type":"print"},{"issue":"2","key":"3","doi-asserted-by":"publisher","first-page":"1489","DOI":"10.1137\/19M1291832","article-title":"Global convergence rate analysis of a generic line search algorithm with noise","volume":"31","author":"Berahas, A. S.","year":"2021","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"1","key":"4","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1080\/10556788.2019.1658107","article-title":"A robust multi-batch L-BFGS method for machine learning","volume":"35","author":"Berahas, Albert S.","year":"2020","journal-title":"Optim. Methods Softw.","ISSN":"https:\/\/id.crossref.org\/issn\/1055-6788","issn-type":"print"},{"key":"5","series-title":"Athena Scientific Optimization and Computation Series","isbn-type":"print","volume-title":"Nonlinear programming","author":"Bertsekas, Dimitri P.","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/1886529000","edition":"2"},{"issue":"2","key":"6","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1093\/imanum\/dry009","article-title":"Exact and inexact subsampled Newton methods for optimization","volume":"39","author":"Bollapragada, Raghu","year":"2019","journal-title":"IMA J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0272-4979","issn-type":"print"},{"issue":"2","key":"7","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1137\/16M1080173","article-title":"Optimization methods for large-scale machine learning","volume":"60","author":"Bottou, L\u00e9on","year":"2018","journal-title":"SIAM Rev.","ISSN":"https:\/\/id.crossref.org\/issn\/1095-7200","issn-type":"print"},{"issue":"2","key":"8","doi-asserted-by":"publisher","first-page":"1008","DOI":"10.1137\/140954362","article-title":"A stochastic quasi-Newton method for large-scale optimization","volume":"26","author":"Byrd, R. H.","year":"2016","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"3","key":"9","doi-asserted-by":"publisher","first-page":"977","DOI":"10.1137\/10079923X","article-title":"On the use of stochastic Hessian information in optimization methods for machine learning","volume":"21","author":"Byrd, Richard H.","year":"2011","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"1","key":"10","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s10107-012-0572-5","article-title":"Sample size selection in optimization methods for machine learning","volume":"134","author":"Byrd, Richard H.","year":"2012","journal-title":"Math. Program.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"issue":"11","key":"11","doi-asserted-by":"publisher","first-page":"4776","DOI":"10.1109\/tnnls.2019.2957843","article-title":"A stochastic quasi-Newton method for large-scale nonconvex optimization with applications","volume":"31","author":"Chen, Huiming","year":"2020","journal-title":"IEEE Trans. Neural Netw. Learn. Syst.","ISSN":"https:\/\/id.crossref.org\/issn\/2162-237X","issn-type":"print"},{"issue":"3","key":"12","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1080\/10556788.2020.1852403","article-title":"A fully stochastic second-order trust region method","volume":"37","author":"Curtis, Frank E.","year":"2022","journal-title":"Optim. Methods Softw.","ISSN":"https:\/\/id.crossref.org\/issn\/1055-6788","issn-type":"print"},{"key":"13","unstructured":"A. Defazio, F. Bach, and S. Lacoste-Julien, SAGA: a fast incremental gradient method with support for non-strongly convex composite objectives, Advances in Neural Information Processing Systems 27, Curran Associates, Inc., 2014, pp. 1646\u20131654."},{"key":"14","doi-asserted-by":"crossref","unstructured":"D. di Serafino, G. Toraldo, and M. Viola, A gradient-based globalization strategy for the Newton method, Numerical Computations: Theory and Algorithms (Cham), Lecture Notes in Computer Science, vol. 11973, Springer International Publishing, 2020, pp. 177\u2013185.","DOI":"10.1007\/978-3-030-39081-5_16"},{"key":"15","doi-asserted-by":"publisher","first-page":"Paper No. 125612, 14","DOI":"10.1016\/j.amc.2020.125612","article-title":"Using gradient directions to get global convergence of Newton-type methods","volume":"409","author":"di Serafino, Daniela","year":"2021","journal-title":"Appl. Math. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0096-3003","issn-type":"print"},{"key":"16","series-title":"Adaptive Computation and Machine Learning","isbn-type":"print","volume-title":"Deep learning","author":"Goodfellow, Ian","year":"2016","ISBN":"https:\/\/id.crossref.org\/isbn\/9780262035613"},{"key":"17","unstructured":"R. M. Gower, D. Goldfarb, and P. Richt\u00e1rik, Stochastic block BFGS: squeezing more curvature out of data, Proceedings of the 33rd International Conference on International Conference on Machine Learning, vol. 48, 2016, pp. 1869\u20131878, JMLR.org."},{"issue":"1","key":"18","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/s10107-020-01506-0","article-title":"Stochastic quasi-gradient methods: variance reduction via Jacobian sketching","volume":"188","author":"Gower, Robert M.","year":"2021","journal-title":"Math. Program.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"key":"19","unstructured":"S. Horv\u00e1th and P. Richtarik, Nonconvex variance reduced optimization with arbitrary sampling, Proceedings of the 36th International Conference on Machine Learning, Proceedings of Machine Learning Research, vol. 97, PMLR, June 9\u201315, 2019, pp. 2781\u20132789."},{"issue":"1","key":"20","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1137\/17M1144799","article-title":"Variance-based extragradient methods with line search for stochastic variational inequalities","volume":"29","author":"Iusem, Alfredo N.","year":"2019","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"key":"21","unstructured":"M. Jahani, M. Nazari, R. Tappenden, A. Berahas, and M. Tak\u00e1\u010d, SONIA: a symmetric blockwise truncated optimization algorithm, Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, vol. 130, PMLR, April 13\u201315, 2021, pp. 487\u2013495."},{"key":"22","unstructured":"R. Johnson and T. Zhang, Accelerating stochastic gradient descent using predictive variance reduction, Advances in Neural Information Processing Systems 26, Curran Associates, Inc., 2013, pp. 315\u2013323."},{"key":"23","series-title":"Universitext","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5361-0","volume-title":"Probability theory","author":"Klenke, Achim","year":"2014","ISBN":"https:\/\/id.crossref.org\/isbn\/9781447153603"},{"issue":"6","key":"24","doi-asserted-by":"publisher","first-page":"1164","DOI":"10.1080\/10556788.2015.1025403","article-title":"Descent direction method with line search for unconstrained optimization in noisy environment","volume":"30","author":"Kreji\u0107, Nata\u0161a","year":"2015","journal-title":"Optim. Methods Softw.","ISSN":"https:\/\/id.crossref.org\/issn\/1055-6788","issn-type":"print"},{"issue":"2","key":"25","doi-asserted-by":"publisher","first-page":"1670","DOI":"10.1137\/17M1122943","article-title":"IQN: an incremental quasi-Newton method with local superlinear convergence rate","volume":"28","author":"Mokhtari, Aryan","year":"2018","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"23","key":"26","doi-asserted-by":"publisher","first-page":"6089","DOI":"10.1109\/TSP.2014.2357775","article-title":"RES: regularized stochastic BFGS algorithm","volume":"62","author":"Mokhtari, Aryan","year":"2014","journal-title":"IEEE Trans. Signal Process.","ISSN":"https:\/\/id.crossref.org\/issn\/1053-587X","issn-type":"print"},{"key":"27","first-page":"3151","article-title":"Global convergence of online limited memory BFGS","volume":"16","author":"Mokhtari, Aryan","year":"2015","journal-title":"J. Mach. Learn. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/1532-4435","issn-type":"print"},{"key":"28","unstructured":"P. Moritz, R. Nishihara, and M. Jordan, A linearly-convergent stochastic L-BFGS algorithm, Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (Cadiz, Spain), Proceedings of Machine Learning Research, vol. 51, PMLR, May 9\u201311, 2016, pp. 249\u2013258."},{"issue":"1","key":"29","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1137\/18M1216250","article-title":"A stochastic line search method with expected complexity analysis","volume":"30","author":"Paquette, Courtney","year":"2020","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"3","key":"30","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1007\/s10957-019-01624-6","article-title":"Combining stochastic adaptive cubic regularization with negative curvature for nonconvex optimization","volume":"184","author":"Park, Seonho","year":"2020","journal-title":"J. Optim. Theory Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-3239","issn-type":"print"},{"key":"31","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1214\/aoms\/1177729586","article-title":"A stochastic approximation method","volume":"22","author":"Robbins, Herbert","year":"1951","journal-title":"Ann. Math. Statistics","ISSN":"https:\/\/id.crossref.org\/issn\/0003-4851","issn-type":"print"},{"key":"32","first-page":"233","article-title":"A convergence theorem for non negative almost supermartingales and some applications","author":"Robbins, H.","year":"1971"},{"issue":"1","key":"33","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1214\/aos\/1176346589","article-title":"A Newton-Raphson version of the multivariate Robbins-Monro procedure","volume":"13","author":"Ruppert, David","year":"1985","journal-title":"Ann. Statist.","ISSN":"https:\/\/id.crossref.org\/issn\/0090-5364","issn-type":"print"},{"key":"34","doi-asserted-by":"crossref","unstructured":"J. C. Spall, A second order stochastic approximation algorithm using only function measurements, Proceedings of 1994 33rd IEEE Conference on Decision and Control, vol. 3, 1994, pp. 2472\u20132477.","DOI":"10.1109\/CDC.1994.411511"},{"key":"35","doi-asserted-by":"crossref","unstructured":"J. C. Spall, Stochastic version of second-order (Newton-Raphson) optimization using only function measurements, Proceedings of the 27th Conference on Winter Simulation (USA), WSC \u201995, IEEE Computer Society, 1995, pp. 347\u2013352.","DOI":"10.1145\/224401.224633"},{"key":"36","doi-asserted-by":"crossref","unstructured":"J. C. Spall, Accelerated second-order stochastic optimization using only function measurements, Proceedings of the 36th IEEE Conference on Decision and Control, vol. 2, 1997, pp. 1417\u20131424.","DOI":"10.1109\/CDC.1997.657661"},{"issue":"2","key":"37","doi-asserted-by":"publisher","first-page":"927","DOI":"10.1137\/15M1053141","article-title":"Stochastic quasi-Newton methods for nonconvex stochastic optimization","volume":"27","author":"Wang, Xiao","year":"2017","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"5","key":"38","doi-asserted-by":"publisher","first-page":"922","DOI":"10.1080\/10556788.2018.1471141","article-title":"Stochastic proximal quasi-Newton methods for non-convex composite optimization","volume":"34","author":"Wang, Xiaoyu","year":"2019","journal-title":"Optim. Methods Softw.","ISSN":"https:\/\/id.crossref.org\/issn\/1055-6788","issn-type":"print"},{"key":"39","doi-asserted-by":"crossref","unstructured":"P. Xu, F. Roosta, and M. W. Mahoney, Second-order optimization for non-convex machine learning: an empirical study, Proceedings of the 2020 SIAM International Conference on Data Mining (SDM), 2020, pp. 199\u2013207.","DOI":"10.1137\/1.9781611976236.23"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2023-92-341\/S0025-5718-2022-03802-3\/mcom3802_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/www.ams.org\/mcom\/2023-92-341\/S0025-5718-2022-03802-3\/S0025-5718-2022-03802-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T04:54:28Z","timestamp":1776833668000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2023-92-341\/S0025-5718-2022-03802-3\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,2]]},"references-count":39,"journal-issue":{"issue":"341","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["S0025-5718-2022-03802-3"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3802","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2022,12,2]]}}}