Upper bound using Bayes risk Bayes' risk is $L^*=0$ for a classification problem. $g_n(x)$ is a classification rule (plug-in) such that $g_n=0$ is $\eta_n(x)\leq 1/2$ and $g_n=1$ otherwise. The function $\eta$ is given by $\eta(x)=\mathbb{E}(Y|X=x)$. Then $\mathbb{P}(g_n(X)\neq Y)\leq 4\mathbb{E}((\eta_n(X)-\eta(X))^2)$
Any hints on how to solve this problem? I see that if $\eta_n\leq 1/2$ then it reduces to show that $\mathbb{P}(0\neq Y)\leq 4\mathbb{E}((\eta_n(X)-\eta(X))^2)$, but how do I get the bayesian risk involved. The right-hand of the inequality looks similar like the bayesian risk for the quadratic loss, but I can't see a way to use it - if it is related to the problem.
 A: First, denote by $g(x) = \mathbb{1}_{\eta(x) > 1/2}$ the Bayes optimal classifier, hence 
$$P(g_n(X) \neq Y) - P(g(X) \neq Y) = L(g_n) - L^* = 2\mathbb{E}|\eta(X) - 1/2|\mathbb{1}_{g_n(X) \neq g(X)},$$
this identity hold for any classifier $g_n$, in particular for plug-in classifier. Now let's notice that when $g_n(x) \neq g(x)$ it holds that $|\eta(x) - 1/2| \leq |\eta(x) - \eta_n(x)|$. Indeed, when $g_n(x) \neq g(x)$, we know that $\eta(x)$ and $\eta_n(x)$ are on different sides of $1/2$ (that's how we defined our plug-in rule). Therefore we continue as:
$$L(g_n) - L^* \leq  2\mathbb{E}|\eta(X) - \eta_n(x)|\mathbb{1}_{g_n(X) \neq g(X)}.$$
Seems, that we are on the right track. Let's for a moment assume that we have some additional knowledge that $|\eta(X) - 1/2| \geq \delta$ almost surely. Knowing this we would immediately deduce that 
$$L(g_n) - L^* \leq  2\mathbb{E}|\eta(X) - \eta_n(x)|\mathbb{1}_{g_n(X) \neq g(X)} \leq 2\mathbb{E}|\eta(X) - \eta_n(x)|\mathbb{1}_{|\eta(X) - \eta_n(X)| \geq \delta},$$
indeed, just notice that $\mathbb{1}_{g_n(X) \neq g(X)} \leq \mathbb{1}_{|\eta(X) - \eta_n(X)| \geq \delta}$.
Well, we are almost done here! Hölder's inequality gives us for $1/p + 1/q = 1$:
$$2\mathbb{E}|\eta(X) - \eta_n(x)|\mathbb{1}_{|\eta(X) - \eta_n(X)| \geq \delta} \leq 2\big(\mathbb{E}|\eta(X) - \eta_n(x)|^p\big)^{1/p}\big(\mathbb{E}\mathbb{1}_{|\eta(X) - \eta_n(X)| \geq \delta}\big)^{1/q}
=2\big(\mathbb{E}|\eta(X) - \eta_n(x)|^p\big)^{1/p}\big(P(|\eta(X) - \eta_n(X)| \geq \delta)\big)^{1/q},$$
here comes Markov's inequality! 
$$2\big(\mathbb{E}|\eta(X) - \eta_n(x)|^p\big)^{1/p}\big(P(|\eta(X) - \eta_n(X)| \geq \delta)\big)^{1/q} \leq 2\big(\mathbb{E}|\eta(X) - \eta_n(x)|^p\big)^{1/p}\Big(\frac{\mathbb{E}|\eta(X) - \eta_n(x)|^p}{\delta^p}\Big)^{1/q} = \frac{2\mathbb{E}|\eta(X) - \eta_n(x)|^p}{\delta^{p - 1}}.$$
This is pretty neat already, but we didn't use the fact that $L^* = 0$, let it be an exercise for you to show that if $L^* = 0$ then $\delta = 1/2$.
We conclude by setting $p = 2$ and $\delta = 1/2$.
