VC dimension and uniform laws for zero–one loss

$$$$

Goals

• Give an example of the integrable Lipschitz conditions
• Show that zero–one loss does not satisfy the integrable Lipschitz conditions
• Define the Vapnik-Chervonenkis (VC) dimension
• State (but do not prove) a ULLN in terms of the VC dimension

Reading

These notes can be supplemented with Hastie, Tibshirani, and Friedman (2009) Chapter 7.9. The final bound is based on Wainwright (2019) Chapter 4.3, which is more advanced by provides a more complete treatment. Finally, if you want to go further, there are nice video tutorials in lectures 7 and 8 of this online course.

Examples of integrable Lipschitz loss

Recall that we proved a ULLN for functions of the form $\varphi (z,\theta )$ satisfying

$$|\varphi (z,\theta )-\varphi (z,{\theta }^{\prime })|\le M(z)\Vert \theta -{\theta }^{\prime }\Vert$$

where $\theta \in \mathrm{\Omega }$ and $\mathrm{\Omega }$ is compact. We called these the ``integrable Lipschtiz’’ (IL) conditions. This is because a Lipschitz function of $\theta$ satisfies

$$|g(\theta )-g({\theta }^{\prime })|\le L\Vert \theta -{\theta }^{\prime }\Vert$$

for some constant $L$, and the IL condition allows this $L$ to depend on $z$, but in a way that is ``integrable’’ by an integrable function $M(z)$.

To use this result to control generalization error, we want to apply this to functions of the form

$$\underset{f\in \mathcal{F}}{sup}|\frac{1}{N}\sum _{n=1}^N\mathcal{L}(f(x_n),y_n)-{\mathbb{E}}_{}[\mathcal{L}(f(x),y)]|.$$

So we might take $z=(x,y)$, a parametric learner $f(\cdot ,y)$, and

$$\varphi (z,\theta )=\mathcal{L}(f(x,\theta ),y).$$

OLS loss

For example, taking squared loss and linear regression, we get

$$\varphi (z,\theta )=({\mathit{x}}^{⊺}\theta -y{)}^2=y^2-2y{\mathit{x}}^{⊺}\theta +\mathrm{trace}\left(\mathit{x}{\mathit{x}}^{⊺}\theta {\theta }^{⊺}\right).$$

Let us assume that $\mathrm{\Omega }$ is compact. (One can show that $\mathrm{\Omega }$ can be safely taken to be compact with high probability as $N$ grows, but I will leave that as a potential homework problem.) We then have, by the triangle inequality and Cauchy–Schwartz,

$$\begin{array}{rl}\varphi (z,\theta )-\varphi (z,{\theta }^{\prime })=& -2y{\mathit{x}}^{⊺}(\theta -{\theta }^{\prime })+\mathrm{trace}(\mathit{x}{\mathit{x}}^{⊺}(\theta {\theta }^{⊺}-{\theta }^{\prime }{{\theta }^{\prime }}^{⊺}).\\ =& -2y{\mathit{x}}^{⊺}(\theta -{\theta }^{\prime })+\mathrm{trace}(\mathit{x}{\mathit{x}}^{⊺}(\theta +{\theta }^{\prime })(\theta -{\theta }^{\prime }{)}^{⊺})\Rightarrow \\ |\varphi (z,\theta )-\varphi (z,{\theta }^{\prime })|\le & 2y\Vert \mathit{x}\Vert \Vert \theta -{\theta }^{\prime }\Vert +{\Vert \mathit{x}\Vert }^2\Vert \theta +{\theta }^{\prime }\Vert \Vert \theta -{\theta }^{\prime }\Vert \\ \le & (2y\Vert \mathit{x}\Vert \Vert \theta -{\theta }^{\prime }\Vert +{\Vert \mathit{x}\Vert }^2\Vert \theta +{\theta }^{\prime }\Vert )\Vert \theta -{\theta }^{\prime }\Vert \\ \le & 2(y\Vert \mathit{x}\Vert \Vert \theta -{\theta }^{\prime }\Vert +{\Vert \mathit{x}\Vert }^2\underset{\theta \in \mathrm{\Omega }}{sup}\Vert \theta \Vert )\Vert \theta -{\theta }^{\prime }\Vert \end{array}$$

where $\underset{\theta \in \mathrm{\Omega }}{sup}\Vert \theta \Vert$ is finite because $\mathrm{\Omega }$ is compact. We can thus take

$$M(z)=2(y\Vert \mathit{x}\Vert \Vert \theta -{\theta }^{\prime }\Vert +{\Vert \mathit{x}\Vert }^2\underset{\theta \in \mathrm{\Omega }}{sup}\Vert \theta \Vert ),$$

and see that quadratic loss satisfies the IL condition, and so a ULLN. (Though recall that we can show directly that this loss obeys a ULLN, as you have done in your homework.)

Bounded derivatives

In general, it suffices to show that the derivative $\frac{\partial \varphi (z;\theta )}{\partial \theta }$ is integrable by an integrable $M(z)$. This is because, for any ${\theta }_1$ and ${\theta }_0$, we can define a path $\theta (t)={\theta }_0+({\theta }_1-{\theta }_0)t$ and write

$$\begin{array}{rl}\varphi (z;{\theta }_1)=& \varphi (z;{\theta }_0)+{\int }_0^1\frac{\partial \varphi (z;\theta (t))}{\partial t}dt\\ =& \varphi (z;{\theta }_0)+{\int }_0^1{\frac{\partial \varphi (z;\theta )}{\partial \theta }|}_{\theta (t)}({\theta }_1-{\theta }_0)dt,\end{array}$$

giving

$$\begin{array}{rl}|\varphi (z;{\theta }_1)-\varphi (z;{\theta }_0)|\le & {\int }_0^1|{\frac{\partial \varphi (z;\theta )}{\partial \theta }|}_{\theta (t)}({\theta }_1-{\theta }_0)|dt\\ \le & {\int }_0^1\Vert {\frac{\partial \varphi (z;\theta )}{\partial \theta }|}_{\theta (t)}\Vert dt\Vert {\theta }_1-{\theta }_0\Vert \\ \le & \underset{\theta \in \mathrm{\Omega }}{sup}\Vert {\frac{\partial \varphi (z;\theta )}{\partial \theta }|}_{\theta }\Vert dt\Vert {\theta }_1-{\theta }_0\Vert \end{array}$$

Therefore, if we can take

$$M(z)=\underset{\theta \in \mathrm{\Omega }}{sup}\Vert {\frac{\partial \varphi (z;\theta )}{\partial \theta }|}_{\theta }\Vert ,$$

and show that ${\mathbb{E}}_{}[M(z)]<\mathrm{\infty }$, then the IL property follows.

Zero–one loss functions

Unfortunately, zero–one losses are not typically IL, since they depend non–smoothly on the classification function $f$. For a simple example, take $x\in {\mathbb{R}}^{}$, $y\in \{0,1\}$ (so it’s a classification problem), and $\mathcal{L}(\hat{y},y)=\mathrm{I}(\hat{y}\ne y)$. Consider the simple threshold classifier

$$f(x;\theta )=\mathrm{I}(x\ge \theta ).$$

Then consider classification error at $\theta =x\pm \epsilon$ for small $\epsilon$ and $y=1$. We have:

$$\mathcal{L}(f(x;x+\epsilon ),1)-\mathcal{L}(f(x;x-\epsilon ),1)=1\text{but}\Vert x+\epsilon -(x-\epsilon )\Vert =2\epsilon .$$

Since $\mathcal{L}(f(x;\theta ),1)$ is discontinuous in $\theta$ at $x$, the function cannot be IL. A different technique is needed to control generalization error for zero–one loss.

VC dimension

$$$$

A key tool in controlling generalization error for functions taking values in $\{0,1\}$ is ``Vapnik–Chervonenkis’’ (VC) dimension. The VC dimension is a measure of complexity of set of functions, so we might write $VC(\mathcal{F})$ for the VC dimension of the function class $\mathcal{F}$, where each member $f\in \mathcal{F}$ maps some domain $x$ to binary values $\{0,1\}$. (The VC dimension can be defined for more general functions by reducing them to binary–valued functions; see Van der Vaart (2000) Chapter 19, for example.)

For a given set of $N$ points, ${\mathcal{X}}_N=(x_1,\dots ,x_N)$, a function $f$ returns a binary vector $f(\mathcal{X}):=(f(x_1),\dots ,f(x_N))$. As $f$ ranges over $\mathcal{F}$, $f(\mathcal{X})$ ranges over possible values of the $2^N$ possible binary vectors.

For example, take our threshold classifier from above. If $N=2$ and $\mathcal{X}=(3,4)$, then as $\theta$ ranges from $-\mathrm{\infty }$ to $\mathrm{\infty }$, $f(\mathcal{X})$ goes from $(1,1)$ to $(0,1)$ (as $\theta$ passes $3$) to $(0,0)$ (as $\theta$ passes $4$). The value $(1,0)$ is impossible to produce with any $f\in \mathcal{F}$ and this $\mathcal{X}$, since $3<4$, and so $4$ is classified as $1$ whenever $3$ is.

As we saw, for a given $\mathcal{X}$, the number of distinct values of $f(\mathcal{X})$ may be more or less than the total number of possibly values $2^N$. If $f(\mathcal{X})$ is able to take all possible $2^N$ values as $f$ ranges over $\mathcal{F}$, then $f$ is said to ``shatter’’ $\mathcal{X}$. Intuitively, $\mathcal{X}$ gets harder to shatter as it contains more and more points. For example, the threshold function above can shatter a single point, but cannot shatter two points. Also intuitively, more expressive function classes can shatter larger and larger sets of points.

VC Dimension

For a given function class $\mathcal{F}$ of functions taking values in $\{0,1\}$, let $VC(\mathcal{F})$ be the largest number $N$ such that there exists a vector $\mathcal{X}$ of length $N$ that can be shattered by $\mathcal{F}$. Equivalently, if $M$ is smallest number such that no $\mathcal{X}$ can be shattered by $\mathcal{F}$, then $VC(\mathcal{F})=M-1$.

Note that the VC dimension doesn’t mean you can shatter all sets of size $VC(\mathcal{F})$. In fact, this is obviously impossible, since a set consisting of $N$ copies of the same value cannot be shattered, no matter how complex $\mathcal{F}$ is. The VC dimension requires only that you can find some set $\mathcal{X}$ of size $VC(\mathcal{F})$ that is shattered, but no such set $VC(\mathcal{F})+1$.

We have already shown that the VC dimension of the boundary classifier is $1$.

The passage from VC dimension to ULLNs is somewhat complex, and beyond the scope of this (undergraduate) course. An end–to–end treatment can be found in Wainwright (2019) chapter four, from which we simply state the result.

Let $VC(\mathcal{F})=\nu$, and $f\in \mathcal{F}$ take values in $\{0,1\}$. Then, by Wainwright (2019):

$$\underset{f\in \mathcal{F}}{sup}|\frac{1}{N}\sum _{n=1}^{N}f(z_n)-{\mathbb{E}}_{}[f(z)]|\le \sqrt{\frac{\nu \log (N+1)}{N}}+\delta \text{with probability at least}1-\exp (-N{\delta }^2/2).$$

Specifically, this is a consequence of the following results from Wainwright (2019):

• Proposition 4.18 and Definition 4.13 (VC dimension implies polynomial discrimination)
• Lemma 4.14 and equation 4.24 (polynomial discrimination controls Rademacher complexity)
• Theorem 4.10 (Rademacher complexity controls the ULLN)

Note that this result is stronger than our asymptotic results, in the sense that it is a finite–sample exact bound, rather than an (otherwise uncontrolled) guarantee as $N\to \mathrm{\infty }$. Finite–sample bounds are much easier to obtain when the function $f(x)$ is bounded as a function of $x$, as is the case for zero–one loss, but which is not typically the case for regression loss.

Note

Exercise: Show that if a function class $f(\mathit{x})$ for $f\in \mathcal{F}$ has finite VC dimension, then the function class $\{\varphi (\mathit{x},y)=\mathrm{I}(f(\mathit{x})\ne y)\text{ for }f\in \mathcal{F}\}$ also has finite VC dimension. Conclude that a ULLN holds for zero–one loss when using a classifier with finite VC dimension.

References

Hastie, T., R. Tibshirani, and J. Friedman. 2009. The Elements of Statistical Learning: Data Mining, Inference and Prediction. 2nd ed. Springer.

Van der Vaart, A. 2000. Asymptotic Statistics. Vol. 3. Cambridge university press.

Wainwright, M. 2019. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Vol. 48. Cambridge university press.