PAC learning axis parallel rectangles

Question

I am trying to understand the proof that the axis parallel rectangles are PAC learnable in the realizable case. This means that given $\epsilon, \delta$ with enough data we can find a function $h$ such that $$\mathbb{P}\left[\text{error} > \epsilon\right] \leq \delta$$ Here error can be seen as the probability of making an error with our chosen function $h$.

Now, for axis parallel rectangles (in binary classification) the usual argument goes like this, let $R$ be the true rectangle and let $R'$ be the smallest rectangle containing the positive examples, clearly $R' \subseteq R$, we consider the four rectangular strips between $R'$ and $R$. Clearly if all of them have probability $\leq \epsilon/4$ then the probability of making an error is less than $\epsilon$, so we can assume that at least one have probability of making an error $\geq \epsilon/4$.

For such a strip the probability of correctly classifying all the $m$ training examples is at most $(1 - \epsilon/4)^m$, and thus taking aunion bound over all strips we get that the probability of correctly classifying everything is less than $4(1-\epsilon/4)^m \leq 4e^{-m/4}$, and with a bit of algebra this yields that the sample complexity is $m \geq (4/\epsilon)\ln(4/\delta)$.

Here is a pdf that explains in a bit more detail, with some pictures, I just had to condense the argument as much as I can to fit it in here.

My question is, why do we have to consider the four rectangular strips separatedly, why can't we just say that the probability of the region between $R'$ and $R$ has to be greater than $\epsilon$ (because otherwise we are done), and thus using the same argument we would arrive at the better bound $m \geq (1/\epsilon)\ln(1/\delta)$?

Sorry for the long question, and thanks in advance.

Answer 1

The question is a little vague, but it seems like what you want to argue is along the line of this: Let $R$ be the concept to learn, and take any $R^*\subset R$ be any rectangle covering a $(1-\epsilon)$-fraction of $R$. Then with some probability $R'$ will contain $R^*$.

The problem with this is that the particular probability depends on the specific choice of $R^*$. I think what you're confused about is that want $R'$ to perform well on unseen examples. By construction $R'$ will correctly classify all the training data. The bad event is actually that all of the training data is concentrated in too small a rectangle; this happens with probability at most that of the event that one of the strips is missed by all the training examples.

Answer 2

hmm... well, in the proof you mention, we draw points (x,y) from some distribution D, and check whether they fall into a square really. I.e. we pick the same $\delta$ for each bound (max x, min x, max y, min y). Now if you had a circle, you can't just do that - you have to pick a delta for a radius, and the radius is a function of coordinates. So that will make the proof more complicated.

If you go for non-concave polygons - its should get much harder.