Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models
Not on the map. Why?
Abstract (arXiv)
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 varepsilon with a cost that is m2 d log(1/varepsilon) 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 varepsilon, 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 varepsilon from the solution of the equation, with a model of dimension m = varepsilon-(d+1)/(β-2s) (log(1/varepsilon))d+1 where 1/2≤ s≤1 is the fractional power to the Laplacian, and total computational complexity of O(m3.5 log(1/varepsilon)) and then (b) for Fokker-Planck equation, it is able to produce i.i.d. samples with error varepsilon in Wasserstein-1 distance, with a cost that is O(d varepsilon-2(d+1)/β-2 log(1/varepsilon)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(varepsilon-0.88 log(1/varepsilon)4.5d) in the preparatory phase, and O(varepsilon-1/2log(1/varepsilon)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.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 45 of its 100 references that are in the map. First posted on arXiv 30 Mar 2023.
Builds on
45 of 100 references.
References · 45
- 2017The Deep Ritz method: A deep learning-based numerical algorithm for solving variational problemscited by 583
- 2017Solving high-dimensional partial differential equations using deep learningcited by 556
- 2021Physics-informed neural networks (PINNs) for fluid mechanics: A reviewcited by 473
- 2017PDE-Net: Learning PDEs from Datacited by 311
- 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 243
- 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 214
- 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 208
- 2015Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithmcited by 197
- 2015A Complete Recipe for Stochastic Gradient MCMCcited by 146
- 2016High-dimensional Bayesian inference via the Unadjusted Langevin Algorithmcited by 146
- 2021Solving and Learning Nonlinear PDEs with Gaussian Processescited by 129
- 2018Analysis of Langevin Monte Carlo via convex optimizationcited by 127
33 more
- 2020Towards Theoretically Understanding Why SGD Generalizes Better Than ADAM in Deep Learningcited by 126
- 2017User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradientcited by 116
- 2017Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimizationcited by 97
- 2019A Theoretical Analysis of Deep Neural Networks and Parametric PDEscited by 74
- 2020An overview on deep learning-based approximation methods for partial differential equationscited by 65
- 2022Generic bounds on the approximation error for physics-informed (and) operator learningcited by 65
- 2022Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlocited by 63
- 2020Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networkscited by 62
- 2018Mirrored Langevin Dynamicscited by 61
- 2019Stochastic gradient Markov chain Monte Carlocited by 56
- 2020On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothnesscited by 55
- 2019First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noisecited by 44
- 2017Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlocited by 43
- 2020Non-parametric Models for Non-negative Functionscited by 41
- 2021Machine Learning For Elliptic PDEs: Fast Rate Generalization Bound, Neural Scaling Law and Minimax Optimalitycited by 40
- 2020Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin Algorithmcited by 35
- 2020Projected Stochastic Gradient Langevin Algorithms for Constrained Sampling and Non-Convex Learningcited by 33
- 2019Langevin Monte Carlo without smoothnesscited by 28
- 2021On the Representation of Solutions to Elliptic PDEs in Barron Spacescited by 25
- 2020Finding Global Minima via Kernel Approximationscited by 23
- 2021PSD Representations for Effective Probability Modelscited by 23
- 2021A Priori Generalization Error Analysis of Two-Layer Neural Networks for Solving High Dimensional Schr"odinger Eigenvalue Problemscited by 19
- 2021A Priori Generalization Analysis of the Deep Ritz Method for Solving High Dimensional Elliptic Equationscited by 18
- 2021A Dimension-free Computational Upper-bound for Smooth Optimal Transport Estimationcited by 17
- 2023Algorithmic Stability of Heavy-Tailed SGD with General Loss Functionscited by 15
- 2017Fractional Langevin Monte Carlo: Exploring L'evy Driven Stochastic Differential Equations for Markov Chain Monte Carlocited by 13
- 2021Near-optimal estimation of smooth transport maps with kernel sums-of-squarescited by 12
- 2019Non-Asymptotic Analysis of Fractional Langevin Monte Carlo for Non-Convex Optimizationcited by 8
- 2021Sampling from Arbitrary Functions via PSD Modelscited by 8
- 2020Interpolation and Learning with Scale Dependent Kernelscited by 7
- 2021Infinite-Dimensional Sums-of-Squares for Optimal Controlcited by 6
- 2022Constrained Langevin Algorithms with L-mixing External Random Variablescited by 6
- 2020An exact kernel framework for spatio-temporal dynamicscited by 1
Built on by
Citing papers per year: 2025: 1.
1 paper.