Abstract
We consider the task of sampling with respect to a log-concave probability distribution where the potential is composite, consisting of a smooth convex term and a nonsmooth convex term that may take infinite values. By viewing the target distribution as a minimizer of the Kullback-Leibler (KL) divergence in the Wasserstein space, we establish a strong duality result for this minimization problem. We leverage the resulting duality gap to analyze the complexity of the Proximal Stochastic Gradient Langevin Algorithm (PSGLA). Our framework treats PSGLA as a primal-dual algorithm, proving that for strongly convex potentials, PSGLA achieves a complexity of $O(1/\varepsilon^2)$ in terms of the 2-Wasserstein distance. This represents a significant improvement over the $O(1/\varepsilon^{12})$ complexity previously established for the Projected Langevin Algorithm in convex settings.
Introduction
Sampling from complex probability distributions is a fundamental challenge in Bayesian statistics and machine learning. While the Langevin Algorithm is highly effective for smooth distributions, many modern applications involve "messy" potentials. These include constrained distributions (where parameters must reside within a specific set) or nonsmooth regularizers such as sparsity-inducing priors.
Traditionally, handling these nonsmooth components required either smoothing the potential—which introduces bias—or employing projection-based methods. However, the theoretical convergence rates for these approaches have historically been poor. This paper provides a new theoretical lens for the Proximal Stochastic Gradient Langevin Algorithm (PSGLA), re-interpreting it as a primal-dual optimization method acting on the space of probability measures.
Problem Formulation
The objective is to sample from a distribution $\mu^* \propto \exp(-V(x))$, where the potential $V$ is composite: $$V(x) = F(x) + G(x)$$ In this formulation, $F(x)$ is a smooth, convex function (such as a log-likelihood), and $G(x)$ is a nonsmooth, convex function. Crucially, $G$ can take infinite values, allowing it to act as an indicator function for a constraint set $C$. When $G$ is an indicator function, the distribution is constrained to the support of $C$. Standard Langevin dynamics are ill-suited for such cases because they rely on gradients that are undefined for nonsmooth or infinite terms.
A Primal-Dual Perspective in Wasserstein Space
The authors bridge the gap between optimal transport and convex optimization through three key steps:
- Sampling as Optimization: The task of sampling is viewed as minimizing the KL divergence within the Wasserstein space (the space of probability measures).
- Duality Reformulation: The authors introduce a Lagrangian and a "duality gap" for this KL minimization. In constrained settings, the KL divergence itself can become infinite, making it an unreliable metric for tracking convergence. The duality gap, however, remains well-defined and provides a robust measure of progress.
- Monotone Operators: PSGLA is shown to be equivalent to a stochastic Forward-Backward algorithm involving monotone operators. This allows the application of advanced optimization theory to the analysis of sampling algorithms.
Theoretical Contributions and Complexity
The primary contribution of this work is the dramatic improvement in proven convergence rates. For strongly convex potentials, the authors demonstrate that PSGLA achieves a complexity of $O(1/\varepsilon^2)$ in the 2-Wasserstein distance.
To put this in perspective, the previously known complexity for the Projected Langevin Algorithm—a common choice for constrained sampling—was $O(1/\varepsilon^{12})$ in terms of total variation. By viewing the proximal step as a primal-dual update, the authors show that PSGLA is not merely a heuristic fix for nonsmoothness, but a mathematically rigorous algorithm that inherits the stability and efficiency of proximal methods in optimization.
Numerical Validation
The theoretical findings were validated using controlled numerical experiments, specifically focusing on sampling from a Wishart distribution (a distribution over symmetric positive-definite matrices). The experiments compared PSGLA against the Moreau-Yosida Unadjusted Langevin Algorithm (MYULA).
Key observations from the experiments include:
- Stability: PSGLA proved more stable than MYULA because it does not require a smoothing parameter ($\lambda$), which often complicates the tuning of MYULA.
- Feasibility: Iterates of PSGLA consistently remained within the "feasible" region (the support of the distribution). In contrast, competing methods often drifted into regions where the distribution was undefined, leading to numerical instability.
Conclusion
This work provides a unified framework for smooth, constrained, and nonsmooth sampling. By interpreting PSGLA through the lens of primal-dual optimization, the authors provide the first high-efficiency convergence bounds for constrained log-concave sampling. While future work remains to connect the duality gap to traditional metrics like Total Variation in the general convex (non-strongly convex) case, this paper establishes PSGLA as a state-of-the-art method for complex Bayesian inference tasks.
Summary updated