A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers
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 $\Omega(\text{poly}(1/\varepsilon))$ iterations to output a sample which is $\varepsilon$-close to the target in $\chi^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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Robust Kalman Filters Based on the Sub-Gaussian $α$-stable Distribution
Motivated by filtering tasks under a linear system with non-Gaussian heavy-tailed noise, various robust Kalman filters (RKFs) based on different heavy-tailed distributions have been proposed. Although the sub-Gaussian $\…
Generalized Fast Multichannel Nonnegative Matrix Factorization Based on Gaussian Scale Mixtures for Blind Source Separation
This paper describes heavy-tailed extensions of a state-of-the-art versatile blind source separation method called fast multichannel nonnegative matrix factorization (FastMNMF) from a unified point of view. The common wa…
blind source separationSpeech EnhancementDenoising Lévy Probabilistic Models
Investigating noise distribution beyond Gaussian in diffusion generative models is an open problem. The Gaussian case has seen success experimentally and theoretically, fitting a unified SDE framework for score-based and…
DenoisingNon-Asymptotic Analysis of Fractional Langevin Monte Carlo for Non-Convex Optimization
Recent studies on diffusion-based sampling methods have shown that Langevin Monte Carlo (LMC) algorithms can be beneficial for non-convex optimization, and rigorous theoretical guarantees have been proven for both asympt…
q-exponential family for policy optimization
Policy optimization methods benefit from a simple and tractable policy parametrization, usually the Gaussian for continuous action spaces. In this paper, we consider a broader policy family that remains tractable: the $q…