When resampling to cope with noise, use median, not mean

Benjamin Doerr, Andrew M. Sutton

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Due to their randomized nature, many nature-inspired heuristics are robust to some level of noise in the fitness evaluations. A common strategy to increase the tolerance to noise is to re-evaluate the fitness of a solution candidate several times and to then work with the average of the sampled fitness values. In this work, we propose to use the median instead of the mean. Besides being invariant to rescalings of the fitness, the median in many situations turns out to be much more robust than the mean. We show that when the noisy fitness is ϵ-concentrated, then a logarithmic number of samples suffice to discover the undisturbed fitness (via the median of the samples) with high probability. This gives a simple metaheuristic approach to transform a randomized optimization heuristics into one that is robust to this type of noise and that has a runtime higher than the original one only by a logarithmic factor. We show further that ϵ-concentrated noise occurs frequently in standard situations. We also provide lower bounds showing that in two such situations, even with larger numbers of samples, the average-resample strategy cannot efficiently optimize the problem in polynomial time.

Original languageEnglish (US)
Title of host publicationGECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery, Inc
Pages242-248
Number of pages7
ISBN (Electronic)9781450361118
DOIs
StatePublished - Jul 13 2019
Event2019 Genetic and Evolutionary Computation Conference, GECCO 2019 - Prague, Czech Republic
Duration: Jul 13 2019Jul 17 2019

Publication series

NameGECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference

Conference

Conference2019 Genetic and Evolutionary Computation Conference, GECCO 2019
CountryCzech Republic
CityPrague
Period7/13/197/17/19

    Fingerprint

Keywords

  • Noisy optimization
  • Running time analysis
  • Theory

Cite this

Doerr, B., & Sutton, A. M. (2019). When resampling to cope with noise, use median, not mean. In GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference (pp. 242-248). (GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference). Association for Computing Machinery, Inc. https://doi.org/10.1145/3321707.3321837