Complete proof of PAC learning of axis-aligned rectangles

Question

I have already read PAC learning of axis-aligned rectangles and understand every other part of the example.

From Foundations of Machine Learning by Mohri, 2nd ed., p. 13 (book) or p. 30 (PDF), I am struggling to understand the following sentence of Example 2.4, which is apparently the result of a contrapositive argument:

... if $R(\text{R}_S) > \epsilon$, then $\text{R}_S$ must miss at least one of the regions $r_i$, $i \in [4]$.

i.e., $i = 1, 2, 3, 4$. Could someone please explain why this is the case?

The way I see it is this: given $\epsilon > 0$, if $R(\text{R}_S) > \epsilon$, then $\mathbb{P}_{x \sim D}(\text{R}\setminus \text{R}_S) > \epsilon$. We also know from this stage of the proof that $\mathbb{P}_{x \sim D}(\text{R}) > \epsilon$ as well. Beyond this, I'm not sure how the sentence above is reached.

Answer 1

Let $R_S, R_T$ denote the sample rectangle (smallest consistent rectangle) and the target rectangle correspondingly. Since $R_S\subseteq R_T$, $R(R_S)\le \mu\left(R_T\setminus R_S\right)$. The intuition behind taking strips of mass $\epsilon$ around the edges of $R_T$ is that you want to satisfy two conditions:

1. The strips, $r_1,...,r_4$ should have large enough mass so that with high probability $m(\epsilon)$ samples do not miss them (this would follow from a simple bound for a geometric random variable).

2. The strips should have small enough mass, so that if all were seen by the samples, then $R_T\setminus R_S\subseteq \bigcup\limits_i r_i$, where the latter union has small probability thus bounding $R(R_S)$.

Your question is settled by the geometric argument in the second point. If all strips were seen by the samples, then we can only err on points in the strips.