Trjtdtk

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^textstat, r_H (epsilon) = Oleft(m^textstat, r_H (epsilon/2, 1/2)cdot log(1/epsilon) + fraclog(1/epsilon)epsilon^2right)$

Where $m^textstat, r_H (epsilon)$ is the minimal number $m$ such that for any realizable distribution over training examples $D$ we have that:
$$mathbbE_S sim D^mleft[ l_D(A(S)) right]leq epsilon$$

And where $m^textstat, 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^mleft( l_D(A(S)) geq epsilon right) leq delta$$

Thanks a lot in advance!

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)$:

$beginalign*
E[L] &= int_l geq epsilon / 2ldP + int_l< epsilon / 2 ldP leq int_l geq epsilon / 2dP + int_l< epsilon / 2 fracepsilon2 dP\
&= P(L geq epsilon/2) + fracepsilon2 P(L <epsilon/2)\
&= (1 - epsilon/2)P(L geq epsilon/2) + epsilon/2 < epsilon
Leftrightarrow P(L geq epsilon/2) < epsilon/(2 - epsilon)
endalign*$

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:

$beginalign*
(&epsilon/2, 1/2)mbox-learnable H with m_1 Leftrightarrow exists C_1 > 0, m_1 geq C_1fracd + log(2)epsilon/2\
&Leftrightarrow log(1/epsilon)(m_1 + 1/epsilon^2) geq fraclog(1/epsilon)(C_1d + C_1log(2) + 1/(2epsilon))epsilon/2
endalign*$

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)=fraclog(x)(C_1d+C_1log(2)+x/2)dlog(2x)+log(2x-1) geq C_2$

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

$beginalign*
&... oversetexists C_2geq C_2fracdlog(2/epsilon) + log((2-epsilon)/epsilon)epsilon/2 oversetexists C_3geq frac1C_3 m_3
Leftrightarrow (epsilon/2, epsilon/(2-epsilon))mbox-learnable H with m_3
endalign*$

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

$beginalign*
&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
endalign*$.

Proof is complete.