Sampling from a given target distribution in an efficient manner is a widely studied problem with applications in computer science, operations research, statistics, and many applied subjects. Due to its generality and flexibility, one of the most successful approach to design efficient sampling methods uses the so-called Monte Carlo Markov Chain technique, is the Metropolis-Hastings (MH) algorithm, which, in one venue was named as one of the “top 10” algorithms in computer science. In this talk we will explore how group moves can be added to MH in general state spaces, broadening further the applicability of MH beyond what is available today. The main motivation for adding group moves to MH is because they allow a convenient way to exploit invariances in the target distribution, even if those only concern a subset of the factors, or even if they are only approximate. The main technical difficulty in applying MH in this setting is the computation of the acceptance probability, which we address with tools of topological group theory based on a general result of Luke Tierney. The method is demonstrated in an application to robotics in the so-called simultaneous localization and mapping (SLAM) problem where a robot navigating a 2D environment and equipped with range only sensors has to learn a map of its environment while simultaneously estimating its positions. Our experiments with real-world benchmark data on this problem shows that our general method performs competitively with special-purpose algorithms.

This is joint work with Roshan Shariff and Andras Gyorgy. The talk is based on this paper, that appeared at AISTAT 2015.