A Fourier View of REINFORCE
This provides a theoretical framework for variance reduction in gradient estimation for binary latent variable models, which is incremental but offers a new perspective.
The paper connects the Fourier spectrum of Boolean functions to the REINFORCE gradient estimator for binary latent variable models, showing that REINFORCE estimates degree-1 Fourier coefficients, and uses this to develop a low-variance unbiased gradient estimator with a sample-dependent baseline.
We show a connection between the Fourier spectrum of Boolean functions and the REINFORCE gradient estimator for binary latent variable models. We show that REINFORCE estimates (up to a factor) the degree-1 Fourier coefficients of a Boolean function. Using this connection we offer a new perspective on variance reduction in gradient estimation for latent variable models: namely, that variance reduction involves eliminating or reducing Fourier coefficients that do not have degree 1. We then use this connection to develop low-variance unbiased gradient estimators for binary latent variable models such as sigmoid belief networks. The estimator is based upon properties of the noise operator from Boolean Fourier theory and involves a sample-dependent baseline added to the REINFORCE estimator in a way that keeps the estimator unbiased. The baseline can be plugged into existing gradient estimators for further variance reduction.