{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T22:21:16Z","timestamp":1780698076089,"version":"3.54.1"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,9,17]],"date-time":"2022-09-17T00:00:00Z","timestamp":1663372800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,9,17]],"date-time":"2022-09-17T00:00:00Z","timestamp":1663372800000},"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":["CCF-2007668"],"award-info":[{"award-number":["CCF-2007668"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we study and prove the non-asymptotic superlinear convergence rate of the Broyden class of quasi-Newton algorithms which includes the Davidon\u2013Fletcher\u2013Powell (DFP) method and the Broyden\u2013Fletcher\u2013Goldfarb\u2013Shanno (BFGS) method. The asymptotic superlinear convergence rate of these quasi-Newton methods has been extensively studied in the literature, but their explicit finite\u2013time local convergence rate is not fully investigated. In this paper, we provide a finite\u2013time (non-asymptotic) convergence analysis for Broyden quasi-Newton algorithms under the assumptions that the objective function is strongly convex, its gradient is Lipschitz continuous, and its Hessian is Lipschitz continuous at the optimal solution. We show that in a local neighborhood of the optimal solution, the iterates generated by both DFP and BFGS converge to the optimal solution at a superlinear rate of <jats:inline-formula><jats:alternatives><jats:tex-math>$$(1\/k)^{k\/2}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mn>1<\/mml:mn>\n                      <mml:mo>\/<\/mml:mo>\n                      <mml:mi>k<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>k<\/mml:mi>\n                      <mml:mo>\/<\/mml:mo>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:mrow>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where <jats:italic>k<\/jats:italic> is the number of iterations. We also prove a similar local superlinear convergence result holds for the case that the objective function is self-concordant. Numerical experiments on several datasets confirm our explicit convergence rate bounds. Our theoretical guarantee is one of the first results that provide a non-asymptotic superlinear convergence rate for quasi-Newton methods.<\/jats:p>","DOI":"10.1007\/s10107-022-01887-4","type":"journal-article","created":{"date-parts":[[2022,9,17]],"date-time":"2022-09-17T10:02:36Z","timestamp":1663408956000},"page":"425-473","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Non-asymptotic superlinear convergence of standard quasi-Newton methods"],"prefix":"10.1007","volume":"200","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4759-2870","authenticated-orcid":false,"given":"Qiujiang","family":"Jin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aryan","family":"Mokhtari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,9,17]]},"reference":[{"key":"1887_CR1","first-page":"543","volume":"269","author":"Y Nesterov","year":"1983","unstructured":"Nesterov, Y.: A method for solving the convex programming problem with convergence rate o(1\/k$$^{}2$$). Dokl. Akad. Nauk SSSR 269, 543\u2013547 (1983)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"1887_CR2","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"Y Nesterov","year":"2013","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course, vol. 87. Springer Science & Business Media, Berlin (2013)"},{"key":"1887_CR3","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"A Nemirovsky","year":"1983","unstructured":"Nemirovsky, A., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. SIAM, New Delhi (1983)"},{"issue":"10","key":"1887_CR4","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1073\/pnas.2.10.592","volume":"2","author":"AA Bennett","year":"1916","unstructured":"Bennett, A.A.: Newton\u2019s method in general analysis. Proc. Natl. Acad. Sci. U. S. A. 2(10), 592 (1916)","journal-title":"Proc. Natl. Acad. Sci. U. S. A."},{"key":"1887_CR5","volume-title":"Iterative Solution of Nonlinear Equations in Several Variables","author":"JM Ortega","year":"1970","unstructured":"Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables, vol. 30. SIAM, New Delhi (1970)"},{"key":"1887_CR6","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719857","volume-title":"Trust Region Methods","author":"AR Conn","year":"2000","unstructured":"Conn, A.R., Gould, N.I., Toint, P.L.: Trust Region Methods. SIAM, New Delhi (2000)"},{"issue":"1","key":"1887_CR7","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. 108(1), 177\u2013205 (2006)","journal-title":"Math. Program."},{"key":"1887_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)"},{"key":"1887_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9","volume-title":"Introductory Lectures on Convex Optimization","author":"Y Nesterov","year":"2004","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization. Springer Science & Business Media, Berlin (2004)"},{"key":"1887_CR10","volume-title":"Numerical Optimization","author":"J Nocedal","year":"2006","unstructured":"Nocedal, J., Wright, S.: Numerical Optimization. Springer Science & Business Media, Berlin (2006)"},{"issue":"1\u20133","key":"1887_CR11","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/BF01594934","volume":"50","author":"AR Conn","year":"1991","unstructured":"Conn, A.R., Gould, N.I.M., Toint, P.L.: Convergence of quasi-Newton matrices generated by the symmetric rank one update. Math. Program. 50(1\u20133), 177\u2013195 (1991)","journal-title":"Math. Program."},{"issue":"92","key":"1887_CR12","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1090\/S0025-5718-1965-0198670-6","volume":"19","author":"CG Broyden","year":"1965","unstructured":"Broyden, C.G.: A class of methods for solving nonlinear simultaneous equations. Math. Comput. 19(92), 577\u2013593 (1965)","journal-title":"Math. Comput."},{"key":"1887_CR13","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1093\/imamat\/12.3.223","volume":"12","author":"CG Broyden","year":"1973","unstructured":"Broyden, C.G., Broyden, J.E.D., Jr., More, J.J.: On the local and superlinear convergence of quasi-Newton methods. IMA J. Appl. Math. 12, 223\u2013245 (1973)","journal-title":"IMA J. Appl. Math."},{"issue":"4","key":"1887_CR14","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1137\/0716047","volume":"16","author":"DM Gay","year":"1979","unstructured":"Gay, D.M.: Some convergence properties of Broyden\u2019s method. SIAM J. Numer. Anal. 16(4), 623\u2013630 (1979)","journal-title":"SIAM J. Numer. Anal."},{"key":"1887_CR15","doi-asserted-by":"crossref","unstructured":"Davidon, W.: Variable metric method for minimization. SIAM J. Optim. (1991). https:\/\/epubs.siam.org\/doi\/10.1137\/0801001","DOI":"10.1137\/0801001"},{"issue":"2","key":"1887_CR16","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1093\/comjnl\/6.2.163","volume":"6","author":"R Fletcher","year":"1963","unstructured":"Fletcher, R., Powell, M.J.: A rapidly convergent descent method for minimization. Comput. J. 6(2), 163\u2013168 (1963)","journal-title":"Comput. J."},{"issue":"110","key":"1887_CR17","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1090\/S0025-5718-1970-0279993-0","volume":"24","author":"CG Broyden","year":"1970","unstructured":"Broyden, C.G.: The convergence of single-rank quasi-Newton methods. Math. Comput. 24(110), 365\u2013382 (1970)","journal-title":"Math. Comput."},{"issue":"3","key":"1887_CR18","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1093\/comjnl\/13.3.317","volume":"13","author":"R Fletcher","year":"1970","unstructured":"Fletcher, R.: A new approach to variable metric algorithms. Comput. J. 13(3), 317\u2013322 (1970)","journal-title":"Comput. J."},{"issue":"109","key":"1887_CR19","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1090\/S0025-5718-1970-0258249-6","volume":"24","author":"D Goldfarb","year":"1970","unstructured":"Goldfarb, D.: A family of variable-metric methods derived by variational means. Math. Comput. 24(109), 23\u201326 (1970)","journal-title":"Math. Comput."},{"issue":"111","key":"1887_CR20","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1090\/S0025-5718-1970-0274029-X","volume":"24","author":"DF Shanno","year":"1970","unstructured":"Shanno, D.F.: Conditioning of quasi-Newton methods for function minimization. Math. Comput. 24(111), 647\u2013656 (1970)","journal-title":"Math. Comput."},{"issue":"151","key":"1887_CR21","doi-asserted-by":"publisher","first-page":"773","DOI":"10.1090\/S0025-5718-1980-0572855-7","volume":"35","author":"J Nocedal","year":"1980","unstructured":"Nocedal, J.: Updating quasi-Newton matrices with limited storage. Math. Comput. 35(151), 773\u2013782 (1980)","journal-title":"Math. Comput."},{"issue":"1\u20133","key":"1887_CR22","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/BF01589116","volume":"45","author":"DC Liu","year":"1989","unstructured":"Liu, D.C., Nocedal, J.: On the limited memory BFGS method for large scale optimization. Math. Program. 45(1\u20133), 503\u2013528 (1989)","journal-title":"Math. Program."},{"issue":"135","key":"1887_CR23","first-page":"523","volume":"30","author":"JJ Mor\u00e9","year":"1976","unstructured":"Mor\u00e9, J.J., Trangenstein, J.A.: On the global convergence of Broyden\u2019s method. Math. Comput. 30(135), 523\u2013540 (1976)","journal-title":"Math. Comput."},{"issue":"1","key":"1887_CR24","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1093\/imamat\/7.1.21","volume":"7","author":"M Powell","year":"1971","unstructured":"Powell, M.: On the convergence of the variable metric algorithm. IMA J. Appl. Math. 7(1), 21\u201336 (1971)","journal-title":"IMA J. Appl. Math."},{"issue":"126","key":"1887_CR25","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1090\/S0025-5718-1974-0343581-1","volume":"28","author":"JE Dennis","year":"1974","unstructured":"Dennis, J.E., Mor\u00e9, J.J.: A characterization of superlinear convergence and its application to quasi-Newton methods. Math. Comput. 28(126), 549\u2013560 (1974)","journal-title":"Math. Comput."},{"issue":"5","key":"1887_CR26","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1137\/0724077","volume":"24","author":"RH Byrd","year":"1987","unstructured":"Byrd, R.H., Nocedal, J., Yuan, Y.-X.: Global convergence of a class of quasi-Newton methods on convex problems. SIAM J. Numer. Anal. 24(5), 1171\u20131190 (1987)","journal-title":"SIAM J. Numer. Anal."},{"issue":"1","key":"1887_CR27","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1080\/10556788.2018.1510927","volume":"34","author":"W Gao","year":"2019","unstructured":"Gao, W., Goldfarb, D.: Quasi-newton methods: superlinear convergence without line searches for self-concordant functions. Opt. Methods Softw. 34(1), 194\u2013217 (2019)","journal-title":"Opt. Methods Softw."},{"issue":"3","key":"1887_CR28","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/BF01407874","volume":"39","author":"A Griewank","year":"1982","unstructured":"Griewank, A., Toint, P.L.: Local convergence analysis for partitioned quasi-Newton updates. Numer. Math. 39(3), 429\u2013448 (1982)","journal-title":"Numer. Math."},{"issue":"2","key":"1887_CR29","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF00962795","volume":"61","author":"J Dennis","year":"1989","unstructured":"Dennis, J., Martinez, H.J., Tapia, R.A.: Convergence theory for the structured BFGS secant method with an application to nonlinear least squares. J. Optim. Theory Appl. 61(2), 161\u2013178 (1989)","journal-title":"J. Optim. Theory Appl."},{"issue":"3","key":"1887_CR30","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1093\/imanum\/11.3.325","volume":"11","author":"Y-X Yuan","year":"1991","unstructured":"Yuan, Y.-X.: A modified BFGS algorithm for unconstrained optimization. IMA J. Numer. Anal. 11(3), 325\u2013332 (1991)","journal-title":"IMA J. Numer. Anal."},{"issue":"2","key":"1887_CR31","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1023\/A:1018315205474","volume":"9","author":"M Al-Baali","year":"1998","unstructured":"Al-Baali, M.: Global and superlinear convergence of a restricted class of self-scaling methods with inexact line searches, for convex functions. Comput. Optim. Appl. 9(2), 191\u2013203 (1998)","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"1887_CR32","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1137\/S0036142998335704","volume":"37","author":"D Li","year":"1999","unstructured":"Li, D., Fukushima, M.: A globally and superlinearly convergent Gauss-Newton-based BFGS method for symmetric nonlinear equations. SIAM J. Numer. Anal. 37(1), 152\u2013172 (1999)","journal-title":"SIAM J. Numer. Anal."},{"issue":"1","key":"1887_CR33","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1016\/j.cam.2006.05.018","volume":"205","author":"H Yabe","year":"2007","unstructured":"Yabe, H., Ogasawara, H., Yoshino, M.: Local and superlinear convergence of quasi-Newton methods based on modified secant conditions. J. Comput. Appl. Math. 205(1), 617\u2013632 (2007)","journal-title":"J. Comput. Appl. Math."},{"issue":"2","key":"1887_CR34","doi-asserted-by":"publisher","first-page":"1670","DOI":"10.1137\/17M1122943","volume":"28","author":"A Mokhtari","year":"2018","unstructured":"Mokhtari, A., Eisen, M., Ribeiro, A.: IQN: an incremental quasi-Newton method with local superlinear convergence rate. SIAM J. Optim. 28(2), 1670\u20131698 (2018)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1887_CR35","doi-asserted-by":"publisher","first-page":"785","DOI":"10.1137\/20M1320651","volume":"31","author":"A Rodomanov","year":"2021","unstructured":"Rodomanov, A., Nesterov, Y.: Greedy quasi-Newton methods with explicit superlinear convergence. SIAM J. Optim. 31(1), 785\u2013811 (2021)","journal-title":"SIAM J. Optim."},{"key":"1887_CR36","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s10107-021-01622-5","volume":"194","author":"A Rodomanov","year":"2022","unstructured":"Rodomanov, A., Nesterov, Y.: Rates of superlinear convergence for classical quasi-Newton methods. Math. Program. 194, 159\u2013190 (2022)","journal-title":"Math. Program."},{"issue":"3","key":"1887_CR37","doi-asserted-by":"publisher","first-page":"744","DOI":"10.1007\/s10957-020-01805-8","volume":"188","author":"A Rodomanov","year":"2021","unstructured":"Rodomanov, A., Nesterov, Y.: New results on superlinear convergence of classical quasi-Newton methods. J. Optim. Theory Appl. 188(3), 744\u2013769 (2021)","journal-title":"J. Optim. Theory Appl."},{"key":"1887_CR38","unstructured":"Nesterov, J.E.: \u201dSelf-concordant functions and polynomial-time methods in convex programming,\u201d Report, Central Economic and Mathematic Institute. USSR Acad, Sci (1989)"},{"key":"1887_CR39","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970791","volume-title":"Interior-Point Polynomial Algorithms in Convex Programming","author":"Y Nesterov","year":"1994","unstructured":"Nesterov, Y., Nemirovskii, A.: Interior-Point Polynomial Algorithms in Convex Programming. SIAM, New Delhi (1994)"},{"key":"1887_CR40","first-page":"6745","volume":"96","author":"U Alon","year":"1999","unstructured":"Alon, U., Barkai, N., Notterman, D.A., Gish, K., Ybarra, S., Mack, D., Levine, A.J.: Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays. Cell Biol. 96, 6745\u20136750 (1999)","journal-title":"Cell Biol."},{"issue":"3","key":"1887_CR41","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0168-1699(99)00046-0","volume":"24","author":"A. Jock Blackard","year":"2000","unstructured":"Blackard, A. Jock., Dean, D.J.: Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables. Comput. Electron. Agric. 24(3), 131\u2013151 (2000)","journal-title":"Comput. Electron. Agric."},{"key":"1887_CR42","first-page":"2005","volume":"17","author":"G Isabelle","year":"2003","unstructured":"Isabelle, G., Gunn, S., Ben-Hur, A., Dror, G.: Result analysis of the nips: feature selection challenge. Adv. Neural Inf. Process. Syst. 17, 2005 (2003)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"1887_CR43","unstructured":"LeCun, Y., Cortes, C., Burges, C.\u00a0J.: MNIST handwritten digit database. AT &T Labs [Online]. Available: http:\/\/yann.lecun.com\/exdb\/mnist\/, 2010"},{"key":"1887_CR44","doi-asserted-by":"publisher","DOI":"10.1145\/1961189.1961199","author":"C-C Chang","year":"2011","unstructured":"Chang, C.-C., Lin, C.-J.: Libsvm: a library for support vector machines. ACM Trans. Intell. Syst. Technol. doi (2011). https:\/\/doi.org\/10.1145\/1961189.1961199","journal-title":"ACM Trans. Intell. Syst. Technol. doi"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01887-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01887-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01887-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,18]],"date-time":"2023-05-18T23:05:42Z","timestamp":1684451142000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01887-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,17]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["1887"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01887-4","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,17]]},"assertion":[{"value":"16 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 August 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 September 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}