# Why is $\mathcal{D}^m(\{S:L_{(\mathcal{D},f)}(A(S))\gt \epsilon\})\leq \mathcal{D}^m\left(\bigcup^4_{i=1}F_i\right)$ true?

I am studying the book "Understanding Machine Learning: From Theory to Algorithms". I am struggling to understand the solution to exercise 3 (2) on page 41.

Exercise:

An axis aligned rectangle classifier in the plane is a classifier that assigns 1 to a point if and only if it is inside a certain rectangle. Formally, given real numbers $$a_1\leq b_1, a_2\leq b_2,$$ define the classifier $$h_{(a_1, b_1, a_2, b_2)}$$ by $$h_{(a_1, b_1, a_2, b_2)}(x_1, x_2) = \begin{cases}1&\textrm{if a_1\leq x_1\leq b_1 and a_2\leq x_2\leq b_2}\\ 0&\textrm{otherwise}\end{cases}$$ The class of all axis aligned rectangles in the plane is defined as $$\mathcal{H}_\mathrm{rec}^2 = \{h_{(a_1, b_1, a_2, b_2)}:\textrm{a_1\leq b_1 and a_2\leq b_2}\}$$...rely on realizability assumption. Let $$A$$ be an algorithm that returns the smallest rectangle enclosing all positive examples in the training set. It is shown in (1) that $$A$$ is an ERM.

(2): Show that if $$A$$ receives a training set of size $$\geq \frac{4\log(4/\delta)}{\epsilon}$$ then, with probability of at least $$1-\delta$$ it returns a hypothesis with error of at most $$\epsilon$$.

Hint: Fix some distribution $$\mathcal{D}$$ over $$\mathcal{X}$$, let $$R^*=R(a_1^*,b_1^*,a_2^*,b_2^*)$$ be the rectangle that generates the labels, and let $$f$$ be the corresponding hypothesis. Let $$a_1\geq a_1^*$$ be a number such that the probability mass (w.r.t $$\mathcal{D}$$) of the rectangle $$R_1=R(a_1^*,a_1,a_2^*,b_2^*)$$ is exactly $$\epsilon/4$$. Similarly, let $$b_1,a_2,b_2$$ be numbers suh that the probability masses of the rectangles $$R_2=R(b_1,b_1^*,a_2^*,b_2^*),R_3=R(a_1^*,b_1^*,a_2^*,a_2),R_4=R(a_1^*,b_1^*,b_2,b_2^*)$$ are all exactly $$\epsilon/4$$. Let $$R(S)$$ be the rectanlge returned by $$A$$. See the following illustration:

• Show that $$R(S)\subset R^*$$
• Show that if $$S$$ contains (positive) examples in all of the rectangles $$R_1,R_2,R_3,R_4$$, then the hypothesis returned by $$A$$ has error of at most $$\epsilon$$.
• For each $$i\in\{1,...,4\}$$, upper bound the probability that $$S$$ does not contain an example from $$R_i$$
• Use the union bound to conclude the argument.

From the solution manual, here is the answer on page 2:

Fix some distribution $$\mathcal{D}$$ over $$\mathcal{X}$$, and define $$R^*$$ as in the hint. Let $$f$$ be the hypothesis associated with $$R^*$$ a training $$S$$, denoted $$R(S)$$ the rectagnle returned by the proposed algorithm and by $$A(S)$$ the corresponding hypothesis. The definition of algorithm $$A$$ implies that $$R(S)\subset R^*$$ for every $$S$$. Thus, $$L_{(\mathcal{D},f)}(R(S))=\mathcal{D}(R^*\setminus R(S))$$

Fix some $$\epsilon\in(0,1)$$. Define $$R_1,R_2,R_3,R_4$$ as in the hint. For each $$i\in[4]$$, define the event $$F_i=\{S|_x:S|_x\cap R_i=\emptyset\}$$

Applying the union bound we obtain

$$\mathcal{D}^m(\{S:L_{(\mathcal{D},f)}(A(S))\gt \epsilon\})\leq \mathcal{D}^m\left(\bigcup^4_{i=1}F_i\right)\leq \sum^4_{i=1}\mathcal{D}^m(F_i)$$

So the above is what I don't understand:

Why is $$\mathcal{D}^m(\{S:L_{(\mathcal{D},f)}(A(S))\gt \epsilon\})\leq \mathcal{D}^m\left(\bigcup^4_{i=1}F_i\right)$$

I know what these quantities mean:

• $$\mathcal{D}^m(\{S:L_{(\mathcal{D},f)}(A(S))\gt \epsilon\})$$ is equivalent to "the probability of observing samples $$S$$ such that when algorithm $$A$$ is applied to $$S$$, the true error is greater than $$\epsilon$$.
• $$\mathcal{D}^m\left(\bigcup^4_{i=1}F_i\right)$$ is equivalent to "the probability of observing samples which don't intersect $$R_1$$ or $$R_2$$ or $$R_3$$ or $$R_4$$.

But why is the inequality true? The root of my understanding is that I can't understand how $$\epsilon$$ and $$A(S)$$ are supposed to be involved in interpreting this inequality. As in I don't understand geometrically how $$A(S)$$ and $$\epsilon$$ form subsets in the context of the figure above. I can easily imagine the sets $$F_i$$ though.

Lets say our algorithm chose some rectangle $$\hat R$$ with (true) error bigger than $$\epsilon$$. To prove the inequality, we want to show that we are in one of the 4 events: $$F_1,F_2,F_3,F_4$$.
Notice - that we know that $$\hat R\subseteq R^*$$. Therefore, intuitively, the entire $$\epsilon$$ error comes from the fact that $$\hat R$$ is "much smaller" than $$R^*$$.
Now, from the pigeonhole principle - since we have $$\epsilon$$ error that is "distributed" between the $$4$$ sides, we know that at least one side must contribute with at least $$\frac{\epsilon}{4}$$ error. Formally you can see this from an extension of the pigeonhole principle.
Combining the last two statements, you can conclude that we are in one of the events $$F_1,F_2,F_3,F_4$$ as required.
• Hi, thank you for your answer. I don't understand actually why and how $\epsilon$ is "distributed" between the 4 sides. What exactly does "distributed" mean in this context? (Just fyi I understand what the pigeonhole principle is, but it's not intuitive for me how does the error connect to the probability mass of the $R_i$'s) Aug 16 '21 at 10:44
• Think about $R^*-\hat R$. It is composed of $4$ sides, and the pmf on it has to be at least probability $\epsilon$ (this is exactly what $\epsilon$-error means here). Now take a look at the pmf on each of the $4$ "segments" that compose $R^*-\hat R$. You know that their sum is (at least) the pmf on $R^*-\hat R$, and thus the sum of their pmf's has to be at least $\epsilon$. Now you can apply the pigeonhole principle :) Aug 16 '21 at 10:57