0.10 Complexity regularization

Review: pac bounds

Consider a finite collection of models $\mathcal{F}$ , and recall the basic PAC bound: for any $\delta >0$ , with probability at least $1-\delta$

where

and the loss $\ell$ is assumed to be bounded between 0 and 1. Note that we can write the inequality above as:

Letting ${\delta }_f=\frac{\delta }{\left|\mathcal{F}\right|}$ , we have:

This is precisely the form of Hoeffding's inequality, with ${\delta }_f$ in place of the usual $\delta$ . In effect, in order to have Hoeffding's inequality hold with probability $1-\delta$ for all $f\in \mathcal{F}$ , we must distribute the “ $\delta$ -budget” or “confidence-budget” over all $f\in \mathcal{F}$ (in this case, evenly distributed):

However, to apply the union bound, we do not need to distribute $\delta$ evenly among the candidate models. We only require:

So, if $p\left(f\right)$ are positive numbers satisfying ${\sum }_{f\in \mathcal{F}}p\left(f\right)=1$ , then we can take ${\delta }_f=p\left(f\right)\delta$ . This provides two advantages:

1. By choosing $p\left(f\right)$ larger for certain $f$ , we can preferentially treat those candidates
2. We do not need $\mathcal{F}$ to be finite and we only require ${\sum }_{f\in \mathcal{F}}p\left(f\right)=1$

Prefix codes are one way to achieve this. If we assign a binary prefix code of length $c\left(f\right)$ to each $f\in \mathcal{F}$ , then the values $p\left(f\right)=2^{-c\left(f\right)}$ satisfy ${\sum }_{f\in \mathcal{F}}p\left(f\right)\le 1$ according to the Kraft inequality.

The main point of this lecture is to examine how PAC bounds of the form w.p. $\ge 1-\delta$

can be used to select a model that comes close to achieving the best possible performace

Let ${\widehat{f}}_n$ be the model selected from $\mathcal{F}$ using the training data ${\{X_i,Y_i\}}_{i=1}^n$ . We will specify this model in a moment, but keep in mind that it is notnecessarily the model with minimum empirical risk as before. We would like to have

as small as possible. First, for any $\delta >0$ , define

where

Then w.p. $\ge 1-\delta$

and in particular,

so, by the definition of ${\widehat{f}}_n^{\delta }$ , $\forall f\in \mathcal{F}$

We will make use of the inequality above in a moment. First note that $\forall f\in \mathcal{F}$

The second term is exactly 0, since $E\left[{\widehat{R}}_n\left(f\right)\right]=R\left(f\right)$ .

Now consider the first term $E[R\left({\widehat{f}}_n^{\delta }\right)-{\widehat{R}}_n\left(f\right)]$ . Let $\Omega$ be the set of events on which

From the bound above, we know that $P\left(\Omega \right)\ge 1-\delta$ . Thus,

We can summarize our analysis with the following theorem.

Complexity regularized model selection

Let $\mathcal{F}$ be a countable collection of models, and assign a positive number $c\left(f\right)$ to each $f\in \mathcal{F}$ such that ${\sum }_{f\in \mathcal{F}}{2}^{-c\left(f\right)}\le 1$ . Define the minimum complexity regularized risk model

Then,

This shows that

is a reasonable surrogate for