Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.07776 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909622742286336 |
|---|---|
| author | Chak, Martin |
| author_facet | Chak, Martin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_07776 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On theoretical guarantees and a blessing of dimensionality for nonconvex sampling Chak, Martin Computation Probability 60J05, 65C05, 62F15 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. |
| title | On theoretical guarantees and a blessing of dimensionality for nonconvex sampling |
| topic | Computation Probability 60J05, 65C05, 62F15 |
| url | https://arxiv.org/abs/2411.07776 |