{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T18:28:30Z","timestamp":1789756110773,"version":"4.0.1"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-22-1-215"],"award-info":[{"award-number":["N00014-22-1-215"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 20-08434"],"award-info":[{"award-number":["CCF 20-08434"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["758 TRIPODS 17-40796"],"award-info":[{"award-number":["758 TRIPODS 17-40796"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We consider a step search method for continuous optimization under a stochastic setting where the function values and gradients are available only through inexact probabilistic zeroth- and first-order oracles. (We introduce the term step search for a class of methods, similar to line search, but where step direction can change during the back-tracking procedure.)\u00a0Unlike the stochastic gradient method and its many variants, the algorithm does not use a prespecified sequence of step sizes but increases or decreases the step size adaptively according to the estimated progress of the algorithm. These oracles capture multiple standard settings including expected loss minimization and zeroth-order optimization. Moreover, our framework is very general and allows the function and gradient estimates to be biased. The proposed algorithm is simple to describe and easy to implement. Under fairly general conditions on the oracles, we derive a high probability tail bound on the iteration complexity of the algorithm when it is applied to nonconvex, convex, and strongly convex (more generally, those satisfying the Polyak-\u0141ojasiewicz (PL) condition) functions. Our analysis strengthens and extends prior results for stochastic step and line search methods.<\/jats:p>","DOI":"10.1137\/22m1512764","type":"journal-article","created":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T04:03:31Z","timestamp":1719893011000},"page":"2411-2439","source":"Crossref","is-referenced-by-count":11,"title":["High Probability Complexity Bounds for Adaptive Step Search Based on Stochastic Oracles"],"prefix":"10.1137","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6362-2048","authenticated-orcid":true,"given":"Billy","family":"Jin","sequence":"first","affiliation":[{"name":"School of Operations Research and Information Engineering, Cornell University, Ithaca, NY 14853 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Katya","family":"Scheinberg","sequence":"additional","affiliation":[{"name":"School of Operations Research and Information Engineering, Cornell University, Ithaca, NY 14853 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8511-9649","authenticated-orcid":true,"given":"Miaolan","family":"Xie","sequence":"additional","affiliation":[{"name":"School of Operations Research and Information Engineering, Cornell University, Ithaca, NY 14853 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,7,2]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.2748\/tmj\/1178243286"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-021-09513-z"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1137\/19M1291832"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1137\/16M1080173"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1137-4"},{"key":"ref6","unstructured":"M. Fazel, R. Ge, S. M. Kakade, and M. Mesbahi, Global convergence of policy gradient methods for the linear quadratic regulator, in Proceedings of the International Conference on Machine Learning, 2018, pp. 1467\u20131476."},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/drx043"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"K. He, X. Zhang, S. Ren, and J. Sun, Deep residual learning for image recognition, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016, pp. 770\u2013778.","DOI":"10.1109\/CVPR.2016.90"},{"key":"ref9","first-page":"9193","volume":"34","author":"Jin B.","year":"2021","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref10","unstructured":"D. P. Kingma and J. Ba, Adam: A Method for Stochastic Optimization, preprint, https:\/\/arxiv.org\/abs\/1412.6980, 2014."},{"key":"ref11","unstructured":"Y. LeCun, C. Cortes, and C. Burges, Mnist handwritten digit database, ATT Labs [Online], 2010, http:\/\/yann.lecun.com\/exdb\/mnist."},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-015-9296-2"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"ref14","volume-title":"Numerical Optimization","author":"Nocedal J.","year":"2006","edition":"2"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1137\/18M1216250"},{"key":"ref16","first-page":"643","volume":"3","author":"Polyak B. T.","year":"1963","journal-title":"Zh. Vychisl. Mat. Mat. Fiz."},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"J. D. Romano, T. T. Le, W. La Cava, J. T. Gregg, D. J. Goldberg, P. Chakraborty, N. L. Ray, D. Himmelstein, W. Fu, and J. H. Moore, Pmlb v1.0: An Open Source Dataset Collection for Benchmarking Machine Learning Methods, preprint, arXiv:2012.00058v2, 2021.","DOI":"10.1093\/bioinformatics\/btab727"},{"key":"ref18","unstructured":"T. Salimans, J. Ho, X. Chen, S. Sidor, and I. Sutskever, Evolution Strategies as a Scalable Alternative to Reinforcement Learning, preprint, https:\/\/arxiv.org\/abs\/1703.03864, 2016."},{"key":"ref19","unstructured":"S. Vaswani, A. Mishkin, I. Laradji, M. Schmidt, G. Gidel, and S. Lacoste-Julien, Painless stochastic gradient: Interpolation, line-search, and convergence rates, in Proceedings of the 33rd International Conference on Neural Information Processing Systems, Vol. 32, Curran Associates, 2019, pp. 3732\u20133745."},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596"},{"key":"ref21","unstructured":"H. Xiao, K. Rasul, and R. Vollgraf, Fashion-MNIST: A Novel Image Dataset for Benchmarking Machine Learning Algorithms, preprint, https:\/\/arxiv.org\/abs\/1708.07747, 2017."}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1512764","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:10:44Z","timestamp":1787339444000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1512764"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,2]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1137\/22M1512764"],"URL":"https:\/\/doi.org\/10.1137\/22m1512764","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,2]]}}}