Under what circumstances is Monte Carlo integration better than quasi-Monte Carlo?

Question

A simple enough question: to do a multidimensional integral, given that one has decided that some sort of Monte Carlo method is appropriate, is there any advantage that a regular MC integration using pseudorandom numbers has over a quasi-Monte Carlo integration using a quasirandom sequence? If so, how would I recognize situations where this advantage would come into play? (And if not, why does anyone ever use plain old Monte Carlo integration?)

Answer 1

Monte Carlo simulations are the method of choice for computation of electron scattering. Tricks like importance sampling are used sometimes, so you might say it's not plain old Monte Carlo. But the main point is probably that an inherently stochastic process is simulated here, while you are asking only about using Monte Carlo for integration.

Because nobody else tried to offer an answer, let me try to expand my answer a bit. Assume we have an electron scattering simulation, where only a single number, like a backscattering coefficient, is computed. If we would reformulate this as a multidimensional integral, it would probably be an infinite dimensional integral. On the other hand, during the simulation of a single trajectory, only a finite number of random numbers is required (this number can become quite large, if secondary electron generation is taken into account). If we would use a quasirandom sequence like latin hypercube sampling, we would have to use an approximation with a fixed number of dimensions, and generate a random number for every dimension for each sample point.

So I think the difference is whether some kind of high dimensional unit-hypercube is sampled, versus an infinite dimensional probability cloud around the origin.

Answer 2

Some of my research involves solving large scale stochastic partial differential equations. In which case, traditional monte carlo approximation of the integral of interest converges too slowly for it to be worthwhile in a practical sense... i.e. I don't want to have to run 100 times more simulations just to get a decimal point more accuracy to the integral. Instead, I tend to use other methods like sparse smolyak grids because they offer better accuracy in fewer function evaluations. This is only possible because I can assume a certain degree of smoothness in the function.

It is reasonable to conjecture that if you expect that the function you are integrating to have certain structure (like smoothness), it would be best to use the quasi-monte carlo scheme that exploits it. If you really can't make very many assumptions about the function, then monte carlo is the only tool I can think of to handle it.

Answer 3

Advantages of traditional Monte-Carlo integration over quasi-Monte Carlo integration are discussed in Kocis and Whiten's paper here. They list the following reasons:

• The error bound of qmc methods $\mathcal{O}(\log(N)^{d}/N)$ is "theoretically" better than the $\mathcal{O}(N^{-1/2})$ bound given by naive Monte-Carlo. However, for values of $N$ that are achievable in reasonable time on current hardware, $\mathcal{O}(N^{-1/2})$ is the better option for $d \approx 40$. (Kocis and Whiten were writing in 1997, so presumably $d$ has increased a little since then.)

• The error of a QMC integrations is bound by the Koksma-Hlawka inequality $$ \mathrm{error} \le V[f]D_{N}^{*} $$ where $V[f]$ is the variation of $f$ and $D_{N}^{*}$ is the star of the discrepancy. But quoting from Kocis' paper,

  Unfortunately, the theoretical discrepancy bound of the existing sequences is not useable for moderate and large values of s. The other option, a numerical evaluation of the star discrepancy of a sequence for large s, requires an excessive computational effort, and even reasonable numeric estimates of such discrepancies are very difficult to obtain.

  With traditional Monte-Carlo integration, we can specify an error goal and wait because the error bound is easily computable. With QMC, we have to specify a number of function evaluations and hope the error is within our goal. (Note that there are techniques to overcome this, like randomized quasi-Monte Carlo, where multiple quasi-Monte Carlo estimates are used to estimate the error.)

• Since the "constant terms" of the error bounds for many low-discrepancy sequences we actually possess grow exponentially with dimension, Kocis and Whiten use another metric to estimate the error: The maximum distance between sample points. This gives an error estimate of $\mathcal{O}(1/N^{1/2+2/d})$, and they claim it fits the observed behavior of many integrands.

• For quasi-Monte Carlo to beat traditional Monte-Carlo, the integrand must have "low effective dimension". See Art Owen's paper on this subject here.