A Proximal Algorithm for Sampling from Non-convex Potentials
This addresses a challenging sampling problem in machine learning and statistics, but it is an incremental extension of prior work for non-convex potentials.
The paper tackles the problem of sampling from non-convex and semi-smooth potentials, developing a proximal algorithm based on an alternating sampling framework with rejection sampling. It achieves better complexity than existing methods in most cases considered.
We study sampling problems associated with non-convex potentials that meanwhile lack smoothness. In particular, we consider target distributions that satisfy either logarithmic-Sobolev inequality or Poincaré inequality. Rather than smooth, the potentials are assumed to be semi-smooth or the summation of multiple semi-smooth functions. We develop a sampling algorithm that resembles proximal algorithms in optimization for this challenging sampling task. Our algorithm is based on a special case of Gibbs sampling known as the alternating sampling framework (ASF). The key contribution of this work is a practical realization of the ASF based on rejection sampling in the non-convex and semi-smooth setting. This work extends the recent algorithm in \cite{LiaChe21,LiaChe22} for non-smooth/semi-smooth log-concave distribution to the setting with non-convex potentials. In almost all the cases of sampling considered in this work, our proximal sampling algorithm achieves better complexity than all existing methods.