Randomized Complexity of Vector-Valued Approximation

MaRDI QIDQ6441303zbMATH OpenFDO

Authors Stefan Heinrich

Publication date 23 June 2023

Abstract: We study the randomized $n$-th minimal errors (and hence the complexity) of vector valued approximation. In a recent paper by the author [Randomized complexity of parametric integration and the role of adaption I. Finite dimensional case (preprint)] a long-standing problem of Information-Based Complexity was solved: Is there a constant $c>0$ such that for all linear problems $mathcalP$ the randomized non-adaptive and adaptive $n$-th minimal errors can deviate at most by a factor of $c$? That is, does the following hold for all linear $mathcalP$ and $ninmathbbN$ �egin{equation*} e_n^{ m ran-non} (mathcal{P})le ce_n^{ m ran} (mathcal{P}) , {�f ?} end{equation*} The analysis of vector-valued mean computation showed that the answer is negative. More precisely, there are instances of this problem where the gap between non-adaptive and adaptive randomized minimal errors can be (up to log factors) of the order $n^{1/8}$. This raises the question about the maximal possible deviation. In this paper we show that for certain instances of vector valued approximation the gap is $n^{1/2}$ (again, up to log factors).

This page was built for publication: Randomized Complexity of Vector-Valued Approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6441303)