canonical setting

Strongly log-concave + log-smooth

$\pi\propto e^{-V}$ , $\alpha I\preceq\nabla^2V\preceq\beta I$ , $\kappa=\beta/\alpha$ .

Updated Aug 6, 2026

Upper and lower bounds

Comparison table

6 scoped results. Tildes suppress logarithmic factors.

Best-known and comparison results for Strongly log-concave + log-smooth
Result	Algorithm or model	Complexity	Guarantee	Oracle / start	Assumptions and notes	Review	Sources
best upper	Exact ULD / FORS	$\widetilde O(\kappa^{2/3}d^{1/3}\,\operatorname{polylog}(1/\varepsilon))$	$\mathcal R_q\le\varepsilon^2$	$V,\nabla V$ Cold start under the paper's setup	Exact path-space rejection implementation; fixed Rényi order.Newest claimed frontier; theorem-level transcription still needs human checking.	Citedpreprint	Chen–Chewi–Rakhlin–Zhang (2026), Theorem 3.2 ↗
best lower	General first-order oracle lower bound	$\widetilde\Omega(\min\{\sqrt\kappa\log d,d\})$	Constant total-variation accuracy	$V,\nabla V$ queriesAny randomized algorithm in the stated model	Gaussian subclass; parameter ranges in the theorem.Fixed $d\ge2$ also has the tight $\Theta_d(\log\kappa)$ dependence.	Checkedpublished	Chewi et al. (2023), query lower bounds ↗
upper	MALA	$\widetilde O(\kappa\sqrt d\,\operatorname{polylog}(1/\varepsilon))$	$\lVert\mu_N-\pi\rVert_{\rm TV}\le\varepsilon$	$V,\nabla V$ $\chi^2(\mu_0\Vert\pi)=O(1)$	Standard strong convexity and smoothness only.Stable high-accuracy baseline; warm-start cost is separate.	Checkedmonograph	Chewi (2026), Theorem 7.3.5 ↗
upper	Randomized-midpoint ULMC	$\widetilde O(\kappa^{5/6}d^{1/3}/\varepsilon^{2/3})$	$\lVert\mu_N-\pi\rVert_{\rm TV}\le\varepsilon$	$\nabla V$ Known mode / specified Gaussian start	$\nabla V(0)=0$ ; low-accuracy regime.Do not compare directly with polylogarithmic high-accuracy rows.	Checkedmonograph	Chewi (2026), Theorem 5.3.17 ↗
upper	Block-Krylov Gaussian sampler	$O((d\wedge\sqrt\kappa)\log(d/\varepsilon^2))$	$\sqrt{\operatorname{KL}}\le\varepsilon$	Gaussian matrix-vector / gradientCentered Gaussian model	Gaussian subclass.Nearly tight for Gaussians, not a general-target upper bound.	Checkedmonograph	Chewi (2026), Theorem 9.4.1 ↗
lower	MALA lower bound	$\widetilde\Omega(\kappa\sqrt d\log(1/\varepsilon))$	Constant warm start; TV accuracy	MALA transitions $\chi^2(\mu_0\Vert\pi)\lesssim1$	Algorithm-specific, for every fixed MALA step size.Matches the warm-start MALA upper bound up to logarithms.	Checkedmonograph	Chewi (2026), Theorem 7.6.5 ↗

Scope

The default oracle returns $V(x)$ and $\nabla V(x)$ . Rows are not directly comparable unless the error metric, initialization, and additional smoothness assumptions match.

Reading the frontier

The newest high-accuracy upper bound uses exact simulation of underdamped Langevin diffusion and is still a preprint. The checked MALA and randomized-midpoint rows are retained as stable baselines. The general first-order lower bound is much smaller than the newest upper bound, so the oracle-complexity gap remains open.

Conventions

$\widetilde O$ and $\widetilde\Omega$ suppress logarithmic factors. A warm start means bounded Rényi or chi-squared divergence as specified in the row.