# Optimal Particle-based Approximation of Discrete Distributions (OPAD)

arXiv: https://arxiv.org/abs/2412.00545 · HTML: https://mlsanity.com/paper/2412.00545/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 18 references that are in the map.
- First posted on arXiv 30 Nov 2024.

## Builds on (most cited first, 7 of 7)

- [DAG-GNN: DAG Structure Learning with Graph Neural Networks](https://mlsanity.com/paper/1904.10098/) (2019)
- [DiBS: Differentiable Bayesian Structure Learning](https://mlsanity.com/paper/2105.11839/) (2021)
- [Parameter Priors for Directed Acyclic Graphical Models and the Characterization of Several Probability Distributions](https://mlsanity.com/paper/1301.6697/) (2013)
- [Partition MCMC for inference on acyclic digraphs](https://mlsanity.com/paper/1504.05006/) (2015)
- [Learning Bayesian Networks: A Unification for Discrete and Gaussian Domains](https://mlsanity.com/paper/1302.4957/) (2013)
- [Bayesian structure learning and sampling of Bayesian networks with the R package BiDAG](https://mlsanity.com/paper/2105.00488/) (2021)
- [The Hamming Ball Sampler](https://mlsanity.com/paper/1504.08133/) (2015)

## Built on by (most cited first, 1 of 1)

- [Rational Clarification by Assistive Agents via Value-of-Information Reasoning](https://mlsanity.com/paper/2609.37588/) (2026)

## Abstract (arXiv)

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.