Introduction
Sampling from high-dimensional probability distributions is a foundational challenge in modern statistics and machine learning, particularly within the context of Bayesian inference. One of the most prominent tools for this task is the Unadjusted Langevin Algorithm (ULA). However, ULA relies on the assumption that the "potential" of the target distribution—the function within the exponent of the density—is smooth.
In many practical applications, such as image reconstruction or sparse signal processing, this assumption is violated. Target distributions often involve non-smooth components, such as $L_1$ norms for sparsity or hard constraints (e.g., pixel values restricted to a specific range). While smoothing techniques like the Moreau-Yoshida (MY) envelope have been used to adapt ULA for these scenarios, they introduce a significant "bias": the peak of the smoothed distribution (the MAP estimator) shifts away from the peak of the original distribution. This paper introduces the Forward-Backward Unadjusted Langevin Algorithm (FBULA), a novel approach that leverages the Forward-Backward (FB) envelope to provide a smoothed approximation that perfectly preserves the original distribution's most likely state.
The Problem: Smoothing without Distortion
When dealing with a non-smooth potential $f(x) = g(x) + h(x)$, where $g$ is smooth and $h$ is non-smooth, traditional methods often replace $h$ with its Moreau-Yoshida envelope. While this makes the function differentiable, it alters the geometry of the distribution. Specifically, the minimizers of the MY-smoothed function do not coincide with the minimizers of the original function $f$. In sampling terms, this means the samples generated are effectively drawn from a distribution whose mode is shifted, leading to inaccurate posterior estimates.
The FBULA Methodology
The authors propose the Forward-Backward (FB) envelope as a superior proxy for non-smooth distributions. Originally developed for non-smooth optimization, the FB envelope is defined by combining the gradient of the smooth component $g$ with the proximal operator of the non-smooth component $h$.
Key Innovations:
- MAP Preservation: The mathematical advantage of the FB envelope is that it shares the exact same minimizers as the original non-smooth function. Consequently, the mode of the smoothed distribution used in FBULA is identical to the mode of the target distribution.
- The EULA Framework: The authors introduce the Envelope Unadjusted Langevin Algorithm (EULA), a generalized framework that can accommodate various smoothing envelopes, including MY and FB. This framework also supports "annealing," where the smoothing parameter is adjusted over time to refine the approximation.
- Theoretical Convergence: The paper provides rigorous non-asymptotic convergence bounds in the Wasserstein-1 distance. The authors demonstrate that even if the target distribution lacks global strong log-concavity, the FB envelope exhibits "strong convexity at a distance," allowing for provable convergence rates that were previously difficult to establish for non-smooth targets.
Experimental Results
The effectiveness of FBULA was evaluated across synthetic benchmarks and complex imaging tasks:
- Truncated Gaussians: In tests involving 2, 10, and 100 dimensions with hard boundary constraints, FBULA consistently provided a more accurate approximation of the expected values and variances compared to the Moreau-Yoshida Unadjusted Langevin Algorithm (MYULA). The advantage of FBULA became more pronounced as the dimensionality increased.
- Tomographic Image Reconstruction: Using the Shepp-Logan phantom (a 128x128 test image), the authors performed reconstruction from noisy, incomplete Fourier data under total-variation (TV) regularization. FBULA achieved a lower Mean-Squared Error (MSE) than MYULA. While both algorithms exhibited similar convergence speeds, FBULA’s stationary error was lower, resulting in a final image that was more faithful to the ground truth.
Insights and Implications
The core insight of this work is the bridge it builds between non-smooth optimization and MCMC sampling. By recognizing that a tool designed to find the minimum of a function (the FB envelope) is uniquely suited for sampling—because it does not shift that minimum—the authors have created a more precise tool for Bayesian inference.
While FBULA requires the smooth part of the potential to be thrice-differentiable ($C^3$) and involves Hessian-vector products in its gradient calculations, the computational cost per iteration remains comparable to existing methods like MYULA. The result is a sampling algorithm that offers higher accuracy for the same computational budget.
Conclusion
FBULA represents a significant step forward for sampling from non-smooth, high-dimensional distributions. By preserving the MAP estimator and providing strong theoretical guarantees, it addresses the inherent biases of previous smoothing-based Langevin methods. Future work may extend this envelope-based approach to more advanced dynamics, such as the Kinetic Langevin Algorithm, to further accelerate sampling in complex posterior landscapes.
Summary updated