2024/05/27 by He, Ye, Mousavi-Hosseini, Alireza, Balasubramanian, Krishnakumar +1 · 2 citations
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.2405.16736
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/ε)) versus Ω(poly(1/ε)) iterations to output a sample which is ε-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.