Optimal Particle-based Approximation of Discrete Distributions (OPAD)

• URL: http://arxiv.org/abs/2412.00545v1
• Date: Sat, 30 Nov 2024 17:36:59 GMT
• Title: Optimal Particle-based Approximation of Discrete Distributions (OPAD)
• Authors: Hadi Mohasel Afshar, Gilad Francis, Sally Cripps,
• Abstract summary: We show 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. We show that the optimal weights can be determined based on values that any existing particle-based method already computes.
• Score: 7.127829790714167
• License:
• Abstract: 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.

Related papers

• NETS: A Non-Equilibrium Transport Sampler [15.58993313831079]
  We propose an algorithm, termed the Non-Equilibrium Transport Sampler (NETS) NETS can be viewed as a variant of importance sampling (AIS) based on Jarzynski's equality. We show that this drift is the minimizer of a variety of objective functions, which can all be estimated in an unbiased fashion.
  arXiv  Detail & Related papers  (2024-10-03T17:35:38Z)
• Electrostatics-based particle sampling and approximate inference [0.0]
  A new particle-based sampling and approximate inference method, based on electrostatics and Newton mechanics principles, is introduced. A discrete-time, discrete-space algorithmic design is provided for usage in more general inference problems.
  arXiv  Detail & Related papers  (2024-06-28T16:53:06Z)
• Understanding Diffusion Models by Feynman's Path Integral [2.4373900721120285]
  We introduce a novel formulation of diffusion models using Feynman's integral path. We find this formulation providing comprehensive descriptions of score-based generative models. We also demonstrate the derivation of backward differential equations and loss functions.
  arXiv  Detail & Related papers  (2024-03-17T16:24:29Z)
• Variance Reduction of Resampling for Sequential Monte Carlo [0.0]
  A resampling scheme provides a way to switch low-weight particles for sequential Monte Carlo with higher-weight particles representing the objective distribution. We propose a repetitive deterministic domain with median ergodicity for resampling and have achieved the lowest variances compared to the other resampling methods.
  arXiv  Detail & Related papers  (2023-09-10T17:25:43Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• Unsupervised Learning of Sampling Distributions for Particle Filters [80.6716888175925]
  We put forward four methods for learning sampling distributions from observed measurements. Experiments demonstrate that learned sampling distributions exhibit better performance than designed, minimum-degeneracy sampling distributions.
  arXiv  Detail & Related papers  (2023-02-02T15:50:21Z)
• Machine-Learned Exclusion Limits without Binning [0.0]
  We extend the Machine-Learned Likelihoods (MLL) method by including Kernel Density Estimators (KDE) to extract one-dimensional signal and background probability density functions. We apply the method to two cases of interest at the LHC: a search for exotic Higgs bosons, and a $Z'$ boson decaying into lepton pairs.
  arXiv  Detail & Related papers  (2022-11-09T11:04:50Z)
• Sampling with Mollified Interaction Energy Descent [57.00583139477843]
  We present a new optimization-based method for sampling called mollified interaction energy descent (MIED) MIED minimizes a new class of energies on probability measures called mollified interaction energies (MIEs) We show experimentally that for unconstrained sampling problems our algorithm performs on par with existing particle-based algorithms like SVGD.
  arXiv  Detail & Related papers  (2022-10-24T16:54:18Z)
• Targeted Separation and Convergence with Kernel Discrepancies [61.973643031360254]
  kernel-based discrepancy measures are required to (i) separate a target P from other probability measures or (ii) control weak convergence to P. In this article we derive new sufficient and necessary conditions to ensure (i) and (ii) For MMDs on separable metric spaces, we characterize those kernels that separate Bochner embeddable measures and introduce simple conditions for separating all measures with unbounded kernels.
  arXiv  Detail & Related papers  (2022-09-26T16:41:16Z)
• Efficient CDF Approximations for Normalizing Flows [64.60846767084877]
  We build upon the diffeomorphic properties of normalizing flows to estimate the cumulative distribution function (CDF) over a closed region. Our experiments on popular flow architectures and UCI datasets show a marked improvement in sample efficiency as compared to traditional estimators.
  arXiv  Detail & Related papers  (2022-02-23T06:11:49Z)
• A Note on Optimizing Distributions using Kernel Mean Embeddings [94.96262888797257]
  Kernel mean embeddings represent probability measures by their infinite-dimensional mean embeddings in a reproducing kernel Hilbert space. We show that when the kernel is characteristic, distributions with a kernel sum-of-squares density are dense. We provide algorithms to optimize such distributions in the finite-sample setting.
  arXiv  Detail & Related papers  (2021-06-18T08:33:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.