Proximal Markov Chain Monte Carlo for Non-Smooth Sampling

This direction is merged into another direction: proximal Langevin sampling. Its last version stays readable and citable here.

Version 1 of 124 papers29 conceptsfrozen 2026-10-04

In Bayesian inference, we often seek to sample from distributions where the "energy" or potential function is non-differentiable. This typically happens when we use sparsity-promoting priors (like the $L_1$ norm) or hard constraints to regularize high-dimensional inverse problems in fields like medical imaging and radio astronomy.

Standard gradient-based samplers, such as the Unadjusted Langevin Algorithm (ULA) or Hamiltonian Monte Carlo (HMC), rely on the gradient of the log-density to "push" the Markov chain toward high-probability regions. When the potential is non-smooth, the gradient becomes undefined or discontinuous at the very points—like the sharp peaks of a Laplace distribution—that are most important to the model. This leads to numerical instability, oscillations, and a failure to converge.

To solve this, researchers have integrated proximal operators from the world of non-smooth optimization into the framework of stochastic simulation.

The Proximal Operator as a Stable Step

In optimization, the proximal operator is a tool for minimizing functions that aren't smooth. Intuitively, instead of taking a blind step in the direction of a local gradient, a proximal step asks: "Where can I move that is both close to my current position and has a low function value?"

Mathematically, the proximal operator of a function $f$ with step size $\gamma$ is defined as: $$\text{prox}_{\gamma f}(x) = \arg\min_{u} \left\{ f(u) + \frac{1}{2\gamma} \|u - x\|^2 \right\}$$

As Espen Bernton notes, replacing a standard gradient descent step with a proximal operator is equivalent to a "backward Euler" discretization of the underlying drift. This provides a stabilizing effect: while a forward gradient step can overshoot a sharp peak and oscillate, a proximal step inherently "finds" the peak and stays near it.

Smoothing without Losing the Truth

A core challenge in sampling from non-smooth densities is that we cannot simply "blur" the distribution to make it smooth; doing so would change the very statistics we are trying to estimate.

A common mechanism used to bridge this gap is the Moreau-Yosida envelope. This technique creates a differentiable approximation of a non-smooth function. Crucially, as shown by Armin Eftekhari and Konstantinos C. Zygalakis in their work on the Forward-Backward Unadjusted Langevin Algorithm (FBULA), these envelopes can be designed to preserve the original distribution's most likely state (the MAP estimator).

By sampling from this smoothed surrogate, algorithms like MY-MALA (Moreau-Yosida Metropolis-adjusted Langevin Algorithm) can use gradient-like updates while remaining theoretically sound. Francesca Crucinio and Gareth O. Roberts demonstrated that for non-differentiable targets, these proximal-based samplers follow a unique scaling law of $d^{-2/3}$, making them more efficient than random walks but distinct from standard smooth samplers.

Bridging Optimization and Sampling

The research direction treats sampling as a stochastic counterpart to optimization. Just as proximal algorithms allow optimization to handle composite functions (a smooth part plus a non-smooth part), proximal MCMC does the same for densities.

  1. Composite Sampling: Yin Tat Lee and Kevin Tian introduced the Restricted Gaussian Oracle, a sampling primitive that acts as the stochastic version of a proximal operator. This allows the non-smooth part of a density to be treated as a "black box," mirroring how proximal operators are used in algorithms like ISTA or ADMM.
  2. Stochastic Gradients: For large-scale machine learning, Adil Salim and Peter Richtárik developed the Stochastic Proximal Langevin Algorithm (SPLA). This method combines the stability of proximal steps with the computational efficiency of stochastic gradients, allowing for Bayesian uncertainty quantification in models that were previously restricted to point estimation.

Applications in High-Dimensional Imaging

The practical impact of this work is most visible in high-dimensional inverse problems. In radio interferometry and medical imaging, we often deal with millions of pixels and non-differentiable "Total Variation" or $L_1$ penalties.

Marcelo Pereyra and Jean-Yves Tourneret have shown that proximal MCMC methods allow us to move beyond "best-guess" images to provide rigorous error bars. By using explicit stabilized methods, as explored by Luis Vargas, these samplers can take significantly larger steps than standard methods, achieving up to 30x speedups in convergence while maintaining the stability required to navigate sharp, sparsity-inducing probability landscapes.

Ultimately, this research direction transforms the proximal operator from a tool for finding a single "best" point into a mechanism for exploring the entire landscape of likely solutions, even when that landscape is jagged and sharp.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_proximal_markov_chain_monte_carlo_for_no_c3b11a4f,
  title = {Proximal Markov Chain Monte Carlo for Non-Smooth Sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/proximal-markov-chain-monte-carlo-for-non-smooth-sampling/rdr_c3b11a4f0048426d8970931d1c92489b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_proximal_markov_chain_monte_carlo_for_no_c3b11a4f_v1,
  title = {Proximal Markov Chain Monte Carlo for Non-Smooth Sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/proximal-markov-chain-monte-carlo-for-non-smooth-sampling/rdr_c3b11a4f0048426d8970931d1c92489b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}