{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T22:07:55Z","timestamp":1790806075778,"version":"4.1.0"},"reference-count":57,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["19H04179"],"award-info":[{"award-number":["19H04179"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:p>Evolution strategies (ESs) are zeroth-order stochastic black-box optimization heuristics invariant to monotonic transformations of the objective function. They evolve a multivariate normal distribution, from which candidate solutions are generated. Among different variants, CMA-ES is nowadays recognized as one of the state-of-the-art zeroth-order optimizers for difficult problems. Despite ample empirical evidence that ESs with a step-size control mechanism converge linearly, theoretical guarantees of linear convergence of ESs have been established only on limited classes of functions. In particular, theoretical results on convex functions are missing, where zeroth-order and also first-order optimization methods are often analyzed. In this paper, we establish almost sure linear convergence and a bound on the expected hitting time of an ES family, namely, the $(1+1)_\\kappa$-ES, which includes the (1+1)-ES with (generalized) one-fifth success rule and an abstract covariance matrix adaptation with bounded condition number, on a broad class of functions. The analysis holds for monotonic transformations of positively homogeneous functions and of quadratically bounded functions, the latter of which particularly includes monotonic transformation of strongly convex functions with Lipschitz continuous gradient. As far as the authors know, this is the first work that proves linear convergence of ES on such a broad class of functions.<\/jats:p>","DOI":"10.1137\/20m1373815","type":"journal-article","created":{"date-parts":[[2022,6,14]],"date-time":"2022-06-14T12:39:48Z","timestamp":1655210388000},"page":"1402-1429","source":"Crossref","is-referenced-by-count":19,"title":["Global Linear Convergence of Evolution Strategies on More than Smooth Strongly Convex Functions"],"prefix":"10.1137","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2760-8123","authenticated-orcid":true,"given":"Youhei","family":"Akimoto","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anne","family":"Auger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tobias","family":"Glasmachers","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daiki","family":"Morinaga","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2022,6,14]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/080716980"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1145\/2330163.2330343"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1145\/3205455.3205606"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1109\/CIG.2017.8080408"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/1830483.1830556"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/040603371"},{"key":"atypb7","volume-title":"Linear Convergence on Positively Homogeneous Functions of a Comparison Based Step-Size Adaptive Randomized Search: The (1+1)-ES with Generalized One-Fifth Success Rule, https:\/\/arxiv.org\/abs\/1310.8397","author":"Auger A.","year":"2013"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/140984038"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/130915984"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199610)9:3<279::AID-RSA2>3.0.CO;2-U"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1109\/BTAS.2018.8698539"},{"key":"atypb12","volume-title":"Convex Optimization: Algorithms and Complexity, https:\/\/arxiv.org\/abs\/1405.4980","author":"Bubeck S.","year":"2014"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1137-4"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177698981"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718768"},{"key":"atypb16","first-page":"195","volume-title":"Proceedings of the International Symposium on Systems Engineering and Analysis","author":"Devroye L.","year":"1972"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0793-x"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9585-3"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9622-x"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2019.00790"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2018.01.008"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508399"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1162\/evco_a_00248"},{"key":"atypb24","volume-title":"Proceedings of ICLR","author":"Golovin D.","year":"2020"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/140961602"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/drx043"},{"key":"atypb27","first-page":"2450","volume-title":"Proceedings of NeurIPS","author":"Ha D.","year":"2018"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.2307\/1426671"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1145\/1830761.1830790"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1162\/106365601750190398"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00058-3"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1023\/B:NACO.0000023417.31393.c7"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45061-0_82"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/11513575_14"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.04.004"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.042"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1023\/B:NACO.0000023416.59689.4e"},{"key":"atypb38","volume-title":"Simple Complexity Analysis of Simplified Direct Search, https:\/\/arxiv.org\/abs\/1410.0390","author":"Kone\u010dn\u1ef3 J.","year":"2014"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.5194\/gmd-10-127-2017"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492919000060"},{"key":"atypb41","volume-title":"General Drift Analysis with Tail Bounds, https:\/\/arxiv.org\/abs\/1307.2559","author":"Lehre P. K.","year":"2013"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-29414-4_2"},{"key":"atypb43","volume-title":"https:\/\/arxiv.org\/abs\/1608.03226","author":"Lengler J.","year":"2016"},{"key":"atypb44","volume-title":"Proceedings of AAAI","author":"MacAlpine P.","year":"2012"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1108\/17563780910959893"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1145\/3299904.3340303"},{"key":"atypb47","volume-title":"Lecture notes","author":"Nemirovski A.","year":"1995"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91578-4"},{"key":"atypb49","volume-title":"A Stochastic Line Search Method with Convergence Rate Analysis, https:\/\/arxiv.org\/abs\/1807.07994","author":"Paquette C.","year":"2018"},{"key":"atypb50","volume-title":"Frommann-Holzboog","author":"Rechenberg I.","year":"1973"},{"key":"atypb51","unstructured":"I. Rechenberg,\n                      Evolutionsstrategie\n                      '94, Frommann-Holzboog, Stuttgart, 1994."},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-012-9951-y"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1968.1098903"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1137\/110853613"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0908-z"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1206810109"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1145\/3205455.3205517"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1373815","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:56:28Z","timestamp":1787338588000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1373815"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6]]},"references-count":57,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["10.1137\/20M1373815"],"URL":"https:\/\/doi.org\/10.1137\/20m1373815","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6]]}}}