Review for NeurIPS paper: Asymptotically Optimal Exact Minibatch Metropolis-Hastings

Summary and Contributions: This paper is a study of "minibatch MH" algorithms: variants of Metropolis-Hastings that consider only a subset of factors of a probabilistic model's target density when deciding whether to accept or reject a proposal. It divides these methods into two categories: inexact methods, which are not guaranteed to converge to the correct distribution, and exact methods, which do target the correct distribution but may require more iterations to converge. The paper is concerned only with stateless methods, in which only the current parameter theta is considered when making a proposal and deciding to accept or reject – no additional algorithm-specific state is tracked. The authors make several contributions: • The authors prove theorems about the worst-case behavior of inexact algorithms and existing exact algorithms, by constructing adversarial target distributions and proposals on which these algorithms perform poorly (large bias in inexact algorithms, and slow convergence or large minibatches for some existing exact algorithms). The method is similar to PoissonMH.