Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition

We study the numerical integration problem for functions with infinitely many variables. The function spaces of integrands we consider are weighted reproducing kernel Hilbert spaces with norms related to the ANOVA decomposition of the integrands. The weights model the relative importance of different groups of variables. We investigate randomized quadrature algorithms and measure their quality by estimating the randomized worst-case integration error.In particular, we provide lower error bounds for a very general class of randomized algorithms that includes non-linear and adaptive algorithms. Furthermore, we propose new randomized changing dimension algorithms (also called multivariate decomposition methods) and present favorable upper error bounds. For product weights and finite-intersection weights our lower and upper error bounds match and show that our changing dimension algorithms are optimal in the sense that they achieve convergence rates arbitrarily close to the best possible convergence rate. As more specific examples, we discuss unanchored Sobolev spaces of different degrees of smoothness and randomized changing dimension algorithms that use as building blocks interlaced scrambled polynomial lattice rules.