Analysis of Primal-Dual Langevin Algorithms
math.OC
Submitted: 2024-05-28
Updated: 2026-10-26
License: http://creativecommons.org/licenses/by/4.0/
The gist: We analyze a recently proposed class of algorithms for the problem of sampling from probability distributions μ in R d with a Lebesgue density of the form μ(x) proportional to (-f(Kx)-g(x))…
Terminology
Abstract
We analyze a recently proposed class of algorithms for the problem of sampling from probability distributions μ in R d with a Lebesgue density of the form μ(x) proportional to (-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 μ 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.
Sources
- Approximate Primal-Dual Fixed-Point based Langevin Algorithms for Non-smooth Convex Potentials
- Proximal Langevin Sampling With Inexact Proximal Mapping
- Subgradient Langevin Methods for Sampling from Non-smooth Potentials
- Accelerated Bayesian imaging by relaxed proximal-point Langevin sampling
- Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithms
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise