Black-box optimization of noisy functions with unknown smoothness - Archive ouverte HAL Access content directly
Conference Papers Year :

Black-box optimization of noisy functions with unknown smoothness

(1) , (1) , (1, 2)
1
2
Jean-Bastien Grill
  • Function : Author
  • PersonId : 972490
Michal Valko
Rémi Munos
  • Function : Author
  • PersonId : 836863

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.
Fichier principal
Vignette du fichier
grill2015black-box.pdf (585.6 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01222915 , version 1 (31-10-2015)
hal-01222915 , version 2 (01-12-2015)
hal-01222915 , version 3 (29-01-2016)
hal-01222915 , version 4 (02-08-2018)

Identifiers

  • HAL Id : hal-01222915 , version 4

Cite

Jean-Bastien Grill, Michal Valko, Rémi Munos. Black-box optimization of noisy functions with unknown smoothness. Neural Information Processing Systems, 2015, Montréal, Canada. ⟨hal-01222915v4⟩
1054 View
1108 Download

Share

Gmail Facebook Twitter LinkedIn More