Estimating Gradients for Discrete Random Variables by Sampling without Replacement
arXiv:2002.06043
Abstract
We derive an unbiased estimator for expectations over discrete random variables based on sampling without replacement, which reduces variance as it avoids duplicate samples. We show that our estimator can be derived as the Rao-Blackwellization of three different estimators. Combining our estimator with REINFORCE, we obtain a policy gradient estimator and we reduce its variance using a built-in control variate which is obtained without additional model evaluations. The resulting estimator is closely related to other gradient estimators. Experiments with a toy problem, a categorical Variational Auto-Encoder and a structured prediction problem show that our estimator is the only estimator that is consistently among the best estimators in both high and low entropy settings.
ICLR 2020
References in corpus (18)
- Auto-Encoding Variational Bayes
- Categorical Reparameterization with Gumbel-Softmax
- Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation
- The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables
- Dual Learning for Machine Translation
- Neural Variational Inference and Learning in Belief Networks
- Attention, Learn to Solve Routing Problems!
- Gradient Estimation Using Stochastic Computation Graphs
- REBAR: Low-variance, unbiased gradient estimates for discrete latent variable models
- Variational Bayesian Inference with Stochastic Search
- Deep AutoRegressive Networks
- Memory Augmented Policy Optimization for Program Synthesis and Semantic Parsing
- Sticking the Landing: Simple, Lower-Variance Gradient Estimators for Variational Inference
- Rao-Blackwellized Stochastic Gradients for Discrete Distributions
- ARSM: Augment-REINFORCE-Swap-Merge Estimator for Gradient Backpropagation Through Categorical Variables
- Neural Machine Translation with Gumbel-Greedy Decoding
- Learning Beam Search Policies via Imitation Learning
- Direct Policy Gradients: Direct Optimization of Policies in Discrete Action Spaces
Cited by in corpus (9)
- Gradient Estimation with Stochastic Softmax Tricks
- Efficient Marginalization of Discrete and Structured Latent Variables via Sparsity
- Experimental design for MRI by greedy policy search
- Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions
- Joint Stochastic Approximation and Its Application to Learning Discrete Latent Variable Models
- Learning-to-Rank with Partitioned Preference: Fast Estimation for the Plackett-Luce Model
- Rao-Blackwellizing the Straight-Through Gumbel-Softmax Gradient Estimator
- CARMS: Categorical-Antithetic-REINFORCE Multi-Sample Gradient Estimator
- Conditional Poisson Stochastic Beam Search