Chapter 2 ERM with finite hypothesis classes

Let’s start with the second term from (1.6):

Remember that the only thing that’s random here is $Z=(z_1,\mathrm{\dots },z_m)$ , since $h^{\ast }$ is just some fixed hypothesis. So, we can frame this as $\frac{1}{m}{\sum }_{i=1}^m{r}_i$ , where the $r_i=\mathrm{\ell }(h^{\ast },z_i)$ are iid random variables with mean $𝔼\mathrm{\ell }(h^{\ast },z_i)=L_{𝒟}(h^{\ast })$ . The law of large numbers therefore guarantees that as $m\to \mathrm{\infty }$ , $\frac{1}{m}{\sum }_{i=1}^m{r}_i$ converges (almost surely) to $L_{𝒟}(h^{\ast })$ , and so this term in the bound converges to zero.

In fact, for many $\mathscr{H}$ and $\mathrm{\ell }$ , the other term will also have the same property, that $L_Z({\widehat{h}}_Z)\to L_{𝒟}({\widehat{h}}_Z)$ . Therefore, by (1.6), we have (if $h^{\ast }$ is a minimizer of $L_{𝒟}$ ) that $L_{𝒟}({\widehat{h}}_Z)\to L_{𝒟}(h^{\ast })$ . Various formalizations of this last property are called consistency, and it’s a nice property to have: eventually, your learning algorithm works as well as it could have. One problem with this notion, though, is that this is all it tells you. There’s no guarantee about what happens with $m=1,000$ , or when going from $m=1,000$ to $m=1,000,000$ , or anything at all other than “eventually it works.”

A more precise analysis might use the central limit theorem. Let ${\sigma }^2=Var[r_i]$ and assume this is finite; ¹¹1Formally, we’d write $\frac{1}{\sqrt{m}}{\sum }_{i=1}^m(r_i-𝔼r_i)\stackrel{d}{\to }𝒩(0,{\sigma }^2)$ ; the $\stackrel{d}{\to }$ is convergence in distribution. informally, the CLT then says that $\frac{1}{m}{\sum }_{i=1}^m{r}_i$ behaves like $𝒩(L_{𝒟}(h^{\ast }),{\sigma }^2/m)$ . In fact, it’s often true that the first term is also asymptotically normal ([VAN98], Section 5.3). This is a nicer result than before: it still doesn’t say anything particular for a finite $m$ (maybe the CLT takes a long time to kick in), but it tells us a lot about the asymptotic behaviour, including both its limiting value and also roughly how much variation we can expect around that value.

It can be tough to find these exact limiting distributions in general, though, and they’re not always true (e.g. the one I didn’t state for the first term above has some strict requirements on the way that $h$ is parameterized, which are often not true for real models ([WMG+23])). A similar but somewhat looser style of bound is to say that ²²2You can check the wiki page for a formal definition of ${𝒪}_p$ , but it roughly means “with any constant probability, a sequence of sampled random variables is $𝒪(1/\sqrt{m})$ .” the estimation error is ${𝒪}_p(1/\sqrt{m})$ , which is implied by the CLT result above, but can also be much easier to show. Again, this doesn’t imply anything for a finite $m$ (just like how $𝒪$ analyses don’t say anything for any specific input size on your algorithms), but it does say things like “for reasonably large $m$ , observing four times as much data should roughly halve your estimation error.”

The most preferred kind of result, though, is usually one with explicit constants: something like (if $|\mathscr{H}|$ is finite – see section 2.3)

or, where $B$ is a problem parameter,

These results give you a rate, but also apply to any $m$ , not just eventually. (They might not be meaningful for small $m$ , though; if you’re using 0-1 loss, it’s not very helpful to say the estimation error is less than four!)

We’re first going to assume that $\mathrm{\ell }(h,z)\in [a,b]$ for all $h,z$ ; often $a=0$ , and e.g. for the 0-1 loss we have $b=1$ . For something like the square loss, it isn’t “automatically” bounded, but it still might be bounded by the choice of $\mathscr{H}$ and $𝒟$ ; we’ll discuss this later.

Recall that we have two things to bound in (1.6):

and

As we discussed, (B) is an average of iid random variables. We can bound this with the following form of Hoeffding’s inequality, which we’ll prove in chapter 3:

Applying this to the random variables $x_i=\mathrm{\ell }(h^{\ast },z_i)$ handles the bound for (B).

It’s tempting to also try to apply this result directly to (A), which would then complete our bound and everything would be really simple. The problem is that the $\mathrm{\ell }({\widehat{h}}_Z,z_i)$ aren’t independent! The choice of ${\widehat{h}}_Z$ depends on all of $Z$ , i.e. on all of the other $z_j$ , so $\mathrm{\ell }({\widehat{h}}_Z,z_1)$ and $\mathrm{\ell }({\widehat{h}}_Z,z_2)$ are not independent.

So, how can we bound this? The most common way is called uniform convergence. The idea is that if we know that $L_{𝒟}(h)-L_Z(h)$ is small for all $h\in \mathscr{H}$ , then it’ll be small for ${\widehat{h}}_Z$ , no matter how we pick it – since it’s something in $\mathscr{H}$ . That is, ⁴⁴4 $sup$ is the version of $\max$ for potentially infinitely many things, like how $inf$ is the version of $\min$ . if we know that

then we also have that $L_{𝒟}({\widehat{h}}_Z)-L_Z({\widehat{h}}_Z)\le \epsilon$ . Or, stating it another way,

and so upper-bounding the right-hand side bounds the left-hand side.

How can we bound that?

To start, we’ll make a kind of drastic assumption: that $|\mathscr{H}|$ is finite, e.g. we’re only considering $500$ possible hypotheses.

Another way to state proposition 2.2 is that with $m$ samples, we can achieve estimation error at most $\epsilon$ with probability at least $1-(|\mathscr{H}|+1)\exp \left(-\frac{m{\epsilon }^2}{2{(b-a)}^2}\right)$ .

Or, alternatively, we can say that we can achieve estimation error at most $\epsilon$ with probability at least $1-\delta$ if we have at least $\frac{2{(b-a)}^2}{{\epsilon }^2}\log \frac{|\mathscr{H}|+1}{\delta }$ samples.