Randomized complexity of parametric integration and the role of adaption. I: Finite dimensional case

DOI10.1016/J.JCO.2023.101821MaRDI QIDQ6154554zbMATH OpenOpenAlexFDO

Authors

Publication date 15 February 2024

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

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

zbMATH Keywords

algorithmadaptivevector-valued meanrandomizedinformation-based complexitynonadaptive

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Analysis of algorithms and problem complexity (68Q25) Algorithms for approximation of functions (65D15)

Abstract: We study the randomized $n$-th minimal errors (and hence the complexity) of vector valued mean computation, which is the discrete version of parametric integration. The results of the present paper form the basis for the complexity analysis of parametric integration in Sobolev spaces, which will be presented in Part 2. Altogether this extends previous results of Heinrich and Sindambiwe (J. Complexity, 15 (1999), 317--341) and Wiegand (Shaker Verlag, 2006). Moreover, a basic problem of Information-Based Complexity on the power of adaption for linear problems in the randomized setting is solved.

Recommendations

• Randomized complexity of parametric integration and the role of adaption. II: Sobolev spaces
• Complexity of parametric integration in various smoothness classes
• Randomized complexity of mean computation and the adaption problem
• Complexity of Banach space valued and parametric integration

Cites work

• scientific article; zbMATH DE number 3688714 (Why is no real title available?)
• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• scientific article; zbMATH DE number 193625 (Why is no real title available?)
• Can adaption help on the average?
• Complexity of stochastic integration in Sobolev classes
• Convergence of stochastic processes
• Deterministic and stochastic error bounds in numerical analysis
• Information of varying cardinality
• Lower complexity bounds for parametric stochastic Itô integration
• Monte Carlo approximation of weakly singular integral operators
• Monte Carlo complexity of parametric integration
• On adaptive information with varying cardinality for linear problems with elliptically contoured measures
• On the Power of Restricted Monte Carlo Algorithms
• On the complexity of computing the \(L_q\) norm
• On the optimality of linear methods for operator approximation in convex classes of functions
• On the power of adaption
• Optimal Monte Carlo and quantum algorithms for parametric integration.
• Optimal sequential and non-sequential procedures for evaluating a functional
• Optimal stochastic quadrature formulas for convex functions
• Quadrature Formulas for Monotone Functions
• Quantum summation with an application to integration.
• Randomized approximation of Sobolev embeddings. III
• The adaption problem for approximating linear operators
• The randomized information complexity of elliptic PDE
• Tractability of multivariate problems. Volume I: Linear information

Cited in

(4)

• Randomized approximation of summable sequences -- adaptive and non-adaptive
• Randomized complexity of parametric integration and the role of adaption. II: Sobolev spaces
• Homogeneous algorithms and solvable problems on cones
• Randomized complexity of mean computation and the adaption problem

This page was built for publication: Randomized complexity of parametric integration and the role of adaption. I: Finite dimensional case

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