{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T07:04:40Z","timestamp":1776841480710,"version":"3.51.2"},"reference-count":21,"publisher":"American Mathematical Society (AMS)","issue":"360","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n We study gradient descent with backtracking line search (GD-BLS) to solve the noisy optimization problem\n \n \n \n \n \n \n \u03b8\n \n <\/mml:mi>\n \n \u22c6\n \n <\/mml:mo>\n <\/mml:msub>\n \u2254<\/mml:mo>\n a<\/mml:mi>\n r<\/mml:mi>\n g<\/mml:mi>\n m<\/mml:mi>\n i<\/mml:mi>\n \n n<\/mml:mi>\n \n \n \u03b8\n \n <\/mml:mi>\n \n \u2208\n \n <\/mml:mo>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:msub>\n \n E<\/mml:mi>\n <\/mml:mrow>\n [<\/mml:mo>\n f<\/mml:mi>\n (<\/mml:mo>\n \n \u03b8\n \n <\/mml:mi>\n ,<\/mml:mo>\n Z<\/mml:mi>\n )<\/mml:mo>\n ]<\/mml:mo>\n <\/mml:mrow>\n \\theta _\\star \u2254argmin_{\\theta \\in \\mathbb {R}^d} \\mathbb {E}[f(\\theta ,Z)]<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , imposing that the objective function\n \n \n \n \n F<\/mml:mi>\n (<\/mml:mo>\n \n \u03b8\n \n <\/mml:mi>\n )<\/mml:mo>\n \u2254<\/mml:mo>\n \n E<\/mml:mi>\n <\/mml:mrow>\n [<\/mml:mo>\n f<\/mml:mi>\n (<\/mml:mo>\n \n \u03b8\n \n <\/mml:mi>\n ,<\/mml:mo>\n Z<\/mml:mi>\n )<\/mml:mo>\n ]<\/mml:mo>\n <\/mml:mrow>\n F(\\theta )\u2254\\mathbb {E}[f(\\theta ,Z)]<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is strictly convex but not necessarily\n \n \n \n L<\/mml:mi>\n L<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -smooth. Assuming that\n \n \n \n \n \n E<\/mml:mi>\n <\/mml:mrow>\n [<\/mml:mo>\n \n \u2016\n \n <\/mml:mo>\n \n \n \u2207\n \n <\/mml:mi>\n \n \u03b8\n \n <\/mml:mi>\n <\/mml:msub>\n f<\/mml:mi>\n (<\/mml:mo>\n \n \n \u03b8\n \n <\/mml:mi>\n \n \u22c6\n \n <\/mml:mo>\n <\/mml:msub>\n ,<\/mml:mo>\n Z<\/mml:mi>\n )<\/mml:mo>\n \n \n \u2016\n \n <\/mml:mo>\n 2<\/mml:mn>\n <\/mml:msup>\n ]<\/mml:mo>\n ><\/mml:mo>\n \n \u221e\n \n <\/mml:mi>\n <\/mml:mrow>\n \\mathbb {E}[\\|\\nabla _\\theta f(\\theta _\\star ,Z)\\|^2]>\\infty<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , we first prove that sample average approximation based on GD-BLS allows to estimate\n \n \n \n \n \n \u03b8\n \n <\/mml:mi>\n \n \u22c6\n \n <\/mml:mo>\n <\/mml:msub>\n \\theta _\\star<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n with an error of size\n \n \n \n \n \n \n O<\/mml:mi>\n <\/mml:mrow>\n \n P<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n (<\/mml:mo>\n \n B<\/mml:mi>\n \n \n \u2212\n \n <\/mml:mo>\n 0.25<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n \\mathcal {O}_\\mathbb {P}(B^{-0.25})<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , where\n \n \n \n B<\/mml:mi>\n B<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is the available computational budget. We then show that we can improve upon this rate by stopping the optimization process earlier when the gradient of the objective function is sufficiently close to zero, and use the residual computational budget to optimize, again with GD-BLS, a finer approximation of\n \n \n \n F<\/mml:mi>\n F<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . By iteratively applying this strategy\n \n \n \n J<\/mml:mi>\n J<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n times we establish that we can estimate\n \n \n \n \n \n \u03b8\n \n <\/mml:mi>\n \n \u22c6\n \n <\/mml:mo>\n <\/mml:msub>\n \\theta _\\star<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n with an error of size\n \n \n \n \n \n \n O<\/mml:mi>\n <\/mml:mrow>\n \n P<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n (<\/mml:mo>\n \n B<\/mml:mi>\n \n \n \u2212\n \n <\/mml:mo>\n \n 1<\/mml:mn>\n 2<\/mml:mn>\n <\/mml:mfrac>\n (<\/mml:mo>\n 1<\/mml:mn>\n \n \u2212\n \n <\/mml:mo>\n \n \n \u03b4\n \n <\/mml:mi>\n \n J<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n \\mathcal {O}_\\mathbb {P}(B^{-\\frac {1}{2}(1-\\delta ^{J})})<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , where\n \n \n \n \n \n \u03b4\n \n <\/mml:mi>\n \n \u2208\n \n <\/mml:mo>\n (<\/mml:mo>\n 1<\/mml:mn>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n 2<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n \\delta \\in (1\/2,1)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is a user-specified parameter. More generally, we show that if\n \n \n \n \n \n E<\/mml:mi>\n <\/mml:mrow>\n [<\/mml:mo>\n \n \u2016\n \n <\/mml:mo>\n \n \n \u2207\n \n <\/mml:mi>\n \n \u03b8\n \n <\/mml:mi>\n <\/mml:msub>\n f<\/mml:mi>\n (<\/mml:mo>\n \n \n \u03b8\n \n <\/mml:mi>\n \n \u22c6\n \n <\/mml:mo>\n <\/mml:msub>\n ,<\/mml:mo>\n Z<\/mml:mi>\n )<\/mml:mo>\n \n \n \u2016\n \n <\/mml:mo>\n \n 1<\/mml:mn>\n +<\/mml:mo>\n \n \u03b1\n \n <\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n ]<\/mml:mo>\n ><\/mml:mo>\n \n \u221e\n \n <\/mml:mi>\n <\/mml:mrow>\n \\mathbb {E}[\\|\\nabla _\\theta f(\\theta _\\star ,Z)\\|^{1+\\alpha }]>\\infty<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n for some known\n \n \n \n \n \n \u03b1\n \n <\/mml:mi>\n \n \u2208\n \n <\/mml:mo>\n (<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n ]<\/mml:mo>\n <\/mml:mrow>\n \\alpha \\in (0,1]<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n then this approach, which can be seen as a retrospective approximation algorithm with a fixed computational budget, allows to learn\n \n \n \n \n \n \u03b8\n \n <\/mml:mi>\n \n \u22c6\n \n <\/mml:mo>\n <\/mml:msub>\n \\theta _\\star<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n with an error of size\n \n \n \n \n \n \n O<\/mml:mi>\n <\/mml:mrow>\n \n P<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n (<\/mml:mo>\n \n B<\/mml:mi>\n \n \n \u2212\n \n <\/mml:mo>\n \n \n \u03b1\n \n <\/mml:mi>\n \n 1<\/mml:mn>\n +<\/mml:mo>\n \n \u03b1\n \n <\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n (<\/mml:mo>\n 1<\/mml:mn>\n \n \u2212\n \n <\/mml:mo>\n \n \n \u03b4\n \n <\/mml:mi>\n \n J<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n \\mathcal {O}_\\mathbb {P}(B^{-\\frac {\\alpha }{1+\\alpha }(1-\\delta ^{J})})<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , where\n \n \n \n \n \n \u03b4\n \n <\/mml:mi>\n \n \u2208\n \n <\/mml:mo>\n (<\/mml:mo>\n 2<\/mml:mn>\n \n \u03b1\n \n <\/mml:mi>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n 3<\/mml:mn>\n \n \u03b1\n \n <\/mml:mi>\n )<\/mml:mo>\n ,<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n \\delta \\in (2\\alpha \/(1+3\\alpha ),1)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is a tuning parameter. Beyond knowing\n \n \n \n \n \u03b1\n \n <\/mml:mi>\n \\alpha<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , achieving the aforementioned convergence rates does not require to tune the algorithms\u2019 parameters according to the specific functions\n \n \n \n F<\/mml:mi>\n F<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and\n \n \n \n f<\/mml:mi>\n f<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n at hand, and we exhibit a simple noisy optimization problem for which stochastic gradient is not guaranteed to converge while the algorithms discussed in this work are.\n <\/p>","DOI":"10.1090\/mcom\/4103","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T14:09:09Z","timestamp":1749478149000},"page":"1887-1925","source":"Crossref","is-referenced-by-count":0,"title":["Gradient descent for convex and smooth noisy optimization"],"prefix":"10.1090","volume":"95","author":[{"given":"Feifei","family":"Hu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathieu","family":"Gerber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"key":"1","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/b137107","volume-title":"Analysis. I","author":"Amann, Herbert","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/3764371536"},{"issue":"3","key":"2","doi-asserted-by":"publisher","first-page":"2257","DOI":"10.1137\/18M1230323","article-title":"Stochastic (approximate) proximal point methods: convergence, optimality, and adaptivity","volume":"29","author":"Asi, Hilal","year":"2019","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"2","key":"3","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":"11","key":"4","doi-asserted-by":"publisher","first-page":"7711","DOI":"10.1109\/TIT.2013.2277869","article-title":"Bandits with heavy tail","volume":"59","author":"Bubeck, S\u00e9bastien","year":"2013","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"6","key":"5","doi-asserted-by":"publisher","first-page":"2695","DOI":"10.1214\/16-AOS1440","article-title":"Sub-Gaussian mean estimators","volume":"44","author":"Devroye, Luc","year":"2016","journal-title":"Ann. Statist.","ISSN":"https:\/\/id.crossref.org\/issn\/0090-5364","issn-type":"print"},{"key":"6","unstructured":"M. Faw, I. Tziotis, C. Caramanis, A. Mokhtari, S. Shakkottai, and R. Ward, The power of adaptivity in SGD: self-tuning step sizes with unbounded gradients and affine variance, Conference on Learning Theory, PMLR, 2022, pp. 313\u2013355."},{"key":"7","first-page":"Paper No. 136, 48","article-title":"Convergence rates for the stochastic gradient descent method for non-convex objective functions","volume":"21","author":"Fehrman, Benjamin","year":"2020","journal-title":"J. Mach. Learn. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/1532-4435","issn-type":"print"},{"key":"8","unstructured":"G. Garrigos and R. M. Gower, Handbook of convergence theorems for (stochastic) gradient methods, Preprint, arXiv:2301.11235, 2023."},{"key":"9","unstructured":"A. Khaled and P. Richt\u00e1rik, Better theory for SGD in the nonconvex world, Preprint, arXiv:2002.03329, 2020."},{"key":"10","doi-asserted-by":"crossref","unstructured":"S. Kim, R. Pasupathy, and S. G. Henderson, A guide to sample average approximation, Handbook of Simulation Optimization, 2015, pp. 207\u2013243.","DOI":"10.1007\/978-1-4939-1384-8_8"},{"key":"11","unstructured":"Y. Malitsky and K. Mishchenko, Adaptive gradient descent without descent, Preprint, arXiv:1910.09529, 2019."},{"key":"12","series-title":"Springer Optimization and Its Applications","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91578-4","volume-title":"Lectures on convex optimization","volume":"137","author":"Nesterov, Yurii","year":"2018","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319915777"},{"key":"13","doi-asserted-by":"crossref","unstructured":"D. Newton, R. Bollapragada, R. Pasupathy, and N. K. Yip, A retrospective approximation approach for smooth stochastic optimization, Mathematics of Operations Research (2024).","DOI":"10.1287\/moor.2022.0136"},{"key":"14","unstructured":"T. D. Nguyen, T. H. Nguyen, A. Ene, and H. Nguyen, Improved convergence in high probability of clipped gradient methods with heavy tailed noise, Adv. Neural Inf. Process. Syst. 36 (2024)."},{"issue":"1-2","key":"15","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/s10107-021-01710-6","article-title":"Stopping criteria for, and strong convergence of, stochastic gradient descent on Bottou-Curtis-Nocedal functions","volume":"195","author":"Patel, Vivak","year":"2022","journal-title":"Math. Program.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"key":"16","doi-asserted-by":"crossref","unstructured":"V. Patel, S. Zhang, and B. Tian, Global convergence and stability of stochastic gradient descent, Adv. Neural Inf. Process. Syst. 35 (2022), 36014\u201336025.","DOI":"10.52202\/068431-2610"},{"issue":"3","key":"17","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1287\/opre.2013.1163","article-title":"Optimal budget allocation for sample average approximation","volume":"61","author":"Royset, Johannes O.","year":"2013","journal-title":"Oper. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/0030-364X","issn-type":"print"},{"issue":"4","key":"18","doi-asserted-by":"publisher","first-page":"1694","DOI":"10.1214\/16-AOS1506","article-title":"Asymptotic and finite-sample properties of estimators based on stochastic gradients","volume":"45","author":"Toulis, Panos","year":"2017","journal-title":"Ann. Statist.","ISSN":"https:\/\/id.crossref.org\/issn\/0090-5364","issn-type":"print"},{"key":"19","series-title":"Cambridge Series in Statistical and Probabilistic Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511802256","volume-title":"Asymptotic statistics","volume":"3","author":"van der Vaart, A. W.","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/0521496039"},{"key":"20","unstructured":"H. Wang, M. Gurbuzbalaban, L. Zhu, U. Simsekli, and M. A. Erdogdu, Convergence rates of stochastic gradient descent under infinite noise variance, Adv. Neural Inf. Process. Syst. 34 (2021), 18866\u201318877."},{"key":"21","unstructured":"J. Zhang, T. He, S. Sra, and A. Jadbabaie, Why gradient clipping accelerates training: a theoretical justification for adaptivity, Preprint, arXiv:1905.11881, 2019."}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2026-95-360\/S0025-5718-2025-04103-6\/S0025-5718-2025-04103-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T06:04:59Z","timestamp":1776837899000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2026-95-360\/S0025-5718-2025-04103-6\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":21,"journal-issue":{"issue":"360","published-print":{"date-parts":[[2026,7]]}},"alternative-id":["S0025-5718-2025-04103-6"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/4103","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":[[2025,6,9]]}}}