Is there a mistake in Vapnik's "Basic Lemma"?

Question

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?

Answer 1

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.)