Randomized Complexity of Parametric Integration and the Role of Adaption II. Sobolev Spaces

Stefan Heinrich

paper

Randomized Complexity of Parametric Integration and the Role of Adaption II. Sobolev Spaces

arXiv:2306.13499

Abstract

We study the complexity of randomized computation of integrals depending on a parameter, with integrands from Sobolev spaces. That is, for $r, d_{1}, d_{2} \in N$ , $1 \leq p, q \leq \infty$ , $D_{1} = [0, 1]^{d_{1}}$ , and $D_{2} = [0, 1]^{d_{2}}$ we are given $f \in W_{p}^{r} (D_{1} \times D_{2})$ and we seek to approximate $S f = \int_{D_{2}} f (s, t) d t (s \in D_{1}),$ with error measured in the $L_{q} (D_{1})$ -norm. Our results extend previous work of Heinrich and Sindambiwe (J.\ Complexity, 15 (1999), 317--341) for $p = q = \infty$ and Wiegand (Shaker Verlag, 2006) for $1 \leq p = q < \infty$ . Wiegand's analysis was carried out under the assumption that $W_{p}^{r} (D_{1} \times D_{2})$ is continuously embedded in $C (D_{1} \times D_{2})$ (embedding condition). We also study the case that the embedding condition does not hold. For this purpose a new ingredient is developed -- a stochastic discretization technique. The paper is based on Part I, where vector valued mean computation -- the finite-dimensional counterpart of parametric integration -- was studied. In Part I a basic problem of Information-Based Complexity on the power of adaption for linear problems in the randomized setting was solved. Here a further aspect of this problem is settled.

32 pages