Session III.5 - Information-Based Complexity
Tuesday, June 20, 14:30 ~ 15:00
On the Role of Adaption in Linear Problems
Stefan Heinrich
RPTU Kaiserslautern-Landau, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
The relation between $n$-th minimal errors of linear problems in the randomized non--adaptive and adaptive setting is studied. In a recent paper [1] the author solved a long-standing problem of Information-Based Complexity: Is there a constant $c \gt 0$ such that for all linear problems $\mathcal{P}$ the randomized non-adaptive and adaptive $n$-th minimal errors can deviate at most by the factor $c$? That is, does the following hold for all linear $\mathcal{P}$ and $n\in {\bf N}$ \[ e_n^{\rm ran-non} (\mathcal{P})\le ce_n^{\rm ran} (\mathcal{P}) \,? \] The analysis of vector-valued mean computation showed that the answer is negative. In this talk we discuss further aspects of this problem: large gaps between adaptive and non-adaptive minimal errors [2], infinite dimensional problems with deviation tending to infinity with $n$, as well as scalar-valued problems: mean computation and integration.
References
[1] S. Heinrich, Randomized Complexity of Parametric Integration and the Role of Adaption I. Finite Dimensional Case, preprint, see https://www.uni-kl.de/AG-Heinrich/Publications.html
[2] S. Heinrich, Randomized Complexity of Vector-Valued Approximation, to appear in: A. Hinrichs, P. Kritzer, F. Pillichshammer (eds.). Monte Carlo and Quasi-Monte Carlo Methods 2022. Springer Verlag. Preprint see https://www.uni-kl.de/AG-Heinrich/Publications.html