Nesterov smoothing for sampling without smoothness
share
We study the problem of sampling from a target distribution in ℝ^d whose potential is not smooth. Compared with the sampling problem with smooth potentials, this problem is more challenging and much less well-understood due to the lack of smoothness. In this paper, we propose a novel sampling algorithm for a class of non-smooth potentials by first approximating them by smooth potentials using a technique that is akin to Nesterov smoothing. We then utilize sampling algorithms on the smooth potentials to generate approximate samples from the original non-smooth potentials. With a properly chosen smoothing intensity, the accuracy of the algorithm is guaranteed. For strongly log-concave distributions, our algorithm can achieve ℰ error in Wasserstein-2 distance with complexity 𝒪( d^1/3/ℰ^5/3) . For log-concave distributions, we achieve ℰ error in total variation with complexity 𝒪( M_π d /ℰ^3) in expectation with M_π being the second moment of the target distribution. For target distributions satisfying the logarithmic-Sobolev inequality, our algorithm has complexity 𝒪( d /ℰ).
READ FULL TEXT