Zeroth-order log-concave sampling
Zeroth-order log-concave sampling
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 $\varepsilon>0$ and $q\geq2$, the sampler, initialized at $Ï_{0}$, outputs a sample whose law is $\varepsilon$-close in $q$-Rényi divergence to $Ï$, the uniform distribution over a convex body in $\mathbb{R}^{d}$, using $\widetilde{O}(qM_{q}^{q/(q-1)}d^{2}\,\lVert\operatorname{cov}Ï\rVert\log\frac{1}{\varepsilon})$ membership queries, where $M_{q}=\lVert\text{d}Ï_{0}/\text{d}Ï\rVert_{L^{q}(Ï)}$. We further introduce a simple annealing scheme that produces a warm start in $q$-Rényi divergence (i.e., $M_{q}=O(1)$) using $\widetilde{O}(qd^{2}R^{3/2}\,\lVert\operatorname{cov}Ï\rVert^{1/4})$ queries, where $R^{2}=\mathbb{E}_Ï[|\cdot|^{2}]$. This interpolates between known complexities for warm-start generation in total variation and Rényi-infinity divergence. To relay a Rényi warmness across the annealing scheme, we establish hypercontractivity under simultaneous heat flow and translate it into an improved mixing guarantee for the proximal sampler under a logarithmic Sobolev inequality. These results extend naturally to general log-concave distributions accessible via evaluation oracles, incurring additional quadratic queries.
Yunbum Kook
数学
Yunbum Kook.Zeroth-order log-concave sampling[EB/OL].(2025-07-24)[2025-08-18].https://arxiv.org/abs/2507.18021.点此复制
评论