Randomizing the trapezoidal rule gives the optimal RMSE rate in Gaussian Sobolev spaces

2022/12/22 by Goda, Takashi, Kazashi, Yoshihito, Suzuki, Yuya · 1 citation
#FOS: Mathematics #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.2212.11476

Abstract

Randomized quadratures for integrating functions in Sobolev spaces of order α≥ 1, where the integrability condition is with respect to the Gaussian measure, are considered. In this function space, the optimal rate for the worst-case root-mean-squared error (RMSE) is established. Here, optimality is for a general class of quadratures, in which adaptive non-linear algorithms with a possibly varying number of function evaluations are also allowed. The optimal rate is given by showing matching bounds. First, a lower bound on the worst-case RMSE of O(n^-α-1/2) is proven, where n denotes an upper bound on the expected number of function evaluations. It turns out that a suitably randomized trapezoidal rule attains this rate, up to a logarithmic factor. A practical error estimator for this trapezoidal rule is also presented. Numerical results support our theory.

Cited by

• Quasi-Monte Carlo integration over ℝ^s with boundary-damping importance sampling

Related

• Sub-optimality of Gauss--Hermite quadrature and optimality of the trapezoidal rule for functions with finite smoothness
• A randomised trapezoidal quadrature
• Linear Monte Carlo quadrature with optimal confidence intervals
• Optimality of quasi-Monte Carlo methods and suboptimality of the sparse-grid Gauss--Hermite rule in Gaussian Sobolev spaces
• On the Randomization of Frolov's Algorithm for Multivariate Integration