  Training models with discrete latent variables is challenging due to the high
variance of unbiased gradient estimators. While low-variance reparameterization
gradients of a continuous relaxation can provide an effective solution, a
continuous relaxation is not always available or tractable. Dong et al. (2020)
and Yin et al. (2020) introduced a performant estimator that does not rely on
continuous relaxations; however, it is limited to binary random variables. We
introduce a novel derivation of their estimator based on importance sampling
and statistical couplings, which we extend to the categorical setting.
Motivated by the construction of a stick-breaking coupling, we introduce
gradient estimators based on reparameterizing categorical variables as
sequences of binary variables and Rao-Blackwellization. In systematic
experiments, we show that our proposed categorical gradient estimators provide
state-of-the-art performance, whereas even with additional
Rao-Blackwellization, previous estimators (Yin et al., 2019) underperform a
simpler REINFORCE with a leave-one-out-baseline estimator (Kool et al., 2019).
