Stochastic Simultaneous Optimistic Optimization

Michal Valko 1 Alexandra Carpentier 1, 2 Rémi Munos 1
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal, Inria Lille - Nord Europe
Abstract : 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.
Type de document :
Communication dans un congrès
International Conference on Machine Learning, Jun 2013, Atlanta, United States
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger
Contributeur : Michal Valko <>
Soumis le : jeudi 30 mai 2013 - 16:13:59
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : mardi 3 septembre 2013 - 10:15:22


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00789606, version 2


Michal Valko, Alexandra Carpentier, Rémi Munos. Stochastic Simultaneous Optimistic Optimization. International Conference on Machine Learning, Jun 2013, Atlanta, United States. 〈hal-00789606v2〉



Consultations de la notice


Téléchargements de fichiers