$4$ PAC$-$Learning of Axis$-$Aligned Boxes $[8+10=18$ points$]$

In this problem, we consider the class of $n-$dimensional axis$-$aligned boxes. Each function $c$ in this class is specified by a

set of $2n$ values $l_1,$dots,$l_n$ and $u_1,$dots,$u_n$ in $0,1,$ which defines an axis$-$aligned $n-$dimensional box. Given an $n-$dimensional

input vector $x,c(x)$ is defined to be $1($or $\text{'}+\text{'})$ if for every iin$\{1,$dots,$n\}$ the $i\text{'}$th coordinate of $x$ lies in $l_i,u_i.$ Otherwise,

$c(x)$ is defined to be $0($or $\text{'}-\text{'}).$

An example of a $2-$dimensional axis$-$aligned box is shown in the figure below.

$($a$)$ Let $C$ be the class of $n-$dimensional axis$-$aligned boxes, and cinC be the unknown target function. State an efficient

algorithm that takes as input an arbitrary set of points $x_1,x_2,$dots,$x_m$ each a point in $n-$dimensional space, and their

corresponding labels $c(x_1),c(x_2),$dots,$c(x_m),$ and outputs a function hinC that is consistent with this data. Your

algorithm should run in polynomial time in $m,n$ and facilitate answering part $($b$)$ below.

$($b$)$ Let $D$ be an arbitrary, unknown distribution, and let $c$ be an arbitrary, unknown $n-$dimensional axis$-$aligned box.

Suppose your algorithm from part $($a$)$ is given as input $m$ points $x_1,x_2,$dots,$x_m$ drawn i$.$i$.$d$.$ from $D$ and their

corresponding labels $c(x_1),c(x_2),$dots,$c(x_m).$ Let $h$ be the function output by your algorithm. Let $$ and $lon$ be fixed

parameters in $(0,\frac{1}{2}).$ Without referring to VC dimension, state and prove an upper bound for $m$ to ensure accuracy

$lon$ with confidence parameter $?$ Don't worry about getting the best possible constant factors in your bound, just focus

on the important parameters $(n,,lon).$

Hint: you can use the fact that $(1-x{)}^{\frac{1}{n}}1-\frac{x}{n}$ for any $x1$ and positive integer $n.$