{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T07:07:44Z","timestamp":1784185664693,"version":"3.55.0"},"reference-count":53,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100007352","name":"State Secretariat for Education, Research and Innovation","doi-asserted-by":"crossref","award":["22.00133"],"award-info":[{"award-number":["22.00133"]}],"id":[{"id":"10.13039\/501100007352","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2026,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>In this work, we study the iteration complexity of gradient methods for minimizing convex quadratic functions regularized by powers of Euclidean norms. We show that, due to the uniform convexity of the objective, gradient methods have improved convergence rates. For the general class of all first-order methods, we prove a lower bound on the rate of order [Formula: see text] in terms of the functional residual, where [Formula: see text] is the iteration number and [Formula: see text] is the power of the regularization term. This rate is optimal and was previously achieved by the composite fast gradient method. Therefore, we establish that this rate is tight for the class of uniformly convex quadratic functions. A special case of our problem is [Formula: see text], i.e., cubically regularized convex quadratic functions. It naturally appears as a subproblem at each iteration of the cubic Newton method, and our theory shows that the rate of [Formula: see text] is optimal in this case. Despite its theoretical efficiency, the composite gradient methods requires solving a univariate nonlinear equation of order [Formula: see text] to compute the step. In contrast, we develop a simple version of the basic gradient descent using a novel step size that has a convergence rate of [Formula: see text]. We show that this rate is unimprovable for a class of first-order momentum-free methods with small step sizes. Numerical experiments also demonstrate the tightness of our bounds.<\/jats:p>","DOI":"10.1137\/25m1736578","type":"journal-article","created":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T07:00:37Z","timestamp":1784185237000},"page":"1509-1536","source":"Crossref","is-referenced-by-count":0,"title":["Complexity of Minimizing Regularized Convex Quadratic Functions"],"prefix":"10.1137","volume":"36","author":[{"given":"Daniel Berg","family":"Thomsen","sequence":"first","affiliation":[{"name":"INRIA, \u00c9cole Normale Sup\u00e9rieure & CMAP, \u00c9cole polytechnique, Paris, France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nikita","family":"Doikov","sequence":"additional","affiliation":[{"name":"School of Operations Research and Information Engineering (ORIE), Cornell University, Ithica, NY 14850 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,7,16]]},"reference":[{"key":"ref1","unstructured":"N. Agarwal and E. Hazan, Lower bounds for higher-order convex optimization, in Proceedings of the 31st Conference On Learning Theory, Proceedings of Machine Learning Research 75, S. Bubeck, V. Perchet, and P. Rigollet, eds. 2018, pp. 774\u2013792, https:\/\/proceedings.mlr.press\/v75\/agarwal18a.html."},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1145\/3708502"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-024-02164-2"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1293-1"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0817"},{"key":"ref6","unstructured":"D. Berg Thomsen, Oracle Lower Bounds for Minimizing Regularized Quadratic Functions, master\u2019s thesis, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, 2024."},{"key":"ref7","volume-title":"Advances in Neural Information Processing Systems 31","author":"Carmon Y.","year":"2018"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/20M1321759"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s10543-019-00791-2"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976991.ch10"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0286-5"},{"key":"ref12","unstructured":"T. Chen, The Lanczos Algorithm for Matrix Functions: A Handbook for Scientists, preprint, arXiv:2410.11090, 2024."},{"key":"ref13","series-title":"AMS Chelsea Publishing Series","volume-title":"Introduction to Approximation Theory","author":"Cheney E. W.","year":"1998"},{"key":"ref14","unstructured":"A. Chowdhury, J. Yang, and P. Drineas, An Iterative, Sketching-based framework for Ridge regression, in Proceedings of the 35th International Conference on Machine Learning, PMLR 80, 2018, pp. 989\u2013998, https:\/\/proceedings.mlr.press\/v80\/chowdhury18a.html (accessed 2024-04-03)."},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"A. R. Conn, N. I. M. Gould, and P. L. Toint, Trust Region Methods, SIAM, Philadelphia, PA, 2000, https:\/\/epubs.siam.org\/doi\/book\/10.1137\/1.9780898719857 (accessed 2024-01-03).","DOI":"10.1137\/1.9780898719857"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-023-02040-5"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-025-02237-x"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-021-01838-7"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1137\/08072440X"},{"key":"ref20","unstructured":"E. Gorbunov, N. Tupitsa, S. Choudhury, A. Aliev, P. Richt\u00e1rik, S. Horv\u00e1th, and M. Tak\u00e1\u010d, Methods for convex \\((l\\unicode{x005F}0, l\\unicode{x005F}1)\\)-smooth optimization: clipping, acceleration, and adaptivity, in Proceedings of the International Conference on Learning Representations (ICLR), 2025, https:\/\/proceedings.iclr.cc\/paper_files\/paper\/2025\/hash\/f21a5fedfbcb55406ddaf51cf90d494a-Abstract-Conference.html."},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497322735"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-010-0011-7"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2019.1670177"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1137\/16M1087801"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1137\/17M1142077"},{"key":"ref26","unstructured":"A. Griewank, The Modification of Newton\u2019s Method for Unconstrained Optimization by Bounding Cubic Terms, Technical report, 1981, https:\/\/doi.org\/10.13140\/RG.2.1.4097.2960."},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2014.08.003"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-84858-7_3"},{"key":"ref29","unstructured":"E. Hazan and S. Kakade, Revisiting the Polyak Step Size, preprint, arXiv:1905.00313, 2019."},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0933-y"},{"key":"ref31","volume-title":"Linear Algebra","author":"Hoffman K.","year":"1971"},{"key":"ref32","unstructured":"P. Kacham and D. Woodruff, Sketching algorithms and lower bounds for Ridge regression, in Proceedings of the 39th International Conference on Machine Learning, PMLR 162, 2022, pp. 10539\u201310556, https:\/\/proceedings.mlr.press\/v162\/kacham22a.html (accessed 2024-04-03)."},{"key":"ref33","unstructured":"A. Koloskova, H. Hendrikx, and S. U. Stich, Revisiting gradient clipping: Stochastic bias and tight convergence guarantees, in International Conference on Machine Learning, PMLR 202, 2023, pp. 17343\u201317363."},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1137\/16M1099546"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1007\/s10543-008-0197-5"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1201\/9781420036114"},{"key":"ref37","volume-title":"Information-based Complexity of Convex Programming","author":"Nemirovski A.","year":"1994"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(85)90100-4"},{"key":"ref39","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"Nemirovski A.","year":"1983"},{"key":"ref40","first-page":"543","volume":"269","author":"Nesterov Y.","year":"1983","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0089-x"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91578-4"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01449-1"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2020.1854252"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-024-02456-9"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0706-8"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-40065-5_5"},{"key":"ref48","series-title":"Transl. Ser. Math. Engrg.","volume-title":"Introduction to optimization","author":"Polyak B. T.","year":"1987"},{"key":"ref49","volume-title":"Advances in Neural Information Processing Systems 30","author":"Roulet V.","year":"2017"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1007\/s10013-016-0238-3"},{"key":"ref51","unstructured":"D. Vankov, A. Rodomanov, A. Nedich, L. Sankar, and S. U. Stich, Optimizing \\((l\\unicode{x005F}0, l\\unicode{x005F}1)\\)-Smooth functions by gradient methods, in Proceedings of the International Conference on Learning Representations (ICLR), 2025, https:\/\/openreview.net\/forum?id=GQ1Tc3vHbt."},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1002\/sapm1953321243"},{"key":"ref53","unstructured":"J. Zhang, T. He, S. Sra, and A. Jadbabaie, Why gradient clipping accelerates training: A theoretical justification for adaptivity, in Proceedings of the International Conference on Learning Representations (ICLR), 2020, https:\/\/openreview.net\/forum?id=BJgnXpVYwS."}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T07:00:43Z","timestamp":1784185243000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/25M1736578"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,16]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9,30]]}},"alternative-id":["10.1137\/25M1736578"],"URL":"https:\/\/doi.org\/10.1137\/25m1736578","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,16]]}}}