# How to optimize sampling for global sensitivity analysis

What is a good way to sample parameters for performing global sensitivity analysis? Some methods are defined using integrals, some are use Monte Carlo. How do these compare?

• I answered this question for some reason thinking it was on global sensitivity, not local sensitivity for parameter estimation... so I deleted the answer and moved it here, thinking it might be nice to share anyways! – Chris Rackauckas Dec 12 '19 at 15:45
• thanks for doing it. I enjoyed reading it quite a bit! – Anton Menshov Dec 12 '19 at 18:13

## 1 Answer

What you're looking for goes under the name of quasi-Monte Carlo (QMC) sequences. Quasi Monte Carlo sequences are "more random than random", i.e. they fill high dimensional spaces better than random sequences tend to do, which somewhat matches a more intuitive form of randomness. But more importantly, since they "fill space well" (a property that can be quantified as have a low discrepancy), they tend to be a very good way of sampling to make integrals converge faster. Because of this, quasi Monte Carlo sequences can have faster convergence than Monte Carlo integration methods, moving from $$O(\frac{1}{\sqrt{N}})$$ with random sampling to $$O(\frac{1}{N})$$ for quasi-random sequences with low discrepancy.

Sobol sensitivity analysis, or variance-based global sensitivity analysis is usually the place people start when wanting to understand sensitivities in a way that allows for independently quantifying main effects (first indices) vs interaction effects (total indices, second indices, etc.). For an overview of global sensitivity metrics, you can consult these lecture notes which pools together a summary of various methods and tries to piece together the underlying commonalities. Basically what's going on is they utilize a probabilistic description and thus all amount to some kind of continuous average in some form, which all turns into approximations of high dimensional integrals. High dimensional integrals are computed fast using Monte Carlo types of methods, and thus one arrives at estimators that utilize random sampling, where random can then be replaced with QMC.

For more details on the advantages of QMC sampling, this paper is a good overview. These kinds of quasi-Monte Carlo sequences can be mixed with integral estimators for variance-based global sensitivity analysis to give fast and accurate means of calculation. This is for example how the global sensitivity analysis methods of the DifferentialEquations.jl library works, and many other sensitivity libraries like R's sensitivity utilize these kinds of estimators and ask the user to pass in "design matrices" of QMC-sampled points.

There are many libraries out there for generating quasi-Monte Carlo sequences. The aptly named QuasiMonteCarlo.jl pools together a few different sampling methods, including Latin Hypercube and Sobol sequences. randtoolbox is a similar package in R. There's more stuff out there, but this should supply you with the language you need to find the results you need.

One final note is to leave you with a caution that QMC is not the "end-all-be-all". Adaptive Monte Carlo methods change sampling strategies on the fly to match behaviors of the function it's trying to understand. Algorithms like VEGAS is such a method, and these can be better in some cases. For example, if doing Monte Carlo integration and most of the density is found a small area of the space, QMC is a waste at most of the points, while adaptive Monte Carlo will quickly learn to preferentially sample around the high density region in a few stages. However, these ideas are complementary, not contradictory, and so the most recent "good methods" combine adaptive and quasi-random strategies together. This paper is a good introduction to such a mixed method. I think it's also important to note that CUBA, one of the best high-dimensional quadrature libraries, notes that its Monte Carlo method implementations (like VEGAS) use quasi-Monte Carlo sequences, and mentions that this can be a great improvement to the method. And it's easy to understand why: adaptive methods help concentrate points in the right place, and quasi-random sequences better sample points in a given place: a match made in heaven! While all of this section is written and derived from the point of view of numerical quadrature, note that the computation of global sensitivity measurements, such as the Sobol indices, is a quadrature, and so there are papers which more directly address adaptive methods + QMC and their relationship to the computational of Sobol global sensitivity metrics.