Stochastic Simultaneous Optimistic Optimization

Valko, Michal; Carpentier, Alexandra; Munos, Rémi

Document type :

Communication dans un congrès avec actes

Title :

Stochastic Simultaneous Optimistic Optimization

Author(s) :

Valko, Michal [Auteur]

Sequential Learning [SEQUEL]
Carpentier, Alexandra [Auteur]
Statistical Laboratory [Cambridge]
Sequential Learning [SEQUEL]
Munos, Rémi [Auteur]
Sequential Learning [SEQUEL]

Conference title :

International Conference on Machine Learning

City :

Atlanta

Country :

Etats-Unis d'Amérique

Start date of the conference :

2013-06-16

HAL domain(s) :

Statistiques [stat]/Machine Learning [stat.ML]

English abstract : [en]

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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

European Project :

Composing Learning for Artificial Cognitive Systems

Collections :