Information Technology Reference
In-Depth Information
Proof (
Proof of Theorem 3
).
The proof is analogous to the former proof, but we need
to write most of the probabilistic inequalities in the different direction.
With probability at least 1
−
η
, the following bound on true risk holds true:
ω
I
)+
ln
N
−
ln
η
R
emp
(
ω
I
)
≤
R
(
.
(30)
2
I
By joining (30) and (21) we obtain, with probability at least 1
−
2
η
the system of in-
equalities:
ln
N
−
ln
η
R
emp
(
R
emp
(
ω
I
)
−
≤
R
(
ω
I
)
≤
ω
I
)
2
I
+
−
η
2
I
ln
.
(31)
)
n
:
After
n
independent folds we obtain, with probability at least
(
1
−
2
η
ln
N
n
k
=
1
R
emp
(
ω
I
,
k
)
−
1
n
η
2
I
−
−
ln
−
ln
η
2
I
n
k
=
1
R
emp
(
ω
I
,
k
)
C
1
n
≤
.
(32)
Again as in the former proof, we need to relate
R
emp
(
ω
I
,
k
)
from each fold to
R
emp
(
ω
I
)
,
but now we need the relation to be in the direction
R
emp
(
ω
I
,
k
)
≥···
, so that we can
plug the right-hand-side of it into (32) and keep it true.
We write
ln
N
ln
N
−
ln
η
−
ln
η
ω
I
)
R
emp
(
ω
I
)
−
≤
R
emp
(
−
2
I
2
I
R
emp
(
ω
I
)
.
(33)
≤
Reading it from the right-hand-side: the second is a (13)-like inequality but for discrete
measures, which is true with probability at least 1
−
η
, and the first inequality is true
with probability 1 by definition of
ω
I
.
