{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:32:38Z","timestamp":1761611558864,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,7,8]],"date-time":"2023-07-08T00:00:00Z","timestamp":1688774400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,8]],"date-time":"2023-07-08T00:00:00Z","timestamp":1688774400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003484","name":"Heinrich-Heine-Universit\u00e4t D\u00fcsseldorf","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003484","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This note considers the momentum method by Polyak and the accelerated gradient method by Nesterov, both without line search but with fixed step length applied to strongly convex quadratic functions assuming that exact gradients are used and appropriate upper and lower bounds for the extreme eigenvalues of the Hessian matrix are known. Simple 2-d-examples show that the Euclidean distance of the iterates to the optimal solution is non-monotone. In this context, an explicit bound is derived on the number of iterations needed to guarantee a reduction of the Euclidean distance to the optimal solution by a factor <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\epsilon $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03f5<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. For both methods, the bound is optimal up to a constant factor, it complements earlier asymptotically optimal results for the momentum method, and it establishes another link of the momentum method and Nesterov\u2019s accelerated gradient method.<\/jats:p>","DOI":"10.1007\/s10957-023-02261-w","type":"journal-article","created":{"date-parts":[[2023,7,8]],"date-time":"2023-07-08T18:01:58Z","timestamp":1688839318000},"page":"456-474","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Iteration Complexity of Fixed-Step Methods by Nesterov and Polyak for Convex Quadratic Functions"],"prefix":"10.1007","volume":"202","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2247-7216","authenticated-orcid":false,"given":"Melinda","family":"Hagedorn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3458-123X","authenticated-orcid":false,"given":"Florian","family":"Jarre","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,8]]},"reference":[{"key":"2261_CR1","unstructured":"Barr\u00e9, M., Taylor, A., d\u2019Aspremont, A.: Complexity guarantees for Polyak steps with momentum. In: 33rd Annual Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 125, pp. 1\u201327 (2020)"},{"key":"2261_CR2","unstructured":"Defazio, A.: Momentum via primal averaging: theoretical insights and learning rate schedules for non-convex optimization. arXiv:2010.00406pdf (2020)"},{"key":"2261_CR3","unstructured":"D\u00e9fossez, A., Bottou, L., Bach, F., Usunier, N.: A simple convergence proof of Adam and Adagrad. Transactions on Machine Learning Research. arXiv:2003.02395pdf (2022)"},{"issue":"1","key":"2261_CR4","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1137\/20M1322716","volume":"31","author":"J Diakonioklas","year":"2021","unstructured":"Diakonioklas, J., Jordan, M.I.: Generalized momentum-based methods: a Hamiltonian perspective. SIAM J. Optim. 31(1), 915\u2013944 (2021)","journal-title":"SIAM J. Optim."},{"key":"2261_CR5","unstructured":"Ganesh, S., Deb, R., Thoppe, G., Budhiraja, A.: Does momentum help in stochastic optimization? A sample complexity analysis. arXiv:2110.15547v3 (2022)"},{"key":"2261_CR6","unstructured":"Gitman, I., Lang, H., Zhang, P., Xiao, L.: Understanding the role of momentum in stochastic gradient methods. In: Wallach, H., Larochelle, H., Beygelzimer, A., d\u2019Alch\u00e9-Buc, F., Fox, E., Garnett, R. (eds) Advances in Neural Information Processing Systems, Vol. 32 (NeurIPS 2019). https:\/\/proceedings.neurips.cc\/paper\/2019 (2019)"},{"key":"2261_CR7","doi-asserted-by":"crossref","unstructured":"Goh, G.: Why Momentum Really Works. Distill. http:\/\/distill.pub\/2017\/momentum (2017)","DOI":"10.23915\/distill.00006"},{"key":"2261_CR8","unstructured":"Gratton, S., Jerad, S., Toint, P.L.: First-Order Objective-Function-Free Optimization Algorithms and Their Complexity (2022)"},{"key":"2261_CR9","unstructured":"Gratton, S., Jerad, S., Toint, P.L.: Parametric complexity analysis for a class of first-order Adagrad-like algorithms. arXiv:2203.01647pdf (2022)"},{"key":"2261_CR10","doi-asserted-by":"crossref","unstructured":"Gratton, S., Toint, P.L.: OFFO minimization algorithms for second-order optimality and their complexity. arXiv:2203.03351pdf (2022)","DOI":"10.1007\/s10589-022-00435-2"},{"issue":"261","key":"2261_CR11","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1090\/S0025-5718-07-01922-9","volume":"77","author":"RC Li","year":"2008","unstructured":"Li, R.C.: On Meinardus\u2019 examples for the conjugate gradient method. Math. Comput. 77(261), 335\u2013352 (2008)","journal-title":"Math. Comput."},{"key":"2261_CR12","first-page":"543","volume":"269","author":"YE Nesterov","year":"1983","unstructured":"Nesterov, Y.E.: A method for solving the convex programming problem with convergence rate $$O(1\/k^2)$$. Dokl. Acad. Nauk. SSSR 269, 543\u2013547 (1983)","journal-title":"Dokl. Acad. Nauk. SSSR"},{"key":"2261_CR13","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"YE Nesterov","year":"2003","unstructured":"Nesterov, Y.E.: Introductory Lectures on Convex Optimization: A Basic Course, vol. 87. Springer, Berlin (2003)"},{"issue":"3","key":"2261_CR14","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1007\/s10208-013-9150-3","volume":"15","author":"B O\u2019Donoghue","year":"2015","unstructured":"O\u2019Donoghue, B., Cand\u00e8s, E.: Adaptive restart for accelerated gradient schemes. Found. Comput. Math. 15(3), 715\u2013732 (2015)","journal-title":"Found. Comput. Math."},{"issue":"5","key":"2261_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0041-5553(64)90137-5","volume":"4","author":"BT Polyak","year":"1964","unstructured":"Polyak, B.T.: Some methods of speeding up the convergence of iteration methods. USSR Comput. Math. Math. Phys. 4(5), 1\u201317 (1964)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"2261_CR16","volume-title":"Introduction to Optimization","author":"BT Polyak","year":"1987","unstructured":"Polyak, B.T.: Introduction to Optimization. Optimization Software Inc., Publications Division, Duluth (1987)"},{"key":"2261_CR17","unstructured":"Sebbouh, O., Gower, R.M., Defazio, A.: On the Convergence of the Stochastic Heavy Ball Method. https:\/\/othmanesebbouh.github.io\/publications\/heavy ball.pdf (2020)"},{"key":"2261_CR18","unstructured":"The GitHub repository: https:\/\/github.com\/MHagedorn\/momentum (2022)"},{"key":"2261_CR19","unstructured":"Yang, T., Lin, Q., Li, Z.: Unified convergence analysis of stochastic momentum methods for convex and non-convex optimization. arXiv:1604.03257pdf (2016)"}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-023-02261-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-023-02261-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-023-02261-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,21]],"date-time":"2024-07-21T08:03:58Z","timestamp":1721549038000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-023-02261-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,8]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["2261"],"URL":"https:\/\/doi.org\/10.1007\/s10957-023-02261-w","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"type":"print","value":"0022-3239"},{"type":"electronic","value":"1573-2878"}],"subject":[],"published":{"date-parts":[[2023,7,8]]},"assertion":[{"value":"13 December 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 June 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}