Finite-order weights imply tractability of multivariate integration (Q1883584)

The multivariate integration of high dimension \(s\) is discussed in the context of tractability and strong tractability of quasi-Monte Carlo algorithms. Although the number of input variables can be very large it is often observed in such problems that functions mainly depend on groups of just a few variables at a time. Such an example is computational finance, where the dimensions of hundreds or thousands are common. In this case the classical integration rules such as trapezoidal rule, Simpson's rule, Gaussian rule, etc., are not efficient, whereas Monte Carlo (MC) and quasi-Monte Carlo (QMC) algorithms are more succesful. These algorithms take the average of function values over either random (MC) or deterministic (QMC) set of points \(P_n:=\{ {\mathbf x}_0, {\mathbf x}_1, \ldots , {\mathbf x}_{n-1} \}\). The basic question is how the minimal number of function values \(n\) needed to reduce the initial error by a factor \(\varepsilon\) depends on \(s\) and \(\varepsilon^{-1}\). The strong tractability implies no dependence on \(s\) and only polynomial dependence on \(\varepsilon^{-1}\), whereas polynomial dependence on both \(s\) and \(\varepsilon^{-1}\) implies tractability. Tractability usually does not hold in Hilbert spaces such as classical Sobolev and Korobov spaces where all variables play the same role. To obtain tractability, weighted Sobolev and Korobov spaces are considered. Besides, the considered ones are reproducing kernel Hilbert spaces. The existence of efficient QMC algorithms for anchored and unanchored Sobolev kernels is considered. In the case of anchored Sobolev space, the strong tractability is proven for arbitrary finite order weights. In the case of unanchored Sobolev space the tractability is shown for all bounded finite order weights. In both cases the dependence on \(\varepsilon^{-1}\) is quadratic. For finite order weights, almost linear dependence on \(\varepsilon^{-1}\) can be achieved at the expese of polynomial dependence on \(s\) whose degree then is proportional to the order of the weights. It is shown that these tractability bounds can be achieved by shifted lattice rules with generators computed by the component-by-component algorithm. Other QMC algorithms, which use low discrepancy sequences such as Halton, Sobol, and Niederreiter sequences, also are considered, showing that these sequences allow to achieve similar bounds. The error bounds for the actual QMC methods are evaluated and explicit worst-case error bounds for shifted lattice rules and for the Niederreiter sequence are presented. Conditions on general weights are presented that guarantee tractability and strong tractability of multivariate integration.