PaperlayerView exact revision on arXiv

Source-linked AI summary

Monte Carlo Gradient Estimation in Machine Learning

Shakir Mohamed, Mihaela Rosca, Michael Figurnov, Andriy Mnih

arXiv:1906.10652v2stat.MLcs.LGmath.OC

TL;DR

The paper surveys how to compute gradients of expectations, a problem central to sensitivity analysis and many machine-learning applications. It develops and compares score-function, pathwise, and measure-valued estimators, concluding that estimator choice depends on function smoothness, parameter dimension, and variance considerations.

  • Problem

    Computing gradients of expectations is a fundamental problem across computational science and underlies many machine-learning and sensitivity-analysis applications.

  • Method

    The paper develops three estimator classes—score-function, pathwise, and measure-valued—while analyzing their principles, variance control, applications, and applicability.

  • Results

    The survey organizes these gradients into gradients-of-measures and gradients-of-paths and derives the corresponding estimator approaches across many research areas.

  • Takeaways & Limitations

    For continuous functions and measures, pathwise estimation is a good default; black-box or nondifferentiable costs require score-function or measure-valued methods, with dimension guiding the choice.

  • Takeaways & Limitations

    The paper deliberately limits its main scope to measures that are continuous in their domain, leaving discrete-distribution settings largely for separate treatment.

Abstract

from arXiv · show

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.

1. Introduction

The paper frames stochastic-gradient computation as sensitivity analysis for expectations whose distributional parameters are learned. It motivates a broad review of Monte Carlo estimators, their applications, and practical trade-offs.

  • Problem: The central problem is computing the gradient of a general probabilistic objective F with respect to distributional parameters θ.The expectation averages a cost f over a probability measure p(x; θ).
  • Scope: The review restricts attention to probability measures that are continuous in their domain and differentiable with respect to distributional parameters.This leaves discrete-distribution settings outside the main scope.
  • Why it matters: This gradient supports model explanation and optimisation by characterising how the expected cost changes when θ changes.The paper calls this sensitivity analysis.
  • Challenges: Monte Carlo estimators are needed because expectations may lack closed forms, involve high-dimensional integrals and parameters, or use non-differentiable or black-box costs.Machine-learning applications additionally require efficient, accurate, parallelisable computation with few cost evaluations.
  • Scope: The review develops score-function, pathwise and measure-valued estimators, alongside variance control, case studies, generalisations and guidance for choosing methods.It also connects stochastic-gradient problems across five research areas.

2. Monte Carlo Methods and Stochastic Optimisation

Monte Carlo methods approximate expectations by averaging samples, making them applicable when integrals are difficult to evaluate directly. The resulting stochastic gradients support explanation and optimisation across diverse statistical and machine-learning problems.

  • Monte Carlo estimation: Monte Carlo estimation applies when an integral is expressible as a function times a distribution that can be sampled easily.The sample average is itself a random estimator of the expectation.
  • Estimator criteria: A Monte Carlo estimator should be consistent, unbiased, low-variance and computationally efficient.These properties concern convergence, average correctness, estimate accuracy and practical cost.
  • Estimator criteria: Low-variance gradients improve estimate accuracy and can make stochastic optimisation more efficient by permitting larger learning rates.This may reduce the number of optimisation steps needed for convergence.
  • Stochastic optimisation: The gradient characterises cost sensitivity for explanation and is the key quantity required to optimise distributional parameters θ.The stochastic optimisation loop alternates simulation with optimisation.
  • Applications: The gradient problem appears in approximate inference, reinforcement learning, experimental design, active learning and computational finance.Examples include variational inference, probability-of-improvement design and pricing sensitivities.

3. Intuitive Analysis of Gradient Estimators

Gradient estimators can differentiate either the measure or the sampling path. Their variance and computational cost depend on the estimator, cost function, parameter dimension and available variance reduction.

  • Estimator classes: Measure derivatives differentiate p(x; θ), whereas path derivatives differentiate the cost along the pathway from θ through x to the cost.The score-function and measure-valued estimators are measure derivatives; the pathwise estimator is a path derivative.
  • Estimator classes: The review focuses on score-function, pathwise and measure-valued estimators, which are all consistent and unbiased but differ in variance and computational cost.The comparison also considers differentiability and changing cost functions.
  • Quadratic costs: For quadratic costs, score-function variance is highest, pathwise variance lower, and measure-valued variance lowest, although pathwise can win for some mean gradients.The ranking is therefore not universal.
  • Computational cost: Score-function and pathwise estimators use one sample even for multivariate distributions, whereas measure-valued estimation requires 2D cost evaluations for D parameters.This makes measure-valued estimation less attractive in high-dimensional settings.
  • Changing cost functions: For exponential and cosine costs, changing k can reverse which estimator has the lowest or highest variance as the functions become sharper.The pathwise variance increases with k in the illustrated exponential case.
  • Variance reduction: Control variates substantially reduce score-function variance, while coupling provides variance reduction for the measure-valued estimator.The figures use both techniques to compare reduced-variance estimators.

4. Score Function Gradient Estimators

The score-function estimator is a general measure-derivative approach for Monte Carlo gradient estimation. It is widely used under several names across the literature.

  • Overview: The score-function estimator differentiates the measure and is among the most general gradient estimators available.The paper derives it and examines its properties and applications.
  • Terminology: It is also known as the likelihood ratio method and the REINFORCE estimator.These names appear across different research literatures.

4.1 Score Functions

The score function is the gradient of the log probability and provides a key identity for rewriting probability derivatives. Its zero expectation and Fisher-information variance are central properties for deriving and analysing gradient estimators.

  • The score function is the gradient of the log probability with respect to distributional parameters.It is obtained by differentiating the logarithm of the probability distribution.
  • The score identity converts derivatives of probabilities into probability-weighted derivatives of log probabilities.This form supports Monte Carlo estimators based on expectations under the measure p.
  • The score has zero expectation under the probability distribution.This property follows from differentiating the fact that a probability distribution integrates to one.
  • The variance of the score is the Fisher information and helps establish the Cramer-Rao lower bound.

4.2 Deriving the Estimator

The score-function estimator is derived by exchanging differentiation and integration, applying the score identity, and expressing the result as an expectation. A baseline can preserve unbiasedness while reducing variance.

  • The estimator is derived by rewriting the sensitivity gradient as an expectation involving the score function and cost.The derivation first exchanges integration and differentiation, then applies the score identity.
  • The resulting expectation has the form needed for Monte Carlo estimation because it combines a samplable distribution with a score-weighted cost.
  • A constant baseline can replace the cost with a shifted version without introducing bias.The added term has zero expectation because the score itself has zero expectation.
  • The baseline-corrected estimator is preferred because it provides a simple and effective form of variance reduction.

4.3 Estimator Properties and Applicability

The score-function estimator is broadly applicable but depends on valid differentiation–integration interchange and absolute continuity. Its variance can grow with importance-ratio instability, dimensionality, and cost variability.

  • Applicability: An unbiased score-function gradient requires conditions that justify exchanging differentiation and integration.These include smoothness, integrability, differentiability, and an integrable domination condition.
  • Applicability: Absolute continuity is required because the importance ratio must remain defined wherever the original measure has support.Failure can bias the gradient, as in the uniform distribution U[0, θ] whose parameter defines the support.
  • Applicability: The bounded-support example shows that the score-function estimator can fail to provide the correct gradient at a support boundary.
  • Variance: Near-failures of absolute continuity increase variance through the importance ratio, while complete failures can produce biased gradients.
  • Variance: In high dimensions, importance weights can become highly skewed, producing high variance despite having expectation one.
  • Variance: O(D2) variance arises for a summed cost with bounded individual variance, and irrelevant cost terms further increase estimator variance.Using derivatives of the cost can remove terms that do not influence the parameter being differentiated.
  • Computational considerations: Highly variable costs can produce highly variable gradients, motivating normalization, bounding, or clipping of cost values.The gradient can be interpreted through covariance between the cost and score function.

4.4 Research in Score Function Gradient Estimation

Research on score-function gradient estimation spans operations research, computational finance, machine learning, and reinforcement learning. The estimator has a long development history and remains central to several learning methods.

  • The score-function estimator has been developed and applied across computational science, especially operations research, computational finance, and machine learning.The surveyed literature emphasizes theoretical insight and practical context.
  • The estimator emerged through independent work in the 1960s and was later called the score function method and likelihood ratio method.Early applications included nuclear-reactor design, Monte Carlo optimization, discrete-event systems, and queueing systems.
  • Its application requires attention to differentiability and the validity of interchanging integration and differentiation.This issue is particularly relevant in discrete-event systems studied in operations research.
  • In machine learning, the estimator underlies REINFORCE, policy-gradient methods, actor-critic methods, and some variational-inference approaches.

5. Pathwise Gradient Estimators

Pathwise gradient estimators reparameterize samples through a differentiable sampling path, moving distributional parameters into the cost so standard differentiation can estimate gradients. This approach often offers lower variance and easier implementation than score-function estimators, but requires suitable path information.

  • 5.3 Estimator Properties and Applicability: Pathwise estimation is less general-purpose than score-function estimation because it requires information about the underlying sampling path, but it can provide lower variance and easier implementation.Its advantages arise from exploiting structural characteristics of how randomness enters the objective.
  • 5.1 Sampling Paths: A pathwise estimator samples parameter-independent noise and transforms it through a parameterized deterministic path into samples from the target distribution.The representation is x = g(ϵ, θ), with ϵ drawn from a base distribution independent of θ.
  • 5.2 Derivation: LOTUS reparameterizes expectations over x as expectations over base noise, placing θ inside the cost and enabling differentiation under the integral.The resulting gradient applies the chain rule to the transformed cost.
  • 5.2 Derivation: The pathwise gradient computes gradients of expectations by pushing parameters into the cost function and applying standard differentiation through the sampling path.The sampling path need not always be invertible, extending applicability beyond the basic change-of-variables formula.
  • 5.3 Estimator Properties and Applicability: The basic pathwise estimator requires a differentiable path used for sampling, so rejection-sampled Gamma distributions do not directly satisfy its assumptions.Implicit reparameterization can instead use derivatives of an inverse path, broadening applicability to additional distributions.
  • 5.3 Estimator Properties and Applicability: For Gaussian measures, the pathwise estimator has a dimension-free variance bound in terms of the squared Lipschitz constant of the cost function.Tail bounds can support rapid Monte Carlo convergence, sometimes even with a single sample, although sharper costs may require more samples.

6. Measure-valued Gradients

Measure-valued gradients represent density derivatives using signed-measure decompositions and estimate sensitivities as weighted differences of expectations. The resulting estimators are unbiased and general-purpose, including for nondifferentiable costs and discrete or continuous distributions.

  • 6. Measure-valued Gradients: Measure-valued gradient estimators exploit signed-measure properties to construct derivatives of probability measures.They are also called weak derivative methods or measure-valued derivatives.
  • 6.1 Weak Derivatives: A density derivative is decomposed into positive and negative densities multiplied by constants, forming a weak-derivative triple.For each scalar parameter, the triple is (cθi, p+, p−); multivariate parameters use one triple per dimension.
  • 6.1 Weak Derivatives: The weak derivative does not require the density itself to be differentiable, only suitable convergence of integrals against test functions.The decomposition is not unique and can be obtained through the Hahn-Jordan decomposition.
  • 6.2 Measure-valued Estimator: The measure-valued estimator computes a gradient as a weighted difference of two expectations under the positive and negative component distributions.The two component samples can be coupled with common random numbers for variance reduction.
  • 6.2 Measure-valued Estimator: For Bernoulli distributions, the measure-valued estimator coincides with the score-function estimator.The weak derivative uses the triple (1, δ1, δ0).
  • 6.2 Measure-valued Estimator: The estimator applies to any cost function, differentiable or not, because it only requires evaluating the cost at different inputs.The same framework extends from scalar to vector parameters and from univariate to factorized multivariate distributions.

6.3 Estimator Properties and Applicability

Measure-valued gradients can remain correct without the domination condition required by score-function derivations, while their variance depends on decomposition, coupling, cost magnitude, and measure variance. Their principal practical limitation is computational cost in high-dimensional parameter spaces.

  • 6.3.1 Domination: The measure-valued derivative avoids the domination requirement that can cause pathology for score-function estimators on bounded-support distributions.In the revisited bounded-support example, it achieves the correct gradient value without requiring domination.
  • 6.3.1 Domination: Under bounded continuous costs, weak-derivative theory establishes unbiasedness; unbiasedness also extends to some unbounded or almost-everywhere-continuous costs.The broader conditions require discontinuity sets to have measure zero under the positive and negative components.
  • 6.3.2 Bias and Variance Properties: Coupling reduces measure-valued estimator variance by increasing the covariance between positive- and negative-component evaluations.The choice of weak-derivative decomposition also affects variance, with Hahn-Jordan decomposition suggested as generally favorable.
  • 6.3.2 Bias and Variance Properties: The coupled measure-valued estimator is insensitive to the dimensionality of measure parameters but sensitive to cost magnitude and measure variance.Figure 5 examines these effects for Gaussian measures with linear and fourth-order costs.
  • 6.3.3 Computational Cost: Measure-valued gradients require two cost evaluations per parameter, making them computationally expensive in high-dimensional parameter spaces.This per-parameter cost is the trade-off for adapting sampling distributions to obtain low variance.

6.4 Research in Measure-valued Derivatives

Research on weak derivatives established their behavior under several operations and supplied derivations for common distributions, strengthening the foundation for measure-valued gradient estimators.

  • 6.4 Research in Measure-valued Derivatives: Subsequent weak-derivative research characterized behavior under convex combinations, convolution, transformation, restriction, and conditions sufficient for unbiasedness.Derivations for many common distributions were later provided explicitly after often being omitted in earlier papers.

7. Variance Reduction Techniques

Variance reduction is central to Monte Carlo gradient estimation because lower-variance gradients improve accuracy and can make stochastic optimisation more efficient. The survey examines larger samples, coupling, conditioning, and control variates, emphasizing trade-offs between generic simplicity and problem-specific effectiveness.

  • Increasing samples reduces estimator variance as O(1/N), but computational cost grows linearly with N.
  • Coupling reduces variance when paired function evaluations are positively correlated, but finding effective couplings can be difficult.Common random numbers provide a simple coupling technique for closely related distributions.
  • Maxwell-Gaussian coupling can reduce variance for the measure-valued gradient estimator, whereas Weibull-Weibull coupling can increase variance depending on the cost function.
  • Conditioning, or Rao-Blackwellisation, guarantees lower variance when conditional expectations can be computed, but those computations may be costly.In that case, increasing the number of samples over the original space may be easier and at least as effective.
  • Control variates reduce variance when the auxiliary function has a tractable expectation and is correlated with the target, with stronger correlation yielding greater reduction.Estimating the optimal coefficient from the same samples introduces bias, although it is often small and decreases quickly as sample size increases.
  • Linear controls remain the default practical choice, while non-linear controls may help in small-sample settings but offer no asymptotic advantage.Running-average baselines are easy and cheap but are not optimal and do not guarantee lower variance than the vanilla score-function estimator.

8. Case Studies in Gradient Estimation

The case studies compare Monte Carlo gradient estimators, variance-reduction methods, and sampling choices across variational inference experiments. They show that estimator performance depends on variance, convergence, function-evaluation cost, and implementation complexity.

  • The case studies examine gradient estimation across supervised, unsupervised, and reinforcement learning, including combinations of estimator and variance-reduction methods.The review identifies unexplored combinations as potential future-work directions.
  • Variance reduction: Automatic differentiation enables delta-method control variates that reduce variance for both score-function and pathwise estimators.These methods exploit differentiability of the cost function and can be implemented without manual derivation.
  • Estimator comparisons: The pathwise estimator has lower variance and faster convergence than the score-function estimator, while delta-method control variates reduce score-function variance more than a moving-average baseline.Where applicable, the pathwise estimator reaches the same performance level with lower variance and faster convergence.
  • Sampling trade-offs: Increasing the number of samples benefits the score-function estimator more than the pathwise estimator, and N = 100, B = 32 matches the delta-control-variate result at N = 10, B = 32.This comparison exposes a trade-off between implementation complexity and sample efficiency.
  • Estimator comparisons: The measure-valued estimator matches pathwise variance without cost gradients and outperforms vanilla score-function estimation, but its advantage depends on function-evaluation cost and baselines.With equal function evaluations, the vanilla score-function estimator remains higher-variance, while a moving-average baseline performs best.

9. Discussion and Extensions

The discussion connects Monte Carlo gradient estimators to implementation frameworks, estimator extensions, and practical verification. It also identifies boundaries involving computational support, unavailable densities, Gaussian-specific methods, and discrete distributions.

  • Verification: Estimator implementations should be validated against analytic gradients when available and against agreement among unbiased estimators over many samples.Control-variate implementations can additionally be checked by comparing stochastic and analytic expectations and gradients.
  • Stochastic computational graphs: Stochastic computational graphs combine deterministic and stochastic components to automatically compute gradients for differentiable and non-differentiable costs.They support score-function and pathwise estimators, variance reduction, and higher-order gradients.
  • Stochastic computational graphs: Existing automated computational frameworks do not yet include measure-valued gradients, although weak derivatives and sampling mechanisms could support such extensions.The paper notes that common distributions often have known weak derivatives and positive and negative density components.
  • Gaussian measures: Gaussian measures permit pathwise estimation through the location-scale transform and direct mean and covariance gradients through Bonnet’s and Price’s theorems.Price’s theorem is more computationally expensive because it requires Hessian evaluation.
  • Implicit models: Pathwise estimation requires a known differentiable log-probability, limiting direct use with likelihood-free or implicit probabilistic models.Kernel substitution and Stein’s identity are described as approaches for gradient estimation in implicit models.
  • Scope: The review is intentionally limited to continuous distributions, leaving discrete latent-variable and combinatorial-optimisation settings outside its main scope.Score-function and measure-valued derivatives can still apply when discrete distributions are continuous with respect to their parameters.

10. Conclusion

The paper frames Monte Carlo gradient estimation as a fundamental problem spanning many applications and offers practical guidance for choosing among estimator classes. It also identifies unresolved needs for new estimators and stronger variance-reduction tools.

  • Monte Carlo gradient estimation underlies applications across applied statistics, queueing theory, machine learning, computational finance, experimental design, optimal transport, continuous-time stochastic processes, and variational inference.
  • For continuous functions and continuous measures, the pathwise estimator is a good default because it is relatively easy to implement and typically has sufficiently low variance.
  • For non-differentiable or black-box costs, score-function and measure-valued gradients remain available; measure-valued gradients typically have lower variance when parameter dimensionality is low.
  • Discrete measures permit score-function or measure-valued gradients, while broad testing is recommended to verify estimator unbiasedness in implementation.
  • Future work still requires gradient estimators for explicit or implicitly diffused measures and new variance-reduction tools, especially for complex systems such as Markov processes.

Appendix A. Common Distributions

Appendix A provides a reference table for distributions mentioned in the paper and their densities.

  • Appendix A provides definitions of distributions mentioned within the paper.
  • The appendix serves as a reference for the distributions used in the paper.
  • Table 2 lists distributions and their densities.
Loading 1906.10652v2…