When Are Quasi-Monte Carlo Algorithms Efficient for High Dimensional Integrals?

By Ian H. Sloan, Henryk Wozniakowski. 1998

Recently, quasi-Monte Carlo algorithms have been successfully used for multivariate integration of high dimensiond, and were significantly more efficient than Monte Carlo algorithms. The existing theory of the worst case error bounds of quasi-Monte Carlo algorithms does not explain this phenomenon. This paper presents a partial answer to why quasi-Monte Carlo algorithms can work well for arbitrarily larged. It is done by identifying classes of functions for which the effect of the dimensiondis negligible. These areweightedclasses in which the behavior in the successive dimensions is moderated by a sequence of weights. We prove that the minimalworst caseerror of quasi-Monte Carlo algorithms does not depend on the dimensiondiff the sum of the weights is finite. We also prove that the minimal number of function values in the worst case setting needed to reduce the initial error by ? is bounded byC??p, where the exponentp? 1, 2], andCdepends exponentially on the sum of weights. Hence, the relatively small sum of the weights makes some quasi-Monte Carlo algorithms strongly tractable. We show in a nonconstructive way that many quasi-Monte Carlo algorithms are strongly tractable. Even random selection of sample points (done once for the whole weighted class of functions and then the worst case error is established for that particular selection, in contrast to Monte Carlo where random selection of sample points is carried out for a fixed function) leads to strong tractable quasi-Monte Carlo algorithms. In this case the minimal number of function values in theworst casesetting is of order ??pwith the exponentp= 2. The deterministic construction of strongly tractable quasi-Monte Carlo algorithms as well as the minimal exponentpis open.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels (2014, background): “However, several authors noticed that QMC methods perform better than MC even for very highdimensional integration [Sloan and Wozniakowski, 1998, Dick et al., 2013]2.”
Fixed and Random Effects in Nonlinear Models (2001, background): “A number of such strategies is surveyed in Bhat (1999), Sloan and Wozniakowski (1998) and Morokoff and Caflisch (1995).”
A multi-level cross-classified model for discrete response variables (2000, methodology): “…Carlo simulation methods for multi-dimensional integration has been receiving substantial attention in recent years with increasingly sophisticated quasirandom sequences being proposed (see, for example, Sloan and Wozniakowski, 1998; Owen, 1998; Mullen et al., 1995; Kocis and Whiten, 1997).”
TT-GMRES: on solution to a linear system in the structured tensor format (2012, unknown): “Such problems are posed, for example, in quantum chemistry [1,2], financial mathematics [3,4] and many others.”
Discrete Choice Methods with Simulation by Kenneth E. Train (2003, background): “We demonstrate this identity in the last section of this chapter; Theil (1971) and Ruud (2000) also provide useful and heuristic proofs.”
Constructing Sobol Sequences with Better Two-Dimensional Projections (2008, methodology): “One way to model the relative importance between variables or groups of variables is to introduce weights following Sloan and Woźniakowski [22] (see [21] for a more general setting).”
Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration (2010, methodology): “6 Weighted discrepancy Apart from the classical concept of discrepancy there is also the idea of weighted discrepancy as introduced by Sloan & Woźniakowski [247], who observed that different coordinates may have different influence on the quality of approximation of an integral by a QMC rule.”
Randomized Halton sequences (2000, unknown): “Based on the these arguments and the results of [18], we may expect improvement from the integrands of type (i) to type (iv).”
Monte Carlo and Quasi-Monte Carlo Sampling (2009, background): “and since it can be shown that for this class of functions, we have [372]”
DMRG Approach to Fast Linear Algebra in the TT-Format (2011, background): “Tensors arise naturally in high-dimensional problems, for example, in quantum chemistry [1, 2], financial mathematics [3, 4], and in many other areas.”
Halton Sequences for Mixed Logit (2000, methodology): “Numerous procedures have been proposed in the numerical analysis literature for taking “intelligent” draws from a distribution rather than random ones (see, e.g., Sloan and Wozniakowski, 1998; Morokoff and Caflisch, 1995.)”