Strong tractability of multivariate integration using quasi–Monte Carlo algorithms

Abstract:

We study quasi–Monte Carlo algorithms based on low discrepancy sequences for multivariate integration. We consider the problem of how the minimal number of function evaluations needed to reduce the worst-case error from its initial error by a factor of $\varepsilon$ depends on ${\varepsilon }^{-1}$ and the dimension $s$. Strong tractability means that it does not depend on $s$ and is bounded by a polynomial in ${\varepsilon }^{-1}$. The least possible value of the power of ${\varepsilon }^{-1}$ is called the $\varepsilon$-exponent of strong tractability. Sloan and Woźniakowski established a necessary and sufficient condition of strong tractability in weighted Sobolev spaces, and showed that the $\varepsilon$-exponent of strong tractability is between 1 and 2. However, their proof is not constructive. In this paper we prove in a constructive way that multivariate integration in some weighted Sobolev spaces is strongly tractable with $\varepsilon$-exponent equal to 1, which is the best possible value under a stronger assumption than Sloan and Woźniakowski’s assumption. We show that quasi–Monte Carlo algorithms using Niederreiter’s $(t,s)$-sequences and Sobol sequences achieve the optimal convergence order $O(N^{-1+\delta })$ for any $\delta >0$ independent of the dimension with a worst case deterministic guarantee (where $N$ is the number of function evaluations). This implies that strong tractability with the best $\varepsilon$-exponent can be achieved in appropriate weighted Sobolev spaces by using Niederreiter’s $(t,s)$-sequences and Sobol sequences.