On Generation in Metric Spaces Jiaxun Li, Vinod Raman, Ambuj Tewari Abstract We study generation in separable metric instance spaces. We extend the language generation framework from 13 beyond countable domains by defining novelty through metric separation and allowing asymmetric novelty parameters for the adversary and the generator. We introduce the ( ε , ε ′ ) (\varepsilon,\varepsilon^{\prime}) -closure dimension, a scale-sensitive analogue of closure dimension, which yields characterizations of uniform and non-uniform generatability and a sufficient condition for generation in the limit. Along the way, we identify a sharp geometric contrast. Namely, in doubling spaces, including all finite-dimensional normed spaces, generatability is stable across novelty scales and invariant under equivalent metrics. In general metric spaces, however, generatability can be highly scale-sensitive and metric-dependent; even in the natural infinite-dimensional Hilbert space ℓ 2 \ell^{2} , all notions of generation may fail abruptly as the novelty parameters vary. 1 Introduction LLMs are trained on massive amounts of data from which they learn to generate new, previously unseen, grammatically valid strings in a natural language such as English. 13 recently provided an elegant framework that captures the essence of generation. In their model, the learner receives a sequence of strings from an adversary drawn from a language in a known language collection. The learner has to generate novel valid strings from the true language that is initially unknown to the learner. This framework is inspired by the seminal work of 7 on language identification in the limit. In 7 ’s model, an adversary enumerates strings from a language in a collection. The learner’s task is to identify the true language from only the positive examples shown by the adversary. 13 changed the identification requirement to generation: the learner has to generate novel, unseen strings from the true language. This simple change, from identification to generation, completely changes the nature of provable guarantees. On the one hand, since the seminal characterization by 3 of language collections identifiable in the 7 model, we know that very few natural collections are identifiable in the limit. On the other hand, 13 showed that any countable collection is generatable in the limit. They also connected their theoretical findings to empirical phenomena such as under-generation (mode collapse) and over-generation (hallucination). Their elegant framework and surprising results have led to a flurry of work on extending their basic framework in various interesting directions. In particular, a recent work ( 21 ) examined characterizations of various variants of the language generation model, including generation in the limit, non-uniform generation, and uniform generation. However, like much of the work on the language generation model, this work also assumed that the example space is countable . Because no additional structure is assumed, the only formalization of “novelty” is that the generated object be distinct from previously seen objects. There is no way to ensure that the object is “different enough.” However, generative AI is now being used to generate objects in spaces with rich structure. In such spaces, the assumption of countability becomes restrictive. For example, a neural surrogate for an SDE solver might generate random functions over a spatial domain ( 16 ) . A generative model for proteins has to not only model their 3D structure in a continuous space but also respect translational and rotational symmetries ( 9 ) . Inspired by applications in spaces with richer structure, in this paper we initiate the study of generation in metric spaces . 1.1 Main Contributions This work initiates a theoretical study of generation in metric spaces , extending prior learning-theoretic frameworks that were restricted to countable example spaces. Our main contributions are as follows: • We extend the language generation model to separable metric instance spaces \mathcal{X} , while retaining binary hypothesis classes \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} . We introduce a notion of novelty based on metric separation rather than mere distinctness, and define two independent novelty parameters for the adversary and the generator. This leads to a strictly richer and nontrivial generalization of the countable setting. • We introduce the (\varepsilon,\varepsilon^{\prime}) -closure dimension, a metric analogue of closure dimension that explicitly depends on scale. Using this notion, we obtain complete characterizations of uniform and non-uniform generatability, as well as a sufficient condition for generation in the limit. Moreover, we generalize the algorithmic framework from the countable case to the metric space setting under appropriate oracle access. • In doubling spaces, including all finite-dimensional normed spaces, we show that generatability behaves in a well-controlled manner: uniform and non-uniform generatability is invariant to the choice of novelty scales and preserved under equivalent metrics. • Beyond doubling spaces, we demonstrate sharp and sometimes non-intuitive behaviors. Generatability can be very sensitive to the novelty parameters and to choices of metric. Our constructions show that all notions of generation can fail abruptly as scales change even in one of the simplest infinite-dimensional space \ell^{2} , highlighting a qualitative gap between finite and infinite-dimensional spaces. Extending generation to metric spaces presents several challenges. First, unlike in the countable setting, novelty can no longer be defined by distinctness alone and must instead reflect geometric separation. This necessitates introducing asymmetric novelty parameters for the adversary and the generator. Second, several characterization results in the countable example space setting rely explicitly on countability, for example through enumeration arguments, which do not extend to general metric spaces. Finally, due to the asymmetry between the adversary’s and the generator’s novelty parameters, constructing hypothesis classes and counterexamples requires careful consideration of their relative scales. 1.2 Related Work Our work builds on the framework of language generation in the limit, introduced by 13 . Since then, subsequent work has investigated a range of questions surrounding this language generation model. Here, we discuss the most relevant prior works. Uniform and Non-Uniform Generation 21 introduced stronger notions of generation: uniform and non-uniform generation, and provided characterization for uniform and non-uniform generation. 5 also, independently studied non-uniform generation and showed that all countable collections can be non-uniformly generated. 6 proposed an almost Pareto-optimal algorithm for non-uniform language generation. 8 studied unions of generatable classes and solved two open problems posed by 21 . Extensions of Language Generation Several extensions of language generation have been proposed. 20 , 18 and 4 investigated language generation with contamination, in which the adversary is allowed to omit instances or generate instances outside the language. 19 studied representative generation, in which the generator needs to output a distribution that is representative of the seen data. 2 introduced and investigated safe language generation, in which there exists a harmful language that the generator needs to avoid. Other Related Work Several follow-up studies have proposed and studied different definitions of breadth in the language generation model, and showed that requiring the generator to generate diverse instances from the target language makes generation significantly harder ( 11 ; 12 ; 14 ; 15 ) . 1 study language identification in a metric space setting by revisiting the classical identification in the limit framework and extending it to scenarios where distances between languages are measured by a metric. In contrast, our work adopts a fundamentally different perspective: we study generation rather than identification, and the metric structure is imposed on the instance space rather than on the space of languages. 2 Preliminaries 2.1 Example Space and Hypothesis Class Throughout the paper, we let \mathcal{X} , the example space, be a separable metric space , i.e., a metric space with a countable dense subset. Let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} be a binary hypothesis class. For a hypothesis h\in\mathcal{H} , let \text{supp}(h):=\{x\in\mathcal{X}:h(x)=1\} , that is, its collection of positive examples. For any class \mathcal{H} and a finite sequence of examples x_{1},\dots,x_{n} , define the version space as: \mathcal{H}(x_{1},\dots,x_{n}):=\{h\in\mathcal{H}:\{x_{1},\dots,x_{n}\}\subseteq\operatorname{supp}(h)\}. For any class \mathcal{H} , define its induced closure operator \langle\cdot\rangle_{\mathcal{H}} as: \langle x_{1},\dots,x_{n}\rangle_{\mathcal{H}}:=\begin{cases}\bigcap_{h\in\mathcal{H}(x_{1:n})}\operatorname{supp}(h),&\text{if $|\mathcal{H}(x_{1:n})|\geq 1$}\\ \bot,&\text{if $|\mathcal{H}(x_{1:n})|=0$}\end{cases}. Intuitively, \langle x_{1},\dots,x_{n}\rangle_{\mathcal{H}} captures the set of points that must belong to the target hypothesis given consistency with the observed examples. We will also need several other definitions about metric spaces. Definition 2.1 (Closed Ball) . Assume \mathcal{X} is a separable metric space equipped with metric \rho(\cdot,\cdot) . For a point x\in\mathcal{X} or a set A\subseteq\mathcal{X} , we denote by B(x,\varepsilon) or B(A,\varepsilon) the closed \varepsilon -balls centered at x or A , respectively, defined as B(x,\varepsilon):=\{y\in\mathcal{X}:\rho(x,y)\leq\varepsilon\},\qquad B(A,\varepsilon):=\{y\in\mathcal{X}:\inf_{x\in A}\rho(x,y)\leq\varepsilon\}. Definition 2.2 (Covering Number) . Let (\mathcal{X},\rho) be a metric space and \varepsilon>0 . An \varepsilon -covering of a set A\subseteq\mathcal{X} is a finite set \{\theta_{1},\dots,\theta_{M}\}\subset\mathcal{X} such that A\subset B(\{\theta_{i}\}_{i=1}^{M},\varepsilon) . The \varepsilon -covering number N(\varepsilon;A,\rho) is defined as N(\varepsilon;A,\rho):=\min\left\{M\in\mathbb{N}:\exists\ \varepsilon\text{-covering of }A\text{ with }M\text{ points}\right\}. If no such finite covering exists, we write N(\varepsilon;A,\rho)=\infty . To prevent the adversary from exhausting all positive examples and thus making the task of generating unseen positive examples impossible, we make the following assumption for the hypothesis set. This assumption extends a similar condition used in previous work on generation in the countable example space setting (see Definition A.1 ). Definition 2.3 ( r -Uniformly Unbounded Support ( r -UUS)) . For some r>0 , a hypothesis class \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} satisfies the r -Uniformly Unbounded Support ( r -UUS) property if for every h\in\mathcal{H} , N(r;\operatorname{supp}(h),\rho)=\infty. The r -UUS property satisfies the following monotonicity result, which we prove in Appendix D . Lemma 2.1 . Let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} be any class satisfying the r -UUS property for an r>0 . Then for any positive \delta0 and let 0<\varepsilon,\varepsilon^{\prime}\leq r . If there exists a generator \mathcal{G} such that for every h\in\mathcal{H} , and any sequence \{x_{i}\}_{i=1}^{\infty}\subseteq\operatorname{supp}(h) such that \operatorname{supp}(h)\subseteq B(\{x_{i}\}_{i=1}^{\infty},\varepsilon) (i.e., the adversary eventually reveals an \varepsilon -cover of the support), there exists a t^{\star}\in\mathbb{N} such that \mathcal{G}(x_{1:s})\in\operatorname{supp}(h)\setminus B(\{x_{i}\}_{i=1}^{s},\varepsilon^{\prime}) for all s\geq t^{\star} , then we say \mathcal{H} is ( \varepsilon,\varepsilon^{\prime} )-generatable in the limit . Remark 2.1 . The assumption \operatorname{supp}(h)\subseteq B(\{x_{i}\}_{i=1}^{\infty},\varepsilon) is an analogous to the enumeration assumption in the countable example space setting (see Definition A.2 ). It requires the adversary to eventually show the whole structure of the hypothesis set to the generator. For the rest of the paper, \varepsilon governs the adversary’s revelation scale, while \varepsilon^{\prime} governs the generator’s novelty requirement. Our definition above is intentionally general and does not specify the relative magnitudes of \varepsilon and \varepsilon^{\prime} . This is because the relative magnitudes of novelty on the adversary and generator sides are application dependent. For example, consider authors preparing a paper submission to a conference. An experienced author may read several papers that are closely related in topics (corresponding to a small \varepsilon for adversary) yet generate a paper that is substantially different, for example, by introducing a new technique or applying known methods to a new problem. In this case the generator’s \varepsilon^{\prime} is larger than than the adversary’s \varepsilon . Alternatively, a beginning researcher may read a very diverse set of papers spanning many topics (a large \varepsilon ), yet generate a paper closely aligned with one of them, such as by extending an existing line of work. Here, the generator’s \varepsilon^{\prime} is smaller than the adversary’s \varepsilon . Our definition of generatability in the limit is designed to encompass both behaviors. Next, we extend two strengthenings of the notion of generation in the limit introduced by 21 . The first notion, called uniform generation, is the strongest. It requires the number t^{\star} in Definition 2.5 (which is the number of samples required by the generator before it starts generating consistently) to be independent of both the target hypothesis set and the sequence of instances. Definition 2.6 (Uniform Generatability) . Let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} be any hypothesis class satisfying the r - \operatorname{UUS} property for some r>0 and let 0<\varepsilon,\varepsilon^{\prime}\leq r . If there exists a generator \mathcal{G} and d^{\star}\in\mathbb{N} , such that for every h\in\mathcal{H} and any sequence \{x_{i}\}_{i=1}^{\infty}\subseteq\operatorname{supp}(h) , if there exists t such that N(\varepsilon;\{x_{i}\}_{i=1}^{t},\rho)\geq d^{\star} , then \mathcal{G}(x_{1:s})\in\operatorname{supp}(h)\setminus B(\{x_{i}\}_{i=1}^{s},\varepsilon^{\prime}) for all s\geq t , then we say \mathcal{H} is ( \varepsilon,\varepsilon^{\prime} )-uniformly generatable . The second is called non-uniform generation, which requires the number t^{\star} in Definition 2.5 to only be independent of the sequence of instances (i.e., it can depend on the target hypothesis). Definition 2.7 (Non-Uniform Generatability) . Let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} be any hypothesis class satisfying the r - \operatorname{UUS} property for some r>0 and let 0<\varepsilon,\varepsilon^{\prime}\leq r . If there exists a generator \mathcal{G} such that for every h\in\mathcal{H} there exists a d_{h}\in\mathbb{N} , such that for any sequence \{x_{i}\}_{i=1}^{\infty}\subseteq\operatorname{supp}(h) , if there exists t such that N(\varepsilon;\{x_{i}\}_{i=1}^{t},\rho)\geq d_{h} , then \mathcal{G}(x_{1:s})\in\operatorname{supp}(h)\setminus B(\{x_{i}\}_{i=1}^{s},\varepsilon^{\prime}) for all s\geq t , then we say \mathcal{H} is ( \varepsilon,\varepsilon^{\prime} )-non-uniformly generatable . It is clear that our framework strictly generalizes the countable example space setting considered in 21 . This is achieved by equipping a countable example space with the discrete \{0,1\} -metric. We include a formal proposition in Appendix D for completeness sake. 3 Characterizations of Generatability In this section, we characterize hypothesis classes that are uniformly and non-uniformly generatable, and we provide a sufficient condition for generatability in the limit. We show that, despite the additional metric structure, the resulting characterizations closely parallel those obtained in the countable example space setting (see Appendix A for more details). Consequently, we state the main results in this section and defer the proofs to Appendix B . In Appendix E , we also have a discussion about the computability of generation. Although these characterizations are straightforward, generation in metric spaces exhibits several counterintuitive phenomena that do not arise in the countable example space setting. We explore these phenomena in more detail in Section 4 . We first extend the techniques from 21 to account for metric space structure. As a result, we first define a metric analog of the Closure dimension originally defined for countable example space (see Definition A.5 ). Definition 3.1 ( (\varepsilon,\varepsilon^{\prime}) -Closure dimension) . The (\varepsilon,\varepsilon^{\prime}) -Closure dimension of \mathcal{H} , denoted \operatorname{C}_{\varepsilon}^{\varepsilon^{\prime}}(\mathcal{H}) , is the largest d\in\mathbb{N} such that there exist h\in\mathcal{H} and a sequence \{x_{i}\}_{i=1}^{t}\subseteq\operatorname{supp}(h) satisfying N(\varepsilon;\{x_{i}\}_{i=1}^{t},\rho)=d\quad\text{and}\quad N(\varepsilon^{\prime};\langle x_{1},\dots,x_{t}\rangle_{\mathcal{H}},\rho)<\infty. If the above holds for arbitrarily large d\in\mathbb{N} , we set \operatorname{C}_{\varepsilon}^{\varepsilon^{\prime}}(\mathcal{H})=\infty . If no such sequence exists for d=1 , we set \operatorname{C}_{\varepsilon}^{\varepsilon^{\prime}}(\mathcal{H})=0 . Unlike the Closure dimension, the (\varepsilon,\varepsilon^{\prime}) -Closure dimension is scale-sensitive . In Section 4 we will further explore its property for different scales of \varepsilon and \varepsilon^{\prime} . Our first theorem uses this dimension to provide a complete characterization of which classes are uniform generatable. Theorem 3.1 (Characterization of Uniform Generatability) . Let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} be any hypothesis class satisfying the r - \operatorname{UUS} property for some r>0 and let 0<\varepsilon,\varepsilon^{\prime}\leq r . Then, \mathcal{H} is (\varepsilon,\varepsilon^{\prime}) -uniformly generatable if and only if \operatorname{C}_{\varepsilon}^{\varepsilon^{\prime}}(\mathcal{H})<\infty . Similarly to the countable example space setting, for every finite hypothesis class \mathcal{H} satisfying the r -UUS property with \varepsilon\geq\varepsilon^{\prime} , we have \operatorname{C}_{\varepsilon}^{\varepsilon^{\prime}}(\mathcal{H})<\infty . In contrast, when \varepsilon<\varepsilon^{\prime} , there exists a finite hypothesis class that is not non-uniformly generatable. Intuitively, if the generator is required to produce outputs that are more novel than those revealed by the adversary, the generation task may become impossible. Further discussion is provided in Appendix B . Corollary 3.2 (Finite Classes are Uniformly Generatable) . Let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} be any finite hypothesis class satisfying the r - \operatorname{UUS} property for some r>0 and let 0<\varepsilon,\varepsilon^{\prime}\leq r such that \varepsilon^{\prime}\leq\varepsilon . Then, \mathcal{H} is (\varepsilon,\varepsilon^{\prime}) -uniformly generatable. We next move to characterize non-uniform generatability. We show that our characterization of uniform generatability leads to a characterization of non-uniform generatability. Theorem 3.3 (Characterization of Non-uniform Generatability) . Let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} be any hypothesis class satisfying the r - \operatorname{UUS} property for some r>0 and let 0<\varepsilon,\varepsilon^{\prime}\leq r . The following statements are equivalent. (i) \mathcal{H} is (\varepsilon,\varepsilon^{\prime}) -non-uniformly generatable. (ii) There exists a non-decreasing sequence of classes \mathcal{H}_{1}\subseteq\mathcal{H}_{2}\subseteq\dots such that \mathcal{H}=\bigcup_{i\in\mathbb{N}}\mathcal{H}_{i} and \operatorname{C}_{\varepsilon}^{\varepsilon^{\prime}}(\mathcal{H}_{n})<\infty for every n\in\mathbb{N}. An immediate consequence of combing Corollary 3.2 and Theorem 3.3 is the following corollary. Corollary 3.4 (Countable Classes are Non-uniformly Generatable) . Let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} be any countable hypothesis class satisfying the r - \operatorname{UUS} property for some r>0 and let 0<\varepsilon,\varepsilon^{\prime}\leq r such that \varepsilon^{\prime}\leq\varepsilon . Then, \mathcal{H} is (\varepsilon,\varepsilon^{\prime}) -non-uniformly generatable. We finally give a sufficient condition for generatability in the limit by showing the finite union of uniform generatable classes are generatable in the limit. Theorem 3.5 (Sufficient Condition for Generatability in the Limit) . Let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} be any class satisfying the r - UUS property for some r>0 and let 0<\varepsilon,\varepsilon^{\prime}\leq r . If there exists a finite sequence of classes \mathcal{H}_{1},\dots,\mathcal{H}_{n} such that \mathcal{H}=\bigcup_{i=1}^{n}\mathcal{H}_{i} and \operatorname{C}_{\varepsilon}^{\varepsilon^{\prime}}(\mathcal{H}_{i})<\infty for all i\in[n] , then \mathcal{H} is (\varepsilon,\varepsilon^{\prime}) -generatable in the limit. It is worth noting that characterizing generation in the limit is already subtle even in the absence of any metric structure ( 21 ) . Nevertheless, we show that our sufficient condition is in an “almost necessary” sense, as suggested by the counterintuitive behavior of generatability under unions. The proof is also shown in Appendix B . Theorem 3.6 . Let (\mathcal{X},\rho) be any metric space. For any r>0,0\leq\varepsilon,\varepsilon^{\prime}\leq r/2 such that N(r;\mathcal{X},\rho)=\infty , there exists \mathcal{H}_{1}\subseteq\{0,1\}^{\mathcal{X}} and \mathcal{H}_{2}\subseteq\{0,1\}^{\mathcal{X}} such that \mathcal{H}_{1} is (\varepsilon,\varepsilon^{\prime}) -uniformly generatable, \mathcal{H}_{2} is (\varepsilon,\varepsilon^{\prime}) -non-uniformly generatable, but \mathcal{H}_{1}\cup\mathcal{H}_{2} is not (\varepsilon,\varepsilon^{\prime}) -generatable in the limit. 4 Properties of Generatability Beyond the structure of the hypothesis class itself, generatability depends on two additional parameters: the novelty thresholds with respect to the adversary and the generator, denoted by \varepsilon and \varepsilon^{\prime} , respectively. In this section, we study how generatability varies as these novelty parameters change. We also investigate generatability under different metrics defined on the same underlying space. 4.1 Generatability is Well Behaved in Doubling Spaces We first establish a robustness result for generatability in doubling spaces. A doubling space is a metric space in which balls at one scale can be covered by finitely many balls at any smaller scale. In such spaces, we show that, both uniform and non-uniform generatability are invariant across all choices of scale parameters \varepsilon and \varepsilon^{\prime} , and are preserved under any change to an equivalent metric. Definition 4.1 . A metric space \mathcal{X} with metric \rho is said to be doubling if there exists a constant M>0 such that for any x\in\mathcal{X} and any r>0 , the ball B(x,r) can be covered by at most M balls of radius r/2 . We first show a stronger result than Lemma 2.1 : in doubling spaces, the r -UUS property is invariant to the choice of the scale parameter r . The proof is deferred to Appendix D for completeness. Theorem 4.1 . Let \mathcal{X} be a doubling metric space with metric \rho . Suppose \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} is a class satisfying r -UUS property for some r>0 . Then it also satisfies the r^{\prime} -UUS property for any r^{\prime}>0 . In this case, we simply say that \mathcal{H} has the UUS property. We are now ready to present robustness results for uniform and non-uniform generatability in doubling spaces. Theorem 4.2 . Let \mathcal{X} be a doubling metric space with metric \rho . Let \varepsilon,\varepsilon^{\prime},\delta,\delta^{\prime}>0 satisfy 0<\delta<\varepsilon and 0<\delta^{\prime}<\varepsilon^{\prime} . Suppose \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} satisfies the UUS property. Then \mathcal{H} is (\varepsilon,\varepsilon^{\prime}) -uniformly (resp. non-uniformly) generatable if and only if it is (\delta,\delta^{\prime}) -uniformly (resp. non-uniformly) generatable. Proof. By Theorem 3.1 and 3.3 , we only need to show that \operatorname{C}_{\varepsilon}^{\varepsilon^{\prime}}(\mathcal{H})<\infty if and only if \operatorname{C}_{\delta^{\prime}}^{\delta^{\prime}}(\mathcal{H})<\infty . Since \mathcal{X} is a doubling space, there exists C such that for any x\in\mathcal{X} , B(x,\varepsilon) can be covered by the union of at most C balls of radius \delta and B(x,\varepsilon^{\prime}) can be covered by the union of at most C balls of radius \delta^{\prime} . Then under our assumption, for any subset A\subseteq\mathcal{X} , N(\varepsilon;A,\rho)=\infty\iff N(\delta;A,\rho)=\infty. And if N(\varepsilon;A,\rho)<\infty , we have N(\varepsilon;A,\rho)\leq N(\delta;A,\rho)\leq CN(\varepsilon;A,\rho). Comparing with the definition of the closure dimension completes the proof. ∎ It is well known that Euclidean space \mathbb{R}^{d} is a doubling metric space. As a result, we have the following corollary: Corollary 4.3 . In any finite-dimensional normed vector space \mathcal{X} , if \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} satisfies the UUS property, then for any \varepsilon,\varepsilon^{\prime},\delta,\delta^{\prime}>0 , \mathcal{H} is (\varepsilon,\varepsilon^{\prime}) -uniformly (resp. non-uniformly) generatable if and only if it is (\delta,\delta^{\prime}) -uniformly (resp. non-uniformly) generatable. We next study how the generatability behave under changes of the underlying metric. The proof is similar to that of Theorem 4.2 so we defer it to Appendix D . Theorem 4.4 . Let \mathcal{X} be a doubling metric space with metrics \rho_{1} and \rho_{2} such that \rho_{1} is equivalent with \rho_{2} . Suppose \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} is a hypothesis class. Then, it satisfies the UUS property with respect to \rho_{1} if and only if it satisfies the UUS property with respect to \rho_{2} . Moreover, \mathcal{H} is uniformly (resp. non-uniformly) generatable with respect to \rho_{1} if and only if it is uniformly (resp. non-uniformly) generatable with respect to \rho_{2} . So far, we have established the desired stability properties of uniform and non-uniform generation in doubling metric spaces. What about generation in the limit? Unfortunately, pathological phenomena can occur: generatability can change abruptly when changing the scale parameters \varepsilon or \varepsilon^{\prime} across a threshold. We present such an example in Example 4.5 here and leave the construction and proof to Appendix C . Example 4.5 . In the space of real numbers, \mathbb{R} , there is a hypothesis class \mathcal{H} that satisfies the UUS property, and is (\varepsilon,1) -generatable in the limit for any \varepsilon\in(0,1) , but not (1,1) -generatable in the limit. These examples illustrate phenomena that are specific to generation in metric spaces and are examined in more detail in the next section. 4.2 Generatability is Scale-Sensitive So far we have seen that generatability behaves stable in a doubling space. When moving forward to general, potentially infinite-dimensional, metric spaces, however, such robust properties do not hold any more. Generatability becomes depending on novelty parameters \varepsilon and \varepsilon^{\prime} , and the underlying metric of the space. Informally, consider the generation game as follows: The adversary reveals instances from a hypothesis set h that are mutually \varepsilon -separated, while the generator must eventually produce instances in h that are at least \varepsilon^{\prime} -far from all previously observed ones. Intuitively, the game becomes easier when \varepsilon is larger, since the adversary is forced to reveal more widely separated instances, allowing the generator to observe new regions of the hypothesis support. Similarly, the game also becomes easier when \varepsilon^{\prime} is smaller, as this permits the generator to generate instances with less novelty relative to those already observed. In this section, we establish monotonicity results with respect to both \varepsilon and \varepsilon^{\prime} . For uniform and non-uniform generation, the results align with this intuition: if a hypothesis class \mathcal{H} is (\varepsilon,\varepsilon^{\prime}) -uniformly (resp. non-uniformly) generatable, then it remains so when \varepsilon is increased or \varepsilon^{\prime} is decreased. We illustrate this behavior with an example in the \ell^{2} space as Example 4.9 , where increasing \varepsilon or decreasing \varepsilon^{\prime} makes generation easier. Notably, this example also shows a separation between all finite dimensional metric spaces, and the infinite-dimensional space \ell^{2} . Depending on the choice of scale parameters \varepsilon and \varepsilon^{\prime} , the same hypothesis class can exhibit all possible regimes of generatability, ranging from not generatable in the limit to uniformly generatable. This phenomenon cannot occur in a doubling space. The situation for generation in the limit is more subtle, as already illustrated by Example 4.5 . When considering generation in the limit, monotonicity holds only when \varepsilon is decreased. In contrast, increasing \varepsilon can cause generatability to fail: a hypothesis class may be (\varepsilon,\varepsilon^{\prime}) -generatable in the limit for small \varepsilon , yet lose this property once \varepsilon exceeds a threshold. Example 4.8 demonstrates that, in \ell^{2} , generatability in the limit can disappear when \varepsilon and \varepsilon^{\prime} exceed such thresholds. Moreover, in contrast to Example 4.5 in the doubling-space setting, Example 4.8 is more general: the threshold values of \varepsilon and \varepsilon^{\prime} at which generatability fails can be chosen arbitrarily. (a) Illustration of Example 4.8 , showing generatability in the limit can disappear when \varepsilon and \varepsilon^{\prime} exceed a threshold. (b) Illustration of Example 4.9 , showing increasing \varepsilon or decreasing \varepsilon^{\prime} makes generation easier. Figure 1: Illustration of two generation regimes in a metric space. The horizontal axis represents the adversary parameter, and the vertical axis represents the generator parameter. Theorem 4.6 . Let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} be any hypothesis class satisfying the r - \operatorname{UUS} property for some r>0 and let 0<\varepsilon,\varepsilon^{\prime}\leq r . If \mathcal{H} is (\varepsilon,\varepsilon^{\prime}) -generatable in the limit, then for any positive \delta\leq\varepsilon , \delta^{\prime}\leq\varepsilon^{\prime} , \mathcal{H} is (\delta,\delta^{\prime}) -generatable in the limit. Theorem 4.7 . Let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} be any hypothesis class satisfying the r - \operatorname{UUS} property for some r>0 and let 0<\varepsilon,\varepsilon^{\prime}\leq r . If \mathcal{H} is (\varepsilon,\varepsilon^{\prime}) -uniformly (or non-uniformly) generatable in the limit, then for any \varepsilon\leq\delta\leq r and 0<\delta^{\prime}\leq\varepsilon^{\prime} , \mathcal{H} is (\delta,\delta^{\prime}) -uniformly (or non-uniformly) generatable in the limit. Theorems 4.6 and 4.7 establish monotonicity with respect to both \varepsilon and \varepsilon^{\prime} for all three notions of generation, which we prove in Appendix D . Example 4.8 . In \ell^{2} -space, for any r>0 and any 0<\varepsilon,\varepsilon^{\prime},\gamma,\gamma^{\prime}\leq r , there exists a hypothesis class \mathcal{H}\subseteq\{0,1\}^{\ell^{2}} satisfying the r - \operatorname{UUS} property and is (\gamma,\gamma^{\prime}) -generatable in the limit for any \gamma<\varepsilon,\gamma^{\prime}<\varepsilon^{\prime} . Moreover, it is not (\gamma,\gamma^{\prime}) -generatable in the limit if \gamma\geq\varepsilon or \gamma^{\prime}\geq\varepsilon^{\prime} . Figure 1a gives an illustration of this example. We now present the construction and the underlying intuition here, and defer the full proof to Appendix C . Recall that \ell^{2} is the space that contains all sequences (x_{i})_{i=1}^{\infty} such that \sum_{i}x_{i}^{2}<\infty . Let e_{k}\in\ell^{2} denote the k -th standard basis vector. Define u_{k}:=2r\cdot e_{k},\qquad a_{k}:=\varepsilon\cdot e_{k},\qquad g_{k}:=\varepsilon^{\prime}\cdot e_{k}. Let \mathcal{I} be the set of all infinite subsets of \mathbb{N}_{+} , i.e., \mathcal{I}=\{I|I\in 2^{\mathbb{N}_{+}},|I|=\infty\} . For I\in\mathcal{I} , let U_{I}=\{u_{k}|k\in I\},\quad O_{I}=\{a_{2k}|k\in I\}\cup\{g_{2k^{n}+1}|k\in I,n\in\mathbb{N}\},\quad D_{I}=\{g_{2k+1}|k\in I\} and construct the hypothesis class \mathcal{H} such that \mathcal{H}=\{h_{I_{1},I_{2},I_{3}}|I_{1},I_{2},I_{3}\in\mathcal{I},\quad\operatorname{supp}(h_{I_{1},I_{2},I_{3}})=\{\mathbf{0}\}\cup U_{I_{1}}\cup O_{I_{2}}\cup D_{I_{3}}\} Here, u_{k} and U_{I} are constructed to ensure that \mathcal{H} satisfies the r -UUS property. As will be seen in the proof, the points a_{k} are constructed for the adversary, while the points g_{k} are constructed for the generator. In fact, the g_{k} are the only instances with an explicit structure, which enables the generator to repeatedly produce them. The set O_{I} is the optimal set : once the adversary reveals some a_{k}\in O_{I} , the generator can generate g_{k} infinitely often. In contrast, D_{I} is the disturbing set : if the adversary continues to reveal g_{k}\in D_{I} , then the generator fails to generate in the limit. Intuitively, when \gamma<\varepsilon and \gamma^{\prime}<\varepsilon^{\prime} , since the adversary must choose a sequence \{x_{i}\}_{i=1}^{\infty} such that \operatorname{supp}(h)\subseteq B(\{x_{i}\}_{i=1}^{\infty},\gamma) , there must exist some time t at which x_{t}=a_{2k} for some k\in\mathbb{N} . From that point on, the generator is able to generate g_{2k^{n}+1} for any n\in\mathbb{N} . When \gamma^{\prime}\geq\varepsilon^{\prime} , on the other hand, as long as the adversary reveals \mathbf{0} , the generator cannot generate any g_{k} , since each g_{k} lies within the \gamma^{\prime} -ball centered at \mathbf{0} . Finally, when \gamma\geq\varepsilon , the adversary may choose to reveal only instances of the form \mathbf{0} , g_{k} , and u_{k} . The generator’s task is to uncover the structure of O_{I} and generate from it. However, due to the interference caused by D_{I} , the generator cannot distinguish whether the observed instances originate from O_{I} or from D_{I} , rendering generation in the limit impossible. Example 4.9 . In \ell^{2} -space, for any r>0 and any 0<\varepsilon_{1},\varepsilon_{2},\varepsilon^{\prime},\gamma,\gamma^{\prime}\leq r such that \varepsilon_{1}\leq\varepsilon_{2} , there exists a hypothesis class \mathcal{H}\subseteq\{0,1\}^{\ell^{2}} satisfying the r - \operatorname{UUS} property and is 1. (\gamma,\gamma^{\prime}) -uniformly generatable for any \gamma\in[\varepsilon_{2},r],\gamma^{\prime}\in(0,\varepsilon^{\prime}) . 2. (\gamma,\gamma^{\prime}) -non uniformly generatable but not uniformly generatable for any \gamma\in[\varepsilon_{1},\varepsilon_{2}) , \gamma^{\prime}\in~(0,\varepsilon^{\prime}) . 3. (\gamma,\gamma^{\prime}) -generatable in the limit but not non-uniformly generatable for any \gamma\in(0,\varepsilon_{1}) , \gamma^{\prime}\in~(0,\varepsilon^{\prime}) . 4. Not (\gamma,\gamma^{\prime}) -generatable in the limit for any \gamma\in(0,r],\gamma^{\prime}\in[\varepsilon^{\prime},r] . Figure 1b gives an illustration of this example. We also present the construction and the underlying intuition here, and defer the proof to Appendix C . Let e_{k}\in\ell^{2} denote the k -th standard basis vector. Define u_{k}:=2r\cdot e_{k},\qquad a_{k,1}:=\tfrac{\sqrt{2}}{2}\varepsilon_{1}\cdot e_{k},\qquad a_{k,2}:=\tfrac{\sqrt{2}}{2}\varepsilon_{2}\cdot e_{k},\qquad g_{k}:=\tfrac{\sqrt{2}}{2}\varepsilon^{\prime}\cdot e_{k}. Let \mathcal{I} be the set of all infinite subsets of \mathbb{N} , i.e., \mathcal{I}=\{I|I\in 2^{\mathbb{N}},|I|=\infty\} . Let \mathcal{I}_{\mathrm{fin}} be the set of all finite subsets of \mathbb{N} , i.e., \mathcal{I}_{\mathrm{fin}}=\{I|I\in 2^{\mathbb{N}},|I|<\infty\} . For I\in\mathcal{I} and J\in\mathcal{I}_{\mathrm{fin}} , let O_{I}=\{g_{k^{n}}|k\in I,n\in\mathbb{N}\}\cup\{u_{k}|k\in I\},\quad D_{I,J}=\{a_{k,1}|k\in I\}\cup\{a_{k,2}|k\in J\} and construct the hypothesis class \mathcal{H} such that \mathcal{H}=\{h_{I_{1},I_{2},J}|I_{1},I_{2}\in\mathcal{I},J\in\mathcal{I}_{\mathrm{fin}},\quad\operatorname{supp}(h_{I_{1},I_{2},J})=O_{I_{1}}\cup D_{I_{2},J}\}. Here, as in Example 4.8 , the points u_{k} are constructed to ensure that the hypothesis class satisfies the r -UUS property. The points a_{k,1} and a_{k,2} are constructed for the adversary, while the points g_{k} are constructed for the generator. The set O_{I} is the optimal set in the sense that once the adversary reveals any instance in this set, the generator is able to generate g_{k} infinitely many times. In contrast, D_{I,J} is the disturbing set : if the adversary continues to reveal instances a_{k,1} and a_{k,2} from this set, the generator fails to generate in the limit. Intuitively, when \gamma\geq\varepsilon_{2} and \gamma^{\prime}<\varepsilon^{\prime} , since \rho(a_{k_{1},j_{1}},a_{k_{2},j_{2}})\leq\varepsilon_{2} for any k_{1},k_{2}\in\mathbb{N} and j_{1},j_{2}\in\{1,2\} , the adversary can reveal at most one example from the disturbing set D_{I,J} . After that, as long as the generator observes any point from O_{I} , it can generate infinitely many instances of g_{k} , making this case uniformly generatable. When \gamma\in[\varepsilon_{1},\varepsilon_{2}) and \gamma^{\prime}<\varepsilon^{\prime} , the adversary can confuse the generator finitely many times by revealing instances of the form a_{k,2} , which makes this case non-uniformly generatable. When \gamma<\varepsilon_{1} and \gamma^{\prime}<\varepsilon^{\prime} , the adversary can confuse the generator infinitely many times by revealing instances of both a_{k,1} and a_{k,2} . However, since the game requires the adversary to reveal the entire structure of h , it must eventually reveal instances from the optimal set O_{I} , which makes this case generatable in the limit. Finally, when \gamma^{\prime}\geq\varepsilon^{\prime} , as long as the adversary reveals any instance g_{k} , the generator is unable to generate any g_{k} thereafter, making this case not generatable in the limit. 4.3 Generatability is Metric-Dependent In Section 4.1 , we showed that uniform generatability is invariant under changes to equivalent metrics. In contrast, in general metric spaces, generatability can depend on the underlying metric: even equivalent metrics on the same instance space may induce different generatability properties. We begin by establishing a stability result. Theorem 4.10 shows that if one metric is bounded by another, then both the UUS property and generatability in the limit transfer in a controlled manner, with the relevant parameters scaling linearly with the bounding constant. In this sense, generatability remains stable under sufficiently mild distortions of the metric. We present the proof in Appendix D . Theorem 4.10 . Let \mathcal{X} be a metric space with metric \rho_{1} and \rho_{2} . Assume there exists M>0 such that for any x,y\in\mathcal{X} , \rho_{2}(x,y)\leq M\rho_{1}(x,y) . Let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} be any class satisfying the r -UUS property for an r>0 with respect to \rho_{2} , and 0<\varepsilon,\varepsilon^{\prime}\leq r . Then \mathcal{H} satisfies the r/M -UUS property with respect to \rho_{1} . Moreover, if \mathcal{H} is (\varepsilon,\varepsilon^{\prime}) -generatable in the limit with respect to \rho_{2} , then \mathcal{H} is also (\varepsilon/M,\varepsilon^{\prime}/M) -generatable in the limit with respect to \rho_{1} . Our next example highlights a sharp contrast. Even when two metrics are equivalent in the topological sense, generatability need not be preserved. In particular, we construct an example in \ell^{2} showing that a hypothesis class can be uniformly generatable under the standard metric, yet fail to be non-uniformly generatable under an equivalent metric. We state the example and leave the full proof in Appendix C . Example 4.11 . In \ell^{2} -space, for any \varepsilon>0 , there exists a hypothesis class \mathcal{H} that satisfies the \varepsilon -UUS property and a metric \rho^{\prime} that is equivalent with the ordinary metric \rho such that \mathcal{H} is (\tau,\tau) -uniform generatable with respect to \rho for any \tau\in(0,\varepsilon) , but \mathcal{H} is not (\tau,\tau) -non-uniformly generatable with respect to \rho^{\prime} for any \tau\in(0,\varepsilon) . 5 Discussion We initiated a theoretical study of generation in metric spaces, extending prior frameworks that were restricted to countable domains. Our results show that introducing geometric structure leads to new scale-dependent and metric-dependent phenomena, while preserving several older characterizations in modified form. In particular, we identified doubling metric spaces as a broad regime in which generatability behaves in a stable and robust manner, and demonstrated that outside this regime, generatability can be highly sensitive to both the novelty parameters and the choice of metric. Although our framework is theoretical, it aligns naturally with how novelty is operationalized in several continuous-domain generative applications. For example, in protein structure generation, a generated structure is often classified as novel only if its maximum structural similarity to all training structures falls below a fixed threshold, corresponding to a distance-based exclusion relative to the training set ( 17 ) . More broadly, empirical studies of generative model generalization have observed that generated samples may lie closer to the training set than independently held-out test samples in a feature space, reflecting a separation between the scale at which training data are revealed and the scale at which novelty is required of generated outputs ( 10 ) . Our framework makes this distinction explicit by allowing separate novelty parameters for the adversary and the generator. Several directions remain open, including studying generation when outputs are considered equivalent under natural symmetries, identifying geometric conditions beyond doubling that ensure stable behavior, and strengthening our understanding of generation in the limit under additional structural assumptions. Appendix A Summary of Results for Countable Example Space Generation We recall the formal definitions of generation in countable example spaces and the main structural results established in prior work, which motivate and inform our development of generation in metric spaces. Through this section, \mathcal{X} is a countable example space and \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} is a binary hypothesis class. A.1 Definitions of Generation Definition A.1 (Uniformly Unbounded Support (UUS) [ 21 ] ) . A hypothesis class \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} satisfies the Uniformly Unbounded Support (UUS) property if |\operatorname{supp}(h)|=\infty for every h\in\mathcal{H} . Let \mathcal{X} be an countable example space and let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} be a hypothesis class satisfying the UUS property. Definition A.2 (Generatability in the Limit [ 21 ] ) . The hypothesis class \mathcal{H}\subseteq{\{0,1\}}^{\mathcal{X}} is generatable in the limit if there exists a generator \mathcal{G} such that for every h\in\mathcal{H} and every enumeration \{x_{1},x_{2},\dots\} of \operatorname{supp}(h) , there exists t^{\star}\in\mathbb{N} such that \mathcal{G}(x_{1:s})\in\operatorname{supp}(h)\setminus\{x_{1},\dots,x_{s}\}\quad for all s\geq t^{\star}. Definition A.3 (Uniform Generatability [ 21 ] ) . The hypothesis class \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} is uniformly generatable if there exists a generator \mathcal{G} and an integer d^{\star}\in\mathbb{N} such that for every h\in\mathcal{H} and every sequence \{x_{1},x_{2},\dots\}\subseteq\operatorname{supp}(h) , if there exists t\in\mathbb{N} such that |\{x_{1},\dots,x_{t}\}|=d^{\star} then \mathcal{G}(x_{1:s})\in\operatorname{supp}(h)\setminus\{x_{1},\dots,x_{s}\}\quad\text{for all }s\geq t. Definition A.4 (Non-uniform Generatability [ 21 ] ) . The hypothesis class \mathcal{H}\subseteq{\{0,1\}^{\mathcal{X}}} is non-uniformly generatable if there exists a generator \mathcal{G} such that for every h\in\mathcal{H} , there exists an integer d_{h}^{\star}\in\mathbb{N} such that for every sequence \{x_{1},x_{2},\dots\}\subseteq\operatorname{supp}(h) , if there exists t\in\mathbb{N} such that |\{x_{1},\dots,x_{t}\}|=d^{\star} , then \mathcal{G}(x_{1:s})\in\operatorname{supp}(h)\setminus\{x_{1},\dots,x_{s}\}\quad\text{for all }s\geq t. A.2 Closure Dimension and Characterizations Definition A.5 (Closure Dimension [ 21 ] ) . The closure dimension of a hypothesis class \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} , denoted \operatorname{C}(\mathcal{H}) , is the largest integer d\in\mathbb{N} such that there exist distinct points x_{1},\dots,x_{d}\in\mathcal{X} with \langle x_{1},\dots,x_{d}\rangle_{\mathcal{H}}\neq\bot\quad\text{and}\quad|\langle x_{1},\dots,x_{d}\rangle_{\mathcal{H}}|<\infty. If such d exists for arbitrarily large values, we write \operatorname{C}(\mathcal{H})=\infty . Theorem A.1 (Uniform Generatability Characterization [ 21 ] ) . A hypothesis class \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} is uniformly generatable if and only if \operatorname{C}(\mathcal{H})<\infty. Theorem A.2 (Non-uniform Generatability Characterization [ 21 ] ) . A hypothesis class \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} is non-uniformly generatable if and only if there exists a non-decreasing sequence of subclasses \mathcal{H}_{1}\subseteq\mathcal{H}_{2}\subseteq\cdots\quad\text{such that}\quad\mathcal{H}=\bigcup_{i=1}^{\infty}\mathcal{H}_{i} and \operatorname{C}(\mathcal{H}_{i})<\infty\quad\text{for all }i\in\mathbb{N}. Theorem A.3 (Sufficient Condition for Generatability in the Limit [ 21 ] ) . A hypothesis class \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} is generatable in the limit if there exists a finite sequence of subclasses \mathcal{H}_{1},\dots,\mathcal{H}_{n}\subseteq\mathcal{H}\text{ such that }\mathcal{H}=\bigcup_{i=1}^{n}\mathcal{H}_{i} and \operatorname{C}(\mathcal{H}_{i})<\infty\text{ for all }i\in[n]. Appendix B Proofs in Section 3 To simplify the proof, we give a definition of generatable sequence, which is a sequence that belongs to some hypothesis class h . Definition B.1 (Generatable Sequence) . Let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} be a hypothesis class satisfying the r - \operatorname{UUS} property for some r>0 . A (finite or infinite) sequence \{x_{i}\}_{i\in I}\subseteq\mathcal{X} is called generatable if there exists h\in\mathcal{H} such that \{x_{i}\}_{i\in I}\subseteq\operatorname{supp}(h), where I=\{1,\dots,t\} for some t\in\mathbb{N} or I=\mathbb{N} . B.1 Proofs for Uniform Generation Lemma B.1 (Necessity in Theorem 3.1 ) . Let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} be any hypothesis class satisfying the r - \operatorname{UUS} property for some r>0 and and let 0<\varepsilon,\varepsilon^{\prime}\leq r . If \operatorname{C}_{\varepsilon}^{\varepsilon^{\prime}}(\mathcal{H})=\infty , then \mathcal{H} is not (\varepsilon,\varepsilon^{\prime}) -uniformly generatable. Proof. Let \mathcal{G} be any generator and suppose \operatorname{C}_{\varepsilon}^{\varepsilon^{\prime}}(\mathcal{H})=\infty . We show that for every d\in\mathbb{N} , there exists a h^{\star}\in\mathcal{H} and a sequence (x_{i})_{i\in\mathbb{N}} with \{x_{1},x_{2},\dots\}\subseteq\operatorname{supp}(h^{\star}) such that there exists t\geq d with N(\varepsilon;\{x_{i}\}_{i=1}^{t},\rho)=d and for any s\geq t , \mathcal{G}(x_{1:s})\notin\operatorname{supp}(h^{\star})\setminus\bigcup_{i=1}^{s}B(x_{i},\varepsilon^{\prime}) . To that end, fix a d\in\mathbb{N} . Since \operatorname{C}_{\varepsilon}^{\varepsilon^{\prime}}(\mathcal{H})=\infty , we know that there exists some d^{\star}\geq d and a generatable sequence \{z_{1},\dots,z_{t^{\star}}\} with N(\varepsilon;\{z_{i}\}_{i=1}^{t^{\star}},\rho)=d^{\star} such that N(\varepsilon^{\prime};\langle z_{1},\dots,z_{t^{\star}}\rangle_{\mathcal{H}},\rho)~<~\infty. We know that there exists t such that N(\varepsilon;\{z_{i}\}_{i=1}^{t},\rho)=d . Since \mathcal{H}(z_{1:t^{\star}})\subseteq\mathcal{H}(z_{1:t}) , we also know that N(\varepsilon^{\prime};\langle z_{1},\dots,z_{t}\rangle_{\mathcal{H}},\rho)<\infty. Because N(\varepsilon^{\prime};\langle z_{1},\dots,z_{t}\rangle_{\mathcal{H}},\rho)<\infty , there exists z_{t+1},\dots,z_{p}\in\langle z_{1},\dots,z_{t}\rangle_{\mathcal{H}} such that \{z_{1},\dots,z_{p}\} is an \varepsilon^{\prime} -covering of \langle z_{1},\dots,z_{t}\rangle_{\mathcal{H}} . Note that for every x\in\mathcal{X}\setminus\langle z_{1},\dots,z_{t}\rangle_{\mathcal{H}} , there exists a h\in\mathcal{H}(\langle z_{1},\dots,z_{t}\rangle_{\mathcal{H}}) such that x\notin\operatorname{supp}(h) . Let \hat{x}_{p}=\mathcal{G}(z_{1},\dots,z_{p}) denote the prediction of \mathcal{G} when given as input z_{1},\dots,z_{p} . Without loss of generality suppose that \hat{x}_{p}\notin\langle z_{1},\dots,z_{t}\rangle_{\mathcal{H}} . Then, using the previous observation, there exists h^{\star}\in\mathcal{H}(\langle z_{1},\dots,z_{t}\rangle_{\mathcal{H}}) such that \hat{x}_{p}\notin\operatorname{supp}(h^{\star})\setminus\bigcup_{i=1}^{p}B(z_{i},\varepsilon^{\prime}) . Pick this h^{\star} and consider the stream x_{1},x_{2},\dots by adding z_{1},\dots,z_{p} first and then appending the stream x_{p+1},x_{p+2},\dots\subseteq\operatorname{supp}(h^{\star}) . By definition, \mathcal{G}(x_{1:p})=\mathcal{G}(z_{1:p})\notin\operatorname{supp}(h^{\star})\setminus\bigcup_{i=1}^{p}B(x_{i},\varepsilon^{\prime}). Since p\geq d and d\in\mathbb{N} was chosen arbitrarily, our proof is complete. ∎ Lemma B.2 (Sufficiency in Theorem 3.1 ) . Let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} be any hypothesis class satisfying the r - \operatorname{UUS} property for some r>0 and and let 0<\varepsilon,\varepsilon^{\prime}\leq r . When \operatorname{C}_{\varepsilon}^{\varepsilon^{\prime}}(\mathcal{H})<\infty , there exists a generator \mathcal{G} , such that for every h\in\mathcal{H} and any sequence (x_{i})_{i\in\mathbb{N}} with \{x_{1},x_{2},\dots\}\subseteq\operatorname{supp}(h) , if there exists t such that N(\varepsilon;\{x_{i}\}_{i=1}^{t},\rho)=\operatorname{C}_{\varepsilon}^{\varepsilon^{\prime}}(\mathcal{H})+1 , then \mathcal{G}(x_{1:s})\in\operatorname{supp}(h)\setminus\bigcup_{i=1}^{s}B(x_{i},\varepsilon^{\prime}) for all s\geq t . Proof. Let 0\leq d<\infty and suppose \operatorname{C}_{\varepsilon}^{\varepsilon^{\prime}}(\mathcal{H})=d . Then, for every generatable sequence \{x_{1},x_{2},\dots\} , we have that N(\varepsilon^{\prime};\langle x_{1},\dots,x_{t}\rangle_{\mathcal{H}},\rho)=\infty whenever N(\varepsilon;\{x_{i}\}_{i=1}^{t},\rho)\geq d+1 . Consider the following generator \mathcal{G} . If N(\varepsilon;\{x_{i}\}_{i=1}^{t},\rho)\leq d , \mathcal{G} plays any \hat{x}_{t} . But on round t with N(\varepsilon;\{x_{i}\}_{i=1}^{t},\rho)\geq d+1 , \mathcal{G} plays any \hat{x}_{t}\in\langle x_{1},\dots,x_{t}\rangle_{\mathcal{H}}\setminus\bigcup_{i=1}^{t}B(x_{i},\varepsilon^{\prime}) . Let h^{\star} be the hypothesis chosen by the adversary. It suffices to show that \hat{x}_{t}\in\operatorname{supp}(h^{\star})\setminus\bigcup_{i=1}^{t}B(x_{i},\varepsilon^{\prime}) for all t\geq d+1 . However, this just follows from the fact that N(\varepsilon^{\prime};\langle x_{1},\dots,x_{t}\rangle_{\mathcal{H}},\rho)=\infty and \langle x_{1},\dots,x_{t}\rangle_{\mathcal{H}}\subseteq\operatorname{supp}(h^{\star}) . In particular, N(\varepsilon^{\prime};\langle x_{1},\dots,x_{t}\rangle_{\mathcal{H}},\rho)=\infty ensures that \hat{x}_{t} is well-defined and \langle x_{1},\dots,x_{t}\rangle_{\mathcal{H}}\subseteq\operatorname{supp}(h^{\star}) ensures that it always lies in \operatorname{supp}(h^{\star})\setminus\bigcup_{i=1}^{t}B(x_{i},\varepsilon^{\prime}) . ∎ Composing Lemmas B.1 and B.2 gives a characterization of uniform generatability. Next we prove Corollary 3.2 . of Corollary 3.2 . We only need to show that \operatorname{C}_{\varepsilon}^{\varepsilon^{\prime}}(\mathcal{H})<\infty . To do this, suppose \mathcal{H}=\{h_{1},\dots,h_{s}\} . For any A\subset[s] such that A\neq\emptyset , define N_{A,\varepsilon}=N(\varepsilon;\bigcap_{i\in A}\operatorname{supp}(h_{i}),\rho),\quad N_{A,\varepsilon^{\prime}}=N(\varepsilon^{\prime};\bigcap_{i\in A}\operatorname{supp}(h_{i}),\rho). Note that, from our assumption, we always have N_{A,\varepsilon}\leq N_{A,\varepsilon^{\prime}} . We claim that \operatorname{C}_{\varepsilon}^{\varepsilon^{\prime}}(\mathcal{H})=\max\{N_{A,\varepsilon}|A\subset[s],A\neq\emptyset,N_{A,\varepsilon^{\prime}}<\infty\}. To show this, let A^{\star}\in\argmax_{A}\{N_{A,\varepsilon}|A\subset[s],A\neq\emptyset,N_{A,\varepsilon^{\prime}}<\infty\}, and let \{x_{1},\dots,x_{d}\} be a \varepsilon -covering of \bigcap_{i\in A^{\star}}\operatorname{supp}(h_{i}) where d=N_{A^{\star},\varepsilon} . Then, we know that \{x_{1},\dots,x_{d}\} is a generatable sequence such that N(\varepsilon^{\prime};\langle x_{1},\dots,x_{d}\rangle_{\mathcal{H}},\rho)\leq N(\varepsilon^{\prime};\bigcap_{i\in A^{\star}}\operatorname{supp}(h_{i}),\rho)<\infty. So \operatorname{C}_{\varepsilon}^{\varepsilon^{\prime}}(\mathcal{H})\geq N_{A^{\star},\varepsilon} . On the other hand, for any generatable sequence z_{1},\dots,z_{p} such that N(\varepsilon;\{z_{i}\}_{i=1}^{p},\rho)>N_{A^{\star},\varepsilon}, there exists A^{\prime}\subset[s] such that \langle z_{1},\dots,z_{p}\rangle_{\mathcal{H}}=\bigcap_{i\in A^{\prime}}\operatorname{supp}(h_{i}) . By the definition of N_{A^{\star},\varepsilon} , we know that N(\varepsilon^{\prime};\bigcap_{i\in A^{\prime}}\operatorname{supp}(h_{i}),\rho)=\infty . Thus \operatorname{C}_{\varepsilon}^{\varepsilon^{\prime}}(\mathcal{H})\leq N_{A^{\star},\varepsilon} , the proof is completed. ∎ We also provide an example of a hypothesis class \mathcal{H} consisting of only two hypothesis that is not non-uniformly generatable in \ell^{2} . Example B.3 . In \ell^{2} space, for any \varepsilon^{\prime},\varepsilon>0 and any 0<\varepsilon,\varepsilon^{\prime}\leq r with \varepsilon<\varepsilon^{\prime} , there exists a hypothesis \mathcal{H}\subseteq\{0,1\}^{\ell^{2}} satisfying the r - \operatorname{UUS} property and is not (\varepsilon,\varepsilon^{\prime}) -non-uniformly generatable. Proof. Recall that \ell^{2} is the space that contains all sequences (x_{i})_{i=1}^{\infty} such that \sum_{i}x_{i}^{2}<\infty . Let e_{k}\in\ell^{2} denote the k -th standard basis vector. Define a_{k}:=\frac{\sqrt{2}}{2}\varepsilon^{\prime}\cdot e_{k},\quad g_{k}:=\frac{\sqrt{2}}{2}r\cdot e_{k}. Construct the hypothesis set h_{1} and h_{2} such that \operatorname{supp}(h_{1})=\{a_{k}|k\in\mathbb{N}\}\cup\{g_{2k}|k\in\mathbb{N}\},\quad\operatorname{supp}(h_{2})=\{a_{k}|k\in\mathbb{N}\}\cup\{g_{2k+1}|k\in\mathbb{N}\}. Let \mathcal{H}=\{h_{1},h_{2}\} . Then, for any t, we have N(\varepsilon;\{a_{i}\}_{i=1}^{t},\rho)=t\quad\text{and}\quad N(\varepsilon^{\prime};\langle a_{1},\dots,a_{t}\rangle_{\mathcal{H}},\rho)=1. As a result, \operatorname{C}^{\varepsilon^{\prime}}_{\varepsilon}(\mathcal{H})=\infty , thus \mathcal{H} is not uniformly generatable. The fact that it is not non-uniformly generatable is a direct corollary from Theorem 3.3 . ∎ B.2 Proofs for Non-Uniform Generation We now prove Theorem 3.3 across two lemmas, starting with the necessity direction. Lemma B.4 (Necessity in Theorem 3.3 ) . Let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} be any hypothesis class satisfying the r - \operatorname{UUS} property for some r>0 and and let 0<\varepsilon,\varepsilon^{\prime}\leq r . If \mathcal{H} is (\varepsilon,\varepsilon^{\prime}) -non-uniformly generatable, then there exists a sequence of non-decreasing, (\varepsilon,\varepsilon^{\prime}) -uniformly generatable classes \mathcal{H}_{1}\subseteq\mathcal{H}_{2}\subseteq\cdots such that \mathcal{H}=\bigcup_{n\in\mathbb{N}}\mathcal{H}_{n} . Proof. Suppose \mathcal{H} is (\varepsilon,\varepsilon^{\prime}) -non-uniformly generatable and \mathcal{G} is a (\varepsilon,\varepsilon^{\prime}) -non-uniform generator for \mathcal{H} . For every h\in\mathcal{H} , let d_{h}\in\mathbb{N} be the smallest natural number such that for any sequence \{x_{i}\}_{i=1}^{\infty}\subset\operatorname{supp}(h) , if there exists t such that N(\varepsilon;\{x_{i}\}_{i=1}^{t},\rho)\geq d_{h} , then \mathcal{G}(x_{1:s})\in\operatorname{supp}(h)\setminus\bigcup_{i=1}^{s}B(x_{i},\varepsilon^{\prime}) for all s\geq t . Let \mathcal{H}_{n}:=\{h\in\mathcal{H}:d_{h}\leq n\} for all n\in\mathbb{N} . Then, by the definition of \mathcal{G} , we know for every n\in\mathbb{N} , \mathcal{G} is a (\varepsilon,\varepsilon^{\prime}) -uniform generator for \mathcal{H}_{n} , and therefore \mathcal{H}_{n} is \varepsilon -uniformly generatable. The proof is complete after noting that \mathcal{H}_{1}\subseteq\mathcal{H}_{2}\subseteq\cdots and \mathcal{H}=\bigcup_{n\in\mathbb{N}}\mathcal{H}_{n} . ∎ Lemma B.5 (Sufficiency in Theorem 3.3 ) . Let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} be any hypothesis class satisfying the r - \operatorname{UUS} property for some r>0 and and let 0<\varepsilon,\varepsilon^{\prime}\leq r . If there exists a sequence of non-decreasing, (\varepsilon,\varepsilon^{\prime}) -uniformly generatable classes \mathcal{H}_{1}\subseteq\mathcal{H}_{2}\subseteq\dots such that \mathcal{H}=\bigcup_{n\in\mathbb{N}}\mathcal{H}_{n} , then \mathcal{H} is (\varepsilon,\varepsilon^{\prime}) -non-uniformly generatable. Proof. Suppose \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} is a class satisfying the r - \operatorname{UUS} property for which there exists a sequence of non-decreasing, (\varepsilon,\varepsilon^{\prime}) -uniformly generatable classes \mathcal{H}_{1}\subseteq\mathcal{H}_{2}\subseteq\dots with \mathcal{H}=\bigcup_{n=1}^{\infty}\mathcal{H}_{n} . By definition of uniform generatability, for every n\in\mathbb{N} , there exists a uniform generator \mathcal{G}_{n} for \mathcal{H}_{n} . Let d_{\mathcal{G}_{n}} denote the (\varepsilon,\varepsilon^{\prime}) -uniform generation sample complexity of \mathcal{G}_{n} with respect to \mathcal{H}_{n} . Consider the following generator \mathcal{G} . Fix t\in\mathbb{N} and consider any sequence \{x_{1},\dots,x_{t}\} such that |\mathcal{H}(x_{1},\dots,x_{t})|\geq 1 . Let d_{t}:=N(\varepsilon;\{x_{i}\}_{i=1}^{t},\rho) . \mathcal{G} first computes n_{t}=\max\{n\in[t]:d_{\mathcal{G}_{n}}\leq d_{t}\}\cup\{0\}. If n_{t}=0 , \mathcal{G} plays any \hat{x}_{t}\in\mathcal{X} . If n_{t}>0 , \mathcal{G} uses \mathcal{G}_{n_{t}} to generate new instances, which means \mathcal{G}(x_{1},\dots,x_{t})=\mathcal{G}_{n_{t}}(x_{1},\dots,x_{t}). We now prove that such a \mathcal{G} is a (\varepsilon,\varepsilon^{\prime}) -non-uniform generator for \mathcal{H} . To that end, let h^{\star} be the hypothesis chosen by the adversary and suppose that h^{\star} belongs to \mathcal{H}_{n^{\star}} . Let d^{\star}=\max\{d_{\mathcal{G}_{n^{\star}}},n^{\star}\}. We show that for any sequence \{x_{i}\}_{i=1}^{\infty}\subseteq\operatorname{supp}(h^{\star}) , if there exists t^{\star}\in\mathbb{N} such that N(\varepsilon;\{x_{i}\}_{i=1}^{t^{\star}},\rho)=d^{\star} , then \mathcal{G}(x_{1:s})\in\operatorname{supp}(h)\setminus\bigcup_{i=1}^{s}B(x_{i},\varepsilon^{\prime}) for all s\geq t^{\star} . Fix any valid sequence \{x_{i}\}_{i=1}^{\infty}\subseteq\operatorname{supp}(h^{\star}) , and suppose, without loss of generality, that N(\varepsilon;\{x_{i}\}_{i=1}^{t^{\star}},\rho)=d^{\star} for some t^{\star}\in\mathbb{N}. Fix any s\geq t^{\star}. By definition, \mathcal{G} first computes n_{s}=~\max\{n\in[s]:d_{\mathcal{G}_{n}}\leq d_{s}\}\cup\{0\}. Note that n_{s}\geq n^{\star} since s\geq n^{\star} and d_{\mathcal{G}_{n^{\star}}}\leq d_{s} . Thus, |\mathcal{H}_{n_{s}}(x_{1:s})|\geq 1 since h^{\star}\in\mathcal{H}_{n^{\star}} . Accordingly, by construction of \mathcal{G} , it uses \mathcal{G}_{n_{s}} to generate a new instance. The proof is complete by noting that h^{\star}\in\mathcal{H}_{n_{s}} and d_{s}\geq d_{\mathcal{G}_{n_{s}}} which guarantees that \mathcal{G}_{n_{s}}(x_{1},\dots,x_{s})\in\operatorname{supp}(h^{\star})\setminus\bigcup_{i=1}^{s}B(x_{i},\varepsilon^{\prime}) . ∎ We now show that every countable hypothesis class are non-uniformly generatable with \varepsilon\geq\varepsilon^{\prime} . Proof. (of Corollary 3.4 ) Suppose \mathcal{H} is a countable hypothesis class satisfying the r -UUS property. Consider an arbitrary enumeration h_{1},h_{2},\dots of \mathcal{H} . Let \mathcal{H}_{n}=\{h_{1},\dots,h_{n}\} for all n\in\mathbb{N} . Then, \mathcal{H}_{1},\mathcal{H}_{2},\dots is a non-decreasing sequence of classes such that \mathcal{H}=\bigcup_{n\in\mathbb{N}}\mathcal{H}_{n}. Moreover, since for every n\in\mathbb{N} , we have that |\mathcal{H}_{n}|=n<\infty , Corollary 3.2 gives that \mathcal{H}_{n} is (\varepsilon,\varepsilon^{\prime}) -uniformly generatable, completing the proof. ∎ B.3 Proofs for Generation in the Limit Proof of Theorem 3.5 . Let \mathcal{H}=\bigcup_{i=1}^{n}\mathcal{H}_{i} be such that \operatorname{C}_{\varepsilon}^{\varepsilon^{\prime}}(\mathcal{H}_{i})<\infty for all i\in[n]. Let c:=\max_{i\in[n]}\operatorname{C}(\mathcal{H}_{i}). Consider the following generator \mathcal{G} . Let t^{\star}\in\mathbb{N} be the smallest time point for which N(\varepsilon;\{x_{i}\}_{i=1}^{t*},\rho)=c+1. \mathcal{G} plays arbitrarily up to, but not including, time point t^{\star} . On time point t^{\star} , \mathcal{G} computes \langle x_{1},\dots,x_{t^{\star}}\rangle_{\mathcal{H}_{i}} for all i\in[n] . Let S\subseteq[n] be the subset of indices such that i\in S if and only if \langle x_{1},\dots,x_{t^{\star}}\rangle_{\mathcal{H}_{i}}\neq\bot. For every i\in S , let (z^{(i)}_{j})_{j\in\mathbb{N}} be the natural ordering of some dense subset of \langle x_{1},\dots,x_{t^{\star}}\rangle_{\mathcal{H}_{i}} , which is guaranteed to exist since \mathcal{X} is separable. For every t\geq t^{\star} , sequence of revealed examples x_{1},\dots,x_{t} , and i\in S , \mathcal{G} computes n_{t}^{i}:=\max\{n\in\mathbb{N}:\{z^{(i)}_{1},\dots,z^{(i)}_{n}\}\subset B(\{x_{i}\}_{i=1}^{t},\varepsilon)\cap\langle x_{1},\dots,x_{t^{\star}}\rangle_{\mathcal{H}_{i}}\} and i_{t}\in\argmax_{i\in S}n_{t}^{i}. Finally, \mathcal{G} plays any \hat{x}_{t}\in\{z_{j}^{(i_{t})}\}_{j=1}^{\infty}\setminus B(\{x_{i}\}_{i=1}^{t},\varepsilon^{\prime}) . We claim that \mathcal{G} generates from \mathcal{H} in the limit. Let h^{\star}\in\mathcal{H} be the hypothesis chosen by the adversary and \{x_{i}\}_{i=1}^{\infty}\subseteq\operatorname{supp}(h^{\star}) be such that \operatorname{supp}(h^{\star})\subseteq B(\{x_{i}\}_{i=1}^{\infty},\varepsilon) . Let c=\max_{i\in[n]}\operatorname{C}(\mathcal{H}_{i}) and t^{\star}\in\mathbb{N} be the smallest time point for which N(\varepsilon;\{x_{i}\}_{i=1}^{t*},\rho)=c+1. By definition of \operatorname{C}_{\varepsilon}^{\varepsilon^{\prime}}(\cdot) , we know that for every i\in S , N(\varepsilon^{\prime};\langle x_{1},\dots,x_{t^{\star}}\rangle_{\mathcal{H}_{i}},\rho)=\infty, so N(\varepsilon^{\prime};\{z_{j}^{(i)}\}_{j=1}^{\infty},\rho)=\infty, Let S^{\star}\subseteq S be such that i\in S^{\star} if and only if \{z_{j}^{(i)}\}_{j=1}^{\infty}\subseteq\operatorname{supp}(h^{\star}). It suffices to show that there exists a finite time point s^{\star}\in\mathbb{N} such that for all t\geq s^{\star} , we have that i_{t}\in S^{\star}. To see why such an s^{\star} must exist, pick some j^{\star}\in S^{\star}. Note that n_{t}^{j^{\star}}\rightarrow\infty because \operatorname{supp}(h)\subseteq B(\{x_{i}\}_{i=1}^{\infty},\varepsilon) . On the other hand, observe that for every j\notin S^{\star} , there exists a n^{j}\in\mathbb{N} such that n_{t}^{j}\leq n^{j} for any t\in\mathbb{N} . This is because, if j\notin S^{\star} , then there must be an index n^{j}\in\mathbb{N} such that z^{(j)}_{n^{j}}\notin\operatorname{supp}(h^{\star}). Thus, n_{t}^{j} must be at most n^{j} . Since there are at most a finite number of indices not in S^{\star} , we have that \max_{j\notin S^{\star}}n^{j}<\infty , which means that eventually, n_{t}^{j^{\star}}>n_{t}^{j} for all j\notin S^{\star} , and thus there exists a s^{\star}\in\mathbb{N} such that i_{t}\in S^{\star} for all t\geq s^{\star}. This completes the proof. ∎ Remark B.1 . The inference N\!\left(\varepsilon^{\prime};\ \langle x_{1},\dots,x_{t^{\star}}\rangle_{\mathcal{H}_{i}},\rho\right)=\infty\quad\Longrightarrow\quad N\!\left(\varepsilon^{\prime};\ \{z_{j}^{(i)}\}_{j=1}^{\infty},\rho\right)=\infty is valid under our convention that covering numbers are defined using closed \varepsilon^{\prime} -balls. Indeed, by construction, \{z_{j}^{(i)}\}_{j\geq 1} is dense in \langle x_{1},\dots,x_{t^{\star}}\rangle_{\mathcal{H}_{i}} , and any finite cover of the dense set by closed balls would automatically cover the whole set. If instead one defines covering numbers using open balls, the above implication may fail because an open-ball cover of a dense subset need not cover boundary points. In that case, one can modify (z_{j}^{(i)}) to be a natural enumeration of D\ \cup\ D_{\partial}, where D is a dense subset of \langle x_{1},\dots,x_{t^{\star}}\rangle_{\mathcal{H}_{i}} and D_{\partial} is a dense subset of its boundary. The proof of Theorem 3.6 is an direct extension of Theorem 3.2 in 8 . To begin, we state a lemma that connects a hypothesis class in \mathbb{Z} to any metric space \mathcal{X} . Lemma B.6 (Embedding \{0,1\}^{\mathbb{Z}} into \{0,1\}^{\mathcal{X}} ) . Let (\mathcal{X},\rho) be a metric space and let r>0 . Assume that the covering number N(r;\mathcal{X},\rho)=\infty . Let 0<\varepsilon,\varepsilon^{\prime}\leq r/2 . Then there exists an injective map (embedding) \iota:\{0,1\}^{\mathbb{Z}}\to\{0,1\}^{\mathcal{X}} such that for every \mathcal{H}\subseteq\{0,1\}^{\mathbb{Z}} , \mathcal{H} is uniformly generatable (resp., non-uniformly generatable, generatable in the limit) in the sense of Definitions A.3 , A.4 , A.2 if and only if \iota(\mathcal{H}):=\{\iota(h):h\in\mathcal{H}\} is (\varepsilon,\varepsilon^{\prime}) -uniformly generatable (resp., non-uniformly generatable, generatable in the limit). Proof. Since N(r;\mathcal{X},\rho)=\infty , there exists an infinite r -packing in \mathcal{X} . In particular, we may choose a countably infinite subset and relabel it as \{x_{j}\}_{j\in\mathbb{Z}}\subseteq\mathcal{X} such that \rho(x_{i},x_{j})>r\qquad\text{for all }i\neq j. Define \iota:\{0,1\}^{\mathbb{Z}}\to\{0,1\}^{\mathcal{X}} by \iota(h)(x_{j})=h(j)\quad\forall j\in\mathbb{Z},\qquad\iota(h)(x)=0\quad\forall x\notin\{x_{j}\}_{j\in\mathbb{Z}}. Then \iota is injective and satisfies \operatorname{supp}(\iota(h))=\{x_{j}:j\in\operatorname{supp}(h)\}. We claim that for any x\in\mathcal{X} , \bigl|B(x,\varepsilon)\cap\{x_{j}\}_{j\in\mathbb{Z}}\bigr|\leq 1\quad\text{and}\quad\bigl|B(x,\varepsilon^{\prime})\cap\{x_{j}\}_{j\in\mathbb{Z}}\bigr|\leq 1. Indeed, if x_{i},x_{j}\in B(x,\varepsilon) with i\neq j , then by the triangle inequality, \rho(x_{i},x_{j})\leq\rho(x_{i},x)+\rho(x,x_{j})\leq 2\varepsilon\leq r, contradicting \rho(x_{i},x_{j})>r . The argument for \varepsilon^{\prime} is identical. The above claim implies that, restricted to hypotheses supported on \{x_{j}\} , membership in an \varepsilon -ball (resp. \varepsilon^{\prime} -ball) identifies at most one index j\in\mathbb{Z} . Consequently, under the identification j\leftrightarrow x_{j} , the (\varepsilon,\varepsilon^{\prime}) -novelty constraints in (\mathcal{X},\rho) coincide with the distinctness-based novelty constraints in the countable space \mathbb{Z} used in Definitions A.3 , A.4 , A.2 . Formally, any adversary strategy on \mathbb{Z} can be simulated on \mathcal{X} by replacing each integer j it plays with the point x_{j} ; likewise, any generator strategy on \mathbb{Z} can be simulated on \mathcal{X} by outputting x_{j} whenever it would output j . Conversely, any play in \mathcal{X} against \iota(\mathcal{H}) can be projected back to \mathbb{Z} by mapping each encountered point in \{x_{j}\} to its unique index. (Without loss of generality, we assume the generator’s outputs lie in \{x_{j}\}_{j\in\mathbb{Z}} , since outputs outside \{x_{j}\}_{j\in\mathbb{Z}} cannot certify membership in any \operatorname{supp}(\iota(h)) .) Therefore, there exists a winning (uniform / non-uniform / limit) strategy for \mathcal{H} in the countable game if and only if there exists a winning (\varepsilon,\varepsilon^{\prime}) -strategy for \iota(\mathcal{H}) in the metric game. This proves the stated equivalences. ∎ Proof of Theorem 3.6 . Lemma B.6 provides an embedding \iota that preserves (non-)uniform generatability and generatability in the limit between the countable setting on \mathbb{Z} and the metric setting on (\mathcal{X},\rho) . Applying this embedding to the collections constructed in Theorem 3.2 of 8 transfers their properties to the metric space. In particular, the images of the collections \mathcal{L}_{1} and \mathcal{L}_{2} retain their respective (non-)uniform generatability properties. The failure of generatability for their union is also preserved under the embedding. This establishes the claimed separation in the metric setting. ∎ Appendix C Constructing Examples in Section 4 C.1 Useful Lemmas for Constructing Hypothesis Classes This section collects several useful lemmas for constructing hypothesis classes. Lemma C.1 provides a tool for constructing classes that are not non-uniformly generatable. Lemmas C.2 and C.3 are used to construct classes that fail to be generatable in the limit. These lemmas will play a central role in the proofs of the examples in Section 4 . Lemma C.1 . Let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} be a hypothesis class satisfying the r - \operatorname{UUS} property for some r>0 , and let 0<\varepsilon,\varepsilon^{\prime}\leq r . Suppose that: 1. There exist hypothesis classes \mathcal{H}_{1} and \mathcal{H}_{2} such that \mathcal{H}_{1} satisfies the \varepsilon -UUS property and \mathcal{H}=\mathcal{H}_{1}+\mathcal{H}_{2}:=\left\{h\;\middle|\;\operatorname{supp}(h)=\operatorname{supp}(h_{1})\cup\operatorname{supp}(h_{2}),\;h_{1}\in\mathcal{H}_{1},\;h_{2}\in\mathcal{H}_{2}\right\}. 2. Either \mathcal{H}_{1} does not satisfy the \varepsilon^{\prime} -UUS property, or \mathcal{H}_{1} is not (\varepsilon,\varepsilon^{\prime}) -generatable in the limit. 3. There exist n\in\mathbb{\mathbb{N}} and hypotheses h_{21},\dots,h_{2n}\in\mathcal{H}_{2} such that \bigcap_{i=1}^{n}\operatorname{supp}(h_{2i})=\emptyset. Then \mathcal{H} is not (\varepsilon,\varepsilon^{\prime}) -non-uniformly generatable in the limit. Proof. Suppose, toward a contradiction, that \mathcal{H} is (\varepsilon,\varepsilon^{\prime}) -non-uniformly generatable in the limit, and let \mathcal{G} be a corresponding non-uniform generator. For each h\in\mathcal{H} , let d_{h}\in\mathbb{N} be the smallest integer such that for any sequence \{x_{i}\}_{i=1}^{\infty}\subset\operatorname{supp}(h) , whenever there exists t with N(\varepsilon;\{x_{i}\}_{i=1}^{t},\rho)\geq d_{h} , we have \mathcal{G}(x_{1:s})\in\operatorname{supp}(h)\setminus\bigcup_{i=1}^{s}B(x_{i},\varepsilon^{\prime})\quad\text{for all }s\geq t. We show that \mathcal{G} induces an (\varepsilon,\varepsilon^{\prime}) -generator for \mathcal{H}_{1} , leading to a contradiction. Fix any h_{1}\in\mathcal{H}_{1} and choose a sequence \{x_{j}\}_{j=1}^{\infty}\subset\operatorname{supp}(h_{1}) such that \operatorname{supp}(h_{1})\subset\bigcup_{j=1}^{\infty}B(x_{j},\varepsilon). For each i\in[n] , define h^{\prime}_{2i}\in\mathcal{H} by \operatorname{supp}(h^{\prime}_{2i})=\operatorname{supp}(h_{1})\cup\operatorname{supp}(h_{2i}). Let d:=\max_{i\in[n]}d_{h^{\prime}_{2i}}+1. Then, after observing t samples such that N(\varepsilon;\{x_{i}\}_{i=1}^{t},\rho)\geq d , the definition of \mathcal{G} implies \mathcal{G}(x_{1:t})\in\bigcap_{i=1}^{n}\operatorname{supp}(h^{\prime}_{2i})\setminus\bigcup_{i=1}^{t}B(x_{i},\varepsilon^{\prime}). Since \bigcap_{i=1}^{n}\operatorname{supp}(h^{\prime}_{2i})=\operatorname{supp}(h_{1}), it follows that for all s\geq t , \mathcal{G}(x_{1:s})\in\operatorname{supp}(h_{1})\setminus\bigcup_{i=1}^{s}B(x_{i},\varepsilon^{\prime}). If \mathcal{H}_{1} satisfies the \varepsilon^{\prime} -UUS property, this shows that \mathcal{H}_{1} is (\varepsilon,\varepsilon^{\prime}) -generatable in the limit with generator \mathcal{G} , contradicting assumption (2). Otherwise, \mathcal{H}_{1} does not satisfy the \varepsilon^{\prime} -UUS property. Then there exists h_{10}\in\mathcal{H}_{1} such that N(\varepsilon^{\prime};\operatorname{supp}(h_{10}),\rho)<\infty. Repeating the argument above with h_{10} in place of h_{1} . Let \{\theta_{1},\dots,\theta_{M}\}\subseteq\operatorname{supp}(h_{10}) be an \varepsilon^{\prime} -cover of \operatorname{supp}(h_{10}) . Consider the adversary sequence that begins with x_{i}=\theta_{i} for i\leq M . From our assumption, we obtain a time t such that for all s\geq t , \mathcal{G}(x_{1:s})\in\operatorname{supp}(h_{10})\setminus\bigcup_{i=1}^{s}B(x_{i},\varepsilon^{\prime}). However, since \operatorname{supp}(h_{10})\subseteq\bigcup_{i=1}^{M}B(x_{i},\varepsilon^{\prime}), this contradicting the definition of \mathcal{G} . In both cases we obtain a contradiction, completing the proof. ∎ The lemma below is an extension of Proposition A.1 from 8 . Lemma C.2 . Let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} be any hypothesis class satisfying the r - \operatorname{UUS} property for some r>0 , and let 0<\varepsilon,\varepsilon^{\prime}i_{k}>m for all k>m , there exists a hypothesis h\in\mathcal{H} such that \{x_{i_{k}}\}_{k=1}^{\infty}\subseteq\operatorname{supp}(h)\subseteq B\left(\{x_{i_{k}}\}_{k=1}^{\infty},\,\min\{\varepsilon,\varepsilon^{\prime}\}\right), then \mathcal{H} is not (\varepsilon,\varepsilon^{\prime}) -generatable in the limit. Intuitively, the lemma says that if the hypothesis class \mathcal{H} is rich enough such that an adversary can fix a finite prefix after which any continuation is consistent with uncountably many h , then the generator can be permanently trapped and forced to fail. Proof. Let \mathcal{G} be a generator. We show that there exists a hypothesis h\in\mathcal{H} and a subsequence \{x_{i_{k}}\}_{k=1}^{\infty} of \{x_{i}\}_{i=1}^{\infty} , both depending on \mathcal{G} , such that \operatorname{supp}(h)\subseteq\bigcup_{k=1}^{\infty}B(x_{i_{k}},\varepsilon), and \mathcal{G} fails to generate h in the limit. We construct the subsequence inductively. Let i_{1}=1,i_{2}=2,\dots,i_{m}=m . Define i_{m+1}=\min\left\{k>i_{m}\mid x_{k}\notin B\left(\{x_{i_{1}},\dots,x_{i_{m}},\mathcal{G}(x_{i_{1}}),\dots,\mathcal{G}(x_{i_{1}},\dots,x_{i_{m}})\},\varepsilon^{\prime}\right)\right\}. Assuming i_{1},\dots,i_{n-1} have been defined where n>m , we set i_{n}=\min\left\{k>i_{n-1}\mid x_{k}\notin B\left(\{x_{i_{1}},\dots,x_{i_{n-1}},\mathcal{G}(x_{i_{1}}),\dots,\mathcal{G}(x_{i_{1}},\dots,x_{i_{n-1}})\},\varepsilon^{\prime}\right)\right\}. By the assumption that \mathcal{H} satisfies the \varepsilon^{\prime} -UUS property, we have N(\varepsilon^{\prime},\{x_{i}\}_{i=1}^{\infty},\rho)=\infty , so this inductive process continues indefinitely. Thus, \{x_{i_{k}}\}_{k=1}^{\infty} is a well-defined subsequence of \{x_{i}\}_{i=1}^{\infty} . By assumption, there exists h\in\mathcal{H} such that \operatorname{supp}(h)\subseteq\bigcup_{k=1}^{\infty}B(x_{i_{k}},\varepsilon)\quad\text{ and}\quad\operatorname{supp}(h)\subseteq\bigcup_{k=1}^{\infty}B(x_{i_{k}},\varepsilon^{\prime}) Finally, we claim that for every n>m , the generator \mathcal{G} either outputs a point not in \operatorname{supp}(h) , or a point lying in B(\{x_{i_{k}}\}_{k=1}^{n},\varepsilon^{\prime}) . To establish this, it suffices to show that \mathcal{G}(x_{i_{1}},\dots,x_{i_{n}})\notin\bigcup_{k=n+1}^{\infty}B(x_{i_{k}},\varepsilon^{\prime}). This follows directly from the inductive construction: for any j\geq n+1 , we have x_{i_{j}}\notin B\left(\mathcal{G}(x_{i_{1}},\dots,x_{i_{n}}),\varepsilon^{\prime}\right). Hence, \mathcal{G} fails to generate h in the limit. ∎ Lemma C.3 . Let \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} satisfy the r -UUS property for some r>0 , and let 0<\varepsilon,\varepsilon^{\prime}0 and any finite sequence of positive integers \{j_{i}\}_{i=0}^{n-1} , let h\in\mathcal{H} be such that \operatorname{supp}(h)=A_{p_{n}}\cup\left(\bigcup_{i=0}^{n-1}\{x_{i\ell}\}_{\ell=1}^{j_{i}}\right) Then h satisfies \operatorname{supp}(h)\subseteq B\bigl(\{x_{ni}\}_{i=1}^{\infty},1\bigr)\cup B\Bigl(\bigcup_{i=0}^{n-1}\{x_{i\ell}\}_{\ell=1}^{j_{i}},1\Bigr). and \operatorname{supp}(h)=A_{p_{n}}\cup B\Bigl(\bigcup_{i=0}^{n-1}\{x_{i\ell}\}_{\ell=1}^{j_{i}},1/2\Bigr). 3. For any n\in\mathbb{N} , A_{p_{n}}\cap A_{p_{0}}=\emptyset . What’s more, for any n>0 , since B(\{x_{ij}\}_{i\geq n+1,j\geq 1},1/2\})=\{x_{ij}:i\geq n+1,j\geq 1\}, we have A_{p_{n}}\cap B(\{x_{ij}\}_{i\geq n+1,j\geq 1},1/2)=\emptyset. Thus all three conditions of Lemma C.3 holds, makes \mathcal{H} not (1,1/2) -generatable in the limit. C.3 Proof of Example 4.8 Proof. Recall that \ell^{2} is the space that contains all sequences (x_{i})_{i=1}^{\infty} such that \sum_{i}x_{i}^{2}<\infty . Let e_{k}\in\ell^{2} denote the k -th standard basis vector. Define u_{k}:=2r\cdot e_{k},\qquad a_{k}:=\varepsilon\cdot e_{k},\qquad g_{k}:=\varepsilon^{\prime}\cdot e_{k}. Let \mathcal{I} be the set of all infinite subsets of \mathbb{N} , i.e., \mathcal{I}=\{I|I\in 2^{\mathbb{N}},|I|=\infty\} . For I\in\mathcal{I} , let U_{I}=\{u_{k}|k\in I\},\quad O_{I}=\{a_{2k}|k\in I\}\cup\{g_{2k^{n}+1}|k\in I,n\in\mathbb{N}\},\quad D_{I}=\{g_{2k+1}|k\in I\} and construct the hypothesis class \mathcal{H} such that \mathcal{H}=\{h_{I_{1},I_{2},I_{3}}|I_{1},I_{2},I_{3}\in\mathcal{I},\quad\operatorname{supp}(h_{I_{1},I_{2},I_{3}})=\{\mathbf{0}\}\cup U_{I_{1}}\cup O_{I_{2}}\cup D_{I_{3}}\} Here, u_{k} and U_{I} are constructed to ensure that \mathcal{H} satisfies the r -UUS property. As will be seen in the proof, the points a_{k} are constructed for the adversary, while the points g_{k} are constructed for the generator. In fact, the g_{k} are the only instances with an explicit structure, which enables the generator to repeatedly produce them. The set O_{I} is the optimal set : once the adversary reveals some a_{k}\in O_{I} , the generator can generate g_{k} infinitely often. In contrast, D_{I} is the disturbing set : if the adversary continues to reveal g_{k}\in D_{I} , then the generator fails to generate in the limit. Case 1: \gamma\in(0,\varepsilon) and \gamma^{\prime}\in(0,\varepsilon^{\prime}) . Suppose h\in\mathcal{H} and \{x_{i}\}_{i=1}^{\infty}\subseteq\operatorname{supp}(h) such that \operatorname{supp}(h)\subseteq B(\{x_{i}\}_{i=1}^{\infty},\gamma) . Since \gamma<\varepsilon and the points \{a_{2k}\} are mutually \sqrt{2}\varepsilon -seperated, each a_{2k}\in\operatorname{supp}(h) must itself appear among the x_{i} ’s. Then, there exists t>0 such that x_{t}=a_{2K} for some K . Then, suppose s\geq t , so a_{K}\in\{x_{i}\}_{i=1}^{s} . By our construction, A_{K}:=\{g_{2K^{n}+1}\}_{n=1}^{\infty}\setminus B(\{x_{i}\}_{i=1}^{s},\gamma^{\prime})\neq\emptyset Thus, constructing the generator \mathcal{G} such that \mathcal{G}(x_{1:s})\in A_{K} will guarantee \mathcal{H} generatable in the limit. Now we use Lemma C.3 to prove that \mathcal{H} is not (\gamma,\gamma^{\prime}) -generatable in the limit if \gamma\geq\varepsilon or \gamma^{\prime}\geq\varepsilon^{\prime} . Case 2: \gamma\in[\varepsilon,r] and \gamma^{\prime}\in[0,\varepsilon^{\prime}) . Let \{p_{i}\}_{i\geq 1}=\{3,5,7,\dots\} be the sequence of odd prime numbers. Using Lemma C.3 , let k=1 , y_{1}=\mathbf{0} , for any i\geq 1,j\geq 1 let x_{ij}=\begin{cases}u_{p_{i}^{(j+1)/2}}&j\text{ is odd,}\\ g_{2\cdot p_{i}^{j/2}+1}&j\text{ is even.}\end{cases} Moreover, let x_{0j}=\begin{cases}u_{2^{(j+1)/2}}&j\text{ is odd,}\\ g_{2\cdot 2^{j/2}+1}&j\text{ is even.}\end{cases} We verify that the conditions of Lemma C.3 holds. 1. For any infinite sequence of positive integers \{j_{i}\}_{i=1}^{\infty} , from our construction of x_{ij} , we can find J_{1},J_{2}\in 2^{\mathbb{N}} such that \bigcup_{i=1}^{\infty}\{x_{i\ell}\}_{\ell=1}^{j_{i}}=\{u_{k}|k\in{J_{1}}\}\cup\{g_{2k+1}|k\in J_{2}\}. Then, if we let I_{2}=\{2^{n}|n\in\mathbb{N}\} , I_{1}=I_{2}\cup J_{1} , I_{3}=I_{2}\cup J_{2} , since \gamma\geq\varepsilon , B(\mathbf{0},\gamma) can cover all the points of the form a_{k} . Thus, h=h_{I_{1},I_{2},I_{3}} satisfies \operatorname{supp}(h)\subseteq B(\mathbf{0},\gamma)\cup B(\{x_{0i}\}_{i=1}^{\infty},\gamma)\cup B(\bigcup_{i=1}^{\infty}\{x_{i\ell}\}_{\ell=1}^{j_{i}},\gamma) Moreover, if A_{0}=\bigcup_{k\in\mathbb{N}}\bigl\{u_{2^{k}},a_{2\cdot 2^{k}},g_{2\cdot 2^{k}+1}\bigr\}, that is, A_{0} contains the “protected” part for the n=0 hypothesis (a whole copy of a u/a/g -pattern indexed by powers of 2). We then know \operatorname{supp}(h)\subseteq B(\mathbf{0},\gamma^{\prime})\cup A_{0}\cup B(\bigcup_{i=1}^{\infty}\{x_{i\ell}\}_{\ell=1}^{j_{i}},\gamma^{\prime}). Thus the first condition holds. 2. Similarly, for any n>0 and finite sequence of positive integers \{j_{i}\}_{i=0}^{n-1} , we can find the corresponding hypothesis h with A_{n} contains the “protected” part for the n th-hypothesis (a whole copy of a u/a/g -pattern indexed by powers of p_{n} ). A_{n}=\bigcup_{k\in\mathbb{N}}\bigl\{u_{p_{n}^{k}},a_{2\cdot p_{n}^{k}},g_{2\cdot p_{n}^{k}+1}\bigr\}. 3. By our construction, and our assumption \gamma^{\prime}<\varepsilon^{\prime} , this condition holds because \{A_{n}\}_{n\geq 0} are on different coordinates in \ell^{2} . With all the three condition of Lemma C.3 holds, we know that \mathcal{H} is not generatable in the limit when \gamma\geq\varepsilon and \gamma^{\prime}\leq\varepsilon^{\prime} . Case 3: \gamma^{\prime}\in[\varepsilon^{\prime},r] . Using Lemma C.3 , let k=1 , y_{1}=\mathbf{0} , for any i\geq 1,j\geq 1 let x_{ij}=\begin{cases}u_{p_{i}^{(j+2)/3}}&j\equiv 1\pmod{3},\\ a_{2*p_{i}^{(j+1)/3}}&j\equiv 2\pmod{3},\\ g_{2*p_{i}^{(j/3)}}&j\equiv 0\pmod{3},\end{cases} Moreover, let x_{0j}=\begin{cases}u_{2^{(j+2)/3}}&j\equiv 1\pmod{3},\\ a_{2*2^{(j+1)/3}}&j\equiv 2\pmod{3},\\ g_{2*2^{(j/3)}}&j\equiv 0\pmod{3},\end{cases} We again verify that the conditions of Lemma C.3 holds. 1. For any infinite sequence of positive integers \{j_{i}\}_{i=1}^{\infty} , we can find J_{1},J_{2},J_{3}\in 2^{\mathbb{N}} such that \bigcup_{i=1}^{\infty}\{x_{i\ell}\}_{\ell=1}^{j_{i}}=\{u_{k}|k\in{J_{1}}\}\cup\{a_{2k}|k\in J_{2}\}\cup\{g_{2k+1}|k\in J_{3}\}. Then, if we let I_{1}=\{2^{n}|n\in\mathbb{N}\}\cup J_{1} , I_{2}=\{2^{n}|n\in\mathbb{N}\}\cup J_{2} , I_{3}=\mathbb{N} , since the ball B(\mathbf{0},\gamma) covers all the points of the form g_{k} , we know that h=h_{I_{1},I_{2},I_{3}} satisfies \operatorname{supp}(h)\subseteq B(\mathbf{0},\gamma)\cup B(\{x_{0i}\}_{i=1}^{\infty},\gamma)\cup B(\bigcup_{i=1}^{\infty}\{x_{i\ell}\}_{\ell=1}^{j_{i}},\gamma) Moreover, if A_{0}=\Bigl(\bigcup_{k\in\mathbb{N}}\bigl\{u_{2^{k}},a_{2\cdot 2^{k}}\bigr\}\Bigr)\setminus B(\mathbf{0},\gamma^{\prime}), we have \operatorname{supp}(h)\subseteq B(\mathbf{0},\gamma^{\prime})\cup A_{0}\cup B(\bigcup_{i=1}^{\infty}\{x_{i\ell}\}_{\ell=1}^{j_{i}},\gamma^{\prime}). Thus the first condition holds. 2. Similarly, for any n>0 and finite sequence of positive integers \{j_{i}\}_{i=0}^{n-1} , we can find the corresponding hypothesis h with A_{n}=\Bigl(\bigcup_{k\in\mathbb{N}}\bigl\{u_{p_{n}^{k}},a_{2\cdot p_{n}^{k}}\bigr\}\Bigr)\setminus B(\mathbf{0},\gamma^{\prime}). 3. By our construction, if \varepsilon>\gamma^{\prime} , then for any i\neq j , \{a_{i},u_{i}\}\cap B(\{u_{j},a_{j},g_{j}\},\gamma^{\prime})=\emptyset. Thus this condition holds. If \varepsilon\leq\gamma^{\prime} , then A_{n}=\bigl\{u_{p_{n}^{k}}|k\in\mathbb{N}\bigr\},\text{ for all }n\geq 1,\quad A_{0}=\bigl\{u_{2^{k}}|k\in\mathbb{N}\bigr\}. Since for any i\neq j , \{u_{i}\}\cap B(\{u_{j},a_{j},g_{j}\},\gamma^{\prime})=\emptyset, this condition holds as well. With all the three condition of Lemma C.3 holds, we know that \mathcal{H} is not generatable in the limit when \varepsilon^{\prime}\leq\gamma^{\prime} . ∎ C.4 Proof of Example 4.9 Proof. Let e_{k}\in\ell^{2} denote the k -th standard basis vector. Define u_{k}:=2r\cdot e_{k},\qquad a_{k,1}:=\tfrac{\sqrt{2}}{2}\varepsilon_{1}\cdot e_{k},\qquad a_{k,2}:=\tfrac{\sqrt{2}}{2}\varepsilon_{2}\cdot e_{k},\qquad g_{k}:=\tfrac{\sqrt{2}}{2}\varepsilon^{\prime}\cdot e_{k}. Let \mathcal{I} be the set of all infinite subsets of \mathbb{N} , i.e., \mathcal{I}=\{I|I\in 2^{\mathbb{N}},|I|=\infty\} . Let \mathcal{I}_{\mathrm{fin}} be the set of all finite subsets of \mathbb{N} , i.e., \mathcal{I}_{\mathrm{fin}}=\{I|I\in 2^{\mathbb{N}},|I|<\infty\} . For I\in\mathcal{I} and J\in\mathcal{I}_{\mathrm{fin}} , let O_{I}=\{g_{k^{n}}|k\in I,n\in\mathbb{N}\}\cup\{u_{k}|k\in I\},\quad D_{I,J}=\{a_{k,1}|k\in I\}\cup\{a_{k,2}|k\in J\} and construct the hypothesis class \mathcal{H} such that \mathcal{H}=\{h_{I_{1},I_{2},J}|I_{1},I_{2}\in\mathcal{I},J\in\mathcal{I}_{\mathrm{fin}},\quad\operatorname{supp}(h_{I_{1},I_{2},J})=O_{I_{1}}\cup D_{I_{2},J}\}. Here, as in Example 4.8 , the points u_{k} are constructed to ensure that the hypothesis class satisfies the r -UUS property. The points a_{k,1} and a_{k,2} are constructed for the adversary, while the points g_{k} are constructed for the generator. The set O_{I} is the optimal set in the sense that once the adversary reveals any instance in this set, the generator is able to generate g_{k} infinitely many times. In contrast, D_{I,J} is the disturbing set : if the adversary continues to reveal instances a_{k,1} and a_{k,2} from this set, the generator fails to generate in the limit. Case 1: \gamma\in[\varepsilon_{2},r] and \gamma^{\prime}\in(0,\varepsilon^{\prime}) . Fix any h\in\mathcal{H} and let \{x_{i}\}_{i=1}^{\infty}\subseteq\operatorname{supp}(h) . Suppose there exists t such that N(\gamma;\{x_{i}\}_{i=1}^{t},\rho)\geq 2. Then there must exist an index i\leq t such that x_{i}=g_{K} or x_{i}=u_{K} for some K\in\mathbb{N} . For any s\geq t , define A_{s}:=\{g_{K^{n}}\}_{n=1}^{\infty}\setminus B(\{x_{i}\}_{i=1}^{s},\gamma^{\prime}). By construction, A_{s} is nonempty for all s\geq t . Therefore, defining a generator \mathcal{G} such that \mathcal{G}(x_{1:s})\in A_{s} for all s\geq t ensures that \mathcal{H} is uniformly generatable. Case 2: \gamma\in[\varepsilon_{1},\varepsilon_{2}) and \gamma^{\prime}\in(0,\varepsilon^{\prime}) . Let h_{I_{1},I_{2},J}\in\mathcal{H} and denote d_{h}:=|J| . Given any sequence \{x_{i}\}_{i=1}^{\infty}\subseteq\operatorname{supp}(h) , suppose there exists t such that N(\gamma;\{x_{i}\}_{i=1}^{t},\rho)\geq d_{h}+2. Then, as before, there exists some i\leq t such that x_{i}=g_{K} or x_{i}=u_{K} for some K\in\mathbb{N} . For all s\geq t , the set A_{s}:=\{g_{K^{n}}\}_{n=1}^{\infty}\setminus B(\{x_{i}\}_{i=1}^{s},\gamma^{\prime}) is nonempty. Therefore, defining a generator \mathcal{G} such that \mathcal{G}(x_{1:s})\in A_{s} for all s\geq t ensures that \mathcal{H} is non-uniformly generatable. To show that \mathcal{H} is not (\gamma,\gamma^{\prime}) -uniformly generatable, it suffices to prove that C_{\gamma}^{\gamma^{\prime}}(\mathcal{H})=\infty . For any d\in\mathbb{N} , consider \langle a_{1,2},\dots,a_{d,2}\rangle_{\mathcal{H}}=\{a_{i,2}\}_{i=1}^{d}. Then N(\gamma;\{a_{i,2}\}_{i=1}^{d},\rho)=d\quad\text{and}\quad N(\gamma^{\prime};\langle a_{1,2},\dots,a_{d,2}\rangle_{\mathcal{H}},\rho)\leq d. Since this holds for all d\in\mathbb{N} , we conclude that C_{\gamma}^{\gamma^{\prime}}(\mathcal{H})=\infty . Case 3: \gamma\in(0,\varepsilon_{1}) and \gamma^{\prime}\in(0,\varepsilon^{\prime}) . In this regime, \mathcal{H} is generatable in the limit by Theorem 4.6 . Define \mathcal{H}_{1}=\{h_{I}:I\in\mathcal{I},J\in\mathcal{I}_{\text{fin}}\ \operatorname{supp}(h_{I})=D_{I,J}\},\qquad\mathcal{H}_{2}=\{h_{I}:I\in\mathcal{I},\ \operatorname{supp}(h_{I})=O_{I}\}. It is straightforward to verify that all assumptions of Lemma C.1 are satisfied. Therefore, \mathcal{H} is not non-uniformly generatable. Case 4: \gamma^{\prime}\in[\varepsilon^{\prime},r] . This case follows by the same reasoning as the third case of Example 4.8 , and we omit the details. ∎ C.5 Proof of Example 4.11 Proof. Assume \varepsilon=1 for simplicity. Define the weight sequence \{\delta_{n}\}_{n=1}^{\infty} by \delta_{n}=\begin{cases}\frac{1}{4}&\text{if }n\text{ is even},\\ 1&\text{if }n\text{ is odd}.\end{cases} Suppose x,y\in\ell^{2} , where x=\{x_{i}\}_{i=1}^{\infty} and y=\{y_{i}\}_{i=1}^{\infty} . Then define the weighted \ell^{2} metric \rho^{\prime} by \rho_{2}^{\prime}(x,y)=\left(\sum_{i=1}^{\infty}\delta_{i}\cdot(x_{i}-y_{i})^{2}\right)^{1/2}. Let m,k\in\mathbb{N},a_{m,k}\in\ell^{2} such that a_{m,k}=\frac{\sqrt{2}}{2^{m}}\cdot e_{k} . Let \mathcal{I} be the set of all infinite subsets of \mathbb{N} , i.e., \mathcal{I}=\{I|I\in 2^{\mathbb{N}},|I|=\infty\} . For I\in\mathcal{I} , let A_{mI}=\{a_{m,2^{n}\cdot(2k+1)}\ |\ k\in I,n\geq 0\}. Construct the hypothesis class \mathcal{H} such that \mathcal{H}=\left\{h_{\mathbf{I}}\;\middle|\;\mathbf{I}=(I_{i})_{i\in\mathbb{N}}\in\mathcal{I}^{\mathbb{N}},\ \operatorname{supp}(h_{\mathbf{I}})=\bigcup_{i=1}^{\infty}A_{iI_{i}}\right\} It is clear that it satisfies 1-UUS property. We now show that for any \tau<1 , it is (\tau,\tau) -uniformly generatable with respect to \rho . Thus we only need to show that C_{\tau}^{\tau}(\mathcal{H})<\infty . Suppose \frac{1}{2^{m}}\leq\tau<\frac{1}{2^{m-1}} for some m\in\mathbb{N} . Observe that for any k_{1},k_{2},m_{1},m_{2}\in\mathbb{N} such that m_{1},m_{2}>m , \rho(a_{m_{1},k},a_{m_{2},k^{\prime}})<\frac{1}{2^{\min(m_{1},m_{2})-1}}\leq\frac{1}{2^{m}}, thus for a sequence \{x_{i}\}_{i=1}^{t}\subset\operatorname{supp}(h) , if N(\tau;\{x_{i}\}_{i=1}^{t},\rho)\geq 2 , there must exists s\tau,\quad\forall n_{1},n_{2}\in\mathbb{N},\quad n_{1}\neq n_{2}, it then holds that N(\tau;\langle x_{1},\dots,x_{t}\rangle_{\mathcal{H}},\rho)=\infty , which induces C_{\tau}^{\tau}(\mathcal{H})\leq 2 . Now we show that \mathcal{H} is not (\tau,\tau) -non-uniformly generatable with respect to \rho^{\prime} for any \tau<1 . Suppose \frac{1}{2^{m}}\leq\tau<\frac{1}{2^{m-1}} for some m\in\mathbb{N} . Let \displaystyle\mathcal{H}_{1}= \displaystyle\left\{h_{I}\,\middle|\,I\in\mathcal{I},\ \operatorname{supp}(h_{I})=A_{mI}\right\}, \displaystyle\mathcal{H}_{2}= \displaystyle\left\{h_{\mathbf{I}}\,\middle|\,\mathbf{I}=(I_{i})_{i\in\mathbb{N},\,i\neq m}\in\mathcal{I}^{\mathbb{N}},\ \operatorname{supp}(h_{\mathbf{I}})=\bigcup_{i=1,\,i\neq m}^{\infty}A_{iI_{i}}\right\}. Then \mathcal{H}=\mathcal{H}_{1}+\mathcal{H}_{2} . We again use Lemma C.1 to prove that \mathcal{H} is not (\tau,\tau) -non-uniformly generatable in the limit with respect to \rho^{\prime} . First, we apply Lemma C.2 to show that \mathcal{H}_{1} is not (\tau,\tau) -generatable in the limit with respect to \rho^{\prime} . Let \{x_{i}\}_{i=1}^{\infty}\subseteq\mathcal{X} be defined by x_{1}=a_{m,3},\quad x_{2}=a_{m,6},\quad x_{i}=a_{m,\,2i-1}\ \text{for }i\geq 3. We denote by B^{\prime}(x,\tau) the \tau -ball of x with respect to \rho^{\prime} . Observe that for k,k^{\prime}\in\mathbb{N} with k\neq k^{\prime} , if both k and k^{\prime} are even, then \rho^{\prime}(a_{m,k},a_{m,k^{\prime}})=\frac{1}{2^{m}}\leq\tau. Consequently, \{\,a_{m,\,2^{n}(2k+1)}\mid k\in\mathbb{N},\ n\geq 1\,\}\subseteq B^{\prime}(x_{2},\tau), since 2^{n}(2k+1) is even for all n\geq 1 . For h\in\mathcal{H}_{1} , if \operatorname{supp}(h)=A_{mI} with I=\{1,i_{1},i_{2},i_{3},\dots\}\subseteq\mathbb{N} indexed so that i_{k}1 , then x_{i_{k}+1}=a_{m,2i_{k}+1} , thus \{a_{m,\,2i+1}:i\in I\}=\{x_{1}\}\cup\{x_{i_{k}+1}\}_{k\geq 1}. As a result, we have \{x_{1},x_{2}\}\cup\{x_{i_{k}+1}\}_{k\geq 1}\subseteq\operatorname{supp}(h)\subseteq B^{\prime}\big(\{x_{1},x_{2}\}\cup\{x_{i_{k}+1}\}_{k\geq 1},\tau\big). Therefore, by Lemma C.2 , \mathcal{H}_{1} is not \tau -generatable in the limit with respect to \rho^{\prime} . Finally, let I_{1}=\{3^{n}\}_{n=1}^{\infty} and I_{2}=\{5^{n}\}_{n=1}^{\infty} , let \operatorname{supp}(h_{2j})=\bigcup_{i=1,i\neq m}^{\infty}A_{iI_{j}},\quad j=1,2. Then, \operatorname{supp}(h_{21})\bigcap\operatorname{supp}(h_{22})=\emptyset. Note that \mathcal{H}_{1} is not (\tau,\tau) -generatable in the limit, and \mathcal{H}_{2} contains two hypotheses with disjoint supports. Therefore, all the three conditions of Lemma C.1 are satisfied, thus \mathcal{H} is not \tau -non-uniformly generatable in the limit with respect to \rho^{\prime} . ∎ Appendix D Other Technical Details D.1 Proofs Related to the UUS Property This subsection collects short proofs establishing a basic monotonicity result for the UUS property in general metric spaces, as well as a stronger scale-invariance result in doubling spaces. We first show that the UUS property is monotone in the scale parameter. Proof of Lemma 2.1 . If \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} is a class satisfying the r -UUS property, then for any h\in\mathcal{H} , for any finite sequence \{x_{i}\}_{i=1}^{N} , we have \operatorname{supp}(h)\not\subseteq B(\{x_{i}\}_{i=1}^{N},r) , thus \operatorname{supp}(h)\not\subseteq B(\{x_{i}\}_{i=1}^{N},\delta) . As a result, N(\delta;\operatorname{supp}(h),\rho)=\infty , so \mathcal{H} satisfies the \delta -UUS property. ∎ The previous lemma shows monotonicity of the UUS property in the scale parameter. Under the additional assumption that (\mathcal{X},\rho) is doubling, we now show that UUS is in fact scale-invariant. Proof of Lemma 4.1 . Since \mathcal{H} satisfies the r -UUS property, for any h\in\mathcal{H} we have N(r;\operatorname{supp}(h),\rho)=\infty. Because \mathcal{X} is doubling, the covering number of a set is infinite at one scale if and only if it is infinite at any other scale. Therefore, for any r^{\prime}>0 , N(r^{\prime};\operatorname{supp}(h),\rho)=\infty, which shows that \mathcal{H} satisfies the r^{\prime} -UUS property. ∎ D.2 Recovering the Countable Framework This subsection shows that our metric-space formulation strictly generalizes the countable example space model studied in 21 . In particular, when the instance space is equipped with the discrete metric at a sufficiently small scale, our notions of novelty, coverage, and generatability reduce exactly to their counterparts in the countable setting. Thus, all generatability notions considered in this paper are consistent with the classical framework. Proposition D.1 . Let \mathcal{X} be a countable set equipped with the discrete metric \rho(x,y)=\begin{cases}1,&x\neq y,\\ 0,&x=y.\end{cases} Let r<1 and 0<\varepsilon,\varepsilon^{\prime}\leq r . Suppose \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} satisfies the r -UUS property. Then \mathcal{H} is (\varepsilon,\varepsilon^{\prime}) -generatable in the limit (respectively, (\varepsilon,\varepsilon^{\prime}) -non-uniformly generatable, (\varepsilon,\varepsilon^{\prime}) -uniformly generatable) if and only if \mathcal{H} is generatable in the limit (respectively, non-uniformly generatable, uniformly generatable) in the sense of 21 (see Appendix A for the definitions). Proof sketch. Under the discrete metric and the assumption r<1 , every \varepsilon -ball with \varepsilon\leq r reduces to a singleton. As a result, \varepsilon -coverings coincide with set-theoretic coverings, and the notions of novelty and coverage in Definition 2.5 reduce exactly to those in 21 . The equivalence follows by direct comparison of definitions. ∎ D.3 Other Proofs in Section 4 This subsection collects proofs in Section 4 , showing how generatability properties behave under changes of scale and metric. We first establish that, in doubling metric spaces, generatability is invariant under equivalent metrics via the closure dimension. We then show that, in general metric spaces, generatability notions are monotone with respect to the novelty parameters and are stable under Lipschitz changes of the metric, with appropriate rescaling of parameters. Proof of Theorem 4.4 . Choose any \varepsilon,\varepsilon^{\prime}>0 , denote \operatorname{C}_{\varepsilon,1}^{\varepsilon^{\prime}}(\mathcal{H}) and \operatorname{C}_{\varepsilon,2}^{\varepsilon^{\prime}}(\mathcal{H}) as the (\varepsilon,\varepsilon^{\prime}) -closure dimension of \mathcal{H} with respect to \rho_{1} and \rho_{2} . By Theorem 3.1 and 3.3 , we only need to show that \operatorname{C}_{\varepsilon,1}^{\varepsilon^{\prime}}(\mathcal{H})<\infty if and only if \operatorname{C}_{\varepsilon,2}^{\varepsilon^{\prime}}(\mathcal{H})<\infty . Since \mathcal{X} is a doubling space and \rho_{1} is equivalent with \rho_{2} , for any subset A\subseteq\mathcal{X} , N(\varepsilon;A,\rho_{1})=\infty\iff N(\varepsilon;A,\rho_{2})=\infty. and if N(\varepsilon;A,\rho_{1})<\infty , there must exists C_{1},C_{2}\in\mathbb{R}_{+} such that C_{1}N(\varepsilon;A,\rho_{1})\leq N(\varepsilon;A,\rho_{2})\leq C_{2}N(\varepsilon;A,\rho_{1}). Comparing with the definition of closure dimension completes the proof. ∎ Proof of Theorem 4.6 . Suppose \mathcal{H} is (\varepsilon,\varepsilon^{\prime}) -generatable in the limit, and let \mathcal{G} be an (\varepsilon,\varepsilon^{\prime}) -generator. We show that \mathcal{G} is also a (\delta,\delta^{\prime}) -generator, which implies that \mathcal{H} is (\delta,\delta^{\prime}) -generatable in the limit. Let \{x_{i}\}_{i=1}^{\infty}\subseteq\operatorname{supp}(h) be a sequence such that \operatorname{supp}(h)\subseteq\bigcup_{i=1}^{\infty}B(x_{i},\delta). Since \delta\leq\varepsilon , we also have \operatorname{supp}(h)\subseteq B\!\left(\{x_{i}\}_{i=1}^{\infty},\varepsilon\right). By the definition of an (\varepsilon,\varepsilon^{\prime}) -generator, there exists s such that for all t\geq s , \mathcal{G}(x_{1:t})\in\operatorname{supp}(h)\setminus B\!\left(\{x_{i}\}_{i=1}^{t},\varepsilon^{\prime}\right). Since \varepsilon^{\prime}>\delta^{\prime} , it follows that \mathcal{G}(x_{1:t})\in\operatorname{supp}(h)\setminus B\!\left(\{x_{i}\}_{i=1}^{t},\delta^{\prime}\right). This completes the proof. ∎ Proof of Theorem 4.7 . We prove the result for uniform generatability; the non-uniform case follows by an analogous argument. Suppose \mathcal{H} is (\varepsilon,\varepsilon^{\prime}) -uniformly generatable, and let \mathcal{G} be an (\varepsilon,\varepsilon^{\prime}) -uniform generator. Let d\in\mathbb{N} be the smallest integer such that for any sequence \{x_{i}\}_{i=1}^{\infty}\subseteq\operatorname{supp}(h) , if there exists t with N(\varepsilon;\{x_{i}\}_{i=1}^{t},\rho)\geq d, then \mathcal{G}(x_{1:s})\in\operatorname{supp}(h)\setminus B\!\left(\{x_{i}\}_{i=1}^{s},\varepsilon^{\prime}\right)\quad\text{for all }s\geq t. We show that \mathcal{G} is also a (\delta,\delta^{\prime}) -uniform generator. Fix any sequence \{x_{i}\}_{i=1}^{\infty}\subseteq\operatorname{supp}(h) and suppose that for some t , N(\delta;\{x_{i}\}_{i=1}^{t},\rho)\geq d. Since \delta\geq\varepsilon , it follows that N(\varepsilon;\{x_{i}\}_{i=1}^{t},\rho)\geq d. By the definition of \mathcal{G} , for all s\geq t we therefore have \mathcal{G}(x_{1:s})\in\operatorname{supp}(h)\setminus B\!\left(\{x_{i}\}_{i=1}^{s},\varepsilon^{\prime}\right). Because \varepsilon^{\prime}>\delta^{\prime} , this implies \mathcal{G}(x_{1:s})\in\operatorname{supp}(h)\setminus B\!\left(\{x_{i}\}_{i=1}^{s},\delta^{\prime}\right). This completes the proof. ∎ Proof of Theorem 4.10 . We write B_{1}(x,\varepsilon) and B_{2}(x,\varepsilon) for the \varepsilon -balls centered at x with respect to \rho_{1} and \rho_{2} , respectively. First observe that for any x\in\mathcal{X} and \gamma>0 , B_{1}\!\left(x,\frac{\gamma}{M}\right)\subseteq B_{2}(x,\gamma). Consequently, for any h\in\mathcal{H} , if N(\rho_{2};\operatorname{supp}(h),r)=\infty, then N(\rho_{1};\operatorname{supp}(h),r/M)=\infty. Thus, \mathcal{H} satisfies the (r/M) -UUS property with respect to \rho_{1} . Now suppose \mathcal{G} is an (\varepsilon,\varepsilon^{\prime}) -generator for \mathcal{H} with respect to \rho_{2} . We show that \mathcal{G} is also an (\varepsilon/M,\varepsilon^{\prime}/M) -generator with respect to \rho_{1} . Let \{x_{i}\}_{i=1}^{\infty}\subseteq\operatorname{supp}(h) be a sequence such that \operatorname{supp}(h)\subseteq B_{1}\!\left(\{x_{i}\}_{i=1}^{\infty},\varepsilon/M\right). By the inclusion above, this implies \operatorname{supp}(h)\subseteq B_{2}\!\left(\{x_{i}\}_{i=1}^{\infty},\varepsilon\right). Therefore, there exists s such that for all t\geq s , \mathcal{G}(x_{1:t})\in\operatorname{supp}(h)\setminus B_{2}\!\left(\{x_{i}\}_{i=1}^{t},\varepsilon^{\prime}\right). Since B_{1}\!\left(x,\varepsilon^{\prime}/M\right)\subseteq B_{2}(x,\varepsilon^{\prime}), it follows that \mathcal{G}(x_{1:t})\in\operatorname{supp}(h)\setminus B_{1}\!\left(\{x_{i}\}_{i=1}^{t},\varepsilon^{\prime}/M\right). This completes the proof. ∎ Appendix E Remarks on Computability There are few remarks on the algorithms on generation in the limit in the countable example space setting [ 13 , 21 , 6 ] . We point out that the algorithm by 13 for generation in the limit which only uses the oracle “is x\in\operatorname{supp}(h) ” is not directly extendable to the metric space setting. Because it explicitly uses the countable structure of the example space, as well as the countable structure of the hypothesis class. We leave the extension as an open problem. However, the algorithm in Appendix I by 21 which uses an ERM oracle can be extended with some modification. From our definition, \langle x_{1},\dots,x_{n}\rangle_{\mathcal{H}} is the set of positive examples common to all hypothesis in the version space of \mathcal{H} consistent with the sample (x_{1},1),\dots,(x_{n},1). From this perspective, one can check closure membership, i.e. given an example x and a generatable sequence \{x_{1},\dots,x_{n}\} , return \mathds{1}\{x\in\langle x_{1},\dots,x_{n}\rangle_{\mathcal{H}}\} , using access to an Empirical Risk Minimization (ERM) oracle. Formally, an ERM oracle is a mapping \mathcal{O}:2^{\{0,1\}^{\mathcal{X}}}\times(\mathcal{X}\times\{0,1\})^{\star}\rightarrow\mathbb{N}\cup\{0\} , which given a class \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} and a labeled sample S\in(\mathcal{X}\times\{0,1\})^{\star} , outputs \min_{h\in\mathcal{H}}\sum_{(x,y)\in S}\mathds{1}\{h(x)\neq y\}. Then, given a class \mathcal{H} , a generatable sequence \{x_{1},\dots,x_{n}\} , one can compute \mathds{1}\{x\in\mathds{1}\{\langle x_{1},\dots,x_{n}\rangle_{\mathcal{H}}\} using the following procedure: Define the sample S_{x}=\{(x_{1},1),\dots,(x_{n},1),(x,0)\}. Query \mathcal{O} on S_{x} and \mathcal{H} and let r_{x} be its output. Output r_{x} . To see why this works, suppose r_{x}=0 . Then, that means there exists a hypothesis h\in\mathcal{H} such that \{x_{1},\dots.x_{n}\}\subseteq\operatorname{supp}(h) but x\notin\operatorname{supp}(h) . Thus, it cannot be the case that x\in\langle x_{1},\dots,x_{n}\rangle_{\mathcal{H}}. On the other hand, if r_{x}=1 , then it must mean that for every h\in\mathcal{H} such that \{x_{1},\dots,x_{n}\}\subseteq\operatorname{supp}(h) , we have that h(x)=1 . Accordingly, x\in\langle x_{1},\dots,x_{n}\rangle_{\mathcal{H}} by definition. The generator described in Lemma B.2 can be efficiently implemented given access to a max–min oracle \mathcal{O}_{\emph{max-min}}:2^{\{0,1\}^{\mathcal{X}}}\times\mathcal{X}^{\star}\to\mathcal{X}, together with oracle access to the metric. Given a hypothesis class \mathcal{H}\subseteq\{0,1\}^{\mathcal{X}} and a finite sequence of examples x_{1},\dots,x_{t} , the oracle \mathcal{O}_{\emph{max-min}} returns \argmax_{x\in\mathcal{X}\setminus B(\{x_{i}\}_{i=1}^{t},\varepsilon^{\prime})}\;\min_{h\in\mathcal{H}}\sum_{i=1}^{t}\mathds{1}\{h(x_{i})\neq 1\}+\mathds{1}\{h(x)\neq 0\}. The inner minimization coincides with the output of an empirical risk minimization (ERM) oracle \mathcal{O}_{\mathrm{ERM}} as described above. Consequently, the max–min oracle can be equivalently written as \mathcal{O}_{\emph{max-min}}(\mathcal{H},x_{1:t})=\argmax_{x\in\mathcal{X}\setminus B(\{x_{i}\}_{i=1}^{t},\varepsilon^{\prime})}\;\mathcal{O}_{\mathrm{ERM}}\!\big(\mathcal{H},\{(x_{1},1),\dots,(x_{t},1),(x,0)\}\big). The generator in Lemma B.2 can therefore be implemented using a single call to the max–min oracle at each round. To see this, suppose that t\geq\operatorname{C}(\mathcal{H})+1 . Since N(\varepsilon^{\prime};\langle x_{1},\dots,x_{t}\rangle_{\mathcal{H}},\rho)=\infty , it follows that \langle x_{1},\dots,x_{t}\rangle_{\mathcal{H}}\setminus B(\{x_{i}\}_{i=1}^{t},\varepsilon^{\prime})\neq\emptyset, and moreover, for every x\in\langle x_{1},\dots,x_{t}\rangle_{\mathcal{H}}\setminus B(\{x_{i}\}_{i=1}^{t},\varepsilon^{\prime}) , \mathcal{O}_{\mathrm{ERM}}\!\big(\mathcal{H},\{(x_{1},1),\dots,(x_{t},1),(x,0)\}\big)\geq 1. As a result, \max_{x\in\mathcal{X}\setminus B(\{x_{i}\}_{i=1}^{t},\varepsilon^{\prime})}\;\mathcal{O}_{\mathrm{ERM}}\!\big(\mathcal{H},\{(x_{1},1),\dots,(x_{t},1),(x,0)\}\big)\geq 1, and thus the oracle \mathcal{O}_{\emph{max-min}}(\mathcal{H},x_{1:t}) returns a point \hat{x}_{t}\in\mathcal{X}\setminus B(\{x_{i}\}_{i=1}^{t},\varepsilon^{\prime}) such that \mathcal{O}_{\mathrm{ERM}}\!\big(\mathcal{H},\{(x_{1},1),\dots,(x_{t},1),(\hat{x}_{t},0)\}\big)\geq 1. Such a point \hat{x}_{t} must therefore belong to \langle x_{1},\dots,x_{t}\rangle_{\mathcal{H}} , completing the proof. If we insist on using only an ERM oracle, then the max–min oracle is unattractive, as it may require uncountably many ERM calls per round. Instead, fix a countable dense subset (y_{i})_{i\geq 1} of \mathcal{X} . When t\geq\operatorname{C}(\mathcal{H})+1 , we can search over (y_{i}) and invoke only finitely many ERM calls before returning: Input: x_{1},\dots,x_{t}\in\mathcal{X} for i=1,2,3,\dots do 1 if y_{i}\notin B(\{x_{j}\}_{j=1}^{t},\varepsilon^{\prime}) then 2 if \mathcal{O}_{\mathrm{ERM}}\!\big(\mathcal{H},\{(x_{1},1),\dots,(x_{t},1),(y_{i},0)\}\big)\geq 1 then 3 return y_{i} end if 4 end if 5 end for 6 Algorithm 1 Search over a dense subset using ERM Under the condition t\geq\operatorname{C}(\mathcal{H})+1 , the above procedure is guaranteed to stop after finitely many iterations. In this regime, only finitely many calls to the ERM oracle are required in each round. When t<\operatorname{C}(\mathcal{H})+1 , however, the procedure may fail to terminate, and in particular it is not clear whether one can always implement the generator using only finitely many ERM oracle calls per round. Whether such a finite-ERM implementation exists in general remains an open problem.