Evaluating the Variance ofLikelihood-Ratio Gradient Estimators
Seiya Tokui 1 2 Issei Sato 2 3
1 Preferred Networks 2 The University of Tokyo 3 RIKENICML 2017 @ Sydney

Task: Gradient estimation for stochastic
computational graph
Want to compute the following gradient:
𝜙𝑥𝑧𝑓Computational Graph∇𝜙 𝔼𝑞𝜙 (𝑧|𝑥) 𝑓(𝑥, 𝑧)
If• No stochasiticity in 𝑧(𝑞 is a delta distribution)→ use backprop• 𝑧 is stochastic(stochastic computational graph)→ need more techniques

2Example: Variational inference in deep
directed graphical models𝑥𝑧1𝑧23

Generative model𝑝𝜃 𝑥, 𝑧 = 𝑝𝜃 𝑥 𝑧1 𝑝𝜃 𝑧1 𝑧2 𝑝𝜃 𝑧2 𝑧3 𝑝𝜃 (𝑧3 )𝑧3𝑝𝜃

Each factor is written by a NN

Approximate posterior
𝑞𝜙 𝑧 𝑥 = 𝑞𝜙 𝑧1 𝑥 𝑞𝜙 𝑧2 𝑧1 𝑞𝜙 (𝑧3 |𝑧2 )Each factor is written by a NN

Graphical Modelsbound)𝑞𝜙 Objective function (variational𝑝𝜃 𝑥, 𝑧
ℒ 𝜙, 𝜃 ≔ 𝔼𝑞𝜙 (𝑧|𝑥) log
𝑞𝜙 𝑧 𝑥 = 𝑓(𝑥, 𝑧)
We want to compute ∇𝜙 ℒ to optimize ℒwith a gradient method.

Overview of unbiased estimators
Likelihood-ratio estimators

Reparameterization trick✓ 𝑧 can be continuous or discrete✓ 𝑓 can be non-continuous✓ Tend to have high variance✓ Many (heuristic) techniques toreduce the variance exist✓ 𝑧 must be continuous✓ 𝑓 must be differentiable✓ Tend to have low variance inpractice (but not guaranteed)

Our finding: when there are 𝑀 random variables, also likelihood-ratio
estimators can be formulated with reparameterization for 𝑀 − 1 variables→ unified framework of gradient estimators

4

A unified framework of gradient estimators

5

Let 𝑧 = (𝑧1 , … , 𝑧𝑀 ) and 𝑞𝜙 𝑧 𝑥 = ς𝑀
𝑖=1 𝑞𝜙𝑖 (𝑧𝑖 |pa 𝑖 ).
The set of parents of 𝒛𝒊

Suppose we have a reparameterization formula:𝑧𝑖 ∼ 𝑞𝜙𝑖 𝑧𝑖 pa𝑖 ⟺ 𝑧𝑖 = 𝑔𝜙𝑖 pa𝑖 , 𝜖𝑖 , 𝜖𝑖 ∼ 𝑝(𝜖𝑖 )Noise variable that generates 𝒛𝒊
Differentiable even if 𝒈 is nonExchange ∇ and 𝔼 partially for each 𝑖 :continuous (⇐ 𝒛𝒊 is discrete)∇𝜙𝑖 𝔼𝑞𝜙 (𝑧|𝑥) 𝑓 𝑥, 𝑧 = ∇𝜙𝑖 𝔼𝜖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖 = 𝔼𝜖∖𝑖 ∇𝜙𝑖 𝔼𝜖𝑖 𝑓(𝑥, 𝑔𝜙 𝑥, 𝜖 )Reparameterization

Local marginalization[Williams, 1992][Kingma & Welling, 2014][Rezende+, 2014][Titsias & Lázaro-Gredilla, 2014][Titsias & Lázaro-Gredilla, 2015]

A unified framework of gradient estimators∇𝜙𝑖 𝔼𝑞𝜙 (𝑧|𝑥) 𝑓 𝑥, 𝑧 = 𝔼𝜖∖𝑖 ∇𝜙𝑖 𝔼𝜖𝑖 𝑓(𝑥, 𝑔𝜙 𝑥, 𝜖 )Local gradient

Each method differs in how to estimate the local gradient.
• Likelihood-ratio estimator: use log derivative trick• Reparameterization estimator: use reparameterization trick• Optimal estimator: exactly (or numerically) compute the innerexpectation

6

Likelihood-ratio estimator under the framework7∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑧 = 𝔼𝜖𝑖 𝑓 𝑥, 𝑧 − 𝑏𝑖 𝑥, 𝜖 ∇𝜙𝑖 log 𝑞𝜙𝑖 𝑧𝑖 pa𝑖 + 𝐶𝑖 𝑥, 𝜖∖𝑖Baseline

Residual

Baseline
Definition
Constant 𝑏𝑖 is a constant of 𝑥 and 𝜖. 𝐶𝑖 = 0.

Running average of sampled 𝑓

Independent 𝑏𝑖 (𝑥, 𝜖∖𝑖 ) is a constant of 𝜖𝑖 . 𝐶𝑖 = 0.

Input-dependent baseline
Local signal [Mnih & Gregor, 2014]

Linear𝑏𝑖 (𝑥, 𝜖) is linear against 𝑧𝑖 .

Fully𝑏 (𝑥, 𝜖) may be nonlinear against 𝑧𝑖 .
informed 𝑖

ExampleMuProp [Gu+, 2016]

The optimal estimator (general)

8

Reparameterization estimator under the framework
Apply the reparameterization trick to the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= 𝔼𝜖𝑖 ∇𝜙𝑖 𝑓(𝑥, 𝑔𝜙 𝑥, 𝜖 )• If 𝑔𝜙 is not continuous, the above equation does not hold(in other words, Monte Carlo estimation of the right handside has infinite variance).
• Otherwise, the reparameterization trick can be used.

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)

𝑧𝑖

9

10

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)𝑧𝑖
All the 𝜖𝑖 ’s are fixed.

0

1

1

1

1

0

0

0

1

11

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)𝑧𝑖
All the 𝜖𝑖 ’s are fixed.

0

1

1

1

1

0

00

1

12

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)𝑧𝑖
All the 𝜖𝑖 ’s are fixed.

10

1

1

1

10

10

13

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)𝑧𝑖
All the 𝜖𝑖 ’s are fixed.

01

1

1

1

0

00

1

14

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)𝑧𝑖
All the 𝜖𝑖 ’s are fixed.

0100000

10

15

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)𝑧𝑖
All the 𝜖𝑖 ’s are fixed.

01

1

1

1

0

0

0

1

16

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)𝑧𝑖
All the 𝜖𝑖 ’s are fixed.

00

0

1

1

1

1

11

17

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)𝑧𝑖
All the 𝜖𝑖 ’s are fixed.

01

1

1

1

000

1

18

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)𝑧𝑖
All the 𝜖𝑖 ’s are fixed.

00

1

1

1

000

1

19

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)𝑧𝑖
All the 𝜖𝑖 ’s are fixed.

01

1

1

1

0

00

1

20

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)𝑧𝑖
All the 𝜖𝑖 ’s are fixed.

010

10

1001

21

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)𝑧𝑖
All the 𝜖𝑖 ’s are fixed.

01

1

1

1

0

00

1

22

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)𝑧𝑖
All the 𝜖𝑖 ’s are fixed.

01

1

1

1

1

0

10

23

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)𝑧𝑖
All the 𝜖𝑖 ’s are fixed.

01

1

1

1

0

00

1

24

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)𝑧𝑖
All the 𝜖𝑖 ’s are fixed.

010

1

10001

25

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)𝑧𝑖
All the 𝜖𝑖 ’s are fixed.

01

1

1

1

0

00

1

26

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)𝑧𝑖
All the 𝜖𝑖 ’s are fixed.

01

1

1

1

1

0

0

1

27

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)𝑧𝑖
All the 𝜖𝑖 ’s are fixed.

01

1

1

1

0

00

1

28

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)𝑧𝑖
All the 𝜖𝑖 ’s are fixed.

01

1

1

1

0

0

00

29

Optimal estimator under the framework(slow for use in every iteration, yet useful for evaluation purpose)

Exactly (or numerically) compute the local gradient:∇𝜙𝑖 𝔼𝜖𝑖 𝑓 𝑥, 𝑔𝜙 𝑥, 𝜖

= ෍ 𝑓 𝑥, 𝑧 ∇𝜙𝑖 𝑞𝜙𝑖 𝑧𝑖 pa𝑖Implementation (Bernoulli case):••

Sample 𝜖 and compute 𝑧 = 𝑔𝜙 (𝑥, 𝜖)and 𝑓(𝑥, 𝑧)
For each 𝑖:• Flip 𝑧𝑖 and resample
descendants of 𝑧𝑖 with fixed 𝜖∖𝑖• Recompute 𝑓(𝑥, 𝑧)• Compute the local gradient(the above equation)𝑧𝑖
All the 𝜖𝑖 ’s are fixed.

011

1

10001

30
Evaluating the variance of estimators within the framework
Theorem 1 The optimal estimator achieves the minimum
variance among all estimators within the framework.
(∵ the property of Rao-Blackwellization)
Theorem 2 When 𝑧𝑖 is a Bernoulli variable, there is anindependent baseline 𝑏𝑖⋆ with which the likelihood-ratio
estimator achieves the optimal variance.
(I.e., LR with independent baseline can be the optimal estimator.)

Experiment:variational learning of sigmoid belief networks
𝑧1𝑧2𝑧3𝑝𝜃𝑞𝜙• Datasets: MNIST and Omniglot• 784-dimensional binary (0/1) inputs• Each latent variable follows a
Bernoulli distribution with the logit
given by the net input (i.e., sigmoidBernoulli unit)• In the optimal estimator, the Bernoulli
unit is reparameterized by 0/1
thresholding at 𝜖 ∼ 𝑈(0, 1).

31

Experimental results:
variational learning of sigmoid belief nets

32

Conclusion• We proposed a framework of gradient estimators forstochastic computational graph by reparameterization andlocal marginalization.
• We formulated a hierarchy of baseline techniques forlikelihood-ratio estimators and showed the relationshipbetween this hierarchy and the optimal estimator.
• The experimental results show that the variance of gradientestimation for binary discrete variables is approaching to theoptimum with recent advancements, yet a non-negligible gap
still exists, indicating the possibility of further improvements.

33

(end)

34

Appendix:
results with shallow networks

35Appendix:
training curve of deep networks

36Appendix:
training curve of shallow networks

37Appendix: final performance on test sets

• VB stands for variational bound• LL stands for log likelihood, which is approximated by“Monte Carlo objective” using sample of size 50,00038