Monte carlo methods and the curse of dimensionality for solving PDEs

Question

Do Monte Carlo methods suffer from the curse of dimensionality when solving PDEs? I was under the impression that they do not, since the variance scales like $\sigma /\sqrt{N}$, and thus it only depends on the number of samples and not on the number of dimensions.

However, I've read in several references (for example in this one), that direct Monte Carlo methods for simulating the Fokker-Planck equation also suffer from the curse of dimensionality, hence my question. I'm not sure I understand where this dependence is coming from, are there any good references about this topic? I would like to know how this type of Monte Carlo algorithms to solve Fokker-Planck equations scale with the dimensions.

Also, is there any Monte Carlo method to solve this type of equations that doesn't suffer from the curse of dimensionality?

Thank you very much.

Answer 1

If your discrete simulation of the system in some region of $\mathbb R^d$ uses a rectangular grid with $N$ points in each coordinate direction, that's $N^d$ points, and thus $N^d$ values that must be all be updated in each iteration. So right there you have a factor in the complexity that is exponential in $d$. That's the curse of dimensionality. It has little to do with the details of the particular method you are using.

Answer 2

I checked your reference, and that claim does not have any additional detail or any reference. I am not sure you should take it too seriously.

Monte-Carlo does indeed beat the curse of dimensionality, but it also changes the problem a bit. As Robert Israel pointed out, if you goal is to solve the PDE on a grid with $N^d$ points in dimension $d$, then you cannot beat the curse of dimensionality. So something has to give.

Monte-Carlo methods are used when the goal is to compute the value of the solution at some given point $(x,t)$ (and only that point, or at some small collection of points). The idea is to reformulate the equation in terms of a Brownian motion or stochastic ODE, so that you can write $u(x,t)$ as the expectation against this stochastic process, in the form:

$$u(x,t) = \mathbb{E}[\cdots].$$

Then you sample some Brownian motion paths, or simulate the stochastic ODE, and replace the expectation by an empirical mean. As you said, the variance scales like $1/\sqrt{N}$ where $N$ is the number of sample paths, which is independent of dimension. This means the number of sample paths needed to obtain a particular error is independent of dimension.