Optimal importance sampling for the approximation of integrals

We consider optimal importance sampling for approximating integrals I(f)=∫Df(x)ϱ(x)dx of functions ff in a reproducing kernel Hilbert space H⊂L1(ϱ)H⊂L1(ϱ) where ϱϱ is a given probability density on D⊆RdD⊆Rd. We show that there exists another density ωω such that the worst case error of importance sampling with density function ωω is of order n−1/2n−1/2.As a result, for multivariate problems generated from nonnegative kernels we prove strong polynomial tractability of the integration problem in the randomized setting.The density function ωω is obtained from the application of change of density results used in the geometry of Banach spaces in connection with a theorem of Grothendieck concerning 2-summing operators.