Simulation gradient estimation and simultaneous perturbation

Fix a finite dimension $d\ge 1$, an open set $\mathrm{\Theta }\subseteq {\mathbb{R}}^d$, and a probability space $(\mathrm{\Omega },\mathcal{F},P)$. A simulation payoff is a jointly measurable map $H:\mathrm{\Theta }\times \mathrm{\Omega }\to \mathbb{R}$ such that $H(\theta ,\cdot )$ is integrable for each $\theta \in \mathrm{\Theta }$. Its objective is $J(\theta ):=\mathbb{E}[H(\theta ,\cdot )]\mathrm{.}$ A payoff-oracle call at $\theta$ returns an integrable real random variable $Y(\theta )$ with $\mathbb{E}[Y(\theta )]=J(\theta )$. Two calls may use the same random input or different random inputs; their joint law is part of the chosen coupling. A single oracle call is one function evaluation, regardless of the cost of its internal simulation.

For a parameter-dependent random payoff, pointwise weak convergence of its output law, even together with uniform convergence of its expected payoff, implies convergence of derivatives of the expected payoffs.

Use Simulation objectives and unbiased payoff oracles and write $J(\theta )=\mathbb{E}[H(\theta ,Z)]$ using one fixed random input $Z$ whose law does not depend on $\theta$. If, for almost every input, the map $\theta \mapsto H(\theta ,Z)$ is differentiable, its pathwise (or reparameterized) gradient estimator is $G_{\mathrm{p}\mathrm{w}}(\theta ,Z):=D_{\theta }H(\theta ,Z)\mathrm{.}$ When $H(\theta ,Z)=h(T(\theta ,Z),\theta )$, with differentiable $T$ and $h$, the chain rule gives $G_{\mathrm{p}\mathrm{w}}=D_{x}h(T(\theta ,Z),\theta )D_{\theta }T(\theta ,Z)+{\mathrm{\partial }}_{\theta }h(T(\theta ,Z),\theta )\mathrm{.}$ The estimator differentiates the simulated outcome while holding the same random input fixed. This definition alone does not assert that its expectation equals $\mathrm{\nabla }J(\theta )$.

Gradients are Euclidean column vectors, and vector expectations are taken coordinatewise.

Assume the Axiom of Choice. Let $\mathrm{\Theta }\subseteq {\mathbb{R}}^d$ be open, fix ${\theta }_0\in \mathrm{\Theta }$, let $\nu$ be a fixed sigma-finite positive measure on a measurable space $(\mathcal{X},\mathcal{A})$, and let $p_{\eta }$ be normalized densities of probability laws $P_{\eta }$ relative to $\nu$. Suppose there are an open ball $U\subseteq \mathrm{\Theta }$ about ${\theta }_0$, a measurable set $S\in \mathcal{A}$, and one $\nu$-null set $N$ such that, for every $\eta \in U$ and every $x\mathrm{\notin }N$, $p_{\eta }(x)>0$ exactly when $x\in S$, and $\eta \mapsto p_{\eta }(x)$ is continuously differentiable. Assume the coordinate derivatives are measurable, let $H:\mathcal{X}\to \mathbb{R}$ be measurable, and suppose $\int \mathrm{\mid }H\mathrm{\mid }{p}_{\eta }d\nu <\mathrm{\infty }$ for each $\eta \in U$. Finally assume there is $G\in L^1(\nu )$ such that $\mathrm{\mid }H(x)\mathrm{\mid }{\sup }_{\eta \in U}\mathrm{\parallel }{\mathrm{\nabla }}_{\eta }{p}_{\eta }(x){\mathrm{\parallel }}_2\le G(x)\text{for }\nu \text{-almost every }x\mathrm{.}$ If also ${\mathbb{E}}_{{\theta }_0}\text{\hspace{0.17em}⁣}[H(X{)}^2\mathrm{\parallel }{S}_{{\theta }_0}(X){\mathrm{\parallel }}_2^2]<\mathrm{\infty },$ where $S_{{\theta }_0}={\mathrm{\nabla }}_{\theta }\log p_{{\theta }_0}$ is the score of Score and Fisher information, then $J(\theta )={\mathbb{E}}_{\theta }H(X)$ is Fréchet differentiable at ${\theta }_0$ and $\mathrm{\nabla }J({\theta }_0)={\mathbb{E}}_{{\theta }_0}[H(X)S_{{\theta }_0}(X)]\mathrm{.}$ The score estimator is unbiased and has finite coordinate variances. The fixed-support hypothesis is a sufficient condition here.

Use Simulation objectives and unbiased payoff oracles: let $H:\mathrm{\Theta }\times \mathrm{\Omega }\to \mathbb{R}$ be the simulation payoff on its probability space and write its objective as $J(\eta ):=\mathbb{E}[H(\eta ,\cdot )]\mathrm{.}$ For $\theta \in \mathrm{\Theta }$, a direction $v\in {\mathbb{R}}^d$, and $h>0$ with $\theta \pm hv\in \mathrm{\Theta }$, the coupled central-difference estimator is the random variable $D_{h,v}^{\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{p}}(\omega ):=\frac{H(\theta +hv,\omega )-H(\theta -hv,\omega )}{2h}\mathrm{.}$ The same random input $\omega$ is used in both terms; this fixes their joint law and, when both payoffs are square-integrable, their covariance. The estimator's variance is not asserted to be smaller for every coupling.

Input a dimension $d\ge 1$, $\theta \in \mathrm{\Theta }\subseteq {\mathbb{R}}^d$, a scalar $c>0$, a payoff oracle from Simulation objectives and unbiased payoff oracles, and a random vector $\mathrm{\Delta }=({\mathrm{\Delta }}_1,\dots ,{\mathrm{\Delta }}_d)$ whose coordinates are independent, symmetric about zero, and nonzero almost surely. Require $\theta +c\mathrm{\Delta },\theta -c\mathrm{\Delta }\in \mathrm{\Theta }$ almost surely. The perturbation and simulator inputs are realized on a common probability space. Require the paired random-parameter oracle outputs $Y^{+},Y^{-}$, extended by zero on the exceptional zero-output branch, to be measurable real random variables; fixed-parameter integrability alone does not impose this condition.

1. Draw one $\mathrm{\Delta }$. If any ${\mathrm{\Delta }}_i=0$ or either $\theta +c\mathrm{\Delta }$ or $\theta -c\mathrm{\Delta }$ is outside $\mathrm{\Theta }$, return the zero vector in ${\mathbb{R}}^d$ without calling the oracle.

2. Call the oracle once at $\theta +c\mathrm{\Delta }$ and once at $\theta -c\mathrm{\Delta }$, obtaining $Y^{+}$ and $Y^{-}$.

3. Return ${\widehat{G}}_i(\theta ):=\frac{Y^{+}-Y^{-}}{2c{\mathrm{\Delta }}_i},i=1,\dots ,d\mathrm{.}$

The same numerator supplies all $d$ coordinates. The zero-output branch has probability zero under the input assumptions, so one estimator uses exactly two oracle calls almost surely, independently of $d$. The definition does not assert unbiasedness, finite variance, or convergence of an update rule.

Gradients are Euclidean column vectors, and vector expectations are taken coordinatewise.

Let $\mathrm{\Theta }\subseteq {\mathbb{R}}^d$ be open, let $H:\mathrm{\Theta }\times \mathrm{\Omega }\to \mathbb{R}$ be the simulation payoff from Simulation objectives and unbiased payoff oracles, and fix ${\theta }_0\in \mathrm{\Theta }$. Suppose there is an open ball $U$ about ${\theta }_0$ such that for almost every $\omega$, $H(\cdot ,\omega )$ is continuously differentiable on $U$ and ${\mathrm{\nabla }}_{\theta }H(\cdot ,\omega )$ is continuous there, and ${\mathrm{\nabla }}_{\theta }H(\theta ,\cdot )$ is measurable for every $\theta \in U$. Assume $\mathrm{\parallel }{\mathrm{\nabla }}_{\theta }H(\theta ,\omega ){\mathrm{\parallel }}_2\le M(\omega )$ for all $\theta \in U$ outside one measurable null set, where $M$ is nonnegative and integrable, and assume $\mathbb{E}\mathrm{\parallel }{\mathrm{\nabla }}_{\theta }H({\theta }_0,\cdot ){\mathrm{\parallel }}_2^2<\mathrm{\infty }$. Then $J(\theta )=\mathbb{E}H(\theta ,\cdot )$ is Fréchet differentiable at ${\theta }_0$ and $\mathrm{\nabla }J({\theta }_0)=\mathbb{E}[{\mathrm{\nabla }}_{\theta }H({\theta }_0,\cdot )]\mathrm{.}$ Thus the pathwise estimator from Pathwise and reparameterized simulation-gradient estimators is unbiased at ${\theta }_0$ and has finite coordinate variances.

Let $Y^{+}$ and $Y^{-}$ be square-integrable real simulation outputs with any specified joint law, and let $h>0$. The central-difference estimator $D=(Y^{+}-Y^{-})\mathrm{/}(2h)$ satisfies $\mathrm{Var}(D)=\frac{\mathrm{Var}(Y^{+})+\mathrm{Var}(Y^{-})-2\mathrm{Cov}(Y^{+},Y^{-})}{4h^2}\mathrm{.}$ The formula applies in particular when the two outputs use common random numbers as in Coupled finite-difference simulation-gradient estimator. Positive covariance reduces this variance relative to independent outputs with the same marginals; coupling alone does not guarantee positive covariance.

Gradients are Euclidean column vectors, and vector expectations are taken coordinatewise.

Assume AC for the conditional-expectation interface. Let $\mathrm{\Theta }\subseteq {\mathbb{R}}^d$ be open, $\theta \in \mathrm{\Theta }$, and $f:\mathrm{\Theta }\to \mathbb{R}$ be $C^3$. Let ${\mathrm{\Delta }}_1,\dots ,{\mathrm{\Delta }}_d$ be independent, symmetric about zero, and nonzero almost surely, with $\mathbb{E}\mathrm{\mid }{\mathrm{\Delta }}_j\mathrm{\mid }<\mathrm{\infty },\mathbb{E}\mathrm{\mid }{\mathrm{\Delta }}_i{\mathrm{\mid }}^{-1}<\mathrm{\infty },q_i:=\mathbb{E}\text{\hspace{0.17em}⁣}\left[\frac{\mathrm{\parallel }\mathrm{\Delta }{\mathrm{\parallel }}_2^3}{\mathrm{\mid }{\mathrm{\Delta }}_i\mathrm{\mid }}\right]<\mathrm{\infty }\mathrm{.}$ For each $0<c\le c_0$, assume $\{\theta +t\mathrm{\Delta }:\mathrm{\mid }t\mathrm{\mid }\le c\}\subseteq \mathrm{\Theta }$ almost surely and, for almost every realized $\mathrm{\Delta }$, this segment lies in an open set $V_{c,\mathrm{\Delta }}\subseteq \mathrm{\Theta }$ on which $\mathrm{\parallel }{D}^{3}f(y){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le M_3$, where the operator norm is the supremum of $\mathrm{\mid }{D}^{3}f[u,v,w]\mathrm{\mid }$ over unit vectors $u,v,w$. Assume the two oracle outputs in Two-evaluation simultaneous-perturbation gradient estimator satisfy $\mathbb{E}[Y^{\pm }\mid \mathrm{\Delta }]=f(\theta \pm c\mathrm{\Delta })$ and $\mathbb{E}\text{\hspace{0.17em}⁣}\left[\frac{\mathrm{\mid }{Y}^{+}-f(\theta +c\mathrm{\Delta })\mathrm{\mid }+\mathrm{\mid }{Y}^{-}-f(\theta -c\mathrm{\Delta })\mathrm{\mid }}{\mathrm{\mid }{\mathrm{\Delta }}_i\mathrm{\mid }}\right]<\mathrm{\infty }$ for every $i$. Then $\mid \mathbb{E}[{\widehat{G}}_i(\theta )]-{\mathrm{\partial }}_{i}f(\theta )\mid \le \frac{M_3{c}^2}{6}{q}_i,{\parallel \mathbb{E}[\widehat{G}(\theta )]-\mathrm{\nabla }f(\theta )\parallel }_2\le \frac{M_3{c}^2}{6}{\left({\sum }_{i=1}^d{q}_i^2\right)}^{1\mathrm{/}2}\mathrm{.}$

Assume AC. At a current history $\mathcal{F}$, let $c>0$, let ${\mathrm{\Delta }}_i\mathrm{\ne }0$ almost surely, and use the two-evaluation estimator from Two-evaluation simultaneous-perturbation gradient estimator. Suppose the weighted conditional second moment is bounded: $\mathbb{E}\text{\hspace{0.17em}⁣}\left[(\mathrm{\mid }{Y}^{+}{\mathrm{\mid }}^2+\mathrm{\mid }{Y}^{-}{\mathrm{\mid }}^2){\sum }_{i=1}^d\mathrm{\mid }{\mathrm{\Delta }}_i{\mathrm{\mid }}^{-2}\right|\mathcal{F}]\le B$ almost surely, with deterministic $B<\mathrm{\infty }$. Then $\mathbb{E}[\mathrm{\parallel }\widehat{G}{\mathrm{\parallel }}_2^2\mid \mathcal{F}]\le \frac{B}{2c^2},\mathrm{Var}(\widehat{G}\mid \mathcal{F})\le \frac{B}{2c^2},$ where the vector conditional variance is the sum of coordinate conditional variances as in Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates.

Gradients of scalar functions are Euclidean column vectors, with $Dg(\theta )[v]=⟨\mathrm{\nabla }g(\theta ),v⟩$ under The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$; vector expectations are taken coordinatewise.

Let $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$ be a probability space, let $(E_k,{\mathcal{E}}_k)$ be measurable spaces for $0\le k\le N$, and let each ${\xi }_k:\mathrm{\Omega }\to E_k$ be a measurable random element; write $\xi =({\xi }_0,\dots ,{\xi }_N)$. Let $\mathrm{\Theta }\subseteq {\mathbb{R}}^d$ be open, fix ${\theta }_0\in \mathrm{\Theta }$, and choose an open ball $U$ with ${\theta }_0\in U\subseteq \mathrm{\Theta }$. Let $d,m\ge 1$, let $N\ge 0$ be a finite integer, and let the states lie in ${\mathbb{R}}^m$. The maps are $u_0:\mathrm{\Theta }\times E_0\to {\mathbb{R}}^m$, ${\mathrm{\Psi }}_k:{\mathbb{R}}^m\times \mathrm{\Theta }\times E_{k+1}\to {\mathbb{R}}^m$, ${\mathrm{\ell }}_k:{\mathbb{R}}^m\times \mathrm{\Theta }\to \mathbb{R}$, and $\varphi :{\mathbb{R}}^m\times \mathrm{\Theta }\to \mathbb{R}$. Gradients of scalar functions are columns; $D_u{\mathrm{\Psi }}_k$ is an $m\times m$ Jacobian and $D_{\theta }{\mathrm{\Psi }}_k$ is an $m\times d$ Jacobian. Let $u_0=u_0(\theta ,{\xi }_0),u_{k+1}={\mathrm{\Psi }}_k(u_k,\theta ,{\xi }_{k+1})(0\le k<N)\mathrm{.}$ Assume the displayed maps are measurable for the corresponding product sigma-algebras (Borel on Euclidean factors and ${\mathcal{E}}_k$ on each input factor), and that there is a common measurable null set outside which their sections are continuously differentiable in their state and parameter variables on $U$. Define $F_N(\theta ,\xi ):=\varphi (u_N,\theta )+{\sum }_{k=0}^{N-1}{\mathrm{\ell }}_k(u_k,\theta ),J_N(\theta ):=\mathbb{E}[F_N(\theta ,\xi )]\mathrm{.}$ Assume $F_N(\theta ,\xi )$ is integrable for every $\theta \in U$, and that there is a nonnegative integrable random variable $M$ with $\mathrm{\parallel }{\mathrm{\nabla }}_{\theta }{F}_N(\theta ,\xi ){\mathrm{\parallel }}_2\le M$ for all $\theta \in U$ almost surely, while $\mathbb{E}\mathrm{\parallel }{\mathrm{\nabla }}_{\theta }{F}_N({\theta }_0,\xi ){\mathrm{\parallel }}_2^2<\mathrm{\infty }$. Put $S_0=D_{\theta }{u}_0$, propagate $S_{k+1}=D_u{\mathrm{\Psi }}_k{S}_k+D_{\theta }{\mathrm{\Psi }}_k,$ and define reverse variables by $p_N={\mathrm{\nabla }}_u\varphi (u_N,\theta ),p_k={\mathrm{\nabla }}_u{\mathrm{\ell }}_k(u_k,\theta )+(D_u{\mathrm{\Psi }}_k{)}^{\mathsf{T}}{p}_{k+1}\mathrm{.}$ Then the discrete adjoint integrand ${\mathrm{\Gamma }}_N={\mathrm{\nabla }}_{\theta }\varphi +S_0^{\mathsf{T}}{p}_0+{\sum }_{k=0}^{N-1}({\mathrm{\nabla }}_{\theta }{\mathrm{\ell }}_k+(D_{\theta }{\mathrm{\Psi }}_k{)}^{\mathsf{T}}{p}_{k+1})$ satisfies $\mathrm{\nabla }{J}_N({\theta }_0)=\mathbb{E}[{\mathrm{\Gamma }}_N({\theta }_0,\xi )]$.

For a family of discretizations indexed by $h$, if each discrete objective satisfies the preceding pathwise interchange hypotheses, $\mathbb{E}\mathrm{\parallel }{\mathrm{\Gamma }}_h({\theta }_0)-\mathrm{\Gamma }({\theta }_0){\mathrm{\parallel }}_2\to 0$, and the continuous-limit objective has derivative $\mathrm{\nabla }J({\theta }_0)=\mathbb{E}[\mathrm{\Gamma }({\theta }_0)]$ under the same pathwise interchange conditions, then $\mathrm{\nabla }{J}_h({\theta }_0)\to \mathrm{\nabla }J({\theta }_0)$. This conclusion gives no rate unless a quantitative bound on $\mathbb{E}\mathrm{\parallel }{\mathrm{\Gamma }}_h({\theta }_0)-\mathrm{\Gamma }({\theta }_0){\mathrm{\parallel }}_2$ is also supplied. Euler–Maruyama is the special case ${\mathrm{\Psi }}_k(u,\theta ,\mathrm{\Delta }{W}_k)=u+b(u,\theta )h_k+\sigma (u,\theta )\mathrm{\Delta }{W}_k$, with $\mathrm{\Delta }{W}_k$ the simulated Brownian increment.

All tangent, reverse and adjoint derivatives are evaluated on the common full-probability event where the sample maps are $C^1$. Define ${\mathrm{\Gamma }}_N=0$ on its measurable null complement, and use this version in expectations.