I have a concern about the "Basic Lemma" which Valdimir Vapnik states and proves in his 1998 book *Statistical Learning Theory* (ch. 14.3, pp. 574–76): It seems like a certain coefficient should have been 2 instead of 1. I'm hoping I'm just wrong, but I'd appreciate any comments or clarifications.


First, some context:


Suppose a sample space $(X,\mu)$ is given, and that we have selected a system $S$ of events $A\subseteq X$.


We can then define various real-valued functions over $S$. For example, the probability measure $\mu$ maps an event in $S$ into its probability; and given a fixed data set, we can also define a frequency function $f$ which maps an event into its frequency in the data set.


This space of functions is equipped with a distance measure:


$$||s-t|| = \sup\_{A\in S} |s(A) - t(A)|.$$


This distance measure respects the triangle inequality, a property that it essentially inherits from the usual distance measure $|x-y|$ on the real number line.


Then, the critical issue:


Suppose that three independent and equally large data sets are drawn from $X$; we can then define the three frequency functions $f$, $f\_1$, and $f\_2$ corresponding to these data sets.


If we fix $A$ but let the data sets be chosen randomly, the numbers $f(A)$, $f\_1(A)$, and $f\_2(A)$ are random variables. The probability $\mu(A)$ is deterministic.


The "Basic Lemma" (p. 574) now states that


$$\Pr\left(||f\_1 - f\_2|| > \varepsilon\right)
\;\leq\;
\Pr\left(||f - \mu|| >\frac{\varepsilon}{2}\right) - \Pr\left(||f - \mu|| >\frac{\varepsilon}{2}\right)^2.$$


Vapnik proves this (p. 576) by noting that the two frequencies $f\_1$ and $f\_2$ can only differ by $\varepsilon$ from each other if at least one of them differs by $\varepsilon/2$ from $\mu$. (Otherwise a detour over $\mu$ would reduce the distance between $f\_1$ and $f\_2$, violating the triangle inequality.)


But the probability of a proposition is smaller than the probability of its logical consequences, so


$$\Pr\left(||f\_1 - f\_2|| > \varepsilon\right)
\;\leq\;
\Pr\left(
 ||f\_1 - \mu|| > \frac{\varepsilon}{2}
 \;\textrm{ or }\;
 ||f\_2 - \mu|| >\frac{\varepsilon}{2}.
\right)$$


Since $f\_1$ and $f\_2$ are independent, and since they are both equal to $f$ in distribution, we can reduce this to


$$\Pr\left(||f\_1 - f\_2|| > \varepsilon\right)
\;\leq\;
1 -
\left(1 - 
\Pr\left(
 ||f - \mu|| > \frac{\varepsilon}{2}
\right)
\right)^2.$$


He then states without further comment that this proves the inequality (p. 576).


This seems wrong.


By expanding, $1 - (1 - a)^2 = 2a - a^2$; and $a - a^2$ is a tighter bound than $2a - a^2$, so we can't just decrease the coefficient.


So where does his right-hand side come from? It seems like the inequality should in fact have read


$$\Pr\left(||f\_1 - f\_2|| > \varepsilon\right)
\;\leq\;
2\Pr\left(||f - \mu|| >\frac{\varepsilon}{2}\right) - \Pr\left(||f - \mu|| >\frac{\varepsilon}{2}\right)^2.$$


Or what? Does anybody have a thought on this?



Is there a mistake in Vapnik's "Basic Lemma"?
You're right, it seems.
Suppose


1. $X=\{1, -1\}$;
2. $\mu(\{1\})=\mu(\{-1\})=1/2$;
3. $S$ is the power set of $X$;
4. our data sets have just one element each, so that $f(\{1\})$ is either 0 or 1; and
5. $\epsilon=\frac12$.


Then
$$\Pr\left(||f - \mu|| >\frac{\varepsilon}{2}\right)\ge \Pr\left(|f(\{1\})-\mu(\{1\})|>\frac14\right)=1$$
so the stated inequality, if true, would give
 $$\frac12=\Pr\left(||f\_1 - f\_2|| > \varepsilon\right)
\;\leq\;
\Pr\left(||f - \mu|| >\frac{\varepsilon}{2}\right) - \Pr\left(||f - \mu|| >\frac{\varepsilon}{2}\right)^2=1-1^2=0,$$
a contradiction.


(If the first mistake in the book is on page 574, that's pretty good though.)


