Stochastic Simultaneous Optimistic Optimization - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2013

Stochastic Simultaneous Optimistic Optimization

Michal Valko
Rémi Munos
  • Fonction : Auteur
  • PersonId : 836863

Résumé

We study the problem of global maximization of a function f given a finite number of evaluations perturbed by noise. We consider a very weak assumption on the function, namely that it is locally smooth (in some precise sense) with respect to some semi-metric, around one of its global maxima. Compared to previous works on bandits in general spaces (Kleinberg et al., 2008; Bubeck et al., 2011a) our algorithm does not require the knowledge of this semi-metric. Our algorithm, StoSOO, follows an optimistic strategy to iteratively construct upper confidence bounds over the hierarchical partitions of the function domain to decide which point to sample next. A finite-time analysis of StoSOO shows that it performs almost as well as the best specifically-tuned algorithms even though the local smoothness of the function is not known.
Fichier principal
Vignette du fichier
paper.pdf (569.52 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00789606 , version 1 (15-04-2013)
hal-00789606 , version 2 (30-05-2013)

Identifiants

  • HAL Id : hal-00789606 , version 2

Citer

Michal Valko, Alexandra Carpentier, Rémi Munos. Stochastic Simultaneous Optimistic Optimization. International Conference on Machine Learning, Jun 2013, Atlanta, United States. ⟨hal-00789606v2⟩
807 Consultations
455 Téléchargements

Partager

Gmail Facebook X LinkedIn More