Black-box optimization of noisy functions with unknown smoothness

Jean-Bastien Grill 1 Michal Valko 1 Rémi Munos 1
1 SEQUEL - Sequential Learning
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : We study the problem of black-box optimization of a function $f$ of any dimension, given function evaluations perturbed by noise. The function is assumed to be locally smooth around one of its global optima, but this smoothness is unknown. Our contribution is an adaptive optimization algorithm, POO or parallel optimistic optimization, that is able to deal with this setting. POO performs almost as well as the best known algorithms requiring the knowledge of the smoothness. Furthermore, POO works for a larger class of functions than what was previously considered, especially for functions that are difficult to optimize, in a very precise sense. We provide a finite-time analysis of POO's performance, which shows that its error after $n$ evaluations is at most a factor of $\sqrt{\ln n}$ away from the error of the best known optimization algorithms using the knowledge of the smoothness.
Type de document :
Communication dans un congrès
Neural Information Processing Systems, Dec 2015, Montréal, Canada
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01222915
Contributeur : Michal Valko <>
Soumis le : vendredi 29 janvier 2016 - 17:30:11
Dernière modification le : jeudi 11 janvier 2018 - 06:27:32

Fichier

grill2015black-box.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01222915, version 3

Collections

Citation

Jean-Bastien Grill, Michal Valko, Rémi Munos. Black-box optimization of noisy functions with unknown smoothness. Neural Information Processing Systems, Dec 2015, Montréal, Canada. 〈hal-01222915v3〉

Partager

Métriques

Consultations de la notice

290

Téléchargements de fichiers

132