$x_i$ is i.i.d random variables with mean $p$. $v_1 = \frac{1}{n}\sum_{i=1}^n{x_i}$, $v_2 = \frac{1}{n}\sum_{i=n+1}^{2n}{x_i}$.Then $\frac{1}{2} \Pr[|v_1-p| \geq 2 \epsilon] \leq \Pr[|v_1-v_2| \geq \epsilon]$ is a lemma to prove VC bound in statistical learning. However, I feel hard to prove it. Any hints?
How to prove the double sample trick inequality $\frac{1}{2} \Pr[|v_1-p| \geq 2 \epsilon] \leq \Pr[|v_1-v_2| \geq \epsilon]$?
-
0@ByronSchmuland,excuse me, $v_2 = \sum_{i=n+1}^{2n}{x_i}$ – 2012-10-04
1 Answers
The orignal problem is a lemma to prove
\begin{equation} \frac{1}{2} \Pr[\sup\limits_{\phi \in \Phi}{|\mu_1(\phi)-E[\phi(z)]|} \geq 2\epsilon] \leq \Pr[\sup\limits_{\phi \in \Phi}{|\mu_1(\phi)-\mu_2(\phi)|} \geq \epsilon] \end{equation}
where $\mu_1 = \frac{1}{n}\sum\limits_{i=1}^{n}{z_i}, \mu_2 = \frac{1}{n}\sum\limits_{i=n+1}^{2n}{z_i}$. And also $n \geq \frac{\ln(2)}{\epsilon^2}$.
Now we directly prove the general theorem. The prove of the lemma can be adapted from this proof in a straight-forward way.
Fix $z_1,z_2,...,z_{2n}$. Consider $\phi^*$
\begin{equation} \phi^* = \arg\sup_{\phi \in \Phi}{|\mu_1-E[\phi]|} \end{equation}
We have relationship
\begin{equation} \begin{array}{ll} &I[|\mu_1(\phi^*)-\mu_2(\phi^*)| \geq \epsilon|] \\ \geq & I[|\mu_1(\phi^*)-E[\phi^*]| \geq 2\epsilon] \land I[|\mu_2(\phi^*)-E[\phi^*]| \leq \epsilon]] \\ =& I[|\mu_1(\phi^*)-E[\phi^*]| \geq 2\epsilon]I[|\mu_2(\phi^*)-E[\phi^*]| \leq \epsilon]] \end{array} \end{equation}
Taking expectation on both sides,
\begin{equation} \begin{array}{ll} & \Pr[\sup\limits_{\phi \in \Phi}{|\mu_1(\phi)-E[\phi(z)]|} \geq 2\epsilon] \Pr[|\mu_2(\phi^*)-E[\phi(z)]| \leq \epsilon] \\ \leq & \Pr[|\mu_1(\phi^*)-\mu_2(\phi^*)| \geq \epsilon] \\ \leq & \Pr[\sup\limits_{\phi \in \Phi}{|\mu_1-\mu_2|} \geq \epsilon] \end{array} \end{equation}
According to Chernoff Bound and the condition that $n \geq \frac{\ln(2)}{\epsilon^2}$,
\begin{equation} \Pr[|\mu_2(\phi^*)-E[\phi^*(z)]| \leq \epsilon] \geq 1-2e^{-2n\epsilon^2} \geq \frac{1}{2} \end{equation}
Now we conclude that
\begin{equation} \frac{1}{2} \Pr[\sup\limits_{\phi \in \Phi}{|\mu_1(\phi)-E[\phi(z)]|} \geq 2\epsilon] \leq \Pr[\sup\limits_{\phi \in \Phi}{|\mu_1(\phi)-\mu_2(\phi)|} \geq \epsilon] \end{equation}