Sunday 6 September 2026

The estimator and its unbiasedness

Write the target as an expectation under the proposal by inserting the likelihood ratio $\varphi (x)/g_{\mu }(x)$: $$p={\int }_a^{\infty }\varphi (x)dx={\int }_a^{\infty }\frac{\varphi (x)}{\varphi (x-\mu )}\varphi (x-\mu )dx={𝔼}_{X~N(\mu ,1)}[w(X)\mathbf{1}\{X\ge a\}].$$

The weight is the ratio of the two Gaussian densities, $$w(x)=\frac{\varphi (x)}{\varphi (x-\mu )}=\exp (-\frac{1}{2}{x}^2+\frac{1}{2}(x-\mu {)}^2)=e^{-\mu x+{\mu }^2/2}.$$

The estimator is $${\widehat{p}}_{\mu }=\frac{1}{n}\sum _{i=1}^{n}w(X_i)\mathbf{1}\{X_i\ge a\},X_i~N(\mu ,1),$$ and $𝔼[{\widehat{p}}_{\mu }]=p$ by the change of measure above, for every $\mu$. Unbiasedness never depends on $\mu$; only the variance does.

The second moment collapses to a shifted tail

The per-sample variance is $M(\mu )-p^2$ with $$M(\mu )={𝔼}_{X~N(\mu ,1)}[w(X{)}^2\mathbf{1}\{X\ge a\}]={\int }_a^{\infty }\frac{\varphi (x{)}^2}{\varphi (x-\mu )}dx.$$

The key algebraic step — the one a candidate typically fumbles — is to complete the square in the integrand rather than fight the integral numerically. With $\varphi (x)=\frac{1}{\sqrt{2\pi }}{e}^{-x^2/2}$, $$\frac{\varphi (x{)}^2}{\varphi (x-\mu )}=\frac{1}{\sqrt{2\pi }}\exp (-x^2+\frac{1}{2}(x-\mu {)}^2).$$

The exponent is $$-x^2+\frac{1}{2}{x}^2-\mu x+\frac{1}{2}{\mu }^2=-\frac{1}{2}{x}^2-\mu x+\frac{1}{2}{\mu }^2=-\frac{1}{2}(x+\mu {)}^2+{\mu }^2.$$

Hence $$\frac{\varphi (x{)}^2}{\varphi (x-\mu )}=e^{{\mu }^2}\varphi (x+\mu ),$$ and integrating from $a$ to $\infty$ gives $$M(\mu )=e^{{\mu }^2}{\int }_a^{\infty }\varphi (x+\mu )dx=e^{{\mu }^2}\overline{\Phi }(a+\mu ).$$

Minimizing $M$ is easiest through $\ln M(\mu )={\mu }^2+\ln \overline{\Phi }(a+\mu )$: $$\frac{d}{d\mu }\ln M(\mu )=2\mu -\frac{\varphi (a+\mu )}{\overline{\Phi }(a+\mu )}=0.$$

So the optimal shift solves $$\boxed{2{\mu }^{\star }=\frac{\varphi (a+{\mu }^{\star })}{\overline{\Phi }(a+{\mu }^{\star })}=h(a+{\mu }^{\star })}$$ where $h$ is the Gaussian hazard rate. Since $M$ is convex in this sense (the hazard rate is increasing, so the derivative crosses zero once), this stationary point is the global minimum.

Solving for $a=3$ and the variance gain

Use the Mills-ratio expansion $h(t)=\varphi (t)/\overline{\Phi }(t)\approx t+1/t-2/t^3$ for large $t$. With $t=a+\mu =3+\mu$, the fixed point $2\mu =h(3+\mu )$ gives, iterating, $${\mu }^{\star }\approx 3.15,t^{\star }=a+{\mu }^{\star }\approx 6.15.$$

Note the heuristic ''shift the proposal mean up to the threshold'' ($\mu \approx a$) is almost right; the exact optimum sits just above $a$ because the tail mass beyond $a$ concentrates slightly past it.

Now evaluate the variances.

• Crude: $\mathrm{V}\mathrm{a}\mathrm{r}=p(1-p)=1.3499\times {10}^{-3}(0.99865)=1.348\times {10}^{-3}.$
• Importance sampling at ${\mu }^{\star }$: with ${\mu }^{\star }=3.15$, $$M({\mu }^{\star })=e^{(3.15{)}^2}\overline{\Phi }(6.15)=e^{9.9225}(3.76\times {10}^{-10})\approx 7.90\times {10}^{-6},$$ $$\mathrm{V}\mathrm{a}\mathrm{r}=M({\mu }^{\star })-p^2=7.90\times {10}^{-6}-1.82\times {10}^{-6}\approx 6.08\times {10}^{-6}.$$

The variance reduction factor is $$\frac{1.348\times {10}^{-3}}{6.08\times {10}^{-6}}\approx 2.2\times {10}^2.$$

Answer. 1. ${\widehat{p}}_{\mu }=\frac{1}{n}{\sum }_i{e}^{-\mu X_i+{\mu }^2/2}\mathbf{1}\{X_i\ge a\}$ with $X_i~N(\mu ,1)$; unbiased for all $\mu$. 2. $M(\mu )=e^{{\mu }^2}\overline{\Phi }(a+\mu )$, and ${\mu }^{\star }$ solves $2{\mu }^{\star }=\varphi (a+{\mu }^{\star })/\overline{\Phi }(a+{\mu }^{\star })$. 3. For $a=3$: ${\mu }^{\star }\approx 3.15$, giving roughly a 220-fold reduction in per-sample variance (equivalently, about $220\times$ fewer draws for the same accuracy).

Note

The zero-variance ideal proposal is the conditional density $g^{\star }(x)=\varphi (x)\mathbf{1}\{x\ge a\}/p$, i.e. the normal truncated to the tail — but it requires knowing $p$ and is awkward to sample, which is exactly why the tractable single-parameter tilt is used. Also worth knowing: antithetic variates would help almost nothing here, because the payoff $\mathbf{1}\{Z\ge 3\}$ is essentially never triggered by both $Z$ and $-Z$; the pairing gives you two zeros nearly always. Rare-event estimation is the textbook case where importance sampling wins and antithetics do not.

(a) The mutual-information bound

Define $F(w,s)=L_D(w)-\frac{1}{n}{\sum }_i\ell (w,z_i)$, so the target is ${\mathbb{E}}_{P_{W,S}}[F(W,S)]$.

The identity that does the work is the Donsker–Varadhan variational formula for relative entropy: for any two probability measures $P\ll \overline{P}$ and any measurable $g$ with ${\mathbb{E}}_{\overline{P}}[e^g]<\infty$, $${\mathbb{E}}_P[g]\le D(P\Vert \overline{P})+\log {\mathbb{E}}_{\overline{P}}\left[e^g\right].$$ Apply it with $P=P_{W,S}$, $\overline{P}=P_W\otimes P_S$, and $g=\lambda F(W,S)$ for $\lambda >0$. Since $D(P_{W,S}\Vert P_W\otimes P_S)=I(W;S)$, $$\lambda {\mathbb{E}}_{P_{W,S}}[F]\le I(W;S)+\log {\mathbb{E}}_{P_W\otimes P_S}\left[e^{\lambda F}\right].$$

The step a candidate misses is that the product measure both centers $F$ and factorizes it. Under $\overline{P}=P_W\otimes P_S$, condition on $W=w$; then $S$ is still i.i.d.\ $D$ and independent of $w$, and $$F(w,S)=-\frac{1}{n}\sum _{i=1}^n(\ell (w,Z_i)-L_D(w))$$ is a centered average of $n$ i.i.d.\ $\sigma$-sub-Gaussian terms. Its MGF factorizes: $${\mathbb{E}}_S\left[e^{\lambda F(w,S)}\right]=\prod _{i=1}^n\mathbb{E}\left[e^{-\frac{\lambda }{n}(\ell (w,Z_i)-L_D(w))}\right]\le \prod _{i=1}^n{e}^{{\lambda }^2{\sigma }^2/(2n^2)}=e^{{\lambda }^2{\sigma }^2/(2n)}.$$ Averaging over $w~P_W$ preserves the bound, so $\log {\mathbb{E}}_{\overline{P}}[e^{\lambda F}]\le {\lambda }^2{\sigma }^2/(2n)$. (In particular ${\mathbb{E}}_{\overline{P}}[F]=0$: under the product law the empirical risk is unbiased for the population risk of an independent hypothesis.) Hence $$\lambda {\mathbb{E}}_{P_{W,S}}[F]\le I(W;S)+\frac{{\lambda }^2{\sigma }^2}{2n},\text{i.e.}{\mathbb{E}}_{P_{W,S}}[F]\le \frac{I(W;S)}{\lambda }+\frac{\lambda {\sigma }^2}{2n}.$$ Minimizing the right side over $\lambda >0$ at ${\lambda }^{\star }=\sqrt{2nI(W;S)/{\sigma }^2}$ gives $\mathbb{E}[F]\le \sqrt{2{\sigma }^{2}I(W;S)/n}$. Repeating with $\lambda <0$ (equivalently applying the argument to $-F$) gives the matching lower bound, so $$|{\mathbb{E}}_{P_{W,S}}[L_D(W)-L_S(W)]|\le \sqrt{\frac{2{\sigma }^2}{n}I(W;S)}.∎$$

(b) Deterministic rules have infinite mutual information

Let $G=\{(f(s),s):s\in {\mathbb{R}}^N\}\subset \mathcal{W}\times {\mathbb{R}}^N$ be the graph. Because $W=f(S)$ deterministically, $P_{W,S}(G)=1$. Under the product law, $$(P_W\otimes P_S)(G)={\int }_{{\mathbb{R}}^N}{P}_W(\{f(s)\})d{P}_S(s)=0,$$ since $P_W$ is atomless, so $P_W(\{w\})=0$ for every point $w$. Thus $P_{W,S}$ assigns full mass to a set of product-measure zero: $P_{W,S}\text{⧸}\ll P_W\otimes P_S$, and by definition of relative entropy $I(W;S)=D(P_{W,S}\Vert P_W\otimes P_S)=+\infty$. The bound of (a) then reads $|\text{gap}|\le \infty$: vacuous, even though for, say, a bounded loss the true gap is $O(1/\sqrt{n})$.

Responsible step: the Donsker–Varadhan inequality itself. It compares $P_{W,S}$ against $P_W\otimes P_S$, and this comparison is infinitely loose precisely when the joint law is mutually singular with the product — i.e.\ when the hypothesis is a deterministic function of continuous data. The moral: mutual information is only an upper bound mechanism; a finite gap forces neither finite $I(W;S)$ nor tightness, which is why one randomizes the algorithm (or passes to conditional-mutual-information/CMI frameworks that stay finite by construction).

(c) The noisy mean estimator

(i) The estimator depends on $S$ only through the sufficient statistic ${\overline{Z}}_n$, and $\xi ⟂S$, so $S\to {\overline{Z}}_n\to W$ is a Markov chain and $W⟂S\mid {\overline{Z}}_n$. Hence $$I(W;S)=I(W;{\overline{Z}}_n)+\underset{=0}{\underbrace{I(W;S\mid {\overline{Z}}_n)}}=I(W;{\overline{Z}}_n).$$ Now ${\overline{Z}}_n~N(\mu ,1/n)$ and $W={\overline{Z}}_n+\xi$ with $\xi ~N(0,{\tau }^2)$ is a scalar additive-Gaussian channel with input variance $1/n$ and noise variance ${\tau }^2$: $$\boxed{I(W;S)=\frac{1}{2}\log (1+\frac{1/n}{{\tau }^2})=\frac{1}{2}\log (1+\frac{1}{n{\tau }^2}).}$$

(ii) Substituting into (a), $$\left|\text{gap}\right|\le \sqrt{\frac{2{\sigma }^2}{n}·\frac{1}{2}\log (1+\frac{1}{n{\tau }^2})}=\sigma \sqrt{\frac{1}{n}\log (1+\frac{1}{n{\tau }^2})}.$$ As $\tau \to 0^{+}$ the argument of the log diverges and the bound $\to \infty$ — exactly the deterministic-ERM pathology of (b): plain $W={\overline{Z}}_n$ is a continuous deterministic function of the data, so $I(W;S)=\infty$.

(iii) With $\sigma =1$ require $\sqrt{\frac{1}{n}\log (1+\frac{1}{n{\tau }^2})}\le \frac{1}{\sqrt{n}}$, i.e. $\log (1+\frac{1}{n{\tau }^2})\le 1$, i.e. $\frac{1}{n{\tau }^2}\le e-1$. The smallest admissible noise is $$\boxed{{\tau }_{min}=\frac{1}{\sqrt{n(e-1)}}\approx \frac{0.763}{\sqrt{n}}.}$$ The required injected noise has standard deviation $\Theta (1/\sqrt{n})$ — the same order as the sampling fluctuation of ${\overline{Z}}_n$ itself (whose s.d.\ is $1/\sqrt{n}$). To certify even a $1/\sqrt{n}$ generalization bound by the information method, you must blur the estimator by an amount comparable to the signal you extracted; here that roughly doubles the estimator's variance. Information-theoretic control literally charges you for the precision with which the output remembers the sample.

Closing notes

• The bound's $\sqrt{I/n}$ shape caps its rate at $1/\sqrt{n}$ even when the true excess gap is a fast $1/n$. For instance the associated linear–quadratic model has an exact gap of order $1/n$ that the sub-Gaussian information bound can never reproduce; recovering fast rates needs the small-KL/quadratic regime of PAC-Bayes (Catoni/Seeger-type bounds), not the sub-Gaussian one.
• A tempting error in (b) is to compute $I=H(W)-H(W\mid S)$ and blithely set $H(W\mid S)=0$; for a continuous $W$ the conditional differential entropy is $-\infty$, which is the same phenomenon (singularity of the joint against the product) seen correctly through the absolute-continuity failure above.
• The Steinke–Zakynthinou conditional-mutual-information framework sidesteps (b) entirely by conditioning on a supersample, forcing the relevant information quantity to lie in $[0,\log 2]$ per example regardless of determinism.