Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin Algorithm

Adil Salim, Peter Richtárik

The Challenge of Constrained Sampling

Bayesian inference and machine learning frequently require sampling from a target distribution $\mu^* \propto \exp(-V(x))$. Often, the potential function $V$ is composite, taking the form $V = F + G$, where $F$ is a smooth loss (such as a log-likelihood) and $G$ is a nonsmooth regularizer or an indicator function representing hard constraints (e.g., restricting $x$ to a specific box or sphere).

While standard Langevin dynamics excel when $V$ is smooth, they struggle with the "sharp edges" or boundaries introduced by $G$. Previous attempts to handle such constraints, such as the Projected Langevin Algorithm, yielded extremely pessimistic theoretical complexity bounds—sometimes as high as $\mathcal{O}(1/\varepsilon^{12})$. A primary reason for this bottleneck is that the standard analytical tool, the Kullback-Leibler (KL) divergence, can become infinite when an algorithm's iterates step outside the support of the target distribution, causing traditional convergence proofs to break down.

A New Perspective: Optimal Transport and Monotone Inclusion

To overcome this limitation, the authors bridge Optimal Transport and Monotone Operator Theory. They treat the sampling task as a minimization problem of the KL divergence over the Wasserstein space of probability measures. Recognizing that KL divergence is an insufficient "yardstick" in constrained settings, they introduce a novel Lagrangian function and a duality gap specifically tailored for this space.

Crucially, they prove that "strong duality" holds even when the potential is nonsmooth. This duality gap remains finite and provides a robust, mathematically sound alternative for proving convergence.

The PSGLA Algorithm and Primal-Dual Optimization

Building on this duality, the authors demonstrate that the Proximal Stochastic Gradient Langevin Algorithm (PSGLA) can be viewed as a stochastic Forward-Backward algorithm. In classical optimization, this algorithm finds the zero of the sum of two monotone operators; here, the operators are defined over probability distributions.

The PSGLA update rule consists of a gradient step on the smooth component $F$, the addition of Gaussian noise (the Langevin step), and the application of a proximal operator (a generalized projection) for the nonsmooth component $G$:

$$x^{k+1} = \text{prox}_{\gamma G} \left( x^k - \gamma \nabla f(x^k, \xi^{k+1}) + \sqrt{2\gamma}W^{k+1} \right)$$

A profound insight of this work is that when constraints are involved, the Langevin algorithm behaves exactly like primal-dual algorithms used in classical convex optimization (such as the Chambolle-Pock algorithm). Furthermore, unlike smoothing methods like the Moreau-Yosida Unadjusted Langevin Algorithm (MYULA) that allow iterates to wander outside the constraint set during the process, PSGLA naturally preserves support, keeping iterates strictly within the domain of $G$.

Key Results and Complexity Leap

The theoretical framework yields a massive leap in complexity bounds. For strongly convex potentials, the authors prove that PSGLA achieves a complexity of $\mathcal{O}(1/\varepsilon^2)$ in terms of the 2-Wasserstein distance. This represents a dramatic improvement over the $\mathcal{O}(1/\varepsilon^{12})$ rate previously associated with projected Langevin methods in total variation.

These results hold even for target distributions with "hard" boundaries (i.e., not fully supported). The authors validate their theoretical findings with numerical experiments, successfully sampling from distributions supported by sets of positive semi-definite matrices with trace constraints.

Limitations and Future Directions

While the duality gap is a powerful theoretical mechanism, its physical or statistical interpretation is less intuitive than standard metrics like Total Variation or Wasserstein distance. Connecting this gap to other common convergence metrics remains an open research area.

Additionally, the current theory relies heavily on the log-concavity (convexity) of the target distribution, making the extension to non-convex potentials (multi-modal distributions) a significant challenge. Finally, while the $\mathcal{O}(1/\varepsilon^2)$ rate is optimal with respect to $\varepsilon$, the constants hidden in the asymptotic notation depend on the dimension $d$ and potential properties, which can still be large in high-dimensional settings.

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, 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 (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 $\cO(1/\varepsilon^2)$ in terms of the 2-Wasserstein distance. In contrast, the complexity of the Projected Langevin Algorithm is $\cO(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