2023/03/30 by Raj, Anant, Şimşekli, Umut, Rudi, Alessandro · 1 citation
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · doi:10.48550/arxiv.2303.17109
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 \citerudi2021psd (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 m2 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 1/2≤ s≤1 is the fractional power to the Laplacian, and total computational complexity of O(m3.5 log(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)/β-2 log(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.88 log(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.