Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin Algorithm

Adil Salim, Peter Richtárik

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:

  1. Sampling as Optimization: The task of sampling is viewed as minimizing the KL divergence within the Wasserstein space (the space of probability measures).
  2. 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.
  3. 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

Abstract

We consider the task of sampling with respect to a log concave probability distribution. The potential of the target distribution is assumed to be composite, \textit{i.e.}, written as the sum of a smooth convex term, and a nonsmooth convex term possibly taking infinite values. The target distribution can be seen as a minimizer of the Kullback-Leibler divergence defined on the Wasserstein space (\textit{i.e.}, the space of probability measures). In the first part of this paper, we establish a strong duality result for this minimization problem. In the second part of this paper, we use the duality gap arising from the first part to study the complexity of the Proximal Stochastic Gradient Langevin Algorithm (PSGLA), which can be seen as a generalization of the Projected Langevin Algorithm. Our approach relies on viewing PSGLA as a primal dual algorithm and covers many cases where the target distribution is not fully supported. In particular, we show that if the potential is strongly convex, the complexity of PSGLA is $O(1/\varepsilon^2)$ in terms of the 2-Wasserstein distance. In contrast, the complexity of the Projected Langevin Algorithm is $O(1/\varepsilon^{12})$ in terms of total variation when the potential is convex.
BibTeX
@inproceedings{salim2020primal,
  author = {Adil Salim and Peter Richtárik},
  title = {{Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin Algorithm}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=qtJjcosUWk},
}
Figure