View abstract

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.


[1] S. Heinrich, Randomized Complexity of Parametric Integration and the Role of Adaption I. Finite Dimensional Case, preprint, see

[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

View abstract PDF