2019

Monte Carlo Gradient Estimation in Machine Learning

Mohamed, Shakir, Rosca, Mihaela, Figurnov, Michael et al.

Understand

This paper is a broad and accessible survey of the methods we have at our disposal for Monte Carlo gradient estimation in machine learning and across the statistical sciences: the problem of computing the gradient of an expectation of a function with respect to parameters defining the distribution that is integrated; the problem of sensitivity analysis.

In machine learning research, this gradient problem lies at the core of many learning problems, in supervised, unsupervised and reinforcement learning.
We will generally seek to rewrite such gradients in a form that allows for Monte Carlo estimation, allowing them to be easily and efficiently used and analysed.
We explore three strategies--the pathwise, score function, and measure-valued gradient estimators--exploring their historical development, derivation, and underlying assumptions.

Built on

The Monte Carlo method
N. Metropolis and S. Ulam · 1949
Earlier work this paper cites.
A stochastic approximation method
H. Robbins and S. Monro · 1951
Earlier work this paper cites.
A useful theorem for nonlinear devices having Gaussian inputs
R. Price · 1958
Earlier work this paper cites.
Transformations des signaux aléatoires a travers les systemes non linéaires sans mémoire
G. Bonnet · 1964
Earlier work this paper cites.
Monte Carlo analysis of reactivity coefficients in fast reactors general theory and applications
L. B. Miller · 1967
Earlier work this paper cites.
Some Problems in Monte Carlo Optimization
R. Y. Rubinstein · 1969
Earlier work this paper cites.
Differentiation under the integral sign
H. Flanders · 1973
Earlier work this paper cites.
Computational graphs and rounding error
F. L. Bauer · 1974
Earlier work this paper cites.
Optimization and perturbation analysis of queueing networks
Y. Ho and X. Cao · 1983
Earlier work this paper cites.
About one Monte Carlo method for solving linear equations
R. Y. Rubinstein and J. Kreimer · 1983
Earlier work this paper cites.
Driving frequency selection for frequency domain simulation experiments
S. Jacobson, A. Buss, and L. Schruben · 1986
Earlier work this paper cites.
Monte Carlo Optimization, Simulation and Sensitivity of Queueing Networks
R. Y. Rubinstein · 1986
Earlier work this paper cites.
Likelilood ratio gradient estimation: An overview
P. W. Glynn · 1987
Earlier work this paper cites.
Smoothed (conditional) perturbation analysis of discrete event dynamical systems
W.-B. Gong and Y. C. Ho · 1987
Earlier work this paper cites.
Convergence properties of infinitesimal perturbation analysis estimates
P. Heidelberger, X.-R. Cao, M. A. Zazanis, and R. Suri · 1988
Earlier work this paper cites.
Perturbation analysis gives strongly consistent sensitivity estimates for the M/G/1 queue
R. Suri and M. A. Zazanis · 1988
Earlier work this paper cites.
Importance sampling for stochastic simulations
P. W. Glynn and D. L. Iglehart · 1989
Earlier work this paper cites.
Indirect estimation via l = λ w l=\lambda w
P. W. Glynn and W. Whitt · 1989
Earlier work this paper cites.
On automatic differentiation
A. Griewank et al · 1989
Earlier work this paper cites.
Sampling derivatives of probabilities
G. C. Pflug · 1989
Earlier work this paper cites.
Sensitivity analysis for simulations via likelihood ratios
M. I. Reiman and A. Weiss · 1989
Earlier work this paper cites.
Likelihood ratio gradient estimation for stochastic systems
P. W. Glynn · 1990
Earlier work this paper cites.
Control variate remedies
B. L. Nelson · 1990
Earlier work this paper cites.
Gradient estimation via Perturbation Analysis
P. Glasserman and Y. C. Ho · 1991
Earlier work this paper cites.
Sensitivity analysis of discrete event systems by the “push out” method
R. Y. Rubinstein · 1992
Earlier work this paper cites.
Simple statistical gradient-following algorithms for connectionist reinforcement learning
R. J. Williams · 1992
Earlier work this paper cites.
A splitting scheme for control variates
A. N. Avramidis and J. R. Wilson · 1993
Earlier work this paper cites.
Second derivative sample path estimators for the GI/G/M queue
M. C. Fu and J.-Q. Hu · 1993
Earlier work this paper cites.
Discrete Event Systems: Sensitivity analysis and stochastic optimization by the score function method
R. Y. Rubinstein and A. Shapiro · 1993
Earlier work this paper cites.
Optimization via simulation: A review
M. C. Fu · 1994
Earlier work this paper cites.
Optimal mean squared error analysis of the harmonic gradient estimators
S. H. Jacobson · 1994
Earlier work this paper cites.
Application of RPA and the harmonic gradient estimators to a priority queueing system
F. J. Vázquez-Abad and S. H. Jacobson · 1994
Earlier work this paper cites.
Bayesian experimental design: A review
K. Chaloner and I. Verdinelli · 1995
Earlier work this paper cites.
Likelihood ratio gradient estimation for stochastic recursions
P. W. Glynn and P. L’Ecuyer · 1995
Earlier work this paper cites.
Note: On the interchange of derivative and expectation for likelihood ratio derivative estimators
P. L’Ecuyer · 1995
Earlier work this paper cites.
Black Scholes and Beyond: Option Pricing Models
N. Chriss · 1996
Earlier work this paper cites.
Random variate generation in one line of code
L. Devroye · 1996
Earlier work this paper cites.
Simulation-based Econometric Methods
C. Gouriéroux and A. Monfort · 1996
Earlier work this paper cites.
Optimization and sensitivity analysis of computer simulation models by the score function method
J. P. Kleijnen and R. Y. Rubinstein · 1996
Earlier work this paper cites.
Optimization of Stochastic Models: The Interface between Simulation and Optimization
G. C. Pflug · 1996
Earlier work this paper cites.
The score function method
R. Y. Rubinstein, A. Shapiro, and S. Uryasév · 1996
Earlier work this paper cites.
A variational approach to Bayesian logistic regression models and their extensions
T. Jaakkola and M. Jordan · 1997
Earlier work this paper cites.
Reinforcement Learning: An Introduction
R. S. Sutton and A. Barto · 1998
Earlier work this paper cites.
Applications of Malliavin calculus to Monte Carlo methods in finance
E. Fournié, J.-M. Lasry, J. Lebuchoux, P.-L. Lions, and N. Touzi · 1999
Earlier work this paper cites.
A harmonic analysis approach to simulation sensitivity analysis
S. H. Jacobson and L. Schruben · 1999
Earlier work this paper cites.
An introduction to variational methods for graphical models
M. I. Jordan, Z. Ghahramani, T. S. Jaakkola, and L. K. Saul · 1999
Earlier work this paper cites.
Optimal policies and simulation-based optimization for capacitated production inventory systems
R. Kapuscinski and S. Tayur · 1999
Earlier work this paper cites.
Measure-valued differentiation for stochastic processes: The finite horizon case
B. Heidergott and F. Vázquez-Abad · 2000
Earlier work this paper cites.
New victories in the supply-chain revolution still looking for ways to tighten shipping, inventory, and even manufacturing costs at your company? Here’s how four masters of supply-chain efficiency are doing it
P. Siekman · 2000
Earlier work this paper cites.
Policy gradient methods for reinforcement learning with function approximation
R. S. Sutton, D. A. McAllester, S. P. Singh, and Y. Mansour · 2000
Earlier work this paper cites.
A course on sensitivity analysis for gradient estimation of DES performance measures
F. J. Vázquez-Abad · 2000
Earlier work this paper cites.
Probability and Random Processes
G. Grimmett and D. Stirzaker · 2001
Earlier work this paper cites.

Similar

The bias-variance dilemma of the Monte Carlo method
Z. Mark and Y. Baram · 2001
Cited alongside, same era.
The optimal reward baseline for gradient-based reinforcement learning
L. Weaver and N. Tao · 2001
Cited alongside, same era.
Some new perspectives on the method of control variates
P. W. Glynn and R. Szechtman · 2002
Cited alongside, same era.
Optimal Malliavin weighting function for the computation of the Greeks
E. Benhamou · 2003
Cited alongside, same era.
Measure-valued differentiation for stochastic systems: From simple distributions to Markov chains
B. Heidergott, G. Pflug, and F. Vázquez-Abad · 2003
Cited alongside, same era.
Stochastic Approximation and Recursive Algorithms and Applications , volume 35
H. Kushner and G. G. Yin · 2003
Cited alongside, same era.
Getting it right: Joint distribution tests of posterior simulators
J. Geweke · 2004
Cited alongside, same era.
Variance reduction techniques for gradient estimates in reinforcement learning
E. Greensmith, P. L. Bartlett, and J. Baxter · 2004
Cited alongside, same era.
Variational learning and bits-back coding: An information-theoretic view to Bayesian learning
A. Honkela and H. Valpola · 2004
Cited alongside, same era.
Sensitivity analysis using Itô–Malliavin calculus and martingales, and application to stochastic optimal control
E. Gobet and R. Munos · 2005
Cited alongside, same era.
Variational message passing
J. Winn and C. M. Bishop · 2005
Cited alongside, same era.
Nonuniform random variate generation
L. Devroye · 2006
Cited alongside, same era.

Then

Stochastic structured variational inference
M. Hoffman and D. Blei · 2015
Later among the works it cites.
Variational inference with normalizing flows
D. Rezende and S. Mohamed · 2015
Later among the works it cites.
Optimal Transport for Applied Mathematicians
F. Santambrogio · 2015
Later among the works it cites.
Gradient estimation using stochastic computation graphs
J. Schulman, N. Heess, T. Weber, and P. Abbeel · 2015
Later among the works it cites.
Local expectation gradients for black box variational inference
M. Titsias and M. Lázaro-Gredilla · 2015
Later among the works it cites.
Stochastic gradient estimation with finite differences
L. Buesing, T. Weber, and S. Mohamed · 2016
Later among the works it cites.
Stochastic backpropagation through mixture density distributions
Original
A. Graves · 2016
Later among the works it cites.
MuProp: Unbiased backpropagation for stochastic neural networks
S. Gu, S. Levine, I. Sutskever, and A. Mnih · 2016
Later among the works it cites.
Counterfactual prediction with deep instrumental variables networks
J. Hartford, G. Lewis, K. Leyton-Brown, and M. Taddy · 2016
Later among the works it cites.
(Bandit) Convex optimization with biased noisy gradient oracles
X. Hu, L. Prashanth, A. György, and C. Szepesvári · 2016
Later among the works it cites.
Continuous control with deep reinforcement learning
T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra · 2016
Later among the works it cites.
A kernelized Stein discrepancy for goodness-of-fit tests
Q. Liu, J. Lee, and M. Jordan · 2016
Later among the works it cites.
The Concrete distribution: A continuous relaxation of discrete random variables
C. J. Maddison, A. Mnih, and Y. W. Teh · 2016
Later among the works it cites.
Learning in implicit generative models
Original
S. Mohamed and B. Lakshminarayanan · 2016
Later among the works it cites.
Operator variational inference
R. Ranganath, D. Tran, J. Altosaar, and D. Blei · 2016
Later among the works it cites.
Deep amortized inference for probabilistic programs
Original
D. Ritchie, P. Horsfall, and N. D. Goodman · 2016
Later among the works it cites.
The generalized reparameterization gradient
F. R. Ruiz, M. Titsias, and D. Blei · 2016
Later among the works it cites.
Taking the human out of the loop: A review of Bayesian optimization
B. Shahriari, K. Swersky, Z. Wang, R. P. Adams, and N. De Freitas · 2016
Later among the works it cites.
Mastering the game of Go with deep neural networks and tree search
D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, et al · 2016
Later among the works it cites.
Deep variational information bottleneck
A. A. Alemi, I. Fischer, J. V. Dillon, and K. Murphy · 2017
Later among the works it cites.
Variational inference: A review for statisticians
D. M. Blei, A. Kucukelbir, and J. D. McAuliffe · 2017
Later among the works it cites.
UCI machine learning repository, 2017
D. Dua and C. Graff · 2017
Later among the works it cites.
Beta-VAE: Learning basic visual concepts with a constrained variational framework
I. Higgins, L. Matthey, A. Pal, C. Burgess, X. Glorot, M. Botvinick, S. Mohamed, and A. Lerchner · 2017
Later among the works it cites.
Automatic differentiation variational inference
A. Kucukelbir, D. Tran, R. Ranganath, A. Gelman, and D. M. Blei · 2017
Later among the works it cites.
Grammar variational autoencoder
M. J. Kusner, B. Paige, and J. M. Hernández-Lobato · 2017
Later among the works it cites.
Gradient estimators for implicit models
Y. Li and R. E. Turner · 2017
Later among the works it cites.
SGDR: Stochastic gradient descent with warm restarts
I. Loshchilov and F. Hutter · 2017
Later among the works it cites.
Reducing reparameterization gradient variance
A. Miller, N. Foti, A. D’Amour, and R. P. Adams · 2017
Later among the works it cites.
Reparameterization gradients through acceptance-rejection sampling algorithms
C. Naesseth, F. Ruiz, S. Linderman, and D. Blei · 2017
Later among the works it cites.
Control functionals for Monte Carlo integration
C. J. Oates, M. Girolami, and N. Chopin · 2017
Later among the works it cites.
Black Box Variational Inference: Scalable, Generic Bayesian Computation and its Applications
R. Ranganath · 2017
Later among the works it cites.
REBAR: Low-variance, unbiased gradient estimates for discrete latent variable models
G. Tucker, A. Mnih, C. J. Maddison, J. Lawson, and J. Sohl-Dickstein · 2017
Later among the works it cites.
Automatic differentiation in machine learning: A survey
A. G. Baydin, B. A. Pearlmutter, A. A. Radul, and J. M. Siskind · 2018
Later among the works it cites.
Quasi-Monte Carlo variational inference
A. Buchholz, F. Wenzel, and S. Mandt · 2018
Later among the works it cites.
Neural scene representation and rendering
S. A. Eslami, D. J. Rezende, F. Besse, F. Viola, A. S. Morcos, M. Garnelo, A. Ruderman, A. A. Rusu, I. Danihelka, K. Gregor, et al · 2018
Later among the works it cites.
Implicit reparameterization gradients
M. Figurnov, S. Mohamed, and A. Mnih · 2018
Later among the works it cites.
DiCE: The infinitely differentiable Monte Carlo estimator
J. Foerster, G. Farquhar, M. Al-Shedivat, T. Rocktäschel, E. P. Xing, and S. Whiteson · 2018
Later among the works it cites.
Differentiation via logarithmic expansions
M. C. Fu, B. Heidergott, H. Leahu, and F. Vazquez-Abad · 2018
Later among the works it cites.
Pathwise derivatives beyond the reparameterization trick
M. Jankowiak and F. Obermeyer · 2018
Later among the works it cites.
Reparameterization gradient for non-differentiable models
W. Lee, H. Yu, and H. Yang · 2018
Later among the works it cites.
A baseline for any order gradient estimation in stochastic computation graphs
J. Mao, J. Foerster, T. Rocktäschel, M. Al-Shedivat, G. Farquhar, and S. Whiteson · 2018
Later among the works it cites.
Total stochastic gradient algorithms and applications in reinforcement learning
P. Parmas · 2018
Later among the works it cites.
PIPPS: Flexible model-based policy search robust to the curse of chaos
P. Parmas, C. E. Rasmussen, J. Peters, and K. Doya · 2018
Later among the works it cites.
Learning implicit generative models with the method of learned moments
S. Ravuri, S. Mohamed, M. Rosca, and O. Vinyals · 2018
Later among the works it cites.
A spectral approach to gradient estimation for implicit distributions
J. Shi, S. Sun, and J. Zhu · 2018
Later among the works it cites.
Maximizing acquisition functions for Bayesian optimization
J. T. Wilson, F. Hutter, and M. P. Deisenroth · 2018
Later among the works it cites.
Variance reduction properties of the reparameterization trick
M. Xu, M. Quiroz, R. Kohn, and S. A. Sisson · 2018
Later among the works it cites.
GO gradient for expectation-based objectives
Y. Cong, M. Zhao, K. Bai, and L. Carin · 2019
Closest in time.
Pathwise derivatives for multivariate distributions
M. Jankowiak and T. Karaletsos · 2019
Closest in time.
Measure-valued derivatives for approximate Bayesian inference
M. Rosca, M. Figurnov, S. Mohamed, and A. Mnih · 2019
Closest in time.
New tricks for estimating gradients of expectations
Original
C. J. Walder, P. Rousse, R. Nock, C. S. Ong, and M. Sugiyama · 2019
Closest in time.
Credit assignment techniques in stochastic computation graphs
T. Weber, N. Heess, L. Buesing, and D. Silver · 2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…