Lower Error Bounds for Randomized Multilevel and Changing Dimension Algorithms

Abstract We provide lower error bounds for randomized algorithms that approx-imate integrals of functions depending on an unrestricted or even infinite number of variables. More precisely, we consider the infinite-dimensional integration prob-lem on weighted Hilbert spaces with an underlying anchored decomposition and arbitrary weights. We focus on randomized algorithms and the randomized worst case error. We study two cost models for function evaluation which depend on the number of active variables of the chosen sample points. Multilevel algorithms be-have very well with respect to the first cost model, while changing dimension algo-rithms and also dimension-wise quadrature methods, which are based on a similar idea, can take advantage of the more generous second cost model. We prove the first non-trivial lower error bounds for randomized algorithms in these cost mod-els and demonstrate their quality in the case of product weights. In particular, we show that the randomized changing dimension algorithms provided in [L. Plaskota, G. W. Wasilkowski, J. Complexity 27 (2011), 505–518] achieve convergence rates arbitrarily close to the optimal convergence rate.