All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD2-S4-T3.1
Paper Title Information-Theoretic Bounds for Integral Estimation
Authors Donald Quincy Adams, Adarsh Barik, Jean Honorio, Purdue University, United States
Session D2-S4-T3: IT Bounds on Estimation
Chaired Session: Tuesday, 13 July, 23:00 - 23:20
Engagement Session: Tuesday, 13 July, 23:20 - 23:40
Abstract 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.