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
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.
June 23, 2020 at 11:06 am
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.
June 25, 2020 at 2:06 pm
Je n’avais pas vu le blog de Francis Bach sur le sujet. Ni le blog tout court!
June 23, 2020 at 11:03 am
[…] 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 […]
June 18, 2020 at 1:48 pm
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.
June 18, 2020 at 2:58 pm
Showing my ignorance in the matter then!!!