Abstract:Guarantees for algorithms sampling from nonlogconcave target measures on $\mathbb{R}^d$ are studied. For the class of measures with logdensities that have bounded Hessians and are strongly concave outside a Euclidean ball of radius $R$, it is shown that complete polynomial complexity can in fact be achieved if $R\leq c\sqrt{d}$. On the other hand, an exponential number of point evaluations is shown to be generally necessary for any algorithm as soon as $R\geq C\sqrt{d}$ for constants $C>c>0$. Importance sampling with a tail-matching proposal achieves the former, owing to a blessing of dimensionality. It is also shown that if strong concavity outside a ball is replaced by a distant dissipativity condition, then sampling guarantees must generally scale exponentially with $d$ in essentially all parameter regimes.
From: Martin Chak [view email]
[v1]
Tue, 12 Nov 2024 13:19:23 UTC (57 KB)
[v2]
Mon, 26 May 2025 16:25:19 UTC (119 KB)
[v3]
Wed, 19 Aug 2026 11:45:58 UTC (107 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。