GumbelMax

GumbelMax refers to the Gumbel-max trick, a technique used in probability theory and machine learning to sample from a discrete distribution given by a set of log-probabilities or logits. The method works by adding independent Gumbel noise to each log-probability and selecting the index of the largest resulting value.

Formally, given logits l1, l2, ..., lK, one samples g1, g2, ..., gK independently from a standard Gumbel distribution. Then the chosen index is i* = argmax_i (li + gi). This procedure yields a correct sample from the categorical distribution with probabilities proportional to exp(li); specifically, P(i* = i) = exp(li) / sum_j exp(lj). The trick enables sampling without explicitly computing the normalization.

Implementation notes: a standard way to generate a Gumbel sample is gi = -log(-log(Ui)) where Ui are independent Uniform(0,1) samples. The procedure requires generating a Gumbel value for each category, so its cost grows with the number of categories. It is often used in settings where logits are readily available and explicit normalization is undesirable or costly.

Relation to related methods: the Gumbel-Max trick provides exact sampling, while the Gumbel-Softmax (or Concrete distribution) offers a differentiable, continuous relaxation by applying a softmax to li + gi with a temperature parameter. This relaxation enables gradient-based optimization in neural networks.

Applications include discrete sampling in probabilistic models, variational inference, reinforcement learning, and other areas where sampling from a categorical distribution is needed.