Proof. If \(\mathcal{H}\) satisfies exact exterior separation, then for every finite nonempty realizable \(S\) we may take the single hypothesis \(h_{S,1}=\operatorname{CLOS}_{\mathcal{H}}\!\left(S\right)\); this proves uniform exterior separability with \(M\!\left(\eta\right)=1\) for every \(\eta>0\).

If \(\mathcal{H}\) satisfies uniform exterior separability, fix \(\eta>0\) and write \(M \mathrel{\vcenter{:}}= M\!\left(\eta\right)\) for the bound from Definition [def:ues]. For each finite nonempty realizable \(S\), let \(\mu_{S,\eta}\) be the uniform distribution on the corresponding family \(h_{S,1},\dots,h_{S,M}\). Then for every \(x \notin \operatorname{CLOS}_{\mathcal{H}}\!\left(S\right)\), \[\Pr_{h \sim \mu_{S,\eta}}\left(x \in h\right) = \frac{1}{M} \left| \left\{i : x \in h_{S,i}\right\} \right| \leq \eta\,,\] so distributional exterior separability holds.

Finally, assume distributional exterior separability, fix a finite nonempty realizable \(S\), and let \(F \subseteq \mathcal{X}\setminus \operatorname{CLOS}_{\mathcal{H}}\!\left(S\right)\) be finite. Choose \(\eta < 1/\left| F \right|\) and let \(\mu_{S,\eta}\) witness Definition [def:des]. Then \[\mathbb{E}_{h \sim \mu_{S,\eta}}\left[\left| h \cap F \right|\right] = \sum_{x \in F} \Pr_{h \sim \mu_{S,\eta}}\left(x \in h\right) \leq \left| F \right|\eta < 1\,.\] Hence some \(h \in \mathcal{H}_S\) satisfies \(\left| h \cap F \right|=0\), proving finite exterior separability. It remains to prove the strictness of the first and third implications. We divide this into the two propositions below.

 ◻

Proof. Let \(\mathcal{X}=\{0,1,2\}\) and \(\mathcal{H}=\left\{\{0,1\},\{0,2\}\right\}\). Then \(\mathcal{H}_{\cap} \mathrel{\vcenter{:}}= \left\{\{0\},\{0,1\},\{0,2\}\right\}\). Note that \(\operatorname{VCdim}(\mathcal{H}_{\cap})=1\). Therefore, by 1, \(\mathcal{H}\) is improperly positive-only learnable. However, let \(S=\{0\}\) and \(F=\{1,2\}\). Note that \(F\cap \operatorname{CLOS}_{\mathcal{H}}(S)=F\cap S=\varnothing\), but there is no \(h\in\mathcal{H}\) such that \(S\subseteq h\) and \(h\cap F=\varnothing\). Thus, \(\mathcal{H}\) does not satisfy finite exterior separability (6), and, by [prop:hierarchy-appendix], it does not satisfy uniform exterior separability either ([def:ues]). In [thm:main], we showed that any class that does not satisfy uniform exterior separability is not properly positive-only learnable. ◻

Proof of 6. In 3, we introduced a concept class \(\mathcal{H}_{\mathrm{spr}}\) with \(\operatorname{VCdim}(\mathcal{H}_{\mathrm{spr}}) = 1\) that satisfies uniform exterior separability ([def:ues]), but does not satisfy exact exterior separation ([def:ees]). From [thm:random-characterization], this implies that \(\mathcal{H}_{\mathrm{spr}}\) is properly learnable from positive-only examples. However, natarajan1987learning? shows that exact exterior separation is necessary for properly learning with one-sided error. ◻

Proof of 1. This is an immediate implication of the following (standard) second-order uniform convergence result; cf. Section 5.1.2 in Boucheron_Bousquet_Lugosi_2005?.

Indeed, let \(\gamma \mathrel{\vcenter{:}}= \frac{\varepsilon}{16}\). Apply the standard second-order uniform-convergence theorem with reference set \(A^\star = \varnothing\) and confidence parameter \(\delta = \frac{1}{2}\). Then for \[m = O\!\left(\frac{d\log{\frac{1}{\gamma}}}{\gamma}\right) = O\!\left(\frac{d\log{\frac{1}{\varepsilon}}}{\varepsilon}\right)\,,\] there exists a realization \(z_1,\dots,z_m\in\Omega\) such that every \(A\in\mathcal{H}\) satisfies \[\frac{1}{m}\left| \left\{i \in \left\{1,\dots,m\right\} : z_i \in A\right\} \right| \leq \nu\left(A\right)+\sqrt{\nu\left(A\right)\gamma}+\gamma\,.\] If now \(\nu\left(A\right)\leq \frac{\varepsilon}{2}\), then \[\frac{1}{m}\left| \left\{i \in \left\{1,\dots,m\right\} : z_i \in A\right\} \right| \leq \frac{\varepsilon}{2} + \sqrt{\frac{\varepsilon}{2}\cdot \frac{\varepsilon}{16}} + \frac{\varepsilon}{16} \leq \varepsilon\,.\] Setting \(M \mathrel{\vcenter{:}}= m\) proves the claim. ◻

Proof of [thm:distributional-implies-uniform]. Recall that \(d^\star\) is finite by the duality theorem (2). Fix \(0<\eta<1\) and a finite nonempty realizable set \(S \subseteq \mathcal{X}\). By distributional exterior separability ([def:des]), applied with parameter \(\frac{\eta}{2}\), there exists a probability distribution \(\mu\) supported on \(\mathcal{H}_S\) such that \[\sup_{x \notin \operatorname{CLOS}_{\mathcal{H}}\!\left(S\right)} \Pr_{h \sim \mu}\left(x \in h\right) \leq \frac{\eta}{2}\,.\] For each exterior point \(x \notin \operatorname{CLOS}_{\mathcal{H}}\!\left(S\right)\), define \[R_x^S \mathrel{\vcenter{:}}= \left\{h \in \mathcal{H}_S : x \in h\right\}\,,\] and let \[\mathcal{R}_S \mathrel{\vcenter{:}}= \left\{R_x^S : x \notin \operatorname{CLOS}_{\mathcal{H}}\!\left(S\right)\right\}\,.\] Observe that \(\mathcal{R}_S\) is obtained from \(\mathcal{H}^\star\) by restricting the domain from \(\mathcal{H}\) to \(\mathcal{H}_S\) and then discarding the concepts only containing non-exterior points. Therefore, it follows that \[\operatorname{VCdim}{}\!\left(\mathcal{R}_S\right) \leq \operatorname{VCdim}{}\!\left(\mathcal{H}^\star\right) = d^\star\,.\] Since every set in \(\mathcal{R}_S\) has \(\mu\)-measure at most \(\eta/2\), this is exactly the regime in which the second-order form of uniform convergence is useful. We use 1 to the concept class \(\mathcal{R}_S\) over the domain \(\mathcal{H}_S\), under the probability measure \(\mu\). Since \(\operatorname{VCdim}{}\!\left(\mathcal{R}_S\right)\leq d^\star\), this yields a multiset \[h_{S,1},\dots,h_{S,M\!\left(\eta\right)} \in \mathcal{H}_S \qquad \text{with} \qquad M\!\left(\eta\right) = O\!\left(\frac{d^\star \log{\frac{1}{\eta}}}{\eta}\right)\] such that every \(R \in \mathcal{R}_S\) with \(\mu\left(R\right)\leq \frac{\eta}{2}\) satisfies \[\frac{1}{M\!\left(\eta\right)} \left| \left\{i \in \left\{1,\dots,M\!\left(\eta\right)\right\} : h_{S,i} \in R\right\} \right| \leq \eta\,.\] Now fix any \(x \notin \operatorname{CLOS}_{\mathcal{H}}\!\left(S\right)\). Since \(R_x^S \in \mathcal{R}_S\) and \(\mu\left(R_x^S\right) = \Pr_{h \sim \mu}\left(x \in h\right) \leq \frac{\eta}{2},\) the above implies \[\frac{1}{M\!\left(\eta\right)} \left| \left\{i \in \left\{1,\dots,M\!\left(\eta\right)\right\} : x \in h_{S,i}\right\} \right| = \frac{1}{M\!\left(\eta\right)} \left| \left\{i : h_{S,i} \in R_x^S\right\} \right| \leq \eta\,.\] Since \(x\) was arbitrary, the family \(h_{S,1},\dots,h_{S,M\!\left(\eta\right)}\) witnesses UES at level \(\eta\). As the bound on \(M\!\left(\eta\right)\) depends only on \(\eta\) and \(d^\star\), this proves UES ([def:ues]). ◻

Proof. Observe that in [thm:distributional-implies-uniform] we have proved that under the assumption \(\operatorname{VCdim}(\mathcal{H}) < \infty,\) uniform exterior separability is equivalent to distributional exterior separability ([def:des]). We divide the proof into two parts, one for each direction of the claim.

-1em Part 1 (\(2 \Longrightarrow 1\)): Define the learner \(\mathcal{A}\) for any multi-set \(S_+\in \mathcal{X}^{[*]}\) as \[\mathcal{A}(S_+) \sim \mu_{S_+, \exp(-|S_+|)}\,.\] Fix \(\varepsilon,\delta \in (0,1)\), a distribution \(\mathcal{D}\) over \(\mathcal{X}\) and \(\ell \in \mathcal{H}\). Let \(S_+\sim \mathcal{D}_+^n\), for \(n \in \mathbb{N}\), and write \(d \mathrel{\vcenter{:}}= \operatorname{VCdim}{}\!\left(\mathcal{H}\right)\).

By the standard realizable VC bound applied to the positive distribution \(\mathcal{D}_+\) (see, e.g., BlumerEhrenfeuchtHausslerWarmuth1989?, shalev2014understanding?), there is a universal constant \(C > 0\) such that if \[n \geq \frac{C \left(d \ln{\frac{1}{\varepsilon}} + \ln{\frac{1}{\delta}}\right)}{\varepsilon},\] then with probability at least \(1-\frac{\delta}{2}\) every \(h \in \mathcal{H}\) such that \(\mathop{\mathrm{\mathrm{Domain}}}(S_+) \subseteq h\) satisfies \[\mathcal{D}_+\!\left(\ell \setminus h\right) \leq \frac{\varepsilon}{2}\,.\] Since \(\mathcal{D}\!\left(\ell \setminus h\right) = \mathcal{D}(\ell) \cdot \mathcal{D}_+\!\left(\ell \setminus h\right) \leq \mathcal{D}_+\!\left(\ell \setminus h\right)\), the same event implies \(\mathcal{D}\!\left(\ell \setminus h\right) \leq \frac{\varepsilon}{2}\) for every such \(h\).

Observe that, for every \(y \notin \operatorname{CLOS}_{\mathcal{H}}\!\left(S_+\right)\), and \(n \geq \ln \left(\frac{\delta \varepsilon}{4}\right)\) \[\mathbb{E}_{\mathcal{A}}\left[\mathbb{1} \left\{y \in \mathcal{A}(S_+)\right\}\right] \leq \exp(-n) \leq \frac{\varepsilon\delta}{4}\,.\] Because \(\operatorname{CLOS}_{\mathcal{H}}\!\left(S_+\right) \subseteq \ell\), every negative point lies outside the closure, and therefore by the DES property ([def:des]) \[\mathbb{E}_{\mathcal{A}}\left[\mathcal{D}\!\left(\mathcal{A}(S_+) \setminus \ell\right) \right] \leq \frac{\varepsilon\delta}{4}\,.\] Thus, \[\mathbb{E}_{\mathcal{S}_+ \sim \mathcal{D}_+^{n}, \mathcal{A}}\left[\mathcal{D}\!\left(\mathcal{A}(S_+) \setminus \ell\right) \right] \leq \frac{\varepsilon\delta}{4}\,.\] Markov’s inequality gives \[\Pr_{\mathcal{S}_+ \sim \mathcal{D}_+^{n}, \mathcal{A}} \left(\mathcal{D}\!\left(\mathcal{A}(S_+) \setminus \ell\right) > {\varepsilon/2}\right) \leq \frac{\delta}{2}\,.\] Combining this with the bound on false negatives, we obtain \[\Pr_{\mathcal{S}_+ \sim \mathcal{D}_+^{n}, \mathcal{A}}\left(\operatorname{err}_{\mathcal{D}}\!\left(\mathcal{A}(S_+),\ell\right) > \varepsilon\right) \leq \delta\,.\]

-1em Part 2 (\(1 \Longrightarrow 2\)): Fix a finite nonempty realizable set \(S \subseteq \mathcal{X}\) and a parameter \(\eta>0\). If \(\mathcal{X}\setminus \operatorname{CLOS}_{\mathcal{H}}\!\left(S\right)=\varnothing\), then any point mass on a concept in \(\mathcal{H}_S\) witnesses distributional exterior separability, so there is nothing to prove. Thus assume \(\mathcal{X}\setminus \operatorname{CLOS}_{\mathcal{H}}\!\left(S\right)\neq \varnothing\).

If \(\eta \geq 1\), the conclusion is again trivial, so assume \(\eta<1\). Choose and fix one concept \(h_S \in \mathcal{H}_S\). For each \(x \notin \operatorname{CLOS}_{\mathcal{H}}\!\left(S\right)\), choose \(\ell_x \in \mathcal{H}_S\) such that \(x \notin \ell_x\); this is possible by the definition of the closure. Let \[k \mathrel{\vcenter{:}}= \left| S \right|\,, \qquad \varepsilon\mathrel{\vcenter{:}}= \frac{1}{4k}\,, \qquad \delta \mathrel{\vcenter{:}}= \frac{\eta}{2}\,,\] and let \(n \mathrel{\vcenter{:}}= m{}_{\mathcal{H}}\!\left(\varepsilon,\delta\right)\) be the sample complexity of a proper learner \(\mathcal{A}\) at these parameters. Let \(U_S\) denote the uniform distribution on \(S\), and let \(\nu\) be the law of \(\mathcal{A}\left(S_+\right)\) when \[S_+\sim U_S^n\,.\] Fix any exterior point \(x \notin \operatorname{CLOS}_{\mathcal{H}}\!\left(S\right)\), consider distribution \(\mathcal{D}_x\) defined as \[\mathcal{D}_x(x)=\frac{1}{2} \qquad\text{and}\qquad \mathcal{D}_x(s)=\frac{1}{2k}\;\text{ for each } s\in S\,,\] and zero elsewhere. Also let \(\ell_x\) be any concept with \(x \notin \ell_x\) and \(S \subseteq \ell_x\). Observe that since \(x \notin \operatorname{CLOS}_{\mathcal{H}}\!\left(S\right)\) such \(\ell_x\) always exists. Also, \(\mathcal{D}_{+, S} \mathrel{\vcenter{:}}= U_S\). Hence the learner sees the same sample law \(U_S^n\) for every such \(x\), so its output law is always \(\nu\).

Now, if \(x \in \mathcal{A}\left(S_+\right)\), then \(x\) is a false positive under the target \(\ell_x\), and therefore \[\operatorname{err}_{\mathcal{D}_x}\left(\mathcal{A}\left(S_+\right),\ell_x\right) \geq \mathcal{D}_x(x)=\frac{1}{2}>\varepsilon\,.\] By the PAC guarantee, \[\nu\!\left(\left\{h:x\in h\right\}\right) = \Pr_{S_+\sim U_S^n, \mathcal{A}}\left(x\in \mathcal{A}\left(S_+\right)\right) \leq \delta\,,\] where the probability is over \(S_+\sim U_S^n\) and the learner’s internal randomness. Likewise, if \(\mathcal{A}\left(S_+\right)\notin \mathcal{H}_S\), then it misses some point \(s\in S\), and since \(s\in \ell_x\) and \(\mathcal{D}_x(s)=1/\left(2k\right)>\varepsilon\), this again forces \[\operatorname{err}_{\mathcal{D}_x}\left(\mathcal{A}\left(S_+\right),\ell_x\right)>\varepsilon\,.\] Hence \[\nu\!\left(\mathcal{H}\setminus \mathcal{H}_S\right) = \Pr\left(\mathcal{A}\left(S_+\right)\notin \mathcal{H}_S\right) \leq \delta\,,\] where again the probability is over \(S_+\sim U_S^n\) and over the learner’s internal randomness. Define a probability distribution \(\mu\) on \(\mathcal{H}_S\) by moving all \(\nu\)-mass outside \(\mathcal{H}_S\) onto the single concept \(h_S\): \[\mu(A) \mathrel{\vcenter{:}}= \nu\!\left(A\cap \mathcal{H}_S\right) + \nu\!\left(\mathcal{H}\setminus \mathcal{H}_S\right)\mathbb{1}\left\{h_S\in A\right\}\,, \qquad A\subseteq \mathcal{H}\,.\] Then \(\mu\) is supported on \(\mathcal{H}_S\), and for every \(x \notin \operatorname{CLOS}_{\mathcal{H}}\!\left(S\right)\), \[\Pr_{h\sim\mu}\left(x\in h\right) \leq \nu\!\left(\left\{h:x\in h\right\}\right) + \nu\!\left(\mathcal{H}\setminus \mathcal{H}_S\right) \leq \delta+\delta = \eta\,.\] Thus \(\mu\) witnesses distributional exterior separability for the pair \(\left(S,\eta\right)\). Since \(S\) and \(\eta\) were arbitrary, \(\mathcal{H}\) satisfies distributional exterior separability. ◻

Proof of [thm:few-random-bits-suffice]. Observe that the second item implies the first immediately since a learner using finitely many random bits is a randomized learner. Below we prove the converse.

Assume that \(\mathcal{H}\) is properly PAC learnable from positive-only examples by a randomized learner. Then, due to [thm:random-characterization], \(\operatorname{VCdim}{}\!\left(\mathcal{H}\right)<\infty\) and \(\mathcal{H}\) satisfies distributional exterior separability. Now, applying the quantitative version of [thm:distributional-implies-uniform] from 8.3, implies that for every \(\eta \in (0,1)\) and every finite nonempty realizable set \(S\subseteq \mathcal{X}\), there are hypotheses \(h_{S,1},\dots,h_{S,M\!\left(\eta\right)} \in \mathcal{H}_S\) such that \(M\!\left(\eta\right) = O\!\left( (\frac{\left(d^\star+1\right)}{\eta})\, \cdot\,\log{\frac{1}{\eta}} \right)\) and \[\sup_{x\notin \operatorname{CLOS}_{\mathcal{H}}\!\left(S\right)} \frac{1}{M\!\left(\eta\right)} \left| \left\{ i\in\left\{1,\dots,M\!\left(\eta\right)\right\}: x\in h_{S,i} \right\} \right| \leq \eta\,.\] Fix \(\varepsilon,\delta \in (0,1)\) and set \[\eta \mathrel{\vcenter{:}}= \frac{\varepsilon\delta}{8}\,, \qquad\text{and}\qquad M \mathrel{\vcenter{:}}= M\!\left(\eta\right)\,.\] For every finite nonempty realizable set \(S\), fix a list \(h_{S,1},\dots,h_{S,M} \in \mathcal{H}_S\) at scale \(\eta\) (as above).

-1em Learning Algorithm. Let \(K\) be a power of two satisfying \(M \leq K < 2M .\) The learner uses \(\log_2 K\) random bits to draw a uniform seed \(J \sim U_{\left\{1,\dots,K\right\}} .\) It then converts this seed into an index \(I(J) \mathrel{\vcenter{:}}= 1+\left(J-1 \bmod M\right) \in \left\{1,\dots,M\right\}.\) Thus, for every \(i\in\left\{1,\dots,M\right\}\), \[\Pr\left(I(J)=i\right) \leq \frac{2}{M}\,.\]

Given a positive multiset \(S_+\in\mathcal{X}^{[*]}\), let \(T \mathrel{\vcenter{:}}= \mathop{\mathrm{\mathrm{Domain}}}\!\left(S_+\right)\) be the set of distinct examples in \(S_+\). If \(T\) is empty or is not realizable, the learner outputs an arbitrary fixed concept in \(\mathcal{H}\). Otherwise, the learner outputs \(\mathcal{A}\left(S_+,J\right) \mathrel{\vcenter{:}}= h_{T,I(J)} .\) Observe that this learner is proper, since \(h_{T,I(J)}\in\mathcal{H}\), and it is consistent with the observed positives, since \(h_{T,I(J)}\in\mathcal{H}_T\).

-1em Upper Bound on False Negative Rate. Fix a distribution \(\mathcal{D}\) over \(\mathcal{X}\) and a target concept \(\ell\in\mathcal{H}\), and let \(S_+\sim \mathcal{D}_+^n .\) Write \(d=\operatorname{VCdim}{}\!\left(\mathcal{H}\right)\). By the standard realizable VC bound applied to the positive distribution \(\mathcal{D}_+\), if \(n \gtrsim (\frac{1}{\varepsilon})\cdot (d\log{\frac{1}{\varepsilon}} + \log{\frac{1}{\delta}}),\) then with probability at least \(1-\frac{\delta}{2}\) over \(S_+\), every \(h\in\mathcal{H}\) consistent with \(S_+\) satisfies \(\mathcal{D}_+\!\left(\ell\setminus h\right) \leq \frac{\varepsilon}{2}.\) Since \(\mathcal{D}\!\left(\ell\setminus h\right) = \mathcal{D}\!\left(\ell\right)\, \mathcal{D}_+\!\left(\ell\setminus h\right) \leq \mathcal{D}_+\!\left(\ell\setminus h\right),\) the same event implies \(\mathcal{D}\!\left(\ell\setminus h\right) \leq \frac{\varepsilon}{2}\) for every consistent \(h\in\mathcal{H}\). The learner’s output is always consistent with \(S_+\). Hence, conditioned on this event, \(\mathcal{D}\!\left(\ell\setminus \mathcal{A}\left(S_+,J\right)\right) \leq \frac{\varepsilon}{2}.\)

-1em Upper Bound on False Positive Rate. Condition on the observed multiset \(S_+\), and therefore on \(T=\mathop{\mathrm{\mathrm{Domain}}}\!\left(S_+\right)\). Since \(S_+\) is realizable, \(T\subseteq \ell\), and hence \(\operatorname{CLOS}_{\mathcal{H}}\!\left(T\right) \subseteq \ell .\) Thus every negative point \(x\notin \ell\) satisfies \(x\notin \operatorname{CLOS}_{\mathcal{H}}\!\left(T\right).\) For such an \(x\), the index \(I(J)\) and the UES list satisfy \[\begin{align} \Pr\nolimits_J\!\left(x\in \mathcal{A}\left(S_+,J\right)\right) = \Pr\nolimits_J\!\left(x\in h_{T,I(J)}\right) \leq \frac{2}{M} \left| \left\{ i\in\left\{1,\dots,M\right\}: x\in h_{T,i} \right\} \right| \leq 2\eta\,. \end{align}\] Therefore, \[\begin{align} \mathbb{E}_J~ \left[\mathcal{D}( \mathcal{A}({S_+},J)\setminus \ell ) | {S_+}\right] = \int_{\mathcal{X}\setminus \ell} \Pr\nolimits_J(x\in \mathcal{A}(S_+,J)) \,{\rm d}\mathcal{D}(x) \leq 2\eta \,. \end{align}\]

Next, by Markov’s inequality, \[\Pr_J\!\left( \mathcal{D}\!\left(\mathcal{A}\left(S_+,J\right)\setminus \ell\right) > \frac{\varepsilon}{2} \,\middle|\, S_+ \right) \leq \frac{2\eta}{\varepsilon/2} = \frac{4\eta}{\varepsilon} = \frac{\delta}{2}\,.\] Finally, averaging over \(S_+\) gives \[\Pr_{S_+,J}\!\left( \mathcal{D}\!\left(\mathcal{A}\left(S_+,J\right)\setminus \ell\right) > \frac{\varepsilon}{2} \right) \leq \frac{\delta}{2}\,.\]

-1em Conclusion. Thus, with probability at least \(1-\frac{\delta}{2}\) over the sample, the false-negative mass is at most \(\frac{\varepsilon}{2}\). Also, with probability at least \(1-\frac{\delta}{2}\) over the sample and the learner’s random bits, the false-positive mass is at most \(\frac{\varepsilon}{2}\). A union bound gives that \(\Pr_{S_+,J}\!\left( \operatorname{err}_{\mathcal{D}}\!\left(\mathcal{A}\left(S_+,J\right),\ell\right) > \varepsilon \right) \leq \delta .\) Thus, the learner properly PAC learns \(\mathcal{H}\) from positive-only examples with sample complexity \[m\left(\varepsilon,\delta\right) = O\!\left( \frac{ d\log{\frac{1}{\varepsilon}} + \log{\frac{1}{\delta}} }{\varepsilon} \right) = \widetilde{O}\!\left( \frac{d+\log{\frac{1}{\delta}}}{\varepsilon} \right)\,.\]

It remains to bound the number of random bits. Since \(M = O\!\left( (\frac{(d^\star+1)}{\eta})\cdot (\log{\frac{1}{\eta}}) \right)\) and \(\eta=\frac{\varepsilon\delta}{8},\) \[\log_2 K \leq 1+\log_2 M = \widetilde{O}\!\left( \log{\frac{d^\star+2}{\varepsilon\delta}} \right)\,.\] Finally, by 2, \(d^\star < 2^{d+1}\), it follows that \(r\left(\varepsilon,\delta\right) = \widetilde{O}\!\left( d+\log{\frac{1}{\varepsilon\delta}} \right) .\) ◻

Proof. Let \(\mathcal{A}\) be a deterministic proper learner such that \(\mathcal{H}\) is properly learnable from positive-only examples by \(\mathcal{A}\). Suppose, toward a contradiction, that \(\operatorname{CLOS}_{\mathcal{H}}\!\left(\left\{x\right\}\right) \notin \mathcal{H}\) for some realizable point \(x\), and fix any \(n \in \mathbb{N}\).

Let \(x^n\) denote the multi-set consisting of \(n\) copies of \(x\), and let \(h=\mathcal{A}(x^n)\). We consider two cases.

-1em Case 1: \(x \notin h\). Let \(\ell \in \mathcal{H}\) be any concept such that \(x \in \ell\), and define \(\mathcal{D}=U_{\left\{x\right\}}\). Then \(\mathcal{D}_+=\mathcal{D}\), and the only possible positive sample is \(S_+=x^n\). Hence \(\operatorname{err}_{\mathcal{D}}(h,\ell)=1.\)

-1em Case 2: \(x \in h\). Since \(h\in\mathcal{H}\) and \(x\in h\), we have \(\operatorname{CLOS}_{\mathcal{H}}\!\left(\left\{x\right\}\right) \subseteq h .\) Because \(\operatorname{CLOS}_{\mathcal{H}}\!\left(\left\{x\right\}\right) \notin \mathcal{H}\), it follows that there exists \(x' \in h \setminus \operatorname{CLOS}_{\mathcal{H}}\!\left(\left\{x\right\}\right) .\) By the definition of \(\operatorname{CLOS}_{\mathcal{H}}\!\left(\left\{x\right\}\right)\), there exists a concept \(\ell \in \mathcal{H}\) such that \(x \in \ell\) but \(x' \notin \ell\). Define \(\mathcal{D}=U_{\left\{x,x'\right\}}\). Then \(\mathcal{D}_+=U_{\left\{x\right\}}\), so again the only possible positive sample is \(S_+=x^n\). Moreover, since \(x'\in h\setminus \ell\), \(\operatorname{err}_{\mathcal{D}}(h,\ell) \geq \frac{1}{2}.\)

Thus, for every \(n\), there exists a distribution \(\mathcal{D}\) and a target concept \(\ell\in\mathcal{H}\) such that \[\Pr_{S_+\sim \mathcal{D}_+^n} \left[ \operatorname{err}_{\mathcal{D}}(\mathcal{A}(S_+),\ell) \geq \frac{1}{2} \right] = 1\,.\] This contradicts the assumption that \(\mathcal{H}\) is properly learnable from positive-only examples by \(\mathcal{A}\). ◻

Proof of [thm:randomness-necessary]. Consider concept class \[\mathcal{H}=\left\{\{1, a\} \mid a \in \mathbb{N}\setminus \{1\} \right\},\] over \(\mathcal{X}= \mathbb{N}\). Notice that \(\operatorname{CLOS}_{\mathcal{H}}(\{1\}) = \{1\} \notin \mathcal{H}\). Thus, \(\mathcal{H}\) does not satisfy the singleton closure property. Therefore, it is not properly learnable from positive examples by a deterministic learner.

However, \(\operatorname{VCdim}(\mathcal{H}) = 1\), and similarly to the proof of 3, it is easy to see that \(\mathcal{H}\) satisfies the uniform exterior separability property. Therefore, due to [thm:random-characterization], it is properly learnable from positive examples. ◻

Proof. Fix any \(\varepsilon, \delta \in (0, 1)\) and distribution \(\mathcal{D}\) over \(\mathcal{X}\) and \(\ell \in \mathcal{H}\). Let the learner be defined as \(\mathcal{A}(S) \mathrel{\vcenter{:}}= \operatorname{CLOS}_{\mathcal{H}}(S)\). Let \(n \geq \frac{d \ln{\frac{1}{\varepsilon}} + \ln{\frac{1}{\delta}}}{\varepsilon}\) and \(S_+\sim \mathcal{D}_+^{n}\).

Observe that \(\operatorname{CLOS}_\mathcal{H}(S_+)\) is an ERM for \(\mathcal{H}\). Thus, we can use standard realizable PAC bounds (see, e.g., BlumerEhrenfeuchtHausslerWarmuth1989?, shalev2014understanding?), and with probability at least \(1 - \delta\), \[\mathcal{D}\left(\ell \setminus \operatorname{CLOS}_\mathcal{H}(S_+)\right) \leq \mathcal{D}_+ \left(\ell \setminus \operatorname{CLOS}_\mathcal{H}(S_+) \right) \leq \varepsilon\,.\] Moreover, due to realizability \(\mathop{\mathrm{\mathrm{Domain}}}(S_+) \subseteq \ell\), and, hence, \(\operatorname{CLOS}_\mathcal{H}(S_+) \subseteq \ell\). Subsequently, \(\mathcal{D}(\operatorname{CLOS}_\mathcal{H}(S_+) \setminus \ell) = 0\). Therefore, with probability \(1 - \delta\), \(\operatorname{err}_\mathcal{D}(\operatorname{CLOS}_\mathcal{H}(S_+), \ell) \leq \varepsilon\). ◻

Proof. We divide the proof into two parts corresponding to the two claims.

Part 1 (consistency implies FES).Consider any \(S, F\) that violate finite exterior separability in 6. For any \(x \in F\) define \(\mathcal{D}_x\) as \[\mathcal{D}_x(x) = \frac{1}{2}, \qquad \forall x' \in S: \mathcal{D}_x(x') = \frac{1}{2\left| S \right|}\,,\] and zero elsewhere. Also, let \(\ell_x\) be any concept containing \(S\) that does not contain \(x\); such a concept exists since \(x \notin \operatorname{CLOS}_{\mathcal{H}}(S)\).

Since \(S,F\) violate finite exterior separability, every \(h \in \mathcal{H}\) satisfies at least one of the following two conditions: either (1) \(x_1 \notin h\) for some \(x_1 \in S\), or (2) \(x_2 \in h\) for some \(x_2 \in F\). In case (1), \[\sum_{x \in F} \operatorname{err}_{\mathcal{D}_x} (h, \ell_x) \geq \frac{\left| F \right|}{2\left| S \right|}\,.\] In case (2), \[\sum_{x \in F} \operatorname{err}_{\mathcal{D}_x} (h, \ell_x) \geq \operatorname{err}_{\mathcal{D}_{x_2}}(h, \ell_{x_2}) \geq \frac{1}{2}\,.\] Therefore, for either case \[\frac{\sum_{x \in F} \operatorname{err}_{\mathcal{D}_x} (h, \ell_x)}{\left| F \right|} \geq \frac{1}{2 \max(\left| S \right|, \left| F \right|)}\,.\] This implies that, for every proper positive-only learner \(\mathcal{A}\) and every \(n \in \mathbb{N}\), \[\label{eq:consistency-implies-FES-1} \frac{\sum_{x \in F} \mathbb{E}_{S_+\sim U_{S}^{n}, \mathcal{A}}\left[ \operatorname{err}_{\mathcal{D}_x} (\mathcal{A}(S_+), \ell_x)\right]}{\left| F \right|} \geq \frac{1}{2 \max(\left| S \right|, \left| F \right|)}\,.\tag{1}\]

Now for the sake of contradiction, assume that \(\mathcal{H}\) is properly positive-only consistent. Therefore, there exists a proper learner \(\mathcal{A}\) such that for every \(x \in F\), \[\lim_{n\to\infty} \mathbb{E}_{S_+\sim U_S^n,\mathcal{A}}\left[ \operatorname{err}_{\mathcal{D}_x}(\mathcal{A}(S_+),\ell_x) \right] = 0\,.\] Since \(F\) is finite, this would imply \[\lim_{n\to\infty} \frac{ \sum_{x \in F} \mathbb{E}_{S_+\sim U_S^n,\mathcal{A}}\left[ \operatorname{err}_{\mathcal{D}_x}(\mathcal{A}(S_+),\ell_x) \right] }{\left| F \right|} = 0\,,\] contradicting 1 . Therefore, \(\mathcal{H}\) is not properly positive-only consistent, which completes the proof of the first part.

-1em Part 2 (FES over countable domain implies consistency). Fix an enumeration \(\mathcal{X}=\left\{x_1,x_2,\dots\right\}\) and write \(X_m=\left\{x_1,\dots,x_m\right\}\). Define the learner \(\mathcal{A}\) as follows. Given a realizable sample \(S_+\), choose \(\mathcal{A}(S_+)\in\mathcal{H}_{\mathop{\mathrm{\mathrm{Domain}}}(S_+)}\) such that \(\mathcal{A}(S_+)\cap\left(X_{|S_+|}\setminus \operatorname{CLOS}_{\mathcal{H}}(S_+)\right)=\varnothing\). Such a concept exists by finite exterior separability, applied to \(S=\mathop{\mathrm{\mathrm{Domain}}}(S_+)\) and \(F=X_{|S_+|}\setminus \operatorname{CLOS}_{\mathcal{H}}(S_+)\).

Consider any distribution \(\mathcal{D}\) over \(\mathcal{X}\) and any \(\ell \in \mathcal{H}\). Since \(\mathcal{X}\) is countable, there exists \(n_{\mathcal{D}}(\varepsilon)\in\mathbb{N}\) such that \[\mathcal{D}\left(\mathcal{X}\setminus X_{n_{\mathcal{D}}(\varepsilon)}\right) \leq \frac{\varepsilon}{2}\,.\] Now fix any \(n \geq n_{\mathcal{D}}(\varepsilon)\) and any multi-set \(S_+\in \mathcal{X}^n\). By construction, \(\mathcal{A}(S_+)\) has no false positives on \(X_{n_{\mathcal{D}}(\varepsilon)} \setminus \operatorname{CLOS}_{\mathcal{H}}(S_+)\), and since \(\operatorname{CLOS}_{\mathcal{H}}(S_+)\subseteq \ell\), it has no false positives on \(X_{n_{\mathcal{D}}(\varepsilon)}\). Therefore, \[\label{eq:const-char-decompose} \begin{align} \operatorname{err}_{\mathcal{D}}(\mathcal{A}(S_+), \ell) & \leq \mathcal{D}(\ell \cap X_{n_{\mathcal{D}}(\varepsilon)} \setminus \mathcal{A}(S_+)) + \mathcal{D}(\mathcal{X}\setminus X_{n_{\mathcal{D}}(\varepsilon)}) \\ & \leq \mathcal{D}(\ell \cap X_{n_{\mathcal{D}}(\varepsilon)} \setminus \mathcal{A}(S_+)) + \frac{\varepsilon}{2}\,. \end{align}\tag{2}\] Let \(\mathcal{H}' = \left\{h \cap X_{n_{\mathcal{D}}(\varepsilon)} \mid h \in \mathcal{H}\right\}\). By definition \(\operatorname{VCdim}(\mathcal{H}') \leq n_{\mathcal{D}}(\varepsilon)\). Applying the standard realizable PAC bound to \(\mathcal{H}'\) and distribution \(\mathcal{D}_+\), for \(n \gtrsim \frac{1}{\varepsilon}\cdot \left(n_{\mathcal{D}}(\varepsilon) \ln{\frac{1}{\varepsilon}}\right)\), \[\mathbb{E}_{S_+\sim \mathcal{D}_+^{n}}\left[\mathcal{D}(\ell \cap X_{n_{\mathcal{D}}(\varepsilon)} \setminus \mathcal{A}(S_+))\right] \leq \varepsilon/2\,.\] Combining with this implies \(\mathbb{E}_{S_+\sim \mathcal{D}_+^{n}}\left[\operatorname{err}_{\mathcal{D}}(\mathcal{A}(S_+), \ell)\right] \leq \varepsilon.\) Therefore, \[\lim_{n \to \infty} \mathbb{E}_{S_+\sim \mathcal{D}_+^{n}}\left[\operatorname{err}_{\mathcal{D}}(\mathcal{A}(S_+), \ell)\right] = 0\,.\qedhere{}\] ◻

Proof of 2. Let \(x_1,\dots,x_n\) be i.i.d.from \(Q\), and let \(N = (N_\omega)_{\omega \in \Omega}\) be the random histogram, where \(N_\omega = \sum_{i=1}^n \mathbb{1}\{x_i = \omega\}.\) Then \(N\) completely determines the sampled multiset. So for any fixed multiset \(S \in \Omega^n\), if \(m(S)\) denotes its multiplicity vector, then \[\Pr_{S' \sim Q^n}[S' = S \text{ as multisets}] = \Pr[N = m(S)]\,.\]

Now define, for each \(i\), \(Y_i = e_{x_i}\), where \(e_\omega\) is the unit vector at coordinate \(\omega\). Then \(N = \sum_{i=1}^n Y_i\,.\) So the probability of any fixed multiset is exactly a point mass of the sum of independent random vectors \(Y_1,\dots,Y_n\).

For each \(i\), the distribution of \(Y_i\) has maximal atom \[\sup_{y} \Pr[Y_i = y] = \sup_{\omega \in \Omega} Q(\omega) \leq 1 - \gamma\,.\] Hence \[1 - \sup_y \Pr[Y_i = y] \geq \gamma \qquad \text{for every } i\,.\] Now apply Theorem 10, for independent random vectors \(Y_1,\dots,Y_n\), \[\sup_x \Pr\!\left[\sum_{i=1}^n Y_i = x\right] \le \sqrt{\frac{C}{\sum_{i=1}^n \bigl(1 - \sup_y \Pr[Y_i = y]\bigr)}}\,.\] Therefore, \[\sup_x \Pr[N = x] \le \sqrt{\frac{C}{\sum_{i=1}^n \gamma}} = \sqrt{\frac{C}{n\gamma}}\,.\qedhere{}\] ◻

Proof of [thm:ERM-separation]. Recall the concept class defined in 3 \[\label{eq:ERM-separation-conceptclass} \mathcal{H}_{\mathrm{spr}} \mathrel{\vcenter{:}}= \left\{\left\{1\right\},\left\{2\right\}\right\} \cup \left\{\left\{1,2,i\right\} : i \geq 3\right\}\,.\tag{3}\]

-1em Part 1 (Learnability by deterministic learners). We first show that there exists a deterministic proper learner \(\mathcal{A}\) such that \(\mathcal{H}_{\mathrm{spr}}\) is proper positive-only learnable by \(\mathcal{A}\).

For every \(n \geq 9\) and multi-set \(S_+\in \mathcal{X}^{n}\), let \(o(S_+)\) denote the number of repetitions of \(1\) in \(S_+\). Consider the learning algorithm \(\mathcal{A}\) defined as follows \[\mathcal{A}(S_+) = \begin{cases} \{1, 2, i\} & \text{if } i \in S_+\setminus \{1, 2\} \\ \{1\} & o(S_+) \geq n - \sqrt{n}\\ \{2\} & o(S_+) \leq \sqrt{n}\\ \{1, 2, o(S_+) \} & \text{o.w.} \end{cases}\] For samples of size less than \(9\), define \(\mathcal{A}\) arbitrarily as any concept in \(\mathcal{H}_{\mathrm{spr}}\). Note that \(\mathcal{A}\) is proper and deterministic by definition. Consider any \(\varepsilon, \delta \in (0, 1)\), distribution \(\mathcal{D}\) over \(\mathcal{X}\), \(\ell \in \mathcal{H}_{\mathrm{spr}}\) and \(n \geq \left(\frac{16C}{\varepsilon\delta}\right)^4\) where \(C\) is the universal constant in 2. We prove that \[\Pr_{S_+\sim \mathcal{D}_+^{n}} \left[\operatorname{err}_{\mathcal{D}}(\mathcal{A}\left(S_+\right), \ell) \geq \varepsilon\right] \leq \delta\,.\] We prove the claim for 3 distinct cases of \(\mathcal{D}\) and \(\ell\).

-1em Case 1: \(\ell=\{1\}\) or \(\ell=\{2\}\). Then the learner receives a sample consisting only of the corresponding point. If \(\ell=\{1\}\), then \(o(S_+)=n\) and \(\mathcal{A}(S_+)=\{1\}\); if \(\ell=\{2\}\), then \(o(S_+)=0\) and \(\mathcal{A}(S_+)=\{2\}\). In both cases, the error is zero.

-1em Case 2: \(\ell = \{1, 2, i^\star\}\) and \(\mathcal{D}_+ (i^\star) > \frac{\varepsilon}{4}\) for some \(i^\star \in \mathbb{N}\setminus \{1, 2\}\). Since \(n > \frac{4\ln(1 / \delta)}{\varepsilon}\), we have \[\Pr[ i^\star \notin S_+] < (1 - \varepsilon/4)^{n} \leq e^{- {n} \varepsilon/ 4} \leq \delta\,.\] Thus, with probability at least \(1-\delta\), the sample contains \(i^\star\), and \(\mathcal{A}\) outputs \(\{1,2,i^\star\}\). On this event the error is zero.

-1em Case 3: \(\ell = \{1, 2, i^\star\}\) and \(\mathcal{D}_+ (i^\star) \leq \frac{\varepsilon}{4}\) for some \(i^\star \in \mathbb{N}\setminus \{1, 2\}\). Since \(\ell = \{1, 2, i^*\}\), the false negative rate of \(\mathcal{A}\) is \[\label{eq:thm:proper-intersect-closed-learnable-fn} \begin{align} \mathcal{D}(\ell \setminus \mathcal{A}\left(S_+\right)) & = \mathcal{D}(1) \, \mathbb{1}[\mathcal{A}(S_+)(1) = 0] + \mathcal{D}(2) \, \mathbb{1}[\mathcal{A}(S_+)(2) = 0] + \mathcal{D}(i^*) \mathbb{1}[\mathcal{A}(S_+)(i^\star) = 0] \\ & \leq \mathcal{D}_+(1) \, \mathbb{1}[\mathcal{A}(S_+)(1) = 0] + \mathcal{D}_+(2) \, \mathbb{1}[\mathcal{A}(S_+)(2) = 0] + \varepsilon/ 4\,. \end{align}\tag{4}\]

Then, we divide case 3 into two cases depending on values \(\mathcal{D}_+(1)\) and \(\mathcal{D}_+(2)\).

-1em Case 3.1: \(\mathcal{D}_+(1)\leq \frac{1}{2 \sqrt {n}}\) or \(\mathcal{D}_+(2) \leq \frac{1}{2 \sqrt {n}}\). Without loss of generality assume \(\mathcal{D}_+(1)\leq \frac{1}{2 \sqrt {n}}\). Then, using multiplicative Chernoff bound, since \({n} > \left(\frac{6 \ln{\frac{1}{\delta}}}{\varepsilon}\right)^2\) we have \[\Pr[o(S_+) > \sqrt{{n}}] \leq e^{-{\sqrt{{n}}/6}} \leq \delta\,.\] Thus, with probability at least \(1 - \delta\), \(\mathcal{A}(S_+)\) is either \(\{2\}\) or \(\{1, 2, i^\star\}\). In the latter case the error is zero. In the former case, 4 implies \[\operatorname{err}_\mathcal{D}(\mathcal{A}(S_+), \ell) = \mathcal{D}(\ell \setminus \mathcal{A}(S_+)) \leq \mathcal{D}_+(1)+ \frac{\varepsilon}{4} \leq \frac{1}{2 \sqrt{{n}}} + \frac{\varepsilon}{4}.\] Therefore, since \({n} > \left(\frac{2}{3 \varepsilon}\right)^2\) we have \(\operatorname{err}_\mathcal{D}(\mathcal{A}(S_+), \ell) \leq \varepsilon\).

-1em Case 3.2: \(\mathcal{D}_+(1), \mathcal{D}_+(2) > \frac{1}{2 \sqrt {n}}\). First suppose \(\mathcal{D}_+(1)\leq \frac{2}{\sqrt {n}}\). Using \({n} \geq \left(\frac{8}{\varepsilon}\right)^2\), we get \[\label{eq:thm:proper-intersect-closed-learnable-bound1} \mathcal{D}_+(1)\mathbb{1}[\mathcal{A}(S_+)(1) = 0] \leq \frac{2}{\sqrt {n}} \leq \frac{\varepsilon}{4}\,.\tag{5}\] Otherwise, \(\mathcal{D}_+(1)>\frac{2}{\sqrt n}\). Since \({n} \geq \left(\frac{4 \ln(4 / \delta)}{\varepsilon}\right)^2\), another multiplicative Chernoff bound gives \[\Pr[o(S_+) \leq \sqrt{{n}}] \leq e^{-{\sqrt{{n}}/4}} \leq \frac{\delta}{4}\,.\] Thus, with probability at least \(1 - \frac{\delta}{4}\) we have \(\mathcal{A}(S_+)(1) = 1\), and subsequently \[\mathcal{D}_+(1)\mathbb{1}[\mathcal{A}(S_+)(1) = 0] = 0\,.\] Combining this with , shows that, regardless of the value of \(\mathcal{D}_+(1)\), with probability \(1-\frac{\delta}{4}\), \[\mathcal{D}_+(1)\mathbb{1}[\mathcal{A}(S_+)(1) = 0] \leq \varepsilon/ 4\,.\] Similarly, with probability at least \(1-\frac{\delta}{4}\), \(\mathcal{D}_+(2) \mathbb{1}[\mathcal{A}(S_+)(2) = 0] \leq \varepsilon/ 4\).

Combining these two bounds with a union bound and , we get that, with probability at least \(1-\frac{\delta}{2}\), the false-negative rate is bounded by \[\label{eq:thm:proper-intersect-closed-learnable-bound-fn} \mathcal{D}(\ell \setminus \mathcal{A}(S_+)) \leq \frac{3\varepsilon}{4}\,.\tag{6}\] It remains to bound the false-positive rate. For every \(k \in \{0, 1, \ldots , n\}\), let \(S_k\) denote the multi-set consisting of \(k\) copies of \(1\) and \(n-k\) copies of \(2\). By the definition of \(\mathcal{A}\), since \(n\geq 9\), \[\label{eq:thm:proper-intersect-closed-learnable-fp} \begin{align} \mathcal{D}(\mathcal{A}(S_+) \setminus \ell) = \sum_{k \in \mathbb{N}\setminus \ell} \mathcal{D}(k) \mathbb{1} \left[\mathcal{A}(S_+)\left(k\right) = 1\right] = \sum_{\sqrt{n} \leq k \leq n - \sqrt{n}, k \neq i^\star} \mathcal{D}(k) \mathbb{1} \left[S_+= S_k\right]\,. \end{align}\tag{7}\]

Since \(\mathcal{D}_+(1),\mathcal{D}_+(2)>\frac{1}{2\sqrt n}\), we have \(\sup_{k\in\mathbb{N}}\mathcal{D}_+(k)<1-\frac{1}{2\sqrt n}\). By 2, and since \(n\geq \left(\frac{16C}{\varepsilon\delta}\right)^4\), for every multi-set \(S\) we have \[\Pr_{S_+\sim\mathcal{D}_+^n}[S_+=S] \leq \sqrt{\frac{2C}{\sqrt n}} \leq \frac{\varepsilon\delta}{8}\,.\] Combining this with , we get \[\begin{align} \mathbb{E}\left[\mathcal{D}(\mathcal{A}(S_+)\setminus\ell)\right] &\leq \sum_{\sqrt n \leq k \leq n-\sqrt n,\;k\neq i^\star} \mathcal{D}(k)\Pr[S_+=S_k] \leq \frac{\varepsilon\delta}{8} \sum_{\sqrt n \leq k \leq n-\sqrt n,\;k\neq i^\star} \mathcal{D}(k) \leq \frac{\varepsilon\delta}{8}\,. \end{align}\] Therefore, by Markov’s inequality, \(\Pr[\mathcal{D}(\mathcal{A}(S_+)\setminus\ell)>\varepsilon/4]\leq \delta/2.\) Combining this with 6 shows that \(\Pr_{S_+\sim\mathcal{D}_+^n}[\operatorname{err}_{\mathcal{D}}(\mathcal{A}(S_+),\ell)>\varepsilon]\leq \delta\), completing the proof of learnability by deterministic learners.

-1em Part 2 (Non-learnability by deterministic ERM learners). We then prove that \(\mathcal{H}_{\mathrm{spr}}\) is not properly positive-only learnable by any deterministic ERM proper learner \(\mathcal{A}\). Fix any \(n \geq 2\). For any \(a \in \mathbb{N}\setminus \{1,2\}\), define the pair \((\mathcal{D}_a,\ell_a)\) as follows: \[\ell_a=\left\{1,2,a+1\right\}, \quad \mathcal{D}_a(1)=\frac{1}{2n}, \quad \mathcal{D}_a(2)=\frac{n-1}{2n}, \quad \mathcal{D}_a(a)=\frac{1}{2}\,,\] where \(\mathcal{D}_a\) is zero elsewhere. Let \(S\) be a multi-set with exactly one copy of \(1\) and \(n-1\) copies of \(2\). Since \(\mathcal{A}\) is an ERM learner, we have \(\mathop{\mathrm{\mathrm{Domain}}}(S)\subseteq \mathcal{A}(S)\). Thus, \(\mathcal{A}(S)=\{1,2,a^\star\}\) for some \(a^\star\in\mathbb{N}\setminus\{1,2\}\). Furthermore, under the target \(\ell_{a^\star}=\left\{1,2,a^\star+1\right\}\), the point \(a^\star\) is negative and has \(\mathcal{D}_{a^\star}\)-mass \(1/2\). Hence, \[\operatorname{err}_{\mathcal{D}_{a^\star}}\left(\mathcal{A}(S),\ell_{a^\star}\right)=\frac{1}{2}\,.\] In addition, under \(\mathcal{D}_{+,a^\star}\), the mass of \(1\) is \(1/n\) and the mass of \(2\) is \((n-1)/n\). Therefore, \[\Pr_{S_+\sim \mathcal{D}_{+,a^\star}^n}[S_+=S] \geq n\cdot \frac{1}{n}\left(\frac{n-1}{n}\right)^{n-1} > \left(\frac{n-1}{n}\right)^n \geq \frac{1}{4}\,.\] Consequently, \[\Pr_{S_+\sim \mathcal{D}^{n}_{+,a^\star}}\left[\operatorname{err}_{\mathcal{D}_{a^\star}}\left(\mathcal{A}(S_+),\ell_{a^\star}\right) \geq \frac{1}{2}\right] \geq \frac{1}{4}\,.\] Thus, \(\mathcal{H}_{\mathrm{spr}}\) is not properly positive-only learnable by \(\mathcal{A}\). ◻

Proof. We divide the proof into two parts corresponding to the two claims.

-1em Part 1 (Separation of consistency and non-uniform learnability). Consider the concept class \[\mathcal{H}_{\mathrm{bin}} \mathrel{\vcenter{:}}= \{ h_a \mid a \geq 3 \}\,, \qquad h_a \mathrel{\vcenter{:}}= \{1,2,a,a+2,a+4,\ldots\}\,.\] Observe that \(\operatorname{VCdim}(\mathcal{H}_{\mathrm{bin}})=1\). We first show that \(\mathcal{H}_{\mathrm{bin}}\) satisfies the finite exterior separability property. Consider any finite-sized \(S \subseteq \mathbb{N}\) that is realized by \(\mathcal{H}_{\mathrm{bin}}\), and any \(F \subseteq \mathbb{N}\setminus \operatorname{CLOS}_{\mathcal{H}_{\mathrm{bin}}}(S)\). We consider two cases for \(S\), and in each case we show that there exists \(h \in \mathcal{H}_{\mathrm{bin}}\) such that \(\mathop{\mathrm{\mathrm{Domain}}}(S) \subseteq h\), but \(F \cap h = \varnothing\).

Case 1: There exists some \(a \geq 3\) such that \(a \in \mathop{\mathrm{\mathrm{Domain}}}(S)\). Denote \[t = \min(\mathop{\mathrm{\mathrm{Domain}}}(S)\setminus \{1,2\})\,.\] It is easy to see that \(h_t = \operatorname{CLOS}_{\mathcal{H}_{\mathrm{bin}}}(S).\) Thus, since \(F \subseteq \mathbb{N}\setminus \operatorname{CLOS}_{\mathcal{H}_{\mathrm{bin}}}(S)\), we have \(h_t \cap F = \varnothing\). Moreover, by the definition of the closure, \(\mathop{\mathrm{\mathrm{Domain}}}(S) \subseteq h_t\).

Case 2: \(\mathop{\mathrm{\mathrm{Domain}}}(S) \subseteq \{1,2\}\). If \(F=\varnothing\), then any \(h \in \mathcal{H}_{\mathrm{bin}}\) satisfies the desired condition. Otherwise, choose \(r \geq 3\) such that \(r > \max(F).\) Then \(\mathop{\mathrm{\mathrm{Domain}}}(S) \subseteq \{1,2\} \subseteq h_r\). Moreover, since \(r > \max(F)\), no element of \(F\) belongs to the tail \(\{r,r+2,r+4,\ldots\}\) of \(h_r\). Also, since \(\{1,2\} \subseteq \operatorname{CLOS}_{\mathcal{H}_{\mathrm{bin}}}(S)\), we have \(\{1,2\} \cap F = \varnothing\). Therefore, \(h_r \cap F = \varnothing\).

Combining these two cases, we conclude that \(\mathcal{H}_{\mathrm{bin}}\) satisfies finite exterior separability. By 9, \(\mathcal{H}_{\mathrm{bin}}\) is proper positive-only consistent. It remains to prove that \(\mathcal{H}_{\mathrm{bin}}\) is not non-uniformly proper positive-only learnable.

For any \(a \geq 3\), define the pair \((\mathcal{D}_a,\ell_a)\) as follows: \[\ell_a = h_{3+(a \bmod 2)}, \qquad \mathcal{D}_a(1)=\mathcal{D}_a(2)=\frac{1}{4}, \qquad \mathcal{D}_a(a)=\frac{1}{2}\,,\] where \(\mathcal{D}_a\) is zero elsewhere. Notice that \(\mathcal{D}_{a,+} = U_{\{1,2\}}.\) Indeed, by the definition of \(\ell_a\), the point \(a\) is not labeled positive by \(\ell_a\), while both \(1\) and \(2\) are labeled positive.

For the sake of contradiction, suppose that \(\mathcal{H}_{\mathrm{bin}}\) is non-uniformly proper positive-only learnable by a proper learner \(\mathcal{A}\). Consider any \[n \geq \max \left\{ m{}_{\mathcal{H}_{\mathrm{bin}}}\left(\frac{1}{4},\frac{1}{4},h_3\right)\,, m{}_{\mathcal{H}_{\mathrm{bin}}}\left(\frac{1}{4},\frac{1}{4},h_4\right) \right\}\,.\] We now show that for any fixed \(S_+\in \{1,2\}^n\), \[\lim_{a \to \infty} \Pr_{\mathcal{A}} \left[ a \in \mathcal{A}(S_+) \text{ or } a+1 \in \mathcal{A}(S_+) \right] =1\,.\] Since \(\mathcal{A}\) is proper, for every fixed \(S_+\in \{1,2\}^n\), there exists an \(\mathbb{N}_{\geq 3}\)-valued random variable \(B_{S_+}\) such that \(\mathcal{A}(S_+)=h_{B_{S_+}}.\) For every realization \(B_{S_+}=b\), if \(a \geq b\), then exactly one of \(a\) and \(a+1\) belongs to \(h_b\), because \(a\) and \(a+1\) have opposite parity and \(h_b\) contains all sufficiently large numbers with the same parity as \(b\). Therefore, \[\{B_{S_+} \leq a\} \subseteq \left\{ a \in \mathcal{A}(S_+) \text{ or } a+1 \in \mathcal{A}(S_+) \right\}\,.\] Since \(B_{S_+}\) is natural-number-valued, we have \(\lim_{a \to \infty} \Pr[B_{S_+} \leq a] = 1.\) Hence, \[\lim_{a \to \infty} \Pr_{\mathcal{A}} \left[ a \in \mathcal{A}(S_+) \text{ or } a+1 \in \mathcal{A}(S_+) \right] =1\,.\] Since \(\{1,2\}^n\) is finite, averaging over \(S_+\sim U_{\{1,2\}}^n\) gives \[\lim_{a \to \infty} \Pr_{S_+\sim U_{\{1,2\}}^n,\,\mathcal{A}} \left[ a \in \mathcal{A}(S_+) \text{ or } a+1 \in \mathcal{A}(S_+) \right] =1\,.\]

Now observe that the event \(a \in \mathcal{A}(S_+)\) implies \[\operatorname{err}_{\mathcal{D}_a}\left(\mathcal{A}(S_+),\ell_a\right) \geq \frac{1}{2}\,,\] because \(\mathcal{D}_a\) assigns mass \(\frac{1}{2}\) to \(a\), and \(a \notin \ell_a\). Similarly, the event \(a+1 \in \mathcal{A}(S_+)\) implies \[\operatorname{err}_{\mathcal{D}_{a+1}}\left(\mathcal{A}(S_+),\ell_{a+1}\right) \geq \frac{1}{2}\,.\] Therefore, \[\lim_{a \to \infty} \Pr_{S_+\sim U_{\{1,2\}}^n,\,\mathcal{A}} \left[ \operatorname{err}_{\mathcal{D}_a}\left(\mathcal{A}(S_+),\ell_a\right) + \operatorname{err}_{\mathcal{D}_{a+1}}\left(\mathcal{A}(S_+),\ell_{a+1}\right) \geq \frac{1}{2} \right] =1\,.\] Consequently, there exists \(a^\star \in \mathbb{N}\) such that \[\Pr_{S_+\sim U_{\{1,2\}}^n,\,\mathcal{A}} \left[ \operatorname{err}_{\mathcal{D}_{a^\star}}\left(\mathcal{A}(S_+),\ell_{a^\star}\right) + \operatorname{err}_{\mathcal{D}_{a^\star+1}}\left(\mathcal{A}(S_+),\ell_{a^\star+1}\right) \geq \frac{1}{2} \right] > \frac{1}{2}\,.\] Using a union bound we get \[\Pr_{S_+\sim U_{\{1,2\}}^n,\,\mathcal{A}} \left[ \operatorname{err}_{\mathcal{D}_{a^\star}}\left(\mathcal{A}(S_+),\ell_{a^\star}\right) \geq \frac{1}{4} \right] + \Pr_{S_+\sim U_{\{1,2\}}^n,\,\mathcal{A}} \left[ \operatorname{err}_{\mathcal{D}_{a^\star+1}}\left(\mathcal{A}(S_+),\ell_{a^\star+1}\right) \geq \frac{1}{4} \right] > \frac{1}{2}\,.\] Thus, for some \(b \in \{a^\star,a^\star+1\}\), we have \[\Pr_{S_+\sim U_{\{1,2\}}^n,\,\mathcal{A}} \left[ \operatorname{err}_{\mathcal{D}_b}\left(\mathcal{A}(S_+),\ell_b\right) \geq \frac{1}{4} \right] > \frac{1}{4}\,.\] By definition, \(\ell_b \in \{h_3,h_4\}\), and as observed above, \(\mathcal{D}_{b,+}=U_{\{1,2\}}\). This contradicts \[n \geq \max \left\{ m{}_{\mathcal{H}_{\mathrm{bin}}}\left(\frac{1}{4},\frac{1}{4},h_3\right)\,, m{}_{\mathcal{H}_{\mathrm{bin}}}\left(\frac{1}{4},\frac{1}{4},h_4\right) \right\}\,.\] Therefore, \(\mathcal{H}_{\mathrm{bin}}\) is not non-uniformly properly positive-only learnable.

Part 2 (Separation of non-uniform learnability and learnability). Recall the concept class considered in 4: \[\mathcal{H}_{\mathrm{tail}} \mathrel{\vcenter{:}}= \left\{h_a : a \geq 3\right\}, \qquad\text{where}\qquad h_a \mathrel{\vcenter{:}}= \left\{1,2\right\} \cup \left\{m \in \mathbb{N}: m \geq a\right\}\,.\] Observe that \(\operatorname{VCdim}(\mathcal{H}_{\mathrm{tail}}) = 1\). In 4, we already showed that \(\mathcal{H}_{\mathrm{tail}}\) does not satisfy the distributional exterior separability property, and thus it also does not satisfy the uniform exterior separability property. Therefore, by [thm:random-characterization], \(\mathcal{H}_{\mathrm{tail}}\) is not properly positive-only learnable. It remains to prove that \(\mathcal{H}_{\mathrm{tail}}\) is non-uniformly properly positive-only learnable.

Define the learner \(\mathcal{A}\) as follows. For any \(n \in \mathbb{N}\) and \(S_+\in \mathcal{X}^n\), let \[i(S_+) \mathrel{\vcenter{:}}= \min\bigl(\mathop{\mathrm{\mathrm{Domain}}}(S_+)\setminus \left\{1,2\right\}\bigr)\,,\] whenever \(\mathop{\mathrm{\mathrm{Domain}}}(S_+)\setminus \left\{1,2\right\}\) is non-empty, and set \[\mathcal{A}(S_+) \mathrel{\vcenter{:}}= \begin{cases} h_{i(S_+)} & \text{if } \mathop{\mathrm{\mathrm{Domain}}}(S_+)\setminus \left\{1,2\right\} \neq \varnothing,\\ h_{\max\left\{n,3\right\}} & \text{otherwise\,.} \end{cases}\] Fix a target concept \(\ell=h_{a^\star}\) for some \(a^\star \geq 3\). We show that this learner succeeds with a sample size that may depend on \(a^\star\). Consider any \(n \geq a^\star\). For every \(S_+\in \ell^n\), we claim that \(\mathcal{A}(S_+) \subseteq \ell.\) Indeed, if \(\mathop{\mathrm{\mathrm{Domain}}}(S_+)\setminus \left\{1,2\right\}\) is non-empty, then \(i(S_+) \in \ell\setminus \left\{1,2\right\}\), and therefore \(i(S_+)\geq a^\star\). Hence \(h_{i(S_+)} \subseteq h_{a^\star}.\) On the other hand, if \(\mathop{\mathrm{\mathrm{Domain}}}(S_+)\setminus \left\{1,2\right\}=\varnothing\), then \(\mathcal{A}(S_+)=h_{n} \subseteq h_{a^\star}\). Thus, for every positive-only sample \(S_+\in \ell^n\), the learner has zero false positives.

Next, observe that \(\mathcal{A}\) always satisfies \(\mathop{\mathrm{\mathrm{Domain}}}(S_+) \subseteq \mathcal{A}(S_+)\). Therefore, by applying standard realizable PAC bounds to \(\mathcal{H}_{\mathrm{tail}}\) under \(\mathcal{D}_+\), there exists a universal constant \(C>0\) such that for \(n \geq C \frac{\log(1/\varepsilon)+\log(1/\delta)}{\varepsilon},\) with probability at least \(1-\delta\), the false negative is bounded by \[\mathcal{D}(\ell\setminus \mathcal{A}(S_+)) \leq \mathcal{D}_+(\ell\setminus \mathcal{A}(S_+)) \leq \varepsilon\,.\] Now using \(\mathcal{A}(S_+) \subseteq \ell\) yields that \(\mathcal{H}_{\mathrm{tail}}\) is non-uniformly proper positive-only learnable by \(\mathcal{A}\). ◻

Proof. Consider the learner \(\mathcal{A}(S_+) = \operatorname{CLOS}_\mathcal{H}(S_+)\). Clearly \(\mathcal{A}\) satisfies \(\mathcal{A}(S') = \mathcal{A}(S)\) for all positive samples \(S\) and \(S'\) such that \(S \subseteq S'\) and \(\mathop{\mathrm{\mathrm{Domain}}}(S') \subseteq \mathcal{A}(S)\). Thus, \(\mathcal{A}\) is stable. Combining this with 1 completes the proof. ◻

Proof. Assume that \(\mathcal{H}\) does not satisfy the stated property. Then either \(\operatorname{VCdim}(\mathcal{H}) = \infty\), which implies that \(\operatorname{VCdim}(\mathcal{H}_{\cap}) = \infty\), and by the results of lee2026smoothed?, this in turn implies that \(\mathcal{H}\) is not positive-only learnable; or there exists a finite set \(B = \{x_1, x_2, \ldots, x_s\} \subseteq \mathcal{X}\) such that \(\operatorname{CLOS}_\mathcal{H}(B) \notin \mathcal{H}\).

Denote \(F \mathrel{\vcenter{:}}= \mathcal{X}\setminus \operatorname{CLOS}_\mathcal{H}(B)\). For any \(x \in F\), define the distribution \(\mathcal{D}_x\) as \[\mathcal{D}_x(x) = \frac{1}{2}\,, \quad \mathcal{D}_{x} (x') = \frac{1}{2s} \text{ for all } x' \in B\,,\] and zero elsewhere. Also, let \(\ell_x\) be any concept in \(\mathcal{H}\) such that \(B \subseteq \ell_x\), but \(\ell_x(x) = 0\). Note that since \(x \notin \operatorname{CLOS}_\mathcal{H}(B)\) such a concept \(\ell_x\) always exists. Notice that for all \(x \in F\), we have \(\mathcal{D}_{+, x} = U_B\). We prove that for every proper size-dependent stable positive-only learner \(\mathcal{A}\), \[\lim_{n \rightarrow \infty} \sup_{x \in F} \Pr_{S_+\sim U_B^{n}, \mathcal{A}} \left[ \operatorname{err}_{\mathcal{D}_x} \left(\mathcal{A}(S_+), \ell_x \right) \geq \frac{1}{2s} \right] = 1\,.\] Therefore, \(\mathcal{A}\) cannot learn \(\mathcal{H}\) with positive-only examples.

Let \(\mathcal{A}\) be any proper size-dependent stable positive-only learner for \(\mathcal{H}\). We prove the claim for two distinct cases, depending on the output of \(\mathcal{A}\) over input samples that contain all \(B\).

-1em Case 1: There exists a finite-sized multi-set \(E \in \mathcal{X}^{[*]}\) such that \(\mathop{\mathrm{\mathrm{Domain}}}(E) = B\), and \[\Pr_{\mathcal{A}}\left[B \subseteq \mathcal{A}(E)\right] > 0.\] Note that due to the stability of \(\mathcal{A}\), every sample \(S_+\in B^{n}\) that contains \(E\) satisfies \(\mathcal{A}(S_+) = f(E, n)\) with probability \(1\) over the learner’s randomness. Moreover, as \(n\) goes to infinity the probability of a \(S_+\) sampled by \(U_B^{n}\) containing \(E\) goes to 1. Thus, \[\label{eq:stable-proper-positive-char-1} \lim_{n \to \infty}\Pr_{S_+\sim U_B^{n}, \mathcal{A}}[\mathcal{A}(S_+) = f(E, n)] = 1\,.\tag{8}\]

We consider two distinct cases based on \(f(E, n)\). Case 1.1: If \(B \nsubseteq f(E, n)\), then for all \(x \in F\) we have \(\operatorname{err}_{\mathcal{D}_x}(f(E, n), \ell_x) \geq \frac{1}{2s}\). By combining this with , we attain our objective. Case 1.2: If \(B \subseteq f(E, n)\), then since \(f(E, n) \in \mathcal{H}\), there exists an \(x_E \in f(E, n) \cap F\). Thus, \(\operatorname{err}_{\mathcal{D}_{x_E}}(f(E, n), \ell_{x_E}) = \frac{1}{2}\). By combining this with , we attain our objective.

-1em Case 2: No such \(E\) exists. Then for every sample \(S_+\) containing \(B\) and every \(x \in F\), we have \[\Pr_{S_+\sim U_B^{n}, \mathcal{A}}[\operatorname{err}_{\mathcal{D}_x}(\mathcal{A}(S_+), \ell_x) \geq \frac{1}{2s}] = 1\,.\] Note that, as \(n\) goes to infinity, the probability of a \(S_+\) sampled by \(U_B^{n}\) containing \(B\) goes to 1. ◻