Source-linked AI summary
Reparameterization Gradients through Acceptance-Rejection Sampling Algorithms
Christian A. Naesseth, Francisco J. R. Ruiz, Scott W. Linderman, David M. Blei
TL;DR
Gamma and Dirichlet variational factors can be difficult to reparameterize because rejection sampling introduces discontinuities. The paper develops RSVI to derive gradients through existing rejection samplers; on two deep exponential-family datasets, it reports reduced gradient variance and faster ELBO convergence.
Problem
Method
Results
On two deep exponential-family datasets, RSVI achieves a significant reduction in variance and faster convergence of the ELBO.
Source: §1 · p. 2Takeaways & Limitations
RSVI broadens the class of variational distributions with reparameterization gradients by leveraging efficient transformations developed in rejection-sampling research.
Source: §7 · p. 8More complicated accept-reject-like algorithms, including adaptive rejection sampling, importance sampling, sequential Monte Carlo, and MCMC, are left for future work.
Source: §7 · p. 8
Abstract
from arXiv · showhide
Variational inference using the reparameterization trick has enabled large-scale approximate Bayesian inference in complex probabilistic models, leveraging stochastic optimization to sidestep intractable expectations. The reparameterization trick is applicable when we can simulate a random variable by applying a differentiable deterministic function on an auxiliary random variable whose distribution is fixed. For many distributions of interest (such as the gamma or Dirichlet), simulation of random variables relies on acceptance-rejection sampling. The discontinuity introduced by the accept-reject step means that standard reparameterization tricks are not applicable. We propose a new method that lets us leverage reparameterization gradients even when variables are outputs of a acceptance-rejection sampling algorithm. Our approach enables reparameterization on a larger class of variational distributions. In several studies of real and synthetic data, we show that the variance of the estimator of the gradient is significantly lower than other state-of-the-art methods. This leads to faster convergence of stochastic gradient variational inference.
1 Introduction
The paper extends reparameterization gradients to variational distributions simulated by rejection sampling. On two deep exponential-family datasets, RSVI reduces gradient variance and speeds ELBO convergence.
1 Introduction
- Reparameterization often yields lower-variance gradient estimates than the score-function estimator, but has typically been limited to Gaussian variational families.Prior work had begun addressing this scope limitation.Source: §1 · p. 1
- Reparameterization requires a differentiable transformation of a simple random variable; the paper treats rejection-sampler transformations as a route to expand its scope.The auxiliary random variable has a fixed distribution.Source: §1 · p. 1
- RSVI uses existing rejection samplers to derive stochastic gradients for variational parameters, broadening the distributions amenable to efficient inference.The approach exposes the samplers’ transformations to construct reparameterization gradients.Source: §1 · pp. 1–2
- On two deep exponential-family datasets, RSVI achieves a significant reduction in gradient variance and faster ELBO convergence.The paper compares RSVI with the state of the art and studies gamma and Dirichlet variational factors.Source: §1 · p. 2
2 Variational Inference
Variational inference approximates an intractable posterior with a parameterized distribution and optimizes its ELBO. The section reviews score-function and reparameterization gradients, including why rejection sampling complicates the latter.
2 Variational Inference
- Variational inference approximates the posterior with a parameterized family and optimizes its parameters by maximizing the ELBO.When conjugacy requirements hold, coordinate ascent can find a local ELBO optimum; otherwise, Monte Carlo gradient estimates support stochastic optimization.Source: §2 · p. 2
- The score-function estimator expresses the ELBO gradient as an expectation under the variational distribution, but typically has high variance and needs variance-reduction techniques.The cited techniques include Rao–Blackwellization and control variates.Source: §2 · p. 2
- Reparameterization can lower estimator variance, but requires continuous latent variables and simulation through a differentiable transformation of parameter-independent noise.The auxiliary distribution is typically standard normal or standard uniform.Source: §2 · p. 2
- For simplicity, the paper assumes the entropy gradient is available analytically, though it says the method can extend to non-analytical entropy terms.The authors do not explore that extension.Source: §2 · p. 2
- Gamma and Dirichlet samples often come from rejection samplers, whose discontinuous mappings obstruct standard reparameterization.With a differentiable transformation h of fixed-noise ε, the gradient can be written as an expectation involving ∇_z f(h(ε, θ)) and ∇_θ h(ε, θ), plus the entropy gradient.Source: §2 · pp. 2–3
3 Reparameterizing the Acceptance-Rejection Sampler
The paper reparameterizes rejection sampling by focusing on the accepted proposal sample, integrating out the accept-reject variable to obtain gradients. It uses this construction to build an unbiased ELBO gradient estimator and a stochastic variational inference algorithm.
3 Reparameterizing the Acceptance-Rejection Sampler
- Marginalizing the accept-reject variable yields a continuous mapping under mild assumptions, enabling reparameterization for variational families whose samples come from rejection samplers.The method uses the distribution of the accepted proposal sample rather than differentiating through the discontinuous accept-reject step.Source: §3 · p. 3
3.1 Reparameterized Rejection Sampling
- A reparameterizable proposal generates z as h(ε, θ) from parameter-independent ε, then accepts or rejects the proposed sample.For Gamma(θ, 1) with θ = 2, the illustrated Marsaglia–Tsang sampler has acceptance probability 0.98.Source: §3.1 · p. 3, Figure 1 · p. 4
3.2 The Reparameterized Rejection Sampler in Variational Inference
- The ELBO expectation can be expressed over accepted samples ε, producing a gradient with reparameterization, proposal-correction, and entropy terms.The paper defines g_rep as the model-and-latent-variable gradient term and g_cor as the correction for using a proposal different from q; a one-sample Monte Carlo estimate is unbiased.Source: §3.2 · pp. 3–4
- An importance-sampling alternative uses weights q(h(ε, θ); θ)/r(h(ε, θ); θ), but is expected to benefit only low-dimensional problems because weights may have high variance for high-dimensional z.The authors report that a single accepted ε sample sufficed in their practice for the proposed estimator.Source: §3.2 · pp. 4–5
3.3 Full Algorithm
- RSVI repeatedly samples an accepted ε, estimates the gradient, selects a step size, and updates the variational parameters.The full algorithm uses the step-size sequence proposed by Kucukelbir et al. [2016], which combines RMSprop and Adagrad.Source: §3.2 · p. 5, §3.3 · p. 5
4 Related Work
The paper distinguishes its rejection-sampling approach from prior methods for extending reparameterization and compares it with g-rep. It also describes how the approach can extend to more expressive variational families when those methods use rejection sampling.
4 Related Work
- ADVI cannot fit gamma or Dirichlet variational posteriors, while the cited gamma-specific inverse-CDF approximation is limited to gamma and computationally expensive.The paper also notes that stochastic-computation-graph gradients cannot be directly applied to variational inference with rejection sampling because of discontinuities and random numbers of random variables.Source: §4 · p. 5
- Unlike g-rep’s standardization transformation, rsvi reuses rejection-sampling transformations chosen for high acceptance, and the paper reports lower variance and faster convergence than g-rep.The authors expect high acceptance to make the correction term g_cor approximately zero.Source: §4 · pp. 5–6
- RSVI can extend reparameterization to more expressive variational methods whenever rejection sampling is used to generate their random variables.Source: §4 · p. 6
5 Examples of Acceptance-Rejection Reparameterization
The section applies rejection-sampling reparameterization to gamma and Dirichlet variational distributions, and describes shape augmentation for gamma sampling. In a Dirichlet approximation to a multinomial likelihood, rsvi has lower gradient variance than g-rep.
5 Examples of Acceptance-Rejection Reparameterization
- rsvi applies to variational families with a reparameterizable rejection sampler, beyond the gamma and Dirichlet examples studied here.The paper identifies gamma and Dirichlet as examples, not the method’s limits.Source: §5 · p. 6
5.1 Gamma Distribution
- For Gamma(α, 1) with α ≥ 1, the Marsaglia–Tsang sampler has acceptance probabilities above 0.95 at α = 1 and 0.98 at α = 2.As α increases toward infinity, the proposal distribution approaches the auxiliary standard normal and acceptance approaches 1.Source: §5.1 · p. 6
- As α increases, the gamma sampler’s correction term decreases; its transformed ε distribution approaches a standard normal faster than g-rep’s standardization.The figure plots the absolute gradient of the target-to-proposal log-ratio against ε.Source: §5.1 · p. 6, Figure 2 · p. 6
- Shape augmentation uses uniform variables to raise the gamma shape used by the rejection sampler, exploiting its improved behavior at larger α.The resulting sample can use a Gamma(α + B, 1) variable instead of the original z.Source: §5.1 · p. 6
5.2 Dirichlet Distribution
- rsvi has lower variance than g-rep for the first component of a Dirichlet approximation to a multinomial likelihood, especially with shape augmentation.The comparison uses K = 100 components, a uniform prior, and N = 100 trials.Source: Figure 4 · p. 7, §5.2 · p. 7
- For the Dirichlet case, the method changes variables to independent gamma variables and applies the gamma transformation to each component.The study compares rsvi with g-rep for a Dirichlet approximation to a multinomial likelihood.Source: §5.2 · p. 7
6 Experiments
On Olivetti faces, rsvi improves the ELBO faster initially than the compared methods; on NIPS, it has lower gradient variance than g-rep, with further reductions as augmentation steps increase.
Model and setup
- The evaluations compare rsvi with advi, bbvi, and g-rep on a sparse gamma deep exponential family; model settings include three layers with 100, 40, and 15 components.The experiments set αz = 0.1 and use Gamma(0.1, 0.3) weight priors and Gamma(0.1, 0.1) top-layer local-variable priors.Source: §6 · pp. 7–8
Data
- The experiments use Olivetti grayscale face images and NIPS 2011 conference papers in bag-of-words form with an effective vocabulary of 5715 words.The Olivetti images are 64×64 pixels with 8-bit values.Source: §6 · p. 7
Results
- Rsvi shows significantly faster initial ELBO improvement than advi, bbvi, and g-rep on Olivetti faces.For comparable implementations, rsvi is approximately two times faster than g-rep.Source: §6 · p. 8, Figure 5 · p. 8
- On NIPS, rsvi has lower gradient variance than g-rep, and increasing shape-augmentation steps B further reduces variance.Table 1 reports estimated variance from 10 samples at initialization and at rsvi iteration 2600.Source: §6 · p. 8, Table 1 · p. 8
7 Conclusions
Rsvi derives reparameterization gradients for variational distributions simulated with acceptance-rejection samplers and reports lower-variance gradients than other state-of-the-art methods. The authors identify more complex accept-reject-like simulation algorithms as future directions.
Conclusion
- Rsvi derives reparameterization gradients when variational draws are generated by an acceptance-rejection sampler.The method uses transformations developed in the rejection-sampling literature.Source: §7 · p. 8
- In practice, rsvi leads to lower-variance gradients than other state-of-the-art methods and enables reparameterization for a large class of variational distributions.The approach takes advantage of efficient transformations developed for rejection sampling.Source: §7 · p. 8
Future work
- Adaptive rejection sampling, importance sampling, sequential Monte Carlo, and Markov chain Monte Carlo are proposed as future extensions.The paper frames these as more complicated simulation algorithms with accept-reject-like steps.Source: §7 · p. 8
A.1 Distribution of ε
The appendix characterizes the distribution of the accepted auxiliary variable ε by deriving its cumulative distribution function and differentiating it to obtain its density.
Accepted-variable distribution
- The accepted ε has a cumulative distribution function expressed using the event that ε_i ≤ ε and the rejection test U_i < q(h(ε_i, θ); θ) / [Mθ r(h(ε_i, θ); θ)].The derivation considers the univariate continuous case and states that the result also holds for discrete and multivariate settings.Source: §A.1 · p. 11
- The derivation uses z = h(ε, θ), with ε drawn from s(ε), as a reparameterization of z drawn from r(z; θ).It applies this relationship in expressing the accepted-variable distribution.Source: §A.1 · p. 11
- Differentiating the cumulative distribution function with respect to ε gives the accepted variable's density.The appendix relates the construction to the geometric area-under-the-curve argument for rejection sampling, applied to ε rather than z.Source: §A.1 · p. 11
A.2 Derivation of the Gradient
The gradient derivation assumes an almost-everywhere differentiable transformation and continuity in θ, then uses a log-derivative step to express the gradient.
Gradient derivation
- The derivation assumes h is almost everywhere differentiable with respect to θ and the stated product involving f, q, and r is continuous in θ for every ε.These conditions are given before the gradient derivation.Source: §A.2 · p. 11
- The final derivation step identifies π(ε; θ) and applies the log-derivative trick.The surrounding discussion concerns the gradient of the log-ratio in gcor for invertible reparameterizations.Source: §A.2 · p. 11
- The displayed ratio is q(h(ε, θ); θ) divided by r(h(ε, θ); θ).The expression is stated in terms of the transformed variable h(ε, θ).Source: §A.2 · p. 11
A.3 Examples of Reparameterizable Rejection Samplers
The appendix presents examples of reparameterizable rejection samplers and auxiliary-variable mappings, then gives details of the gamma reparameterization and its gradients.
A.3 Examples of Reparameterizable Rejection Samplers
- Table 2 lists gamma, truncated normal, and von Mises samplers, pairing each distribution with a transformation h(ε, θ) and proposal s(ε).Source: §A.3 · p. 11, Table 2 · p. 12
- Table 3 gives six distributions represented through auxiliary gamma random variables, specifying each target, auxiliary-variable distribution, and mapping g(˜z, θ).Source: §A.3 · p. 11, Table 3 · p. 12
A.4 Reparameterizing the Gamma Distribution
- With rate β=1, which is not restrictive because the rate can be reparameterized, the appendix defines the gamma density and gradients; invertible h enables a simplified log-ratio gradient.Source: §A.4 · p. 12