Online Program Home
My Program

Abstract Details

Activity Number: 673
Type: Invited
Date/Time: Thursday, August 4, 2016 : 10:30 AM to 12:20 PM
Sponsor: Section on Bayesian Statistical Science
Abstract #317990 View Presentation
Title: Scalable Discrete Sampling as a Multi-Armed Bandit Problem
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

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.

Authors who are presenting talks have a * after their name.

Back to the full JSM 2016 program

Copyright © American Statistical Association