arXiv:2602.14478stat.MLcs.DS2026-02

提出一种无需投影的约束采样新方法,可高效生成复杂约束下的随机样本。

Constrained and Composite Sampling via Proximal Sampler

  • 通过提升空间将约束采样转化为近均匀分布采样,仅需分离预言机和次梯度预言机
  • 在任意凸集上实现无偏采样,混合时间在瑞尼与卡方散度下有理论保证
  • 适用于贝叶斯推断等复合目标分布,特别适合缺乏几何先验的场景

本文研究两类对数凹采样问题:约束采样与复合采样。针对定义在凸集 $K \subset \mathbb{R}^d$ 上、密度正比于 $\exp(-f(x))$ 的目标分布($f$ 为凸函数),通过仿射提升将问题转化为在 $\mathbb{R}^{d+1}$ 中的近均匀分布采样。采用基于切平面法与拒绝采样的邻近采样器实现该过程,仅依赖 $K$ 的分离预言机和 $f$ 的次梯度预言机,无需投影、反射、障碍函数或镜映映射。第二部分研究复合采样,即目标密度正比于 $\exp(-f(x)-h(x))$,其中 $f$ 和 $h$ 均为闭凸函数。通过 $h$ 的提升构造双提升形式,嵌入 $\mathbb{R}^{d+2}$ 空间,并应用前述算法。保留 $f$ 与 $h$ 分离结构,展示了如何组合子梯度与邻近算子构建提升问题的分离预言机。对于两类问题,均建立了基于瑞尼与 $χ^2$ 散度的混合时间界。

原文摘要 · Abstract (English)

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.

采样算法凸优化贝叶斯推断随机算法

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。