Let be a probability measure on and let be the set of probability measures on with bounded second moment. Let and be real valued functions on . We will find it convenient to define vector valued functions whose components are the functions respectively.

    The paper proposes a primal-dual Langevin Monte carlo algorithm to sample from the measure that solves satisfying the constraints

    The constrained sampling problem encompasses a number of practical problems such as sampling from convex sets, by sampling from for a close convex set .Rate constrained Bayesian models

    Let . be a smooth and strongly convex function. To the measure with density we can associate a diffusion process called Langevin diffusion, defined through the SDE The density of satisfies the Fokker-Planck equation In particular the KL divergence has the form In some sense the Fokker-Planck equation is the gradient flow of KL divergence in 2-Wasserstein space. The diffusion brings the distribution of closer to the measure from which we wish to draw samples.

    Discretization of the SDE through the forward Euler-Maruyama method leads to the Langevin Monte Carlo algorithm whereby is the size of the step. The convergence rate of this discretization has been established for potentials satisfying various smoothness and convexity conditions, or the measure satisfies appropriate LSI condition.

    Define the Lagrangian Put where is the normalizing constant. Then

    One has

    Define the dual function The Lagrangian minimizer is From the relaxation of the primal problem, we have the bound for all feasible .The dual problem seeks the optimal lower bound

    Suppose there exists together with constants and such that

2. for all
3. for all

Then

This reduces the sampling from the solution distribution of the primal problem to sampling from One can obtain via dual ascent. However it requires computing intractible integrals with respect to the distribution .