|| Information-Theoretic Bounds for Integral Estimation
||Donald Quincy Adams, Adarsh Barik, Jean Honorio, Purdue University, United States|
||D2-S4-T3: IT Bounds on Estimation
||Tuesday, 13 July, 23:00 - 23:20
||Tuesday, 13 July, 23:20 - 23:40
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 will 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 ∞-norm radius r using at most T queries to the oracle function is Ω(2^d r^(d+1) √(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.