Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition (Q2016136)

The authors study numerical integration problems for functions with infinitely many variables. An important tool is the analysis of variance (ANOVA) decomposition of the integrand. The paper extends the analysis of convergence rates of random multilevel algorithms (a.o. quasi-Monte Carlo methods) started in [\textit{F. J. Hickernell} et al., J. Complexity 26, No. 3, 229--254 (2010; Zbl 1207.65005)] and [\textit{J. Baldeaux} and \textit{M. Gnewuch}, SIAM J. Numer. Anal. 52, 1128--1155 (2014)]. The layout of the paper, as indicated in the introduction, is given below: \S 1: Introduction (\(2 {1\over 2}\) pages) \qquad A thorough discussion of the background material and previous results \S 2: Preliminaries (\(9\) pages) \qquad Introduction of weights, function spaces, cost and error criteria and algorithms \S 3: Lower error bounds (\(2 {1\over 2}\) pages) \qquad Provides a.o. lower bounds for the error (cf. Theorem 1.1) \S 4: Changing dimension algorithms (\(9\) pages) \qquad The bound given before is shown to be sharp for finite-intersection and product weights (an upper bound is given, along with sharp upper error bounds) \S 5: Examples: unanchored Sobolev spaces and interlaced scrambled polynomial lattice rules (\(5\) pages) \qquad Unanchored Sobolev spaces of smoothness \(\xi\geq 1\) are studied and it is shown that the optimal rate of convergence is achieved in case of interlaced scrambled polynomial lattice rules. Appendix (\(3 {1\over 2}\) pages) \qquad Embedding between spaces and bounds on a square sum of Walsh coefficients for the functions studied in \S 5 are given.