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