Information-Theoretic Bounds for Integral Estimation
  In this paper, we consider a zero-order stochastic oracle model of estimating
definite integrals. In this model, integral estimation methods may query an
oracle function for a fixed number of noisy values of the integrand function
and use these values to produce an estimate of the integral. We first show that
the information-theoretic error lower bound for estimating the integral of a
$d$-dimensional function over a region with $l_\infty$ radius $r$ using at most
$T$ queries to the oracle function is $\Omega(2^d r^{d+1}\sqrt{d/T})$.
Additionally, we find that the Gaussian Quadrature method under the same model
achieves a rate of $O(2^{d}r^d/\sqrt{T})$ for functions with zero fourth and
higher-order derivatives with respect to individual dimensions, and for
Gaussian oracles, this rate is tight. For functions with nonzero fourth
derivatives, the Gaussian Quadrature method achieves an upper bound which is
not tight with the information-theoretic lower bound. Therefore, it is not
minimax optimal, so there is space for the development of better integral
estimation methods for such functions.
