Cold Rao-Blackwellized Straight-Through Gumbel-Softmax Gradient Estimator

Alexander ShekhovtsovICLR 2023 · OpenReview

TL;DR

This paper introduces ZGR, a novel gradient estimator for discrete random variables that overcomes the limitations of existing methods by leveraging a zero-temperature limit of the Gumbel-Rao estimator. ZGR is computationally efficient, unbiased for quadratic loss functions, and demonstrates strong performance in VAEs and quantized neural networks, offering a compelling alternative to current state-of-the-art techniques.

What Problem Does This Paper Address?

Estimating gradients of expectations involving discrete random variables is crucial for many machine learning tasks, including learning with discrete latent representations and training neural networks with quantized weights or activations. While methods like the Gumbel-Softmax family (e.g., Gumbel-Rao) have been developed to tackle this, they often suffer from high variance or require careful tuning of a temperature hyperparameter. The Gumbel-Rao estimator, in particular, shows promise at low temperatures but its behavior at zero temperature, where the relaxation becomes discrete, was not well understood. This paper addresses the challenge of finding a stable, efficient, and unbiased gradient estimator in this "cold" limit.

Methods

The core contribution is the development of the ZGR (Zero-temperature Gumbel-Rao) estimator. The authors analyze the Gumbel-Rao estimator in the limit of zero temperature and discover that the internal Monte Carlo integration simplifies to a closed-form solution. This leads to ZGR, which is presented as:

  • A zero-temperature limit: It's derived from Gumbel-Rao but is free from the temperature hyperparameter.
  • A decomposition: ZGR can be expressed as the average of two simpler estimators: the Straight-Through (ST) estimator and the DARN estimator. This decomposition is key to understanding its properties.
  • Unbiasedness for quadratic functions: A significant theoretical result is that ZGR is unbiased for quadratic loss functions, a property that extends the benefits of binary DARN estimators to the general categorical case.
  • Computational efficiency: ZGR is designed to be computationally inexpensive, avoiding the need for multiple samples or complex operations.

Datasets

The paper uses standard datasets for evaluation:

  • MNIST: Used for both Variational Autoencoder (VAE) and quantized neural network experiments. A binarized version (MNIST-B) is also used.
  • Omniglot: Used for VAE experiments, specifically a down-sampled version (Omniglot-28-D) with dynamic binarization.
  • FashionMNIST: Used for quantized neural network experiments.

No new benchmarks are introduced; the experiments are designed to compare ZGR against existing methods on established tasks.

Key Insights and Ideas

  • The "cold limit" is valuable: By analyzing the Gumbel-Rao estimator at zero temperature, the authors unlock a new, stable, and unbiased estimator (ZGR) that avoids the pitfalls of low-temperature approximations.
  • Decomposition reveals power: Expressing ZGR as the average of ST and DARN highlights how combining seemingly suboptimal estimators can yield a superior result, particularly in its unbiasedness for quadratic functions.
  • Unbiasedness for quadratics is a strong property: This theoretical guarantee suggests ZGR will perform well in scenarios where loss functions can be reasonably approximated by quadratic forms, offering more accurate gradient estimates than ST for interacting discrete variables.
  • Practical efficiency matters: ZGR's computational simplicity and lack of hyperparameters make it a highly attractive alternative for real-world applications where training time and tuning are critical.

Key Results

  • VAE Experiments: ZGR demonstrates competitive or superior performance compared to other gradient estimators in VAE training, often achieving lower mean squared error (MSE) and comparable variance to state-of-the-art unbiased estimators like RF(M) and GR-MC, while being significantly faster. In Figure 1, ZGR shows a favorable bias-variance trade-off, with limiting bias lower than other Gumbel-Rao variants and moderate limiting variance.
  • Quantized Neural Networks: ZGR performs comparably to biased estimators like ST and GS-ST, and can replace low-temperature GR-MC variants. While unbiased estimators are out of competition in this setting, ZGR offers a good balance of performance and efficiency.
  • Computational Cost: ZGR is shown to be significantly faster than GR-MC and competitive with other efficient methods, making it practical for deep models.
  • Theoretical Guarantees: ZGR is proven to be unbiased for quadratic loss functions, a significant improvement over ST which is only unbiased for multilinear functions.

Limitations and Future Work

  • Bias-variance trade-off in learning: The paper notes that while MSE is a useful metric for gradient estimation accuracy, the bias-variance trade-off in actual learning can be complex. Momentum in optimizers can reduce variance, but bias can accumulate.
  • Warm-up for GS-ST: The authors suggest that a warm-up period with GS-ST at higher temperatures might be beneficial for certain scenarios, indicating potential for further hyperparameter optimization.
  • Broader applicability: The authors hypothesize that ZGR's unbiasedness for quadratic functions makes it suitable for learning formulations that can be approximated by quadratics, such as Bayesian learning or multi-sample objectives, suggesting future research directions.
  • Comparison to other unbiased estimators: While ZGR is compared to RF(M) and GR-MC, the paper mentions that other recent unbiased methods appear to offer only marginal improvements over RF(M) with similar sample complexity, leaving room for direct comparisons in future work.

Summary updated

Abstract

The problem of estimating the gradient of an expectation in discrete random variables arises in many applications: learning with discrete latent representations, training neural networks with quantized weights, activations, conditional blocks, etc. This work contributes to the development of the popular Gumbel-Softmax family of estimator, which is based on approximating argmax with a temperature-parametrized softmax. The state-of-the art in this family, the Gumbel-Rao estimator uses internal MC samples to reduce the variance. We show that in the limit of zero temperature the internal integration has a closed form solution. The limit estimator, called ZGR, has a favorable bias and variance, is simple to implement and computationally inexpensive and is obviously free of the temperature hyperparameter. Furthermore, ZGR is unbiased for the class of quadratic functions of categorical variables and can be decomposed into a sum of two simple but not very well performing on their own estimators: the straight through estimator and the DARN estimator. Experiments thoroughly validate the method.
BibTeX
@inproceedings{shekhovtsov2023cold,
  author = {Alexander Shekhovtsov},
  title = {{Cold Rao-Blackwellized Straight-Through Gumbel-Softmax Gradient Estimator}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=EN8YE5dkOO},
}
Figure