Multivariate integration for analytic functions with Gaussian kernels

This is the authors' abstract. We don't add key points for this paper.

We study multivariate integration of analytic functions defined on R d R^d . These functions are assumed to belong to a reproducing kernel Hilbert space whose kernel is Gaussian, with nonincreasing shape parameters. We prove that a tensor product algorithm based on the univariate Gauss-Hermite quadrature rules enjoys exponential convergence and computes an ε ε -approximation for the d d -variate integration using an order of ( ln ε − 1 ) d (ln \,ε ⁻¹)^d function values as ε ε goes to zero. We prove that the exponent d d is sharp by proving a lower bound on the minimal (worst case) error of any algorithm based on finitely many function values. We also consider four notions of tractability describing how the minimal number n ( ε , d ) n(ε ,d) of function values needed to find an ε ε -approximation in the d d -variate case behaves as a function of d d and ln ε − 1 ln \,ε ⁻¹ . One of these notions is new. In particular, we prove that for all positive shape parameters, the minimal number n ( ε , d ) n(ε ,d) is larger than any polynomial in