2016 · 30 citations · 31 references
ComputingComputer ScienceMathematicsAlgorithmsProbability TheoryStatistical ComputingComputational StatisticsMonte Carlo MethodsMonte Carlo SimulationError BoundsFunction DecompositionLower BoundsLower Bounds For Randomized AlgorithmsLower Bounds Of ErrorReproducing Kernel Hilbert SpacesSobolev SpacesUpper Bounds
In this paper, we consider the infinite-dimensional integration problem on weighted reproducing kernel Hilbert spaces with norms induced by an underlying function space decomposition of analysis of variance type. The weights model the relative importance of different groups of variables. We present new randomized multilevel algorithms to tackle this integration problem and prove upper bounds for their randomized error. Furthermore, we provide in this setting the first nontrivial lower error bounds for general randomized algorithms, which, in particular, may be adaptive or nonlinear. These lower bounds show that our multilevel algorithms are optimal. Our analysis refines and extends the analysis provided in [F. J. Hickernell, T. Müller-Gronbach, B. Niu, and K. Ritter, J. Complexity, 26 (2010), pp. 229--254], and our error bounds improve substantially on the error bounds presented there. As an illustrative example, we discuss the unanchored Sobolev space and employ randomized quasi--Monte Carlo multilevel algorithms based on scrambled polynomial lattice rules.
31
N. Aronszajn · Transactions of the American Mathematical Society · 1950 · 5.4K citations · Full text
Multilevel Monte Carlo Path Simulation
Michael B. Giles · Operations Research · 2008 · 1.5K citations
Science · 1989 · 861 citations