Optimal Particle-based Approximation of Discrete Distributions (OPAD)
This provides a theoretical and practical improvement for particle-based methods in statistics and machine learning, though it is incremental as it builds on existing techniques.
The paper proves that for any particle set approximating a discrete distribution, there is a unique optimal weighting that minimizes KL divergence, and shows this reweighting improves performance of existing particle-based methods at no extra cost. Empirical results on Bayesian Variable Selection and Bayesian Structure Learning demonstrate consistent and often substantial gains.
Particle-based methods include a variety of techniques, such as Markov Chain Monte Carlo (MCMC) and Sequential Monte Carlo (SMC), for approximating a probabilistic target distribution with a set of weighted particles. In this paper, we prove that for any set of particles, there is a unique weighting mechanism that minimizes the Kullback-Leibler (KL) divergence of the (particle-based) approximation from the target distribution, when that distribution is discrete -- any other weighting mechanism (e.g. MCMC weighting that is based on particles' repetitions in the Markov chain) is sub-optimal with respect to this divergence measure. Our proof does not require any restrictions either on the target distribution, or the process by which the particles are generated, other than the discreteness of the target. We show that the optimal weights can be determined based on values that any existing particle-based method already computes; As such, with minimal modifications and no extra computational costs, the performance of any particle-based method can be improved. Our empirical evaluations are carried out on important applications of discrete distributions including Bayesian Variable Selection and Bayesian Structure Learning. The results illustrate that our proposed reweighting of the particles improves any particle-based approximation to the target distribution consistently and often substantially.