Optimality of Quasi-Monte Carlo Methods and Suboptimality of the Sparse-Grid Gauss–Hermite Rule in Gaussian Sobolev Spaces

Abstract

Abstract. Optimality of several quasi-Monte Carlo methods and suboptimality of the sparse-grid quadrature based on the univariate Gauss–Hermite rule are proved in the Sobolev spaces of mixed dominating smoothness of order [Formula: see text], where the optimality is in the sense of worst-case convergence rate. For sparse-grid Gauss–Hermite quadrature, lower and upper bounds are established, with rates coinciding up to a logarithmic factor. This common algebraic rate is found to be only [Formula: see text] with [Formula: see text] function evaluations, although the optimal rate is known to be [Formula: see text]. The lower bound is obtained by exploiting the structure of the Gauss–Hermite nodes and is independent of the quadrature weights; consequently, no modification of the weights can improve the rate [Formula: see text]. In contrast, several quasi-Monte Carlo methods with a change of variables are shown to achieve the optimal rate, some up to, and one including, the logarithmic factor.