Constrained and Composite Sampling via Proximal Sampler

Thanh Dang; Jiaming Liang

stat.MLFeb 16, 2026

Constrained and Composite Sampling via Proximal Sampler

Authors: Thanh Dang, Jiaming Liang

Organizations: Department of Computer Science, University of Rochester, Rochester, NY 14620. · Goergen Institute for Data Science and Artificial Intelligence (GIDS-AI) and Department of Computer Science, University of Rochester, Rochester, NY 14620

Abstract

We study two log-concave sampling problems: constrained sampling and composite sampling. First, we consider sampling from a target distribution with density proportional to $\exp(-f(x))$ supported on a convex set $K \subset \mathbb{R}^d$ , where $f$ is convex. The main challenge is enforcing feasibility without degrading mixing. Using an epigraph transformation, we reduce this task to sampling from a nearly uniform distribution over a lifted convex set in $\mathbb{R}^{d+1}$ . We then solve the lifted problem using a proximal sampler. Assuming only a separation oracle for $K$ and a subgradient oracle for $f$ , we develop an implementation of the proximal sampler based on the cutting-plane method and rejection sampling. Unlike existing constrained samplers that rely on projection, reflection, barrier functions, or mirror maps, our approach enforces feasibility using only minimal oracle access, resulting in a practical and unbiased sampler without knowing the geometry of the constraint set. Second, we study composite sampling, where the target is proportional to $\exp(-f(x)-h(x))$ with closed and convex $f$ and $h$ . This composite structure is standard in Bayesian inference with $f$ modeling data fidelity and $h$ encoding prior information. We reduce composite sampling via an epigraph lifting of $h$ to constrained sampling in $\mathbb{R}^{d+1}$ , which allows direct application of the constrained sampling algorithm developed in the first part. This reduction results in a double epigraph lifting formulation in $\mathbb{R}^{d+2}$ , on which we apply a proximal sampler. By keeping $f$ and $h$ separate, we further demonstrate how different combinations of oracle access (such as subgradient and proximal) can be leveraged to construct separation oracles for the lifted problem. For both sampling problems, we establish mixing time bounds measured in Rényi and $χ^2$ divergences.

Figures & tables

U\leq\exp\left(-\Theta_{y,s}^{\eta,Q}(w)+\mathcal{P}_{1}(w)\right),

(14)

Algorithm 2 RGO implementation of Algorithm 1

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

U\leq\exp\left(-\widetilde{\Theta}_{y,u,v}^{\eta,\widetilde{Q}}(p)+\widetilde{\mathcal{P}}_{1}(p)\right)

(80)

Appendix

Algorithm 5 RGO implementation of Algorithm 4

Explore similar work

May 12, 2026

A proximal gradient algorithm for composite log-concave sampling

We propose an algorithm to sample from composite log-concave distributions over

\mathbb{R}^d

, i.e., densities of the form

π\propto e^{-f-g}

, assuming access to gradient evaluations of

α_f

-convex

f

and a restricted Gaussian oracle (RGO) for

α_g

-convex

g

, where

α_g \ge 0

. The latter requirement means that we can easily sample from the density

\text{RGO}_{g,h,y}(x) \propto \exp(-g(x) -\frac{1}{2h}||y-x||^2)

, which is the sampling analogue of the proximal operator for

g

. If

f + g

α

-convex and

f

β

-smooth, our sampler achieves

\varepsilon

error in total variation distance using

\widetilde{\mathcal O}(κ\sqrt d \log^4(1/\varepsilon))

oracle calls where

κ:= 1 \vee β/α

, with

0\le α_g \le β

and

α:= α_f + α_g > 0

, which matches prior state-of-the-art results for the case

g=0

. We further extend our results to cases where (1)

π

is non-log-concave but satisfies a Poincaré or log-Sobolev inequality, and (2)

f

is non-smooth but Lipschitz.

Linghai Liu, Sinho Chewi

Yale University

Log-Concave Sampling

Ask PDF

May 12, 2026

Manifold Sampling via Entropy Maximization

Sampling from constrained distributions has a wide range of applications, including in Bayesian optimization and robotics. Prior work establishes convergence and feasibility guarantees for constrained sampling, but assumes that the feasible set is connected. However, in practice, the feasible set often decomposes into multiple disconnected components, which makes efficient sampling under constraints challenging. In this paper, we propose MAnifold Sampling via Entropy Maximization (MASEM) for sampling on a manifold with an unknown number of disconnected components, implicitly defined by smooth equality and inequality constraints. The presented method uses a resampling scheme to maximize the entropy of the empirical distribution based on k-nearest neighbor density estimation. We show that, in the mean field, MASEM decreases the KL-divergence between the empirical distribution and the maximum-entropy target exponentially in the number of resampling steps. We instantiate MASEM with multiple local samplers and demonstrate its versatility and efficiency on synthetic and robotics-based benchmarks. MASEM enables fast and scalable mixing across a range of constrained sampling problems, improving over alternatives by an order of magnitude in Sinkhorn distance with competitive runtime.

Cornelius V. Braun, Tilman Burghoff, Marc Toussaint

Technische Universität Berlin · Robotics Institute Germany

Markov Chain Monte Carlo

Ask PDF

Jun 10, 2026

A unified complexity bound for logconcave sampling

We give a simple, unified, and nearly tight bound for sampling arbitrary logconcave distributions from a warm start using the In-and-Out algorithm along with exponential lifting. The main new ingredient in the analysis is an improved bound on the Poincaré constant of a lifted distribution. As a consequence, the resulting convergence rate is nearly tight for both constrained settings (e.g., Gaussian restricted to a convex body) and well-conditioned settings (e.g., strongly logconcave and smooth densities).

Yunbum Kook, Santosh S. Vempala

Georgia Tech

Log-Concave Sampling

Ask PDF