0.9 Error bounds in countably infinite spaces

Introduction

In the last lecture , we studied bounds of the following form: for any $\delta >0$ , with probability at least $1-\delta$ ,

which led to upper bounds on the estimation error of the form

The key assumptions made in deriving the error bounds were:

• (i) bounded loss function
• (ii) finite collection of candidate functions

The bounds are valid for every $P_{XY}$ and are called distribution-free.

Deriving bounds for countably infinite spaces

In this lecture we will generalize the previous results in a powerful way by developing bounds applicable to possibly infinitecollections of candidates. To start let us suppose that $\mathcal{F}$ is a countable, possibly infinite, collection of candidate functions.Assign a positive number c( $f$ ) to each $f\in \mathcal{F}$ , such that

The numbers c( $f$ ) can be interpreted as

• (i) measures of complexity
• (ii) -log of prior probabilities
• (iii) codelengths

In particular, if P( $f$ ) is the prior probability of $f$ then

so $c\left(f\right)\equiv -logp\left(f\right)$ produces

Now recall Hoeffding's inequality. For each $f$ and every $ϵ>0$

or for every $\delta >0$

Suppose $\delta >0$ is specified. Using the values c( $f$ ) for $f\in \mathcal{F}$ , define

Then we have

Furthermore we can apply the union bound as follows

So for any $\delta >0$ with probability at least $1-\delta$ , we have that $\forall f\in \mathcal{F}$

Special case

and

which implies that for any $\delta >0$ with probability at least $1-\delta$ , we have

Note that this is precisely the bound we derived in the last lecture .

Choosing c( $f$ )

The generalized bounds allow us to handle countably infinite collections of candidate functions, but we require that

Of course, if $c\left(f\right)=-logp\left(f\right)$ where $p\left(f\right)$ is a proper prior probability distribution then we have

However, it may be difficult to design a probability distribution over an infinite class of candidates. The coding perspectiveprovides a very practical means to this end.

Assume that we have assigned a uniquely decodable binary code to each $f\in \mathcal{F}$ , and let c( $f$ ) denote the codelength for $f$ . That is, the code for $f$ is c( $f$ ) bits long. A very useful class of uniquely decodable codes are called prefix codes.

Prefix Code

A code is called a prefix codeif no codeword is a prefix of any other codeword.

The kraft inequality

For any binary prefix code, the codeword lengths $c_1$ , $c_2$ , ... satisfy

Conversely, given any $c_1$ , $c_2$ , ... satisfying the inequality above we can construct a prefix code with these codeword lengths.We will prove this result a bit later, but now let's see how this is useful in our learning problem.

Assume that we have assigned a binary prefix codeword to each $f\in \mathcal{F}$ , and let c( $f$ ) denote the bit-length of the codeword for $f$ . Set $\delta \left(f\right)=2^{-c\left(f\right)}\delta$ . Then