A* Sampling

By Chris J. Maddison, Daniel Tarlow, Tom Minka. 2014

445 citations recorded by the source corpus.

The problem of drawing samples from a discrete distribution can be converted into a discrete optimization problem [1, 2, 3, 4]. In this work, we show how sampling from a continuous distribution can be converted into an optimization problem over continuous space. Central to the method is a stochastic process recently described in mathematical statistics that we call the Gumbel process. We present a new construction of the Gumbel process and A* Sampling, a practical generic sampling algorithm that searches for the maximum of a Gumbel process using A* search. We analyze the correctness and convergence time of A* Sampling and demonstrate empirically that it makes more efficient use of bound and likelihood evaluations than the most closely related adaptive rejection sampling-based algorithms.

Subfields: Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Probabilistic & Bayesian Methods

Citations in the corpus

Predictive Sampling with Forecasting Autoregressive Models (2020, methodology): “(13) In the case of the Gumbel-Max reparametrization, the posterior Gumbel noise p ( (cid:15) | x ) can be computed straightfor-wardly by using the notion that the maximum and the location of the maximum are independent (Maddison et al., 2014; Kool et al., 2019).”
wav2vec 2.0: A Framework for Self-Supervised Learning of Speech Representations (2020, methodology): “The Gumbel softmax enables choosing discrete codebook entries in a fully differentiable way [16, 24, 35].”
vq-wav2vec: Self-Supervised Learning of Discrete Speech Representations (2019, methodology): “The Gumbel-Softmax (Gumbel, 1954; Jang et al., 2016; Maddison et al., 2014) enables selecting discrete codebook variables in a fully differentiable way and we use the straight-through estimator of Jang et al. (2016).”
Categorical Reparameterization with Gumbel-Softmax (2016, methodology): “The Gumbel-Max trick (Gumbel, 1954; Maddison et al., 2014) provides a simple and efﬁcient way to draw samples z from a categorical distribution with class probabilities π : where g 1 ...g k are i.i.d samples drawn from Gumbel (0 , 1) 1 .”
The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables (2016, methodology): “To motivate the construction of Concrete random variables, we review a method for sampling from discrete distributions called the Gumbel-Max trick (Luce, 1959; Yellott, 1977; Papandreou & Yuille, 2011; Hazan & Jaakkola, 2012; Maddison et al., 2014).”
Adversarial Filters of Dataset Biases (2020, methodology): “The slice sampling approach can be efﬁciently implemented using what is known as the Gumbel method or Gumbel trick (Gumbel & Lieblein, 1954; Maddison et al., 2014), which uses random perturbations to turn sampling into a simpler problem of optimization.”
Searching for a Robust Neural Architecture in Four GPU Hours (2019, methodology): “3) needs to sample from a discrete probability distribution, we cannot back-propagate gradients through A i;j in Eq. (4) to optimize A i;j. To allow back-propagation, we ﬁrst use the Gumbel-Max trick [11, 27] to re-formulate Eq. (3) as Eq. (5), which provides an efﬁcient way to draw samples from a d”
Learning latent representations across multiple data domains using Lifelong VAEGAN (2020, methodology): “In order to mitigate this, we use the Gumbel-Max trick [23, 41] for achieving the differentiable relaxation of discrete random variables.”
Scalable Recollections for Continual Lifelong Learning (2017, methodology): “variables, we follow the success of recent work (Jang et al., 2017;Maddison et al.,2017) and employ the GumbelSoftmax function. The Gumbel-Softmax function leverages the Gumbel-Max trick (Gumbel,1954;Maddison et al., 2014) which provides an efﬁcient way to draw samples z from a categorical distribut”
Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement (2019, methodology): “For details, see Maddison et al. (2014).”
Argmax Flows and Multinomial Diffusion: Towards Non-Autoregressive Language Models (2021, unknown): “For a more extensive introduction see (Maddison et al., 2014; Kool et al., 2019).”
AdversarialNAS: Adversarial Neural Architecture Search for GANs (2019, methodology): “pled from the candidate set according to the learnable architecture controller. Inspired by Gradient-based NAS algorithm [29], we relax the function f n;i;j to a soft version through Gumbel-Max trick [30]: fsoft n;i;j (x) = X f2F G exp((pf n;i;j +o f)=˝) P 02F exp((p f0 n;i;j +of 0)=˝) f(x); (1) whe”
Differentiable Sampling with Flexible Reference Word Order for Neural Machine Translation (2019, methodology): “The Gumbel-Softmax is derived from the Gumbel-Max trick (Maddison et al., 2014), an algorithm for sampling one-hot vector z ∈ Rk from a categorical distribution (p1, .”
Completely Unsupervised Phoneme Recognition by Adversarially Learning Mapping Relationships from Audio Embeddings (2018, unknown): “In gumbel-softmax, the inverse temperature was set to 0.9 without annealing [36].”
Classical Planning in Deep Latent Space: Bridging the Subsymbolic-Symbolic Boundary (2017, methodology): “It continuously approximates Gumbel-Max [Maddison et al., 2014], a method”
KDGAN: Knowledge Distillation with Generative Adversarial Networks (2018, methodology): “We propose to relax the discrete distributions learned by the classifier and the teacher into concrete distributions [25, 31] with the Gumbel-Max trick [20, 30].”
Argmax Flows and Multinomial Diffusion: Learning Categorical Distributions (2021, unknown): “For a more extensive treatment see (Maddison et al., 2014; Kool et al., 2019).”