Efficient Informed Proposals for Discrete Distributions via Newton's Series Approximation

• URL: http://arxiv.org/abs/2302.13929v1
• Date: Mon, 27 Feb 2023 16:28:23 GMT
• Title: Efficient Informed Proposals for Discrete Distributions via Newton's Series Approximation
• Authors: Yue Xiang, Dongyao Zhu, Bowen Lei, Dongkuan Xu, Ruqi Zhang
• Abstract summary: We develop a gradient-like proposal for any discrete distribution without a strong requirement. Our method efficiently approximates the discrete likelihood ratio via Newton's series expansion. We prove that our method has a guaranteed convergence rate with or without the Metropolis-Hastings step.
• Score: 13.349005662077403
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Gradients have been exploited in proposal distributions to accelerate the convergence of Markov chain Monte Carlo algorithms on discrete distributions. However, these methods require a natural differentiable extension of the target discrete distribution, which often does not exist or does not provide effective gradient guidance. In this paper, we develop a gradient-like proposal for any discrete distribution without this strong requirement. Built upon a locally-balanced proposal, our method efficiently approximates the discrete likelihood ratio via Newton's series expansion to enable a large and efficient exploration in discrete spaces. We show that our method can also be viewed as a multilinear extension, thus inheriting its desired properties. We prove that our method has a guaranteed convergence rate with or without the Metropolis-Hastings step. Furthermore, our method outperforms a number of popular alternatives in several different experiments, including the facility location problem, extractive text summarization, and image retrieval.

Related papers

• A Stein Gradient Descent Approach for Doubly Intractable Distributions [5.63014864822787]
  We propose a novel Monte Carlo Stein variational gradient descent (MC-SVGD) approach for inference for doubly intractable distributions. The proposed method achieves substantial computational gains over existing algorithms, while providing comparable inferential performance for the posterior distributions.
  arXiv  Detail & Related papers  (2024-10-28T13:42:27Z)
• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  Proximal point methods have attracted considerable interest owing to their numerical stability and robustness against imperfect tuning. This paper presents a comprehensive analysis of a broad range of variations of the proximal point method (SPPM)
  arXiv  Detail & Related papers  (2024-05-24T21:09:19Z)
• Uncertainty Quantification via Stable Distribution Propagation [60.065272548502]
  We propose a new approach for propagating stable probability distributions through neural networks. Our method is based on local linearization, which we show to be an optimal approximation in terms of total variation distance for the ReLU non-linearity.
  arXiv  Detail & Related papers  (2024-02-13T09:40:19Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Implicit Variational Inference for High-Dimensional Posteriors [7.924706533725115]
  In variational inference, the benefits of Bayesian models rely on accurately capturing the true posterior distribution. We propose using neural samplers that specify implicit distributions, which are well-suited for approximating complex multimodal and correlated posteriors. Our approach introduces novel bounds for approximate inference using implicit distributions by locally linearising the neural sampler.
  arXiv  Detail & Related papers  (2023-10-10T14:06:56Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  We analyze a Newton algorithm for homogeneous distributed convex optimization, where each machine can calculate gradients of the same population objective. We show that our method can reduce the number, and frequency, of required communication rounds compared to existing methods without hurting performance.
  arXiv  Detail & Related papers  (2021-10-07T17:51:10Z)
• A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms [67.67377846416106]
  We present a distributional approach to theoretical analyses of reinforcement learning algorithms for constant step-sizes. We show that value-based methods such as TD($lambda$) and $Q$-Learning have update rules which are contractive in the space of distributions of functions.
  arXiv  Detail & Related papers  (2020-03-27T05:13:29Z)
• Stein Variational Inference for Discrete Distributions [70.19352762933259]
  We propose a simple yet general framework that transforms discrete distributions to equivalent piecewise continuous distributions. Our method outperforms traditional algorithms such as Gibbs sampling and discontinuous Hamiltonian Monte Carlo. We demonstrate that our method provides a promising tool for learning ensembles of binarized neural network (BNN) In addition, such transform can be straightforwardly employed in gradient-free kernelized Stein discrepancy to perform goodness-of-fit (GOF) test on discrete distributions.
  arXiv  Detail & Related papers  (2020-03-01T22:45:41Z)

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.