= Solution
The <two-interval approximation by one interval> supplies an approximation guarantee for every input <probability distribution> $D$. Merge overlapping target <intervals>, and write the target positive <set> as at most two disjoint ordered <intervals> $I_1,I_2$. Put $p_j=D(I_j)$ and $p=p_1+p_2$. If there is only one nonempty component, the target already belongs to the <interval> <hypothesis class> and has zero <misclassification risk>. If the <interval> notation permits empty <intervals> and the target is empty, choose that same empty <interval> in $H$.
In the two-component case, choosing the heavier component as the hypothesis loses only the lighter component, so its <misclassification risk> is
$$
\min(p_1,p_2)\leq\frac p2.
$$
Alternatively, choose the single <interval> $J$ spanning both components. This produces no false negatives, and its false positives lie in the gap. Its <misclassification risk> is at most $1-p$. Both candidates are in $H$, so there exists an <interval> $h^*$ with
$$
\operatorname{err}_D(h^*)\leq\min\left(\frac p2,1-p\right)\leq\frac13.
$$
For the last step, use $p/2\leq1/3$ if $p\leq2/3$, and $1-p\leq1/3$ if $p\geq2/3$. This avoids any assumption that an empty <interval> or the whole real line belongs to $H$.
Use <empirical risk minimization> over <intervals> on independent labelled examples. The generalization result needed here is the <VC uniform convergence theorem>: for a binary <hypothesis class> of finite <VC dimension> $v$, there is a universal constant $A$ such that, for any labelled-data <probability distribution> and $0<\eta,\delta<1$, a sample size
$$
m\geq\frac A{\eta^2}\left(v\log\frac2\eta+\log\frac2\delta\right)
$$
ensures, with probability at least $1-\delta$, that every hypothesis's <empirical misclassification risk> differs from its <misclassification risk> by at most $\eta$. This theorem does not require the labels to be realizable by the <hypothesis class>.<Learnability and VC Dimension in MIT 6.790>[Sections “Uniform Convergence implies Agnostic PAC Learnability” and “Fundamental Theorem of Learnability”]{ref}
The <interval> <hypothesis class> has <VC dimension> two: any two ordered points can receive all four labellings, whereas an <interval> cannot label three ordered points $1,0,1$. Take $\eta=1/24$ and choose an <interval> $\widehat h$ minimizing the <empirical misclassification risk>. On the simultaneous convergence event,
$$
\begin{aligned}
\operatorname{err}_D(\widehat h)
&\leq\widehat{\operatorname{err}}(\widehat h)+\eta\\
&\leq\widehat{\operatorname{err}}(h^*)+\eta\\
&\leq\operatorname{err}_D(h^*)+2\eta\\
&\leq\frac13+\frac1{12}=\frac5{12}=\frac12-\frac1{12}.
\end{aligned}
$$
Therefore
$$
\boxed{C\text{ is weakly PAC learnable using }H,\qquad\gamma=\frac1{12}.}
$$
Since $v$ and $\eta$ are fixed constants, \b[$O(1+\log(1/\delta))$ examples suffice], which is polynomial in $1/\delta$ as required by the paper's definition of <weak PAC learning>.
For completeness, <empirical risk minimization> over <intervals> is computationally effective. Sort the sample and group equal coordinates, since one <interval> cannot split identical inputs. Give each group weight equal to the number of positive labels minus the number of negative labels in that group. The number of empirical mistakes made by an <interval> is the total number of positives minus the total weight of the consecutive groups it contains. Select the consecutive block of maximum weight, or select a finite <interval> outside the sample if every nonempty block has negative weight. This enumerates all possible sample labellings by <intervals> and attains the minimum <empirical misclassification risk>; sorting and a maximum-block scan are sufficient. The <time complexity> is $O(m\log m)$.
Back to article page
