Optimally Adaptive Integration of Univariate Lipschitz Functions

Autor: Erik D. Demaine, Dmitriy Katz, Ilya Baran
Rok vydání: 2007
Předmět:
Zdroj: Algorithmica. 50:255-278
ISSN: 1432-0541
0178-4617
Popis: 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 e 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 ${\rm DOPT}$ and ${\rm ROPT}$, the performances of the best possible deterministic and randomized algorithms, respectively. We give a deterministic algorithm that uses $O({\rm DOPT}(f,\epsilon)\cdot\log(\epsilon^{-1}/{\rm DOPT}(f,\epsilon)))$ samples and show that an asymptotically better algorithm is impossible. However, any deterministic algorithm requires $\Omega({\rm ROPT}(f,\epsilon)^{2})$ 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 $O({\rm ROPT}(f,\epsilon)^{4/3}+{\rm ROPT}(f,\epsilon)\cdot\log(1/\epsilon))$ samples. We also show that any algorithm requires $\Omega({\rm ROPT}(f,\epsilon)^{4/3}+{\rm ROPT}(f,\epsilon)\cdot\log(1/\epsilon))$ samples in expectation on some problem instance (f,e), which proves that our algorithm is optimal.
Databáze: OpenAIRE
Externí odkaz: