How much randomness is needed for high-confidence Monte Carlo integration?
Robert J. Kunsch  1@  , Daniel Rudolf@
1 : RWTH Aachen University

We study Monte Carlo methods for integrating smooth d-variate functions based on n function evaluations.

In terms of the root mean squared error (RMSE), methods providing optimal error rates for integrating functions from classical Sobolev Spaces as well as Sobolev Spaces of dominating mixed smoothness are well known. One of the recent methods with optimal error rates is based on a randomly shifted and dilated Frolov grid and requires only very few random numbers, namely 2d random numbers, irrespective of n.

If, however, the error is measured in terms of small error with high probability, the so-called probabilistic error criterion, the latter method is suboptimal. In classical Sobolev spaces, methods with high confidence, i.e. optimal probabilistic error, combine control variates with the median-of-means, or exploit concentration of mass in the case of stratified sampling; in any event, the amount of random numbers in such optimal methods needs to grow with n.

This raises the question: How small can the probabilistic error be if we limit the amount of randomness? Restricted Monte Carlo methods that only use a small amount of random bits have already been studied for the RMSE criterion. A similar study for the probabilistic error criterion of restricted Monte Carlo methods will be presented.

  • Autre
Personnes connectées : 2 Vie privée