  Learning models with discrete latent variables using stochastic gradient
descent remains a challenge due to the high variance of gradient estimates.
Modern variance reduction techniques mostly consider categorical distributions
and have limited applicability when the number of possible outcomes becomes
large. In this work, we consider models with latent permutations and propose
control variates for the Plackett-Luce distribution. In particular, the control
variates allow us to optimize black-box functions over permutations using
stochastic gradient descent. To illustrate the approach, we consider a variety
of causal structure learning tasks for continuous and discrete data. We show
that our method outperforms competitive relaxation-based optimization methods
and is also applicable to non-differentiable score functions.
