Binary learning minimax excess risk

Let $(\mathcal{X},\mathrm{\Sigma })$ be a measurable instance space and let $\mathcal{H}$ be a nonempty class of measurable functions $h:\mathcal{X}\to \{0,1\}$. Give $\{0,1\}$ its full power-set sigma-algebra; all joint and sample spaces below carry the corresponding product sigma-algebras. For a finite set of distinct points $T=\{x_1,\dots ,x_n\}$, its indexed trace family is ${\mathcal{F}}_{\mathcal{H},T}:=\{\{j\in [n]:h(x_j)=1\}:h\in \mathcal{H}\}\subseteq \mathcal{P}([n])\mathrm{.}$ The set $T$ is shattered by $\mathcal{H}$ when ${\mathcal{F}}_{\mathcal{H},T}=\mathcal{P}([n])$, and $\mathrm{VCdim}(\mathcal{H})$ is the supremum of the integers $n\ge 0$ for which some $n$ distinct points are shattered; the value is $+\mathrm{\infty }$ if these integers are unbounded. This definition is independent of the chosen ordering of $T$, since a reordering bijects the index sets and all their subsets.

For a probability law $D$ on $\mathcal{X}\times \{0,1\}$, the zero-one risk of a measurable binary predictor $g$ is $R_D(g):=D\{(x,y):g(x)\mathrm{\ne }y\}\in [0,1]$, and the class benchmark is $R_D^{\ast }(\mathcal{H}):={\inf }_{h\in \mathcal{H}}{R}_D(h)\in [0,1]$. The class excess risk of $g\in \mathcal{H}$ is ${\mathrm{\Delta }}_D(g):=R_D(g)-R_D^{\ast }(\mathcal{H})\in [0,1]$; no attainment of the infimum is asserted. A law $D$ is realizable by $\mathcal{H}$ when there is an $f\in \mathcal{H}$ with $D\{(x,y):y=f(x)\}=1$. For such a pair $(D,f)$, define its target risk by $R_D(g,f):=D_X\{x:g(x)\mathrm{\ne }f(x)\}$, where $D_X:=D\circ {\pi }_X^{-1}$ is the instance marginal under the projection ${\pi }_X(x,y)=x$. On the probability-one event $Y=f(X)$, the indicators of $g(X)\mathrm{\ne }Y$ and $g(X)\mathrm{\ne }f(X)$ agree; hence $R_D(g)=R_D(g,f)$ for every measurable binary $g$, and $R_D^{\ast }(\mathcal{H})=0$.

Let $\mathcal{D}$ be the class of all probability laws on $\mathcal{X}\times \{0,1\}$, and let ${\mathcal{D}}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}}(\mathcal{H}):=\{D\in \mathcal{D}:\text{there is }f\in \mathcal{H}\text{ with }D\{(x,y):y=f(x)\}=1\}$. For integer $m\ge 1$, an admissible possibly randomized learner $A$ is a rule that depends on $\mathcal{H}$ and $m$, not on $D$. Its seed space and law are fixed as part of $A$, independently of $D$: a probability space $({\mathrm{\Omega }}_A,{\mathcal{F}}_A,{\nu }_A)$ and a seed $U\sim {\nu }_A$ independent of the sample. Given an ordered sample $S\in (\mathcal{X}\times \{0,1\}{)}^m$, $A(S,U)$ outputs a measurable member of $\mathcal{H}$. For every fixed $x\in \mathcal{X}$, the evaluation $(S,U)\mapsto A(S,U)(x)$ must be measurable on $((\mathcal{X}\times \{0,1\}{)}^m\times {\mathrm{\Omega }}_A,(\mathrm{\Sigma }\otimes 2^{\{0,1\}}{)}^{\otimes m}\otimes {\mathcal{F}}_A)$, and for every $D\in \mathcal{D}$ the risk $R_D(A(S,U))$ must be measurable as a function of the sample and seed. The sample law $D^m$ is the $m$-fold product law, so its coordinates are independent and each has law $D$. Probabilities and expectations involving $A$ use the product law $D^m\otimes {\nu }_A$. Let ${\mathcal{A}}_m(\mathcal{H})$ denote this class of learners, and write $A(S)$ for $A(S,U)$ when the random seed is suppressed. These measurability conditions make each displayed expectation and probability well defined. Define the expected minimax excess risks by ${\mathfrak{M}}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}}(m,\mathcal{H}):={\inf }_{A\in {\mathcal{A}}_m(\mathcal{H})}{\sup }_{D\in {\mathcal{D}}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}}(\mathcal{H})}{\mathbb{E}}_{S\sim D^m,A}{R}_D(A(S)),$ ${\mathfrak{M}}_{\mathrm{a}\mathrm{g}\mathrm{n}}(m,\mathcal{H}):={\inf }_{A\in {\mathcal{A}}_m(\mathcal{H})}{\sup }_{D\in \mathcal{D}}{\mathbb{E}}_{S\sim D^m,A}[R_D(A(S))-R_D^{\ast }(\mathcal{H})]\mathrm{.}$ For a tolerance $\eta \ge 0$, their high-probability tail versions are ${\mathfrak{T}}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}}(m,\mathcal{H},\eta ):={\inf }_{A\in {\mathcal{A}}_m(\mathcal{H})}{\sup }_{D\in {\mathcal{D}}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}}(\mathcal{H})}{\mathrm{Pr}}_{S\sim D^m,A}\{R_D(A(S))>\eta \},$ ${\mathfrak{T}}_{\mathrm{a}\mathrm{g}\mathrm{n}}(m,\mathcal{H},\eta ):={\inf }_{A\in {\mathcal{A}}_m(\mathcal{H})}{\sup }_{D\in \mathcal{D}}{\mathrm{Pr}}_{S\sim D^m,A}\{R_D(A(S))-R_D^{\ast }(\mathcal{H})>\eta \}\mathrm{.}$ The lower bounds below are high-probability statements; their expectation consequences follow by integrating the nonnegative excess risk.

Supervised prediction problems: fixes the measurable instance space, label space, and measurable predictors; this definition specializes its labels and actions to $\{0,1\}$.

Population and empirical risk: defines population risk as the integral of the loss under the joint law; for zero-one loss this is $D\{g(X)\mathrm{\ne }Y\}$.

Population and empirical risks are measurable: composition with a fixed measurable predictor makes its loss measurable, so the zero-one risk above is a defined probability; measurability of a random learner's risk is separately required in this definition.

Shattering and the Vapnik–Chervonenkis dimension of a set family: a family $\mathcal{F}\subseteq \mathcal{P}([n])$ shatters $T\subseteq [n]$ exactly when its trace family $\mathcal{F}{\mathrm{\mid }}_T$ equals $\mathcal{P}(T)$; here the trace family is formed only after indexing distinct points of the finite set.

The disagreement and realizability events above are measurable: for measurable binary predictors $g,f$, their disagreement set in $\mathcal{X}\times \{0,1\}$ is a union of the measurable rectangles $g^{-1}(\{0\})\times \{1\}$ and $g^{-1}(\{1\})\times \{0\}$; the agreement event is the corresponding opposite union. The definitions and lower-bound constructions use finite binary labels and finite support; they require no conditional-label kernel, measurable selector, or Axiom of Choice. No Sauer–Shelah trace count is used.