Finite-class realizable and agnostic sample complexity

Let $\mathcal{H}$ be a finite nonempty class of measurable binary classifiers, put $N=\mathrm{\mid }\mathcal{H}\mathrm{\mid }$, and let $0<ϵ,\delta <1$. For IID samples, the finite-list exact ERM is realizable $(ϵ,\delta )$-PAC whenever the law is realizable by $\mathcal{H}$ and

$m\ge \frac{\log N+\log (1\mathrm{/}\delta )}{ϵ}\mathrm{.}$

For arbitrary laws, a finite-list $\eta$-approximate ERM with fixed $0\le \eta <ϵ$ is agnostic $(ϵ,\delta )$-PAC whenever

$m\ge \frac{2(\log N+\log (2\mathrm{/}\delta ))}{(ϵ-\eta {)}^2}\mathrm{.}$

Here $m$ is a positive integer and logarithms are natural. In particular, exact agnostic ERM ($\eta =0$) has the sufficient sample size $m\ge 2(\log N+\log (2\mathrm{/}\delta ))\mathrm{/}{ϵ}^2$. These are sufficient upper bounds; they do not assert optimality or computational efficiency.

Realizable and agnostic PAC learning: defines the two PAC criteria and includes learner randomness in their probability statements when present.

Finite-class realizable PAC bound: proves the realizable finite-class sample-size condition.

Finite-class agnostic ERM bound: proves the agnostic ERM excess-risk bound used to obtain the agnostic sample size.

The natural logarithm as the inverse of the exponential function: defines the natural logarithm used in the sample-size formulas.

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: supplies the monotonicity and product law used in the sample-size comparison.