Stochastic Particle-Optimization Sampling and the Non-Asymptotic Convergence Theory

Particle-optimization sampling (POS) is a recently developed technique to generate high-quality samples from a target distribution by iteratively updating a set of interactive particles. A representative algorithm is the Stein variational gradient descent (SVGD). Though obtaining significant empirical success, the {\em non-asymptotic} convergence behavior of SVGD remains unknown. In this paper, we generalize POS to a stochasticity setting by injecting random noise in particle updates, called stochastic particle-optimization sampling (SPOS). Standard SVGD can be regarded as a special case of our framework. Notably, for the first time, we develop non-asymptotic convergence theory for the SPOS framework (which includes SVGD), characterizing the bias of a sample approximation w.r.t. the numbers of particles and iterations under both convex- and noncovex-energy-function settings. Remarkably, we provide theoretical understand of a pitfall of SVGD that can be avoided in the proposed SPOS framework, i.e., particles tent to collapse to a local mode in SVGD under some particular conditions. Our theory is based on the analysis of nonlinear stochastic differential equations, which serves as an extension and a complemented development to the asymptotic convergence theory for SVGD such as [1].