1
$\begingroup$

I came across the following exercise, and I just can't seem to crack it:

Let $l$ be some loss function such that $l \leq 1$. Let $H$ be some hypothesis class, and let $A$ be a learning algorithm. show that:

$m^{\text{stat, r}}_H (\epsilon) = O\left(m^{\text{stat, r}}_H (\epsilon/2, 1/2)\cdot \log(1/\epsilon) + \frac{\log(1/\epsilon)}{\epsilon^2}\right)$

Where $m^{\text{stat, r}}_H (\epsilon)$ is the minimal number $m$ such that for any realizable distribution over training examples $D$ we have that: $$\mathbb{E}_{S \sim D^m}\left[ l_D(A(S)) \right]\leq \epsilon$$

And where $m^{\text{stat, r}}_H (\epsilon, \delta)$ is the minimal number $m$ such that for any realizable distribution over training examples $D$ we have that: $$P_{S \sim D^m}\left( l_D(A(S)) \geq \epsilon \right) \leq \delta$$

Thanks a lot in advance!

$\endgroup$
0
$\begingroup$

We want to prove:

If H is PAC learnable, then $\forall \epsilon, \exists C, \forall m \geq m_2:=Clog(1/\epsilon)(m_1+1/\epsilon^2), E[L] \leq \epsilon \mbox{ (a)}$
where $m_1:=m(\epsilon/2,1/2)$

Since $L \leq 1$, we have $E[L] \leq 1$. So proof is trivial for $\epsilon \geq 1$. Let $\epsilon \in (0, 1)$.

Find an equivalence for $(a)$:

$\begin{align*} E[L] &= \int_{l \geq \epsilon / 2}ldP + \int_{l< \epsilon / 2} ldP \leq \int_{l \geq \epsilon / 2}dP + \int_{l< \epsilon / 2} \frac{\epsilon}{2} dP\\ &= P(L \geq \epsilon/2) + \frac{\epsilon}{2} P(L <\epsilon/2)\\ &= (1 - \epsilon/2)P(L \geq \epsilon/2) + \epsilon/2 < \epsilon \Leftrightarrow P(L \geq \epsilon/2) < \epsilon/(2 - \epsilon) \end{align*}$

Therefore, if

$\forall \epsilon, \forall m \geq m_3:=m(\epsilon/2, \epsilon/(2 - \epsilon)), P(L \geq \epsilon/2) < \epsilon/(2 - \epsilon)\mbox{ (b)}$ holds,

$\forall \epsilon, \forall m \geq m(\epsilon)=m_3, E[L] \leq \epsilon \mbox{ (c)}$ holds too (and vice versa)

Prove $(b) \Rightarrow (a)$:

Using The Fundamental Theorem of Statistical Learning for PAC learnable H with VC dimension $d$, we have:

$\begin{align*} (&\epsilon/2, 1/2)\mbox{-learnable H with } m_1 \Leftrightarrow \exists C_1 > 0, m_1 \geq C_1\frac{d + log(2)}{\epsilon/2}\\ &\Leftrightarrow log(1/\epsilon)(m_1 + 1/\epsilon^2) \geq \frac{log(1/\epsilon)(C_1d + C_1log(2) + 1/(2\epsilon))}{\epsilon/2} \end{align*}$

which uses $1/\epsilon > 1$ and $log(1/\epsilon) > 0$.

Now we use an inequality without proof (plot the function here)

$\forall x > 1, \forall d, C_1 \geq 0, \exists C_2 > 0, f(x)=\frac{log(x)(C_1d+C_1log(2)+x/2)}{dlog(2x)+log(2x-1)} \geq C_2$

Setting $x=1/\epsilon$, we continue as:

$\begin{align*} &... \overset{\exists C_2}{\geq} C_2\frac{dlog(2/\epsilon) + log((2-\epsilon)/\epsilon)}{\epsilon/2} \overset{\exists C_3}{\geq} \frac{1}{C_3} m_3 \Leftrightarrow (\epsilon/2, \epsilon/(2-\epsilon))\mbox{-learnable H with }m_3 \end{align*}$

By setting $m_2 := C_3log(1/\epsilon)(m_1 + 1/\epsilon^2)$, we have $m_2 \geq m_3$, thus

$\begin{align*} &\forall \epsilon, \forall m \geq m_3, P(L \geq \epsilon/2) < \epsilon/(2 - \epsilon)\\ &\Rightarrow \forall \epsilon, \exists C, \forall m \geq m_2 := Clog(1/\epsilon)(m_1 + 1/\epsilon^2) \geq m_3, P(L \geq \epsilon/2) < \epsilon/(2 - \epsilon)\\ &\Rightarrow \forall \epsilon, \exists C, \forall m \geq m_2 := Clog(1/\epsilon)(m_1 + 1/\epsilon^2), E[L] < \epsilon \end{align*}$.

Proof is complete.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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