View Single Post
  #1  
Old 02-16-2016, 07:29 PM
wordchao wordchao is offline
Junior Member
 
Join Date: Feb 2016
Posts: 2
Default example non-overlap hypothesis set H to make union bound equals vc bound

consider the union bound, when H consists of only h1 and h2,
Pr[|Ein(g)-Eout(g)|>e]
<=Pr[|Ein(h1)-Eout(h1)|>e or |Ein(h2)-Eout(h2)|>e] (eq.1)
<=Pr[|Ein(h1)-Eout(h1)|>e] + Pr[|Ein(h2)-Eout(h2)|>e] (eq.2)
=2exp(-2Ne^2) (eq.3)

i wonder which kind of h1 and h2 can more "accurately" satisfy the union bound, maybe this means union bound equals vc bound.
in other words, can i find h1 and h2 to let (eq.1)=(eq.2)?

Pr[|Ein(h1)-Eout(h1)|>e or |Ein(h2)-Eout(h2)|>e]
=Pr[|Ein(h1)-Eout(h1)|>e and |Ein(h2)-Eout(h2)|>e] (eq.a)
+Pr[|Ein(h1)-Eout(h1)|>e and |Ein(h2)-Eout(h2)|<=e] (eq.b)
+Pr[|Ein(h1)-Eout(h1)|<=e and |Ein(h2)-Eout(h2)|>e] (eq.c)

if (eq.2)=(eq.1), then,
sup(eq.a)=0
sup(eq.b)=sup(eq.c)=1/2(eq.3)=exp(-2Ne^2)

but i cannot find the example h1&h2, which means h1 and h2 has no overlap when considering the union bound.
can u help? thanks.
Reply With Quote