# Showing Axis-Aligned Rectangles With Noise Are PAC-Learnable (FML, Problem 2.6)

I asked the following in Math Stack Exchange and was told "You may be more likely to get an answer on stats.stackexchange.com". I figured this is a more suitable place.

In what follows, an axis-aligned rectangle is an element of the set $$\mathcal{C}:=\{[l,r]\times [b,t]\in\mathscr{P}(\mathbb{R}^2)\mid l,r,b,t\in \mathbb{R}\}$$. This will be our concept class and our hypothesis set, i.e., $$\mathcal{H}=\mathcal{C}$$.

I'm trying to solve problem 2.6 of Foundations of Machine Learning (Second Edition) by M. Mohri et al which goes as follows.

## The Problem.

2.6 Learning in the presence of noise - rectangles. In example 2.4, we showed that the concept class of axis-aligned rectangles is PAC-learnable. Consider now the case where the training points received by the learner are subject to the following noise: points negatively labeled are unaffected by noise but the label of a positive training point is randomly flipped to negative with probability $$\eta \in (0,1/2)$$. The exact value of the noise rate $$\eta$$ is not known to the learner but an upper bound $$\eta'$$ is supplied to him with $$\eta\leq \eta'<1/2$$. Show that the algorithm returning the tightest rectangle containing positive points can still PAC-learn axis-aligned rectangles in the presence of this noise.

## My Attempted Solution.

Let $$\mathcal{A}$$ be the algorithm described in the problem and $$R\in \mathcal{C}$$. Let $$\varepsilon>0$$, $$m\in\mathbb{N}$$ and $$\mathcal{D}$$ a distribution over $$\mathbb{R}^2\times \{0,1\}$$ such that $$(X,Y)\sim \mathcal{D}$$ where the described property is satisfied for $$Y$$ (that is, $$Y=1$$ with probability $$1-\eta$$ when $$X\in R$$ and $$Y=0$$ with probability $$\eta$$ in the same scenario. $$Y=0$$ if $$X\notin R$$). Let $$l,r,b,t\in\mathbb{R}$$ be such that $$R = [l,r]\times [b,t]$$.

Let $$S:=((X_1,Y_1),\dots, (X_m,Y_m))\sim \mathcal{D}^m$$ $$i.i.d.$$ and $$R_S = \mathcal{A}(S)$$. If $$\mathbb{P}(X\in R)<\varepsilon$$, then, since $$R_S\subseteq R$$, we are done (since the only error can come from $$R\setminus R_S \subseteq R$$). If not, define $$r_1 = [l,s_1]\times [b,t]$$ where $$s_1=\inf\{s\geq l\mid \mathbb{P}(X\in [l,s]\times [b,t])\geq \varepsilon /4\}$$ (so that $$r_1$$ consists of taking a chunk from the left of $$R$$). Define $$r_2,r_3,r_4$$ similarly (taking a chunk from the right, bottom, and top of $$R$$). If the risk of $$R_S$$, $$\mathcal{R}(R_S):=\mathbb{P}(\mathbb{1}_{R_S}(X)\neq \mathbb{1}_{R}(X))=\mathbb{P}(X\in R_S\triangle R)=\mathbb{P}(X\in R\setminus R_S)$$, is greater or equal than $$\varepsilon$$, then $$R_S\cap r_i=\emptyset$$ for some $$i$$ (since $$R\setminus R_S\subseteq r_1\cup\dots \cup r_4$$ otherwise). Therefore, \begin{align} \mathbb{P}(\mathcal{R}(R_S)\geq \varepsilon) &\leq \mathbb{P}\left(\bigcup_{i=1}^4\{R_S\cap r_i=\emptyset\}\right)\\ & \leq \sum_{i=1}^4 \mathbb{P}\left(R_S\cap r_i=\emptyset\right)\\ & \leq \sum_{i=1}^4 \mathbb{P}\left(\lnot (X_1\in r_i\land Y_1=\mathbb{1}_{R}(X)),\dots , \lnot (X_m\in r_i\land Y_m=\mathbb{1}_R(X))\right)\\ & = \sum_{i=1}^4 \mathbb{P}\left(X\notin r_i\lor Y\neq\mathbb{1}_{R}(X)\right)^m\\ \end{align}

Using \begin{align*} \mathbb{P}\left(X\notin r_i\lor Y\neq\mathbb{1}_{R}(X)\right)&=1-\mathbb{P}\left(X\in r_i, Y=1\right)\\ & =1-\mathbb{P}(Y=1\mid X\in r_i)\mathbb{P}(X\in r_i)\\ & \leq 1-(1-\eta)\varepsilon/4\\ & \leq 1-(1-\eta')\varepsilon/4\\ & \leq \exp(-(1-\eta')\varepsilon/4)\\ \end{align*} it follows that $$\sum_{i=1}^4 \mathbb{P}\left(X\notin r_i\lor Y\neq\mathbb{1}_{R}(X)\right)^m\leq 4\exp(-m(1-\eta')\varepsilon/4)$$ and thus $$\mathbb{P}(\mathcal{R}(R_S)\geq \varepsilon)\leq 4\exp(-m(1-\eta')\varepsilon/4)$$. Therefore, setting the RHS smaller than $$\delta$$, we obtain the sample complexity $$m\geq \frac{4}{(1-\eta')\varepsilon}\log\left(\frac{4}{\delta}\right).$$

## My Question.

Is my answer correct? The book states that for the noisy scenario, the correct setting is agnostic PAC-learning, however, the problem asks for PAC-learnability, so I'm not sure if I'm doing what is expected. Furthermore, I've used $$\mathcal{R}(R_S)=\mathbb{P}(\mathbf{1}_{R_S}(X)\neq \mathbf{1}_{R}(X))$$, should have I used $$\mathcal{R}(R_S)=\mathbb{P}(\mathbf{1}_{R_S}(X)\neq Y)$$ instead? Why and why not?