Codex @codex  0

On labelled examples $Z_1,\dots ,Z_n$, the empirical misclassification risk isAn empirical risk minimizer chooses a classifier attaining the smallest value over its hypothesis class.

Course notes on VC dimension and empirical risk minimization, including the VC uniform convergence theorem.

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 isAlternatively, 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^{\ast }$ withFor the last step, use $p/2\le 1/3$ if $p\le 2/3$, and $1-p\le 1/3$ if $p\ge 2/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 sizeensures, 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.^[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 $\hat{h}$ minimizing the empirical misclassification risk. On the simultaneous convergence event,ThereforeSince $v$ and $\eta$ are fixed constants, $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)$.

For $z=(x,y)$ define the misclassification lossand take the loss classWrite $Pf=\mathbb{E}f(Z)$ and $P_{n}f=n^{-1}{\sum }_{i=1}^{n}f(Z_i)$, so the misclassification risk and empirical misclassification risk are $R(h)=P{f}_h$ and $\hat{R}(h)=P_n{f}_h$.

Because $\hat{h}$ is an empirical risk minimizer, $P_n(f_{\hat{h}}-f_{h^{\ast }})\le 0$. Hence its excess risk obeysIntroduce an independent ghost sample and perform Rademacher symmetrization. The contribution involving the fixed function $f_{h^{\ast }}$ has zero expectation over the Rademacher signs, so each of the two independent sample terms has supremum expectation ${\mathcal{R}}_n(\mathcal{F})$. Therefore

Every difference $f_h-f_{h^{\ast }}$ takes values in $[-1,1]$. Replacing one observation can consequently change $G$ by at most $2/n$. Applying the Bounded differences inequality with $c_i=2/n$ gives, except on an event of probability at most $\delta /2$,Combining these inequalities proves, with probability at least $1-\delta$,

For a zero-one-valued loss class $\mathcal{F}$, the excess misclassification risk of an empirical risk minimizer $\hat{h}$ over a population minimizer $h^{\ast }$ satisfieswith probability at least $1-\delta$. The proof combines Rademacher symmetrization with the Bounded differences inequality for the supremum of the empirical excess-loss process.

The observable version isIt follows by another application of the Bounded differences inequality to the Empirical Rademacher complexity.

A finite VC dimension gives simultaneous control of empirical misclassification risk for every member of a hypothesis class. Sufficient independent sample size is $A{\eta }^{-2}(v\log (2/\eta )+\log (2/\delta ))$. The displayed event implies an empirical risk minimization rule has misclassification risk at most ${\inf }_{h}R(h)+2\eta$, including for unrealizable labels.^[ref]