Efficient Informed Proposals for Discrete Distributions via Newton's Series Approximation
This addresses a bottleneck in discrete-space MCMC for practitioners in fields like optimization and machine learning, offering a novel approach without strong differentiability assumptions.
The paper tackled the problem of designing efficient proposal distributions for Markov chain Monte Carlo on discrete distributions without requiring a differentiable extension, by developing a method based on Newton's series approximation that enables large exploration and outperforms alternatives in experiments like facility location and text summarization.
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.