Zeroth-order log-concave sampling
Yunbum Kook
我们研究了对数凹采样的零阶查询复杂度，特别是使用成员资格预言从凸体中进行均匀采样。我们提出了一个简单的近端采样器变体，该变体在初始预热和输出保证之间实现了匹配的Rényi阶查询复杂度。具体来说，对于任何ε>0和q≥2，采样器从π_0初始化，输出一个样本，其法律在q-Rényi散度中ε-接近于π，即ℝ^d中凸体上的均匀分布，使用O(qM_q^q/(q-1)d^2 ‖covπ‖log1/ε)成员资格查询，其中M_q=‖dπ_0/dπ‖_L^q(π)。我们进一步引入了一个简单的退火方案，该方案在q-Rényi散度中产生一个预热开始（即M_q=O(1)）使用O(qd^2R^3/2 ‖covπ‖^1/4)查询，其中R^2=𝔼_π[|·|^2]。这在总变差和Rényi-无穷散度中预热开始生成的已知复杂度之间进行了插值。为了在退火方案中传递Rényi预热，我们建立了在同时热流下的超收缩性，并将其转化为在对数Sobolev不等式下近端采样器的改进混合保证。这些结果自然地扩展到通过评估预言可访问的一般对数凹分布，产生额外的二次查询。
We study the zeroth-order query complexity of log-concave sampling, specifically uniform sampling from convex bodies using membership oracles. We propose a simple variant of the proximal sampler that achieves the query complexity with matched Rényi orders between the initial warmness and output guarantee. Specifically, for any ε>0 and q≥2, the sampler, initialized at π_0, outputs a sample whose law is ε-close in q-Rényi divergence to π, the uniform distribution over a convex body in ℝ^d, using O...