Lower bounds for the complexity of linear functionals in the randomized setting

Hinrichs (2009) [3] recently studied multivariate integration defined over reproducing kernel Hilbert spaces in the randomized setting and for the normalized error criterion. In particular, he showed that such problems are strongly polynomially tractable if the reproducing kernels are pointwise nonnegative and integrable. More specifically, let n(ran)(epsilon, INTd) be the minimal number of randomized function samples that is needed to compute an epsilon-approximation for the d-variate case of multivariate integration. Hinrichs proved that that n(ran) (epsilon, INTd) <= [pi/2 (1/epsilon)(2)] for all epsilon epsilon (0, 1) and d epsilon N. In this paper we prove that the exponent 2 of epsilon(-1) is sharp for tensor product Hilbert spaces whose univariate reproducing kernel is decomposable and univariate integration is not trivial for the two parts of the decomposition. More specifically we have n(ran) (epsilon, INTd) >= [1/8 (1/epsilon)(2)] for all epsilon epsilon (0, 1) and d >= 2 In epsilon(-1) - In 2/ In alpha(-1) where alpha epsilon [1/2, 1) depends on the particular space.