Wasserstein distance estimates for the distributions of numerical
approximations to ergodic stochastic differential equations
- URL: http://arxiv.org/abs/2104.12384v1
- Date: Mon, 26 Apr 2021 07:50:04 GMT
- Title: Wasserstein distance estimates for the distributions of numerical
approximations to ergodic stochastic differential equations
- Authors: J.M. Sanz-Serna, Konstantinos C. Zygalakis
- Abstract summary: We study the Wasserstein distance between the in distribution of an ergodic differential equation and the distribution in the strongly log-concave case.
This allows us to study in a unified way a number of different approximations proposed in the literature for the overdamped and underdamped Langevin dynamics.
- Score: 0.3553493344868413
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a framework that allows for the non-asymptotic study of the
$2$-Wasserstein distance between the invariant distribution of an ergodic
stochastic differential equation and the distribution of its numerical
approximation in the strongly log-concave case. This allows us to study in a
unified way a number of different integrators proposed in the literature for
the overdamped and underdamped Langevin dynamics. In addition, we analyse a
novel splitting method for the underdamped Langevin dynamics which only
requires one gradient evaluation per time step. Under an additional smoothness
assumption on a $d$--dimensional strongly log-concave distribution with
condition number $\kappa$, the algorithm is shown to produce with an
$\mathcal{O}\big(\kappa^{5/4} d^{1/4}\epsilon^{-1/2} \big)$ complexity samples
from a distribution that, in Wasserstein distance, is at most $\epsilon>0$ away
from the target distribution.
Related papers
- Near Minimax-Optimal Distributional Temporal Difference Algorithms and The Freedman Inequality in Hilbert Spaces [24.03281329962804]
We propose a non-parametric distributional TD algorithm (NTD) for a $gamma$-discounted infinite-horizon Markov decision process.
We establish a novel Freedman's inequality in Hilbert spaces, which would be of independent interest.
arXiv Detail & Related papers (2024-03-09T06:19:53Z) - Correction to "Wasserstein distance estimates for the distributions of
numerical approximations to ergodic stochastic differential equations" [1.2691047660244337]
method for analyzing non-asymptotic guarantees of numerical discretizations of ergodic SDEs in Wasserstein-2 distance is presented.
arXiv Detail & Related papers (2024-02-13T18:31:55Z) - Symmetric Mean-field Langevin Dynamics for Distributional Minimax
Problems [78.96969465641024]
We extend mean-field Langevin dynamics to minimax optimization over probability distributions for the first time with symmetric and provably convergent updates.
We also study time and particle discretization regimes and prove a new uniform-in-time propagation of chaos result.
arXiv Detail & Related papers (2023-12-02T13:01:29Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
This work provides a general framework for the non-asymotic analysis of sampling error in 2-Wasserstein distance.
Our theoretical analysis is further validated by numerical experiments.
arXiv Detail & Related papers (2021-09-08T18:00:05Z) - Lattice partition recovery with dyadic CART [79.96359947166592]
We study piece-wise constant signals corrupted by additive Gaussian noise over a $d$-dimensional lattice.
Data of this form naturally arise in a host of applications, and the tasks of signal detection or testing, de-noising and estimation have been studied extensively in the statistical and signal processing literature.
In this paper we consider instead the problem of partition recovery, i.e.of estimating the partition of the lattice induced by the constancy regions of the unknown signal.
We prove that a DCART-based procedure consistently estimates the underlying partition at a rate of order $sigma2 k*
arXiv Detail & Related papers (2021-05-27T23:41:01Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
We provide a new convergence analysis of gradient Langevin dynamics (SGLD) for sampling from a class of distributions that can be non-log-concave.
At the core of our approach is a novel conductance analysis of SGLD using an auxiliary time-reversible Markov Chain.
arXiv Detail & Related papers (2020-10-19T15:23:18Z) - On the cost of Bayesian posterior mean strategy for log-concave models [0.0]
We consider the problem of computing Bayesian estimators using Langevin Monte-Carlo type approximation.
We establish some quantitative statistical bounds related to the underlying Poincar'e constant of the model.
We establish new results about the numerical approximation of Gibbs measures by Cesaro averages of Euler schemes of (over-damped) Langevin diffusions.
arXiv Detail & Related papers (2020-10-08T04:51:10Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP)
We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
arXiv Detail & Related papers (2020-06-04T17:51:00Z) - A diffusion approach to Stein's method on Riemannian manifolds [65.36007959755302]
We exploit the relationship between the generator of a diffusion on $mathbf M$ with target invariant measure and its characterising Stein operator.
We derive Stein factors, which bound the solution to the Stein equation and its derivatives.
We imply that the bounds for $mathbb Rm$ remain valid when $mathbf M$ is a flat manifold.
arXiv Detail & Related papers (2020-03-25T17:03:58Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.