Monte Carlo is great: its error is independent of the dimension of the integrand.
Or is it ??
I wrote a little blogpost :
https://www.branchini.fun/posts/monte_carlo_indep/ 🤔
Share and comment (no login needed, just email ! Choose "post as guest" ) if you liked it .
Or better, if everything I am saying is wrong and I should revise my beliefs 🤓
@nbranchini I have wondered about exactly this when teaching about MC. Ideally, I would make a clear comparison to the alternative: grid quadrature.
Does anyone know a simple reference that shows the curse of dimensionality for grid quadrature? Ideally with a reference to its rate of convergence?
@markvanderwilk
(e.g. section 7.4 , and the result at the end of page 13 )
@nbranchini This is indeed exactly what I was looking for!
This provides a very compelling story:
- Deterministic quadrature rules relying on uniform grids slow their convergence down with the dimension.
- The *rate* of MC doesn't slow down.
- However, a particular problem can have a single-sample variance that grows with D.
- Importance sampling / MCMC is a way to reduce this effect.
@markvanderwilk
what is grid quadrature exactly ? (sorry, probably different naming conventions)
This chapter has a lot on curse of dimension of many classical quadrature rules
https://artowen.su.domains/mc/Ch-quadrature.pdf