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 -