A realizable VC minimax lower bound

Since $d$ is the finite VC dimension, choose distinct $x_0,x_1,\dots ,x_{d-1}$ shattered by $\mathcal{H}$. For each of the finitely many label vectors $\theta \in \{0,1{\}}^d$, shattering supplies a target $f_{\theta }\in \mathcal{H}$ with those labels on these points; finite choice suffices for this finite family. Put $ϵ=(d-1)\mathrm{/}(32m)$ and define the finite mixture $\mu =(1-8ϵ){\delta }_{x_0}+{\sum }_{i=1}^{d-1}\frac{8ϵ}{d-1}{\delta }_{x_i}$. The range on $m$ gives $8ϵ=(d-1)\mathrm{/}(4m)\le 1$, so all mixture weights are nonnegative and sum to one. For each $\theta$, let $D_{\theta }$ be the law of $(X,f_{\theta }(X))$ for $X\sim \mu$.

Let $M$ count sample positions drawn from the rare atoms $x_1,\dots ,x_{d-1}$. Then $M\sim \mathrm{Bin}(m,8ϵ)$ and ${\mu }_0:=\mathbb{E}M=(d-1)\mathrm{/}4\ge 1\mathrm{/}4$. Since $e^p={\sum }_{j=0}^{\mathrm{\infty }}{p}^j\mathrm{/}j!\ge 1+p$ for $p\ge 0$, $\mathbb{E}{2}^M=(1+8ϵ{)}^m\le e^{{\mu }_0}$. For any nonnegative random variable $X$ and $b>0$, $\mathbb{E}X\ge b\mathrm{Pr}\{X\ge b\}$ because $X\ge b{\mathbf{1}}_{\{X\ge b\}}$; apply this to $X=2^M$ and $b=2^{2{\mu }_0}$. On $\{M\ge 2{\mu }_0\}$, $2^M\ge 2^{2{\mu }_0}$, hence $\mathrm{Pr}\{M\ge 2{\mu }_0\}\le e^{{\mu }_0-2{\mu }_0\log 2}\le e^{-{\mu }_0\mathrm{/}3}$, where $\log 2\ge 2\mathrm{/}3$ because $g(x)=\log x-2(x-1)\mathrm{/}(x+1)$ has $g(1)=0$ and $g^{\mathrm{\prime }}(x)=(x-1{)}^2\mathrm{/}(x(x+1{)}^2)\ge 0$ for $x\ge 1$. Since $2{\mu }_0=(d-1)\mathrm{/}2$, $\mathrm{Pr}\{M\le (d-1)\mathrm{/}2\}\ge 1-e^{-{\mu }_0\mathrm{/}3}\ge 1-e^{-1\mathrm{/}12}\ge 1\mathrm{/}13$; the last inequality follows from $e^{1\mathrm{/}12}\ge 1+1\mathrm{/}12=13\mathrm{/}12$.

Fix any vector of sample atom indices and observed labels for which $M\le (d-1)\mathrm{/}2$. At least $(d-1)\mathrm{/}2$ rare atoms were not observed. Under the uniform prior on $\theta$, each unseen label ${\theta }_i$ is still an independent fair bit, independent of the learner's output at $x_i$, because the learner depends only on the observed sample and independent internal randomness. Therefore, if $W$ is the learner's risk contribution from $x_1,\dots ,x_{d-1}$, then ${\mathbb{E}}_{\theta ,A}[W\mid \text{observed data}]\ge \frac{1}{2}\frac{d-1}{2}\frac{8ϵ}{d-1}=2ϵ$, while $0\le W\le 8ϵ$. Applying [F2] to $W\mathrm{/}(8ϵ)$ at $t=1\mathrm{/}8$ yields ${\mathrm{Pr}}_{\theta ,A}\{W>ϵ\mid \text{observed data}\}\ge 1\mathrm{/}7$.

Each $D_{\theta }$ is realizable by $f_{\theta }$, so [F4] gives $R_{D_{\theta }}^{\ast }(\mathcal{H})=0$. By [F3] and the event $Y=f_{\theta }(X)$ of probability one, the zero-one risk and target risk of the learner's output agree. The full target risk is at least $W$. Averaging step 1.3 over sample locations and labels, then using step 1.2, gives ${\mathrm{Pr}}_{\theta ,S\sim D_{\theta }^m,A}\{R_{D_{\theta }}(A(S),f_{\theta })>ϵ\}\ge \frac{1}{7}\cdot \frac{1}{13}=\frac{1}{91}>\frac{1}{100}$. This is an average over the finite set $\{0,1{\}}^d$, so at least one $\theta$ has conditional failure probability at least $1\mathrm{/}91$. Its $D_{\theta }$ and $f_{\theta }$ satisfy the statement.