Optimal importance sampling for the approximation of integrals

AbstractWe consider optimal importance sampling for approximating integrals I(f)=∫Df(x)ϱ(x)dx of functions f in a reproducing kernel Hilbert space H⊂L1(ϱ) where ϱ is a given probability density on D⊆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/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