Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities

概要

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 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.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities

# 概要
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…

# 原典
https://arxiv.org/abs/2611.05813

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。