| Paper ID | D2-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.
|
