[2507.18021] Zeroth-order Logconcave Sampling

Mathematics > Statistics Theory arXiv:2507.18021 (math) [Submitted on 24 Jul 2025 (v1), last revised 2 Apr 2026 (this version, v2)] Title:Zeroth-order Logconcave Sampling Authors:Yunbum Kook, Santosh S. Vempala View a PDF of the paper titled Zeroth-order Logconcave Sampling, by Yunbum Kook and 1 other authors View PDF HTML (experimental) Abstract:We study the zeroth-order query complexity of sampling from a general logconcave distribution: given access to an evaluation oracle for a convex function $V:\mathbb{R}^{d}\rightarrow\mathbb{R}\cup\{\infty\}$, output a point from a distribution within $\varepsilon$-distance to the density proportional to $e^{-V}$. A long line of work provides efficient algorithms for this problem in TV distance, assuming a pointwise warm start (i.e., in $\infty$-Rényi divergence), and using annealing to generate such a warm start. Here, we address the natural and more general problem of using a $q$-Rényi divergence warm start to generate a sample that is $\varepsilon$-close in $q$-Rényi divergence. Our first main result is an algorithm with this end-to-end guarantee with state-of-the-art complexity for $q=\widetilde{\Omega}(1)$. Our second result shows how to generate a $q$-Rényi divergence warm start directly via annealing, by maintaining $q$-Rényi divergence throughout, thereby obtaining a streamlined analysis and improved complexity. Such results were previously known only under the stronger assumptions of smoothness and access to first-order or...