Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities
Abstract
We study the query complexity of sampling from smooth distributions on ℝd using first-order oracles. For d-dimensional strongly log-concave targets with condition number κ=2, we prove that any randomized sampler requires exp(Ω(log1/3 d)) queries even from a constant warm start. This rules out polylogarithmic dimension dependence and strictly separates strongly log-concave sampling from Gaussian sampling. For targets with L-smooth potentials satisfying an α-log-Sobolev inequality with κ= L/α, we prove an Ω(κ) query lower bound for d≳log2κ. This shows that log-Sobolev sampling is strictly harder than strongly log-concave sampling. Our proofs construct instance-dependent tests that target samples typically pass but outputs of algorithms making few queries typically fail. For strongly log-concave targets, we embed a sequence of hidden Gaussian into high-degree tensor polynomial with smooth gates, forcing any algorithm to uncover the layers sequentially. The log-Sobolev construction hides a constant fraction of the target mass in angular caps while controlling the log-Sobolev constant via delicate estimates.
Related
- Strong log-concavity in probit regression
- Subpolynomial-Query Proximal Sampling Beyond Log-Concavity
- Stability under mixtures of transportation inequalities and restricted log-Sobolev inequalities
- A Note on Fractional Sobolev inequalities revisited
- Sharp Sobolev inequalities on minimal immersions via optimal transport
BibTeX
@misc{zhou2026towards,
title = {{Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities}},
author = {Huanjian Zhou and Taiji Suzuki},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05813},
eprint = {2611.05813},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05813},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities
AU - Huanjian Zhou
AU - Taiji Suzuki
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.05813
UR - https://arxiv.org/abs/2611.05813
AB - We study the query complexity of sampling from smooth distributions on ℝ^d using first-order oracles. For d-dimensional strongly log-concave targets with condition number κ=2, we prove that any randomized sampler requires exp(Ω(log^1/3 d)) queries even from a constant warm start. This rules out polylogarithmic dimension dependence and strictly separates strongly log-concave sampling from Gaussian sampling. For targets with L-smooth potentials satisfying an α-log-Sobolev inequality with κ= L/α, we prove an Ω(κ) query lower bound for d≳log^2κ. This shows that log-Sobolev sampling is strictly harder than strongly log-concave sampling. Our proofs construct instance-dependent tests that target samples typically pass but outputs of algorithms making few queries typically fail. For strongly log-concave targets, we embed a sequence of hidden Gaussian into high-degree tensor polynomial with smooth gates, forcing any algorithm to uncover the layers sequentially. The log-Sobolev construction hides a constant fraction of the target mass in angular caps while controlling the log-Sobolev constant via delicate estimates.
ER -