Title: Design of informed local proposals for MCMC in discrete spaces
Authors: Giacomo Zanella - Bocconi University (Italy) [presenting]
Abstract: There is a lack of methodological results to guide practitioners in designing efficient Markov chain Monte Carlo (MCMC) algorithms in discrete spaces. For example, it is still unclear how to extend gradient-based MCMC (e.g. Langevin and Hamiltonian schemes) to networks or partitions spaces. This is particularly relevant when fitting Bayesian nonparametric models, which often involve combinatorial and discrete latent structures. Motivated by this observation, we consider the problem of designing appropriate informed MCMC proposal distributions in discrete spaces. In particular: assuming perfect knowledge of the target measure, what is the optimal Metropolis-Hastings proposal given a fixed set of allowed local moves? Under regularity assumptions on the target, we derive the class of asymptotically optimal proposal distributions, which we call locally-balanced Proposals. Such proposals are maximal elements, in terms of Peskun ordering, among proposals obtained as pointwise transformations of the target density. This class of proposals includes Langevin MCMC as a special case and can be seen as a generalization of gradient-based methods to discrete frameworks. We discuss asymptotic analysis, applications to discrete frameworks and connections to other schemes (e.g Multiple-Try).