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.


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:

enter image description here

  • 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.


1 Answer 1


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.

  • $\begingroup$ 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) $\endgroup$
    – Slim Shady
    Aug 16, 2021 at 10:44
  • $\begingroup$ 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 :) $\endgroup$
    – nir shahar
    Aug 16, 2021 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.