On theoretical guarantees and a blessing of dimensionality for nonconvex sampling

Existing guarantees for algorithms sampling from nonlogconcave measures on $\mathbb{R}^d$ are generally inexplicit or unscalable. Even for the class of measures with logdensities that have bounded Hessians and are strongly concave outside a Euclidean ball of radius $R$, no available theory is comprehensively satisfactory with respect to both $R$ and $d$. In this paper, it is shown that complete polynomial complexity can in fact be achieved if $R\leq c\sqrt{d}$, whilst an exponential number of point evaluations is 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. On the other hand, if strong concavity outside a ball is replaced by a distant dissipativity condition, then sampling guarantees must generally scale exponentially with $d$ in all parameter regimes.