The shifted ODE method for underdamped Langevin MCMC
In this paper, we consider the underdamped Langevin diffusion (ULD) and propose a numerical approximation using its associated ordinary differential equation (ODE). When used as a Markov Chain Monte Carlo (MCMC) algorithm, we show that the ODE approximation achieves a 2-Wasserstein error of ε in O(d...
| Main Authors: | , , |
|---|---|
| Format: | Internet publication |
| Language: | English |
| Published: |
2021
|
| _version_ | 1797109830805094400 |
|---|---|
| author | Foster, J Lyons, T Oberhauser, H |
| author_facet | Foster, J Lyons, T Oberhauser, H |
| author_sort | Foster, J |
| collection | OXFORD |
| description | In this paper, we consider the underdamped Langevin diffusion (ULD) and propose a numerical approximation using its associated ordinary differential equation (ODE). When used as a Markov Chain Monte Carlo (MCMC) algorithm, we show that the ODE approximation achieves a 2-Wasserstein error of ε in O(d13/ε23) steps under the standard smoothness and strong convexity assumptions on the target distribution. This matches the complexity of the randomized midpoint method proposed by Shen and Lee [NeurIPS 2019] which was shown to be order optimal by Cao, Lu and Wang. However, the main feature of the proposed numerical method is that it can utilize additional smoothness of the target log-density f. More concretely, we show that the ODE approximation achieves a 2-Wasserstein error of ε in O(d25/ε25) and O(d−−√/ε13) steps when Lipschitz continuity is assumed for the Hessian and third derivative of f. By discretizing this ODE using a third order Runge-Kutta method, we can obtain a practical MCMC method that uses just two additional gradient evaluations per step. In our experiment, where the target comes from a logistic regression, this method shows faster convergence compared to other unadjusted Langevin MCMC algorithms. |
| first_indexed | 2024-03-07T07:46:48Z |
| format | Internet publication |
| id | oxford-uuid:51b090dd-a0a1-43d3-aff4-620adfaba63a |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:46:48Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | oxford-uuid:51b090dd-a0a1-43d3-aff4-620adfaba63a2023-06-09T11:06:38ZThe shifted ODE method for underdamped Langevin MCMCInternet publicationhttp://purl.org/coar/resource_type/c_7ad9uuid:51b090dd-a0a1-43d3-aff4-620adfaba63aEnglishSymplectic Elements2021Foster, JLyons, TOberhauser, HIn this paper, we consider the underdamped Langevin diffusion (ULD) and propose a numerical approximation using its associated ordinary differential equation (ODE). When used as a Markov Chain Monte Carlo (MCMC) algorithm, we show that the ODE approximation achieves a 2-Wasserstein error of ε in O(d13/ε23) steps under the standard smoothness and strong convexity assumptions on the target distribution. This matches the complexity of the randomized midpoint method proposed by Shen and Lee [NeurIPS 2019] which was shown to be order optimal by Cao, Lu and Wang. However, the main feature of the proposed numerical method is that it can utilize additional smoothness of the target log-density f. More concretely, we show that the ODE approximation achieves a 2-Wasserstein error of ε in O(d25/ε25) and O(d−−√/ε13) steps when Lipschitz continuity is assumed for the Hessian and third derivative of f. By discretizing this ODE using a third order Runge-Kutta method, we can obtain a practical MCMC method that uses just two additional gradient evaluations per step. In our experiment, where the target comes from a logistic regression, this method shows faster convergence compared to other unadjusted Langevin MCMC algorithms. |
| spellingShingle | Foster, J Lyons, T Oberhauser, H The shifted ODE method for underdamped Langevin MCMC |
| title | The shifted ODE method for underdamped Langevin MCMC |
| title_full | The shifted ODE method for underdamped Langevin MCMC |
| title_fullStr | The shifted ODE method for underdamped Langevin MCMC |
| title_full_unstemmed | The shifted ODE method for underdamped Langevin MCMC |
| title_short | The shifted ODE method for underdamped Langevin MCMC |
| title_sort | shifted ode method for underdamped langevin mcmc |
| work_keys_str_mv | AT fosterj theshiftedodemethodforunderdampedlangevinmcmc AT lyonst theshiftedodemethodforunderdampedlangevinmcmc AT oberhauserh theshiftedodemethodforunderdampedlangevinmcmc AT fosterj shiftedodemethodforunderdampedlangevinmcmc AT lyonst shiftedodemethodforunderdampedlangevinmcmc AT oberhauserh shiftedodemethodforunderdampedlangevinmcmc |