Duplicate predictors do not enlarge the finite class

Let $(\mathcal{X},{\mathrm{\Sigma }}_X)$ be a measurable space, give $\{0,1\}$ its discrete sigma-algebra, and use binary zero-one loss. Let $L=(h_1,\dots ,h_K)$ be a nonempty ordered finite list of measurable classifiers, and let $\mathcal{H}$ be the set of its $q$ distinct classifiers, where $1\le q\le K$. For any labeled sample $S=((x_i,y_i){)}_{i=1}^m\in (\mathcal{X}\times \{0,1\}{)}^m$ with $m\ge 1$, put ${\widehat{R}}_S(h)=m^{-1}{\sum }_{i=1}^m\mathbf{1}\{h(x_i)\mathrm{\ne }{y}_i\}$ and, for a law $P$ on $\mathcal{X}\times \{0,1\}$, put $R_P(h)=P\{(x,y):h(x)\mathrm{\ne }y\}$. For every such sample and every finite tolerance $\eta \ge 0$, the finite-list ERM on $L$ returns the same classifier as the procedure on the list formed by retaining only the first occurrence of each distinct classifier. Thus the empirical minimum and selected prediction rule are unchanged by duplicate entries. Let ${\widehat{h}}_{\eta }(S)$ denote this finite-list ERM on $L$. For any such law $P$, $0\le \eta <ϵ<1$, $0<\delta <1$, and positive integer $m$ satisfying the following condition, if $S$ is an IID sample of size $m$ from $P$, then ${\mathbb{P}}_S\{R_P({\widehat{h}}_{\eta }(S))-{\inf }_{h\in \mathcal{H}}{R}_P(h)\le ϵ\}\ge 1-\delta$: $m\ge \frac{2(\log q+\log (2\mathrm{/}\delta ))}{(ϵ-\eta {)}^2}$ is sufficient for agnostic excess risk at most $ϵ$ with probability at least $1-\delta$; the bound depends on $q$, not the original list length $K$.

Realizable and agnostic PAC learning: defines the agnostic excess-risk guarantee used here.

Finite-list empirical risk minimization: selects the first list entry whose empirical risk is within the supplied tolerance of the finite-list minimum.

Finite-class realizable and agnostic sample complexity: gives the agnostic finite-class sample-size condition in terms of the number of distinct hypotheses.