## Abstract

We consider approximation of weighted integrals of functions with infinitely many variables in the worst case deterministic and randomized settings. We assume that the integrands f belong to a weighted quasi-reproducing kernel Hilbert space, where the weights have product form and satisfy γ_{j}=O(j^{-β}) for β>1. The cost of computing f(x) depends on the number Act(x) of active coordinates in x and is equal to (Act(x)), where is a given cost function. We prove, in particular, that if the corresponding univariate problem admits algorithms with errors O(n ^{-κ2}), where n is the number of function evaluations, then the ∞-variate problem is polynomially tractable with the tractability exponent bounded from above by max(2κ,2(β-1)) for all cost functions satisfying (d)=O(e^{k·d}), for any k<0. This bound is sharp in the worst case setting if β and κ are chosen as large as possible and (d) is at least linear in d. The problem is weakly tractable even for a larger class of cost functions including (d)=O(e^{k·d}). Moreover, our proofs are constructive.

Original language | English |
---|---|

Pages (from-to) | 505-518 |

Number of pages | 14 |

Journal | Journal of Complexity |

Volume | 27 |

Issue number | 6 |

DOIs | |

State | Published - Dec 2011 |

### Bibliographical note

Funding Information:We would like to thank Michael Gnewuch and Klaus Ritter for valuable comments concerning this paper. We also thank the anonymous reviewers whose remarks helped to improve the presentation. This research is partially supported by a grant from the Ministry of Science and Higher Education of Poland for 2010–2013.

### Funding

We would like to thank Michael Gnewuch and Klaus Ritter for valuable comments concerning this paper. We also thank the anonymous reviewers whose remarks helped to improve the presentation. This research is partially supported by a grant from the Ministry of Science and Higher Education of Poland for 2010–2013.

Funders | Funder number |
---|---|

Ministerstwo Nauki i Szkolnictwa Wyższego |

## Keywords

- Infinite dimensional integration
- Randomization
- Tractability
- Worst case setting

## ASJC Scopus subject areas

- Algebra and Number Theory
- Statistics and Probability
- Numerical Analysis
- General Mathematics
- Control and Optimization
- Applied Mathematics