Optimally Adaptive Integration of Univariate Lipschitz Functions |
| |
Authors: | Ilya Baran Erik D Demaine Dmitriy A Katz |
| |
Affiliation: | (1) MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar Street, Cambridge, MA 02139, USA;(2) Sloan School of Management, Massachusetts Institute of Technology, 50 Memorial Drive, Cambridge, MA 02142, USA |
| |
Abstract: | We consider the problem of approximately integrating a Lipschitz function f (with a known Lipschitz constant) over an interval. The goal is to achieve an additive error of at most ε using as few samples of f as possible. We use the adaptive framework: on all problem instances an adaptive algorithm should perform almost as well
as the best possible algorithm tuned for the particular problem instance. We distinguish between
and
, the performances of the best possible deterministic and randomized algorithms, respectively. We give a deterministic algorithm
that uses
samples and show that an asymptotically better algorithm is impossible. However, any deterministic algorithm requires
samples on some problem instance. By combining a deterministic adaptive algorithm and Monte Carlo sampling with variance reduction,
we give an algorithm that uses at most
samples. We also show that any algorithm requires
samples in expectation on some problem instance (f,ε), which proves that our algorithm is optimal. |
| |
Keywords: | Adaptive algorithms Lipschitz functions |
本文献已被 SpringerLink 等数据库收录! |
|