Adaptive Stratified Sampling for Monte-Carlo integration of Differentiable functions
We consider the problem of adaptive stratified sampling for Monte Carlo integration of a differentiable function given a finite number of evaluations to the function. We construct a sampling scheme that samples more often in regions where the function oscillates more, while allocating the samples such that they are well spread on the domain (this notion shares similitude with low discrepancy). We prove that the estimate returned by the algorithm is almost as accurate as the estimate that an optimal oracle strategy (that would know the variations of the function everywhere) would return, and we provide a finite-sample analysis.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Finite Time Analysis of Stratified Sampling for Monte Carlo
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 th…
On the Sampling Problem for Kernel Quadrature
The standard Kernel Quadrature method for numerical integration with random point sets (also called Bayesian Monte Carlo) is known to converge in root mean square error at a rate determined by the ratio $s/d$, where $s$ …
Numerical IntegrationSampling Algorithms, from Survey Sampling to Monte Carlo Methods: Tutorial and Literature Review
This paper is a tutorial and literature review on sampling algorithms. We have two main types of sampling in statistics. The first type is survey sampling which draws samples from a set or population. The second type is …
Survey SamplingUsing Stratified Sampling to Improve LIME Image Explanations
We investigate the use of a stratified sampling approach for LIME Image, a popular model-agnostic explainable AI method for computer vision tasks, in order to reduce the artifacts generated by typical Monte Carlo samplin…
Explanation GenerationSpatial Monte Carlo Integration with Annealed Importance Sampling
Evaluating expectations on an Ising model (or Boltzmann machine) is essential for various applications, including statistical machine learning. However, in general, the evaluation is computationally difficult because it …