ARMS: Antithetic-REINFORCE-Multi-Sample Gradient for Binary Variables

Aleksandar Dimitriev, Mingyuan Zhou

TL;DR

ARMS (Antithetic-REINFORCE-Multi-Sample) is a novel gradient estimator for binary variables that significantly reduces noise (variance) by using "antithetic" or negatively correlated samples. It provides a unified framework that generalizes previous state-of-the-art methods and consistently outperforms them in training generative models like Variational Autoencoders (VAEs).

The Challenge of Discrete Variables

In deep learning, we typically rely on calculating gradients to update model parameters. For continuous variables, the "reparameterization trick" (the backbone of VAEs) provides an efficient, low-variance solution. However, this trick fails when dealing with discrete variables (like binary "on/off" switches) because they are inherently non-differentiable.

The standard fallback is the REINFORCE estimator. While REINFORCE is "unbiased" (meaning it converges to the right answer eventually), it suffers from extremely high variance. This means the gradient estimates are very noisy, making training slow and unstable. Previous improvements like DisARM used pairs of negatively correlated samples to cancel out some of this noise, but they struggled to scale well beyond just two samples. The authors of ARMS set out to create an estimator that can use any number of samples ($n$) while maintaining that powerful noise-canceling "antithetic" property.

The ARMS Approach

The core innovation of ARMS is the use of Copulas to generate multiple samples that are all mutually negatively correlated.

  1. Antithetic Sampling: If you have two samples where one is "high" when the other is "low," their average tends to be much more stable than two independent samples. ARMS extends this logic to $n$ samples.
  2. Copula-based Generation: The authors propose two ways to generate these correlated samples:
  3. Dirichlet Copula: Uses a Dirichlet distribution to ensure samples are maximally negatively correlated.
  4. Gaussian Copula: Uses a multivariate normal distribution with a specific correlation matrix to achieve a similar effect.
  5. The Estimator: The authors derive a surprisingly simple formula. They show that the ARMS gradient is essentially the "Leave-One-Out REINFORCE" (LOORF) estimator divided by a debiasing term $(1 - \rho)$, where $\rho$ is the correlation between samples.

This mathematical bridge is elegant: if the samples are independent ($\rho = 0$), ARMS becomes LOORF. If you only use two samples, it perfectly reduces to DisARM.

Key Insights

  • The "Efficiency Gap" Explained: The paper explains why simple independent sampling (LOORF) sometimes beats antithetic pairs (DisARM) as the number of samples increases. LOORF effectively averages $n(n-1)/2$ pairs of samples, while DisARM only uses $n/2$ pairs. ARMS wins because it uses the full $n(n-1)/2$ pairs and makes them negatively correlated.
  • Unified Framework: ARMS isn't just a new tool; it's a generalization. It provides a single mathematical umbrella for LOORF, ARM, and DisARM.
  • Copula Flexibility: While the Dirichlet copula generally showed the lowest variance, the Gaussian copula performed nearly as well and is often easier to implement using standard deep learning libraries.

Experimental Results

The researchers evaluated ARMS by training discrete VAEs on three standard image benchmarks: Dynamic MNIST, Fashion MNIST, and Omniglot. They tested both linear and non-linear (deep) network architectures to ensure robust results.

Gradient variance comparison across different sample sizes.
  • Lower Variance: Across the board, ARMS-D (Dirichlet) and ARMS-N (Gaussian) exhibited significantly lower gradient variance than LOORF, DisARM, and RELAX (a popular but more complex competitor). As the number of samples increases, the variance reduction becomes even more pronounced.
Training ELBO, test log-likelihood, and gradient variance over training steps.
  • Better Performance: In terms of the Evidence Lower Bound (ELBO)—the standard metric for VAE quality—ARMS consistently achieved the best results. For example, on the Fashion MNIST dataset with 10 samples, ARMS achieved a final ELBO of roughly -235.18, outperforming LOORF (-235.59) and DisARM (-235.60).
  • Multi-Sample Bounds: When optimizing the more complex "multi-sample variational bound" (VIMCO), a version of ARMS specifically designed for this task outperformed both the original VIMCO and DisARM.

Limitations and Future Work

  • Binary Only: As the title suggests, this paper focuses on binary variables. Extending ARMS to categorical variables (choosing one of $K$ options) is a promising but currently unexplored direction.
  • Copula Selection: While the proposed copulas work well, there might be even better ways to generate $n$ jointly antithetic samples that aren't strictly based on copulas.
  • Computational Overhead: Generating correlated samples via copulas adds a small amount of computational complexity compared to independent sampling. However, the authors argue this is negligible compared to the cost of evaluating the model's objective function.

Summary updated

Abstract

Estimating the gradients for binary variables is a task that arises frequently in various domains, such as training discrete latent variable models. What has been commonly used is a REINFORCE based...
BibTeX
@inproceedings{dimitriev2021arms,
  author = {Aleksandar Dimitriev and Mingyuan Zhou},
  title = {{ARMS: Antithetic-REINFORCE-Multi-Sample Gradient for Binary Variables}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=GQJz5-Dd4d},
}
Figure