On theoretical guarantees and a blessing of dimensionality for nonconvex sampling

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\le 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\ge 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.