L. Plaskota

Worst case complexity of problems with random information noise

---

Abstract.   We study the worst case complexity of solving problems for which information is partial and contaminated by random noise. It is well know that if information is exact then adaption does not help for solving linear problems, i.e., for approximating linear operators over convex and symmetric sets. On the other hand, randomization can sometimes help significantly. It turns out that for noisy information, adaption may lead to much better approximations than nonadaption, even for linear problems. This holds because, in the presence of noise, adaption is equivalent to randomization. The results obtained are applied to the d-variate integration and $L_\infty$ approximation of functions belonging to Holder and Sobolev classes. Information is given by function evaluations with gaussian noise of variance $\sigma^2$. For exact information, the two problems are intractable since the complexity is proportional to $\varepsilon^{-q}$ where $q$ grows linearly with $d$. For noisy information, the situation is different. For integration, the $\varepsilon$-complexity is of order $\sigma^2/\eps^2$ as $\varepsilon$ goes to zero. Hence the curse of dimensionality is broken due to random noise. For approximation, the complexity is of order $\sigma^2\eps^{-(q+2)}\ln(1/\eps)$, and the problem is intractable also with random noise.

---