$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?
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
|
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} |
|||
|
|
|
$$|v_1 - p| = |(v_1 - v_2) + (v_2 - p)| \leq |v_1 - v_2| + |v_2 - p|$$ $$P(|v_1 - p| \geq 2\epsilon) \leq P(|v_1 - v_2| + |v_2 - p| \geq 2\epsilon) \leq P(|v_1 - v_2| \geq \epsilon) + P(|v_2 - p| \geq \epsilon)$$ Therefore, $$P(|v_1 - p| \geq 2\epsilon) \leq P(|v_1 - v_2| \geq \epsilon) + P(|v_2 - p| \geq \epsilon) \leq P(|v_1 - v_2| \geq \epsilon) + \frac{1}{2}P(|v_1 - p| \geq 2\epsilon)$$ Q.E.D I am leaving it to you to write in arguments that justify each step. They are not particularly hard but this is a very simple and a powerful trick in learning theory and if you plan to stick with it, you will see this occurring in different places in different forms. So, the arguments are good to realize and understand by oneself. |
|||||||||
|
