Asymptotic convergence rates for averaging strategies
| Autor: | Iskander Legheraba, Yann Chevaleyre, Laurent Meunier, Olivier Teytaud |
|---|---|
| Přispěvatelé: | Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Facebook AI Research [Paris] (FAIR), Facebook |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Design of experiments Computer Science - Neural and Evolutionary Computing 0102 computer and information sciences 02 engineering and technology Function (mathematics) 01 natural sciences Evolutionary computation Random search Quadratic equation 010201 computation theory & mathematics Optimization and Control (math.OC) Black box Convergence (routing) 0202 electrical engineering electronic engineering information engineering FOS: Mathematics Applied mathematics 020201 artificial intelligence & image processing [INFO]Computer Science [cs] Neural and Evolutionary Computing (cs.NE) [MATH]Mathematics [math] Mathematics - Optimization and Control Arithmetic mean Mathematics |
| Zdroj: | FOGA |
| Popis: | Parallel black box optimization consists in estimating the optimum of a function using $\lambda$ parallel evaluations of $f$. Averaging the $\mu$ best individuals among the $\lambda$ 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 $\lambda$. We validate our theoretical findings with experiments on some standard black box functions. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|