Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities
Source: arxiv.org/abs/2611.05813
We study the query complexity of sampling from smooth distributions on $\mathbb R^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\gtrsim\log^2κ$. This shows…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.05813
curl -X POST /api/v1/records/arxiv/2611.05813/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.05813/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'