canonical setting

Convex body + membership oracle

$\pi=\operatorname{unif}(K)$ , $B(0,1)\subseteq K$ , membership queries; $\Lambda=\lVert\operatorname{Cov}(\pi)\rVert_{\rm op}$ .

Updated Aug 6, 2026

Upper and lower bounds

Comparison table

4 scoped results. Tildes suppress logarithmic factors.

Edit table

Best-known and comparison results for Convex body + membership oracle
Result	Algorithm or model	Complexity	Guarantee	Oracle / start	Assumptions and notes	Review	Sources
best upper	Proximal / In-and-Out with restart	$\widetilde O(qd^2\Lambda\log^6(1/\varepsilon))$	$\mathcal R_q\le\varepsilon$	Membership $q$ -Rényi warm start, $M_q\le10$	Finite Rényi order and covariance scale as defined in the paper.Provisional transcription of the current finite- $q$ frontier.	Citedpreprint	Kook–Vempala (2026), Theorem 1.1, v2 ↗
lower unknown	General sampling lower bound	Unknown	Membership-query sampling in matching divergence	MembershipWarm or end-to-end must be specified	No matching general lower bound located.The cited obstruction is not a general oracle lower bound.	Unverifiedno primary source	Kook–Vempala (2026), Gaussian-annealing obstruction ↗
upper	Rényi-preserving annealing	$\widetilde O(qd^2R^{3/2}\Lambda^{1/4}+qd^2\Lambda\log^7(1/\varepsilon))$	$\mathcal R_q\le\varepsilon$	MembershipEnd-to-end / cold annealing	$R^2=\mathbb E_\pi\lVert X\rVert^2$ .In isotropic position this is roughly $d^{11/4}$ up to logarithms.	Citedpreprint	Kook–Vempala (2026), Corollary 1.6, v2 ↗
upper	Constrained proximal sampler	$\widetilde O(d^3\,\operatorname{polylog}(1/\varepsilon))$	$\mathcal R_\infty\le\varepsilon$	MembershipPaper's end-to-end setup	Stronger infinite-Rényi target; compare separately from finite $q$ .Published comparator with a stronger divergence guarantee.	Checkedpublished	Kook–Zhang (SODA 2025) ↗

Scope

This page concerns sampling, not volume estimation. It records finite- $q$ Rényi and $R_\infty$ guarantees separately, and it keeps warm-start and annealed cold-start costs distinct.

Lower bounds

The familiar $\widetilde\Omega(d^2)$ membership-query bound in the monograph is for volume estimation, not sampling. It is therefore not placed in this table. The paper on zeroth-order log-concave sampling proves a Gaussian-annealing obstruction, but not a general membership-oracle sampling lower bound.