Convergence Rates and Estimator Selection

Summary

The variational EIG estimators converge at $\mathcal{O}(T^{-1/2})$ in total cost $T=\mathcal{O}(N+K)$ — matching ordinary Monte Carlo and beating NMC’s $\mathcal{O}(T^{-1/3})$ — when the variational family contains the target. The error decomposes into MC variance (term I, $\propto N^{-1/2}$), optimization gap (term II, $\propto K^{-1/2}$), and an irreducible family-misspecification bias (term III). This note states the convergence theorem, summarizes the empirical bias²/variance comparison, and gives the practical rules for choosing among the four estimators.

Overview

Foster 2019 §4 breaks the total error of a variational EIG estimator $\hat{\mu }(d,{\varphi }_K)$ into three terms via the triangle inequality, where $\mathcal{B}(d,\varphi )$ is the bound (e.g. ${\mathcal{L}}_{\text{post}}$, ${\mathcal{U}}_{\text{marg}}$, ${\mathcal{U}}_{\text{VNMC}}$) and ${\varphi }^{\text{*}}$ its optimal parameters:

$$\underset{\text{total error}}{\underbrace{\Vert \hat{\mu }(d,{\varphi }_K)-\mathrm{EIG}(d){\Vert }_2}}\le \underset{\text{I: MC variance}}{\underbrace{\Vert \hat{\mu }(d,{\varphi }_K)-\mathcal{B}(d,{\varphi }_K){\Vert }_2}}+\underset{\text{II: optimization}}{\underbrace{\Vert \mathcal{B}(d,{\varphi }_K)-\mathcal{B}(d,{\varphi }^{\text{*}}){\Vert }_2}}+\underset{\text{III: family gap}}{\underbrace{|\mathcal{B}(d,{\varphi }^{\text{*}})-\mathrm{EIG}(d)|}}.$$

Term I shrinks as $N^{-1/2}$ (LLN); term II shrinks as $K^{-1/2}$ (stochastic optimization); term III is a constant removable only by enlarging the variational family (or, for VNMC, by increasing $L$).

Main Content

Theorem 1 — $\mathcal{O}(T^{-1/2})$ convergence (Foster 2019, §4)

Let $\mathcal{X}$ be a measurable space, $\Phi$ a convex subset of a finite-dimensional inner-product space, $X_1,X_2,\dots \stackrel{\text{i.i.d.}}{\sim }\mathcal{X}$, and $f:\mathcal{X}\times \Phi \to \mathbb{R}$ measurable. For $\mu (\varphi ):=\mathbb{E}[f(X_1,\varphi )]$ and ${\hat{\mu }}_N(\varphi ):=\frac{1}{N}{\sum }_{n}f(X_n,\varphi )$, if ${\sup }_{\varphi \in \Phi }\Vert f(X_1,\varphi ){\Vert }_2<\infty$ then ${\sup }_{\varphi }\Vert {\hat{\mu }}_N(\varphi )-\mu (\varphi ){\Vert }_2=\mathcal{O}(N^{-1/2})$. If additionally ${\varphi }^{\text{*}}$ is the unique minimizer and (Assumption 1) holds, then after $K$ steps of Polyak–Ruppert-averaged SGD, $\Vert \mu ({\varphi }_K)-\mu ({\varphi }^{\text{*}}){\Vert }_2=\mathcal{O}(K^{-1/2})$, so

$$\Vert {\hat{\mu }}_N({\varphi }_K)-\mu ({\varphi }^{\text{*}}){\Vert }_2=\mathcal{O}(N^{-1/2}+K^{-1/2})=\mathcal{O}(T^{-1/2})\text{if }N\propto K.$$

Applies directly to ${\hat{\mu }}_{\text{marg}}$, $-{\hat{\mu }}_{\text{post}}$, and ${\hat{\mu }}_{\text{VNMC}}$ (with $M=L$); via Lemma 2 to ${\hat{\mu }}_{m+\ell }$. Total cost $T=\mathcal{O}(N+K)$, versus NMC’s $T=\mathcal{O}(NM)$.

VNMC asymptotic debiasing (Foster 2019, §4)

Because ${\mathcal{U}}_{\text{VNMC}}(d,L)\to \mathrm{EIG}(d)$ as $L\to \infty$, term III can be driven to zero without enlarging the family. Train $\varphi$ with fixed $L$ at rate $\mathcal{O}(K^{-1/2})$ until the family gap dominates, then increase $N,M$ with $M\propto \sqrt{N}$ so ${\hat{\mu }}_{\text{VNMC}}$ converges at $\mathcal{O}((NM{)}^{-1/3})$. Total cost $T=\mathcal{O}(KL+NM)$: a fast variational stage plus a slower NMC refinement.

Empirical comparison (Foster 2019, Table 2)

Bias² and variance over 5 runs on four benchmarks (lower MSE in bold):

Estimator	A/B test	Preference	Mixed effects	Extrapolation
${\hat{\mu }}_{\text{post}}$	good	good	—	best var
${\hat{\mu }}_{\text{marg}}$	—	best	—	—
${\hat{\mu }}_{\text{VNMC}}$	good	good	—	—
${\hat{\mu }}_{m+\ell }$	—	—	best	best
NMC (baseline)	poor	poor	—	—
Laplace (baseline)	best (exact)	—	—	—

Takeaways: Laplace wins only on the Gaussian A/B model where it is exact; all variational estimators outperform NMC; the implicit estimators (${\hat{\mu }}_{m+\ell }$) win on the implicit-likelihood problems.

Estimator-selection rules (Foster 2019 §5, Table 1)

1. Dimension. ${\hat{\mu }}_{\text{marg}}$ and ${\hat{\mu }}_{m+\ell }$ approximate a distribution over $y$ — prefer them when $\dim (y)\ll \dim (\theta )$. ${\hat{\mu }}_{\text{post}}$ and ${\hat{\mu }}_{\text{VNMC}}$ approximate a distribution over $\theta$ — prefer when $\dim (\theta )\ll \dim (y)$.
2. Explicit vs implicit likelihood. ${\hat{\mu }}_{\text{marg}}$ and ${\hat{\mu }}_{\text{VNMC}}$ require an explicit likelihood; ${\hat{\mu }}_{\text{post}}$ and ${\hat{\mu }}_{m+\ell }$ do not. With an explicit likelihood, prefer ${\hat{\mu }}_{m+\ell }$ over ${\hat{\mu }}_{\text{marg}}$ (use the known likelihood).
3. Consistency vs speed. ${\hat{\mu }}_{\text{VNMC}}$ is the only one guaranteed to converge to the true EIG even when the variational family is wrong — prefer it when compute is not constrained; prefer the others when it is.
4. Bounds. Pair a lower (${\hat{\mu }}_{\text{post}}$) and an upper (${\hat{\mu }}_{\text{marg}}$/${\hat{\mu }}_{\text{VNMC}}$) bound to sandwich the true EIG of competing designs.

Examples

Optimal budget split (Foster 2019, Fig. 1d)

Fixing total budget $T=N+K$ and sweeping the ratio $K/T$, RMSE is minimized for $K/T$ between roughly 0.5 and 0.9 — i.e. spend a majority of the budget on variational optimization, the rest on the final MC estimate. Setting $N\propto K$ recovers the theoretical $\mathcal{O}(T^{-1/2})$ rate (Fig. 1c).

Connections

• Quantifies the payoff over NMC: $\mathcal{O}(T^{-1/2})$ vs $\mathcal{O}(T^{-1/3})$.
• Selection rules are referenced throughout Variational BOED - Overview and inherited by Foster 2020, which adds the design gradient.
• Strong assumptions (Assumption 1 for SGD convergence); in practice $\varphi$ converges to a local optimum ${\varphi }^{†}$, adding $|\mathcal{B}(d,{\varphi }^{†})-\mathcal{B}(d,{\varphi }^{\text{*}})|$ to term III.

See Also

• Variational Posterior Estimator (Barber-Agakov) · Variational Marginal Estimator · Variational NMC Estimator · Implicit Likelihood Estimator — the four estimators
• Unified SGD BOED - Overview — the next step: differentiate the bound in the design too