Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models
share
This paper deals with the problem of efficient sampling from a stochastic differential equation, given the drift function and the diffusion matrix. The proposed approach leverages a recent model for probabilities <cit.> (the positive semi-definite – PSD model) from which it is possible to obtain independent and identically distributed (i.i.d.) samples at precision ε with a cost that is m^2 d log(1/ε) where m is the dimension of the model, d the dimension of the space. The proposed approach consists in: first, computing the PSD model that satisfies the Fokker-Planck equation (or its fractional variant) associated with the SDE, up to error ε, and then sampling from the resulting PSD model. Assuming some regularity of the Fokker-Planck solution (i.e. β-times differentiability plus some geometric condition on its zeros) We obtain an algorithm that: (a) in the preparatory phase obtains a PSD model with L2 distance ε from the solution of the equation, with a model of dimension m = ε^-(d+1)/(β-2s) (log(1/ε))^d+1 where 0<s≤1 is the fractional power to the Laplacian, and total computational complexity of O(m^3.5log(1/ε)) and then (b) for Fokker-Planck equation, it is able to produce i.i.d. samples with error ε in Wasserstein-1 distance, with a cost that is O(d ε^-2(d+1)/β-2log(1/ε)^2d+3) per sample. This means that, if the probability associated with the SDE is somewhat regular, i.e. β≥ 4d+2, then the algorithm requires O(ε^-0.88log(1/ε)^4.5d) in the preparatory phase, and O(ε^-1/2log(1/ε)^2d+2) for each sample. Our results suggest that as the true solution gets smoother, we can circumvent the curse of dimensionality without requiring any sort of convexity.
READ FULL TEXT