Strong tractability of multivariate integration using quasi-Monte Carlo algorithms

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 Wozniakowski 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 Wozniakowski'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.