Finite-class PAC learning and ERM guarantees — Examples

Let $d\ge 1$, let $\mathcal{X}=\{1,\dots ,d\}$ have the discrete sigma-algebra, and let $\mathcal{H}$ be the class of all binary lookup tables on $\mathcal{X}$. Then $\mathrm{\mid }\mathcal{H}\mathrm{\mid }=2^d$. For any $0<ϵ,\delta <1$, the exact ERM is realizable $(ϵ,\delta )$-PAC at every realizable law when $m\ge \frac{d\log 2+\log (1\mathrm{/}\delta )}{ϵ},$ and is agnostic $(ϵ,\delta )$-PAC at every law when $m\ge \frac{2(d\log 2+\log (2\mathrm{/}\delta ))}{{ϵ}^2}\mathrm{.}$ The agnostic condition uses the same class and binary zero-one loss; these are sufficient sample sizes.

Realizable and agnostic PAC learning: defines the realizable and agnostic PAC probability guarantees used here.

Finite-class realizable and agnostic sample complexity: gives the realizable and agnostic finite-class sample-size conditions.

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.

Let $\mathcal{X}=\{a,b\}$ have the discrete sigma-algebra, and let $P$ assign probability $1\mathrm{/}2$ to each of $(a,0)$ and $(b,0)$. Let $h_0(a)=h_0(b)=0$ and $h_1(a)=0$, $h_1(b)=1$, so $\mathcal{H}=\{h_1,h_0\}$ is realizable by $h_0$. Run exact finite-list ERM on the ordered list $(h_1,h_0)$. For every integer $m\ge 1$, if $S=((X_1,Y_1),\dots ,(X_m,Y_m))$ is an IID sample from $P$, the event $S=((a,0),\dots ,(a,0))$ has probability $2^{-m}$; on this event $h_1$ has empirical risk zero and population risk $1\mathrm{/}2$, and the tie-breaking rule returns $h_1$. Thus zero training error does not imply zero population risk on every sample, even for a realizable finite class; PAC guarantees bound a failure probability over samples.

Realizable and agnostic PAC learning: defines realizability and the probability-over-samples form of a PAC guarantee.

Finite-list empirical risk minimization: returns the first exact minimizer in the given order when tolerance is zero.