{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:21:27Z","timestamp":1750306887797,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":35,"publisher":"ACM","license":[{"start":{"date-parts":[[2013,1,16]],"date-time":"2013-01-16T00:00:00Z","timestamp":1358294400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2013,1,16]]},"DOI":"10.1145\/2460239.2460256","type":"proceedings-article","created":{"date-parts":[[2013,4,9]],"date-time":"2013-04-09T12:19:32Z","timestamp":1365509972000},"page":"183-190","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Noisy optimization complexity under locality assumption"],"prefix":"10.1145","author":[{"given":"J\u00e9r\u00e9mie","family":"Decock","sequence":"first","affiliation":[{"name":"Universit\u00e9 Paris-Sud, Orsay, France"}]},{"given":"Olivier","family":"Teytaud","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Sud, Orsay, France"}]}],"member":"320","published-online":{"date-parts":[[2013,1,16]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Recent progress in unconstrained nonlinear optimization without derivatives","author":"Conn A.","year":"1997","unstructured":"A. Conn , K. Scheinberg , and L. Toint , \" Recent progress in unconstrained nonlinear optimization without derivatives ,\" 1997 . {Online}. Available: citeseer.ist.psu.edu\/conn97recent.html A. Conn, K. Scheinberg, and L. Toint, \"Recent progress in unconstrained nonlinear optimization without derivatives,\" 1997. {Online}. Available: citeseer.ist.psu.edu\/conn97recent.html"},{"key":"e_1_3_2_1_2_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/978-3-642-20712-9_2","volume-title":"Towards a complexity theory of randomized search heuristics: Ranking-based black-box complexity,\" in CSR","author":"Doerr B.","year":"2011","unstructured":"B. Doerr and C. Winzen , \" Towards a complexity theory of randomized search heuristics: Ranking-based black-box complexity,\" in CSR , ser. Lecture Notes in Computer Science , A. S. Kulikov and N. K. Vereshchagin, Eds., vol. 6651 . Springer , 2011 , pp. 15 -- 28 . B. Doerr and C. Winzen, \"Towards a complexity theory of randomized search heuristics: Ranking-based black-box complexity,\" in CSR, ser. Lecture Notes in Computer Science, A. S. Kulikov and N. K. Vereshchagin, Eds., vol. 6651. Springer, 2011, pp. 15--28."},{"key":"e_1_3_2_1_3_1","first-page":"273","volume-title":"Regret Bounds for Gaussian Process Bandit Problems,\" in JMLR Workshop and Conference Proceedings: AISTATS","author":"Gr\u00fcnew\u00e4lder S.","year":"2010","unstructured":"S. Gr\u00fcnew\u00e4lder , J.-Y. Audibert , M. Opper , and J. Shawe-Taylor , \" Regret Bounds for Gaussian Process Bandit Problems,\" in JMLR Workshop and Conference Proceedings: AISTATS 2010 , vol. 9 , Chia Laguna Resort , Sardinia, Italie , 2010, pp. 273 -- 280 . {Online}. Available: http:\/\/hal-enpc.archives-ouvertes.fr\/hal-00654517 S. Gr\u00fcnew\u00e4lder, J.-Y. Audibert, M. Opper, and J. Shawe-Taylor, \"Regret Bounds for Gaussian Process Bandit Problems,\" in JMLR Workshop and Conference Proceedings: AISTATS 2010, vol. 9, Chia Laguna Resort, Sardinia, Italie, 2010, pp. 273--280. {Online}. Available: http:\/\/hal-enpc.archives-ouvertes.fr\/hal-00654517"},{"key":"e_1_3_2_1_4_1","volume-title":"Numerical Optimization of Computer Models. New-York: John Wiley & Sons","author":"Schwefel H.-P.","year":"1981","unstructured":"H.-P. Schwefel , Numerical Optimization of Computer Models. New-York: John Wiley & Sons , 1981 , 1995-2nd edition. H.-P. Schwefel, Numerical Optimization of Computer Models. New-York: John Wiley & Sons, 1981, 1995-2nd edition."},{"key":"e_1_3_2_1_5_1","first-page":"109","volume-title":"T. B\u00e4ck, G. Eiben, M. Schoenauer, and H.-P","author":"Beyer H.-G.","year":"1998","unstructured":"H.-G. Beyer , \"Mutate large , but inherit small! On the analysis of mutations in (1,\u0142ambda)-ES with noisy fitness data,\" in Proc. of the 5th Conference on Parallel Problems Solving from Nature , T. B\u00e4ck, G. Eiben, M. Schoenauer, and H.-P . Schwefel, Eds. Springer Verlag , 1998 , pp. 109 -- 118 . H.-G. Beyer, \"Mutate large, but inherit small! On the analysis of mutations in (1,\u0142ambda)-ES with noisy fitness data,\" in Proc. of the 5th Conference on Parallel Problems Solving from Nature, T. B\u00e4ck, G. Eiben, M. Schoenauer, and H.-P. Schwefel, Eds. Springer Verlag, 1998, pp. 109--118."},{"key":"e_1_3_2_1_6_1","first-page":"101","volume-title":"Genetic algorithms in noisy environments, in machine learning: Special issue on genetic algorithms","author":"Fitzpatrick J.","year":"1988","unstructured":"J. Fitzpatrick and J. Grefenstette , \" Genetic algorithms in noisy environments, in machine learning: Special issue on genetic algorithms , p. langley, ed. dordrecht: Kluwer academic publishers, vol. 3 , pp. 101 120,\" 1988 . J. Fitzpatrick and J. Grefenstette, \"Genetic algorithms in noisy environments, in machine learning: Special issue on genetic algorithms, p. langley, ed. dordrecht: Kluwer academic publishers, vol. 3, pp. 101 120,\" 1988."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/4235.985690"},{"key":"e_1_3_2_1_9_1","first-page":"159","volume-title":"Eds.","volume":"866","author":"Hammel U.","year":"1994","unstructured":"U. Hammel and T. B\u00e4ck , \" Evolution strategies on noisy functions: How to improve convergence properties,\" in Parallel Problem Solving From Nature, ser. LNCS, Y. Davidor, H.-P. Schwefel, and R. M\u00e4nner , Eds. , vol. 866 . Jerusalem : springer, 9--14 Oct. 1994 , pp. 159 -- 168 . U. Hammel and T. B\u00e4ck, \"Evolution strategies on noisy functions: How to improve convergence properties,\" in Parallel Problem Solving From Nature, ser. LNCS, Y. Davidor, H.-P. Schwefel, and R. M\u00e4nner, Eds., vol. 866. Jerusalem: springer, 9--14Oct. 1994, pp. 159--168."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/637914.637948"},{"key":"e_1_3_2_1_11_1","volume-title":"On multiplicative noise models for stochastic search,\" in Parallel Problem Solving From Nature, dortmund Allemagne","author":"Jebalia M.","year":"2008","unstructured":"M. Jebalia and A. Auger , \" On multiplicative noise models for stochastic search,\" in Parallel Problem Solving From Nature, dortmund Allemagne , 2008 . {Online}. Available: http:\/\/hal.inria.fr\/inria-00287725\/en\/ M. Jebalia and A. Auger, \"On multiplicative noise models for stochastic search,\" in Parallel Problem Solving From Nature, dortmund Allemagne, 2008. {Online}. Available: http:\/\/hal.inria.fr\/inria-00287725\/en\/"},{"key":"e_1_3_2_1_12_1","volume-title":"Singapour","author":"Teytaud O.","year":"2007","unstructured":"O. Teytaud and A. Auger , \" On the adaptation of the noise level for stochastic optimization,\" in IEEE Congress on Evolutionary Computation , Singapour , 2007 . {Online}. Available : http:\/\/hal.inria.fr\/inria-00173224\/en\/ O. Teytaud and A. Auger, \"On the adaptation of the noise level for stochastic optimization,\" in IEEE Congress on Evolutionary Computation, Singapour, 2007. {Online}. Available: http:\/\/hal.inria.fr\/inria-00173224\/en\/"},{"key":"e_1_3_2_1_13_1","first-page":"146","volume-title":"H. J. van den Herik and A","author":"Coulom R.","year":"2011","unstructured":"R. Coulom , \"Clop : Confident local optimization for noisy black-box parameter tuning,\" in ACG, ser. Lecture Notes in Computer Science , H. J. van den Herik and A . Plaat, Eds., vol. 7168 . Springer , 2011 , pp. 146 -- 157 . R. Coulom, \"Clop: Confident local optimization for noisy black-box parameter tuning,\" in ACG, ser. Lecture Notes in Computer Science, H. J. van den Herik and A. Plaat, Eds., vol. 7168. Springer, 2011, pp. 146--157."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1967654.1967660"},{"key":"e_1_3_2_1_15_1","volume-title":"Bandit-based estimation of distribution algorithms for noisy optimization: Rigorous runtime analysis,\" in Proceedings of Lion4 (accepted)","author":"Rolet P.","year":"2009","unstructured":"P. Rolet and O. Teytaud , \" Bandit-based estimation of distribution algorithms for noisy optimization: Rigorous runtime analysis,\" in Proceedings of Lion4 (accepted) ; presented in TRSH 2009 in Birmingham , 2009. P. Rolet and O. Teytaud, \"Bandit-based estimation of distribution algorithms for noisy optimization: Rigorous runtime analysis,\" in Proceedings of Lion4 (accepted); presented in TRSH 2009 in Birmingham, 2009."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12239-2_61"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1569901.1570064"},{"key":"e_1_3_2_1_18_1","volume-title":"A probabilistic Theory of Pattern Recognition","author":"Devroye L.","year":"1997","unstructured":"L. Devroye , L. Gy\u00f6rfi , and G. Lugosi , A probabilistic Theory of Pattern Recognition . Springer , 1997 . L. Devroye, L. Gy\u00f6rfi, and G. Lugosi, A probabilistic Theory of Pattern Recognition. Springer, 1997."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1967654.1967660"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008306431147"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-008-9354-2"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177699070"},{"key":"e_1_3_2_1_23_1","first-page":"309","article-title":"Consid\u00e9rations \u00e0 l'appui de la d\u00e9couverte de laplace","volume":"37","author":"Bienaym\u00e9 L.","year":"1853","unstructured":"L. Bienaym\u00e9 , \" Consid\u00e9rations \u00e0 l'appui de la d\u00e9couverte de laplace ,\" Comptes Rendus de l'Acad\u00e9mie des Sciences , vol. 37 , pp. 309 -- 324 , 1853 . L. Bienaym\u00e9, \"Consid\u00e9rations \u00e0 l'appui de la d\u00e9couverte de laplace,\" Comptes Rendus de l'Acad\u00e9mie des Sciences, vol. 37, pp. 309--324, 1853.","journal-title":"Comptes Rendus de l'Acad\u00e9mie des Sciences"},{"key":"e_1_3_2_1_24_1","first-page":"157","article-title":"Sur les valeurs limites des integrales","volume":"19","author":"Chebyshev P.","year":"1874","unstructured":"P. Chebyshev , \" Sur les valeurs limites des integrales ,\" Math Pure Appl , vol. 19 , p. 157 -- 160 , 1874 . P. Chebyshev, \"Sur les valeurs limites des integrales,\" Math Pure Appl, vol. 19, p. 157--160, 1874.","journal-title":"Math Pure Appl"},{"key":"e_1_3_2_1_25_1","volume-title":"St Petersburg","author":"Markov A.","year":"2002","unstructured":"A. Markov , \"On certain applications of algebraic continued fractions,\" Ph.D. dissertation , St Petersburg , 2002 . A. Markov, \"On certain applications of algebraic continued fractions,\" Ph.D. dissertation, St Petersburg, 2002."},{"key":"e_1_3_2_1_26_1","series-title":"Springer series in statistics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2545-2","volume-title":"Weak Convergence and Empirical Processes","author":"Vaart A. V. D.","year":"1996","unstructured":"A. V. D. Vaart and J. Wellner , Weak Convergence and Empirical Processes . Springer series in statistics , 1996 . A. V. D. Vaart and J. Wellner, Weak Convergence and Empirical Processes. Springer series in statistics, 1996."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11844297_3"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9391-3"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.11.017"},{"key":"e_1_3_2_1_30_1","volume-title":"Local and global order 3\/2 convergence of a surrogate evolutionnary algorithm,\" in Gecco","author":"Auger A.","year":"2005","unstructured":"A. Auger , M. Schoenauer , and O. Teytaud , \" Local and global order 3\/2 convergence of a surrogate evolutionnary algorithm,\" in Gecco , 2005 , p. 8 p. A. Auger, M. Schoenauer, and O. Teytaud, \"Local and global order 3\/2 convergence of a surrogate evolutionnary algorithm,\" in Gecco, 2005, p. 8 p."},{"key":"e_1_3_2_1_31_1","first-page":"39","volume-title":"Ed.","volume":"1917","author":"Arnold D. V.","year":"2000","unstructured":"D. V. Arnold and H.-G. Beyer , \"Efficiency and mutation strength adaptation of the (mu\/mui,lambda)-es in a noisy environment,\" in Parallel Problem Solving from Nature, ser. LNCS, M. S. et al ., Ed. , vol. 1917 . springer, 2000 , pp. 39 -- 48 . D. V. Arnold and H.-G. Beyer, \"Efficiency and mutation strength adaptation of the (mu\/mui,lambda)-es in a noisy environment,\" in Parallel Problem Solving from Nature, ser. LNCS, M. S. et al., Ed., vol. 1917. springer, 2000, pp. 39--48."},{"key":"e_1_3_2_1_32_1","series-title":"Natural Computing Series","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04378-3","volume-title":"The Theory of Evolution Strategies","author":"Beyer H.-G.","year":"2001","unstructured":"H.-G. Beyer , The Theory of Evolution Strategies , ser. Natural Computing Series . Springer , Heideberg , 2001 . H.-G. Beyer, The Theory of Evolution Strategies, ser. Natural Computing Series. Springer, Heideberg, 2001."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176350965"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729392"},{"key":"e_1_3_2_1_35_1","first-page":"2008","article-title":"Global optimization based on noisy evaluations: an empirical study of two statistical approaches","author":"Vazquez E.","unstructured":"E. Vazquez , J. Villemonteix , M. Sidorkiewicz , and E. Walter , \" Global optimization based on noisy evaluations: an empirical study of two statistical approaches ,\" Journal of Global Optimization , p. 17 pages, 2008 . {Online}. Available: dx.doi.org\/10.1007\/s10898-008-9313-y http:\/\/hal-supelec.archives-ouvertes.fr\/hal-00354656\/en\/ 10.1007\/s10898-008-9313-y E. Vazquez, J. Villemonteix, M. Sidorkiewicz, and E. Walter, \"Global optimization based on noisy evaluations: an empirical study of two statistical approaches,\" Journal of Global Optimization, p. 17 pages, 2008. {Online}. Available: dx.doi.org\/10.1007\/s10898-008-9313-y http:\/\/hal-supelec.archives-ouvertes.fr\/hal-00354656\/en\/","journal-title":"Journal of Global Optimization"},{"key":"e_1_3_2_1_36_1","volume-title":"11th International Workshop, FOGA 2011, Schwarzenberg, Austria, January 5--8, 2011, Proceedings. ACM","author":"Beyer H.-G.","year":"2011","unstructured":"H.-G. Beyer and W. B. Langdon , Eds., Foundations of Genetic Algorithms , 11th International Workshop, FOGA 2011, Schwarzenberg, Austria, January 5--8, 2011, Proceedings. ACM , 2011 . H.-G. Beyer and W. B. Langdon, Eds., Foundations of Genetic Algorithms, 11th International Workshop, FOGA 2011, Schwarzenberg, Austria, January 5--8, 2011, Proceedings. ACM, 2011."}],"event":{"name":"FOGA '13: Foundations of Genetic Algorithms XII","sponsor":["SIGEVO ACM Special Interest Group on Genetic and Evolutionary Computation"],"location":"Adelaide Australia","acronym":"FOGA '13"},"container-title":["Proceedings of the twelfth workshop on Foundations of genetic algorithms XII"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2460239.2460256","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2460239.2460256","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:46Z","timestamp":1750234726000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2460239.2460256"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,16]]},"references-count":35,"alternative-id":["10.1145\/2460239.2460256","10.1145\/2460239"],"URL":"https:\/\/doi.org\/10.1145\/2460239.2460256","relation":{},"subject":[],"published":{"date-parts":[[2013,1,16]]},"assertion":[{"value":"2013-01-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}