Low Bias Low Variance Gradient Estimates for Boolean Stochastic Networks

Adeel Pervez, Taco Cohen, Efstratios GavvesICML 2020 · OpenReview

Training neural networks with discrete latent variables (like binary "on/off" switches) has long been a "holy grail" in machine learning. These models are highly interpretable and expressive, but they suffer from a fundamental flaw: you cannot easily differentiate through a discrete jump. This makes the standard workhorse of AI—backpropagation—unusable.

In their ICML 2020 paper, Adeel Pervez and colleagues introduce FouST (Fourier Straight-Through), a gradient estimator that uses the elegant mathematics of harmonic analysis to bridge the gap between efficiency and accuracy in Boolean stochastic networks.

The Challenge of Discrete Variables

To train stochastic neural networks, researchers typically choose between two imperfect options:

  1. Unbiased Estimators (e.g., REINFORCE): These are mathematically "correct" on average but suffer from massive variance. It’s like trying to find the bottom of a valley during a violent earthquake; the signal is there, but it's buried in noise.
  2. Biased Estimators (e.g., Straight-Through, Gumbel-Softmax): These are fast and "smooth," but they are mathematically "wrong." As models get deeper (hierarchical), this bias compounds, often leading the model to converge to poor solutions or fail to train entirely.

The authors identify a specific gap: we lack an estimator that works directly on the Boolean space $\{-1, +1\}$—without messy continuous relaxations—that remains stable even in complex, deep architectures.

Methods: Harmonic Analysis of Boolean Functions

The core innovation is the application of Harmonic Analysis of Boolean Functions. The authors treat the neural network as a function $f(z)$ over a Boolean cube.

  • Quantifying Bias: They prove that the bias in the popular "Straight-Through" (ST) estimator is essentially a weighted sum of higher-order Taylor coefficients.
  • The FouST Algorithm: To fix this, they introduce three key techniques:
  • Importance Sampling: They re-weight the gradients to correct for the "distribution mismatch" between the true gradient and the ST approximation.
  • Fourier Noise Operator ($T_\rho$): This acts as a "low-pass filter." It smooths the Boolean function by averaging over correlated inputs, which suppresses high-frequency noise (the source of variance) without changing the expected value.
  • Representation Rescaling ($\tau$): By scaling the Boolean variables (e.g., to $\pm 1/\tau$), they can mathematically dampen the influence of those problematic higher-order terms that cause bias.

Key Insights

  • The "Aha!" Moment: The authors show that variance in these networks is caused by high-order Fourier coefficients. This means we can use the Fourier Noise Operator to specifically target and reduce variance without destroying the gradient signal.
  • Reinterpreting DARN: They show that the DARN estimator (a previous state-of-the-art method) can actually be viewed as a specific, lower-bias version of Straight-Through under their harmonic framework.
  • Direct Boolean Optimization: Unlike Gumbel-Softmax, which relies on continuous relaxations that can become "mushy" in deep networks, FouST works directly on the Boolean space, maintaining the discrete nature of the latent variables throughout training.

Key Results

The authors validated FouST across several standard benchmarks, including a toy optimization problem, OMNIGLOT, CIFAR-10, MNIST, and mini-ImageNet.

  • Superior Convergence: On the toy problem, FouST converged to the global minimum, while the standard Straight-Through estimator got stuck due to excessive bias.
  • State-of-the-Art Performance: FouST consistently outperformed Gumbel-Softmax and DARN on OMNIGLOT and CIFAR-10.
Training ELBO comparison across estimators
  • Competitive Bits Per Dimension (BPD): On CIFAR-10, FouST achieved a validation score of 4.02 bpd, outperforming VQ-VAE and VIMCO.
CIFAR-10 BPD Results
  • Extreme Efficiency: FouST is significantly faster than unbiased "control variate" methods. On MNIST, the unbiased REBAR method was 15x to 40x slower than FouST for two- and five-layer models, respectively.
  • Scalability: FouST successfully trained models with up to 10 stochastic layers, a depth where most other biased estimators typically fail.

Limitations and Future Work

  • Boolean Specificity: The current framework is built specifically for Boolean ($\{-1, +1\}$) variables. While many problems can be cast as binary, extending this harmonic analysis to general categorical variables (1-of-K) remains a task for future research.
  • Hyperparameter Tuning: The method introduces parameters like $\rho$ (noise level) and $\tau$ (scaling), which require tuning via cross-validation to find the optimal balance between bias and variance for a specific architecture.
  • Complexity of Analysis: While the algorithm is simple to implement, the theoretical framework requires a background in harmonic analysis, which might be a barrier for some practitioners looking to extend the work.

Reference: Pervez, A., Cohen, T., & Gavves, E. (2020). Low Bias Low Variance Gradient Estimates for Boolean Stochastic Networks. Proceedings of the 37th International Conference on Machine Learning (ICML).

Summary updated

Abstract

Stochastic neural networks with discrete random variables are an important class of models for their expressiveness and interpretability. Since direct differentiation and backpropagation is not pos...
BibTeX
@inproceedings{pervez2020low,
  author = {Adeel Pervez and Taco Cohen and Efstratios Gavves},
  title = {{Low Bias Low Variance Gradient Estimates for Boolean Stochastic Networks}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=Y-g9SDkjAHo},
}
Figure