Bolztmann optimisation as simulating device

“The problem of drawing samples from a discrete distribution can be converted into a discrete optimization problem” Maddison et al., 2014

I recently learned about the Gumbel-Max “trick” proposed by Chris Maddison, Daniel Tarlow, and Tom Minka in a 2014 NIPS talk. Namely that, to generate from a Boltzmann distribution

p_j=\frac{\exp\{g_j\}}{\sum_i \exp\{g_i\}}

is equivalent to adding standard Gumbel noise to the energies and taking the maximum. A rare (?) instance, compared with the reverse of using simulation to reach maxima. Of course, this requires as many simulations as there as terms in the sum. Or a clever way to avoid this exhaustive listing.

“According to Gumbel’s statistics, 326 out of 354 political murders by right-wing factions in the early Weimar Republic went unpunished, and four out of the 22 left-wing capital crimes.” Science News

As an historical aside I discovered Gumbel’s anti-Nazi activism while in Germany in the 1920’s and early 1930’s (until expelled from the University of Heidelberg). Including the 1932 call against Nazis (which Albert Einstein and Heinrich Mann also signed), hence the above poster.

5 Responses to “Bolztmann optimisation as simulating device”

  1. Pierre Jacob Says:

    Thanks for this I’ve written something related here https://statisfaction.wordpress.com/2020/06/23/categorical-distribution-structure-of-the-second-kind-and-gumbel-max-trick/ on a connection that occurred to me while reading this post.

  2. […] connection occurred to me while reading Xi’an’s blog post, which points to this interesting article on Emil Gumbel, academic in Heidelberg up to his exile in […]

  3. The paper by Chris Maddison et al. 2014 introduced A*-sampling. It relies on the Gumbel-max trick to sample continuous distributions but this trick is not a contribution of this (excellent) paper. The trick itself is fairly old and widely used in the discrete choice models literature since the 70’s.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.