Adaptive Stratified Sampling for Monte-Carlo integration of Differentiable functions
This addresses a specific computational challenge in numerical integration for researchers in statistics or applied mathematics, but appears incremental as it builds on existing stratified sampling methods.
The paper tackles the problem of adaptive stratified sampling for Monte Carlo integration of differentiable functions with a finite number of evaluations, proposing a scheme that samples more in oscillatory regions while ensuring good spread. It proves the estimate is nearly as accurate as an optimal oracle strategy and provides a finite-sample analysis.
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 similarly accurate as the estimate that an optimal oracle strategy (that would know the variations of the function everywhere) would return, and provide a finite-sample analysis.