Proximal Langevin Methods for Non-Smooth Sampling

56 concepts33 papers2 proposals

In machine learning and computer vision, we frequently encounter probability distributions with non-smooth or non-differentiable geometries. For instance, when performing Bayesian image restoration, we often employ sparsity-promoting priors like $L_1$ regularization or Total Variation to preserve sharp edges.

Standard gradient-based sampling algorithms, such as the Unadjusted Langevin Algorithm (ULA) or the Metropolis-Adjusted Langevin Algorithm (MALA), rely heavily on the gradient of the target distribution's log-density (the potential function, $U(x)$). When this potential is non-smooth, traditional samplers break down. They oscillate wildly near discontinuities, suffer from numerical instability, or fail to converge entirely.

To solve this, researchers have bridged the gap between convex optimization and stochastic simulation. By replacing or augmenting standard gradient steps with proximal operators, a new class of algorithms—proximal Langevin sampling—enables efficient, stable, and theoretically sound sampling from non-smooth landscapes.


Why Gradients Fail on Non-Smooth Landscapes

To understand why standard methods fail, imagine trying to sample from a Laplace distribution, where the potential function is $U(x) = |x|$. At $x = 0$, the gradient is undefined. If a sampler lands near the origin, a standard forward gradient step will overshoot, bouncing back and forth across the sharp ridge without ever properly exploring the high-density region at the peak.

As highlighted in surveys by Tourneret et al. and Schniter et al., this limitation historically restricted non-smooth models to optimization frameworks that only yield point estimates (like the Maximum A Posteriori or MAP estimator), sacrificing the rich uncertainty quantification provided by fully Bayesian frameworks.


The Proximal Operator as an Implicit Step

In non-smooth optimization, the standard tool for handling non-differentiability is the proximal operator. For a potential function $U$ and a step size $\gamma > 0$, the proximal operator is defined as:

$$\text{prox}_{\gamma U}(x) = \arg\min_{y} \left\{ U(y) + \frac{1}{2\gamma} \|y - x\|^2 \right\}$$

Geometrically, the proximal operator performs a balancing act. It looks ahead to find a point $y$ that minimizes the energy $U(y)$ while ensuring it does not stray too far from the current position $x$.

As shown by Bernton, substituting a standard gradient step with a proximal operator transforms a forward Euler step into an implicit, backward Euler-style step for the drift component of Langevin diffusion. This implicit step provides exceptional stability: instead of blindly following a local, potentially discontinuous gradient, the sampler evaluates the global structure of the potential nearby, neutralizing the oscillations that plague subgradient-based methods.


Smoothing the Landscape: The Moreau-Yoshida Envelope

One of the most prominent ways to integrate proximal operators into Langevin dynamics is through the Moreau-Yoshida envelope. Instead of sampling from the non-smooth potential $U(x)$ directly, we sample from a smoothed approximation $U^\gamma(x)$, defined as:

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

The Moreau-Yoshida envelope acts as a regularized version of the potential. Remarkably, even if $U(x)$ is sharp and non-differentiable, $U^\gamma(x)$ is guaranteed to be continuously differentiable. Its gradient possesses a beautifully simple, closed-form relationship with the proximal operator:

$$\nabla U^\gamma(x) = \frac{1}{\gamma} \left( x - \text{prox}_{\gamma U}(x) \right)$$

This insight forms the foundation of the Moreau-Yoshida Unadjusted Langevin Algorithm (MYULA), analyzed by Durmus et al.. By substituting $\nabla U^\gamma(x)$ into the standard Langevin update, MYULA allows practitioners to use standard gradient-based MCMC machinery on a smooth proxy distribution.

Non-Smooth Potential U(x) ───► Moreau-Yoshida Envelope Uⁿ(x) ───► Smooth Gradient ───► Standard ULA Step

This approach has proven highly effective in high-dimensional imaging inverse problems. For example, Dobigeon et al. applied proximal MCMC methods to image restoration under Poisson noise, while Eldaly et al. utilized MYULA for accelerated Magnetic Resonance Image (MRI) reconstruction, providing both high-quality images and reliable, physics-grounded uncertainty maps.


Operator Splitting and Direct Proximal Stepping

Often, a target potential can be decomposed into a composite form: $U(x) = f(x) + g(x)$, where $f(x)$ is smooth (e.g., a Gaussian likelihood) and $g(x)$ is non-smooth (e.g., an $L_1$ penalty).

Rather than smoothing the entire joint potential, we can use operator splitting. The Proximal Stochastic Gradient Langevin Algorithm (PSGLA) handles this by taking a standard forward gradient step on the smooth part $f$, and an implicit proximal step on the non-smooth part $g$.

Salim et al. demonstrated that injecting Gaussian noise directly into this split framework ensures that the Markov chain correctly explores the target distribution while maintaining the stability inherent to proximal optimization. In a subsequent work, Salim et al. provided a primal-dual interpretation of this algorithm, proving that it can be viewed as a forward-backward splitting method for monotone operators operating within the Wasserstein space of probability measures.

Alternative Envelopes and Higher-Order Discretizations

While Moreau-Yoshida smoothing is powerful, it can slightly shift the modes (MAP estimators) of the target distribution. To address this, Eftekhari et al. introduced the Forward-Backward (FB) envelope for sampling. The FB envelope acts as an admissible smooth proxy that preserves the exact modes of the original distribution, yielding more accurate samples in highly constrained settings.

To improve convergence speed, Klatzer et al. developed the Implicit Midpoint Langevin Algorithm (IMLA). By utilizing an implicit midpoint discretization rather than a forward Euler discretization, IMLA achieves accelerated convergence scaling with the square root of the condition number ($\sqrt{\kappa}$), significantly improving the fidelity of uncertainty quantification.


Theoretical Guarantees and Extensions

The integration of proximal tools into sampling has opened up several theoretical and algorithmic frontiers:

  • Non-Convex Convergence: Early theoretical guarantees for proximal samplers were strictly limited to convex potentials. However, Renaud et al. established a stability framework for Langevin diffusion showing that proximal Langevin methods converge reliably even under non-convex and non-smooth potentials.
  • Optimal Scaling Laws: For Metropolis-adjusted variants (MY-MALA), Crucinio et al. proved that non-differentiable targets require a unique step-size scaling of $d^{-2/3}$ (where $d$ is the dimension), carving out a distinct efficiency niche between random-walk Metropolis ($d^{-1}$) and smooth MALA ($d^{-1/3}$).
  • Beyond Overdamped Langevin: The proximal paradigm has been successfully extended to other sampling architectures. Chaâri et al. integrated proximity operators into Hamiltonian Monte Carlo (HMC) to sample from non-smooth energy functions, while Encinar et al. combined proximal steps with particle-based Langevin dynamics (PIPLA) for parameter estimation.
  • The Restricted Gaussian Oracle: For general structured log-concave sampling, Lee et al. and Liang et al. formalized the sampling analog of a proximal operator as a primitive that draws samples from the product of a Gaussian density and an exponentiated convex function, providing a clean framework for future algorithm design.

Key Foundational Work

Tutorial on Stochastic Simulation and Optimization Methods in Signal Processing (2015) — contributed 2 concept elements to this direction.
Why MCA? Nonlinear sparse coding with spike-and-slab prior for neurally plausible image encoding (2012) — 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_proximal_langevin_sampling_4a9d93e3,
  title = {proximal Langevin sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/proximal-langevin-sampling/rdr_4a9d93e319f5434693f2a943bf2f8586},
  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_langevin_sampling_4a9d93e3_v1,
  title = {proximal Langevin sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/proximal-langevin-sampling/rdr_4a9d93e319f5434693f2a943bf2f8586/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake