# Information-Theoretic Bounds for Integral Estimation

arXiv: https://arxiv.org/abs/2102.10199 · HTML: https://mlsanity.com/paper/2102.10199/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 9 references that are in the map.
- First posted on arXiv 19 Feb 2021.

## Builds on (most cited first, 2 of 2)

- [Information-theoretic Limits for Community Detection in Network Models](https://mlsanity.com/paper/1802.06104/) (2018)
- [On the Information Theoretic Limits of Learning Ising Models](https://mlsanity.com/paper/1411.1434/) (2014)

## Abstract (arXiv)

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_∞ radius r using at most T queries to the oracle function is Omega(2d rd+1√d/T). Additionally, we find that the Gaussian Quadrature method under the same model achieves a rate of O(2drd/√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.