In the proof of Theorem 6.5 from the book by Devroye et al., how is the last inequality derived? $$ \begin{aligned} \mathbb{E}\left\{|\eta(X)-1/2|\mathbf{I}_{\{g(X)\ne g^*(X)\}}\right\} &\leq \mathbb{E}\left\{\mathbf{I}_{\{\eta(X)\ne1/2\}}|\eta(X)-\tilde\eta(X)|\mathbf{I}_{\{g(X)\ne g^*(X)\}}\right\}\\ &= \mathbb{E}\left\{|\eta(X)-\tilde\eta(X)|\mathbf{I}_{\{g(X)\ne g^*(X)\}}\mathbf{I}_{\{|\eta(X)-1/2|\leq\epsilon\}}\mathbf{I}_{\{\eta(X)\ne1/2\}}\right\}\\ &+ \mathbb{E}\left\{|\eta(X)-\tilde\eta(X)|\mathbf{I}_{\{g(X)\ne g^*(X)\}}\mathbf{I}_{\{|\eta(X)-1/2|>\epsilon\}}\right\}\\ &\leq \sqrt{\mathbb{E}\left\{(\tilde\eta(X) - \eta(X))^2\right\}}\\ &\times \Bigg(\sqrt{\mathbb{P}\left\{|\eta(X)-1/2|\leq\epsilon,\eta(X)\ne1/2\right\}}\\ &+\sqrt{\mathbb{P}\left\{g(X)\ne g^*(X),|\eta(X)-1/2|>\epsilon\right\}}\Bigg) \end{aligned} $$ Note that $\eta(x) = \mathbb{E}\{Y|X=x\}$ is the regression function, $\tilde\eta(x)$ is an approximation of $\eta(x)$, $g^*(x)$ is the Bayes classifier $$ g^*(x) = \begin{cases} 0 & \text{if } \eta(x)\leq\dfrac{1}{2} \\ 1 & \text{otherwise} \end{cases}$$ and finally, $g(x)$ is defined like $g^*(x)$ with $\tilde\eta(x)$ replacing $\eta(x)$. $\epsilon>0$ is fixed. $\mathbf{I}_A$ is the indicator function of the set $A$.


1 Answer 1


It appears as the standard method of proof that $(\mathbb{E}X)^2 \leq \mathbb{E}X^2$, so $\mathbb{E}X \leq \sqrt{\mathbb{E}X^2}$. That's how all those square roots get there in the last three lines. C-S is hidden in there, admittedly, and you have to rearrange the $\mathbb{E}\dots \textbf{I}_{stuff}$ into probabilities, but that's the core of it.

  • $\begingroup$ The Wikipedia entry for C-S in probability theory seems to have what is used in the proof above: $(\mathbb{E}XY)^2\leq\mathbb{E}X^2\mathbb{E}Y^2$ or $\mathbb{E}XY\leq\sqrt{\mathbb{E}X^2}\sqrt{\mathbb{E}Y^2}$ $\endgroup$
    – Pardis
    May 1, 2012 at 5:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.