Finite-Time Analysis of Stratified Sampling for Monte Carlo - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2011

Finite-Time Analysis of Stratified Sampling for Monte Carlo

Alexandra Carpentier
  • Fonction : Auteur
  • PersonId : 910455
Rémi Munos
  • Fonction : Auteur
  • PersonId : 836863

Résumé

We consider the problem of stratified sampling for Monte-Carlo integration. We model this problem in a multi-armed bandit setting, where the arms represent the strata, and the goal is to estimate a weighted average of the mean values of the arms. We propose a strategy that samples the arms according to an upper bound on their standard deviations and compare its estimation quality to an ideal allocation that would know the standard deviations of the strata. We provide two regret analyses: a distribution-dependent bound $\widetilde O(n^{-3/2})$ that depends on a measure of the disparity of the strata, and a distribution-free bound $\widetilde O(n^{-4/3})$ that does not.

Domaines

Autres [stat.ML]
Fichier principal
Vignette du fichier
mc-ucb_3.pdf (319.56 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00636924 , version 1 (28-10-2011)
inria-00636924 , version 2 (13-01-2012)
inria-00636924 , version 3 (27-02-2012)

Identifiants

  • HAL Id : inria-00636924 , version 3

Citer

Alexandra Carpentier, Rémi Munos. Finite-Time Analysis of Stratified Sampling for Monte Carlo. NIPS - Twenty-Fifth Annual Conference on Neural Information Processing Systems, Dec 2011, Grenade, Spain. ⟨inria-00636924v3⟩
233 Consultations
244 Téléchargements

Partager

Gmail Facebook X LinkedIn More