提出新采样算法，实现凸体上均匀分布的高效无偏采样。
Oracle-based Uniform Sampling from Convex Bodies
- 基于近端采样与受限高斯预言机，结合投影或分离预言机实现采样。
- 在非渐近复杂度下保证采样精度，使用Rényi和χ²散度量化误差。
- 适用于需要高质量均匀采样的优化与生成任务，如高维几何采样。
我们提出了新的马尔可夫链蒙特卡洛算法，用于从凸体 $K$ 中采样均匀分布。算法基于近端采样，利用在扩展分布上的吉布斯采样，并假设可访问受限高斯预言机（RGO）。本工作的关键贡献是为凸体 $K$ 上的均匀采样提供了 RGO 的高效实现，突破了经典与现代均匀采样器常用的成员预言机模型，转而采用凸优化中常见的更丰富预言机访问方式。通过拒绝采样与对 $K$ 的投影预言机或分离预言机的访问，实现了 RGO。在两种预言机模型下，我们给出了获得无偏样本的非渐近复杂度保证，精度以 Rényi 散度和 $χ^2$-散度衡量，并通过数值实验验证了理论结果。
原文摘要 · Abstract (English)
We propose new Markov chain Monte Carlo algorithms to sample a uniform distribution on a convex body $K$. Our algorithms are based on the proximal sampler, which uses Gibbs sampling on an augmented distribution and assumes access to the so-called restricted Gaussian oracle (RGO). The key contribution of this work is an efficient implementation of the RGO for uniform sampling on convex $K$ that goes beyond the membership-oracle model used in many classical and modern uniform samplers, and instead leverages richer oracle access commonly assumed in convex optimization. We implement the RGO via rejection sampling and access to either a projection oracle or a separation oracle on $K$. In both oracle models, we provide non-asymptotic complexity guarantees for obtaining unbiased samples, with accuracy quantified in Rényi divergence and $χ^2$-divergence, and we support these theoretical guarantees with numerical experiments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。