Analysis of Primal-Dual Langevin Algorithms
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910684415000576 |
|---|---|
| author | Burger, Martin Ehrhardt, Matthias J. Kuger, Lorenz Weigand, Lukas |
| author_facet | Burger, Martin Ehrhardt, Matthias J. Kuger, Lorenz Weigand, Lukas |
| contents | We analyze a recently proposed class of algorithms for the problem of sampling from probability distributions $μ^\ast$ in $\mathbb{R}^d$ with a Lebesgue density of the form $μ^\ast(x) \propto \exp(-f(Kx)-g(x))$, where $K$ is a linear operator and $f,g$ convex and non-smooth. The method is a generalization of the primal-dual hybrid gradient optimization algorithm to a sampling scheme. We give the iteration's continuous time limit, a stochastic differential equation in the joint primal-dual variable, and its mean field limit Fokker-Planck equation. Under mild conditions, the scheme converges to a unique stationary state in continuous and discrete time. Contrary to purely primal overdamped Langevin diffusion, the stationary state in continuous time does not have $μ^\ast$ as its primal marginal. Thus, further analysis is carried out to bound the bias induced by the partial dualization, and potentially correct for it in the diffusion. Time discretizations of the diffusion lead to implementable algorithms, but, as is typical in Langevin Monte Carlo methods, introduce further bias. We prove bounds for these discretization errors, which allow to give convergence results relating the produced samples to the target. We demonstrate our findings numerically first on small-scale examples in which we can exactly verify the theoretical results, and subsequently on typical examples of larger scale from Bayesian imaging inverse problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_18098 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Analysis of Primal-Dual Langevin Algorithms Burger, Martin Ehrhardt, Matthias J. Kuger, Lorenz Weigand, Lukas Optimization and Control 35Q84, 47A52, 49N45, 60H10, 62F15, 65J22, 68U10 We analyze a recently proposed class of algorithms for the problem of sampling from probability distributions $μ^\ast$ in $\mathbb{R}^d$ with a Lebesgue density of the form $μ^\ast(x) \propto \exp(-f(Kx)-g(x))$, where $K$ is a linear operator and $f,g$ convex and non-smooth. The method is a generalization of the primal-dual hybrid gradient optimization algorithm to a sampling scheme. We give the iteration's continuous time limit, a stochastic differential equation in the joint primal-dual variable, and its mean field limit Fokker-Planck equation. Under mild conditions, the scheme converges to a unique stationary state in continuous and discrete time. Contrary to purely primal overdamped Langevin diffusion, the stationary state in continuous time does not have $μ^\ast$ as its primal marginal. Thus, further analysis is carried out to bound the bias induced by the partial dualization, and potentially correct for it in the diffusion. Time discretizations of the diffusion lead to implementable algorithms, but, as is typical in Langevin Monte Carlo methods, introduce further bias. We prove bounds for these discretization errors, which allow to give convergence results relating the produced samples to the target. We demonstrate our findings numerically first on small-scale examples in which we can exactly verify the theoretical results, and subsequently on typical examples of larger scale from Bayesian imaging inverse problems. |
| title | Analysis of Primal-Dual Langevin Algorithms |
| topic | Optimization and Control 35Q84, 47A52, 49N45, 60H10, 62F15, 65J22, 68U10 |
| url | https://arxiv.org/abs/2405.18098 |