A random integration algorithm for high-dimensional function spaces

We introduce a novel random integration algorithm that exhibits a high convergence order for functions characterized by sparse frequencies or rapidly decaying Fourier coefficients. Specifically, for integration in periodic isotropic Sobolev spaces and isotropic Sobolev spaces with compact support, our approach achieves a nearly optimal root mean square error bound. In contrast to previous nearly optimal algorithms, our method exhibits polynomial tractability. Our integration algorithm also enjoys nearly optimal bound for weighted Sobolev space. By incorporating the trick of change of variable, our algorithm is proven to achieve the semi-exponential convergence order for the integration of analytic functions, which marks a significant improvement over the previously obtained super-polynomial convergence order. Furthermore, for integration involving Wiener-type functions, the sample complexity of our algorithm remains independent of the decay rate of the Fourier coefficients.