A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910460202188800 |
|---|---|
| author | He, Ye Mousavi-Hosseini, Alireza Balasubramanian, Krishnakumar Erdogdu, Murat A. |
| author_facet | He, Ye Mousavi-Hosseini, Alireza Balasubramanian, Krishnakumar Erdogdu, Murat A. |
| contents | We study the complexity of heavy-tailed sampling and present a separation result in terms of obtaining high-accuracy versus low-accuracy guarantees i.e., samplers that require only $O(\log(1/\varepsilon))$ versus $Ω(\text{poly}(1/\varepsilon))$ iterations to output a sample which is $\varepsilon$-close to the target in $χ^2$-divergence. Our results are presented for proximal samplers that are based on Gaussian versus stable oracles. We show that proximal samplers based on the Gaussian oracle have a fundamental barrier in that they necessarily achieve only low-accuracy guarantees when sampling from a class of heavy-tailed targets. In contrast, proximal samplers based on the stable oracle exhibit high-accuracy guarantees, thereby overcoming the aforementioned limitation. We also prove lower bounds for samplers under the stable oracle and show that our upper bounds cannot be fundamentally improved. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_16736 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers He, Ye Mousavi-Hosseini, Alireza Balasubramanian, Krishnakumar Erdogdu, Murat A. Statistics Theory Machine Learning We study the complexity of heavy-tailed sampling and present a separation result in terms of obtaining high-accuracy versus low-accuracy guarantees i.e., samplers that require only $O(\log(1/\varepsilon))$ versus $Ω(\text{poly}(1/\varepsilon))$ iterations to output a sample which is $\varepsilon$-close to the target in $χ^2$-divergence. Our results are presented for proximal samplers that are based on Gaussian versus stable oracles. We show that proximal samplers based on the Gaussian oracle have a fundamental barrier in that they necessarily achieve only low-accuracy guarantees when sampling from a class of heavy-tailed targets. In contrast, proximal samplers based on the stable oracle exhibit high-accuracy guarantees, thereby overcoming the aforementioned limitation. We also prove lower bounds for samplers under the stable oracle and show that our upper bounds cannot be fundamentally improved. |
| title | A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers |
| topic | Statistics Theory Machine Learning |
| url | https://arxiv.org/abs/2405.16736 |