Tractability of infinite-dimensional integration in the worst case and randomized settings

L. Plaskota, G. W. Wasilkowski

Research output: Contribution to journalArticlepeer-review

37 Scopus citations


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(ek·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(ek·d). Moreover, our proofs are constructive.

Original languageEnglish
Pages (from-to)505-518
Number of pages14
JournalJournal of Complexity
Issue number6
StatePublished - 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.


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

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Statistics and Probability
  • Numerical Analysis
  • Mathematics (all)
  • Control and Optimization
  • Applied Mathematics


Dive into the research topics of 'Tractability of infinite-dimensional integration in the worst case and randomized settings'. Together they form a unique fingerprint.

Cite this