Randomized complexity of parametric integration and the role of adaption. II: Sobolev spaces

DOI10.1016/J.JCO.2023.101823MaRDI QIDQ6193948zbMATH OpenOpenAlexFDO

Authors

Publication date 19 March 2024

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2306.13499

zbMATH Keywords

adaptivealgorithminformation-based complexitynonadaptiveparametric integrationrandomized

Mathematics Subject Classification ID

Algorithms for approximation of functions (65D15) Numerical integration (65D30) Numerical analysis in abstract spaces (65J99) Analysis of algorithms and problem complexity (68Q25)

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}inmathbbN$, $1lep,qleinfty$, $D_1=[0,1{]}^{d_1}$, and $D_2=[0,1{]}^{d_2}$ we are given $fin{W}_p^r(D_{1}imes{D}_2)$ and we seek to approximate ${\displaystyle }$ Sf=int_{D_2}f(s,t)dtquad (sin D_1), ${\displaystyle }$ 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 $1lep=q<infty$. Wiegand's analysis was carried out under the assumption that $W_p^r(D_{1}imes{D}_2)$ is continuously embedded in $C(D_{1}imes{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.

Recommendations

• Randomized complexity of parametric integration and the role of adaption. I: Finite dimensional case
• Complexity of stochastic integration in Sobolev classes
• Complexity of Sobolev imbeddings and integration in the deterministic and randomized settings
• Randomized approximation of Sobolev embeddings
• Randomized approximation of Sobolev embeddings. II

Cites work

• scientific article; zbMATH DE number 3491650 (Why is no real title available?)
• scientific article; zbMATH DE number 2051207 (Why is no real title available?)
• Monte Carlo complexity of parametric integration
• On the power of adaption
• Optimal error bound of restricted Monte Carlo integration on anisotropic Sobolev classes
• Optimal integration error on anisotropic classes for restricted Monte Carlo and quantum algorithms
• Optimal Monte Carlo and quantum algorithms for parametric integration.
• Quantum approximation. II: Sobolev embeddings
• Quantum integration in Sobolev classes
• Randomized approximation of Sobolev embeddings
• Randomized complexity of parametric integration and the role of adaption. I: Finite dimensional case
• Stochastic approximation of functions and applications
• The randomized information complexity of elliptic PDE
• Tractability of multivariate problems. Volume I: Linear information

Cited in

(8)

• Randomized complexity of parametric integration and the role of adaption. I: Finite dimensional case
• Homogeneous algorithms and solvable problems on cones
• Randomized complexity of mean computation and the adaption problem
• Randomized approximation of summable sequences -- adaptive and non-adaptive
• Uniform approximation of vectors using adaptive randomized information
• On the power of adaption and randomization
• Approximation of functions: optimal sampling and complexity
• Adaptive and non-adaptive randomized approximation of high-dimensional vectors

This page was built for publication: Randomized complexity of parametric integration and the role of adaption. II: Sobolev spaces

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