Minimax Number of Strata for Online Stratified Sampling given Noisy Samples

Alexandra Carpentier 1 Rémi Munos 1
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : We consider the problem of online stratified sampling for Monte Carlo integration of a function given a finite budget of $n$ noisy evaluations to the function. More precisely we focus on the problem of choosing the number of strata $K$ as a function of the budget $n$. We provide asymptotic and finite-time results on how an oracle that has access to the function would choose the partition optimally. In addition we prove a \textit{lower bound} on the learning rate for the problem of stratified Monte-Carlo. As a result, we are able to state, by improving the bound on its performance, that algorithm MC-UCB, defined in~\citep{MC-UCB}, is minimax optimal both in terms of the number of samples n and the number of strata K, up to a $\sqrt{\log(nK)}$. This enables to deduce a minimax optimal bound on the difference between the performance of the estimate outputted by MC-UCB, and the performance of the estimate outputted by the best oracle static strategy, on the class of Hölder continuous functions, and upt to a $\sqrt{\log(n)}$.
Type de document :
Pré-publication, Document de travail
2012
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00698517
Contributeur : Alexandra Carpentier <>
Soumis le : mercredi 16 mai 2012 - 16:20:00
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : jeudi 15 décembre 2016 - 08:13:59

Fichiers

FixedStrata.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00698517, version 1
  • ARXIV : 1205.4095

Collections

Citation

Alexandra Carpentier, Rémi Munos. Minimax Number of Strata for Online Stratified Sampling given Noisy Samples. 2012. 〈hal-00698517〉

Partager

Métriques

Consultations de la notice

414

Téléchargements de fichiers

234