Sampling from Non-Smooth Probability Distributions

64 concepts45 papers1 proposal

In Bayesian inference and machine learning, we frequently encounter probability distributions with "sharp" features. For instance, image reconstruction tasks often employ Total Variation or $L_1$ regularization to preserve crisp edges and enforce sparsity. In probabilistic programming, conditional logic creates piecewise-continuous landscapes with sudden jumps or kinks.

To sample from these distributions, modern statistical computation relies heavily on gradient-based Markov Chain Monte Carlo (MCMC) methods, such as Langevin Monte Carlo (LMC) and Hamiltonian Monte Carlo (HMC). As surveyed by Jean-Yves Tourneret et al. in A Survey of Stochastic Simulation and Optimization Methods in Signal Processing, these algorithms use first-order gradient information to efficiently navigate high-dimensional spaces.

However, when a distribution is non-smooth, this dependency becomes a fatal flaw. At points of non-differentiability—like the sharp tip of a Laplace distribution or the hard boundary of a convex constraint—the gradient is either undefined or changes discontinuously. Standard samplers encountering these boundaries suffer from numerical instability, extreme rejection rates, or failure to conserve energy.

The Intuition: Why Gradients Fail on Jagged Landscapes

Imagine a particle rolling down a smooth hill under the influence of gravity (the gradient) and random thermal fluctuations (noise). This is the physical intuition behind Langevin diffusion. If the hill is smooth, the particle tracks the geometry of the space reliably.

Now, replace the smooth hill with a jagged canyon full of sharp cliffs and V-shaped crevices. If the particle hits a V-shaped crevice, a standard discrete-time simulation will overshoot the bottom, compute an enormous, erroneous gradient on the opposite wall, and violently launch the particle out of the region. If it encounters a hard boundary, the gradient suddenly becomes infinite. As noted by Hadi Mohasel Afshar et al. in Reflection, Refraction, and Hamiltonian Monte Carlo, these sharp transitions break the numerical integration of the particle's path, destroying the mathematical guarantees of the sampler.

The Proximal Solution: Smoothing via Envelopes

How do we restore gradients to a non-smooth landscape without destroying its essential geometry? The most prominent answer borrows a classic tool from optimization: the Moreau-Yosida envelope.

Instead of sampling from the non-smooth potential $U(x)$, we sample from a regularized version $U_\lambda(x)$, defined via a minimization problem:

$$U_\lambda(x) = \inf_{y} \left\{ U(y) + \frac{1}{2\lambda} \|x - y\|^2 \right\}$$

The mapping that solves this minimization is the proximal operator. Crucially, even if $U(x)$ is completely non-differentiable, its Moreau-Yosida envelope $U_\lambda(x)$ is guaranteed to be continuously differentiable with a Lipschitz-continuous gradient.

In Efficient Bayesian Computation by Proximal Markov Chain Monte Carlo: When Langevin Meets Moreau, Alain Durmus et al. introduced the Moreau-Yoshida Unadjusted Langevin Algorithm (MYULA). By substituting the true gradient with the gradient of the Moreau-Yosida envelope, MYULA allows the sampler to glide smoothly over kinks and corners.

Subsequent work has refined this envelope approach to better preserve specific properties of the target distribution. For example, Armin Eftekhari et al. developed The forward-backward envelope for sampling with the overdamped Langevin algorithm, which preserves the exact modes (Maximum A Posteriori estimators) of the original distribution, unlike standard Moreau-Yosida smoothing. To handle ill-conditioned geometries, Han Liu et al. proposed Bregman Proximal Langevin Monte Carlo via Bregman-Moreau Envelopes, replacing standard Euclidean distances with Bregman divergences to adapt to the underlying shape of the distribution.

The Geometric Solution: Reflection and Refraction

Rather than smoothing out the discontinuities, an alternative approach is to embrace them and alter the dynamics of the sampler.

When a Hamiltonian particle hits a sharp boundary where the potential jumps, we can simulate it using the laws of physical optics. In Reflection, Refraction, and Hamiltonian Monte Carlo, Hadi Mohasel Afshar et al. demonstrated that if the particle has enough kinetic energy, it can "refract" through the boundary into the next region; if its energy is too low, it "reflects" off the boundary back into the current region. This allows the sampler to maintain energy conservation and navigate piecewise-continuous spaces without getting stuck.

This concept is extended to probabilistic programming languages by Yuan Zhou et al. in LF-PPL: A Low-Level First Order Probabilistic Programming Language for Non-Differentiable Models, which automatically tracks structural discontinuities to enable Discontinuous HMC.

Bypassing Gradients: Diffusion and Transformation

When gradients are entirely unavailable or too costly to compute due to severe jaggedness, researchers look to zeroth-order or generative frameworks.

The authors of Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion proposed a method that leverages denoising diffusion to bridge isolated modes and navigate discontinuous landscapes without ever computing a gradient. Alternatively, one can transform the coordinate space to map the non-smooth prior into a smooth one. In Bayesian inverse problems with $l_1$ priors: a Randomize-then-Optimize approach, Zheng Wang et al. utilized a coordinate transformation to "Gaussianize" non-smooth $l_1$-type priors, enabling efficient sampling via optimization techniques.

Theoretical Foundations and Convergence

How fast do these non-smooth samplers actually converge? For a long time, theoretical guarantees lagged behind empirical success. Recent breakthroughs, however, have established rigorous bounds.

Espen Bernton analyzed Langevin Monte Carlo through the lens of optimal transport in Langevin Monte Carlo and JKO splitting, proving convergence rates that hold even for non-differentiable potentials. For constrained spaces, Sebastien Bubeck et al. provided the first finite-time polynomial bounds for Projected Langevin Monte Carlo in Finite-Time Analysis of Projected Langevin Monte Carlo.

Furthermore, understanding how these algorithms scale with dimensionality is crucial. In Optimal Scaling Results for Moreau-Yosida Metropolis-adjusted Langevin Algorithms, Francesca Crucinio et al. proved that when sampling non-differentiable targets like the Laplace distribution, the optimal step size scales as $d^{-2/3}$, establishing a unique theoretical niche between standard random walks ($d^{-1/2}$) and smooth Langevin samplers ($d^{-1/6}$). Finally, Marien Renaud et al. extended these guarantees to highly complex settings in From stability of Langevin diffusion to convergence of proximal MCMC for non-log-concave sampling, proving convergence for algorithms operating on potentials that are simultaneously non-smooth and non-convex.

Key Foundational Work

Tutorial on Stochastic Simulation and Optimization Methods in Signal Processing (2015) — contributed 2 concept elements to this direction.
Reflection, Refraction, and Hamiltonian Monte Carlo (2015) — contributed 2 concept elements to this direction.
Finite-Time Analysis of Projected Langevin Monte Carlo (2015) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_smooth_distribution_sampling_b75000a3,
  title = {non-smooth distribution sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-smooth-distribution-sampling/rdr_b75000a3a9c8472380305c09520a3bd1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_smooth_distribution_sampling_b75000a3_v1,
  title = {non-smooth distribution sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-smooth-distribution-sampling/rdr_b75000a3a9c8472380305c09520a3bd1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake