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
|
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.
|
Authors who are presenting talks have a * after their name.