Exact labels, slow version-space shrinkage, and abstention limits

Let $\mathcal{X}=\{a,b\}$ with its full sigma-algebra and label set $\{0,1\}$ with its discrete sigma-algebra. Take the joint law $P={\delta }_{(a,0)}$, use zero-one loss $\mathrm{\ell }(\widehat{y},y)=\mathbf{1}\{\widehat{y}\mathrm{\ne }y\}$, and set $D_X=P_X={\delta }_a$, where $P_X$ is the input marginal of $P$. Define $\mathcal{H}=\{h_0,h_1\}$ by $h_0(a)=h_0(b)=0$ and $h_1(a)=0$, $h_1(b)=1$. For pool $U=(b)$, choose target $h^{\ast }=h_1$ and exact oracle $\mathcal{O}=h_1$. The zero-one error events are measurable by [F1] and [F3], and [F2] defines their risks as their $P$-probabilities. Both risks are zero, so [F4] declares the law realizable by either classifier. Yet $h_0$ and $h^{\ast }$ give different labels at the pool point $b$, whose $D_X$-probability is zero. Thus distributional realizability does not prescribe the label at every possible pool point; [F5]'s pointwise oracle condition is a genuinely stronger interface.

Let $\mathcal{X}=\{a\}$, $\mathcal{H}=\{h_0,h_1\}$ with $h_0(a)=0$ and $h_1(a)=1$, target $h^{\ast }=h_0$, and budget $b\ge 1$. If the filtering update is fed the noisy response $1$ at the initial disagreement $a$, [F6] replaces $V=\{h_0,h_1\}$ by $\{h_1\}$, deleting the true target. Hence the invariant proof cannot be extended to arbitrary noisy responses.

For any $m\ge 2$, take $\mathcal{X}=\{x_1,\dots ,x_m\}$, target $h_{\ast }(x_j)=1$, alternatives $h_i(x_j)=0$ exactly when $j=i$, pool $(x_1,\dots ,x_m)$, and budget $b\ge m$. Before query $i$, the version space is $\{h_{\ast },h_i,\dots ,h_m\}$: this is true initially and, at $x_i$, the exact positive label removes only $h_i$. Thus all $m$ indices are queried and $q=m=\mathrm{\mid }\mathcal{H}\mathrm{\mid }-1$.

Set $m=2^k-1$ for integers $k\ge 2$. Then $\mathrm{\mid }\mathcal{H}\mathrm{\mid }=2^k$ and $q=2^k-1$. By repeated application of [F10]'s product law, $\log \mathrm{\mid }\mathcal{H}\mathrm{\mid }=k\log 2$, and strict increase with $2>1$ gives $\log 2>\log 1=0$. The ratio $q\mathrm{/}(k\log 2)$ is at least $2^{k-1}\mathrm{/}(k\log 2)$; the latter is unbounded because its consecutive-term ratio is $2k\mathrm{/}(k+1)\ge 4\mathrm{/}3$. Therefore no uniform constant multiple of $\log \mathrm{\mid }\mathcal{H}\mathrm{\mid }$ bounds the query count, while [F7]'s logarithmic guarantee remains valid when its branch-shrink premise holds.

Let $\mathcal{X}=\{a\}$, $\mathcal{H}=\{h_0,h_1\}$ with $h_0(a)=0$, $h_1(a)=1$, target $h^{\ast }=h_0$, current version space $V=\mathcal{H}$, and $D_X(\{a\})=1$. The initial version space is consistent with the exact-target model. Then $\mathrm{DIS}(V)=\mathcal{X}$, so [F8] gives abstention probability $D_X(\mathrm{DIS}(V))=1$ although $\mathrm{\mid }V\mathrm{\mid }=2$. This verifies that finiteness alone does not force the disagreement mass to be small. All witnesses are explicit finite constructions, as stated in [A1].