TY - GEN

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

AU - Doerr, Benjamin

AU - Sutton, Andrew M.

PY - 2019/7/13

Y1 - 2019/7/13

N2 - 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.

AB - 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.

KW - Noisy optimization

KW - Running time analysis

KW - Theory

UR - http://www.scopus.com/inward/record.url?scp=85071398049&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85071398049&partnerID=8YFLogxK

U2 - 10.1145/3321707.3321837

DO - 10.1145/3321707.3321837

M3 - Conference contribution

AN - SCOPUS:85071398049

T3 - GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference

SP - 242

EP - 248

BT - GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference

PB - Association for Computing Machinery, Inc

T2 - 2019 Genetic and Evolutionary Computation Conference, GECCO 2019

Y2 - 13 July 2019 through 17 July 2019

ER -