Realizable and agnostic PAC learning

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.