Finite-class PAC learning and ERM guarantees

Let $(\mathcal{X},{\mathrm{\Sigma }}_X)$ be a measurable instance space, let the binary label space $\{0,1\}$ have its discrete sigma-algebra, and let $\mathcal{H}$ be a finite nonempty class of measurable classifiers $h:\mathcal{X}\to \{0,1\}$. For a probability law $P$ on $\mathcal{X}\times \{0,1\}$, write $R_P(h)=P\{(x,y):h(x)\mathrm{\ne }y\}$ for the population zero-one risk. A sample of size $m\ge 1$ consists of $m$ independent observations with common law $P$; write ${\widehat{R}}_S(h)=m^{-1}{\sum }_{i=1}^m\mathbf{1}\{h(X_i)\mathrm{\ne }{Y}_i\}$ for its empirical zero-one risk. The law $P$ is realizable by $\mathcal{H}$ if some $h^{\ast }\in \mathcal{H}$ satisfies $R_P(h^{\ast })=0$.

Put $\mathcal{Z}=\mathcal{X}\times \{0,1\}$ with its product sigma-algebra. For fixed $m\ge 1$, a deterministic learner is a measurable map $A:{\mathcal{Z}}^m\to \mathcal{H}$, where the finite set $\mathcal{H}$ has its discrete sigma-algebra. For a law $P$ on $\mathcal{Z}$, let $S=(Z_1,\dots ,Z_m)$ be an IID sample with common law $P$, and write ${\mathbb{P}}_S$ for probability under its joint law. For $0<ϵ,\delta <1$, the learner is $(ϵ,\delta )$-PAC realizable if, for every law $P$ realizable by $\mathcal{H}$, ${\mathbb{P}}_S\{R_P(A(S))\le ϵ\}\ge 1-\delta$. It is agnostic $(ϵ,\delta )$-PAC if, for every law $P$ on $\mathcal{Z}$, ${\mathbb{P}}_S\{R_P(A(S))-{\inf }_{h\in \mathcal{H}}{R}_P(h)\le ϵ\}\ge 1-\delta$. A randomized learner uses a measurable probability space $(\mathcal{U},{\mathrm{\Sigma }}_U,Q)$ and a measurable output map $A:{\mathcal{Z}}^m\times \mathcal{U}\to \mathcal{H}$, with a seed $U\sim Q$ independent of $S$; in both criteria replace $A(S)$ by $A(S,U)$ and ${\mathbb{P}}_S$ by the joint probability ${\mathbb{P}}_{S,U}$. All risks and the infimum are finite because the zero-one loss is bounded by one. These definitions impose no computational-efficiency claim.

Supervised prediction problems: a supervised problem specifies measurable instance and label spaces, a joint law, measurable predictors, and a measurable loss.

Population and empirical risk: population risk is the expected loss and empirical risk is the sample average of that loss.

Identical distribution and IID families: IID observations are mutually independent and have the same law.

Let $(\mathcal{X},{\mathrm{\Sigma }}_X)$ be a measurable space, let $P$ be a probability law on $\mathcal{X}\times \{0,1\}$, and let $\mathcal{H}$ be a finite nonempty class of measurable classifiers $h:\mathcal{X}\to \{0,1\}$. Let $Z_i=(X_i,Y_i)$, $1\le i\le m$, be IID with law $P$, where $m\ge 1$, and define $R_P(h)=P\{h(X)\mathrm{\ne }Y\}$ and ${\widehat{R}}_S(h)=m^{-1}{\sum }_{i=1}^m\mathbf{1}\{h(X_i)\mathrm{\ne }{Y}_i\}$. With natural logarithms, for $0<\delta <1$ put

$a_{m,\mathcal{H},\delta }:=\sqrt{\frac{\log \mathrm{\mid }\mathcal{H}\mathrm{\mid }+\log (2\mathrm{/}\delta )}{2m}}\mathrm{.}$

Then, with probability at least $1-\delta$, both $\mathrm{\mid }{R}_P(h)-{\widehat{R}}_S(h)\mathrm{\mid }\le a_{m,\mathcal{H},\delta }$ for every $h\in \mathcal{H}$ and

$R_P({\widehat{h}}_{\eta }(S))-{\inf }_{h\in \mathcal{H}}{R}_P(h)\le 2a_{m,\mathcal{H},\delta }+\eta ,$

for each fixed finite tolerance $\eta \ge 0$, where ${\widehat{h}}_{\eta }$ is the measurable finite-list empirical-risk selector applied with tolerance $\eta$ to an ordered list containing every member of $\mathcal{H}$ exactly once. In particular, exact ERM ($\eta =0$) has excess risk at most $2a_{m,\mathcal{H},\delta }$. The conclusion is agnostic: it assumes no zero-risk classifier. No form of the Axiom of Choice is assumed.

Realizable and agnostic PAC learning: defines realizable and agnostic PAC learning for finite measurable binary classes.

Population and empirical risk: defines population and empirical risk as expected loss and sample-average loss.

Uniform deviation bound for a finite unit-range class: gives the choice-free two-sided tail bound for finite classes of measurable functions in $[0,1]$.

The natural logarithm as the inverse of the exponential function: defines $\log$ as the inverse of $\exp$ on positive inputs.

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: establishes that $\log$ is increasing and obeys the product, quotient, and reciprocal laws.

Finite-list empirical risk minimization: specifies the deterministic finite-list ERM selector.

The finite-list ERM selector is measurable: proves that selector measurable and exact or approximate ERM.

Let $\mathcal{H}$ be a finite nonempty class of measurable classifiers $h:\mathcal{X}\to \{0,1\}$ on a measurable instance space, and let $P$ be a law on $\mathcal{X}\times \{0,1\}$ for which some $h^{\ast }\in \mathcal{H}$ has zero population zero-one risk. Let $Z_i=(X_i,Y_i)$, $1\le i\le m$, be IID with law $P$, and let ${\widehat{h}}_0(S)$ be the measurable exact ERM returned by the finite-list selector on an ordered enumeration of $\mathcal{H}$. For $0<ϵ,\delta <1$ and integer $m\ge 1$, if

$m\ge \frac{\log \mathrm{\mid }\mathcal{H}\mathrm{\mid }+\log (1\mathrm{/}\delta )}{ϵ},$

then ${\mathbb{P}}_S\{R_P({\widehat{h}}_0(S))\le ϵ\}\ge 1-\delta$. This is a realizable guarantee; it makes no claim for distributions without a zero-risk member of $\mathcal{H}$. The proof is choice-free.

Realizable and agnostic PAC learning: defines realizability by existence of a zero-risk classifier and the realizable PAC criterion.

Finite-list empirical risk minimization: supplies an exact finite-list ERM selector.

The finite-list ERM selector is measurable: establishes the selector’s measurability and exact-minimizer property.

The natural logarithm as the inverse of the exponential function: defines the natural logarithm as the inverse of the exponential on positive reals.

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.