definition theorem example program
Many objectives in machine learning are expected values of random processes: an expected reward over simulated runs, a loss over random minibatches, an ELBO over samples of a variational family. Their gradients are hard to get right. Running ordinary automatic differentiation through a sampler is wrong whenever the parameter changes the probabilities of the random choices and not only the values computed from them. Lew, Huot, Staton & Mansinghka’s ADEV is a source-to-source transformation of probabilistic programs that is provably correct. It turns a program whose expected return value is into a program whose expected return value is ; running the new program gives unbiased Monte Carlo estimates of the gradient.
Sources: Lew, Huot, Staton & Mansinghka arXiv:2212.06386 (notes) Figure 2, Definitions 2.1–2.4, 3.1, 3.2, 3.5, 4.1, Lemma 4.1, Theorems 2.2, 3.2, 4.3, 5.3, 6.1, Corollary 7.1, Appendix D; Huot, Staton & Vákár arXiv:2001.02209 (notes) Theorem 1.
The failure, in one coin
The paper’s Figure 2:
AD of the deterministic parts only differentiates the branch, , and averages: . This is wrong by , the effect of on which branch runs. The correct derivative adds the change of the branch probability, weighted by the value: in the else branch, with . This is the score function (REINFORCE) term, the same score as in the Fisher Information Metric.
The idea: forward-mode AD, extended at the primitives
- Dual numbers. ADEV extends forward-mode AD by dual numbers. Its correctness proof follows Huot, Staton & Vákár: a logical relation between a term’s meaning and its dual-number translation (ADEV Definitions 2.1–2.4, Lemma 2.1, Theorem 2.2). See Diffeological Space.
- Estimators as values. The real line is replaced by , probability measures on read as unbiased estimators of their means (Definition 3.1). An unbiased derivative of is a with (Definition 3.2).
- Probability via continuations. A probabilistic program of type is interpreted in a submonad of the Continuation Monad, (following Vákár et al. 2019, as the paper says). A sampling primitive is then higher-order: it receives the rest of the program, its continuation, and averages it.
- Derivatives at the primitives. Each probabilistic primitive carries a built-in derivative strategy that accounts for how moves the distribution (Definition 4.1, Lemma 4.1). The strategies are: exact enumeration, REINFORCE (score function), and reparametrisation for continuous distributions. Composition is ordinary forward-mode AD, so the method is modular. The strategy is chosen per primitive, which makes the derivative intensional (Definition 3.5): equal programs written with different primitives get different, equally correct, estimators.
Theorem 3.2, 4.3, 5.3, 6.1 (correctness, in growing languages). For a closed term of the language, the ADEV translation is an unbiased derivative of . In the continuous and full languages this holds under a local domination condition. Corollary 7.1 combines them for the full language.
The prototype is a few dozen lines of Haskell (probcomp/adev). Appendix D recasts the logical-relations proof categorically.
Relation to statistical games
The local gradient rule of a parameterized Statistical Game (AutoBayes Definition 29) drops two terms (Remark 30): where moves the pushforward prior, and where the downstream parameter moves the sampling distribution of the inversion. The second is exactly what naive AD misses in the coin above, and what ADEV’s primitives supply as a score-function or reparametrisation term. ADEV is a compositional way to keep those terms, at the price of variance.
Docs: Julia manual: functions as values — programs take their continuation as an argument.
# A tiny ADEV: dual numbers + probabilistic primitives that see their continuation.
using Random; Random.seed!(1)
struct D <: Number; v::Float64; d::Float64; end # (value, tangent)
D(x::Real) = D(x, 0.0)
Base.:+(a::D, b::D) = D(a.v + b.v, a.d + b.d)
Base.:-(a::D, b::D) = D(a.v - b.v, a.d - b.d)
Base.:-(a::D) = D(-a.v, -a.d)
Base.:*(a::D, b::D) = D(a.v * b.v, a.d * b.v + a.v * b.d)
Base.:/(a::D, b::D) = D(a.v / b.v, (a.d * b.v - a.v * b.d) / b.v^2)
Base.promote_rule(::Type{D}, ::Type{<:Real}) = D
Base.convert(::Type{D}, x::Real) = D(x)
# a program of type Bool, in continuation style: (Bool → D) → D
flip_enum(θ::D) = k -> θ * k(true) + (1 - θ) * k(false) # exact enumeration
function flip_reinforce(θ::D) # one sample + score term
k -> begin
b = rand() < θ.v
l = k(b)
score = b ? θ.d / θ.v : -θ.d / (1 - θ.v) # d/dθ log p(b)
D(l.v, l.d + l.v * score)
end
end
# Figure 2: if flip(θ) then 0 else −θ/2; L(θ) = (θ² − θ)/2, L′(θ) = θ − 1/2
prog(flip) = θ -> flip(θ)(b -> b ? D(0.0) : -θ / 2)
θ = 0.3
prog(flip_enum)(D(θ, 1.0)).d ≈ θ - 0.5 # true: exact
est = sum(prog(flip_reinforce)(D(θ, 1.0)).d for _ in 1:400_000) / 400_000
isapprox(est, θ - 0.5; atol = 0.01) # true: unbiased
naive = θ * 0 + (1 - θ) * (-0.5) # AD of the branches only
isapprox(naive, θ - 0.5; atol = 0.01) # false: off by θ/2import Mathlib
/-- ADEV's Figure 2, as an expectation over the coin: `θ·0 + (1-θ)·(-θ/2)`. -/
noncomputable def L (θ : ℝ) : ℝ := θ * 0 + (1 - θ) * (-(θ / 2))
/-- The correct derivative is `θ - 1/2` ... -/
theorem hasDerivAt_L (θ : ℝ) : HasDerivAt L (θ - 1 / 2) θ := by
have h := ((hasDerivAt_pow 2 θ).sub (hasDerivAt_id θ)).div_const 2
have hL : L = fun t => (t ^ 2 - id t) / 2 := by
funext t; simp only [L, id]; ring
rw [hL]
convert h using 1
simp
ring
/-- ... while differentiating only the branches, `(1-θ)·(-1/2)`, misses `θ/2`. -/
theorem naive_wrong (θ : ℝ) : (θ - 1 / 2) - (1 - θ) * (-(1 / 2)) = θ / 2 := by ring-- ADEV's coin with dual numbers and a continuation-passing flip (exact enumeration)
data D = D Double Double deriving Show -- (value, tangent)
addD, mulD :: D -> D -> D
addD (D a a') (D b b') = D (a + b) (a' + b')
mulD (D a a') (D b b') = D (a * b) (a' * b + a * b')
constD :: Double -> D
constD x = D x 0
flipEnum :: D -> (Bool -> D) -> D -- E_{b ~ flip θ}[k b], differentiated
flipEnum th k = addD (mulD th (k True)) (mulD (addD (constD 1) (mulD (constD (-1)) th)) (k False))
prog :: D -> D -- if flip(θ) then 0 else −θ/2
prog th = flipEnum th (\b -> if b then constD 0 else mulD (constD (-0.5)) th)
main :: IO ()
main = do
let theta = 0.3
D _ d = prog (D theta 1)
print (d, theta - 0.5) -- equal: L′(θ) = θ − 1/2
print ((1 - theta) * (-0.5)) -- the naive answer, off by θ/2