Scalable Discrete Sampling as a Multi-Armed Bandit Problem

• Activity Number: 673
• Type: Invited
• Date/Time: Thursday, August 4, 2016 : 10:30 AM to 12:20 PM
• Sponsor: Section on Bayesian Statistical Science
• Author(s): Yutian Chen* and Zoubin Ghahramani
• Companies: Google DeepMind and University of Cambridge
• Keywords: Approximate Monte Carlo ; Discrete Sampling ; Multi-Armed Bandits ; Subsampling ; Large scale MCMC

Abstract

Drawing a sample from a discrete distribution is one of the building components for Monte Carlo methods. Like other sampling algorithms, discrete sampling suffers from the high computational burden in large-scale inference problems. We study the problem of sampling a discrete random variable with a high degree of dependency that is typical in large-scale Bayesian inference and graphical models, and propose an efficient approximate solution with a subsampling approach. We make a novel connection between the discrete sampling and Multi-Armed Bandits problems with a finite reward population and provide three algorithms with theoretical guarantees. Empirical evaluations show the robustness and efficiency of the approximate algorithms in both synthetic and real-world large-scale problems.