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

DOI10.1016/J.JCO.2023.101821arXiv2306.13471OpenAlexW4390278196MaRDI QIDQ6154554FDOQ6154554

Authors:

Publication date: 15 February 2024

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

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.

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

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

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)

Cites Work

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

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)