CUED Publications database

Lost Relatives of the Gumbel Trick

Balog, M and Tripuraneni, N and Ghahramani, Z and Weller, A Lost Relatives of the Gumbel Trick. In: ICML 2017, 2017-8-6 to 2017-8-11, International Conference Centre, Sydney, Australia. (Unpublished)

Full text not available from this repository.


The Gumbel trick is a method to sample from a discrete probability distribution, or to estimate its normalizing partition function. The method re- lies on repeatedly applying a random perturbation to the distribution in a particular way, each time solving for the most likely configuration. We derive an entire family of related methods, of which the Gumbel trick is one member, and show that the new methods have superior properties in several settings with minimal additional computational cost. In particular, for the Gumbel trick to yield computational benefits for discrete graphical models, Gumbel perturbations on all configurations are typically replaced with so- called low-rank perturbations. We show how a subfamily of our new methods adapts to this set- ting, proving new upper and lower bounds on the log partition function and deriving a family of sequential samplers for the Gibbs distribution. Finally, we balance the discussion by showing how the simpler analytical form of the Gumbel trick enables additional theoretical results.

Item Type: Conference or Workshop Item (UNSPECIFIED)
Divisions: Div F > Computational and Biological Learning
Depositing User: Cron Job
Date Deposited: 17 Jul 2017 19:54
Last Modified: 01 Jul 2021 08:55