Monte Carlo Gradient Estimation in Machine Learning.

Shakir Mohamed, Mihaela Rosca, Michael Figurnov, Andriy Mnih

TL;DR

This paper provides a comprehensive survey of Monte Carlo gradient estimation techniques, crucial for optimizing machine learning models. It delves into three primary methods—score function, pathwise, and measure-valued—explaining their derivations, assumptions, and trade-offs, offering guidance on choosing the right tool for various machine learning tasks.

What Problem Does This Paper Address?

At the heart of many machine learning problems, from supervised learning to reinforcement learning, lies the challenge of computing the gradient of an expected value with respect to the parameters of a probability distribution. This is essential for optimization, but often intractable due to high-dimensional integrals and complex, sometimes non-differentiable, cost functions. The paper aims to provide a unified and accessible overview of the various Monte Carlo methods developed to tackle this "gradient estimation" problem, enabling more efficient and effective model training and analysis.

Methods

The paper systematically explores three main classes of Monte Carlo gradient estimators:

  • Score Function Estimator: This method leverages the derivative of the log-probability distribution. It's general-purpose and applicable to a wide range of problems, including those with discrete distributions or black-box cost functions. However, it can suffer from high variance.
  • Pathwise Estimator: This approach relies on the differentiability of the sampling path (how random variables are generated from parameters). It's often more computationally efficient and has lower variance than the score function estimator when applicable, but it requires differentiable cost functions.
  • Measure-Valued Gradient Estimator: This technique decomposes the derivative of the probability measure into positive and negative components, leading to unbiased estimators with potentially low variance, especially when coupling is used. It's applicable to both discrete and continuous distributions and non-differentiable cost functions but can be computationally expensive in high dimensions.

The paper also discusses crucial aspects like variance reduction techniques (control variates, coupling, conditioning), higher-order gradients, and computational considerations for each method.

Datasets

The paper uses a standard UCI dataset for Bayesian logistic regression (Women's Breast Cancer data set) for empirical evaluation.

Key Insights and Ideas

  • No Silver Bullet: There isn't a single "best" gradient estimator; the choice depends heavily on the problem's characteristics (differentiability of cost function, dimensionality, availability of sampling paths, computational budget).
  • Variance is Key: Low variance is paramount for efficient optimization and accurate sensitivity analysis. Variance reduction techniques are not optional but essential for practical performance.
  • Trade-offs Abound: Each estimator presents a trade-off between generality, computational cost, variance, and applicability. For instance, pathwise estimators are efficient but require differentiable cost functions, while score function estimators are more general but can have higher variance.
  • The Power of Coupling: For measure-valued estimators, coupling (using common random numbers for positive and negative components) can significantly reduce variance, especially when the underlying distributions are related.
  • Stochastic Computational Graphs: The paper highlights the growing importance of computational graphs for building complex probabilistic models and automating gradient estimation, enabling the seamless integration of different estimators and variance reduction techniques.

Key Results

The paper presents extensive theoretical derivations and empirical results, primarily through figures illustrating the variance of different estimators under various conditions.

  • Empirical Comparisons: In the Bayesian logistic regression case study, the pathwise estimator generally showed lower variance and faster convergence than the score-function estimator.
  • Variance Reduction Impact: Control variates (like the delta method and moving average baseline) significantly reduced variance for both score-function and pathwise estimators, with the delta method showing particular effectiveness.
  • Measure-Valued Estimator Performance: While computationally more expensive, the measure-valued estimator, especially with coupling, demonstrated competitive variance reduction, sometimes outperforming others.
  • Dimensionality Effects: The score-function estimator's variance was shown to be sensitive to parameter dimensionality, whereas the measure-valued estimator was less so.

Limitations and Future Work

Limitations:

  • The pathwise estimator is limited to differentiable cost functions.
  • Measure-valued gradients can be computationally prohibitive in high-dimensional parameter spaces.
  • The effectiveness of control variates depends on finding strongly correlated functions.

Future Work:

  • Developing new gradient estimators for situations where the measure is known only implicitly (e.g., diffusion processes).
  • Creating more effective variance reduction tools, particularly for complex systems like Markov processes.
  • Exploring the connections between score functions and importance sampling for variance reduction.
  • Investigating the application of measure-valued derivatives in machine learning.
  • Developing automated computational frameworks for measure-valued gradients.
  • Further research into hybrid estimators and advanced variance reduction techniques.

Summary updated

Abstract

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. We describe their use in other fields, show how they are related and can be combined, and expand on their possible generalisations. Wherever Monte Carlo gradient estimators have been derived and deployed in the past, important advances have followed. A deeper and more widely-held understanding of this problem will lead to further advances, and it is these advances that we wish to support.
BibTeX
@article{mohamed2020monte,
  author = {Shakir Mohamed and Mihaela Rosca and Michael Figurnov and Andriy Mnih},
  title = {{Monte Carlo Gradient Estimation in Machine Learning.}},
  journal = {JMLR},
  year = {2020},
}
Figure