= Two-interval approximation by one interval
{title2=$\inf_{h\text{ interval}}\operatorname{err}_D(h)\leq\tfrac13$}
For a target positive <set> consisting of two disjoint intervals of total <probability> $p$, choosing its heavier component has <misclassification risk> at most $p/2$. Choosing the spanning interval has <misclassification risk> at most $1-p$. The smaller bound is at most $1/3$. The constant is sharp: on three ordered atoms with equal masses and labels $1,0,1$, every single interval makes a mistake on at least one atom. Together with the <VC uniform convergence theorem>, this gives <weak PAC learning> using an interval <hypothesis class>.
Back to article page
