Tractability of infinite-dimensional integration in the worst case and randomized settings

AbstractWe consider approximation of weighted integrals of functions with infinitely many variables in the worst case deterministic and randomized settings. We assume that the integrands f belong to a weighted quasi-reproducing kernel Hilbert space, where the weights have product form and satisfy γj=O(j−β) for β>1. The cost of computing f(x) depends on the number Act(x) of active coordinates in x and is equal to $(Act(x)), where $ is a given cost function. We prove, in particular, that if the corresponding univariate problem admits algorithms with errors O(n−κ/2), where n is the number of function evaluations, then the ∞-variate problem is polynomially tractable with the tractability exponent bounded from above by max(2/κ,2/(β−1)) for all cost functions satisfying $(d)=O(ek⋅d), for any k≥0. This bound is sharp in the worst case setting if β and κ are chosen as large as possible and $(d) is at least linear in d. The problem is weakly tractable even for a larger class of cost functions including $(d)=O(eek⋅d). Moreover, our proofs are constructive