Thumbnail

Asymptotic convergence rates for averaging strategies

Meunier, Laurent; Legheraba, Iskander; Chevaleyre, Yann; Teytaud, Olivier (2021), Asymptotic convergence rates for averaging strategies, in Finck, Steffen, Foundations of Genetic Algorithms, ACM - Association for Computing Machinery : New York, NY, p. 1–11. 10.1145/3450218.3477302

View/Open
Type
Communication / Conférence
Date
2021
Conference title
FOGA '21: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms
Conference date
2021-09
Conference country
Austria
Book title
Foundations of Genetic Algorithms
Book author
Finck, Steffen
Publisher
ACM - Association for Computing Machinery
Published in
New York, NY
ISBN
978-1-4503-8352-3
Pages
1–11
Publication identifier
Metadata
Show full item record
Author(s)
Meunier, Laurent
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Legheraba, Iskander
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Chevaleyre, Yann
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Teytaud, Olivier
Abstract (EN)
Parallel black box optimization consists in estimating the optimum of a function using λ parallel evaluations of f. Averaging the μ best individuals among the λ evaluations is known to provide better estimates of the optimum of a function than just picking up the best. In continuous domains, this averaging is typically just based on (possibly weighted) arithmetic means. Previous theoretical results were based on quadratic objective functions. In this paper, we extend the results to a wide class of functions, containing three times continuously differentiable functions with unique optimum. We prove formal rate of convergences and show they are indeed better than pure random search asymptotically in λ. We validate our theoretical findings with experiments on some standard black box functions.
Subjects / Keywords
Black-Box; Randomized Search Heuristics; Design of Experiments; Parallel Optimization; Evolutionary Computation