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?


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

  • $\begingroup$ Alright, so it's not just me who's crazy. Thanks for the answer. $\endgroup$
    – Mathias
    Jul 22 '14 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.