Source-linked AI summary
Proximal Markov chain Monte Carlo algorithms
Marcelo Pereyra
TL;DR
The paper addresses challenging sampling problems using a new Langevin MCMC algorithm based on convex analysis and proximal techniques. P-MALA has favourable convergence properties, including geometric ergodicity in cases where ULA is transient or other MALA methods are not geometric.
Problem
Sampling in these models is challenging, and standard techniques such as Gibbs sampling can also be challenging.
Method
The paper constructs a new Langevin MCMC algorithm using convex analysis, Moreau techniques, and a first-order approximation based on proximity mappings.
Results
P-MALA inherits the favourable convergence properties of P-ULA and is geometrically ergodic in many cases where ULA is transient or MALA does not have geometric convergence.
Takeaways & Limitations
The method provides an approach for sampling efficiently from high-dimensional densities using approximations and proximity mappings.
Takeaways & Limitations
P-MALA may not be applicable or computationally competitive for models where alternative methods perform very well.
Abstract
from arXiv · showhide
This paper presents a new Metropolis-adjusted Langevin algorithm (MALA) that uses convex analysis to simulate efficiently from high-dimensional densities that are log-concave, a class of probability distributions that is widely used in modern high-dimensional statistics and data analysis. The method is based on a new first-order approximation for Langevin diffusions that exploits log-concavity to construct Markov chains with favourable convergence properties. This approximation is closely related to Moreau-Yoshida regularisations for convex functions and uses proximity mappings instead of gradient mappings to approximate the continuous-time process. The proposed method complements existing MALA methods in two ways. First, the method is shown to have very robust stability properties and to converge geometrically for many target densities for which other MALA are not geometric, or only if the step size is sufficiently small. Second, the method can be applied to high-dimensional target densities that are not continuously differentiable, a class of distributions that is increasingly used in image processing and machine learning and that is beyond the scope of existing MALA and HMC algorithms. To use this method it is necessary to compute or to approximate efficiently the proximity mappings of the logarithm of the target density. For several popular models, including many Bayesian models used in modern signal and image processing and machine learning, this can be achieved with convex optimisation algorithms and with approximations based on proximal splitting techniques, which can be implemented in parallel. The proposed method is demonstrated on two challenging high-dimensional and non-differentiable models related to image resolution enhancement and low-rank matrix estimation that are not well addressed by existing MCMC methodology.
1 Introduction
The paper develops a proximal Langevin MCMC method using convex analysis to sample high-dimensional, log-concave distributions, including possibly non-differentiable targets. It studies convergence properties and demonstrates applications in image resolution enhancement and low-rank matrix estimation.
- High-dimensional inference is challenging when standard methods such as Gibbs sampling are unavailable or ineffective.
- Existing MALA and HMC methods rely on differential calculus and require continuously differentiable target densities.
- The paper moves from differential calculus to convex analysis for MCMC sampling from log-concave distributions.
- The proposed method uses proximal techniques and proximity mappings to construct a Langevin MCMC algorithm for high-dimensional, possibly non-differentiable distributions.
- P-MALA is presented as inheriting favourable convergence properties from proximal ULA while converging to the desired target density.
- Experiments address two challenging applications involving image resolution enhancement and low-rank matrix estimation.
2 Definitions and notations
The paper defines proximity mappings and Moreau approximations as convex-analytic tools for smoothing and approximating log-concave target densities. These constructions support Langevin algorithms while preserving key distributional properties and enabling treatment of non-differentiable targets.
- The sampling problem is to simulate from a probability distribution π on R^n with a density relative to n-dimensional Lebesgue measure.
- A proximity mapping maximizes a concave function penalized by a quadratic distance term, providing a convex-analytic alternative to gradient mappings.
- Proximity mappings are useful for stochastic simulation and can be inexpensive to evaluate or approximate in many high-dimensional statistical models.
- Moreau approximations converge point-wise to π as λ → 0 and are continuously differentiable even when π is not.
- Moreau approximations preserve the maximizers of π and can be evaluated using proximity mappings.
- For lighter-than-Gaussian tails, the Moreau approximation resembles the target near its mode but has Gaussian tails.
- The proximal MALA uses proximity mappings in a new Langevin method with improved geometric convergence properties.
3 Proximal MCMC
The paper develops proximal Langevin chains for log-concave targets, using Moreau approximations and proximity mappings to improve stability and convergence. P-MALA corrects the P-ULA approximation with a Metropolis step and is shown to converge geometrically in broad settings, including cases where MALA does not.
- 3 Proximal MCMC: P-MALA uses convex analysis and proximity mappings to sample from log-concave densities.It is introduced as a proximal Metropolis-adjusted Langevin algorithm exploiting convex analysis.
- 3 Proximal MCMC: P-ULA approximates a Langevin diffusion with invariant measure πλ, where πλ can be made arbitrarily close to π by choosing small λ.The approximation is based on a Moreau regularisation and uses a forward Euler construction.
- 3 Proximal MCMC: λ must satisfy λ ≥ δ/2 for stability; setting λ = δ/2 yields the P-ULA chain.Smaller values can make the proximal update expansive and produce an explosive Markov chain.
- 3 Proximal MCMC: P-ULA is geometrically ergodic for target densities in E(β, γ) for all δ > 0.The paper contrasts this with ULA, which can be non-ergodic or require sufficiently small δ for parts of the same class.
- 3 Proximal MCMC: P-MALA adds a Metropolis–Hastings correction to P-ULA, guaranteeing convergence to π in total variation.P-ULA supplies the proposal, while rejected candidates leave the chain at its current state.
- 3 Proximal MCMC: P-MALA is geometrically ergodic for E(β, γ) targets for all δ > 0 and performs well at acceptance rates of 40%−60%.The paper reports robust stability and geometric convergence in many cases where MALA is not geometrically fast.
4 Applications
The applications evaluate P-MALA on high-dimensional, non-smooth Bayesian image deconvolution and low-rank matrix models. The experiments show useful uncertainty quantification, image reconstruction, posterior predictive checks, and improved sampling efficiency, while exposing model-specific limitations.
- Bayesian image deconvolution: P-MALA computes marginal 90% credibility regions for image pixels in a log-concave deconvolution model.The regions quantify uncertainty in the restored image rather than only producing a MAP estimate.
- Bayesian image deconvolution: The MAP estimate restored sharp edges and fine details, while uncertainty was concentrated at contours and object boundaries.The model detected edge presence accurately but remained uncertain about exact edge locations.
- Bayesian image deconvolution: 50.8 and 11.04 samples per hour were the time-normalised ESS values for P-MALA and MALA, respectively.P-MALA required 49 hours versus 28 hours for MALA but produced lower autocorrelation and higher effective sample size.
- Low-rank matrix estimation: The nuclear-norm prior is simplistic for the tested signal because it omits features including piecewise constancy, periodicity, symmetry, and three-valued pixels.Posterior predictive checks were used to assess whether the model nevertheless captured the data’s main visual characteristics.
5 Conclusion
The paper introduces P-MALA, a proximal Langevin MCMC method based on convex analysis and proximity mappings, with favourable convergence properties for high-dimensional log-concave targets. It supports many non-continuously differentiable models and was demonstrated on challenging image-processing and matrix-estimation problems.
- Convergence: P-MALA is geometrically ergodic in many cases where ULA is transient or explosive and MALA does not converge geometrically.The paper states that P-MALA inherits the favourable convergence properties established for P-ULA.
- Method: P-MALA combines a proximal Langevin approximation with a Metropolis correction to target high-dimensional log-concave densities.The approximation replaces gradient mappings with proximity mappings and is obtained by discretising an auxiliary Langevin diffusion with δ = 2λ.
- Scope: Because it uses proximity mappings instead of gradients, P-MALA applies to target densities that are not continuously differentiable.This extends applicability beyond the differentiability conditions required by MALA and manifold MALA.
- Applications: Experiments on image deconvolution and low-rank matrix denoising show that P-MALA can make Bayesian inference practically feasible for high-dimensional, non-differentiable models.The conclusion identifies these models as poorly addressed by existing MCMC methodology.
- Limitations and future work: The method is directly applicable to log-concave distributions, while its convergence rate as a function of dimension remains a subject for future work.The authors also identify efficient evaluation of proximity mappings on non-canonical Euclidean spaces as an important practical factor.
- Positioning: P-MALA complements rather than replaces existing MALA and HMC methods, especially for log-concave targets with fast proximity mappings.The authors note that other methods may remain preferable when they perform well or when P-MALA is not computationally competitive.