research-article

Noisy optimization complexity under locality assumption

Authors:

Jérémie Decock,

Olivier TeytaudAuthors Info & Claims

FOGA XII '13: Proceedings of the twelfth workshop on Foundations of genetic algorithms XII

Pages 183 - 190

https://doi.org/10.1145/2460239.2460256

Published: 16 January 2013 Publication History

Abstract

In spite of various recent publications on the subject, there are still gaps between upper and lower bounds in evolutionary optimization for noisy objective function. In this paper we reduce the gap, and get tight bounds within logarithmic factors in the case of small noise and no long-distance influence on the objective function.

References

[1]

A. Conn, K. Scheinberg, and L. Toint, "Recent progress in unconstrained nonlinear optimization without derivatives," 1997. {Online}. Available: citeseer.ist.psu.edu/conn97recent.html

[2]

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.

Digital Library

[3]

S. Grünewälder, 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

[4]

H.-P. Schwefel, Numerical Optimization of Computer Models. New-York: John Wiley & Sons, 1981, 1995-2nd edition.

Digital Library

[5]

H.-G. Beyer, "Mutate large, but inherit small! On the analysis of mutations in (1,łambda)-ES with noisy fitness data," in Proc. of the 5th Conference on Parallel Problems Solving from Nature, T. Bäck, G. Eiben, M. Schoenauer, and H.-P. Schwefel, Eds. Springer Verlag, 1998, pp. 109--118.

Digital Library

[6]

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.

Digital Library

[7]

D. V. Arnold and H.-G. Beyer, "Local performance of the (1+1)-ES in a noisy environment," IEEE Transactions on Evolutionary Computation, vol. 6, no. 1, pp. 30--41, 2002.

Digital Library

[8]

D. V. Arnold and H. georg Beyer, "Evolution strategies with cumulative step length adaptation on the noisy parabolic ridge," Tech. Rep., 2006.

[9]

U. Hammel and T. Bäck, "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änner, Eds., vol. 866. Jerusalem: springer, 9--14Oct. 1994, pp. 159--168.

Digital Library

[10]

J. M. Fitzpatrick and J. J. Grefenstette, "Genetic algorithms in noisy environments," Machine Learning, vol. 3, pp. 101--120, 1988.

Digital Library

[11]

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/

[12]

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/

[13]

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.

[14]

R. Coulom, P. Rolet, N. Sokolovska, and O. Teytaud, "Handling expensive optimization with large noise," in FOGA, H.-G. Beyer and W. B. Langdon, Eds. ACM, 2011, pp. 61--68.

Digital Library

[15]

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.

Digital Library

[16]

---,"Adaptive Noisy Optimization," in EvoStar 2010, Istambul, Turquie, Feb. 2010. {Online}. Available: http://hal.inria.fr/inria-00459017

Digital Library

[17]

V. Heidrich-Meisner and C. Igel, "Uncertainty handling cma-es for reinforcement learning," in GECCO, F. Rothlauf, Ed. ACM, 2009, pp. 1211--1218.

Digital Library

[18]

L. Devroye, L. Györfi, and G. Lugosi, A probabilistic Theory of Pattern Recognition. Springer, 1997.

[19]

R. Coulom, P. Rolet, N. Sokolovska, and O. Teytaud, "Handling expensive optimization with large noise," in FOGA, H.-G. Beyer and W. B. Langdon, Eds. ACM, 2011, pp. 61--68.

Digital Library

[20]

D. R. Jones, M. Schonlau, and W. J. Welch, "Efficient global optimization of expensive black-box functions," J. of Global Optimization, vol. 13, no. 4, pp. 455--492, 1998.

Digital Library

[21]

J. Villemonteix, E. Vazquez, and E. Walter, "An informational approach to the global optimization of expensive-to-evaluate functions," Journal of Global Optimization, p. 26 pages, 09 2008. {Online}. Available: dx.doi.org/10.1007/s10898-008-9354-2 http://hal-supelec.archives-ouvertes.fr/hal-00354262/en/

Digital Library

[22]

V. Fabian, "Stochastic approximation of minima with improved asymptotic speed," Ann. Math. Statist., vol. 38, no. 1, pp. 191--200, 1967.

[23]

L. Bienaymé, "Considérations à l'appui de la découverte de laplace," Comptes Rendus de l'Académie des Sciences, vol. 37, pp. 309--324, 1853.

[24]

P. Chebyshev, "Sur les valeurs limites des integrales," Math Pure Appl, vol. 19, p. 157--160, 1874.

[25]

A. Markov, "On certain applications of algebraic continued fractions," Ph.D. dissertation, St Petersburg, 2002.

[26]

A. V. D. Vaart and J. Wellner, Weak Convergence and Empirical Processes. Springer series in statistics, 1996.

[27]

O. Teytaud and S. Gelly, "General lower bounds for evolutionary algorithms," in 10th International Conference on Parallel Problem Solving from Nature (PPSN 2006), 2006.

Digital Library

[28]

H. Fournier and O. Teytaud, "Lower bounds for comparison based evolution strategies using vc-dimension and sign patterns," Algorithmica, vol. 59, no. 3, pp. 387--408, 2011.

Digital Library

[29]

A. Auger, "Convergence results for (1,λ)-SA-ES using the theory of φ-irreducible Markov chains," Theoretical Computer Science, vol. 334, no. 1--3, pp. 35--69, 2005.

Digital Library

[30]

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.

[31]

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.

Digital Library

[32]

H.-G. Beyer, The Theory of Evolution Strategies, ser. Natural Computing Series. Springer, Heideberg, 2001.

Digital Library

[33]

H. Chen, "Lower rate of convergence for locating a maximum of a function," Ann. Statist., vol. 16, no. 3, pp. 1330--1334, 1988.

[34]

J. Kiefer and J. Wolfowitz, "Stochastic estimation of the maximum of a regression function," Annals of Mathematical Statistics, vol. 23, no. 3, p. 462--466, 1952.

[35]

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/

[36]

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.

Cited By

Meunier LRakotoarison HWong PRoziere BRapin JTeytaud OMoreau ADoerr C(2022)Black-Box Optimization Revisited: Improving Algorithm Selection Wizards Through Massive BenchmarkingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2021.310818526:3(490-500)Online publication date: Jun-2022
https://doi.org/10.1109/TEVC.2021.3108185
Liu JMoreau APreuss MRapin JRoziere BTeytaud FTeytaud OCoello Coello C(2020)Versatile black-box optimizationProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3389838(620-628)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3389838
Khalidov VOquab MRapin JTeytaud OFriedrich TDoerr CArnold D(2019)Consistent population controlProceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3299904.3340312(116-123)Online publication date: 27-Aug-2019
https://dl.acm.org/doi/10.1145/3299904.3340312
Show More Cited By

Index Terms

Noisy optimization complexity under locality assumption
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization

Recommendations

Interval-based ranking in noisy evolutionary multi-objective optimization

As one of the most competitive approaches to multi-objective optimization, evolutionary algorithms have been shown to obtain very good results for many real-world multi-objective problems. One of the issues that can affect the performance of these ...
A non-parametric statistical dominance operator for noisy multiobjective optimization
SEAL'12: Proceedings of the 9th international conference on Simulated Evolution and Learning

This paper describes and evaluates a new noise-aware dominance operator for evolutionary algorithms to solve the multiobjective optimization problems (MOPs) that contain noise in their objective functions. This operator is designed with the Mann-Whitney ...
First Investigations on Noisy Model-Based Multi-objective Optimization
EMO 2017: 9th International Conference on Evolutionary Multi-Criterion Optimization - Volume 10173

In many real-world applications concerning multi-objective optimization, the true objective functions are not observable. Instead, only noisy observations are available. In recent years, the interest in the effect of such noise in evolutionary multi-...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

FOGA XII '13: Proceedings of the twelfth workshop on Foundations of genetic algorithms XII

January 2013

198 pages

ISBN:9781450319904

DOI:10.1145/2460239

General Chairs:
Frank Neumann
The University of Adelaide, Australia
,
Kenneth De Jong
George Mason University, USA

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 January 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FOGA '13

Sponsor:

SIGEVO

FOGA '13: Foundations of Genetic Algorithms XII

January 16 - 20, 2013

Adelaide, Australia

Acceptance Rates

Overall Acceptance Rate 72 of 131 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
60
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Meunier LRakotoarison HWong PRoziere BRapin JTeytaud OMoreau ADoerr C(2022)Black-Box Optimization Revisited: Improving Algorithm Selection Wizards Through Massive BenchmarkingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2021.310818526:3(490-500)Online publication date: Jun-2022
https://doi.org/10.1109/TEVC.2021.3108185
Liu JMoreau APreuss MRapin JRoziere BTeytaud FTeytaud OCoello Coello C(2020)Versatile black-box optimizationProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3389838(620-628)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3389838
Khalidov VOquab MRapin JTeytaud OFriedrich TDoerr CArnold D(2019)Consistent population controlProceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3299904.3340312(116-123)Online publication date: 27-Aug-2019
https://dl.acm.org/doi/10.1145/3299904.3340312
Lucas SLiu JPerez-Liebana D(2018)The N-Tuple Bandit Evolutionary Algorithm for Game Agent Optimisation2018 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2018.8477869(1-9)Online publication date: Jul-2018
https://doi.org/10.1109/CEC.2018.8477869
Cauwet MTeytaud ONeumann FSutton A(2016)Noisy OptimizationProceedings of the Genetic and Evolutionary Computation Conference 201610.1145/2908812.2908881(1101-1106)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908812.2908881
Astete-Morales SCauwet MTeytaud OHe JJansen TOchoa GZarges C(2015)Evolution Strategies with Additive NoiseProceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII10.1145/2725494.2725500(76-84)Online publication date: 17-Jan-2015
https://dl.acm.org/doi/10.1145/2725494.2725500
Liu JSt-Pierre DTeytaud OArnold D(2014)A mathematically derived number of resamplings for noisy optimizationProceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2598394.2598458(61-62)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2598394.2598458
Cauwet M(2014)Noisy Optimization: Convergence with a Fixed Number of ResamplingsApplications of Evolutionary Computation10.1007/978-3-662-45523-4_49(603-614)Online publication date: 29-Nov-2014
https://doi.org/10.1007/978-3-662-45523-4_49
Astete-Morales SLiu JTeytaud O(2014)Log-log Convergence for Noisy OptimizationArtificial Evolution10.1007/978-3-319-11683-9_2(16-28)Online publication date: 25-Oct-2014
https://doi.org/10.1007/978-3-319-11683-9_2

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten