| Alexandra Carpentier (Equipe SequeL - INRIA Lille) |
| Adaptive algorithms for Stratified Sampling Monte Carlo |
| Mercredi 30 mai 2012 - 10h30 - Salle séminaire M3-324 |
| Site internet de l'orateur |
| Résumé : |
We consider the problem of estimating the integral of a function f over a domain.
Although no analytic expression for f is available, it is possible to obtain n samples from f, chosen anywhere in the domain. A popular method for computing the integral of the function is to stratify the space in strata and sample points in the strata.
We propose algorithms for returning a stratified estimate of the integral. We prove that those algorithms adapt online the number of samples in each stratum to the amount of variation of the function in the stratum. In particular, this enables to allocate more samples where the function varies more, and be almost as efficient as an "oracle" strategy that has access to the variations of the functions in each stratum.
We also provide some results on (i) how to choose the number of strata in an efficient way and (ii) how to adapt the strata themselves to the specific shape of the function.
We express those results with finite-time bounds on a proxy of the variance of the estimate (returned by the algorithms we present). |
2