# Why is the inequality 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.

So in this question $$R^*$$ is the rectangle corresponding to the true labeling function $$f$$. That means in the population any example inside $$R^*$$ is positive and any example outside $$R^*$$ is negative. Then $$A(S)$$ correctly classifies any positive samples inside $$R(S)$$ and also correctly classifies any negative samples outside of $$R^*$$, but makes a mistake on positive samples lying inside $$R^*$$ but outside $$R(S)$$. Since the true error of $$A(S)$$ is the probability of misclassifying a point, as long as each of the rectangle $$R_1,R_2,R_3,R_4$$ intersect $$R(S)$$, the probability of misclassifying a point is at most the sum of the probability that the point lies in one of these rectangles, that is $$\varepsilon$$.
Now $$R_1,R_2,R_3,R_4$$ were constructed so that the probability mass under the distribution $$\mathcal{D}$$ that generates the samples is $$\frac{\varepsilon}{4}$$. Then for each example drawn, the probability that it does not lie in $$R_1$$ is $$(1-\frac{\varepsilon}{4})$$, and equivalently with $$R_2,R_3,R_4$$. Since we draw $$m$$ samples, the probability that none of these lie in $$R_1$$ is $$(1-\frac{\varepsilon}{4})^m$$. From here we apply the union bound and the result follows.