{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T11:43:56Z","timestamp":1768995836233,"version":"3.49.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,2,8]],"date-time":"2021-02-08T00:00:00Z","timestamp":1612742400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,2,8]],"date-time":"2021-02-08T00:00:00Z","timestamp":1612742400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,7]]},"abstract":"Abstract<\/jats:title>We study the local convergence of classical quasi-Newton methods for nonlinear optimization. Although it was well established a long time ago that asymptotically these methods converge superlinearly, the corresponding rates of convergence still remain unknown. In this paper, we address this problem. We obtain first explicit non-asymptotic rates of superlinear convergence for the standard quasi-Newton methods, which are based on the updating formulas from the convex Broyden class. In particular, for the well-known DFP and BFGS methods, we obtain the rates of the form $$(\\frac{n L^2}{\\mu ^2 k})^{k\/2}$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n \n \n n<\/mml:mi>\n \n L<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:mrow>\n \n \n \u03bc<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n )<\/mml:mo>\n <\/mml:mrow>\n \n k<\/mml:mi>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$(\\frac{n L}{\\mu k})^{k\/2}$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n \n \n nL<\/mml:mi>\n <\/mml:mrow>\n \n \u03bc<\/mml:mi>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n )<\/mml:mo>\n <\/mml:mrow>\n \n k<\/mml:mi>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> respectively, where k<\/jats:italic> is the iteration counter, n<\/jats:italic> is the dimension of the problem, $$\\mu $$<\/jats:tex-math>\n \u03bc<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the strong convexity parameter, and L<\/jats:italic> is the Lipschitz constant of the gradient.\n<\/jats:p>","DOI":"10.1007\/s10107-021-01622-5","type":"journal-article","created":{"date-parts":[[2021,2,9]],"date-time":"2021-02-09T13:40:00Z","timestamp":1612878000000},"page":"159-190","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Rates of superlinear convergence for classical quasi-Newton methods"],"prefix":"10.1007","volume":"194","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9656-8554","authenticated-orcid":false,"given":"Anton","family":"Rodomanov","sequence":"first","affiliation":[]},{"given":"Yurii","family":"Nesterov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,2,8]]},"reference":[{"key":"1622_CR1","doi-asserted-by":"crossref","unstructured":"Davidon, W.: Variable metric method for minimization. Argonne Natl. Lab. Res. Dev. Rep. 5990, (1959)","DOI":"10.2172\/4252678"},{"issue":"2","key":"1622_CR2","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.: A rapidly convergent descent method for minimization. Comput. J. 6(2), 163\u2013168 (1963)","journal-title":"Comput. J."},{"issue":"1","key":"1622_CR3","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1093\/imamat\/6.1.76","volume":"6","author":"C Broyden","year":"1970","unstructured":"Broyden, C.: The convergence of a class of double-rank minimization algorithms: 1. General considerations. IMA J. Appl. Math. 6(1), 76\u201390 (1970)","journal-title":"IMA J. Appl. Math."},{"issue":"3","key":"1622_CR4","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1093\/imamat\/6.3.222","volume":"6","author":"C Broyden","year":"1970","unstructured":"Broyden, C.: The convergence of a class of double-rank minimization algorithms: 2. The new algorithm. IMA J. Appl. Math. 6(3), 222\u2013231 (1970)","journal-title":"IMA J. Appl. Math."},{"issue":"3","key":"1622_CR5","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":"1622_CR6","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":"1622_CR7","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1090\/S0025-5718-1970-0274029-X","volume":"24","author":"D Shanno","year":"1970","unstructured":"Shanno, D.: Conditioning of quasi-Newton methods for function minimization. Math. Comput. 24(111), 647\u2013656 (1970)","journal-title":"Math. Comput."},{"issue":"1","key":"1622_CR8","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1137\/1019005","volume":"19","author":"J Dennis","year":"1977","unstructured":"Dennis, J., Mor\u00e9, J.: Quasi-Newton methods, motivation and theory. SIAM Rev. 19(1), 46\u201389 (1977)","journal-title":"SIAM Rev."},{"key":"1622_CR9","volume-title":"Numerical Optimization","author":"J Nocedal","year":"2006","unstructured":"Nocedal, J., Wright, S.: Numerical Optimization. Springer, Berlin (2006)"},{"issue":"1\u20132","key":"1622_CR10","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/s10107-012-0514-2","volume":"141","author":"A Lewis","year":"2013","unstructured":"Lewis, A., Overton, M.: Nonsmooth optimization via quasi-Newton methods. Math. Program. 141(1\u20132), 135\u2013163 (2013)","journal-title":"Math. Program."},{"key":"1622_CR11","unstructured":"Gower, R., Goldfarb, D., Richt\u00e1rik, P.: Stochastic block BFGS: squeezing more curvature out of data. In: International Conference on Machnie Learning, pp. 1869\u20131878 (2016)"},{"issue":"4","key":"1622_CR12","doi-asserted-by":"publisher","first-page":"1380","DOI":"10.1137\/16M1062053","volume":"38","author":"R Gower","year":"2017","unstructured":"Gower, R., Richt\u00e1rik, P.: Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms. SIAM J. Matrix Anal. Appl. 38(4), 1380\u20131409 (2017)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1622_CR13","unstructured":"Kovalev, D., Gower, R., Richt\u00e1rik, P., Rogozin, A.: Fast linear convergence of randomized BFGS. (2020). arXiv:2002.11337"},{"issue":"1","key":"1622_CR14","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":"1","key":"1622_CR15","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/BF01584554","volume":"2","author":"L Dixon","year":"1972","unstructured":"Dixon, L.: Quasi-Newton algorithms generate identical points. Math. Program. 2(1), 383\u2013387 (1972)","journal-title":"Math. Program."},{"issue":"1","key":"1622_CR16","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF01585007","volume":"3","author":"L Dixon","year":"1972","unstructured":"Dixon, L.: Quasi Newton techniques generate identical points II: the proofs of four new theorems. Math. Program. 3(1), 345\u2013358 (1972)","journal-title":"Math. Program."},{"issue":"99","key":"1622_CR17","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1090\/S0025-5718-1967-0224273-2","volume":"21","author":"C Broyden","year":"1967","unstructured":"Broyden, C.: Quasi-Newton methods and their application to function minimization. Math. Comput. 21(99), 368\u2013381 (1967)","journal-title":"Math. Comput."},{"issue":"3","key":"1622_CR18","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1093\/imamat\/12.3.223","volume":"12","author":"C Broyden","year":"1973","unstructured":"Broyden, C., Dennis, J., Mor\u00e9, J.: On the local and superlinear convergence of quasi-Newton methods. IMA J. Appl. Math. 12(3), 223\u2013245 (1973)","journal-title":"IMA J. Appl. Math."},{"issue":"126","key":"1622_CR19","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1090\/S0025-5718-1974-0343581-1","volume":"28","author":"J Dennis","year":"1974","unstructured":"Dennis, J., Mor\u00e9, 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":"1","key":"1622_CR20","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/BF01589345","volume":"20","author":"A Stachurski","year":"1981","unstructured":"Stachurski, A.: Superlinear convergence of Broyden\u2019s bounded $$\\theta $$-class of methods. Math. Program. 20(1), 196\u2013212 (1981)","journal-title":"Math. Program."},{"issue":"3","key":"1622_CR21","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/BF01407874","volume":"39","author":"A Griewank","year":"1982","unstructured":"Griewank, A., Toint, P.: Local convergence analysis for partitioned quasi-Newton updates. Numer. Math. 39(3), 429\u2013448 (1982)","journal-title":"Numer. Math."},{"issue":"1","key":"1622_CR22","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1137\/0801005","volume":"1","author":"J Engels","year":"1991","unstructured":"Engels, J., Mart\u00ednez, H.: Local and superlinear convergence for partially known quasi-Newton methods. SIAM J. Optim. 1(1), 42\u201356 (1991)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"1622_CR23","first-page":"541","volume":"39","author":"H Yabe","year":"1996","unstructured":"Yabe, H., Yamaki, N.: Local and superlinear convergence of structured quasi-Newton methods for nonlinear optimization. J. Oper. Res. Soc. Jpn. 39(4), 541\u2013557 (1996)","journal-title":"J. Oper. Res. Soc. Jpn."},{"issue":"3","key":"1622_CR24","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1023\/B:COAP.0000044184.25410.39","volume":"29","author":"Z Wei","year":"2004","unstructured":"Wei, Z., Yu, G., Yuan, G., Lian, Z.: The superlinear convergence of a modified BFGS-type method for unconstrained optimization. Comput. Optim. Appl. 29(3), 315\u2013332 (2004)","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"1622_CR25","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":"1622_CR26","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":"1622_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. Optim. Methods Softw. 34(1), 194\u2013217 (2019)","journal-title":"Optim. Methods Softw."},{"issue":"5","key":"1622_CR28","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1137\/0724077","volume":"24","author":"R Byrd","year":"1987","unstructured":"Byrd, R., Nocedal, J., Yuan, Y.: 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":"3","key":"1622_CR29","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1137\/0726042","volume":"26","author":"R Byrd","year":"1989","unstructured":"Byrd, R., Nocedal, J.: A tool for the analysis of quasi-Newton methods with application to unconstrained minimization. SIAM J. Numer. Anal. 26(3), 727\u2013739 (1989)","journal-title":"SIAM J. Numer. Anal."},{"issue":"4","key":"1622_CR30","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1137\/0802026","volume":"2","author":"R Byrd","year":"1992","unstructured":"Byrd, R., Liu, D., Nocedal, J.: On the behavior of Broyden\u2019s class of quasi-Newton methods. SIAM J. Optim. 2(4), 533\u2013557 (1992)","journal-title":"SIAM J. Optim."},{"key":"1622_CR31","unstructured":"Rodomanov, A., Nesterov, Y.: Greedy quasi-Newton methods with explicit superlinear convergence. In: CORE Discussion Papers 06, (2020)"},{"key":"1622_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91578-4","volume-title":"Lectures on convex optimization","author":"Y Nesterov","year":"2018","unstructured":"Nesterov, Y.: Lectures on convex optimization. Springer, Berlin (2018)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01622-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01622-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01622-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T19:03:52Z","timestamp":1656356632000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01622-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,8]]},"references-count":32,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["1622"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01622-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,8]]},"assertion":[{"value":"30 March 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 January 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}