2024-02-25T17:36:55Z
https://soar-ir.repo.nii.ac.jp/oai
oai:soar-ir.repo.nii.ac.jp:00017837
2022-12-14T04:30:47Z
1221:1222
Analysis of runtime of optimization algorithms for noisy functions over discrete codomains
Akimoto, Youhei
Astete-Morales, Sandra
Teytaud, Olivier
Discrete optimization
Additive noise
Runtime analysis
We consider in this work the application of optimization algorithms to problems over discrete codomains corrupted by additive unbiased noise. We propose a modification of the algorithms by repeating the fitness evaluation of the noisy function sufficiently so that, with a fix probability, the function evaluation on the noisy case is identical to the true value. If the runtime of the algorithms on the noise-free case is known, the number of resampling is chosen accordingly. If not, the number of resampling is chosen regarding to the number of fitness evaluations, in an anytime manner. We conclude that if the additive noise is Gaussian, then the runtime on the noisy case, for an adapted algorithm using resamplings, is similar to the runtime on the noise-free case: we incur only an extra logarithmic factor. If the noise is non-Gaussian but with finite variance, then the total runtime of the noisy case is quadratic in function of the runtime on the noise-free case. (C) 2015 Elsevier B.V. All rights reserved.
Article
THEORETICAL COMPUTER SCIENCE. 605:42-50 (2015)
journal article
ELSEVIER SCIENCE BV
2015-11-15
application/pdf
THEORETICAL COMPUTER SCIENCE
605
42
50
0304-3975
AA00862688
https://soar-ir.repo.nii.ac.jp/record/17837/files/Analysis_runtime_optimization_algorithms_noisy_functions.pdf
eng
10.1016/j.tcs.2015.04.008
https://doi.org/10.1016/j.tcs.2015.04.008
© 2015. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/