Proof. We first want to show the inequality 1 . Observe that \(s\) is well-defined and monotonically increasing by the conditions on \(\varepsilon.\) Fix any \(b\geq 1\) and any \(m\geq s(b)\) and \(\mathbb{D}\in \mathcal{D}^*\). It holds \[\begin{align} &\underset{S\sim \mathbb{D}^m}{\mathrm{Prob}}\left[\exists n\in \mathbb{N}\colon \sup\limits_{h\in \mathcal{H}_n}|L_\mathbb{D}(h)-L_S(h)|>\varepsilon(m,b \omega(n))\right]\\\leq &\sum\limits_{n=1}^{\infty}\underset{S\sim \mathbb{D}^m}{\mathrm{Prob}}\left[\sup\limits_{h\in \mathcal{H}_n}|L_\mathbb{D}(h)-L_S(h)|>\varepsilon(m,b \omega(n))\right] \overset{\eqref{eq32uc32assump}}{\leq} \sum\limits_{n=1}^{\infty}\frac{1}{bw(n)}\leq 1/b, \end{align}\] which is equivalent to \[\label{eq32new32S} \underset{S\sim \mathbb{D}^m}{\mathrm{Prob}}\left[\forall n\in \mathbb{N}\colon \sup\limits_{h\in \mathcal{H}_n}|L_\mathbb{D}(h)-L_S(h)|\leq \varepsilon(m,b \omega(n))\right] \geq 1-1/b.\tag{3}\] Now consider any \(h\in \mathcal{H}\) with \(n_h\leq b\). The monotonicity assumptions on \(\varepsilon\) imply \[\label{eq32b} \varepsilon(m,b\omega(n_h))\leq\varepsilon_{b}(m,b\omega(b))\leq 1/2b.\tag{4}\] Set \(a\mathrel{\vcenter{:}}= \tilde{\mathcal{A}}(b,S).\) By the definition of SRMs any sample \(S\) of size \(m\) satisfying the inner condition in 3 also satisfies \[\label{eq32some32S} \begin{align} L_\mathbb{D}(a)&\overset{\eqref{eq32new32S}}{\leq} L_S(a)+\varepsilon(m,b\omega(n_a))\\ &\overset{\eqref{eq32srm32rule}}{=}\min\limits_{h'\in \mathcal{H}}\big[L_S(h')+\varepsilon(m,b\omega(n_{h'})\big]\\ &\leq L_S(h)+\varepsilon(m,b\omega(n_h)\\ &\overset{\eqref{eq32b}}{\leq} L_S(h)+1/2b\\ &\overset{\eqref{eq32new32S}}{\leq} L_\mathbb{D}(h) + \varepsilon(m,b\omega(n_h))+ 1/2b\\ &\overset{\eqref{eq32b}}{\leq} L_\mathbb{D}(h)+1/b. \end{align}\tag{5}\] Together with 3 this establishes 1 .

Now we want to verify that the learner \(\mathcal{A}\) defined in 2 is actually a nonuniform PAC learner for \(\mathcal{H}\). Due to our monotonicity assumptions the function \(s\) is increasing and unbounded, so \(t\) is well-defined. For any \((a,b,h)\in \mathbb{N}_+^2\times \mathcal{H}\) we pick \[\label{eq32mnus} \mathop{\mathrm{m^{NU}_\mathcal{H}}}(a,b,h)\mathrel{\vcenter{:}}= s\big(\max\{a,b,n_h\}\big).\tag{6}\] Now fix any \(a,b\geq 1,\) \(h\in \mathcal{H},\) \(\mathbb{D}\in \mathcal{D}^*\) and \(m\geq \mathop{\mathrm{m^{NU}_\mathcal{H}}}(a,b,h).\) Then there is some \(b'\) with \(s(b')\leq m,\) namely \(b'=\max\{a,b,n_h\}.\) So by definition \(t(m)\) is the largest such \(b'.\) This implies \(t(m)\geq \max\{a,b, n_h\},\) and \(m\geq s(t(m)).\) Hence 1 yields \[\begin{align} &\underset{S\sim \mathbb{D}^m}{\mathrm{Prob}}\left[L_\mathbb{D}(\mathcal{A}(S))\leq L_\mathbb{D}(h)+1/a\right]\\ \geq &\underset{S\sim \mathbb{D}^m}{\mathrm{Prob}}\left[L_\mathbb{D}(\tilde{\mathcal{A}}(t(m),S))\leq L_\mathbb{D}(h)+1/t(m)\right]\\ \geq &1-1/t(m)\geq 1-1/b. \end{align}\] ◻

Proof. This follows from observing that there exists a \(k\)-witness for \(\mathcal{H}\) if and only if \(\mathcal{H}\) does not shatter any set \(X\subseteq\mathcal{X}\) with at least \(k+1\) elements. ◻

Proof. Write \(G\mathrel{\vcenter{:}}= \bigcup_{g\in \mathcal{G}}\mathop{\mathrm{supp}}(g)\) and \(H\mathrel{\vcenter{:}}= \bigcup_{h\in \mathcal{H}}\mathop{\mathrm{supp}}(h)\) and \(\mathcal{F}\mathrel{\vcenter{:}}= \mathcal{G}\oplus\mathcal{H}\). Without loss of generality assume \(|\mathcal{F}|>1,\) otherwise the statement is trivial. Let \(X\subseteq\mathcal{X}\) be shattered by \(\mathcal{F}\). Partition \(X\) into three disjoint sets \(X=(X\cap G)\cup (X\cap H)\cup (X\backslash(G\cup H)).\) Since \(X\) is shattered by \(\mathcal{F}\), its subsets \(X\cap G\), \(X\cap H\) and \(X\backslash(G\cup H)\) are also shattered by \(\mathcal{F}\). By the choice of \(G\) and \(H\), any \(f\in \mathcal{F}\) is \(0\) on \(X\backslash(G\cup H),\) so this set must be empty. From \(G\cap H=\varnothing\) it follows that any \(g\in \mathcal{G}\) is \(0\) on \(X\cap H.\) Hence, \(X\cap H\) must be shattered by \(\mathcal{H}\) (because also \(0\in \mathcal{H}\)). Analogously, \(\mathcal{G}\) shatters \(X\cap G\). This shows \(|X|=|X\cap G|+|X\cap H|\leq \mathop{\mathrm{VCdim}}(\mathcal{G})+\mathop{\mathrm{VCdim}}(\mathcal{H})\) and thus \(\mathop{\mathrm{VCdim}}(\mathcal{G}\oplus\mathcal{H})\leq \mathop{\mathrm{VCdim}}(\mathcal{G})+\mathop{\mathrm{VCdim}}(\mathcal{H})\). For ‘\(\geq\)’, let \(X_1\subseteq\mathcal{X}\) be shattered by \(\mathcal{G}\) and \(X_2\subseteq\mathcal{X}\) be shattered by \(\mathcal{H}.\) Then \(X_1\subseteq G\) and \(X_2\subseteq H\), so \(X_1\) and \(X_2\) must be disjoint sets. Hence, it suffices to show that \(X_1\cup X_2\) is shattered by \(\mathcal{F}.\) For any \(f\colon X\to \mathcal{Y}\) there are some \(g\in \mathcal{G}\) and \(h\in \mathcal{H}\) with \(g\mathord{\upharpoonright}_{X_1}=f\mathord{\upharpoonright}_{X_1}\) and \(h\mathord{\upharpoonright}_{X_2}=f\mathord{\upharpoonright}_{X_2}.\) Since \(h\) is \(0\) on \(X_1\) and \(g\) is \(0\) on \(X_2\) it follows \(f=(g+h)\mathord{\upharpoonright}_{X_1\cup X_2}.\) ◻

Proof. In the case \(k=\ell,\) we choose \(\mathcal{H}^{k,\ell}\) to be the RER class of all hypotheses with support size at most \(k,\) then we are done by Example [ex32rer]. So we assume \(k<\ell\) in the following. Also assume that \(k\) is even, the odd case works analogously.

I. Preliminary work: For a Turing machine \(T\) let \(\mathop{\mathrm{code}}(T)\in \mathbb{N}\) be the goedelization of \(T\) (see [4]). Consider an enumeration \(((T_j,k_j))_{j\in \mathbb{N}}\) of all pairs of Turing machines and numbers from \([\ell-k+1]\) for which the maps \(j\mapsto \mathop{\mathrm{code}}(T_j)\) and \(j\mapsto k_j\) are computable. This exists because recursive enumerability is preserved under cartesian products. Let \((I^j)_{j\in \mathbb{N}}\) be a computable enumeration of tuples of even numbers \(\geq k\) such that \(I^j\) has length \(k_j\) and every even number \(\geq k\) appears in exactly one tuple \(I^j\). Now define \(E\mathrel{\vcenter{:}}= \big\{e\in \mathbb{N}\colon \exists o^e\in \mathcal{Y}^{k_e}\colon T_e(I^e)=o^e\big\},\) the set of all indices \(e\in \mathbb{N}\) for which \(T_e\) halts on the input \(I^e\in \mathbb{N}^{k_e}\) with some binary output \(o^e\) of length \(k_e\). Note that \(E\) is infinite and \(o^e\) is well-defined for \(e\in E.\) Lastly, for \(e\in E\) let \(s_e\) be the number of steps after which \(T_e\) halted on the input \(I^e\) and define \(u_e \mathrel{\vcenter{:}}= 2\cdot 3^e\cdot 5^{s_e}+k+1.\)

II. Construction of \(\mathcal{H}^{k,\ell}\): Consider the hypothesis class \[\label{eq32he} \mathcal{H}_E\mathrel{\vcenter{:}}= \{h_e\colon e\in E\}\cup \{0\}, \text{ where } h_{e}(x)\mathrel{\vcenter{:}}= \begin{cases} 1, &\text{if } x=u_e\\ o^e_i, & \text{if } x=I^e_i\\ 0, & \text{else.} \end{cases}\tag{7}\] Note that the support of \(h_e\) contains only entries of \(I^e\) and the single odd number \(u_e\). So the hypotheses in \(\mathcal{H}_E\) have disjoint supports, which implies \(\mathop{\mathrm{VCdim}}(\mathcal{H}_E)=1.\)

Next, consider the class \(\mathcal{G}\mathrel{\vcenter{:}}= \{g\in \mathcal{Y}^\mathbb{N}\colon \mathop{\mathrm{supp}}(g)\subseteq[k-1]\},\) which satisfies \(\mathop{\mathrm{VCdim}}(\mathcal{G})=k-1.\) As \(\mathop{\mathrm{supp}}(h_e)\) does not contain any elements smaller than \(k,\) the supports of hypotheses from \(\mathcal{G}\) and \(\mathcal{H}_E\) are always disjoint. Lemma 2 now yields that their direct sum \(\mathcal{H}^{k,\ell}\mathrel{\vcenter{:}}= \mathcal{G}\oplus\mathcal{H}_E\) has VC-dimension exactly \(k\).

III. Decidability of \(\mathcal{H}^{k,\ell}\): We describe how membership in \(\mathcal{H}^{k,\ell}\) can be decided from the list representation of \(\mathop{\mathrm{\mathcal{H}_{\mathrm{fin}}}}\). This already gives that \(\mathcal{H}^{k,\ell}\) is RER, as \(\mathop{\mathrm{\mathcal{H}_{\mathrm{fin}}}}\) is an RER class itself.

Given any \(h\in \mathop{\mathrm{\mathcal{H}_{\mathrm{fin}}}},\) first check if there is at most one odd number \(x> k\) in \(\mathop{\mathrm{supp}}(h)\). Return NO if more than one \(x\) is found. If there is none, check for \(\mathop{\mathrm{supp}}(h)\subseteq[k-1]\) and return YES, if this is true and NO otherwise. If there is exactly one such odd number \(x\), try to compute some \(e,s\in \mathbb{N}\) with \(x=2\cdot 3^e\cdot 5^s+k+1.\) If no such \(e\) and \(s\) exist, output NO. Otherwise, compute \(\mathop{\mathrm{code}}(T_e)\), \(k_e\) and \(I^e\) and run (at most) \(s\) steps of \(T_e\) on the input \(I^e\). If \(T_e\) halts after exactly \(s\) steps, check if the output is some tuple \(o^e\in \mathcal{Y}^{k_e}.\) This is true if and only if \(e\in E,\) \(s=s_e\) and \(x=u_e\). Now verify \(h(I_i^e)=o^e_i\) for all \(i=1,\ldots, k_e.\) Lastly, check if all elements of \(\mathop{\mathrm{supp}}(h),\) except \(x\) and the ones from \(I^e,\) are elements of \([k-1].\) If all of this is true, then it must hold \(h=g+h_e\) for some \(g\in \mathcal{G}\), thus return YES. In any other case output NO.

\(\boldsymbol{IV.~eVCdim(}\mathcal{H}^{k,\ell}\boldsymbol{)}\leq \ell\colon\) We describe a computable \(\ell\)-witness for \(\mathcal{H}^{k,\ell}\) in the case \(\ell<\infty\). So we have to find a computable function \(w\colon \mathbb{N}^{\ell+1}\to \mathcal{Y}^{\ell+1}\) such that for all \(h\in \mathcal{H}^{k,\ell}\) and distinct \(x_0,\ldots, x_\ell\in \mathcal{X}\) it holds \[\label{eq32dagger} w(x_0,\ldots, x_\ell)\neq (h(x_0),\ldots, h(x_\ell)).\tag{8}\] Given any input \((x_0,\ldots, x_\ell)\in \mathcal{X}^{\ell+1}\), first check if all entries are pair-wise distinct. If not, \(w\) outputs \(0\). Otherwise, we use the decision procedure described in step III to check whether the hypothesis \(f\) with \(\mathop{\mathrm{supp}}(f)=\{x_0,\ldots, x_\ell\}\) lies in \(\mathcal{H}^{k,\ell}\). In the case \(f\notin \mathcal{H}^{k,\ell}\), \(w\) simply returns \((1,\ldots, 1).\) Then the desired condition 8 holds for any \(h\in \mathcal{H}^{k,\ell}\) due to the fact \(|\mathop{\mathrm{supp}}(h)|\leq \ell+1.\)

Now consider the case \(f\in \mathcal{H}^{k,\ell}.\) By the construction of \(\mathcal{H}^{k,\ell}\) there must be some \(e\in E\) such that \(k_e=\ell-k+1,\) \(o^e=(1,\ldots, 1)\) and \(f=\mathbb{1}_{[k-1]}+h_e.\) In particular, \(\{x_0,\ldots, x_\ell\}=[k-1]\cup \mathop{\mathrm{supp}}(h_e).\) Using the same procedure as in step III, we can compute this index \(e\in E\) and the \(i\leq \ell\) with \(x_i=u_e\), which is the unique odd number \(>k\) in \(\mathop{\mathrm{supp}}(h_e).\) Now \(w(x_0,\ldots, x_\ell)\) is defined as the tuple that is \(1\) everywhere, except at the position \(i,\) where we set it to \(0\). With this choice condition 8 is satisfied for any \(h\in \mathcal{H}^{k,\ell}\) with \(h(x_i)=1.\) Now consider \(h\in \mathcal{H}^{k,\ell}\) with \(h(x_i)=0.\) Write \(h=g+h_{e'}\) for some \(e'\in E\) and \(g\in \mathcal{G}.\) Because of \(h_{e'}(x_i)=0,\) it must hold \(e'\neq e.\) By assumption we have \(|\mathop{\mathrm{supp}}(h_e)|=k_e+1\geq 2,\) so there is some \(x_j\in \mathop{\mathrm{supp}}(h_e)\backslash\{x_i\}\). From \(\mathop{\mathrm{supp}}(h_{e'})\cap \mathop{\mathrm{supp}}(h_e)=\varnothing,\) it follows \(h(x_j)=0.\) So 8 holds for \(h\) as \(w(x_0,\ldots, x_\ell)\) is 1 at position \(j\).

\(\boldsymbol{V.~eVCdim(}\mathcal{H}^{k,\ell}\boldsymbol{)}\geq \ell\colon\) It suffices to show that \(\mathcal{H}^{k,\ell}\) has no computable \((\ell-1)\)-witness. If \(\ell=\infty\) replace \(\ell\) by any number \(\geq k\) in the following. Assume that there was a computable \((\ell-1)\)-witness \(w\colon \mathcal{X}^\ell\to \mathcal{Y}^\ell\) for \(\mathcal{H}^{k,\ell}\). Consider the computable function \(\tilde{w}\colon \mathcal{X}^{\ell-k+1}\to \mathcal{Y}^{\ell-k+1}\) with \[\begin{align} \tilde{w}(x_0,\ldots, x_{\ell-k})= \text{last (\ell-k+1) entries of } w(1,\ldots, k-1, x_0,\ldots, x_{\ell-k}). \end{align}\] By construction there is some \(e\in E\) such that \(T_e\) computes the function \(\tilde{w}\) and \(k_e=\ell-k+1\). Thus by our choices \[\tilde{w}(I^e)=o^e=(h_e(I^e_1),\ldots, h_e(I^e_{k_e})).\] Also note that there is \(g\in \mathcal{G}\) with \[(g(1),\ldots, g(k-1))= \text{the first (k-1) entries of } w(1,\ldots, k-1,I^e).\] Altogether, the hypothesis \(h\mathrel{\vcenter{:}}= g+h_e\in \mathcal{H}^{k,\ell}\) satisfies \[\begin{align} w(1,\ldots, k-1,I^e) =(h(1),\ldots, h(k-1),h(I^e_1),\ldots, h(I^e_{k_e})). \end{align}\] This contradicts \(w\) being an \((\ell-1)\)-witness for \(\mathcal{H}^{k,\ell}.\) ◻